Come trovare 4 punti accanto all'intersezione di due linee

Question

Diciamo che ho alcuni dati bitmap (in nero) su cui alcune linee sono state disegnate a mano in formato vettoriale (in verde). Le linee seguono approssimativamente la forma dei dati bitmap. In alcuni punti, le linee si intersecano.

Quindi quello che sto cercando di fare è conoscere la posizione dell'intersezione delle linee verdi, come posso trovare la posizione di A, B, C e D?

Vedi di seguito per alcuni esempi:

Non sono sicuro di come affrontare questo problema dato il posizionamento casuale delle linee e talvolta non lo sono anche all'interno della sagoma nera. Tuttavia, immagino ci sia un modo. Qualche suggerimento?

Answer 1

più semplice approccio posso pensare è questo:

1. filtrare l'immagine per rimuovere la linea verde. Un approccio semplice sarebbe quello di utilizzare una sorta di assottigliamento che si riempie del colore di sfondo dei pixel vicini.

2. Ora si dovrebbe avere un'immagine che consiste solo di linee nere (larghe) e sfondo bianco.

3. Filtrare nuovamente l'immagine utilizzando un algoritmo di rilevamento angolo, ad esempio Harris detector. Questo ti darà i quattro angoli.

Note:

1. A seconda dei dati di input, si potrebbe ottenere più di quattro angoli. In ogni caso è una buona idea verificare che i quattro angoli che hai estratto siano effettivamente possibili angoli dell'intersezione.

2. Ancora una volta, questo è un approccio piuttosto approssimativo, ma se i dati di input sono puliti come nelle immagini di esempio e la distanza tra le linee verdi e le linee nere non è troppo grande, penso che potrebbe funzionare.

Answer 2

In primo luogo, lasciatemi dire che non so nulla sull'argomento né ho avuto alcuna esperienza con esso. Quindi questa è solo la mia ipotesi. Ma vorrei iniziare ignorando le linee verdi - che, tra l'altro, non sembrano neanche le righe .

Btw, ha avuto a che fare con le strade?

Quindi, disattivare le linee verdi. Dopodiché, prendi un quadratino come uno dei 4 di cui sopra, finché non li controlli tutti e cerchi quelli con il rapporto bianco/nero massimo di pixel. Quelli dovrebbero essere quelli con il "crocevia". Mappando quei pixel neri che confinano con pixel bianchi dovresti avere i bordi strada/campo. Dopo di che determinare quei punti dovrebbe essere facile facile.

Come ho detto, un'ipotesi selvaggia. Problema interessante - chiedo che cosa faranno i ragazzi esperti.

Answer 3

Per prima cosa è necessario estrarre i bordi dall'immagine originale per ottenere poligoni che descrivono il bordo bianco-nero.

Quindi si itera sui punti di questi bordi e si calcola una distanza in senso orario fino al punto di intersezione delle due linee verdi. Le quattro distanze più piccole provengono dai punti che stai cercando.

Questa risposta ti è stata utile? O ho frainteso qualcosa?

Se si desidera solo i 4 angoli, non è necessaria la linea verde: basta prendere i bordi dall'estrazione del bordo, lisciare quindi con un filtro Savitzky-Golay e calcolare la curvatura puntuale. Basta estrarre i punti con la massima curvatura.

Answer 4

È necessaria la vettorizzazione dell'immagine binaria. Il nostro progetto universitario ha avuto ragione sull'argomento - Corners Toolbox Allowing Processing Binary Images in a Compressed Form (non confonderlo con il titolo - "compresso" qui significa che l'immagine binaria viene prima convertita in elenchi collegati di cosiddetti angoli).

1) convertire l'immagine in angoli (vedere il capitolo 4 del collegamento sopra). È quindi possibile utilizzare l'interpolazione di linee dei punti d'angolo (capitolo 5.5) - si modificherebbe il nostro algoritmo per vedere grossi cambiamenti di pendenza (~ 90 gradi) in parti più grandi di linee.

2) non è necessaria la linea verde. È possibile utilizzare l'algoritmo di scheletrizzazione per trovare lo scheletro della parte nera (vedere il capitolo 5.4) e interpolare questo scheletro con linee (vedere il capitolo 5.5 del link sopra).

Se sei interessato al progetto, posso chiedere ai colleghi se siamo in grado di fornire il codice sorgente.

Answer 5

Il modo più semplice sarebbe una scheletrizzazione. Prima separa l'immagine verde e quella nero/bianco. Esegui un algoritmo di scheletro (un'operazione morfologica piuttosto semplice, anche in OpenCV) su entrambe le immagini e determina i punti di intersezione (può essere fatto con un semplice conteggio di 8 quarti di pixel nelle immagini di scheletro: cioè, per ogni pixel nero conta quanti i pixel sono collegati orizzontalmente, verticalmente o diagonalmente e se questo valore è> = 4, è un incrocio). Ora fai una partita vicino-vicino per questi punti scheletrati, e hai finito.

Answer 6

Suppongo tu sappia come ottenere le coordinate (x,y) dell'intersezione della linea vettoriale (verde), quindi tralascerò quella parte.

A partire dal pixel più vicino a (x,y), gradualmente marcia verso l'esterno in una spirale quadrata (o qualche altro modello di ricerca di tuo gradimento) da pixel a pixel. Ad ogni passaggio, controlla se sei su un pixel nero con uno e solo uno bianco Moore neighbour. Se è così, allora il punto in cui il pixel nero e il suo vicino bianco toccano (probabilmente un angolo comune) è uno dei tuoi punti (chiamalo A). Continua a marciare finché non ne trovi altri tre (B, C, D). Questi saranno i quattro punti simili più vicini all'intersezione verde, che funzioneranno bene nei quattro esempi mostrati nella domanda.

Tuttavia, questo algoritmo non funzionerà se l'intersezione verde è a metà strada tra due intersezioni nere; in questo caso mescolerà punti da entrambe le intersezioni nere. Se sei preoccupato per questo, non appena hai trovato il punto A, riavvia la tua spirale in marcia, centrata su A questa volta, e marcia fino a quando non hai trovato B, C, D. Questo sarà in effetti " aggancia "all'intersezione nera più vicina.

È possibile aggiungere più intelligenza per evitare di cercare due volte la stessa area; Riavvia o ri-focalizza il tuo modello di ricerca una volta che hai trovato B e ancora una volta dopo aver trovato C, ecc. Dipende da quanto vuoi/vuoi ottenere.

Answer 7

Dovresti essere in grado di trovare il punto in cui le linee verdi si incrociano e il punto medio in cui le linee nere si incrociano con un processo di erosione (restringendosi ai punti). Quindi utilizzare un tipo di algoritmo a coppia di punti più vicino per individuare le linee nere che si intersecano e anche l'intersezione della linea verde è più vicina.

Quindi, è possibile effettuare una ricerca lontano dal punto in cui le linee nere si intersecano. Avrai bisogno di una coda di priorità che elaborerà i punti in base alla loro distanza dal punto di intersezione delle linee nere, il più vicino prima. Metti i quattro punti adiacenti sull'intersezione delle linee nere nella coda. Per ogni punto della coda, dovrai controllare se è un pixel bianco (vogliamo quelli), controllare che non sia stato visitato prima (salta in quel caso), e quindi aggiungere i suoi quattro pixel adiacenti a la fila. I primi quattro pixel bianchi dovrebbero quelli che vuoi (supponendo che tu abbia avuto un buon metodo di scheletrizzazione/restringimento per trovare l'intersezione), ma dovresti davvero prendere dei pixel bianchi finché non trovi i primi quattro trovati che non sono adiacenti l'uno all'altro .