图像分析与识别课件5

1、123在对处理后的图像数据进行分析之前，图像分割是最重要的步骤之一。图像分割的主要目标是将图像划分为与其中含有的真实世界的物体或区域有强相关性的组成部分。4我们可以将目标定位于完全分割，其结果是一组唯一对应于输入图像中物体的互不相交的区域。我们也可以将目标定位于部分分割，其中的区域并不直接对应于图像物体。5为了获得完全分割，必须与使用有关问题领域的专门知识相协作。 如果目标是部分分割，则图像被划分为分开的同态的区域。这样部分分割的图像必须经过进一步处理，并借助高层知识找到最终的图像分割。6图像分割方法可以划分为三组：1.基于图像或图像部分的全局知识，这种知识一般由图像直方图来表达；2.基于边缘

2、的分割；3.基于区域的分割。78灰度级阈值化是最简单的分割处理。很多物体或图像区域表征为不变的反射率或其表面光的吸收率，因此可以确定一个亮度常量即阈值来分割物体和背景。阈值化计算代价小、速度快。9图像R的完全分割是区域R1,RS的有限集合：jiRRRRjiSii0110算法：单阈值化单阈值化是输入图像f到输出图像g的如下变换，对于属于物体的像素g(i,j)=0，对于属于背景的像素g(i,j)=255（或反之亦然）。时当时当TjifTjifjig),(0),(255),(11原始图像直方图阈值T=6012算法：带阈值化将图像分割为具有一个集合D内的灰度的区域而其它作为背景（带阈值化）。这种阈值化

3、定义还可以用作边界检测子。 其它时当255),(0),(Djifjig13其它当25511055),(0),(jifjig14算法：半阈值化半阈值化的目的是屏蔽掉图像背景，留下物体部分的灰度信息。 时当时当TjifTjifjifjig),(0),(),(),(15原始图像直方图阈值T=12516多阈值的阈值化，其处理后的结果图像不再是二值的，而是由一个有限的灰度值集合组成的图像。算法：多阈值的阈值化其它时当时当时当时当0),(),(3),(2),(1),(321nDjifnDjifDjifDjifjig17如果物体彼此不接触，且它们的灰度与背景明显地不同，则阈值化就是一个合适的分割方法。选择正

4、确的阈值是阈值分割成功的关键，这种选择可以通过人为交互的方式确定，也可以根据某个阈值检测方法来确定。18全局阈值是根据整幅图像图像确定的。局部阈值是与位置相关的。使用局部阈值（自适应阈值）进行分割可以产生较好的结果。这时的阈值是局部图像特征的函数，在图像范围内是变化的。19a)原始图像b)经全局阈值处理后的结果c)被细分为单个子图的图像d)经自适应处理后得到的结果20如果知道经过分割后的图像的某种性质，就可以简化阈值选择的任务。因为阈值可以按照确保该性质得以满足的条件来选择。21例如，当我们知道文本字符覆盖1p的纸张面积时的印刷文本页。使用这个有关纸张面积与字符面积的比率的先验信息，很容易选择

5、一个阈值T（基于图像的直方图）使得1p的图像面积具有比T小的灰度值，而其余的面积具有比T大的灰度值。 22 如果图像由有别于背景灰度值的具有近似相同灰度的物体所组成，所产生的直方图是二模态的。物体像素构成其中的一个峰，而背景像素构成另一个峰，两个峰之间的灰度数值可能是物体和背景间的边界造成的。 2324二模态阈值检测算法通常首先要寻找最大的局部极大值，然后取它们之间的极小值作为阈值。为了避免检测到属于同一全局极大值的两个局部极大值，通常要求这两个极大值对应的灰度之间的间隔不小于一个最小值。25阈值化是图像分割中非常流行的工具。对于阈值分割来说，一般都具有高处理速度，因此可以容易地实现实时图像阈

6、值化处理。 26将图像的直方图用两个或更多个正态分布的概率密度函数来近似的方法，称之为最优阈值化的方法。阈值取为离对应于两个或更多个正态分布最大值之间的最小概率处最近的灰度值，其结果是具有最小错误的分割（被错误分割的像素数目最小）。27 a)背景和物体的概率分布b)对应的直方图和最优阈值 28这些方法的难点在于估计正态分布参数以及这些分布被当作正态分布所具有的不确定性。如下算法展示了这种方法的基本原理，这种方法假设图像中出现两种主要的灰度区域。29算法：迭代的(最优的)阈值选择 1.假设没有有关物体确切位置的知识，作为第一步近似，考虑图像四角含有背景像素而其它部分含有物体像素。 2.在第t步，

7、分别计算背景和物体的灰度平均值 和 ，其中在第t步将图像分割为背景和物体的阈值是 ,它是在前一步确定的。 tBtOtT303.设 提供了一个更新了的背景与物体的区分。xelsobjects_pi#),(_pixelsbackground#),(objects),(background),(jifjifjijitOtB2)1(tOtBtT)1( tT314.如果 则停止，否则返回第2步。ttTT )1(32(a)3D-weighted MR脑图像的全局直方图(b)拟合的高斯分布(c)对应于白质(WM)，灰质(GM)，脑脊髓流(CSF)的三个分布33(a)原始图像(b)灰质(c)白质(d)脑脊髓流

8、(a) (b) (c) (d) 34许多实际的分割问题需要比单一谱段所含的更多的信息。例如，彩色图像、多光谱遥感图像、气象卫星图像。 一种分割方法是在每个谱段中独立地确定阈值，然后综合形成单一的分割图像。35算法：递归的多光谱阈值化1.将整个图像初始化为单个区域；2.给每个谱段计算一个平滑的直方图。在每个直方图中找到一个最显著的峰，确定两个阈值分别对应于该峰两侧的局部最小值； 363.根据这些阈值将各个谱段的每个区域分割为子区域；4.将各个谱段的每个分割投影到多光谱分割中，见下图。下一步处理的区域是这些在多光谱图像中的区域；375.对于图像的每个区域重复第二步，直至每个区域的直方图只含有一个显

