Data structure for pixel based pattern recognition

Question

I have an application that constructs random images based on constraints. Different colored pixels are randomly selected and placed in a grid that satisfy all constraints. For example (simplifying), there might be a constraint that says if a blue or green pixel is at (0,-1), and red pixels are at (-1,-1) and (-1, 0), then placing a white pixel is prohibited. These coordinates are vectors from the current placement location (i.e. its neighborhood).

Right now I am storing the constraints in an array and looping through them, checking to see if each one is applicable or not. I have to do this for each pixel I place in the grid. So the performance suffers as more constraints are added. Also, it is possible for two constraints to be in conflict but it is not easy to check for that.

I'm thinking that a graph type data structure (tree?) might be a way to store all of the constraints such that I can quickly determine from the pixel neighborhood which (if any) constraints apply. But I can't quite figure out how to make such a structure work, given that a single coordinate can contain multiple colors, and how to tie a set of coordinate/colors to set of prohibited pixel colors. Any ideas?

Answer 1

Havent worked with pattern matching, but what comes to mind is:

Take usual graph ds where vertices will be your vectors and edges will be prohibited colors connecting them. Here you can connect all vertices between each other, more optimal will be to take some direction which you will use fill your ds, you should use same starting point and direction when you will be going through pixels arrays. From your example if you start from (0,-1) going clockwise it will be something like: (0,-1) --blue-- (-1, -1), (0,-1) --green-- (-1, -1), (-1, -1) --red -- (-1, 0), (-1, 0) --red--(-1, 1), (-1, 1) --white--(0, 1), (-1, 1) --white-- (1, 1), (-1, 1) --white-- (1, 0)

Now use DFS to search color to check (it will be edge)

Answer 2

It seems to me that a convenient choice would be a kd-tree. By storing your constraints in a kd-tree, you could be able to access the constraints that apply with a nearest neighbor kind of query.

I would suggest you to have a look at the book Algorithms in a Nutshell. You can find an easy implementation of a kd-tree that might be applicable to your problem.

However, keep in mind that if the constraints are not uniformly distributed in your scene, the resulting tree might be not well balanced. In this case you should find a better representation for the constraints, or the actual complexity of the algorithm will be closer to the worst value O(n), rather than the average (and best) value O(log n).

Answer 3

You can use graph cut for solving this problem. It will even take care of the conflicts mentioned. This is basically how it works: it tries to assign labels based on an cost function which you wish to minimize. For your case, the cost function could be something like:

E(x)=infinite ; if constraint is violated
and  0        ; otherwise

Graph cut will assign labels that minimize this cost function. Plus, it is very fast and efficient and converges to the minima. Have a look at the following two references:

1. Graph cuts for energy Minimization
2. Code for implementing graph cut

The second link provides the readymade code for graph cut where you can use your own cost function which is to be minimized (and which can be dependent on the neighbour values as in your case).

Answer 4

For this problem you can use different types of trees.

This seems to be widely researched topic and probably answer would be way longer than normal SO answer. Refer to next links:

https://books.google.co.uk/books?id=ixDjBQAAQBAJ&pg=PA119&lpg=PA119&dq=best+data+structure+for+pattern+recognition&source=bl&ots=BLEx5TOrW9&sig=d_1HjGTeQ7SptvHJ0iZ_yXUG5Vo&hl=sl&sa=X&ei=dgI6VYDTKZPVapmTgdgD&ved=0CFcQ6AEwCA#v=onepage&q=best%20data%20structure%20for%20pattern%20recognition&f=false

http://www.computer.org/csdl/trans/ts/1977/02/01702419.pdf

http://www.ablesw.com/3d-doctor/3dseg.html