U.S. Pat. No. 7,878,891

DETAILED DESCRIPTION OF THE INVENTION

Polyominoes and Photominoes Basics

As described above, polyominoes are generalizations of dominoes, as they are geometric game pieces constructed from connecting n square blocks together with adjacent edges and corners aligned.

FIG. 1shows variations in shape of tetrominoes. Tetrominoes are polyominoes for n=4, where n is the number of squares of the polyomino. For tetrominoes, there are seven piece types modulo, or without, rotations. The names of these pieces are I, J, L, O, S, T, and Z, which relate to the shapes of their corresponding pieces, are shown inFIG. 1.

Regarding rotations, if looking at a particular tetromino on an x-axis and y-axis of a screen, for example, a rotation is a ninety-degree turn around a z-axis that theoretically would be coming straight out of the screen. Thus, for each piece, there could be up to three non-trivial rotations in ninety-degree increments at ninety degrees, 180 degrees and 270 degrees from the original position of the piece. For example, the “O” piece has no rotations because any of these three rotations yields the same shape. The “T” piece, on the other hand, has three rotations.

Regarding flips, there are two sets of pieces that are “flips” of each other. The “L” and “J” pieces are flips or mirrors of each other, and “S” and “Z” pieces are flips of each other.

These seven tetrominoes do not admit a perfect tiling of a rectangle, so tetrominoes do not yield the most elegant jigsaw puzzles. It is possible, however, to tile a rectangle with various combinations of tetrominoes, such as an eight by five rectangle using ten pieces. In addition to jigsaw puzzles, the games that are inextricably associated with tetrominoes are the “falling blocks” video games, such as Tetris.

FIG. 2shows variations in shape of pentominoes. Pentominoes are polyominoes for n=5, where n is the number of squares in the polyomino. For pentominoes, there are twelve piece types modulo, or without, rotations and flips. The names of these pieces are F, I, L, N, P, T, U, V, W, X, Y, and Z, which relate to the shapes of their corresponding pieces, are shown inFIG. 2.

These twelve pentominoes admit a tiling of a rectangle and yield an elegant jigsaw puzzle. The solutions are not unique. For example, for a ten by six rectangle, there are 2,339 solutions. In embodiments, it is possible to have a variation of a “falling blocks” video game based on pentominoes, but the game may be a bit too unwieldy or difficult to play.

“Photominoes” are polyomino game pieces constructed and rendered from visually salient parts detected in photos or images. Photominoes can be computed from either image streams or from a fixed image set, where an image is one frame of an image stream, or video sequence, and a fixed image set is a set of photos. Although either photos or images can be used with the process, for purposes of clarity and brevity the term “image” will be used hereinafter to refer to both terms “photo” and “image.”

In embodiments, it is possible to generate photominoes from videos by extracting keyframes and making photominoes out of these images. It is also possible to generate Photominoes from slides, for example PowerPoint, and other kinds of images.

Generating Photominoes for Video Games

FIG. 3is a flowchart of a process for generating photominoes as used in a video game, according to embodiments. Photominoes can be defined as polyominoes rendered with salient parts detected from photos or images. Photominoes in the case of n=4 are photo tetrominoes. Photo tetrominoes can be used to produce photo-based variations of games such as “falling blocks” video games, such as Tetris. In embodiments, the following process, however, is for the more general version of generating photo polyominoes for any video game. Thus, these embodiments include polyomino cases for n of any positive integer. Further, in embodiments, even within the same game, the number n for each polyomino can vary.

The process starts in step300. For purposes of constructing photominoes, a computer program keeps an enumerated list of the polyomino of size=n piece types, including piece types obtained by rotations and flips. Let P* denote this expanded list. For example, for a polyomino of n=4, or tetrominoes, P* is the set of basic piece types and flips shown inFIG. 1, plus all combinations of rotations and flips of these pieces. In step310, a template is constructed for each piece type in the P* list from the computer program. In step320, the weight of each piece type from step310is initialized to the same weight.

In step330, the process waits for a game piece request from the video game application as dictated by the action of the game until the game ends. As the process waits, a sequence of player actions and game events continues. At some point of the play, a game piece may be needed in the application, and the video game application requests a photomino from a photomino software module. If the game does not end in step340, then a game piece request was received from the video game application.

