分段匹配中的优先顺序划分

摘要

一种用于匹配数字图像的方法，包括：将由像素组成的第一数字图像的图像特征规格化，提供一个由像素组成的第二图像，定义一个有限的候选值集合，其中，一个候选值代表第一图像的图像特性和第二图像的图像特性间一个可能匹配的候选，建立一个匹配罚函数，以估算该候选值，为每个候选值估算匹配罚函数，根据匹配罚函数的估算结果挑选一个候选值，通过对第一图像分段来规格化第一图像，该规格化步骤包括向相应的图段分配至少部分图像像素，为一个图段的至少部分像素确定一个像素重要度参数，该像素重要度参数代表每个像素的相对重要性，并使匹配罚函数部分上由该像素重要度参数确定。

说明书

技术领域

本发明有关一种方法，该方法符合权利要求1中的介绍部分。

技术背景

两个或多个图像的匹配被用于图像处理，其中包含确定连续图像中的匹配部分。在图像处理的若干领域(例如深度再现，图像数据压缩和运动分析)中，图像匹配都是一个基本步骤。

匹配过程包括：确定第一图像的一个第一位置中的图像特征，并确定第二幅图像中这些图像特征的位置。第一和第二图像中图像特征间位置上的差异信息，例如平移或旋转，可被用在以后的处理中。例如，两个连续图像间一个图像特征的平移可被用于获得与该图象特征相关的一个物体的速度量值。

可以利用上下文无关处理来执行图像匹配，在通用图像处理硬件或软件中实现，供MPEG(译)编码和电视扫描速率转换使用。在这些应用中，匹配一个视频流的连续数字图像。这些处理过程中通用的方法如下：

需要匹配的是来自一个视频流的两个连续图像；令这些图像是2维数字图像I₁(x，y)和I₂(x，y)。这两个图像的匹配包括计算一对函数M＝M_x(x，y)和M＝M_y(x，y)，按下面公式理想地将一个图像I₁上的每一个像素映射到图像I₂中的一个像素。

I₁(x，y)＝I₂(x+M_x(x，y)，y+M_y(x，y))

这些函数M包含有关于像素或特征怎样在两个图像之间移动的信息。例如，函数M可被解释为视频流中像素的明显运动，并给出每个像素的一个运动矢量。这一运动矢量可被用在2维图像的深度重现中，电视中扫描频率上调的自然运动中，以及MPEG压缩中(举例来说)。因此，图像匹配包括找出函数M。

将M定义为一个对于所有像素来说都是独立的函数，会使寻找M的提法是不适当的。构造M是非常有问题的，如果可以确定一个函数M，会招致巨大的成本，包括时间上和计算上的花费。为简化寻找M的问题，已提出了函数M的规范化。US 5 072 293中提出一种方法，其中，在图像中的预定决上，函数M被设定为恒定值，它相对于图像帧来说是固定的。这种方案简化了搜索M的问题，并减少了搜索M的费用。这种方法的缺点是，计算仍然费时费钱，而对于某些应用来说，所得到的M的解不够精确。

发明内容

本发明的一个目的是提供一种方法，该方法能够更快更有效地匹配连续图像的部分。

为达到这一目的，在权利要求1的特性部分中定义了上述类型的方法。

按本发明的第一方面，在对第一图像分段之后(其中每个图像的像素都被分配给相应的图段)，为一个图段的至少部分像素确定一个像素重要性参数的值。该像素重要性参数代表每个像素对于匹配目的来说的相对重要性。匹配罚函数是基于该像素重要性参数的，其方法是，在估算罚函数时，为重要的像素分配较大的加权。

在一个实例中，像素重要参数是由一个像素相对于一个图段的硬边界部分的距离和可视度参数确定的。推荐只使用距一个相关边界部分的距离。通过估算一个边界部分对图段所造成的图段深度值，来确定该边界部分的相关性。若该边界部分与深度变化不一致，则很可能该边界部分不体现匹配所需的重要信息。

