Làm thế nào tôi có thể chứng minh rằng thuật toán vượt qua cạnh này hoạt động?

Question

Tôi đã gặp một thuật toán tìm đường bao hình, nhưng tôi gặp khó khăn trong việc chứng minh tại sao nó hoạt động, tôi có loại hiểu tại sao nó hoạt động, nhưng tôi không thể lấy được các công thức được sử dụng trong đó .

Đây là thuật toán:

Giả sử rằng chúng ta có một hình ảnh nhị phân (với con số này là đen và background là màu trắng). Tất cả các điểm ảnh được lưu trữ trong một ma trận nhị phân với 1 là màu trắng và 0 là màu đen.

0) Tìm pixel đen đầu tiên (ví dụ: nếu đó là hình vuông thì nó nằm ở góc trên cùng bên trái).

1) Đặt Lx = x và Ly = y (tọa độ của pixel đầu tiên đó) và Rx = x - 1 và Ry = y. Cũng giữ 2 hằng số firstX = x và firstY = y (chúng ta sẽ cần chúng sau này).

2) Tính Tx = Rx + Ly - Ry và Ty = Ry + Rx - Lx.

3) Làm vòng lặp sau:

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); 

Trong đoạn mã trên m là hình ảnh ban đầu và m2 là hình ảnh chỉ chứa các đường viền.

Tôi đã cố gắng để hình dung cách làm việc này và đây là những gì tôi đã nhận:

Vì vậy, dường như nó đang làm một số loại của các phong trào zigzag để có được những số không trên các cạnh và xác định đường viền.

Vì vậy, câu hỏi của tôi là, đây có phải là thuật toán đã biết không? Và làm thế nào chính xác được các công thức có nguồn gốc:

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

và

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

?

Answer 1

gợi ý:

suốt thực hiện, R, L và T là ngay lập tức 8-láng giềng (theo nghĩa Moore).

Thuật toán liên tục gán T cho một trong R và L, tùy thuộc vào giá trị tại T, sao cho L luôn ở trên một pixel đen và R trên một màu trắng. Sau đó, nó tính toán T bằng cách xoay RL xung quanh R.

---

Giả sử trong một thời gian là Rx=Ry=0; sau đó nếu L là 4 hàng xóm, (Tx,Ty):=(Ly,-Lx), quay 90 °; khác, (Tx,Ty):=((Lx+Ly)/2,((Ly-Lx)/2), một vòng quay 45 °. Quy tắc này được minh họa dưới đây:

---

Cấu hình ban đầu là phía trên bên trái trong hình, với L là điểm ảnh đen đầu tiên.Với quy tắc tiến triển, rõ ràng là thuật toán sẽ theo một chuỗi (chuỗi 8 pixel được kết nối).

Thực tế, đối với vị trí của R, một biến L xung quanh nó, cho đến khi tìm thấy một pixel đen; sau đó, di chuyển R đến điểm ảnh đó. Đây là thủ tục rất có tên là Radial Sweep.

Chúng ta có thể viết lại nó trong các hình thức tương đương (sau khi đổi tên R=B, L=W, và xác định Rot là quy tắc xoay vòng ở trên.)

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

Vẫn còn để chứng minh rằng

1. chuỗi bị đóng (chúng tôi sẽ quay lại pixel bắt đầu),

2. nó là đường viền của một đốm màu (mỗi pi xel trong chuỗi có cả hàng xóm màu đen và trắng),

3. không có pixel nào bị bỏ qua.

Chính xác hơn, L theo đường bao bên trong, trong khi R theo sau đường viền bên ngoài (và T làm cả hai).