In step350an image is randomly chosen from a photo repository, and the image's saliency map is computed. In embodiments, the photo repository can be created by a user through a user interface, in which the user downloads images to the repository and selects images from the repository. In embodiments, the photomino software module uses a default directory of images on a personal computer, such as the “My Pictures” directory, if the application is running on a personal computer, for example. A stream of photominoes will be generated one at a time from this repository of images, rather than computing all the game pieces at once.

For each image, a saliency map is computed. The saliency map can be expressed as a real-valued function on points or block areas in the image. For example, a rectangular image can be partitioned into areas by dividing it evenly into an 8×8 grid of blocks. The saliency value of a block can be computed based on low-level image features such as texture, color, and shape, as well as on high-level features such as a face detected in the image. The saliency value of a block can also be computed based on heuristics such as the center of a photograph being more likely to be important, where in heuristics the most appropriate solution of several found by alternative methods is selected at successive stages of a program for use in the next step of the program. Currently, there are various methods to compute the saliency map. In the preferred embodiment a proprietary method is used.

FIGS. 4A-4Hshow examples of images and photo tetrominoes created from corresponding salient parts of the images, according to embodiments, using methods as described for step350ofFIG. 3. For example, one salient part of the image ofFIG. 4Adetected by the proprietary method is the region at which the branches meet the trunk of the tree. This salient part ofFIG. 4Ais shown in the “T” photo tetromino inFIG. 4B. InFIG. 4C, one salient part of the image is the two men, who are shown in the “Z” photo tetromino inFIG. 4D. InFIG. 4E, one salient part of the image is the large flower directly in the center of the image. InFIG. 4F, the flower is shown in the “L” photo tetromino, rotated ninety degrees to the left from the “L” shown inFIG. 1. InFIG. 4G, one salient part of the image is the building on the right in the forefront of the image. This building is shown in the “O” photo tetromino ofFIG. 4H.

Returning toFIG. 3, in step360, the template and location with the highest weighted saliency score are found. For templates from the set of piece types P*, the basic idea is to slide templates over the image chosen in step350to find the combination of template and template location with the best saliency score. A template location is the location on the image over which the template lies. For each template and template location combination, the corresponding saliency score is calculated by multiplying the saliency score of the template at the template location by the weight of the template piece type.

In embodiments, because the saliency map computation and template matching may not be what a particular user subjectively perceives to be the best template and location for an image, in embodiments, a user interface can be provided for adjusting the location of templates and images. The user interface could include other operations such as scaling, rotating and flipping, according to embodiments. In embodiments, users can select the template type for a particular photo. The extent to which these techniques are helpful will also depend on the particular game.

In embodiments, weighting is not used in the process. The process is a random process, with or without weighting. The process is random because of the random selection of an image when getting the next image in step350. If weighting is not used, then steps320and390are unnecessary. Additionally, in step360, the template and location with the highest saliency score are found without consideration of weighted game pieces.

In step370, the photomino game piece is rendered into a sprite using the template as a mask over the image at the location on the image found in step360. A sprite is a two-dimensional image that is integrated into a larger scene, in this case the video game. In embodiments, the mask is in the shape of the game piece. In embodiments, since it is often easier to implement rectangular graphical objects for the video game, the game piece could be rectangular with pixels that are outside the mask rendered transparent. In embodiments, each game piece can be composed of square objects, for example four squares for each tetromino.

In step380, the sprite is returned to the video game application and appears in the field of play in the video game. In embodiments, for efficiency, the photominoes generated from a photo can be cached for future use by other players or games.

In step390, the weights for each piece type are adjusted. In embodiments, the piece type most recently used for a sprite is adjusted to have a lower weight and the other piece types are adjusted to have relatively higher weights. An important consideration for the video game is to produce a good mix of piece types. This can be achieved by assigning a weight to each piece type that boosts its saliency score if the piece type has not been recently used in the game. For example, in practice, the “S” and “Z” shapes do not generally have high saliency scores without weights. This may be because naturally occurring shapes found in images tend to be roughly elliptical or rectangular. Adjusting the weights after a game piece is created increases the chances of other piece types being generated. Further, the weights make it less likely to generate another game piece of a type that has been generated with relatively high frequency.

