Struttura dati per riconoscimento pattern basato su pixel

Question

Ho un'applicazione che costruisce immagini casuali in base a vincoli. Diversi pixel colorati vengono selezionati in modo casuale e inseriti in una griglia che soddisfa tutti i vincoli. Ad esempio (semplificando), potrebbe esserci un vincolo che dice se un pixel blu o verde è a (0, -1), e i pixel rossi sono a (-1, -1) e (-1, 0), quindi posizionando un pixel bianco è proibito. Queste coordinate sono vettori dall'attuale posizione di posizionamento (cioè il suo vicinato).

In questo momento sto memorizzando i vincoli in un array e scorrendo attraverso di essi, controllando se ciascuno è applicabile o meno. Devo farlo per ogni pixel che inserisco nella griglia. Quindi la performance soffre quando vengono aggiunti altri vincoli. Inoltre, è possibile che due vincoli siano in conflitto ma non è facile controllarli.

Sto pensando che una struttura di dati di tipo grafico (albero?) Potrebbe essere un modo per archiviare tutti i vincoli in modo tale da poter determinare rapidamente dal vicinato dei pixel i vincoli (se esistenti) applicabili. Ma non riesco a capire come fare funzionare una simile struttura, dato che una singola coordinata può contenere più colori e come legare un insieme di coordinate/colori per impostare colori di pixel proibiti. Qualche idea?

Answer 1

È possibile utilizzare il taglio grafico per risolvere questo problema. Si prenderà anche cura dei conflitti menzionati. Questo è fondamentalmente il modo in cui funziona: cerca di assegnare etichette basate su una funzione di costo che desideri minimizzare.Per il tuo caso, la funzione costo potrebbe essere qualcosa del tipo:

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

Il taglio del grafico assegnerà etichette che riducono al minimo questa funzione di costo. Inoltre, è molto veloce ed efficiente e converge ai minimi. Dai un'occhiata alle seguenti due riferimenti:

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

Il secondo collegamento fornisce il codice di readymade per il taglio grafico in cui è possibile utilizzare il proprio funzione di costo che deve essere ridotto al minimo (e che può dipendere dai valori vicini come nel tuo caso).

Answer 2

Per questo problema è possibile utilizzare diversi tipi di alberi.

Questo argomento sembra essere ampiamente ricercato e probabilmente la risposta sarebbe molto più lunga della normale risposta SO. Fare riferimento al seguente link:

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 ha lavorato con il pattern matching, ma quello che viene in mente è:

Prendere soliti ds grafico in cui saranno vertici tua ai vettori e ai bordi saranno vietati i colori che li connettono. Qui puoi collegare tutti i vertici tra di loro, più ottimale sarà prendere una direzione che userai per riempire i tuoi ds, dovresti usare lo stesso punto di partenza e direzione quando passerai attraverso gli array di pixel. Dal tuo esempio se inizi da (0, -1) andando in senso orario sarà qualcosa del tipo: (0, -1) --blue-- (-1, -1), (0, -1) - verde - (-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)

Ora usa DFS per cercare il colore da controllare (sarà il bordo)

Answer 4

Mi sembra che una scelta conveniente sarebbe un albero di kd. Memorizzando i tuoi vincoli in un albero kd, potresti essere in grado di accedere ai vincoli che si applicano con un tipo di query più vicino.

Ti suggerisco di dare un'occhiata al libro Algorithms in a Nutshell. È possibile trovare un easy implementation di un albero kd che potrebbe essere applicabile al tuo problema.

Tuttavia, tenere presente che se i vincoli non sono distribuiti uniformemente nella scena, l'albero risultante potrebbe non essere ben bilanciato. In questo caso dovresti trovare una rappresentazione migliore per i vincoli, o la complessità effettiva dell'algoritmo sarà più vicina al valore peggiore O (n), piuttosto che al valore medio (e migliore) O (log n).