另外，可见度函数处理的是第一图像中的一个像素在第二图像中是否有一个相对应的像素。该函数合并在罚函数中，将在随后的图像中模糊不清的像素移出处理过程。找出模糊不清的像素的方法是，确定第一和第二图像的图段深度值，根据该深度值确定哪些较高位置的图段模糊了其它较低位置的图段。

通过在匹配过程的罚函数中使用一个像素重要性参数，提高了匹配的精确度，并且减少了所需的计算资源。本发明还有关一个用于匹配数字图像的设备。

在从属权利要求中列出了本发明的有利之处。在以下的描述中，将会清楚本发明的进一步的目的，细节，改进和效果，在以下的描述中参照了以下附图。

附图说明

图1概略描述了一个图段匹配处理的例子，图2概略显示了一个用于匹配数字图像的设备。

具体实施方式

在以下的一个本发明实例中，将解释两个图像的匹配。这些图像可以是来自一个视频流的连续图像，但本发明并不局限于此。这些图像是包含图像像素的数字图像，并被定义为两个2维数字图像I₁(x，y)和I₂(x，y)。其中x，y表明图像中各独立像素的坐标。

这两个图像的匹配包括计算一对函数M＝M_x(x，y)和M＝M_y(x，y)。M的定义和以前一样，即，按下面公式将图像I₁中的每一个像素映射到图像I₂中的一个像素。

I₁(x，y)＝I₂(x+M_x(x，y)，y+M_y(x，y))

按本发明，修改了M的构造方法，使得对于具有相似运动的像素组来说，函数M是恒定的，将M的以前定义修改为：

I₁(x，y)＝I₂(x+M_x(G(x，y))，y+M_y(G(x，y)))

函数G的作用是，使M对于一组具有相似运动的像素来说保持恒定。函数G的引入是对匹配问题的一个规范化，这一修改能明显减少寻找M所需的工作量。

M值恒定的一组像素是由具有类似运动的一些像素组成的。为找出这些像素组，通过分段机制将图像划分为图段。一个图像的分段等同于，为该图像中的每个像素确定一个对有限的图段集合之一的唯一的成员资格，其中的图段是一个相关联的像素组合。一个有利的分段方法是准分段，其中，根据一个像素的图像相关属性(例如颜色，亮度，纹理)确定该像素是否是一个图段的成员，其中图段边界是由一个确定的值标记的。准分段得到的图段不必直接与图像物体对应，不过，某一图段内的像素仍有很大的可能具有类似的运动。在共同未决题为“Segmentation of digital images”的专利申请中，描述了一种准分段方法，其中的内容在此引用以供参考。利用准分段方法，可以快速有效地对图像分段。

利用前面提到的准分段方法，将图像I₁划分为图段，所得到的图段包含以定义各图段的边界为边界的像素。作为准分段的结果，图段是由硬边界部分和软边界部分定义的。硬边界部分由图像分析得出，很有可能是一个相关的图段边界。软边界部分是通过计算距所检测到的硬边界部分的距离确定的，因此，是一个相关的图段边界的可能性较小。一个边界部分与图像内容对应得越好，该边界部分越相关。按本发明，表现形式为图段匹配的图像匹配是按优先次序进行的，即，根据相应图段的期望信息内容，匹配具有较高重要性的像素。

在图1中，显示了图像I₁的一个图段10，该图段是通过准分段确定的，以硬边界部分11(由一个实线表示)和一个软边界部分12(由一个虚线表示)为边界。为确定图像I₁和I₂间图段10的位移函数，需要在图像I₂中找出与图段10匹配的图段10的投影，从而产生位移函数M。首先在图像I₂中挑选一些有可能与图段10匹配的候选图段，为每个候选图段计算一个匹配准则，并挑选一个匹配结果最好的图段。该匹配准则是第一图像的图段与第二图像中的一个投影相匹配的确定性的一个量度。如以前所提到的，图段的硬边界部分与软边界部分相比，有更高的确定性因子。

