Struktura danych do rozpoznawania wzorców w oparciu o piksele

Question

Mam aplikację, która tworzy losowe obrazy na podstawie wiązań. Różne kolorowe piksele są losowo wybierane i umieszczane w siatce spełniającej wszystkie ograniczenia. Na przykład (upraszczając) może istnieć ograniczenie, które mówi, że niebieski i zielony piksel ma wartość (0, -1), a czerwone piksele to (-1, -1) i (-1, 0), a następnie umieszczenie biały piksel jest zabroniony. Te współrzędne są wektorami z bieżącego położenia miejsca docelowego (to znaczy z sąsiedztwa).

W tej chwili przechowuję ograniczenia w tablicy i przechodzę przez nie, sprawdzając, czy każdy z nich ma zastosowanie, czy nie. Muszę to zrobić dla każdego piksela, który umieściłem w siatce. Tak więc wydajność cierpi wraz z dodatkowymi ograniczeniami. Możliwe jest również, że dwa ograniczenia są w konflikcie, ale nie jest łatwo to sprawdzić.

Myślę, że struktura danych typu wykresu (drzewo?) Może być sposobem przechowywania wszystkich wiązań, tak, że mogę szybko określić z sąsiedztwa piksela, które mają zastosowanie (jeśli jakiekolwiek) ograniczenia. Ale nie jestem w stanie wymyślić, jak sprawić, aby taka struktura działała, biorąc pod uwagę, że pojedyncza współrzędna może zawierać wiele kolorów i jak powiązać zestaw współrzędnych/kolorów z zestawem zabronionych kolorów pikseli. Jakieś pomysły?

Answer 1

Można użyć cięcia wykresu w celu rozwiązania tego problemu. Zajmie się nawet wspomnianymi konfliktami. Zasadniczo to działa: próbuje przypisać etykiety w oparciu o funkcję kosztów, którą chcesz zminimalizować.W przypadku Twojego przypadku funkcja kosztów może wyglądać następująco:

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

Cięcie wykresu spowoduje przypisanie etykiet, które minimalizują tę funkcję kosztów. Dodatkowo jest bardzo szybki i efektywny i zbiega się z minimami. Zapraszamy do obejrzenia dwóch następujących publikacjach:

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

Drugi link zawiera kod gotowych do wykresu cięcia, gdzie można użyć własnych funkcji kosztu, która ma być zminimalizowane (i które mogą być zależne od wartości sąsiadów, jak w twoim przypadku).

Answer 2

Do tego problemu można używać różnych rodzajów drzew.

Wydaje się, że jest to temat szeroko rozpowszechniony i prawdopodobnie odpowiedź byłaby znacznie dłuższa niż zwykła odpowiedź SO. Odnoszą się do kolejnych linków:

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 pracował z pasujące do wzorca, ale to, co przychodzi do głowy to:

Take zwykłe ds wykres gdzie wierzchołki będzie twój wektory i krawędzie będą zabronione w kolorach łączących je. Tutaj możesz połączyć wszystkie wierzchołki między sobą, bardziej optymalnym będzie przyjęcie jakiegoś kierunku, z którego będziesz korzystać, wypełnij swój ds, powinieneś użyć tego samego punktu początkowego i kierunku, kiedy będziesz przechodził przez tablice pikseli. Z twojego przykładu, jeśli zaczynasz od (0, -1), zgodnie z ruchem wskazówek zegara, będzie to coś w stylu: (0, -1) - niebieskie - (-1, -1), (0, -1) - zielone - (-1, -1), (-1, -1) - wartość - (-1, 0), (-1, 0) - wartość - (- 1, 1), (-1 , 1) - biały - (0, 1), (-1, 1) - biały - (1, 1), (-1, 1) - biały - (1, 0)

Teraz użyj DFS, aby przeszukać kolor, by sprawdzić (będzie krawędzi)

Answer 4

Wydaje mi się, że wygodnym wyborem byłoby drzewo kd. Przechowując twoje ograniczenia w drzewie kd, możesz mieć dostęp do ograniczeń, które mają zastosowanie w zapytaniu typu najbliższy sąsiad.

Proponuję zapoznać się z książką Algorithms in a Nutshell. Możesz znaleźć easy implementation drzewa kd, które może mieć zastosowanie do twojego problemu.

Należy jednak pamiętać, że jeśli wiązania nie są równomiernie rozmieszczone w scenie, wynikowe drzewo może nie być dobrze zbalansowane. W takim przypadku powinieneś znaleźć lepszą reprezentację dla więzów, lub rzeczywista złożoność algorytmu będzie bliższa najgorszej wartości O (n), niż średniej (i najlepszej) wartości O (log n).