Snakes: Active Contour Models 译文 望大家齐心合力，把它整好
2009-06-21 20:10 2004人阅读 评论(8) 收藏 举报
国际计算机视觉学报，321-331(1988)
克吕韦尔学术出版集团，波士顿1987，荷兰制作
蛇：活动轮廓模型
MICHAEL KASS,ANDREW WITKIN,and DEMETRI TERZOPOULOS
加利福尼亚州帕洛阿尔托市山景道3340号，斯伦贝谢Palo Alto研究中心，邮编：94304
摘要
每一个Snake都是能量最小曲线，受外部限制力引导及图像力的影响使它向着线和边缘等特征移动。Snakes是活动轮廓模型：他们自动跟踪附近边缘，准确地使曲线集中。尺度空间（scale-space）的连续性用来去扩大对特征周围区域的捕获。Snakes提供一种许多视觉问题的统一的解决方法，包括检测边，线及主观轮廓；移动跟踪；及立体匹配。我们成功使用Snakes用于交互解释（interactive interpretation），即用户提出一种限制力引导Snake靠近感兴趣的特征。
1 简介
在最近的计算机视觉研究中，低层任务如边缘或线的检测，立体匹配及移动跟踪被广泛的认为是独立的自底向上的过程。Marr和Nishihara[11]强烈的认同这个观点，认为达到2.5维简图,不用高层信息支持，这个计算的开展仅仅使用图像自己。这种连续的死板的方法传播了低层产生的错误，并且没有改正的机会。因此提出了对于低层机理可靠性的迫切的要求。对于低层处理，作为一种不健全但更易实现的目标，我们认为它应该提供几套可选择的方案，这些选择中高层处理也可以被使用，而不是用惟一的结论过早的束缚它们。
在这篇论文中，我们研究其能量最小化，此能量作为一个框架达到这个目标。我们试着设计能量函数，其能量函数的最小值包含这套高层处理可实现的方案。在这些可挑选方案中的选择需要各种研究或者高层的推论。然而，在没有好的高层机制下，我们使用交互方法去探索一个可使用的方案。通过添加合适的能量项去最小化，这对于使用者推动模型到最小值朝着理想的解决方案移动是可能的。这就是活动轮廓模型，即当为位于感兴趣的地方，就可以找到理想解决方案。
能量最小模型在视觉史上有一段丰富的历史，至少可以追溯到Sperling的立体模型[16]。这种模型被认为是典型的自动模型，但是我们发展了交互技术去引导它。交互这种模型允许我们很容易的开发能量格局，并提出一种有效的能量函数，这种函数有最小值且其不太依靠初始点。因此，我们希望高层交互是易于管理的而不是受不必要不可逆的低层的限制。
我们把找图像显著轮廓，如边，线，主观轮廓以及在运动中跟踪轮廓和在立体观测中匹配它们都归为这类问题。我们动态的寻找图像轮廓和传统的检测连接边缘是不同的。在我们的模型中，关键问题如轮廓的连通性和角的存在影响了能量函数，于是也影响到了局部最优轮廓的细节结构。这些关键问题在原则上能够被高层计算解决。也许更重要的是，高层机理能够通过朝着合适的最小值推进来与轮廓交互。优化和松弛（Optimization and relaxation）以前被使用在边和线的检测中[3，5，13，24，25]，但并没有使用交互引导。
在大多数图像交互任务中，正确的低层事件的交互处理需要高层知识。如图1，考虑三个深线的感知组织。在我们的线轮廓模型中，三个不同的组织和三个不同的局部最小值对应。值得注意的是,这个线的形状本质上是不同于这三个例子,而不仅仅是因为线分割的不同连接。分割本身被感知组织改变。
图1.左下：原始木头图片。来自Brodatz纹理图像库。其他：活动轮廓模型的三种不同局部最小值。
没有关于在视觉上物体的的详细知识，在三种解释(interpretation)中判断选择是正确的是困难的。知道木头是分层的结构，或者从图中推断出他的分层结构，能够帮助我们排除解释(b)。除了这个，得到正确的解释是很独立的任务。在许多领域中，如分析地震数据，解释(interpretation)的选择可以依靠专家知识。不同的地震的解释(interpretation)能从相同的地震的部分得到相当不同的感知组织，这些相同的地震的部分依靠他们的知识和训练。因为一个正确的解释（interpretation）不能总是被定义。我们建议寻找合适局部最小值的低层机理代替寻找全局最小值。
不像寻找显著轮廓的其他大多数技术，我们的模型是活动的。它总是最小化它的能量函数，也由此建立了动态行为。因为在最小化其能量时轮廓是滑动的，所以我们称为蛇模型。连续到它的最小值时，高层解释（high-level interpretation）上的改变可以在snake上施加力作用。即使缺少这样的力，当被刺激移动时Snakes也会产生滞后现象。
蛇模型没有试着解决找显著轮廓的整个问题。他们依靠其它的机制（mechanisms）去使之位于靠近理想轮廓的地方。然而，甚至在不满足自动开始的机制（mechanisms）时，snakes也可以用在半自动图像交互。如果一个专家使用者，推动snakes靠近预期的轮廓，剩下的就是受能量最小化的牵引。这个最小化提供了一种能量协助，为人们指向轮廓特征。
Snakes是一种具有更综合技术的例子，此技术通过最小化能量使可变模型和图像匹配。在精神和动机上，这个主意使用了widrow[23]的橡胶模板。从任何开始点snake改变自己到附近合适的显著轮廓。通过使用最小能量表面，我们应用相同的基本技术到从轮廓上重建3d物体。我们期待这个普遍的方法将在视觉上的得打广泛的应用。
在第2部分我们使用欧拉方程展现了snakes的基本数学描述。第3部分我们给出了详细的能量项，其能量项使snakes被不同的，重要的，静态的，单目视觉的特征吸引，如线，边，主观轮廓等等。第4部分应用Snakes模型到跟踪，立体匹配。最后，第5部分讨论了我们现在的工作方向和未来的改进。
、、、、、、、、、、、、
2 基本snakes性能
我们的基本snake模型是一条被控制的连续曲线，其曲线受图像力和外部限制力的影响。内部样条(splint)力用来加以分段平滑限制。图像力把snake推向显著图像特征，如线，边，主观轮廓等等。外部限制力负责推动snakes靠近理想的局部最小值。例如这些力，可以来自使用者接口，自动注意机制(automatic attentional mechanisms)，或者高层解释(high-level interpretations)。
参数v(s)=(x(s),y(s))表达snake的位置,我们可以如下写出能量函数：
(1)
由于弯曲， 表示样条的内部力，控制弯曲， 产生图像力， 产生外部限制力。在这部份，我们介绍 ，并且给出 用于交互解释(interactive interpretation)的例子。 在第三部份讨论。
2.1 内部力
内部样条力被写为：
(2)
样条能量由被 控制的第一项和被 控制的第二项组成。第一项是snake行为像羊皮纸(橡皮筋更合适)，第二项像薄金属板。调整这两个权值控制羊皮纸和薄金属板的相对重要性。若在某个点上，为0，允许snake二阶不连续，并且可以形成角。受控制的连续性曲线是Tikhonov的稳定器[19](stabilizer)的一般化，并且能从形式上被看做问题的规范化[14][15]。
最小化过程的细节在附录中给出。这个程序的时间复杂度为O(n)，即使用稀疏矩阵方法进行n次迭代。每一次有效的迭代都用隐式欧拉方程计算内力和显式欧拉方程处理图像和外部限制力能量。数量的考虑是相对重要的。在完整的显式欧拉方程解法中，有O(n)次迭代，在每一次中要花费n2次驱使穿越整个snake。这个结果是松弛的。为了建立坚固的snakes，使用一种更稳定的方法调节大的内力是重要的。我们的半隐式方法允许力穿越整个snake，而仅使用O(n)次迭代。
2.2 蛇穴
对于低层视觉任务，为了实验不同的能量函数，我们在符号Lisp机(LISP machine一种直接以LISP语言的系统函数为机器指令的计算机)上开发了用户接口。这个接口允许用户选择开始点，并当最小化他们的力时交互的在snakes上施加力。除了它的值作为一个研究工具外，对于半自动图像解释(interpretation)这个接口被证明是有用的。为了具体指定特殊的图像特征，用户仅需推动Snake到特征附近即可。一旦足够靠近，能量最小化将完成剩下的推动任务。准确的轮廓特征跟踪能够以这种方式指定，这要比标点法(pointing)多做一些努力。所以说，Snake能量最小化为图像解释(interpretation)提供动力协助。
我们的接口允许用户把弹簧连接到Snake的任何点上，弹簧的一边被固定到一个固定的点，另一点连接到Snake上，或者被鼠标拖动。在ｘ１，ｘ２点创建一个弹簧，加入-k(x1-x2)2到外部限制力 。
除了弹簧，用户接口提供了1/(r2)被鼠标控制的排斥力。1/r能量函数当r=0时被省略以阻止了数量不稳定，因此导致的潜能被一张火山图象描绘。这个火山对于推动snake从一个局部最小值到另一个是非常有用的。
图二显示了蛇穴接口的使用。两个黑线是不同的snakes，用户用两个弹簧(白色标注)连接他们。其他的弹簧连接snake上的点到屏幕的固定点。在右上方，火山正在snake弯曲附近的snake，每一个snake都有一个被用户指定尖角。
图2：蛇穴用户接口。
3 图像力
在初级视觉中，为了让snake更有用，我们需要能量函数吸引他们到图像特征。在此，我们展现了三种不同的能量函数，分别吸引snake到线，边，和终点。完整的能量公式可以表达为三个能量函数的权值组合。
( 3)
通过调整权值，可以形成各种snake行为。
3.1 线函数
最简单有用的图像函数是图像亮度本身。若令：
=I(x,y) ( 4)
依靠 的正负号，snake将被吸引或是暗线，或是亮线。受到其它的限制，snake将试着使自己位于靠近轮廓的最暗或最亮处。如图1，这个能量函数被使用在snakes上。通过用火山推动，使用者可以很快从这些位置中的一个移动snake到另一个。这个很必要的粗糙的控制表明符号注意机对于引导snake蛇有效的。
3.2 边函数
在一个图像上找边也可以用一个简单的函数来做。如果我们设 ，那么snake将被吸引到有大图像梯度的轮廓。使用这个函数的例子请见图3。在左上方，一个使用者在梨和土豆的边缘设置了两条snake。它用一个弹簧拉起梨snake的边缘。下面的图显示了他放手后发生了什么。Snake马上回到了梨的边缘。
图3：在梨和土豆上有两条snakes。左上：使用者使snakes远离梨
的边缘。其它：使用者放手后，snake回到梨的边缘。
3.3 尺度空间
在图3，由于样条能量项，snake在一段相当大的距离也可以回到梨的边缘。这种类型的聚集对于snake来说是相当普遍的。如果snake的一部分找到一个低能量的图像特征，这个样条项将推动snake临近的部分朝着这个特征的可能的延续地方移动。这有效在最优局部最小值放置了一个大的能量。这个相似的结果可以通过空间平滑的线，或边能量函数达到。一种方案是可以允许snake和模糊能量函数平衡，然后在一个然后慢慢降低这种模糊。这种结果通过尺度延续(scale-continuation)最小化[20][21]。
为了显示尺度空间连续性(scale-space continuation)和Marr-Hildreth的边缘检测理论的关系，我们用稍微不同的边函数进行实验。这个边能量函数是：
(5)
是高斯函数， 为其标准方差。此函数的最小值位于 的零交点(zero-crossings)处。加这个能量项到snake中意味着snake被吸引到零交点(zero-crossings)，但仍然受它自己的平滑限制。图4显示了把尺度空间连续性(scale-space continuation)应用到这个能量函数的示例。左上方显示了在粗尺度空间中的sanke平衡。因为边能量函数是模糊的，snake不能很好的局部化边，但是从很远的地方可以被吸引到最小值。慢慢降低模糊如左上角到右下角所示。作为参考，相对于左下所示的snake的能量函数， 的零交点在相同的snake上叠加见右下图。注意snake从一个零交点跳到另一个。在这个尺度，零交点的形状被小尺度纹理决定，而不是区域边界，然而，由于平滑限制，snake仍能使用零交点局部化。
图4.左上：在粗尺度下边snake平衡
右上：在中尺度下边snake平衡
左下：在尺度空间连续性后的snake平衡
左下：零交点覆盖在最后的snake位置
3.4 终点函数
为了找到线分割和点角的终点，我们在稍微平滑过的图像中使用等高线的曲率。令C(x,y)= I(x,y)是图像稍微平滑的版本。令是梯度角和令n=( , )和 =( - ， )，是沿着和垂直梯度方向的单位向量。然后，在C(x,y)中等高轮廓的曲率能被写为
(6)
(7)
(8)
通过组合 和 我们能创建一个被边和终点吸引的snake。图5显示这种snake的一个例子，此例暴露了一种标准主观轮廓错觉[7]。在错觉中，在边和线之间的snake轮廓的形状被通过样条平滑项整体决定。被snake解决的变化问题和被Brady等提出的用于主观轮廓的插值变化公式[2]有密切的联系。Ullman使用分段圆弧的插值法的提议[22]可能也产生一种相似的差值。Snake模型的一个有趣的方面是相同的snake比起找主观轮廓能更效的在自然意象(natural imagery)找到更多传统边缘。而且，可能它提供的为什么有能力看到主观轮廓的见解才是重要的。
图5. 右：标准主观轮廓错觉。左：在主观轮廓上边/终点snake的平衡。
Snake模型的未来不寻常的方面即有关主观轮廓的精神物理学，是滞后的。因为snake不断地最小化其能量，当被显示移动刺激时，他们呈现滞后现象。图6显示了一个移动的主观轮廓的snake跟踪。当水平线右边那段挪开时，snake越来越弯曲直到内部样条力压倒图像力。然后snake从线跌落并恢复到一个更平滑的形状。所得到的分段的线是足够紧密的能使snake重新接上。然而在一幅静止的图片上显示滞后性是困难的，通过在创建移动刺激，在人类视觉中，读者很容易识别与之对应的滞后性。对于纯自底向上过程和全球最优化，此类滞后性不是典型的。
图6 左：动态主观轮廓错觉。顺序为从左到右，从上到下。右：snake被吸
引到边和终点。当移动的水平线滑到右边时，snake弯曲直到它跌落到线上。
得到的线足够紧凑，能使snake重连接。
4 立体和运动
Snakes也能应用到立体匹配问题。在三维中，如果两个轮廓一致，那么不一致沿着轮廓改变的很慢，除非在长度上轮廓很快的减少。在人类立体观测中不一致梯度限制的心理证据[4]表明人类视觉系统至少在一定程度上认为不一致在空间中不能改变太快。在立体snake中，这个限制被表达在一个额外的能量函数。
( 9)
其中 和 是左，右snake轮廓。
因为这种不一致的平滑限制沿着轮廓使用，它和计算光流的Hildreth[8]的平滑限制有很大的相似性。这个限制意味这是在一个眼中的轮廓局部化的过程中，关于一致的轮廓信息在另一只眼中使用。在立体snake中，立体匹配实际上影响以匹配为基础的检测和特征局部化。这有很大不同，例如，从在原始的基础的立体匹配中的Marr-Poggio立体理论[12]，零交点在匹配过程中总是保持不变。
图7显示了一个3维表面重建的例子，其数据来自在一张纸的轮廓沿着单独立体的snakes测量的不一致数据。表面模型重建比起原始方法是从不同的观点进行，它是3维模型，而不是2.5维模型。
图 7：底端：一张弯曲的纸的立体图。下面的：从纸的轮廓表面重建
使用立体snakes进行匹配。表面模型重建比起原始方法是从不同的观点进行，
它是3维模型，而不是2.5维模型。
4.2 运动
一旦snake找到一个显著视觉特征，就锁定它。如果特征开始慢慢的移动，snake将简单的跟踪到相同的局部最小值。运动如果太快会导致snake跳到一个不同的局部最小值。但是对于一般的速度和视频的采样率，snake能处理好运动跟踪。图8显示了八个选中的帧，边吸引snakes在第一帧手动初始化，之后，snakes自动跟踪嘴。
在这个情况里运动跟踪没有任何帧间限制条件。解释这种限制将毫无疑问使跟踪鲁棒。做这个的一种简单的方法是snake聚集（mass）。那么snake以之前的速度为基础也能预测它的下一点位置。
图8.snakes用于运动跟踪。在第一帧初始化了演讲 者的嘴，
然后snakes高精度的自动跟踪。
5总结
Snakes被证明对于图像轮廓的描述是有用的。我们开始使用他们作为与图像交互匹配的3维模型的基础。当我们开发了更好的能量函数是，snakes的“能量协助”越来越有效。尺度空间连续能极大的扩大感兴趣特征周围的捕获区域。
对于在过去不同对待的一些视觉问题，snakes模型提供了同样的解决方法。实质上，边，线，主观轮廓都能用相同的机理找到。立体中，在运动和匹配中跟踪这些特征是很容易的用相同的轮廓处理的。
也许，Snakes，比它的自底向上2.5维简图（sketch）更包含Marr的“最少委托理论”。Snake提供了许多广泛分开的局部最小值，不能撤回的委托用单一的解释代替，snake能基于来自处理的高层的额外的证据改变他们的解释。例如，他们能调整单目边缘基于双目匹配。
我们知道拥有某一种能力是非常重要的，此能力就是拥有影响底层视觉解释的所有视觉处理层次。就像snake局部能量最小系统提供了一个吸引的方法来处理这个。这个能量最小为高层处理留下了一个比较简单的问题。
本文来源：https://www.2haoxitong.net/k/doc/83bf5487e53a580216fcfeac.html
文档为doc格式