9、著的峰。38 (a) 谱段1阈值化 (b) 谱段2阈值化 (c) 多光谱分割39分层数据结构下的阈值化的目的在于在低分辨率图像中检测区域的出现，在高层直至完全分辨率下给出更精确的区域。 从最低分辨率图像（金字塔的最高层）开始进行分割。为了得到更好的分割精度，离边界近的像素被再次分割为物体或者背景区域。40这种精度增长对于金字塔层重复进行，直至在完全分辨率层得到最终的分割。 这种方法的优点是图像噪声对分割结果的影响明显地小得多。41这是因为在较低分辨率下图像的分割是基于平滑的图像数据，其中噪声被抑制。由平滑数据分割造成的不精确边界，经过在边界附近利用高一层分辨率的数据再次分割而得以矫正。42a)

10、金字塔第n层，分割为物体和背景。b)金字塔第n+1层，为了得到更好的精度必须再次阈值化。4344基于边缘的分割代表了一大类基于图像边缘信息的方法，它是最早的分割方法之一，且现在仍然是非常重要的。 基于边缘的分割依赖于由边缘检测算子找到的图像边缘，这些边缘标示出了图像在灰度、色彩、纹理等方面不连续的位置。 45我们在第四章讲述了各种边缘检测算子，但是由这些边缘检测算子得到的图像结果并不能用作分割结果。必须采用后续的处理将边缘合并为边缘链，使它与图像中的边界对应得更好。或者至少将局部边缘聚合到起来，得到对应于物体部分边界的边缘链。46在分割处理中可获得的先验信息越多，能达到的分割结果就越好。如果能

11、够获得有关期望结果的大量先验信息，边界形状就被详细说明了，分割必须满足所有这些说明。47如果关于边界的先验信息很少，分割方法就必须考虑更多的局部图像信息。如果可获得的先验信息很少，就不能用于评价分割结果的信度，因此就没有反馈矫正分割结果的基础。48基于边缘分割的最常见的问题是在没有边界的地方出现了边缘以及在实际存在边界的地方没有出现边缘，这是由图像噪声或图像中的不当的信息造成的。显然这些情况对分割结果有负面影响。 49在边缘图像中小的边缘值对应于由量化噪声、弱且不规则照明等引起的非显著的灰度变化。可以对边缘图像做简单的阈值化处理排除这些小的数值。这种方法是基于图像的边缘幅度由合适的阈值处理实现

12、，选择合适的全局阈值一般是困难的。50q第四章讲述的简单边缘检测算子的一个问题是使边界变粗。如果边缘带有方向信息，则可以通过施加某种形式的非最大抑制来抑制单个边界邻域内的多个响应，以实现部分矫正。q图像中由噪声产生的边缘可以通过滞后过滤来去除。51算法：有方向的边缘数据的非最大抑制 1.根据8-邻接将边缘方向量化为8个方向；2.对于每个非0幅值的像素，考察由边缘方向指出的两个邻接像素（参见下图）；3.如果两个邻接像素的幅值都超过当前考察像素的幅值，将它们标记出来删除；4.当所有的像素都考察过后，重新扫描图像，以0抹去所有的标记过的像素。52 （由边缘方向确定的） 邻接像素图像中的边界考察像素5

13、3算法：边缘检测算子输出的滞后过滤1.假设超过t1的边缘幅值为边缘，小于t0为噪声；2.将幅值超过t1的所有边缘标注为正确；3.扫描幅值在区间t0, t1内的所有像素；4.如果该像素与已经标注为边界的另一个像素接壤，则将它也标记出来。“接壤”可以定义为4-邻接的或8-邻接的；5.从第2步重复直至稳定。54(a)非最大抑制的边缘图像。 (b)作用于(a)的滞后处理，高阈值是70，低阈值是10。55边缘图像阈值化得到的边界受图像噪声的影响很大，经常会遗漏重要的部分。在它们相互邻域的上下文中考虑边缘的性质能够增加结果图像的品质。 这种评价是基于指定局部邻域内的边缘强度进行的，每个边缘的信度或者被增加

14、或者被减小。56在两个强边缘间的一个弱边缘构成了一个上下文的例子；这个位于其间的弱边缘有很高的可能性属于结果边界的一部分。如果一个边缘置身于没有支持的上下文中，它可能并不是任何边界的一部分。边缘松弛目的在于建立连续的边界。 57中心边缘e在每个端点处有一个顶点，两个顶点处都有三种可能的边界伸展方式。设不计边缘e，以从顶点出发的边缘数来评价每个顶点，称这个数为顶点的类型。这样，边缘e的类型可以用描述每个顶点边缘模式的数对i-j来表示。58环绕中心边缘e的裂缝边缘 59边缘模式及相应的边缘类型60q0-0孤立边缘：对边缘信度产生负面影响。q0-1不确定：弱正面，或对边缘信度无影响。q0-2，0-3

15、死结：对边缘信度产生负面影响。q1-1连续：对边缘信度产生强正面影响。q1-2，l-3连续至边界交叉：对边缘信度产生中等正面影响。q2-2，2-3，3-3边界间架桥：分割中不是必需的，对边缘信度没有影响。61边缘松弛可以根据给定的上下文规则来定义，它可以看作是一个产生式系统。边缘松弛是一个迭代的方法，其中边缘的信度或者收敛到0（边缘终结）或者收敛到1（边缘形成边界）。 62算法：边缘松弛法1.对图像中的所有裂缝边缘计算一个信度c(1)(e)。2.在每个边缘的邻域内，根据边缘信度c(k)(e)确定其边缘类型。3.根据每个边缘的类型和前面的信度c(k)(e)，更新其信度c(k+1)(e)。4.如果

