Algoritmi: corrispondenza ellisse

Ho molte immagini come la seguente (solo bianco e nero):

inserisci la descrizione dell'immagine qui

Il mio ultimo problema è trovare ellissi corrispondenti. Sfortunatamente le immagini reali non sono sempre così belle. Potrebbero essere deformati un po ‘, il che rende probabilmente più difficile la corrispondenza dell’ellisse.

La mia idea è di trovare “punti di rottura”. Li contrassegno nella seguente immagine:

inserisci la descrizione dell'immagine qui

Forse questi punti potrebbero aiutare a creare un abbinamento per le ellissi. Il risultato finale dovrebbe essere qualcosa del genere:

inserisci la descrizione dell'immagine qui

Qualcuno ha un’idea di quale algoritmo può essere usato per trovare questi punti di rottura? O ancora meglio per fare una buona corrispondenza ellisse?

Grazie mille

  1. Campiona i punti della circonferenza

    Basta scansionare la tua immagine e selezionare Tutti i pixel neri con qualsiasi vicino Bianco. È ansible eseguire questa operazione ricolorando i pixel neri rimanenti a qualsiasi colore non utilizzato (blu).

    Dopo aver completato l’intera immagine, è ansible ricolorare la parte interna posteriore dal colore non utilizzato (blu) al bianco.

  2. forma una lista di punti circonferenziali ordinati per cluster / ellisse

    Basta scansionare la tua immagine e trovare il primo pixel nero. Quindi utilizzare A * per ordinare i punti di circonferenza e memorizzare il percorso in alcuni array o list pnt[] e gestirlo come array circolare.

  3. Trova i “punti di rottura”

    Possono essere rilevati dal picco nell’angolo tra i vicini dei punti trovati. qualcosa di simile a

     float a0=atan2(pnt[i].y-pnt[i-1].y,pnt[i].x-pnt[i-1].x); float a1=atan2(pnt[i+1].y-pnt[i].y,pnt[i+1].x-pnt[i].x); float da=fabs(a0-a1); if (da>M_PI) da=2.0*M_PI-da; if (da>treshold) pnt[i] is break point; 

    o usa il fatto che sul punto di rottura l’angolo di pendenza cambia il segno del cambio:

     float a1=atan2(pnt[i-1].y-pnt[i-2].y,pnt[i-1].x-pnt[i-2].x); float a1=atan2(pnt[i ].y-pnt[i-1].y,pnt[i ].x-pnt[i-1].x); float a2=atan2(pnt[i+1].y-pnt[i ].y,pnt[i+1].x-pnt[i ].x); float da0=a1-a0; if (da0>M_PI) da0=2.0*M_PI-da0; if (da0<-M_PI) da0=2.0*M_PI+da0; float da1=a2-a1; if (da1>M_PI) da1=2.0*M_PI-da1; if (da1<-M_PI) da1=2.0*M_PI+da1; if (da0*da1<0.0) pnt[i] is break point; 
  4. ellissi in forma

    quindi, se non sono stati rilevati punti di interruzione, è ansible adattare l'intero pnt [] come singola ellisse. Ad esempio Trova casella di delimitazione. Il suo centro è il centro dell'ellisse e la sua dimensione ti dà semi-assi.

    Se i punti di interruzione sono stati rilevati, individuare innanzitutto il riquadro di delimitazione dell'intero pnt[] per ottenere i limiti per le semiasse e la ricerca dell'area di posizione centrale. Quindi dividere il pnt[] in parti tra i punti di interruzione. Gestire ciascuna parte come parte separata dell'ellisse e adattarla.

    Dopo che tutte le parti pnt[] sono state montate, verifica se alcune ellissi non sono le stesse, ad esempio se sono sovrapposte a un'altra ellisse, sarebbero divise ... Quindi unisci quelle identiche (o media per migliorare la precisione). Quindi ricolora tutti pnt[i] punti pnt[i] in bianco, cancella l'elenco pnt[] e il loop # 2 fino a quando non viene trovato alcun pixel nero.

  5. come adattare l'ellisse dalla selezione dei punti?

    1. algebricamente

      utilizzare l'equazione ellittica con punti noti dispersi "uniformsmente" per formare un sistema di equazioni per calcolare i parametri di ellisse ( x0,y0,rx,ry,angle ).

    2. geometricamente

      per esempio se rilevi la pendenza 0,90,180 o 270 gradi, allora sei all'incrocio di semiasse con circonferenza. Quindi se hai due di questi punti (uno per ciascun semiasse) è tutto ciò che ti serve per il assembly (se è un'ellisse allineata all'asse).

      per le ellissi non allineate agli assi è necessario disporre di una porzione sufficientemente grande della circonferenza disponibile. Puoi sfruttare il fatto che il centro del riquadro di delimitazione è anche il centro dell'ellisse. Quindi se hai l'intera ellisse, conosci anche il centro. Le intersezioni a semiasse con circonferenza possono essere rilevate con il cambiamento tangente più grande e più piccolo. Se hai centrato e due punti è tutto ciò di cui hai bisogno. Nel caso in cui tu abbia solo un centro parziale (solo x o una coordinata y) puoi combinarlo con più punti asse (trova 3 o 4) ... o approssimare le informazioni mancanti.

      Anche la metà H, l'asse delle linee V sta intersecando il centro dell'ellisse in modo che possa essere usato per rilevarlo se non per l'intera ellisse nella lista pnt[] .

      misura dell'ellisse non allineata all'asse

    3. ricerca di approssimazione

      È ansible eseguire il ciclo di "tutti" possibili combinazioni di parametri di ellisse entro i limiti indicati in # 4 e selezionare quello più vicino ai punti. Sarebbe follemente lento di grossolana, quindi usa la ricerca binaria come un approccio simile al mio approssimativamente in class . Vedi anche

      • Montaggio della curva con punti y su posizioni x ripetute (Galaxy Spiral arms)

      su come è usato per adattarsi in modo simile al tuo.

    4. ibrido

      È ansible combinare l'approccio geometrico e l'approssimazione. Calcola innanzitutto ciò che puoi tramite un approccio geometrico. E poi calcola il resto con la ricerca di approssimazione. puoi anche aumentare la precisione dei valori trovati.

    In rari casi quando due ellissi vengono unite senza punto di rottura l'ellisse adattata non corrisponderà ai tuoi punti. Quindi se tale caso viene rilevato devi suddividere i punti usati in gruppi fino a quando le loro corrispondenze coincidono ...

