我怎样才能证明这个边遍历算法有效呢？

Question

我遇到了一种算法，它可以找到图形的轮廓，但我无法证明它为什么有效，我有点理解它为什么有效，但是我无法自己推导出其中使用的公式。

这是算法：

假设我们有一个二值图像（图形为黑色，背景为白色）。所有像素都存储在二进制矩阵中，1为白色，0为黑色。

0) 找到第一个黑色像素（例如，如果它是正方形，则它位于左上角）。

1) 设置 Lx = x 和 Ly = y（第一个像素的坐标），以及 Rx = x - 1 和 Ry = y。还要保留 2 个常量 firstX = x 和 firstY = y（稍后我们将需要它们）。

2) 计算Tx = Rx + Ly - Ry 和Ty = Ry + Rx - Lx。

3) 执行以下循环：

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

在上面的代码中，m是原始图像，m2是仅包含轮廓的图像。

我试图想象这是如何工作的，这就是我得到的：

很明显，它正在做某种锯齿形运动以获得边缘上的那些零点并确定轮廓。

所以，我的问题是，这是已知算法吗？这些公式究竟是如何推导出来的：

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

和

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

?

Answer 1

提示:

在整个执行过程中，R、L 和 T 是直接的 8 个邻居（在 Moore 意义上）。

该算法根据 T 处的值重复将 T 分配给 R 和 L 之一，以便 L 始终在黑色像素上，而 R 始终在白色像素上。然后它通过围绕 R 旋转 RL 来重新计算 T。

暂时假设Rx=Ry=0；那么如果 L 是一个 4-neighbor，(Tx,Ty):=(Ly,-Lx)，旋转 90°；否则，(Tx,Ty):=((Lx+Ly)/2,((Ly-Lx)/2)，旋转 45°。此规则如下所示：

初始配置为图中左上角，L为第一个黑色像素点。给定级数规则，很明显该算法将遵循一条链（8 个连接像素的序列）。

实际上，对于R的位置，围绕它旋转L，直到找到黑色像素；然后将 R 移动到该像素。这就是名为 Radial Sweep.

的过程

我们可以改写成等价的形式（重命名R=B、L=W后，定义Rot就是上面的轮换规则。）

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

还有待证明

链已关闭（我们将回到起始像素），
它是一个斑点的轮廓（链中的每个像素都有黑色和白色的邻居），
没有遗漏任何像素。

更准确地说，L 遵循内部轮廓，而 R 遵循外部轮廓（T 两者都做）。

我怎样才能证明这个边遍历算法有效呢？

How can I prove that this edge traversing algorithm works?

algorithm

image-processing

matrix

geometry

computational-geometry