The weight adjustments should not be drastic, however, so that the game player is not able to predict a pattern of consecutive game piece types and that a pattern of consecutive game pieces of the same type is not likely. For a simple calculation method, it is enough to reduce the wieght of the most recent game piece type by a small percentage, for example ten percent, and spread this difference evenly among the other piece types. In embodiments, this percentage can be any percentage.

The game piece type weights are calculated based on the distribution of the piece types that have been generated. In embodiments, a computation model is used, in which the probability for choosing a piece is given by its weight, the weights must all add up to 1.0. Thus, in this model, all the weights need to be adjusted and not just the most recently used piece type.

The process loops back to step330and waits for a request from the video game system until the game ends. If the game ends in step340, the process ends in step395.

A “Falling Blocks” Photominoes Game

FIG. 5shows an example screen shot of photominoes as used in a “falling blocks” game, according to embodiments. This game provides a novel way for people to interact with and view their photos. In embodiments, photominoes for this game can be polyominoes of the case n=4, and thus are photo tetrominoes and the game is similar to Tetris. As the game proceeds, each photomino game piece in created via the process described forFIG. 3. The game's screen500includes a game window510for playing with the photominoes520and photo windows530and540for showing photos550. The game window510is centered on the game screen500between the two photo windows530and540. There is also a score area560to display the score. Game play proceeds as in classic “falling blocks,” where Photominoes520fall downward and the user can rotate the pieces or move them side-to-side. As described above, the goal is to manipulate the falling pieces so that when they land, the pieces fit together to avoid empty spaces. When a horizontal row is completely filled, that row collapses. Cascading collapses involving successive rows is supported.

When photomino520is completely knocked out in the game window510, the photo corresponding to the Photomino is displayed in one of the photo windows530and540. The photo windows530and540can display several photos550, and the most recently knocked out photos are shown. The player can pause the game action to look at the photos. The game ends when a Photomino lands in such a way that it touches the top of the game window. The score is the number of photos knocked out. In embodiments, any number of photo windows can be displayed in any arrangement relative to the game window.

For user interaction, the keyboard is used with the following mapping. The Up Arrow key rotates the active game piece, Left and Right Arrow keys move the game piece side-to-side, and the Down Arrow key increases the falling speed. The user can momentarily stop the action to look at the photos by using the Enter key to pause and to resume the game.

There are many variations of “falling blocks” game play and scoring variations. These variations can be easily adapted to the basic design. In embodiments, the game can have one or more photo windows in various positions relative to the game window on the game screen.

Generating Photominoes for Jigsaw Puzzles

FIG. 6is a flowchart of a process for generating photominoes as used in a jigsaw puzzle, according to embodiments. As mentioned above, photominoes can be defined as polyominoes rendered with salient parts detected from photos or images. Polyominoes in the case of n=5 are photo pentominoes. Photo pentominoes can be used for jigsaw puzzles since pentominoes admit interesting tilings of rectangles. In embodiments, the following process, however, is for the more general version of generating photo polyominoes for jigsaw puzzles, including polyomino cases for n of any positive integer.

The process starts in step600. For purposes of constructing photominoes, a computer program keeps an enumerated list of the polyomino of size=n piece types, including piece types obtained by rotations and flips. Let P* denote this expanded list. For example, for a polyomino of n=5, or pentominoes, P* is the set of basic piece types shown inFIG. 2plus all combinations of rotations and flips of these pieces. In step610, a template is constructed for each piece type in the P* list from the computer program.

In step620, the number of each piece type required for a complete puzzle is determined. The number is requested from a photomino software module.

In step630, the images are input for the entire jigsaw puzzle so that all game pieces can be computed at once. The images can be randomly chosen from a photo repository. In embodiments, the photo repository can be created by a user through a user interface, in which the user downloads images to the repository and selects images from the repository. In embodiments, the photomino software module uses a default directory of images on a personal computer, such as the “My Pictures” directory, if the application is running on a personal computer, for example.

In step640, saliency maps are created for each image, as discussed above in step350ofFIG. 3.