16、所有的边缘信度都收敛到了0或者1，则停止。否则重复步骤2和3。63a)10步迭代后的边界b)细化后边界c)100步迭代后的细化边界d)(c)重叠在原图上64如果区域的边界未知，但区域本身在图像中已经定义了，那么边界可以唯一地被检测出来。首先，我们假设含有区域的图像或者是二值的或者区域已经被标注出来了。65第一个目标是确定区域内边界。正如以前的定义，区域内边界是区域的一个子集。相反地，外边界不是区域的一个子集。 66算法：内边界跟踪1.从左上方开始搜索图像直至找到一个新区域的一个像素，则该像素P0是这个新区域的所有像素中具有最小行数值的最小的列数的像素。像素P0是区域边界的起始像素。定义一个变量

17、dir，存储从前一个边界元素到当前边界元素沿着边界的前一个移动方向。设置： (a) 当按照4-邻接检测边界时 dir=3。 (b) 当按照8-邻接检测边界时 dir=7。672.按照逆时针方向搜索当前像素的33邻域，从以下的方向开始搜索邻域。 (a) 取(dir+3)除以4的余数。 (b) 取(dir+7)除以8的余数，当dir是偶数时； 取(dir+6)除以8的余数，当dir是奇数时。 找到的第一个与当前像素值相同的像素是一个新的边界元素Pn。更新dir的数值。 683.如果当前的边界元素Pn等于第二个边界元素P1，而且前一个边界元素Pn-1等于P0，则停止。否则重复第2步。4.检测到的内边

18、界由像素P0, , Pn-2构成。 69内边界跟踪的例子(a)4-邻接方向符号(b)8-邻接方向符号(c)4-邻接中搜索顺序(d)8-邻接中搜索顺序(e)8-邻接中搜索顺序(f)在8-邻接中的边界跟踪701.根据4-邻接跟踪区域内边界直至完成。2.外边界由所有的在搜索过程中测试过的非区域像素组成，如果某些像素被测试超过一次，它们就被在外边界上列出超过一次。 算法：外边界跟踪71外边界跟踪：注意某些像素被列出几次72内边界总是区域的一部分，而外边界不是。因此，如果两个区域相邻，它们决不会有共同的边界，这在区域描述、区域归并等较高层的处理中会引起困难。扩展边界定义的优点是它定义了相邻区域的单一的共

19、同边界，可以用标准的像素坐标来标识。73 (a) 内边界 (b) 外边界 (c) 扩展边界741.按照标准的方法定义一个扩展边界的起始像素（按照从左到右、从上到下一行一行地搜索图像的方式找到第一个区域像素）。2.从起始像素沿着跟踪边界的第一个移动方向依赖于背景和区域点的局部结构以及通向当前像素的方向。算法：扩展边界跟踪 753.按照下图所示跟踪扩展边界时所有可能出现的12种情况的查找表跟踪扩展边界，直至得到一个封闭的扩展边界。76q当前位置是中心像素。q下一步的移动方向依赖于背景和区域点的局部结构以及通向当前像素的方向77如果要在没有定义区域的灰度图像中跟踪边界的话，就会遇到更为困难的情况。边

20、界跟踪应该从作为边界元素概率高的像素开始，把在最有可能的方向上的下一个元素加入。通常需要计算在可能边界延续像素处的边缘梯度的幅值和方向。78算法：灰度图像中的边界跟踪 1.假设一直到边界元素xi的边界已经确定。2.定义元素xj是在方向(xi)上与xi邻接的像素。如果在xj处的梯度幅值比事先设置的阈值大，则把xj作为一个边界元素；回到第1步。否则继续到第3步。 793.计算像素xj的33邻域的平均灰度值。将结果与某个事先设置的灰度值做比较，确定xj是在区域内还是在区域外。继续到第4步。804.根据第3步的结果确定方向选择中的符号，考察相应方向(xi)/4的xi的邻接像素xk，以便延续边界跟踪。如

21、果找到了边界延续，xk就是一个新的边界元素，返回第1步。如果xk不是一个边界元素，则从另一个有希望的像素开始跟踪边界。81只要有额外的边界检测知识，我们就应该利用。利用先验知识的一个例子是尽管我们不知道确切的边界位置，但是我们知道边界的起点和终点。 82图是由一组节点ni和节点间的弧(ni,nj)构成的一种普通结构。我们考虑有方向的数值加权的弧，这些权称为费用。边界检测过程被转换为在加权图中搜索最优路径的问题，目标是找到连接两个指定节点即起点和终点的最好路径。83假设在边缘图像中，既有边缘幅度s(x)也有边缘方向(x)的信息。每个图像像素对应于一个以值s(x)加权的图节点。如果边缘方向(xi)

22、和(xj)与局部边界方向一致的话，对应于8-邻接像素xi和xj的两个节点ni和nj就用弧连接起来。84我们可以用如下的规则建立图：要连接代表像素xi的节点ni和代表像素xj的节点nj，像素xj必须是xi在方向d(xi)-/4， (xi)+/4内的三个存在的邻接点之一。85进一步，s(xi)和s(xj)必须比阈值T大，其中T是某个事先指定的反映边缘显著性的阈值。另一个常用的要求是只有当边缘方向的差别小于2时才连接两个节点。86 a)超过边缘幅值阈值的像素的边缘方向b)对应的方向图(a)(b)87设xA是开始的边界元素，xB是结束的边界元素。为了在区域边界检测中使用图搜索技术，必须首先定义有向加权

