Algoritmo e struttura dati per trovare e archiviare il vicinato di superpixel in C++

Question

Ho un'immagine, con risultati di segmentazione, come questa.

Ho bisogno di costruire un grafico di vicinato di patch, colorato in diversi colori. Di conseguenza mi piacerebbe una struttura, che rappresenta i seguenti

Qui numeri rappresentano patch separate, e le linee rappresento quartiere patch. Attualmente non riesco a capire da dove iniziare, quali parole chiave su google.

Qualcuno potrebbe suggerire qualcosa di utile?

L'immagine viene memorizzata nella classe cv :: Mat di OpenCV, come per il grafico, ho intenzione di utilizzare la libreria Boost.Graph.

Quindi, per favore, dammi alcuni collegamenti a esempi di codice e algoritmi, o parole chiave.

Grazie.

Aggiornamento. Dopo un coffee-break e alcune discussioni, mi è venuto in mente quanto segue.

1. Costruire un grafico a traliccio di grandi dimensioni, in cui ogni nodo corrisponde a ciascun pixel dell'immagine e i collegamenti collegano 8 o 4 vicini.
2. Etichettare ciascun nodo del grafico con un valore di pixel corrispondente.
3. Prova a unire in qualche modo nodi con la stessa etichetta.

Il mio altro problema è che non ho familiarità con il BGL (ma il libro è sulla strada :)).

Quindi, cosa ne pensi di questa soluzione?

Update2 Probabilmente, questo link può aiutare.

Tuttavia, la soluzione non è stata ancora trovata.

Answer 1

Si potrebbe risolverlo così:

1. Definire regioni (i numeri nel grafico)

   • fare una matrice 2D che memorizza il numero della regione
   • inizio a (0/0) e impostarlo su 1 (numero regione)
   • imposta l'intera area come 1 utilizzando l'algoritmo di riempimento o qualcosa del genere.
   • durante il riempimento, probabilmente si incontrano coordinate con colori diversi. memorizza quelli all'interno di una coda. inizia a riempire da quelle coordinate e incrementa il numero di regione se il tuo riempimento precedente è stato completato.

   .

2. creare collegamenti tra le regioni

   • scorrere l'array 2D.
   • se si dispone di numeri adiacenti, memorizzare la coppia di numeri (probabilmente in modo ordinato, è inoltre necessario verificare se la coppia esiste già o meno). Devi solo controllare l'elemento in basso, a destra e quello in diagonale a destra, se passi da sinistra a destra.

Anche se devo ammettere che non so nulla su questo argomento .. solo una mia semplice idea ..

Answer 2

penso che se i campioni di colore sono che casuale, probabilmente hai bisogno di un algoritmo di forza bruta per fare ciò che vuoi. Un'idea potrebbe essere:

• Fare un primo passaggio di forza bruta. Questo deve identificare tutte le patch. Ad esempio, crea una matrice A della stessa dimensione dell'immagine e inizializza a 0. Per ogni pixel che è ancora zero, inizia da esso e contrassegnalo come una nuova patch e prova un approccio a forza bruta per trovare l'intero estensione della patch. Ogni cella della matrice avrà quindi un valore uguale al numero della patch in essa contenuta.
• I numeri di patch devono essere 2^N, ad esempio 1, 2, 4, 8, ...
• Creare un'altra matrice B della dimensione dell'immagine, ma ogni cella contiene due valori. Questo rappresenterà la connessione tra i pixel. Per ogni cella della matrice B, il primo valore sarà la differenza assoluta tra il numero di patch nel pixel e il numero di patch di un pixel adiacente. Il primo valore è la differenza con il pixel in basso, il secondo con il pixel a sinistra.
• Seleziona tutti i valori univoci nella matrice B, hai tutte le connessioni possibili.

Questo funziona perché ogni differenza tra i numeri di patch è unica. Per esempio, se in B finisci con i numeri 3, 6, 7 significherà che ci sono contatti tra i patch (4,1), (8,2) e (8,1). Il valore 0 ovviamente significa che ci sono due pixel nella stessa patch l'uno accanto all'altro, quindi devi semplicemente ignorarli.

Answer 3

È possibile utilizzare BFS per contrassegnare le regioni.

Per esporre cv :: Mat a BGL è necessario scrivere molto codice. Penso che scrivere il tuo bfs sia molto più semplice.

Di voi per ogni due negbours scrivete i loro voti a std::set<std::pair<mark_t, mark_t>>. E poi costruisci il grafico da quello.