ofxCV matchShapes implementation?

I’m looking for a way to find out whether a number of shapes are placed in such a way they resemble a given silhouette.
Like a tangram puzzle and the solution, or similar puzzles like the stomachion etc.

Now I came across the openCV function ‘matchShapes’ which compares 2 contours.
I have worked with the openCV add-on before, (ab)using the examples to make them do what I needed, but this seems to be a bit different.

Is this function even available through the add-on? Or do I need to implement it myself somehow…

Maybe there’s a better way to do what I want to do?

Hi Autofasurer,

I understand you want to estimate if the user has placed a set of puzzle elements in a correct layout, resembling a shape you want it to create.

The first thing that occurs to me template matching, in which a template is estimated against an image, usually to find objects in the image. This matching computes the similarity (correlation) between the template and the image, and returns a similarity percentage (from not similar to identical). You can use this function to match the silhouettes of the shape.

Templates are used for more complex systems, usually when you know nothing about the image that the user is generating, but you know how the template is (handwriting for example). In your case, you seem to know about the shapes themselves, it is a combination of puzzle pieces… this can make your system much more simpler. Using the tangram example, you can define a working area (a square where the puzzle pieces can be placed), and you can define the solution to the puzzle as a specific combination of puzzle pieces. The combination is correct if the pieces are placed “more or less” in the correct position to create the complete shape. “More or less” means you define a perfect position and rotation and allow for some deviation.

What do you think?

Hi Hennio,

Thanks for the response. I’ll have a look at the template matching of openCV, but as you say, these things are more used for complex systems. It might be overkill to use it for a simple puzzle type game.

The other solution you suggest is one that has come to mind, but the problem there is, taking the tangram example: there can be multiple solutions, some shapes are interchangeable, the solution can be made anywhere in the screen,…

So here the problem is: what if someone playing finds a solution that was not considered? This would also complicate checking the solution in terms of relative position and rotation of the pieces to one another.

Having an outline to be filled would simplify things, but it would also make the puzzles easier…

All the solutions should be considered when defining the problem… if there are too many to handle, then yes, you should look for another approach…

The oultine can be a simple bounding box that fits exactly around the shape, to define the “workspace”. The piece positions would be normalized to that workspace.

The workspace is defined in red, the piece has to be completed inside. Is is an option?

Well, the workspace is flexible of course… It’s easy to find the bounding box of the puzzle wherever on the screen it is made.

I was also thinking down the lines of gift-wrapping or convex hull algorithms… If there’s a way to figure out the points on the outside of the shape and compare them to the solution, in combination with bounding box, I’m guessing that would get in the neighbourhood.
That’s of course also why I was looking into the ‘matchShapes’ function of openCV.

But coming to think of it, simply comparing the image in the bounding box with the one of the solution is easy.
Somehow I was always thinking in terms of points and shapes making things much more complicated than necessary.