23、图的扩展方法。还必须定义一个费用函数f(xi)作为通过中间节点ni（像素xi）的节点nA和nB（像素xA和xB）间路径的费用估计。88费用函数f(xi)典型地由两部分组成，在开始的边界元素xA和xi之间的最小路径费用的估计g(xi)，以及在xi和结束的边界元素xB之间的最小路径费h(xi)。 从开始节点到节点ni的路径的费用g(xi)一般是路径中弧或节点费用的和。89费用函数相对于路径的长度必须是可分离的和单调的，因此每个弧的局部费用必须是非负的。满足给定条件的的g(xi)一个简单例子是考虑从xA到xi的路径距离。h(xi)的估计可以是从xi到xB的边界的长度。90这有利于优先选择xA和xB间

24、较短的边界作为费用低的路径。如下的图搜索算法（Nilsson的A-算法）可以用于边界检测。91用于边界检测的图搜索算法（Nilsson的A-算法）1.展开起始节点nA，将其所有的后继放入OPEN表中并带有指向起始节点nA的指针。计算每个展开节点的费用函数f。2.如果OPEN表是空的，则失败。确定OPEN表中具有最小费用f(ni)的节点ni，将它从表中除去。如果ni=nB，则通过指针回溯得到最优路径，然后停止。923.如果第2步没有选择停止，展开得到的节点ni，将其后继放入OPEN表中并带有指向ni的指针。计算它们的费用f，返回第2步。 93q当前在OPEN表中的节点加了阴影。q其中最小费用的节

25、点有阴影且轮廓加粗了。q最优路径由回溯定义94如果对于图的建立和搜索没有施加额外的限制，这一过程很容易会造成死循环。为了防止这种行为的发生，将已经访问过的且以前曾被放入OPEN表中的节点不再放入OPEN表中。一种解决死循环问题的简单方法是不允许反向搜索。 95对于图搜索边界检测，一个关键的问题是如何选择评价费用的函数。一个好的费用函数应该具有多数边缘检测问题共有的成分，也要有与具体应用有关的特殊项。 一些通常可用的费用函数有： 961.形成边界的边缘强度：形成边界的边缘强度越强，边界的概率就越高。这一启发式是很自然的，并且几乎总是给出好的结果。注意如果边界由强边缘组成，边界的费用就小。 972

26、.边界曲率：有时要优先选择具有小曲率的边界。如果是这种情况，整个边界的曲率可以用局部曲率增量的单调函数来评价。 983.与一个近似边界位置的接近度：如果知道一个近似边界位置，支持与已知的近似相近的路径是自然的。当一个边界元素包含于边界时，可以用与近似边界的距离来加权边界元素值。994.估计到目标（结束点）的距离：如果边界是相当直的，优先支持与目标节点接近的那些节点的展开是自然的。 100由于边界检测应用的范围相当广泛，所以费用函数需要做些修改使其与特殊的任务相关。设计边界检测费用函数时常需要充分的经验和实验。 101动态规划是基于最优化原理的一种最优化方法。它搜索函数的最优值，该函数的所有变量

27、不是同时内在关联的。考虑如下的简单边界跟踪问题。目标是找到存在于可能的起点A，B，C和可能的终点G，H，I之间的一个最好的路径（最小费用）。102a)边缘图像；b)对应的图，分配了部分弧费用；c)从任何起点到E的可能路径，A-E是最优的；d)到节点D，E，F的最优部分路径；e)到节点G，H，I的最优部分路径；f)从H的回溯定义了最优边界103a)展开图的第一层b)第2步c)第3步，标注出了最后层的最小费用节点d)最优路径由回溯定义104以上例子只有三层，如果图具有更多的层，重复这一过程直至达到一个终点。每次重复由一个优化组成：其中 是分配给节点 的最新费用， 是节点 和 之间的部分路径费用。)

