Trova gli angoli di un rettangolo deformato

Question

Sto provando a creare un programma che corregge automaticamente la prospettiva di un rettangolo. Sono riuscito a ottenere la sagoma del rettangolo e ho il codice per correggere la prospettiva, ma non riesco a trovare gli angoli. Il problema più grande è che, perché è stato deformato, non posso usare il "codice" che segue:

c1 = min(x), min(y) 
    c2 = max(x), min(y) 
    c3 = min(x), max(y) 
    c4 = max(x), max(y) 

Questo non avrebbe funzionato con questa situazione (X rappresenta un angolo):

X0000000000X 
.00000000000 
..X000000000 
.....0000000 
........0000 
...........X 

Qualcuno sa come fare questo?

Answer 1

Il punto più lontano dal centro ti darà un angolo. Il punto più lontano dal primo angolo ti darà un altro angolo, che può essere adiacente o opposto al primo. Il punto più lontano dalla linea tra questi due angoli (un po 'più intensivo di matematica) ti darà una terza curva. Userei la distanza dal centro come un tie breaker. Per trovare il 4 ° angolo, sarà il punto al di fuori del triangolo formato dai primi 3 angoli che hai trovato, più lontano dalla linea più vicina tra quelle curve.

Questo è un modo molto dispendioso in termini di tempo per farlo e non l'ho mai provato, ma dovrebbe funzionare.

Answer 2

Si potrebbe provare a utilizzare un algoritmo scanline - Per ogni riga del poligono (quindi y = min (y) .. max (y)), ottenere l = min (x) e r = max (x). Calcola la pendenza sinistra/destra (deltax) e confrontala con la pendenza della linea precedente. Se è cambiato (usa un po 'di tolleranza qui), sei in un angolo del rettangolo (o vicino ad esso). Ciò non funzionerà in tutti i casi, poiché la pendenza non può essere quella esatta a causa della bassa risoluzione, ma per i rettangoli di grandi dimensioni e le pendenze non troppo simili, questo dovrebbe funzionare.

Almeno, funziona bene per il tuo esempio:

X0000000000X l = 0, r = 11 
.00000000000 l = 1, r = 11, deltaxl = 1, deltaxr = 0 
..X000000000 l = 2, r = 11, deltaxl = 1, deltaxr = 0 
.....0000000 l = 5, r = 11, deltaxl = 3, deltaxr = 0 
........0000 l = 8, r = 11, deltaxl = 3, deltaxr = 0 
...........X l = 11, r = 11, deltaxl = 3, deltaxr = 0 

Si inizia con la parte superiore del rettangolo in cui si ottengono due valori diversi per L e R, per cui si dispone già di due degli angoli. Sul lato sinistro, per le prime tre righe avrai deltax = 1, ma dopo di esso avrai deltax = 3, quindi c'è un angolo in (3, 3). Sul lato destro, nulla cambia, deltax = 0, in modo da ottenere solo il punto alla fine.

Nota che stai "raccogliendo" gli angoli qui, quindi se non hai 4 angoli alla fine, le pendenze erano troppo simili (o hai un'immagine di un triangolo) e puoi passare a un altro (più esatto) algoritmo o semplicemente dare un errore. Lo stesso se hai più di 4 angoli o altre strane cose come i buchi nel rettangolo. Sembra che sia coinvolto un qualche tipo di rilevamento delle immagini, quindi questi casi possono verificarsi, giusto?

ci sono casi in cui un semplice DeltaX = (x - lastx) non funziona bene, vedere questo esempio per il lato sinistro di un rettangolo:

xxxxxx 
xxxxx deltax = 1 dy/dx = 1/1 = 1 
xxxxx deltax = 0 dy/dx = 2/1 = 2 
    xxxx deltax = 1 dy/dx = 3/2 = 1.5 
    xxxx deltax = 0 dy/dx = 4/2 = 2 
    xxx deltax = 1 dy/dx = 5/3 = 1.66 

volte DeltaX è 0, a volte è 1 È preferibile utilizzare la pendenza della linea dal punto effettivo al punto in alto a sinistra/destra (deltay/deltax). Usandolo, dovrai comunque mantenere una tolleranza, ma i tuoi valori diventeranno più precisi con ogni nuova riga.

Answer 3

Questo sembra un problema di carena convessa.

http://en.wikipedia.org/wiki/Convex_hull

Il tuo problema è semplice, ma la stessa soluzione dovrebbe funzionare.

Answer 4

È possibile utilizzare una trasformazione di hough per trovare le 4 linee più prominenti nell'immagine mascherata. Queste linee saranno i lati del quadrilatero. Le linee si intersecano in un massimo di 6 punti, che sono i 4 angoli e i 2 punti di fuga prospettici.

Questi sono facili da distinguere: selezionare qualsiasi punto all'interno del quadrilatero e verificare se la linea da questo punto a ciascuno dei 6 punti di intersezione interseca una qualsiasi delle linee. In caso contrario, allora quel punto di intersezione è un angolo.

Questo ha il vantaggio che funziona bene anche per immagini disturbate o parzialmente ostruite o se la segmentazione non è esatta.

en.wikipedia.org/wiki/Hough_transform

Example CImg Code

sarei molto interessati ai tuoi risultati. Ho pensato di scrivere qualcosa del genere io stesso, per correggere le foto dei fogli di carta presi in un angolo. Attualmente sto lottando per pensare a un modo per correggere la prospettiva se i 4 punti sono noti

p.s.

Verificate anche Zhengyou Zhang, Li-Wei He, "Lavagna bianca scansione e miglioramento dell'immagine" http://research.microsoft.com/en-us/um/people/zhang/papers/tr03-39.pdf per una soluzione più avanzata per il rilevamento quadrilatero

Ho chiesto una questione connessa, che cerca di risolvere il prospettiva trasformare: proportions of a perspective-deformed rectangle