在图1中，与图段10相匹配的图像I₂的候选图段是图像I₂的投影20，30，40，分别以硬边界21，31，41和软边界22，32，42为边界。每一个投影20，30，40的函数M都由相应的箭头M1，M2和M3表示。因此，M1，M2和M3可被认为是函数M的候选值。为确定哪一个候选投影20，30，40与图段10最匹配，必须为每个投影20，30，40计算一个匹配准则。按照本发明，在估算候选投影和M的候选值时，匹配准则给图段的某些像素更高的加权。对于在定义真实的物体边界时意义重大的像素，分配更大的加权。

该匹配准则被用于数字图像处理中，其实现方式是使一个匹配误差或匹配罚函数最小。这种通过使一个匹配函数最小来进行匹配的函数和方法本身在本技术中是已知的，其例子见于De Haan和Biezen所著文章“Sub-pixel motion estimation with 3-Drecursive searchblock-matching”中，该文章发表于信号处理：图像通信6(1994年)229-239。

具有i个候选M_x和M_y的有限集合定义如下，其中M_x和M_y是x和y坐标上的函数M：

{(M_xj，M_yj)|i＝1，2，3，...}

有限候选集合M_x和M_y的挑选本身在本技术中是已知的，例如，从以上提到的De Haan和Biezen的文章中可以查到。候选集合最好保持很小，以减少估算每个候选所需的计算量。对于每个候选，都有一个候选投影与之相联系。

一个图段中的像素集合被记为Ω。第i个候选的匹配处罚MP_i被定义为：

$>>>MP>i>>=>>\Sigma >>>(>x>,>y>)>>\in >\Omega >\; >|>>I>1>>>(>x>,>y>)>>->>I>2>>>(>x>+>>M>>x>,>i>>>,>y>+>>M>>y>,>i>>>)>>|>->->->>(>1>)>>>s>$

该匹配罚函数给一个图段中的每个像素相等的加权。如以前所提到的，在匹配处理中，一个图段中的像素并非具有相同的意义，有些像素代表实际的物体边界，因此具有较高的重要性，而有些像素只与纹理有关，因此对于匹配来说不是重要的。一个图段中各个像素的重要性可以是不一样的，这是由它们相对于该图段最近边界的位置或距离，纹理和/或特性的数量，噪声引起的。另外，可能出现闭塞，其中，一些图段部分地遮住其它图段，其结果是，一些像素在第一幅图像中是可见的，而在随后的图像中是不可见的，反之亦然。在随后的图像中模糊的像素不应被用于匹配，因为对于这些像素来说，在随后的图像中没有与之相匹配的像素，因此它们是不能匹配的。将无法匹配的像素考虑在内会增加匹配处理的计算量，并会导致不精确的结果。

因此，按本发明，提供了一种匹配处理，其中，考虑像素的重要性，并排除不可见的像素。

利用以上设计的工具，将各个像素的重要性考虑在内，匹配处罚函数被修订为：

$>>>MP>i>>=>>\Sigma >>>(>x>,>y>)>>\in >\Omega >\; >PIM>>(>x>,>y>)>>|>>I>1>>>(>x>,>y>)>>->>I>2>>>(>x>+>>M>>x>,>i>>>,>y>+>>M>>y>,>i>>>)>>|>->->->>(>2>)>>>s>$

加权函数PIM(x，y)是一个像素重要性函数，它为每个像素分配一个因子，该因子代表一个像素相对于所期望信息内容的重要性。在该例中，加权函数PIM(x，y)为：

PIM(x，y)＝w(x，y)v(x，y)                  (3)

其中w(x，y)是一个加权函数，v(x，y)是一个可见度函数。一个像素的重要性由P IM(x，y)函数控制，在该实例中，该函数由可见度映像(即v(x，y))，加权函数和边沿或边界所属关系(即w(x，y))确定。其结果是，不可见像素的重要性为零，并且其它的像素被分配一个重要性参数，该参数是根据该像素与该像素所属边界之间的距离确定的，其唯一的条件是该边界被认为是相关的。