28、,()(min)(1kigxCxCmmiimk)(1mkxC1mkx),( kigmmix1mkx105 对于完全的优化问题，有：其中 是终点节点，M是起始点和终止点间的数目。 表示在第一和最后M图层间路径的费用。)(min),(min, 121MknkMxCxxxCMkx),(21MxxxC106应用动态规划方法必须建立完整的图，这可以按照前面章节中给出的一般规则来建立。目标函是可分离的、单调的（如同在A算法中那样）。前面介绍的评价函数也可能适合于动态规划。107q上：人肺部X射线CT原始代表性的图像。q下：显示成白色的检测出的裂缝108算法：作为动态规划的边界跟踪1.指定第1个图层的所有节

29、点的初始费用 和部分路径费用 。2.对于所有的m=1, , M-1重复第3步。 3.在图层m中，对于所有的k=1, , n重复第4步。 1(),1,iC xin ( , )1,1mgi kmM1094.设 设指针从节点 指回节点 ，其中*指示最优的前驱。5.在最后一层M找到最优节点 。通过从 到 的指针回溯得到最优路径。 ),()(min)(1 , 0, 11kigxCxCmmikimk1mkxmixMkxMkx1ix110对于在图中寻找两个节点的路径而言，启发式搜索可能比动态规划更为有效。而且，基于A-算法的图搜索并不需要明确地定义图。动态规划给出了从多个起点和终点中同时搜索最优路径的一个有

30、效的方法。111在动态规划中，待搜索的图总是在搜索开始之前就完整地建立起来的，因此，交互地设置终点不会调用耗时的图重建的过程，这一点不同于启发搜索的情况。 112因此，在建立了完整的图并分配了节点费用之后，连接固定的起点和交互地改变的终点的最优路径可以实时地确定。 在复杂的区域情况下，完整的区域边界通常是从几段边界建立起来的。在定义了起点之后，操作者交互地引导终点使得计算出的最优边界在视觉上是正确的。 113如果操作者对当前的边界满意，以及如果终点进一步移动会导致边界脱离期望位置的情况下，固定终点并将其作为一个新起点作为下段边界的检测。建立一个新的完整的图，操作者交互地定义下一个终点。 114

31、尽管在响应交互修改的终点时的边界检测是非常快的，但是搜索每段边界所需的初始建立完整图的过程是高计算代价的，这是因为图是整幅图像尺寸的。显然，要获得实时性能需要充分的计算能力。 115如果图像由已知形状和大小的物体组成，分割可以看成是在图像中寻找该物体的问题。 典型的任务是在印刷电路板上定位圆形的衬底，或者是在航拍或卫星数据中寻找特殊形状的物体。 116一种方法是在图像中移动一个合适形状和大小的掩模，寻找图像与掩模间的相关性。由于形状变形、旋转、缩放等原因，该特殊的掩模常常与在待处理的数据中物体的表示相差太大。 117一种非常有效的解决该问题的方法是Hough变换，它甚至可用于重叠的或部分遮挡的

32、物体的分割。118我们来考虑圆形检测的例子。设任务是在均匀亮背景的图像中，检测一个已知半径r的黑圆圈。该方法从搜索一个黑像素开始，一旦找到这样的一个像素，就可以确定一条与其关联的可能圆心点的轨迹。这样的可能圆心点的轨迹构成半径为r的圆。119如果原始图像中的所有黑像素关联的轨迹都被构建出来，就可以确定图像空间中每个像素作为圆心轨迹元素出现的频率。待寻找的真正圆心由具有最高出现频率的像素表示。我们已知圆的半径，这样就完成了图像分割。 120下图直观地证明了Hough变换可以成功地应用于如下的图像中：q含有有关待搜索物体（例子中是圆）不完全信息的图像；q出现额外的结构和噪声的图像；q两种兼有的情况

33、。121 a)亮背景下黑圆圈（已知半径r）的原始图像b)每个黑像素定义了一个以它为中心半径r的可能圆心点的轨迹c)确定图像像素作为圆心轨迹元素出现的频率，具有最高出现频率的像素表示圆心（标记为）d)在不完全的圆信息和有重叠结构出现时，Hough变换正确地检测出了圆（标记为） 122最初的Hough变换是设计用来检测直线和曲线的，起初的方法要求知道物体边界线的解析方程，但不需要有关区域位置的先验知识。这种方法的一个突出优点是分割结果的鲁棒性，即分割对数据的不完全或噪声不是非常敏感。123直线由两点A=(x1,y1)和B=(x2,y2)定义。通过点A的所有直线由y1=kx1+q表示，k和q是某些值

34、。这意味着同一个方程可以解释为参数空间k和q的方程。124因此通过点A的所有直线可以表示为方程q=-x1k+y1。类似地通过点B的直线可以表示为q=-x2k+y2。在参数空间k和q中，两条直线的唯一公共点是在原图像空间中表示连接点A和B的唯一存在的直线。125(a) 图像空间 (b) k和q的参数空间126图像中的每条直线在参数空间k和q中由单独一个点表示，直线的任何一部分都变换为同一个点。直线检测的主要思想是确定图像中所有的直线像素，将通过这些像素的所有直线变换到参数空间的对应点。127在最一般的情况下，我们没有任何有关图像中的直线的信息。只考虑有限数目的直线方向。直线的可能方向定义了参数k

35、和q的一个离散化。参数空间被表示为矩形的单元，被称为累计数组A，它的元素是累计单元A(k,q)。 128对于每个边缘元素，确定其参数k和q，这些参数表示了通过该像素的允许方向的直线。对于每条这样的直线，直线参数k和q的值用来增加累计单元A(k,q)的值。 129显然，如果公式y=ax+b所表示的直线出现在图像中，累计单元A(a,b)的值就会被增加很多次，次数等于直线y=ax+b作为可能通过某个边缘像素的直线被检测到的数目。130对于任意像素P，通过它的直线可能是任何的方向k（取自于允许方向的集合），但是第二个参数q受像素P的图像坐标和方向k所约束。 131因此，存在于图像中的直线会引起图像中适

36、合的累计单元的值变大。而通过边缘像素的其它直线，它们不对应于图像中存在的直线，对于每个边缘像素具有不同的参数k和q，所以对应的累计单元极少被增加。132换句话说，图像中存在的直线可以作为累计数组中的高值累计单元被检测出来，检测到的直线参数由累计数组的坐标给出。结果是，图像中直线的检测被变换为累计空间中的局部极值的检测。133Hough变换的重要性质是，它对图像中直线的残缺部分、噪声以及其它共存的非直线结构不敏感。这是由从图像空间到累计空间的变换的鲁棒性引起的，直线残缺的部分只会造成较低的局部极值。134Hough变换随着曲线参数数目的增加导致累计器数据结构成指数增长，限制了其实际应用，使其只可

37、用在具有少量参数的曲线上。如果使用有关边缘方向的先验信息，就可以显著地降低计算负担，有了边缘方向信息时，只需增大少数的累计单元。 135a)原始图像b)边缘图像（很多边缘并不属于直线）c)参数空间d)检测到的直线136算法：使用Hough变换的曲线检测1.考虑用方程f(x,a)=0表示的任意曲线，其中a是曲线的参数向量。2.在参数a的范围内量化参数空间。参数空间的维数n由向量a的参数数目给出。 3.形成一个n维的累计数组A(a)，其结构与参数空间的量化相匹配，并设置所有的元素为0。1374.在适当地阈值化后的梯度图像中，对每个图像点(x1,x2)，对于所有的在第1步使用范围内的a，增大所有的满

