Datenstruktur für Pixel-basierte Mustererkennung

Question

Ich habe eine Anwendung, die zufällige Bilder basierend auf Einschränkungen erstellt. Verschiedene farbige Pixel werden zufällig ausgewählt und in einem Gitter platziert, das alle Beschränkungen erfüllt. Zum Beispiel (vereinfacht) könnte es eine Einschränkung geben, die sagt, wenn ein blaues oder grünes Pixel bei (0, -1) ist und rote Pixel bei (-1, -1) und (-1, 0) sind, dann platzieren Ein weißes Pixel ist verboten. Diese Koordinaten sind Vektoren von dem aktuellen Platzierungsort (d. H. Seiner Nachbarschaft).

Momentan speichere ich die Beschränkungen in einem Array und durchlaufe sie, um zu sehen, ob jeder anwendbar ist oder nicht. Ich muss dies für jeden Pixel tun, den ich im Raster platziere. Daher leidet die Leistung, wenn mehr Einschränkungen hinzugefügt werden. Es ist auch möglich, dass zwei Einschränkungen in Konflikt stehen, aber es ist nicht einfach, dies zu überprüfen.

Ich denke, dass eine Diagrammtyp-Datenstruktur (Baum?) Eine Möglichkeit sein kann, alle Einschränkungen zu speichern, so dass ich aus der Pixelumgebung schnell bestimmen kann, welche (wenn überhaupt) Einschränkungen gelten. Aber ich kann nicht genau herausfinden, wie man eine solche Struktur zum Laufen bringt, vorausgesetzt, dass eine einzelne Koordinate mehrere Farben enthalten kann und wie man einen Satz von Koordinaten/Farben mit einer Reihe verbotener Pixelfarben verbindet. Irgendwelche Ideen?

Answer 1

Sie können den Graphenschnitt verwenden, um dieses Problem zu lösen. Es wird sich sogar um die genannten Konflikte kümmern. Dies ist im Grunde so: Es versucht, Labels auf der Basis einer Kostenfunktion zu vergeben, die Sie minimieren möchten.Für Ihren Fall könnte die Kostenfunktion so etwas wie:

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

Graph geschnittenen Etiketten zuweisen, die diese Kostenfunktion minimieren. Außerdem ist es sehr schnell und effizient und konvergiert zu den Minima. Werfen Sie einen Blick auf den folgenden zwei Referenzen:

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

Der zweite Link liefert den fertigen Code für Graph-Cut, wo Sie Ihre eigene Kostenfunktion verwenden können, die minimiert werden soll (und die wie in Ihrem Fall von den Nachbarwerten abhängig sein kann).

Answer 2

Für dieses Problem können Sie verschiedene Arten von Bäumen verwenden.

Dies scheint weithin recherchiert Thema und wahrscheinlich Antwort wäre viel länger als normal SO Antwort. Siehe nächste 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

Answer 3

Havent arbeitete mit Pattern-Matching, aber was in den Sinn kommt ist:

Nehmen üblichen Graph ds wo Eckpunkten wird Ihre Vektoren und Kanten sind verbotene Farben, die sie verbinden. Hier können Sie alle Scheitelpunkte miteinander verbinden, optimaler ist es, eine Richtung zu nehmen, die Sie verwenden, füllen Sie Ihre DS, sollten Sie den gleichen Startpunkt und Richtung verwenden, wenn Sie durch Pixel-Arrays gehen. Von Ihrem Beispiel, wenn Sie von (0, -1) im Uhrzeigersinn gehen, wird es etwa so aussehen: (0, -1) --blue-- (-1, -1), (0, -1) --grün - (-1, -1), (-1, -1) --red - (-1, 0), (-1, 0) --red - (- 1, 1), (-1 , 1) --weiß - (0, 1), (-1, 1) --weiß-- (1, 1), (-1, 1) --weiß-- (1, 0)

Verwenden Sie jetzt DFS, um Farbe zu überprüfen (es wird Rand sein)

Answer 4

Es scheint mir, dass eine bequeme Wahl wäre ein kd-Baum. Wenn Sie Ihre Integritätsbedingungen in einem kd-Baum speichern, können Sie möglicherweise auf die Einschränkungen zugreifen, die für die nächste Art von Abfrage gelten.

Ich würde vorschlagen, dass Sie sich das Buch Algorithms in a Nutshell ansehen. Sie können eine easy implementation eines kd-Baumes finden, der auf Ihr Problem anwendbar sein könnte.

Beachten Sie jedoch, dass der resultierende Baum möglicherweise nicht gut ausbalanciert ist, wenn die Einschränkungen in Ihrer Szene nicht gleichmäßig verteilt sind. In diesem Fall sollten Sie eine bessere Darstellung für die Abhängigkeiten finden, oder die tatsächliche Komplexität des Algorithmus wird eher dem schlechtesten Wert O (n) als dem durchschnittlichen (und besten) Wert O (log n) entsprechen.