A Hidden-picture Puzzles Generator

1 Pacific Graphics 2008T. Igarashi, N. Max, and F. Sillion(Guest Editors)Volume 27(2008),Number 7A Hidden-picture Puzzles GeneratorJong-Chul Yoon,1In-Kwon Lee1and Henry Kang21 Dept. of Computer Science, Yonsei University2 Dept. of Mathematics and Computer Science, University of Missouri, St. LouisAbstractA Hidden-picture puzzle contains objects hidden in a background image, insuch a way that each object fits closelyinto a local region of the background. Our system converts image of the background and objects into line drawing,and then finds places in which to hide transformed versions of the objects using rotation-invariant shape contextmatching. During the hiding process, each object is subjected to a slight deformation to enhance its similarity tothe background. The results were assessed by a panel of and Subject Descriptors(according to ACM CCS) [Computing Methodologies]: ComputerGraphics-Applications [Computer Applications]: Arts and Humanities1.

2 IntroductionA Hidden-picture puzzle consists of a background picturein which several extraneous graphical objects are generate such a puzzle, an artist first sketches the back-ground and the hidden objects, and then draw them as a co-herent whole so that the hidden objects are not easily notice-able. Hidden-picture Puzzles have been widely used for ed-ucational, commercial, and entertainment purposes, appear-ing regular items in newspapers and magazines, and on theweb [Mal99]. Like many other types of puzzle, they not onlyprovide amusement but also help improve the visual skills ofthe to Ball [Bal08], a well-known designer ofhidden-picture Puzzles , a range of skills are required to gen-erate these Puzzles , including shape recognition, spatial per-ception, eye coordination, memory, concentration, creativityand imagination.

3 This motivates our development of an au-tomatic puzzle generation example of Hidden-picture Puzzles drawnby Ball which exhibit typical properties of hidden -picturepuzzles: Image abstraction: Hidden-picture Puzzles are typicallyline drawings (Figure1(a)) or cartoons with simplifiedcolors (Figure1(b)). Shape similarity: The background must be complicatedenough to hide the objects easily. Also, the shapes of the(a)(b)Figure1: hidden -picturepuzzlesdr awnbyBall( ): (a) Hidden-picture puzzle ina line-drawing style; (b) colored Hidden-picture puzzle witha limited number of object, after some geometric modification, must besimilar to the adjacent region of the background. Shape modification: The transformations and deforma-tions used to increase the shape similarity must not de-stroy the identity of the have designed an automatic system to generate ahidden-picture puzzle (see Figure2) that satisfies theseproperties.

4 We start by converting photographs of poten-tial hidden objects to line drawings and store them in anobject database. The input image is also converted into ac 2008 The Author(s)Journal compilationc 2008 The Eurographics Association and Blackwell by Blackwell Publishing, 9600 Garsington Road, Oxford OX4 2DQ, UK and350 Main Street, Malden, MA 02148, Yoon, In-Kwon Lee & Henry Kang / A Hidden-picture Puzzles Generatorline drawing (or a colored abstraction). For each objectin the database, the system searches an appropriate loca-tion in the background image at which to conceal it, usingtransformation-invariant shape matching. The system thenselects the best matches between candidate objects and loca-tion. The objects with the best matches are then transformed,deformed and embedded in the background image to com-plete the inputBackground imageObject DatabaseLine drawing.

5 Candidate ObjectsShape MatchingShape DeformationObjectResult TransformationFigure 2:System Related Image StylizationExisting methods for image stylization mainly focus on aes-thetic improvement of an image. For example, stroke-basedrendering techniques [SWHS97,Her01,GCS02,DOM 01,HE04] re-renders image in a non-photorealistic style by fill-ing its region with certain types of strokes. Image abstrac-tion or tooning [DS02,WXSC04,CRH05,WOG06] pro-vides stylization via image segmentation and line system adopts the cartoon-like abstraction style to imi-tate hand-drawn hidden picture Puzzles . As an image puz-zle Generator , our work is also related to the image styl-ization algorithms that are driven by puzzle-like proper-ties [KP02,XK07b,XKM07,XK07a]. Shape MatchingVeltkamp and Hagedoorn [VH01] suggest that the shapematching of images can be roughly classified into bright-ness and feature based methods.