38、足f(x, a)=0的累计单元A(a)：A(a)=A(a)+A5.累计数组A(a)中的局部极大值对应于出现在原始图像中的曲线f(x,a)的实现。 138a)原始图像b)边缘图像（请注意边缘信息远不完美）c)参数空间d)检测到的圆139然而，一般要获得描述边界的解析表达常常是不可能的。期望区域的边界极少能表述为少量参数的边界曲线，在这种情况下，广义Hough变换可以提供解决方案，即使不知道边界的解析表达也可以找到物体。140广义Hough变换根据在学习阶段中检测到的样本情形构建一个参数曲线（区域边界）描述。假设已知期望区域的形状、尺寸和旋转。在样本区域内任取一个位置作为参考点xR，则从该参考点出

39、发可以建立任意一条朝着区域边界的直线（参见下图）。141广义Hough变换原理：创建R-表的几何142边界的方向（边缘方向）在直线与区域边界相交处得到。建立一个参考表（R-表），交点参数作为交点处边界方向的函数来存储。使用从参考点出发的不同直线，从参考点到区域边界的所有距离和交点处的边界方向都可以找到。143产生的表按照交点处的边界方向排序。从上图可以清楚地看到，区域边界的不同 点 x 可 以 具 有 相 同 的 边 界 方 向 ，(x)=(x)。这意味着对于每个有可能存在多于一对的(r,)，这可以用来确定潜在的参考点坐标。144123k),(,),(),(111121211111nnrrr)

40、,(,),(),(222222221212nnrrr),(,),(),(333323231313nnrrr),(,),(),(2211nkknkkkkkkrrr145算法：广义Hough变换1.给期望物体构建R-表描述。2.形成一个表示潜在参考点的数据结构A： A(x1,x2,S,) 令所有的累计单元A(x1,x2,S,)为0。1463.在阈值化后的梯度图像中，对每个像素(x1,x2)，确定其边缘方向(x)，找到所有的潜在参考点xR，对于所有可能的旋转和大小变化： 增大所有的A(xR,S,)：)(sin()()(cos()(2211SrxxSrxxRRASxASxARR),(),(1474.数

41、据结构A中的局部极大值给出了适合区域的位置。148Hough变换最初的设计是用来检测解析定义的形状的，例如一般图像中的直线、圆、椭圆，而广义Hough变换可以用来检测任意的形状。即使是广义Hough变换也需要完全定义目标物体的精确形状，即前提是形状是事先定义的，才能获得精确的分割。149Hough变换有很多期望的性质。它可以识别部分的或少许变形的形状，因此在识别部分遮挡的物体时性能非常好。在图像中出现额外结构（其它直线、曲线或物体）时，Hough变换是非常鲁棒的，同时对图像噪声也不敏感。150如果已知一些有关边界位置或形状的信息，使用它是有利的。例如，信息可以是基于某种高层知识或者是来自于在低

42、分辨率图像上做分割的结果。 151一种可能是将图像中的边界作为接近假设边界的显著边界的位置来确定，其中这些显著边界的边缘方向与假设边界的方向相匹配。新的边界像素在与假设边界方向垂直的方向上搜索。 152有关边界位置的先验信息153另一种可能是基于终点的先验信息，这种方法假设图像噪声低且边界相对比较直。这一过程迭代地将边界划分为部分，在与连接每部分终点的线的垂直方向上搜索最强的边缘。154这些垂直方向位于连接线的中点。在与当前部分的终点连接线接近的垂直方向上最强的边缘被接受为新的边界元素。这一过程迭代地进行。155 分而治之迭代边界检测 数字指明分解的步数的序列 156轮廓检测方法：其中的活动轮

43、廓（active contour）模型蛇(snake)利用用户提供的有关所需轮廓的近似位置和形状的知识，启动轮廓的搜索。一个优化方法改进起始轮廓的估计使其与期望的轮廓相匹配。157迄今考虑的所有方法都集中在边界的检测方面，这些边界部分地或全部地对图像进行了分割处理。如果获得了完全的分割，边界将图像分割为区域。158但是如果仅产生了部分分割，区域并没有唯一的定义，根据边界确定区域的问题是一个非常复杂的任务。但是，存在一些能够从不构成封闭边界的部分边界构建区域的方法。这些方法并不总是能找到可以接受的区域，但是它们在很多实际情况中很有用。159算法：从部分边界形成区域1.对每个边界像素x，在不超出给

44、定的最大值M的距离范围内，搜索一个反向边缘像素。如果没有找到反向边缘像素，处理图像中的下一个边界像素。如果找到了一个反向边缘像素，将连接直线上的每个像素标注为潜在的区域成员。1602.计算图像中每个像素的标注次数（标注次数反映了一个像素出现在反向边缘像素连接线上的频繁程度）。设b(x)为像素x的标注次数。1613.加权的标注次数B(x)根据下式确定： 当b(x)=0, B(x)=0.0 当b(x)=1, B(x)=0.1 当b(x)=2, B(x)=0.2 当b(x)=3, B(x)=0.3 当b(x)=3, B(x)=1.0162一个像素x是一个区域成员的置信度定义为该像素x在其33邻域内的

45、求和式iB(xi)。如果x是区域成员的置信度为1或更大，则将x标注为区域像素，否则标记为背景像素。 163164在前面的章节中介绍的分割方法的目标是找到区域间的边界，以下的方法将直接构造区域。 由基于边缘的方法产生的分割和由区域增长方法得到的分割，通常并不总是相同的。 165区域增长技术在有噪声的图像中一般会更好些，其中的边界非常难以检测。一致性是区域的一个重要性质，在区域增长中用作主要的分割准则。它的基本思想是将图像划分为最大一致性的分区。一致性准则可以是基于灰度、色彩、纹理、形状、模型等的标准。 166选择出来的描述区域的性质，对具体的区域增长分割方法的形式、复杂度、先验信息的数量有影响。

46、 167一致性准则是需要特别关注的，它的选择是影响所提方法的最重要的因素，还可以将特殊的启发式信息结合进该标准之中。最简单一致性准则使用区域的平均灰度、区域的色彩性质、简单的纹理性质或多光谱图像平均灰度值的m维向量。 168最自然的区域增长方法是在原始图像数据上开始增长。最简单的每个像素表示一个区域。169区域必须满足以下条件： 其中S是图像中区域的总数，H(Ri)是评价区域Ri的二值性的一致性度量。)2(, 2 , 1)(SiTRUERHi) 3(,)(jijiRRjiFALSERRH邻接于) 1 (01jiRjRiRRSii170算法：区域归并（大纲）1.定义某种初始化方法将图像分割为满足

47、公式(2)的很多小区域。2.为归并两个邻接区域定义一个标准。1713.将满足归并标准的所有邻接区域归并起来。如果不再有两个区域归并后保持条件(2)，则停止。172该算法表示了区域归并分割的一般方法。特殊的算法区别在于初始分割的定义和归并标准。在随后的描述中，区域是指可以顺序地归并为满足公式(2)和公式(3)的更大区域的图像的那些部分。 173算法：通过边界溶解的区域归并1.定义一个将图像划分为具有不变灰度区域的初始分割。存储裂缝边缘信息。2.从边缘数据结构中，删除所有的弱裂缝边缘。1743.如果满足下式： 则迭代地删除邻接区域Ri和Rj的共同边界，其中W是共同边界上的弱边缘数目， li和lj是

48、区域Ri和Rj的周长，T2是一个预先设定的阈值。2),min(TllWji1754.迭代地删除邻接区域Ri和Rj的共同边界，如果满足下式： 或者，使用一个更弱的标准 其中l是共同边界的长度，T3是阈值。3TlW3TW 176下图给出了区域归并方法的一个比较。图a和图b给出了原始图像和其伪彩色表示（为了看到小的灰度变化）。原始图像不能用阈值化来分割，因为其中的所有区域具有显著的且连续的灰度梯度。177图c给出了使用简单归并准则的迭代区域归并方法的结果。注意产生的长条区域对应于图像灰度的纵向变化。如果使用通过边界溶解的区域归并，分割结果会有显著的改善，参见图d。178a)原始图像b)原始图像的伪彩

49、色表示c)迭代区域归并d)通过边界溶解的区域归并179区域分裂与区域归并相反，从将整个图像表示为单个区域开始，该区域一般不能满足条件(2)。因此存在的图像区域顺序地被分裂开以便满足(1)、(2)和(3)。 180尽管这种方法好像是区域归并的对偶，但即便是使用相同的一致性准则，区域分裂也不会产生与后者相同的分割结果。 然而，区域归并和区域分裂不是对偶的。 181一个例子是精致的黑白棋盘：设以被评估区域的四分象限中的平均灰度变化为基础建立一致性标准，该评估区域在下一个较低金字塔层上。 182如果分割过程是基于区域分裂的，那么图像就不会被分裂为子区域，这是因为它的四个象限与由整个图像构成的开始区域具