FIGS. 7A-7Dshow examples of images and photo pentominoes created from corresponding salient parts of the images, according to embodiments. For example, salient parts of the image inFIG. 7Aare the people and the balloons. These salient parts ofFIG. 7Aare shown in the “W” photo tetromino inFIG. 7B. This “W” is rotated 180 degrees from the “W” shown inFIG. 2. InFIG. 7C, one salient part of the image is the two women, who are shown in the “U” photo tetromino inFIG. 7D. The photo pentominoes inFIGS. 7B and 7Dshow designs for puzzle pieces of a jigsaw puzzle.

Returning toFIG. 6, in step650, for each instance of a required piece type, an image and template location that optimizes the saliency scores are found, according to embodiments. Saliency needs to be optimized given a set of images and a set of piece types from P*, along with finding the corresponding template locations. Each template location is the location on the image over which the template lies for the best saliency score. The basic idea is to slide the templates over the images to find the combination with the best saliency score. The process is slightly different depending on the kind of puzzle being targeted. Since the photomino software module is given a set of piece types to begin with, it optimizes over these piece types instead of over one piece type at a time in the video game scenario. For each piece type of the jigsaw puzzle, all images are searched for the image that provides a template location that optimizes the saliency score. For a photo collection of moderate size, all the images can be tried. For large collections, a limit can be set so that the best score of N, for example N=100, randomly selected images will be tried. Alternatively, the user can choose the images for the pieces.

In embodiments, because the saliency map computation and template matching may not be what a particular user subjectively perceives to be the best template and location for an image, in embodiments, a user interface can be provided for adjusting the location of templates and images. The user interface could include other operations such as scaling, rotating and flipping, according to embodiments. In embodiments, users can select the template type for a particular photo. The extent to which these techniques are helpful will also depend on the particular puzzle.

In step660, the puzzle pieces can be rendered by using the templates as masks over their corresponding images at the locations on the images found in step650. In embodiments, the mask is in the shape of the game piece. In embodiments, since it is often easier to implement rectangular graphical objects, the game piece could be rectangular with pixels that are outside the mask rendered transparent. In embodiments, each game piece can be composed of square objects, for example four squares for each tetromino. In step690, the process ends.

FIG. 8Ashows an example of photo pentominoes as jigsaw puzzle pieces, according to embodiments. These pieces are the result of the process shown inFIG. 6. When assembled, these pieces will become a collage composed of the salient regions of interest from the set of images used inFIG. 6.FIG. 8Bshows an example completed jigsaw puzzle assembled from the photo pentomino pieces ofFIG. 8A, according to embodiments.FIG. 8Cshows the solution of the completed jigsaw puzzle ofFIG. 8B, according to embodiments.

In embodiments, to improve the saliency scores of the image and template locations, the process can optimize over all or some subset of tiling solutions for the given dimensions of a puzzle. For example, given pentominoes for a ten by six jigsaw puzzle, the process can calculate the total puzzle piece saliency scores for some or all of the 2,339 solutions to find the one solution with the highest total saliency score.

In embodiments, a different kind of jigsaw puzzle can be constructed by taking a single image and partitioning it into pieces. One goal in creating these pieces is to find pieces that visually connect to each other to form the image. This type of puzzle is easier to solve than the “collage” type puzzle discussed above. In the collage type puzzle, each puzzle piece is from a different image and thus there are no hints as to which pieces belong next to each other. To create the single image jigsaw puzzle, a boundary score function can optimize over the saliency scores of the points near the boundaries of the pieces. This function measures how much the objects found in the imge is cut up. For each solution, the score is computed. The best scoring solution is superimposed over theimage to form the jigsaw puzzle. In embodiments, the best score is the highest score. In embodiments, the best score is the lowest score, which makes the puzzle more difficult to solve.

In embodiments, depending on preference, the cutting up of the salient objects in images can be minimized so that the flavor of the puzzle is to assemble objects in a composition. Cutting of objects in minimized because large sections of each image are used for to create the photominoes in a collage of photominoes corresponding to different images. In other embodiments, the cutting up of objects can be maximized so that the flavor of the puzzle is to put partial objects together to reveal the objects. Cutting of objects in images is maximized by using fewer images or even one image. The photominoes in this case are created from different parts of the fewer images to reveal one or more whole objects when the photominoes are assembled in to the jigsaw puzzle.

