Computer Science and Application计算机科学与应用, 2011, 1, 7-11 http://dx.doi.org/10.12677/csa.2011.11002 Published Online June 2011 (http://www.hanspub.org/journal/csa/) Copyright © 2011 Hanspub CSA Improvement on the Stochastic Completion Field Xiaofang Shao1, Xin Zhang1, Mingjuan Cai2 1Qingdao Branch of Naval Aeronautical Engineering Institute, Qingdao 2Naval Equipment Academa, Shanghai Email: xiaoxiao_0731@163.com Received: Apr. 25th, 2011; revised: May 16th, 2011; accepted: May 21st, 2011. Abstract: Recognizing subjective contour is an important visual psychological phenomenon, which demon- strating remarkable capability of human vision. Among the related works on subjective contour extraction, the stochastic completion field’s model stands out. However, there are still some computation problems of this model which are still unsolved. This paper presents a perceptual completion method for subjective con- tour to overcome these problems. The algorithms suggested use edge evidences and local orientations to con- strain possible geometrical groupings and completions and experimental results show its superiorities. Keywords: Stochastic Completion Fields; Subjective Contour; Perceptual Completion 随机修复场模型的改进 邵晓芳 1,张 欣1,蔡明娟 2 1海军航空工程学院青岛分院,青岛 2海军装备研究院,上海 Email: xiaoxiao_0731@163.com 收稿日期:2011年4月25日;修回日期:2011 年5月16 日;录用日期:2011 年5月21 日 摘 要:主观轮廓是一种重要的视觉心理现象,体现了人类视觉惊人的感知修复能力,而随机修复场模 型则是针对主观轮廓提出的一个比较有影响力的计算模型。针对随机修复场模型存在的问题提出了一个 改进方案。该方案建立了一个根据图像边缘的位置和取向构成的几何关系提取主观轮廓的综合性解决方 法。实验结果验证了算法的有效性。 关键词:随机修复场;主观轮廓;感知修复 1. 引言 主观轮廓是一种在同质物理刺激的视野中根据图 像特征的整体约束知觉到完整轮廓的视觉心理现象, 体现了视觉系统惊人的感知识别和修复图像缺失部分 的能力。主观轮廓作为一种理解目标轮廓知觉、形状 知觉、深度知觉和视觉注意机制的重要现象,不仅仅 有助于解决图像信息处理和机器视觉中的一些经典难 题,而且对于认知科学具有特别重要的意义。相关研 究工作的综述可参见文献[1]。本文主要目标是指出相 关工作中的随机修复场模型存在的一些问题并进行改 进。文章的内容安排如下:第二节简要介绍随机修复 场模型并指出其中存在的问题;第三节介绍我们改进 方法;然后是实验结果和结束语。 2. 随机修复场模型 Williams和Jacobs提出的随机修复场[2](stochastic completion fields)模型是针对主观轮廓现象提出的比 较有影响力的模型。该模型根据“哺乳动物的视觉皮 层精细地对应于特定的位置和方向”这种生理学现 象,提出了以图像平面的网格点上的“粒子”的随机 行走作为边界形状的先验概率分布模型,“粒子”的 随机移动体现Gestalt定律 中的 相近性 和连续 性原则 , 运动轨迹的分布完全由所在点的位置和轮廓的方向决 定,其最大似然路径通过一条最小能量曲线连接“源 点”和“目点”,最后用两个格林函数的卷积计算修 复场。 总体说来,这一模型中没有涉及以下一些问题: 邵晓芳等 随机修复场模型的改进 8 | 1. 引起主观轮廓的亮度刺激的特定形式; 2. 对一幅原始图像如何进行预处理,提取关键 点,形成“粒子”运动的“源集”(即粒子随机移动的 起点集)和“目集”(粒子随机移动的终点集); 3. “源集”和“目集”之间的可连接关系如何判 定,也就是如何确定粒子随机行走的起点和终点; 4. 经过复杂的计算,只能得到估计的修复区域, 无法直接得到感知边界。 3. 随机修复场模型的改进 与前一小节指出的四个问题相对应,我们提出的 改进方案包括以下四个部分: 1. 通过有向边缘检测提取引起主观轮廓的亮度 刺激模式; 2. 通过关键点提取算法提取形成“粒子”运动 的“源集”(即粒子随机移动的起点集)和“目集”(粒 子随机移动的终点集); 3. 采用基于可连接关系图的方法确定“源集” 和“目集”之间的可连接关系; 4. 采用欧拉螺旋曲线连接“源集”和“目集”, 既减小随机修复场模型算法的复杂性,又可以得到感 知的边界,不再是一个修复的区域。 其中有向边缘检测及关键点提取的算法请参见文 献[3],在此主要介绍基于可连接关系图的判断方法以 及如何应用欧拉螺旋曲线连接“源集”和“目集”。 3.1. 可连接关系判断 基于可连接关系图的判断方法针对图像中不可见 的轮廓之间不存在遮挡关系的情况,研究如何根据关 键点的位置和取向信息判断其可连接关系。下面具体 介绍该算法的原理和实现流程[4]。 为便于描述,给出以下定义: 定义 1 关键点的关联取向:对于某一关键点 A , 如果图像中有 条边缘碎片通过 (1)nn A ,每条边缘碎 片在 A 附近的取向角为 Ai (1, ,in ),则称 Ai 为关 键点 A 的第 i个关联取向,而关键点共有 n个关联 取向。 A 定义 2 可连接关系:对任两个关键点 A和 B ,如 果式(1)得到满足,则认为 A和 B 满足 A B的可连接 关系;如果 A 和 B 互换位置后仍然满足式(1),则认为 A 和 B 之间满足双向可连接关系。 2 2 d 2σ min90 e AB Ai ic c (1) 式中, AB 表示 和 A B 两点连线的取向角,表 示A和B之间的距离, d Ai 表示与关键点 A 第 个关联 取向(i i 1,, n ),c和 分别为控制取向角差别和距离 大小的参数。 定义 3 关键点之间的最小距离均值:设一幅图像 中有 N 个关键点 12 ,,, N A AA,对于每个关键点 Aj(1, , j N ),如果 Aj与其没有实际边缘连接的关键 点之间的距离最小值为 min_ j d,则 所 有min_ j d的均值称 为关键点之间的最小距离均值,记做min d。 定义 4 一级可连接关系:如果两个关键点 A和 B 在9c 且3 时具有双向可连接关系,则称 A 和 B 具有一级可连接关系。其中,c的门限设在 9是根据 文献[5]的研究成果,这些研究成果说明一般情况下, 取向角的差值在 0~之间的数字化线段有可能是 共线或者平行的;而 9 3 限制了距离参数对可连接关 系的影响。 定义 5 二级可连接关系:如果两个关键点 A 和 B 在94且c5 min d 时具有双向可连接关系,则称 之为二级可连接关系。 定义 6 三级可连接关系:如果两个关键点 A 和 B 在 且90c min dd时具有双向可连接关系,则称之 为三级可连接关系。 定义 7 连接冲突:设有四个关键点 A 、 B 、 和 C D ,其中 和 A B 满足双向可连接关系, 和 C D 满足双 向可连接关系。因为关键点的位置是由其在图像中的 位置固定的,在假定图像中不存在不可见轮廓之间的 遮挡关系情况下,如果 A B 之间的相连线段与CD之 间的相连线段之间存在交叉点,则判 A 定 B 和CD之 间的连接关系发生连接冲突。 可连接关系图的生成主要通过以下步骤来实现: Step 1:初始化可连接关系图:根据关键点的检测 结果,生成一幅加权图G,图G为一个三元组 ,,EGV ,其中,顶点集V由所有关键点组成(令 N 表示图G的顶点数),各顶点的位置与关键点在图像中 的位置一致; 为V中各点之间的边,如果两个关键 点在图像的边缘图中已经有边缘线相连接,则在 E E 中 添加相应的边; 用于描述V中顶点之间可连接关系, Copyright © 2011 Hanspub CSA 邵晓芳等 | 随机修复场模型的改进 Copyright © 2011 Hanspub CSA 9 初始为空。对于图 G每个顶点 ,记录与相应关 键点的关联取向信息 vV , vn 12 ,, vv ,以下处理步骤 中如果可连接关系是存入 的,同时把形成可连接关 系的关联取向信息一并存入 。 Step 2:处理各关键点之间的一级可连接关系 根据图中各顶点的位置和关联取向信息判别没有 连接边的各点之间是否具有一级可连接关系,在具体 的判别过程中 c和 的初始值都设很小(根据一级可 连接关系的定义), , 9c2 。对于每个顶点 v 进行以下处理: 1) 如果与 v具有一级可连接关系的顶点只有一 个,则进一步判断这两个顶点之间的可连接关系是否 与E中的边产生连接冲突,如果有连接冲突则删除该 连接关系,否则将该连接关系存入 ; 2) 如果与 v具有一级可连接关系的顶点有多个, 则根据这些点到 v的邻近性进行排序,只保留与 E 中的 边没有连接冲突且最邻近的可连接关系,并存入 。 Step 3:连接冲突检测 检测 中的连接关系是否有连接冲突。如果 中 的连接关系都有连接冲突,则清空 并且根据式(2)修 正形成可连接关系的关联取向 Ai 和 B j ;否则根据 E 和 共同描述的图 G中各顶点之间的连接关系在图 G 中搜索最小圈,如果存在,则跳转Step 7,否 则删除 中的连接关系。 90 90 x x x if [0,9 otherwise x 0 ) , , x Ai Bj (2) Step 4:处理各关键点之间的二级可连接关系 选取一定步长增大 c和 ,判别没有连接边的各 点之间是否具有二级可连接关系,直到图 G中出现边 数大于 3的最小圈或者。然后对于每个顶点v 进行以下处理: 45c 1) 如果与 具有二级可连接关系的顶点只有一 个,则进一步判断这两个顶点之间的可连接关系是否 与 v E 中的边产生连接冲突,如果有连接冲突则删除该 连接关系,否则将该连接关系存入 ; 2) 如果与 具有二级可连接关系的顶点有多个,则 根据这些点到 的邻近性进行排序,只保留与 v v E 中的边 没有连接冲突且 min dd的可连接关系,并存入 。 Step 5:连接冲突检测 检测 中的连接关系是否有连接冲突,如果有, 则清空 ;否 则 根 据 E 和 共同描述的图 G中各顶点 之间的连接关系在图 G中搜索最小圈,如果存在,则 跳转 Step 7。 Step 6:处理三级可连接关系 取 ,判别顶点之间是否具有三级可连接关 系,同样将没有连接冲突的可连接关系存入 90c 。 Step 7:输出可连接关系的判断结果 根据 描述的图 G中各顶点之间的连接关系在图 G中添加相应的边,用虚线标识,并输出 E 、 。 3.2. 缺失边界修复 通过可连接关系的判断,主观轮廓的感知修复问 题被转化为:给定关键点对 0 (, A 0 )xy 、,以 及它们相应的取向角 11 (, )Bx y 0 、1 ,目标是找到连接两点 的能量最小曲线,该曲线满足在 A、 B 两点的边界条 件。 满足这些约束条件的欧拉螺旋曲线就是以“曲率 变化和最小”为能量最小原则进行两点之间的平滑连 接,即满足使能量函数 最小。 c E 2d cs E s (3) 式中, d()d s s s ,s代表弧长, () s 为曲线 的曲率函数, s 为曲线的曲率变化函数。 欧拉螺旋曲线方程的一般形式是[5]: 式中, 0 ()ss ,为曲率函数,其中 0 为初 始点曲率,s 为弧长, 为曲率沿弧长的变化系数, 而和 分别如式(5)、式(6)所示。 ()Cs()Ss 22 00 00 00 0 22 000 00 00 sign co si s n sin ππ 22 () 2 () cos 22 ππ s CC x xs y ys s SS (4) 邵晓芳等 随机修复场模型的改进 10 | 2 0 π () cosd 2 s Cs (5) 2 0 π () sind 2 s Ss (6) 这里,我们已知点对的位置和取向信息,如果求 得,就可以计算 01 , 、 L ( L 为总的弧长),从而获 得欧拉螺旋曲线的完整描述。 考虑典型主观轮廓图形的特点,轮廓线一般由直 线或圆弧组成,因此插值所得的轮廓线或者是 0 (圆弧),或者是且 00 0 (直线)。上述计算 过程可依据边界条件得到进一步的简化。 根据上述原理,对于每一个存储在可连接关系图 的 G 中的可连接关系,基于欧拉螺旋曲线的缺口修 复的具体计算过程如下: Step 1:采用Ullman的双弧插值算法[7]获得曲率和 弧长的初始估计值 和,如 0 0 L0 ( 为一个预定 义的非常小的正数),则直接用直线段连接起点A和终 点 B ,并跳出本次循环。 Step 2:根据 和 ,采用迭代优化的方式计算 欧拉螺旋曲线的最佳参数 和 ,迭代终止的条件是 根据 、 、 0 0 0 L b b L b b L 和1 计算出的曲线终点的位置与 1 (, 1 ) x y之间的误差小于一定阈值 或者迭代次数大 于1000; err t Step 3:根据 和 计算参数 b b L ,从而获得曲线 的参数描述; Step 4:根据曲线参数计算在起点A和终点 B 之 间的轮廓修复曲线上点的坐标并在图像中添加起点 A 和终点 B 之间的修复曲线。 上述计算过程中, 实际上是对 b B 点的曲率 1 的 估计,而 则是对式(4)中 b L L 的估计。 4. 实验结果 为验证算法的有效性,本文分别对几幅典型的主 观轮廓图像进行了实验。实验结果如图 1、图 2所示。 各实验中, 0.5 ,。随机修复场模型的相 关实验结果参见文献[2],比较将在结论中给出。 1.5 err t 图1是对Kanisza矩形的实验结果。这幅实验图像 是是直线型主观轮廓的典型代表[4]。图中,图(a)为原 始图像;图(b )为关键点检测的结果;图(c)为可连接关 系图的初始化结果;图(d)为可连接关系的判断结 Figure 1. The results of Kanisza rectangle (a) Original image (b) Key results (c) Initialize the connection graph the results (d) Con- nection Diagram (e) Profile results after repair 图1. 对Kanisza 矩形的实验结果 (a) 原始图像 (b) 关键点检测结 果 (c) 连接图初始化结果 (d) 连接图 (e) 轮廓修复后的结果 Figure 2. The experimental results of subj_contour (a) Original image; (b) Key results; (c) Initialize the connection graph the re- sults; (d) Connection Dia gram (e) Profile re sults after repair 图2. 对subj_contour的实验结果 (a) 原始图像 (b) 关键点检测结 果 (c) 连接图初始化结果 (d) 连接图 (e) 轮廓修复后的结果 果,其中的实线表示存储在E中的可连接关系,而虚 线表示存储在 中的可连接关系,实验中 9c 、 2 时就得出了图(d)所示的连接关系;图(e)为轮廓 缺口修复的最终结果。可以看到,算法的运行效果还 是比较好的。 图2是对 subj_contour 的实验结果。这幅实验图 像是是曲线型主观轮廓的典型代表。图中,图(a)为原 始图像;图(b )为关键点检测的结果;图(c)为可连接关 系图初始化的结果;图(d)为可连接关系的判断结果, 其中的实线表示存储在 E 中的可连接关系,而虚线表 Copyright © 2011 Hanspub CSA 邵晓芳等 随机修复场模型的改进11 | 示存储在 中的可连接关系。参数设置为 、 39c 62 ;图(e)为轮廓缺口修复的最终结果。 在图 2中,由于关键点检测的结果多检测了三个 伪关键点(在图 2e)中小三角的位置,却漏检了一个真 正的关键点,因而后续的处理过程中形成了一个错误 的连接判断。这两组实验结果既说明了关键点的检测 方法尚需改进和提高,也说明了可连接关系判断方法 对关键点检测结果具有一定程度的容错性。 5. 结束语 本文围绕主观轮廓的感知修复问题展开研究,针 对随机修复场模型存在的问题,提出了改进措施及具 体实现的相关算法并进行了实验验证。 与随机修复场模型相比,本文工作的主要特点是: (1) 将视觉生理机制与图像处理算法有机地结合到一 起,提出了一个比较完善的综合性解决方案,给出了 图像底层特征的处理方法,解决了随机修复场模型中 存在的亮度信息处理以及源点目点提取的问题;(2) 具体实现算法以取向估计为基础实现了对轮廓特征提 取的一体化处理,进而进行轮廓组织及缺口修复,解 决了源点目点之间可连接关系的判定问题;(3) 修复 之后的轮廓不再是估计的修复区域,而是直接的感知 边界。 但是,本文的工作还存在一些不足,需要进一步 完善和扩展的研究工作主要有:(1) 随机修复场模型 除了存在上述三个基本问题之外,模型没有考虑边缘 轮廓的封闭性问题以及Gestalt 组合定律中封闭律,而 精神物理学研究表明,封闭性是主观轮廓的主要特性。 对此本文也没有考虑;(2) 基于取向估计的关键点检 测算法的准确率问题,算法还存在一定的误检率和漏 检率,因而尚需改进和提高;(3) 该算法还不能处理 现实中比较复杂的遮挡关系。如何解决这些问题将是 我们下一步研究工作的重点。 参考文献 (References) [1] 邵晓芳, 孙即祥, 张欣. 认知轮廓研究进展[J]. 计算机应用研 究, 2008, 25(7): 1953-1955. [2] L. R. Williams, D. W. Jacobs. Stochastic completion fields: A neural model of tllusory contour shape and salience. Proceeding of 5th International Conference on Computer Vision (ICCV ’95), Cambridge, 1995: 408-415. [3] 邵晓芳, 孙即祥, 张欣等. 一种基于取向估计的关键点检测 算法[J]. 电光与控制, 2008, (4): 33-36. [4] X. F. Shao, M. R. Jiang, R. P. Sun, et al. A systematic method for illusory contour. Proceedings of the 2008 IEEE International Conference on Information and Automation. 2008: 1448-1452. [5] J. H. Elder, R. M. Goldberg. Ecological statistics of Gestalt laws for the perceptual organization of contours. Journal of Vision, 2002, 2(4): 324-353. [6] B. K. Benjamin, F. Ilana, and P. Ana-Maria. Euler spiral for shape completion. International Journal of Computer Vision, 2003, 54(1): 159-182. [7] S. Ullman. Filling in the gaps: The shape of subjective contours and a model for their generation. Biological Cybernetics, 1976, 25(1): 1-6. Copyright © 2011 Hanspub CSA |