50、有相同的度量值。 183而另一方面，区域归并方法开始于将单个像素区域归并为更大的区域，这一过程当区域与棋盘块匹配时就会停止。 这样，如果使用分裂，整个图像将会被作为一个区域；而如果使用归并，棋盘将会被分割为如下图所示的块。 184a)棋盘图像，对应的金字塔；b)区域分裂分割（较高金字塔层是一致的，不可能分裂）；c)区域归并分割 （最低金字塔层由不能归并的区域组成）。 185区域分裂方法一般使用与区域归并方法相似的准则，区别仅在于应用的方向上。 186分裂和归并的结合可以产生兼有两种方法优点的一种新方法。分裂与归并方法在金字塔图像表示上进行，区域是方形的与合适的金字塔层元素对应。 187如果在任

51、一金字塔层中的任意一个区域不是一致的（排除最底层），就将其分裂为4个子区域，它们是下一层的较高分辨率的元素。如果在金字塔的任意一层中有4个区域具有接近相同的一致性度量数值，就将它们归并为金字塔的上一层中的单个区域。188分割过程可以理解为分割四叉树的创建，其中的每个叶子节点代表一个一致区域，即某个金字塔层的元素。分裂与归并对应于分割四叉树的删除或建立部分。在分割过程结束之后，树的叶节点数对应于分割后的区域数。 189在分层数据结构中的分裂与归并 190分割四叉树191起始的图像区域既可以任意选择，也可以根据先验知识来确定。因为分裂和归并的选择都存在，起始分割不必满足(2)和(3)中的任一条件。

52、在分裂与归并算法中，一致性标准起主要作用，正如它在所有其它区域增长方法中一样。 192如果要处理的图像相当简单，分裂与归并方法可以基于局部图像性质。如果图像十分复杂，即使是考虑了语义信息的精心制定的标准也未必可以产生可接受的结果。 193算法：分裂与归并1.定义一个划分为区域的初始分割、一致性准则和一个金字塔数据结构。1942.如果在金字塔数据结构中的任意一个区域不是一致的H(R)=FALSE，就将其分裂为4个子区域；如果具有相同父节点的任意4个区域可以归并为单个一致性区域，则归并它们。如果没有区域可以分裂或归并，则转到第3步。1953.如果任意两个邻接区域Ri和Rj可以归并为一个一致性区域（

53、即使它们在金字塔的不同层或没有相同的父节点），则归并它们。4.如果必须删除小尺寸区域，则将小区域与其最相似的邻接区域归并。196分水岭图像分割算法借助地形学概念进行图像分割，近年来得到广泛应用。该算法的计算过程是串行的，得到的是目标的边界。为讨论分水岭的概念，可借助地形学概念进行。 197把图像看成3D地形的表示，即2D的地基（对应图像空间）加上第三维的高度（对应图像灰度）。图中黄线称为分水线，该分水线将两个重叠圆形目标分开并给出一个最优的结果。198实际中建立不同目标间的分水岭的过程常借助涨水法（水从低上涨）来讨论分水岭的求取技术。利用下图来讨论，为了简便，仅画出各个目标的1D刨面。199假

