Come verificare se quattro punti formano un rettangolo

Question

Sto lavorando a un'app di riconoscimento di forma. In questo momento un insieme di punti (x, y) è determinato dal rivelatore d'angolo (punti rossi, img 2.). Quattro di questi punti (nei riquadri rossi, 2.) Sono vertici di un rettangolo (a volte un rettangolo leggermente deformato). Quale sarebbe il modo migliore per trovarli tra gli altri?

Ecco un esempio di un'immagine in ingresso:

e sembra che questo dopo il rilevamento angolo:

Answer 1

Questa non è una risposta alla tua domanda - è solo un suggerimento.

A mio parere, il rilevatore di angoli è un modo scorretto per rilevare i rettangoli: ci vorrà molto tempo per calcolare tutte le distanze punti come suggerito dal matematico . Devi usare un'altra tecnica in questa situazione:

1. Questo timbro è di colore viola, quindi la prima cosa da fare è la segmentazione del colore.
2. Dopo aver terminato con passaggio 1 è possibile utilizzare Houhg transform per rilevare le linee sull'immagine binaria. Oppure trova tutti i contorni nell'immagine.
3. E il passaggio finale è rilevare il rettangolo.

Aggiornamento:

Ecco un'altra soluzione che dovrebbe funzionare anche in immagini grigie.

1. fare una soglia per convertire immagini a 1 bit (io ho usato da 255 come soglia).
2. Trova tutti i contorni nella nuova immagine che hanno un'area più grande di qualche costante (ho preso).
3. Trova rettangolo di delimitazione per ogni profilo e fare un controllo:

ContourArea/BoundingReactangleArea> costante

Colgo l'constant come 0.9.

E questo algoritmo mi ha dato risultato successivo:

Ecco il codice OpenCV:

Mat src = imread("input.jpg"), gray, result; 
vector<vector<Point> > contours; 
vector<Vec4i> hierarchy; 

result = Mat(src.size(), CV_8UC1); 

cvtColor(src, src, CV_BGR2GRAY); 
threshold(src, gray, 200, 255, THRESH_BINARY_INV); 
findContours(gray, contours, hierarchy, CV_RETR_TREE, CV_CHAIN_APPROX_SIMPLE, Point(0, 0)); 

result = Scalar::all(0); 
for (size_t i=0; i<contours.size(); i++) 
{ 
    Rect rect = boundingRect(contours[i]); 
    if (rect.area() > 1000) 
    { 
     double area = contourArea(contours[i]); 
     if (area/rect.area() > 0.9) 
     { 
      drawContours(result, contours, i, Scalar(255), -1); 
     } 
    } 
} 

Answer 2

calcolare il set di 6 lunghezze che si avrà tra ogni coppia di 4 punti distinti. All'interno di questo insieme di 6 lunghezze se ci sono più di 3 valori distinti, non si dispone di un rettangolo (2 lati uguali più lunghezze diagonali uguali)

Answer 3

consideri si dovrebbe aver ricevuto il numero 8 ma sei stato il numero 7, allora si sta andando ad aggiungere il numero 1 (chiamato delta o correzione degli errori) per correggerlo.

In modo simile disporre di coordinate delta rettangolo per correggere il rettangolo. Controlla che il punto (coordinate) rientri nel delta rettangolo.

Le coordinate rettangolo sono come indicato di seguito:

x+delta,y+delta 
x-delta,y+delta 
x+delta,y-delta 
x-delta,y-delta 

farmi sapere se questo funziona bene per voi o se si trova una soluzione migliore

Answer 4

Siete consapevoli che controllando visivamente nuvola di punti che si puoi già distinguere una moltitudine di rettangoli? In altre parole, è probabile che tu trovi molti rettangoli se non fai una sorta di routine di preselezione ...

Ad ogni modo, a parte il metodo già fornito da @mathatician1975, puoi anche controllare se i lati sono (più o meno) paralleli.

Chiamiamo il metodo di @maticatician1975 method 1 e il controllo parallelo method 2. Poi:

%# method 1: 
n1 = |u1-u2| %# 3 sub., 3 mult, 2 add. per distance 
n2 = |u3-u2| %# total of 6 distances to compute. 
n3 = |u4-u3| %# then max 5+4+3+2+1 = 15 comp. to find unique distances 
n4 = |u1-u4|  
n5 = |u4-u2| %# Total: 
n6 = |u3-u1| %# 12 sub., 18 mult., 12 add, 15 comp 



%# method 2: 
w1 = u1-u2  %# 3 subtractions per vector 
w2 = u3-u2  %# total of 4 vectors to compute 
w3 = u3-u2 
w4 = u1-u4     
         %# 12 sub. 
abs(w1-w3) == [0 0 0] %# 3 sub., 3 comp., 1 sign. 
abs(w2-w4) == [0 0 0] %# 3 sub., 3 comp., 1 sign. 

         %# Total: 18 sub., 6 comp. 2 sign. 

Nota che questi sono entrambi caso peggiore; con un po 'di contabilità puoi ridurre drasticamente il costo di entrambi.

Si noti inoltre che method 2 deve sapere in anticipo che i vertici sono già nell'ordine corretto. Se questo non è il caso, aumenterà il costo di un fattore 4, che è più che method 1..

Posso chiederti come stai calcolando le distanze?