在图像分析中,经常需要判断图像分割所得到的区域之间的关系。通常情况,我们通过八邻接外轮廓(准确说法是扩展边缘,但这样又得费半天口舌解释什么是扩展边缘)来描述一个区域并对区域进行标注,如: 很容易判断两个区域是否相邻(扫描区域的内外边缘像素,如果相邻的像素具有不同的标注值,则为邻居),却较难判断一个区域是否在另一个区域的内部。 如上图中,通过相邻像素的标注值的不同,可以得出A和B互为邻居,A和C互为邻居,却很难知道B和C中,哪个是在A的内部。下面设计算法进行判断。 ====
判断点是否在多边形内部有一个很经典的算法:从该点向任意一方画射线,数该射线与多边形的边的交点数量,如果为奇数则在多边形内部,如果为偶数则在多边形的外部。 这个算法有两个特例: (1)射线和多边形的边重合(下图a,b) (2)射线经过多边形的顶点(下图c,d) 显然,(a)应该算0个交点 ,(b)应该算1个交点,(c)应该算0个交点,(d)应该算1个交点。 总体上来说,这个算法要考虑到几种特殊情况,还是比较繁琐的。下面,针对本文的应用来简化该算法。 数字图像是离散的,通过边界跟踪可以得到全部的轮廓点。 上 图是一个轮廓及待判断点。从该点向X轴画一个射线,与9个轮廓点相交。如果将轮廓的任意两个相邻点的连线作为多边形的一边的话,很不幸,全部交点都是特殊 情况。这里假定轮廓点的排列是有序的,也就是说,是有方向的,只考察轮廓点和它一前一后两个轮廓点之间的关系,则有下面几类情况: 这里对经典的点在多边形内部判断算法进行变形:
为 什么是1个或-1个,2个或-2个呢?这里有方向问题。假设箭头是从下向上的,为-1,箭头是从上往下的,算1,如果箭头是水平的,算0. 这样计算的话,则上图中A类的2种情况分别为1个、1个交点,B类的2种情况分别为2个、-2个交点,C类的2种情况全为0. 如此以来,完全满足前面点在多变形内部的经典算法对几种特殊情况的处理。 为每一个轮廓点赋予一个分值Score,这个分值只与它(Current)和前后两点(Prev,Next)有关,和其它任何点无关。因此,这个分值是静态的,不变化的。我们可以把它计算出来缓存在散列表中。
更进一步,score = prev.Y – next.Y:
_extendContourPointXScoreDic 是一个散列表,储存了轮廓点的Score。因为一般的图像不会特别大,我为Point添加了一个扩展方法GetHashCode32()来获得散列值:
这个散列表还有一个用途——如果某点的散列值在散列表内,则该点在外轮廓上。 判断点是否在轮廓的内部,只需要向左或向右扫描即可。比较向左和向右的扫描长度,选择最短的扫描路线,将扫描所经过的轮廓点的散列值加起来,就是交点数量。该交点数量如果是4的倍数,则代表点在轮廓外,否则,则在轮廓内。 在 扫描的过程中,向左移一点或向右移一点,对应的点的散列值减1或加1,因此,可以省掉移动的过程,用散列值的变化来表示移动。这样又可以加速计算。如果已 知A、B两个区域的 Rectangle,可以先判断,如果B的Rectangle不在A的Rectangle内部,则B一定不在A的内部。这样也可以节省不少计算。 ==== 参考资料:Udi Manber. 算法引论——一种创造性方法. http://www.china-pub.com/26775 P.189。 (xiaotie) |