54、设有水从各谷底涌出并且水位逐渐增高。如果从两个相邻谷底涌出的水的水位高过其间的山峰，这些水就会汇合。如果要阻止这些水汇合，就需在该山峰上修筑水坝，且水坝的高度要随水位的上升而增高。200这个过程随着全部山峰都被水浸没而结束。在这个过程中修筑的各个水坝将整片土地分割成很多区域，这些水坝就构成了这片土地的分水岭。201谷地孔分水岭202a)原始图像b)地形俯视图c)被水淹没的两个不同阶段之一d)被水淹没的两个不同阶段之二203e)进一步淹没的结果f)汇水盆地的水开始聚合（它们之间有一条短水坝）g)长一些的水坝h)最后的分水岭204从上可见，如果能确定出分水岭的位置，就能将图像用一组各自封闭的曲线分

55、割成不同的区域。分水岭图像分割算法就是通过确定分水岭的位置而进行图像分割的。205一般考虑到各区域内部像素的灰度比较接近，而相邻区域像素间的灰度差距比较大。所以可先计算一幅图像的梯度图，再寻找梯度图的分水岭。206在梯度图中，小梯度值像素对应区域的内部，而大梯度值像素对应区域的边界。分水岭算法寻找大梯度值像素的位置，也就是寻找分割边界的位置。207a)原始图像b)取阈值后的结果（相邻沙粒混在一起）c)应用分水岭算法分割的结果d)将图(c)得到的轮廓线叠加到原始图像上的效果(a)(b)(c)(d)208a)原始图像b)梯度图像c)分水线d)叠加于原图像中的分水线209(a)(b)a)电泳现象的图

56、像b)对梯度图像使用分水岭分割算法得到的结果，过度分割现象很明显210直观地说，由于梯度噪声、量化误差及物体内部细密纹理的影响，在平坦区域内部可能会产生许多局部的“谷底”和“山峰”，经分水岭变换后形成小的区域，很容易导致过分割，使希望得到的正确轮廓被大量不相关轮廓所淹没。211a)小气泡图像b)梯度幅值图像c)原始分水岭分割的过分割图像d)平滑梯度图像后的分水岭变换，一些过分割仍然比较明显212为解决上述过分割的问题，一般可在分水岭分割算法之前，对每一个目标区域进行标记。利用标记可将先验知识加进分割过程，从这个角度来说，分水岭算法提供了一个借用先验知识帮助分割的框架。213这些目标区域的标记可

57、以从图像中用特征检测的方法提取出来，必要时也可手工确定标记。对每个目标区域都要确定一个标记，因为标记和最终的分割区域是一对一的。标记的尺寸可大可小（最小一个像素），如果处理噪声大的图像，标记也要较大。214标记控制分水岭图像分割方法的流程框图215a)部分覆盖的两个生物细胞区域b)由区域内距离边界等距离点构成的“等高线”图。因为它的局部极小值和要分开的区域有一对一的关系，所以可以用作标记函数（这里取围绕局部极小值的小区域为标记）c)检测出的分水线可将两个部分覆盖的区域分割开来。216a)显示有内部标记（浅灰色区域）和外部标记（白色线）的图像b)分割的结果(a)(b)217a)原始图像b)梯度图

58、像，33 Sobel边缘检测，直方图均衡化c)原始分水岭分割d)使用区域标记控制减少过分割现象的分水岭分割218219使用区域增长方法分割后的图像，时常是由于参数设置的非最优性所造成，不是含有太多的区域（欠增长）就是含有过少的区域（过增长）。为了改进分割效果，可以在分割后的图像中减少小区域的数目。 220这些小区域根据原来使用的一致性准则是不能与任何邻接的区域归并的。这些小区域在进一步的处理中通常并不重要，可以看作是分割噪声。可以根据如下的算法将它们删除。221算法：小图像区域消解1.搜索最小的图像区域Rmin。2.根据使用的一致性准则，寻找与Rmin最相似的邻接区域R。将R与Rmin归并起来

59、。3.重复步骤1和2，直至所有的比预先选择的尺寸小的区域都被删除为止。 222223匹配是分割的另一种基本方法，可以用于在图像中定位已知的物体，也可以用于搜索特殊的模式等。下图给出了一个期望的模式和其在图像中发现的位置。 224使用匹配的分割，匹配的模式和最佳匹配的位置。 225匹配的用途很广，如果有从不同位置拍摄的不止一幅同一场景的图像，就可以用匹配的方法来确定立体场景的性质。在动态图像（例如，运动的汽车、云彩等）中的匹配是另一个应用领域。 226一般来说，可以用一幅图像抽取出物体或模式，指导在余下的图像中搜索相同的（或相似的）模式。最好的匹配是基于某种最优性准则的，该准则依赖于物体的性质和

60、物体的关系。 227匹配的模式可以非常小，或者也可以表示整个感兴趣的物体。尽管匹配常常建立在图像子区域的灰度性质的直接比较上，但是使用图像导出的特征或高层图像描述来建立匹配也可以同样有效。228在这些情况下，匹配可能变得对图像变换具有不变性。最优性准则可以通过计算从简单的相关性到复杂的图匹配方法来实现。229如果可以期待在待处理的图像中出现的是模式的精确的复制，基于匹配的分割就会非常容易。230然而，在实际的图像中，模式的某部分通常会由于噪声、几何变形、遮挡等因素而损坏。因此，寻找绝对的匹配一般是不可能的，搜索最大匹配的位置更合适。231算法：基于匹配的分割1.对于模式在图像中的每个位置和旋转