6 Brightness-based meth-ods [CTCG95,VJP97] assume that the intensity of each pixelin the image is a feature descriptor, albeit modified by fac-tors such as the poses of the objects depicted in the imageand illumination changes. Feature-based methods recognizeshapes in an image from the spatial configurations of a muchsmall number of features. Lowe s SIFT descriptor [Low03]is well-known, and has been widely used in various applica-tions. The relations among contours (or silhouettes) in an im-age can also be used as shape descriptors [HKR93,LLE00],and Berg et al. [BBM05] introduced geometric blur for ro-bust template matching under affine we need to determine the similarity betweenmany possible regions in our background image and eachhidden object in the object database, a fast matchingmethod is required which is also therefore selected the shape context method of match-ing [BMP02], which is simple but effective.

7 As originallyproposed, a shape context is translation- and scale-invariant;we have improved the method slightly by adding rotation-invariance (see ).3. Preprocessing Converting the Input Image to a Line drawingWe use the coherent line drawing (CLD) method by Kanget al. [KLC07] to generate coherent, smooth, and attractiveline drawings of the background (Figure3) and of the objectsto be CLD method calculates the edge tangent vector flow,then uses the flow-based difference of Gaussians (FDoG)filter for edge detection, with iterative adjustments to en-hance the continuity of edges. In our case, we apply CLDmethod on the input image to create the initial backgroundimage. Then after all the hidden objects are embedded intothe background image, we apply CLD method again on thecombined image to recalculate the edges. This re-processingof the edges makes the objects look more naturally blendedin the background and less conspicuous.

8 This is essential notonly for the quality of final illustration but also for the diffi-culty of the puzzle.(a)(b)Figure 3:(a) Input background image; (b) line drawing ofthe Object DatabaseWe constructed a database of objects (to be hidden ) froma set of arbitrary images. We convert these images into line-drawings using the CLD method. We then manually segmentout the objects and put the line-drawing images of the seg-mented objects in the object database. In our experiments,we use the database of one hundred line-drawing images,each with a resolution of 300 300. To improve the like-lihood of good matches, mirror images of the objects wereadded to the 2008 The Author(s)Journal compilationc 2008 The Eurographics Association and Blackwell Yoon, In-Kwon Lee & Henry Kang / A Hidden-picture Puzzles Generator4. Shape MatchingConsider a background imageBin which one objectOis tobe hidden .

9 We need to find a good match between a region inBand a copy ofOthat may be transformed by some combi-nation of translation, rotation, and scaling. Exhaustive searchof all possible configurations is infeasible. Instead, we com-pute transformation-invariant shape descriptors ofO, and asufficient numbers of candidate regions inB. The similaritybetweenOand each candidate region inBcan then be com-puted efficiently using the shape Rotation-Invariant Shape ContextThe shape descriptors used in our system are based onthe concept of shape context [BMP02], which abstracts theshape of a point cloud. The shape context consists of a smallnumber of histograms which express the spatial relation-ships among the points representing the shape, and allow apossible match between two given shapes to be evaluatedquickly. The use of directional relationships and relative dis-tances between the points makes the shape context scale- first extract the feature pointspi,(i=1.)

10 ,N)fromthe object imageOusing the well-known Harris corner de-tection method [HS98] (see Figure4(b)). Then,Ndifferentshape contexts ofOexist, each of which is computed withrespect to each feature point. Considering a range of dis-tances and directions from a specific center pointpi, the areacovered by the bounding circle (with centerpi) of the pointcloud can be subdivided into several bins ( , 32 bins in Fig-ure4(c)). The shape context ofOwith respect to the specificpiis then determined by counting the number of points ineach bin, which is effectively a two-dimensional histogramexpressing the distance and direction of the other points problem with the original version of shape con-text [BMP02] is that the histogram is not other words, the shape contexts of two differently orientedversion of an object are likely to be different, even thoughcomputed with respect to the same point.