How can I prove that this edge traversing algorithm works?

Question

I've come across an algorithm, which finds the contour of a figure, but I have trouble proving why it works, I have sort of understood why it works, but I can't derive the formulas used in there myself.

This is the algorithm:

Let's assume that we have a binary image (with the figure being black and background being white). All the pixels are stored in a binary matrix with 1 being white and 0 being black.

0) Find the first black pixel (for example if it's a square then it's located in the top left corner).

1) Set Lx = x and Ly = y (coordinates of that first pixel), and Rx = x - 1 and Ry = y. Also keep 2 constants firstX = x and firstY = y (we'll need them later).

2) Calculate Tx = Rx + Ly - Ry and Ty = Ry + Rx - Lx.

3) Do the following loop:

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

In the code above m is the original image and m2 is the image containing only the contour.

I have tried to visualize how this works and this is what i got:

So apparently it's doing some sort of zigzag movements to get those zeros on edges and determine the contour.

So, my question is, is this a known algorithm? And how exactly were these formulas derived:

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

and

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

?

Answer 1

Hints:

Throughout execution, R, L and T are immediate 8-neighbors (in the Moore sense).

The algorithm repeatedly assigns T to one of R and L, depending on the value at T, so that L is always on a black pixel and R on a white one. Then it recomputes T by rotating RL around R.

---

Assume for a while that Rx=Ry=0; then if L is a 4-neighbor, (Tx,Ty):=(Ly,-Lx), a rotation by 90°; else, (Tx,Ty):=((Lx+Ly)/2,((Ly-Lx)/2), a rotation by 45°. This rule is illustrated below:

---

The initial configuration is the top-left in the figure, with L being the first black pixel. Given the progression rule, it is obvious that the algorithm will follow a chain (sequence of 8-connected pixels).

In fact, for a position of R, one rotates L around it, until a black pixel is found; then one moves R to that pixel. This is the very procedure named Radial Sweep.

We can rewrite it in the equivalent form (after renaming R=B, L=W, and defining Rot to be the rotation rule above.)

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

Remains to prove that

1. the chain is closed (we will come back to the starting pixel),

2. it is the contour of a blob (every pixel in the chain has both black and white neighbors),

3. no pixels are missed.

More precisely, L follows the inner contour, while R follows the outer one (and T doing both).