In embodiments, jigsaw puzzle photominoes can be played as a computer game in which players manipulate the puzzle pieces on the screen. In embodiments, the jigsaw puzzle photominoes can be printed out, either in the form of a solution on a single sheet of paper or as separate puzzle pieces in any arrangement on one or more sheets of paper. These printed out puzzle pieces can then be cut up to make physical puzzle pieces. Alternatively, if the puzzle pieces are printed out in the form of a solution, the printout can be kept intact for use as a collage.

For software jigsaw puzzles, in embodiments, a fully assembled photominoes puzzle can be rendered and viewed as a collage. In other embodiments, the puzzle can be rendered and viewed as one or more complete objects. In embodiments, software jigsaw puzzles can be shared with friends and family, who can leave the whole jigsaw puzzle “picture” intact or use it as a jigsaw puzzle.

System Hardware, Software and Components

The present invention can be conveniently implemented using a conventional general purpose or a specialized digital computer or microprocessor programmed according to the teachings of the present disclosure, as will be apparent to those skilled in the computer art.

Photominoes video games and puzzles can be targeted for platforms like tabletop systems, digital cameras with games, photo printing kiosks, and online photo websites. An example of one platform, a tabletop system, is shown inFIG. 9. The tabletop system900typically includes one or more memories910, one or more processors920, and one or more storage devices or repositories930of some sort. The system900further includes a display device940with a screen that displays a video game and/or user interface950. A user can interact with the video game and/or user interface via a touchscreen or other input device (not shown). System900includes a video game application960that includes both video game and puzzle applications. The video game application interfaces with the display device940. When the video game application requires photomino game pieces, the application calls the photomino software module970which returns the requested photomino game pieces. The photomino software module can also provide a user interface950through which a user can select and view images, as well as create and manipulate photominoes, for example.

Appropriate software coding can readily be prepared by skilled programmers based on the teachings of the present disclosure, as will be apparent to those skilled in the software art. Included in the programming or software of the general/specialized computer or microprocessor are software modules for implementing the teachings of the present invention. The present invention can also be implemented by the preparation of application specific integrated circuits or by interconnecting an appropriate network of conventional component circuits, as will be readily apparent to those skilled in the art.

The present invention includes a computer program product which is a storage medium (media) having instructions stored thereon/in which can be used to program a computer to perform any of the features presented herein. The storage medium can include, but is not limited to, any type of disk including floppy disks, optical discs, DVDs, CD-ROMs, microdrives, and magneto-optical disks, ROMs, RAMs, EPROMs, EEPROMs, DRAMs, VRAMs, flash memory devices, magnetic or optical cards, nanosystems (including molecular memory ICs), or any type of media or device suitable for storing instructions and/or data. Various embodiments include a computer program product that can be transmitted in whole or in parts and over one or more public and/or private networks wherein the transmission includes instructions and/or information, which can be used by one or more processors to perform any of the features presented herein. In various embodiments, the transmission can include a plurality of separate transmissions.

Stored on any one of the computer readable medium (media), the present invention includes software for controlling both the hardware of the general purpose/specialized computer(s) and/or microprocessor(s), and for enabling the computer(s) and/or microprocessor(s) to interact with a human user or other mechanism utilizing the results of the present invention. Such software may include, but is not limited to, device drivers, operating systems, user interfaces and applications. Ultimately, such computer readable media further includes software for performing embodiments of the present invention.

The execution of code can be direct or indirect. The code can include compiled, interpreted and other types of languages. Unless otherwise limited by claim language, the execution and/or transmission of code and/or code segments for a function can include invocations or calls to other software or devices, local or remote, to do the function. The invocations or calls can include invocations or calls to library modules, device drivers, interface drivers and remote software to do the function. The invocations or calls can include invocations or calls in distributed and client/server systems.

The foregoing description of preferred embodiments of the present invention has been provided for the purposes of illustration and description. It is not intended to be exhaustive or to limit the invention to the precise forms disclosed. Many modifications and variations will be apparent to the practitioner skilled in the art. Other features, aspects and objects of the invention can be obtained from a review of the figures and the claims. It is to be understood that other embodiments of the invention can be developed and fall within the spirit and scope of the invention and claims. The embodiments were chosen and described in order to best explain the principles of the invention and its practical application, thereby enabling others skilled in the art to understand the invention for various embodiments and with various modifications that are suited to the particular use contemplated. It is intended that the scope of the invention be defined by the following claims and their equivalence.