二值图拓扑性质 —— 迭代修正

本文最后更新于:2022年7月4日 上午

除了将二值图中的局部处理结果直接加起来以外,我们还可以用这些局部处理结果来生成一张新的二值图。本文记录生成二值图的原则和一种并行策略。

迭代修正

除了将二值图中的局部处理结果直接加起来以外,我们还可以用这些局部处理结果来生成一张新的二值图。根据原图中的对应图像单元的局部计算结果,我们可以确定:新的二值图中相应图像单元的值。新的二值图可以被作为:另一个计算周期的输入。这个操作被称为:迭代修正

迭代修正方法非常有用,因为它使得我们可以将:那些很难直接使用局部计数法来进行处理的图像,逐步地转化为:可以使用局部计数法来进行处理的图像。

通过类似迭代腐蚀的操作,我们有可能“蚀刻”出物体的边界,从而,最终得到一张“骨架”图。所谓“骨架”图是指:经过蚀刻以后,一幅图中所剩下的部分。在蚀刻过程中,图像中的许多图像单元(即:像素点)都被“侵蚀”掉了。蚀刻过程的终止条件为:如果继续侵蚀掉图中的任何一个图像单元,都会改变原图的连通关系。避免对最后得到素描图继续进行侵蚀,是非常重要的。为了解决这个问题,我们需要考虑:当我们改变图像中的某一个像素点的值时,Euler数会发生什么变化。那些不改变Euler数的操作被称为是守恒的

幸运的是,由于Euler数满足集合可加性,因此,Euler差值只依赖于:某一个图像单元的邻域。我们假设:某一个图像单元的灰度值为零,并且,它邻域内的所有图像单元的灰度值都为零:如果我们将该图像单元的灰度值从0变为1:

那么,这个操作将会使得图像的Euler数增加1。这个结果并不依赖于:该图像单元邻域以外的其他图像单元上的值。类似地,如果在某一图像单元的邻域中,只有一个图像单元的值为0(或1),那么,改变该图像单元的值,Euler 数不会发生变化:因为,这个操作只是“扩大”一个物体(或缩小空洞)。

在我们的方法中,每一个图像单元的周围都有六个图像单元和它相连(我们将其称为“邻居”)。每一个“邻居”的值可以为0或1.因此,总共有$2^6=64$种可能的邻域结构。对于每一种邻域结构,我们都可以计算其 Euler 差值$E*$,即:当邻域中心的图像单元由0变为1时,该邻域的Euler 数所发生的变化(当邻域中心的图像单元由1变为0时,该邻域的Euler差值为:$-E*$)。

我们所特别感兴趣的是:那些 $E*=0$ 的邻域结构,因为,我们可以任意改变这些邻域的中心像素点上的值,而不改变其Euler数。我们可以将这64种邻域结构,分为如下5种情况:

  1. $E*=+1$: 六个“邻居”的值全为0。这种情况对应于:中心像素点的值的变化(即:由0变为1),将产生出一个新的物体;
  2. $E*=+1$: 六个“邻居”的值全为1。这种情况对应于:中心像素点的值的变化(即:由0变为1),将填满一个洞;
  3. $E*=0$: 我们将这六个“邻居”看作一个圆周序列,那么,这个圆周序列刚好能被分割为两个子序列:并且,其中一个子序列的值全为1,而另一个子序列的值全为0;
  4. $E*=-1$: 圆周序列包含:两个值全为1的子序列,并且,这两个子序列被两个值全为0子序列“隔开”。在这种情况下,中心像素点的变化(即:由0变为1)对应于:两个物体被连接在一起(成为一个物体),或者,一个洞被“分”为两个洞。
  5. $E*=-2$: 三个0和三个1彼此间隔地排列成一个圆周序列。这种情况下,中心像素点的变化(即:由0变为1)对应于:三个物体被连接成为一个物体:或者,一个洞被“分割”为三个洞。

因为每个图像单元只有6个邻居,因此,上面5种情况,包含了所有可能出现的情况。我们根据Euler数的变化,将这些特殊的邻域结构
分别记为:$ N_{+1}, N_{0}, N_{-1} $ 和 $ N_{-2} $.

此外,我们还有一个难题没有解决。在使用并行方式对图像进行处理时,我们可能在“不知不觉”之中,就改变了其Euler数。这是因为:一个图像单元的“邻居”的值,可能会在“不知不觉”中发生变化,从而使得:对该图像单元的Euler差值的计算失效。如果我们用串行方式来进行处理,那么,将不会出现这种问题。当然,我们并不想要对图像进行串行处理。解决这个问题的另一种方法是:将图像分割为:许多交织在一起的子域,从而使得:图像单元的“邻居”位于不同的子域中;然后再用串行的方式对子域进行处理。

如果我们以正方形(作为基本单元)来对图像进行剖分,那么,要保持Euler数不变,所需要的最小子域数为3。我们可以使用周期序列$1,2,3,1,2,3…$来对图像中的某一行图像单元(即:像素点)进行编号;对于下面一行的图像单元,其标注方式和这一行类似,只是编号从2开始:再下一行的编号从3开始。根据我们所使用的关于邻域的定义,图像单元和它的“邻居”的编号是不同的。我们用三种不同颜色来对:正六边形剖分方式,进行编号。之后可以分别并行处理组1,组2,组3的像素。

参考资料

  • 伯特霍尔德・霍恩著 BERTHOLDKLAUSPAULHORN. 机器视觉[M]. 中国青年出版社, 2014.

二值图拓扑性质 —— 迭代修正
https://www.zywvvd.com/notes/study/image-processing/robot-vision/chapter-4/iter-corr/iter-corr/
作者
Yiwei Zhang
发布于
2022年5月8日
许可协议