Come posso dimostrare che questo algoritmo di attraversamento dei bordi funziona?

Question

Mi sono imbattuto in un algoritmo, che trova il contorno di una figura, ma ho difficoltà a dimostrare perché funziona, ho una specie di capito perché funziona, ma non riesco a ricavare le formule usate lì dentro .

Questo è l'algoritmo:

Supponiamo che abbiamo un'immagine binaria (con la figura di essere nero e sfondo bianco di essere). Tutti i pixel sono memorizzati in una matrice binaria con 1 bianco e 0 nero.

0) Trova il primo pixel nero (ad esempio se è un quadrato, si trova nell'angolo in alto a sinistra).

1) Impostare Lx = x e Ly = y (coordinate di quel primo pixel) e Rx = x - 1 e Ry = y. Inoltre mantieni 2 costanti firstX = x e firstY = y (ne avremo bisogno in seguito).

2) Calcolare Tx = Rx + Ly - Ry e Ty = Ry + Rx - Lx.

3) Eseguire il seguente ciclo:

do { 
     if (m[Tx][Ty] == 0) { 
      Lx = Tx; 
      Ly = Ty; 
      m2[Tx][Ty] = 0; 
     } else { 
      Rx = Tx; 
      Ry = Ty; 
     } 
     if (Lx == Rx || Ly == Ry) { 
      Tx = Rx + Ly - Ry; 
      Ty = Ry + Rx - Lx; 
     } else { 
      Ty = (Ly + Ry - Lx + Rx)/2; 
      Tx = (Lx + Rx + Ly - Ry)/2; 
     } 
    } while (Tx != firstX || Ty != firstY); 

Nel codice precedente m è l'immagine originale e m2 è l'immagine contenente solo il contorno.

ho cercato di visualizzare come funziona e questo è quello che ho ottenuto:

Quindi a quanto pare sta facendo una sorta di movimenti a zig-zag per ottenere quei zeri sui bordi e determinare il contorno.

Quindi, la mia domanda è, è un algoritmo noto? E come esattamente sono state queste formule derivate:

Tx = Rx + Ly - Ry; 
Ty = Ry + Rx - Lx; 

e

Ty = (Ly + Ry - Lx + Rx)/2; 
Tx = (Lx + Rx + Ly - Ry)/2; 

?

Answer 1

consigli:

corso dell'esecuzione, R, L e T sono immediati 8-vicini (nel senso Moore).

L'algoritmo assegna ripetutamente T a uno di R e L, a seconda del valore di T, in modo che L sia sempre su un pixel nero e R su uno bianco. Allora ricalcola T da RL ruotando attorno R.

---

assumere per un istante che Rx=Ry=0; quindi se L è un 4-vicino, (Tx,Ty):=(Ly,-Lx), una rotazione di 90 °; altrimenti, (Tx,Ty):=((Lx+Ly)/2,((Ly-Lx)/2), una rotazione di 45 °. Questa regola è illustrato di seguito:

---

La configurazione iniziale è alto a sinistra nella figura, con L essendo il primo pixel nero.Data la regola di progressione, è ovvio che l'algoritmo seguirà una catena (sequenza di 8 pixel connessi).

Infatti, per una posizione di R, si ruota attorno a L, fino a quando viene trovato un pixel nero; quindi si sposta R a quel pixel. Questa è la stessa procedura denominata Radial Sweep.

Possiamo riscrivere nella forma equivalente (dopo che rinomina R=B, L=W, e definendo Rot essere la regola di rotazione sopra.)

B, W= B0, LeftOf(B0) 
do 
    while Rot(B, W) is White 
     W= Rot(B, W) 
    B= Rot(B, W) 
while B != B0 

Resta da dimostrare che

1. catena è chiuso (torneremo al pixel iniziale),

2. è il contorno di un blob (ogni pi xel nella catena ha entrambi i vicini in bianco e nero),

3. nessun pixel è mancato.

Più precisamente, L segue il contorno interno, mentre R segue quello esterno (e T fa entrambi).