为将以上所描述的由一个图段的深度值所表示的重要性差异考虑在内，加权函数w(x，y)定义为：

w(x，y)＝dist(x，y)own(x，y)

因此，加权函数包含两个因素：函数dist(x，y)和own(x，y)。dist(x，y)对加权函数w(x，y)起作用，并由一个像素与一个边界之间的距离确定，own(x，y)有关该边界的重要性。

根据一个像素到一个边界的距离，函数dist(x，y)为该像素分配一个加权函数，因此，具有高确定性的像素在估算罚函数时起的作用更大。在函数dist(x，y)中，使用了一个像素到该图段的一个硬边界部分的距离d(x，y)，因此，加权函数w(x，y)随着到一个硬边界部分的距离的增大而减小。这代表着这样的假设，即，硬边界段是图像的最确定特性，并且，一个像素距离最近的硬边界越远，其重要性越低。对于dist(x，y)，可以选择任何合适的函数，只要函数值随着距离一个图段边界的距离的增大而减小就行。

以下显示了一些函数，不过，所使用的函数可以不局限于这些函数：

1.dist(x，y)＝l/d(x，y)，

2.dist(x，y)＝l/d(x，y)²

3.dist(x，y)＝1若d(x，y)＜1.5；dist(x，y)＝0若d(x，y)≥1.5；且

4.dist(x，y)＝(5-d(x，y))/4若d(x，y)＜5；dist(x，y)＝0若d(x，y)≥5

应指出，所有这些函数都使dist(x，y)的值随着像素到一个硬边界部分距离的增加而减小。在函数3的情况下，在一个预定距离内，函数值恒定，超过该距离，函数值为零，这也使函数值随距离的增加而减小。函数3和4将计算限制在固定数量的最近像素上；这又进一步减小了所需的计算量。如果图像的分段是利用推荐的准分段方法执行的，则在分段处理过程中，已经知道一个像素距离该像素所属图段的最近硬边界部分的距离，其形式是一个距离阵列。这就显著减小了匹配处理的计算量。

利用这样一个距离参数，能很好地表示一个确定像素的显著性。尽管硬边界分段与一个实际物体边界相关的概率很高，但还希望有其它的选择方式，以获得一个图段内像素显著性的更好的表示。特别的，并非所有的硬边界分段对匹配的目的来说都是同等相关的。为选择最相关的硬边界分段，可以使用由一个硬边界分界的相邻图段的深度值。在确定一个硬边界时，很可能有两种情况：

1.该硬边界对应于一个纹理特性，其特点在于相邻图段具有同样的深度值。这类硬边界是与实际物体边界相对应的边界的可能性很小，对于匹配目的来说，不是非常相关的。因此，不应根据距离函数增加这些硬边界部分的值。

2.该硬边界与深度上的不连续相对应，其表现是，该硬边界的两边深度值不等。这种硬边界很有可能是与一个实际物体边界相关的边界，因此，对匹配来说是非常相关的。对于这些边界来说，应保持以前所定义的距离函数。为此，所有权函数own(x，y)定义如下：

own(x，y)＝1，若像素(x，y)与类型2的边界相关，

own(x，y)＝0，若像素(x，y)与类型1的边界相关。

对于以上所提到的估算来说，需要估算一个图段的深度值。确定一个图像中图段深度值的方法本身在本技术中是已知的。在使用本发明时，可以使用任何合适的方法，以确定图段的深度值。一般，这种方法比较连续的图像并得出一个图像的每个图段的深度值。

这一加权函数w(x，y)只考虑与第二组硬边界相对应的硬边界部分的种子点，该第二组硬边界表示深度的不连续性。在估算该函数时，对于每一个硬边界，都要确定它是否属于以上提到的类型1或2。类型1的边界部分，即，不相关的纹理边界，被分配一个低的或零距离值。类型2的边界部分，即相关的物体边界部分，被分配一个高的或最大的距离值。利用该加权函数w(x，y)，可以做到在匹配期间只考虑与一个相关硬边界图段相关的像素。