Questo è quello che ho in mente con questo:

panoramica

Probabilmente hai bisogno di qualcosa del genere:

https://en.wikipedia.org/wiki/Circle_Hough_Transform

I tuoi punti di bordo sono semplicemente pixel neri con almeno un 4-vicino bianco.

Sfortunatamente, però, dici che le tue ellissi possono essere “inclinate”. Le ellissi generiche sono descritte da equazioni quadratiche come

 x² + Ay² + Bxy + Cx + Dy + E = 0 

con B² <4A (⇒ A> 0). Ciò significa che, rispetto al problema del cerchio, non hai 3 dimensioni ma 5. Ciò fa sì che la trasformazione di Hough sia considerevolmente più difficile. Fortunatamente, il tuo esempio suggerisce che non hai bisogno di una risoluzione elevata.


Vedi anche: algoritmo per il rilevamento di un cerchio in un’immagine


MODIFICARE

L’idea di cui sopra per un algoritmo era troppo ottimistica , almeno se applicata in modo semplice. La buona notizia è che sembra che due ragazzi intelligenti (Yonghong Xie e Qiang Ji) abbiano già fatto i compiti per noi:

https://www.ecse.rpi.edu/~cvrl/Publication/pdf/Xie2002.pdf

Non sono sicuro di voler creare il mio algoritmo. Perché non sfruttare il lavoro svolto dagli altri team per capire tutto quel adattamento di curva delle bitmap?

INKSCAPE (collegamento app)

Inkscape è uno strumento open source specializzato in editing di grafica vettoriale con alcune possibilità di lavorare anche con parti raster (bitmap).

Ecco un link a un punto di partenza per l’API di Inkscape:

http://wiki.inkscape.org/wiki/index.php/Script_extensions

Sembra che tu possa scrivere in Inkscape o accedere a Inkscape tramite script esterni.

Potresti anche essere in grado di fare qualcosa con zero script, dall’interfaccia della riga di comando di inkscape:

http://wiki.inkscape.org/wiki/index.php/Frequently_asked_questions#Can_Inkscape_be_used_from_the_command_line.3F

COREL DRAW (Link app)

Corel Draw è riconosciuta come la migliore soluzione di settore per la grafica vettoriale e ha alcuni ottimi strumenti per convertire le immagini rasterizzate in immagini vettoriali.

Ecco un link alla loro API:

https://community.coreldraw.com/sdk/api

Ecco un collegamento all’elaborazione di immagini batch di Corel Draw (soluzione non script):

http://howto.corel.com/en/c/Automating_tasks_and_batch-processing_images_in_Corel_PHOTO-PAINT