另外，如以前所述，在匹配估算时，必须将不可见的像素排除在外。为此，引入了一个可见度函数v(x，y)。若一个像素在下一图像中是不可见的，则该可见度函数的值为零，若一个像素在下一图像中是可见的，则该可见度函数的值为1。为确定可见度函数，必须考虑连续的图像。可以用任何合适的方法实现该可见度函数。一般，确定可见度函数需要为连续图像的图段确定深度值，并根据该深度值确定哪些更高位置的图段使其它较低位置的图段模糊不清。由于图段的深度值还用于确定上述的加权函数w(x，y)，因此在确定w(x，y)和v(x，y)的处理过程中可以共享所需的计算资源。因此，可以选出不可见像素，以使得在匹配计算中不使用这些像素。

如以上所描述的，不能在一个单独的图像的基础上计算可见函数v(x，y)，因此，为了启动本发明所介绍的估算过程，最好进行以下的进程。在第一次匹配迭代期间，为v(x，y)计算第一组深度值。这些计算出的深度值使得能够按从最近到最远的顺序排列图段。如以上所描述的，可以使用任何确定深度值的方法。

在使用过程中，本发明方法在第一迭代步骤中要求一个深度值的估算量，以使用公式3。为启动该过程，必须估算初始深度值，可以使用任意合适的值。在估算初始深度值之后，在随后的迭代中，可以使用以前计算出的深度值。依照本发明的方法是，按照公式(3)，在像素的基础上计算加权函数PIM(x，y)，并随后确定公式(2)所定义的罚函数。

在实例中可见，PIM(x，y)函数与一个像素到一个硬边界部分的距离和可视度函数相关。不过，本发明并不局限于该实例；也可以使用其它为每个像素分配重要值的方法。在这种情况下，必须用每个像素的加权因子来填写一个确定度阵列(x，y)，该阵列与前面提到的距离阵列相对应，该确定度阵列与相应的像素所属的图段相关。特别地，本发明可以只使用加权函数w(x，y)，不考虑可视度函数。尽管损失了一些效率，但减少了所需的计算量。

本发明还可被用于匹配一个单幅图像中的图像部分，例如用于模式或图像识别。

本发明还有关一个计算机程序产品，当在计算机上运行时，该产品的计算机程序代码部分执行本发明方法的步骤。本发明的计算机程序产品可被存储在一个合适的信息载体上，例如一个硬盘、软盘或CD-ROM上，或存储在一个计算机的存储部分中。

本发明还有关一个图2中所显示的设备100，该设备用于匹配数字图像。设备100配有一个处理单元110，用于按上述方法匹配数字图像。处理单元110可被设计为至少部分上可编程的设备，或被设计为用硬件来实现上述一个或多个算法。处理单元10与一个输入部分120相连，通过输入部分120来接收数字图像并送入单元110。单元110还与一个输出部分130相连，通过它可以输出图像间所找到的匹配。

设备100可被插入一个显示设备中，例如一个电视中，特别是一个用于显示3-D图像或视频的三维(3-D)电视中。设备100还可被包含在一个译码装置的运动估算器中。另一个有利的应用是3-D浏览器。

应指出，上面提到的实例只起举例说明的作用，并不限定本发明，本技术专业人员可以不脱离附加权利要求范围，设计出许多不同的实例。在权利要求中，括号内的任何参考符号并不限制本发明。“包含”一词并不排除出现权利要求所列出的元件或步骤之外的元件或步骤。本发明可通过包含若干分立元件的硬件实现，并可通过一个适当编程的计算机实现。在一个列举了若干元件的设备声明中，这些元件中的若干个可由同一个硬件实现。有些方法是在互相不同的非独立权利要求中声明的，这并不意味着不能使用这些方法的组合。