一种检索相似性形状的方法

摘要

本发明公开了一种相似性形状检索方法，步骤为：①提取输入查询图像和数据库中待检索图像的形状轮廓；②用内距离形状上下文描述子对所有形状（包括输入查询形状和数据库中的待检索形状）进行表示。③用动态规划方法对所有形状（包括输入查询形状和数据库中的待检索形状）进行两两之间的匹配。④用内容敏感的相似性度量方法计算获得新的相似度度量排序。⑤获得形状检索的结果。本发明不再使用两两形状之间的不相似性（距离）作为形状检索的直接依据，而是通过对形状的内在差异进行整合，利用形状相似性空间中的结构信息对原始两两形状之间的不相似度（距离）进行改进，从而有效的提升了形状检索的准确率。

说明书

技术领域

本发明涉及对形状进行检索，具体涉及一种检索相似性形状的方法。

背景技术

形状匹配/检索是计算机视觉中的一个非常重要的问题。现有许多种不同的形状匹配方法，并且在提高匹配精度上取得了一定的进展。然而，几乎所有这些方法都重点专注于两两形状之间的相似性度量，试图通过提出更合理的形状描述子和匹配算法，从而更好的度量两个形状之间的相似性或距离。这些方法都基于一个典型的观点，两个形状越相似，它们之间的差异就越小，这个差异通常由距离函数来度量。然而，这一观点忽视了一个事实：对于形状而言，有些同类形状之间的差异可能很大，而有些不同类形状之间的差异可能反而相对较小。这种现象由形状的复杂性引起，由于同类形状间的遮挡、扭曲或非刚性的形变等，同类的形状可能有很大的区别。换言之，对于区别很大的同类形状而言，无论如何改进形状描述子或匹配算法，都不可能对本来差异就很大的两个形状进行很好的度量和比较，使得它们很相似。虽然这种差异可能不是形状之间的本质区别，但却难以消除。要解决这个问题，需要对目前单纯从两个形状本身的特性出发进行相似性度量的思路进行改进。

“内距离形状上下文”是近年来提出的一种很有效的形状描述子。它对于同类形状的非刚性变化具有较强的稳定性。在本发明的系统中，形状描述子使用内距离形状上下文。内距离形状上下文的具体内容，在HaibinLing和David W.Jacobs所著、2007年发表在期刊“IEEE Transactions onPattern Analysis and Machine Intelligence”第26卷第11期上的文章“ShapeClassification Using the Inner-Distance”中有详细介绍。

动态规划方法是运筹学的一个分支，是解决多阶段决策过程的一种数学方法。近年来，动态规划方法在形状匹配、形状检索中取得了广泛的应用。在本发明中，对形状进行匹配使用动态规划方法。关于动态规划方法在形状匹配中应用的内容，在Evangelos Milios和Euripides G.M.Petrakis所著、2000年发表在期刊“IEEE Transactions on Image Processing”第9卷第1期上的文章“Shape Retrieval Based on Dynamic Programming”中有详细的介绍。

发明内容

本发明的目的在于提供一种检索相似性形状的方法，该方法可以提高形状检索的准确率。

本发明提供的一种检索相似性形状的方法，包括下述步骤：

(1)提取输入查询图像和数据库中待检索图像的形状轮廓，查询图像称之为查询形状，待检索图像称之为待检索形状；

(2)在步骤(1)所提取的查询形状和待检索形状的基础上，计算每个形状轮廓的特征，也就是描述子；

(3)在步骤(2)计算得到的形状特征的基础上，对于输入的查询形状和数据库中的待检索形状所组成的形状集合，对集合中的任意两个形状之间进行匹配，求出其两两之间的不相似性度量值，根据这些不相似性度量值组成一个不相似性度量矩阵；

(4)根据步骤(3)求得的不相似性度量矩阵，计算查询形状跟数据库中任意一个待检索形状之间的相似度；

(5)基于步骤(4)中求得的输入查询形状跟数据库中所有待检索形状之间的相似度，确定检索输出结果。

本发明具备如下性质：(1)取代了以前只计算每一对形状的相似度的方式，更多地利用了由已知所有形状组成的流形；(2)没有显性地学习流形或测地线，因为这一计算耗费比较大。一个更好的相似度通过查询形状向数据库中待检索的形状传递相似度来得到。在具体实施方式部分将对本发明的效果作进一步的说明。

附图说明

图1是本发明输入的测试图像示例；

图2是形状轮廓抽样点及内距离示意图，(A)轮廓采样点示意图，(B)形状的内距离示意图，(C)局部形状的内距离示意图；

图3是内角度示意图；

图4是带角度划分的同心圆及其在轮廓表示上的应用示意图；

图5是带角度划分的同心圆及内距离示意图；

图6是计算统计直方图示意图；

图7是轮廓采样点及其统计直方图示意图；

图8是实施本发明方法的系统流程图；

图9是在MPEG-7数据库上检索率的比较；

图10是在MPEG-7数据库上检索的结果的比较；

图11是带局部丢失的形状检索的结果比较。

具体实施方式

本发明涉及到一种相似形状的检索方法和系统。系统中有一个形状数据库，该数据库中包含若干个形状，这些形状是等待被检索输出的形状(以下简称为“待检索形状”)。另外，作为系统的输入，有一个查询形状，数据库中的待检索形状会分别与该输入查询形状进行相似性比较，从而确定哪些待检索形状与输入查询形状足够相似并作为检索结果输出。

检索工作从系统接收输入查询形状开始，以系统返回通过检索得出的若干结果形状结束。

给定一个形状数据库、一个查询形状和一个形状距离函数，它不必是一个度量，本发明学习一个距离函数，这个距离函数通过查询形状和数据库中的待检索形状两两之间的相似度形成的流形上的最短路径来得到。本发明不需要显性地学习这个流形。实验证明，新学习的距离函数能够整合内在形状差异的知识。这个学习过程是非监督的。

在本发明提出的方法中，在根据已有形状描述子和形状匹配算法计算获得的形状相似度基础上，进一步计算得到新的相似度。直观的说，对于一个给定的形状S₁，即使形状S₃与形状S₁不相似，但若与形状S₃相似的形状S₂相似于S₁，那么形状S₁和形状S₃的相似度也会很高。然而，即使形状S₁和形状S₃很相似，但如果与形状S₃相似的形状S₂跟形状S₁并不相似，那么形状S₁和形状S₃的相似度将会很低。因此，得到的新相似度是对内容敏感的，这里给定形状的内容就是与其相似的形状。

即使形状S₁和形状S₃的差异较大，但有一个形状S₂与它们的差异都很小，仍然认为形状S₁和形状S₃相似。这种情况对于多数形状距离是可能的，因为它们不满足三角形不等式的关系，即d(S₁，S₃)≤d(S₁，S₂)+d(S₂，S₃)并不是一直成立。若对某些形状S₁，S₂，S₃，，满足d(S₁，S₃)＞d(S₁，S₂)+d(S₂，S₃)这一情况，那么本章提出的方法能够学到一个新距离d′(S₁，S₃)满足d′(S₁，S₃)≤d(S₁，S₂)+d(S₂，S₃)。同样，若在距离空间中存在一条路径使得d(S₁，S₃)＞d(S₁，S_2，1)+...+d(S_2，u，S₃)，其中u是该路径上形状的数量，那么本方法得到一个新的距离d′(S₁，S₃)≤d(S₁，S_2，1)+...+d(S₂，u，S₃)。由于这条路径表示一个从形状S₁到形状S₃的一个最小扭曲变形的过程，能够忽视不是很关键的形状差异，并且集中在较关键的形状差异上，这样就得到了一个新的距离d′。本发明通过这个新的距离度量提升了形状检索的正确率。

下面结合附图和实例对本发明方法作进一步详细的说明。

如图8所示，本发明方法包括下述步骤：

(1)提取输入查询图像和数据库中待检索图像的轮廓。输入的查询图像和数据库中的待检索图像，都是二值图像。如果输入的查询图像不是二值图像，先将其转换成二值图像。转换的方法包括人工手工标注或图像分割方法(例如，图归一化切分等算法)等。如图1所示，图中所示的形状是本发明的输入图像。从输入的查询图像和数据库的待检索图像中，通过轮廓提取算法得到形状轮廓。

从输入的查询图像所提取的形状轮廓称为查询形状，从数据库中的待检索图像所提取的形状轮廓称为待检索形状。由于形状轮廓包含了二值图像的关键信息，同时轮廓提取非常容易实现，所以输入的查询图像也可称为输入查询形状，二值图像数据库也可称为形状数据库，数据库中的待检索图像也可称为待检索形状。文中后面分别采用“查询形状”、“形状数据库”和“待检索形状”的说法。

对于数据库中的待检索图像，从二值图像得到相应的形状轮廓的处理工作，不用在检索阶段进行，可以事先完成。对于输入的查询图像，其提取形状轮廓的工作只能在检索阶段完成。

(2)在步骤(1)所提取的查询形状和待检索形状的基础上，计算每个形状轮廓的特征，也就是描述子。本发明使用内距离形状上下文作为形状的描述子。具体做法如下：

(2.1)对每个形状轮廓进行均匀采样。每个轮廓上采样N个点，N的取值在不同的应用环境中根据需要设定，如N＝100。见图2(A)所示，在该图中剪刀的外轮廓上的圆形实心点即为轮廓上的采样点。

(2.2)对于每个形状轮廓上的每个采样点p_i，i表示采样点的序号，i＝1，...，N，使用内距离形状上下文描述子进行描述。对于某个形状来说，其形状轮廓上的所有N个采样点的内距离形状描述子，共同组成了这个形状的特征。

计算每个采样点的内距离形状上下文描述子，具体做法如下：

(2.2.1)计算内距离。定义采样点之间的内距离为在形状内部连接两个采样点的最短路径的长度。使用最短路径算法计算某个采样点p_i到形状边界上其它采样点之间的内距离，计算方法如下：①首先构造一个图结构，在该图结构中，每个采样点p_i作为图的顶点，设其中任意两个采样点为p₁和p₂，判断连接这两个顶点的边是否落在形状的内部，如果落在形状的内部，那么就在这两个顶点之间保留一条边的连接，边权重等于它们之间的欧式距离||p₁-p₂||。如果该边没有完全落在形状的内部，则这两个顶点之间没有一条边直接相连。②在整个权重图上使用最短路径算法(如迪科斯彻(Dijkstra)算法)，获得任意两个点之间的最短连接，该最短距离即为内距离。在图2(C)中是形状局部细节上的最短路径线段。

(2.2.2)计算内角度。定义一个采样点p₁相对于另一个采样点p₂的内角度为轮廓采样点p₁的切线方向和从点p₁出发的p₁、p₂之间的最短路径方向之间的夹角。如图3中，p₁和p₂是轮廓上的两个采样点，图中所示的角度θ即为p₁和p₂之间的内角度。

(2.2.3)计算内距离形状上下文描述子。本发明中使用带方向划分的同心圆作为计算描述子的工具，所谓带方向划分是指以采样点p_i的切线方向为零度角方向，将360度空间均匀划分成G个区间，如图4所示，同心圆的圆心处于某个轮廓采样点p_i，同心圆每个圆的半径以及同心圆的方向角度划分根据应用的具体场合而定，假设零角度方向为采样点p_i的切线方向，假设角度划分为G个区间，本例中使用的是将360度划分为G＝12个区间，每个区域为30度。又假设有R个同心圆，本例中R＝5，则R个同心圆和G个角度区间结合起来构成了(R+1)×G个区间。然后结合(2.2.1)和(2.2.2)获得的内距离和内角度，确定轮廓上其他的点在以点p_i为圆心的带方向距离划分同心圆的(R+1)×G个区间中的分布，获得一个统计直方图，该直方图见图7右侧所示。该统计直方图即为内距离形状上下文描述子。其数学定义为：

h_i(k)＝#{p_j：1≤j≤N，j≠i，p_j-p_i∈bin(k)}

在上式中，h_i表示轮廓上第i个采样点的内距离形状上下文统计直方图，h_i(k)表示落在该统计直方图的第k个区间里点的个数，k的取值范围是从1到(R+1)×G的整数。p_i表示第i个采样点，也就是该统计直方图描述的对象，p_j则表示形状轮廓上的N个采样点中，除了p_i以外其他N-1个点中的任意一个。p_i是上述同心圆的圆心，p_j-p_i表示一个向量，该向量指向p_j。bin表示上述的用带方向距离划分的同心圆获得的区间划分，bin(k)表示第k个区间。表达式的含义是如果向量p_j-p_i落在区间bin(k)中，则认为点p_j落在统计直方图的区间k中，把相应的统计直方图的区间k中的点的数量h_i(k)加1。符号#表示累加的含义。

结合图4、图5进一步解释，在图4中，设圆心所在的位置为p_i，箭头指向的位置为p_j，经过一个中间点p_w，图5中从圆心出发的折线段的长度即为内距离，在计算内距离形状上下文描述子时，首先将图5中的折线段做部分旋转得到图6中所示的直线段，然后看该直线段末端端点落在哪个距离区间中，判断该直线段与点p_i的切线方向的夹角(即图6中接近圆心位置所标示的角度θ)的度数落在哪个角度区间中，结合上述两部分信息，最终确定点p_j落在哪个区间中，然后将该区间的累加值在之前的基础上加1。

最终获得的统计直方图如图7所示，颜色越深的地方表示点数越少，颜色越浅的地方表示点数越多。

在图7的统计直方图中，横轴方向表示角度区间划分，纵轴方向表示距离区间划分。

(2.3)计算每个形状轮廓的特征

重复(2.2)的过程，计算获得某个形状轮廓上每一个采样点的内距离形状上下文描述子，从而获得对该形状的描述。这种对整个形状的描述，是通过一组如(2.2.3)描述的统计直方图所组成，每个统计直方图都是该形状轮廓上某一个点的描述。这样一组描述子，就是前面所述的形状特征。

重复这个过程，计算获得输入查询形状和数据库中所有待检索形状的特征。

对于数据库中的待检索形状，其形状轮廓特征的计算不用在检索阶段进行，可以事先完成。对于输入的查询形状，其形状轮廓特征的计算只能在检索阶段完成。

(3)形状匹配

在步骤(2)计算得到的形状特征的基础上，对于输入的查询形状和数据库中的待检索形状所组成的形状集合，对集合中的任意两个形状之间进行匹配，求出其两两之间的不相似性度量值(距离)。

(3.1)两个形状之间的匹配

本发明使用动态规划方法，求解任意两个形状轮廓上采样点的最佳对应关系和这两个形状之间的不相似性度量值(距离)，完成形状匹配。具体做法如下：

假设待匹配的其中一个形状为A，另外一个形状为B，由A和B的轮廓采样点组成两个序列集合，分别记为{p_i，i＝1，...，N}，{q_j，j＝1，...，N}。

(3.1.1)分别计算序列{p_i，i＝1，...，N}中的任意一个点p_i与序列{q_j，j＝1，...，N}中的任意一个点q_j之间的特征距离c(i，j)，该距离定义为由(2.2)计算得到的点p_i的统计直方图与点q_j的统计直方图之间的距离，其数学定义如下：

$c(i,j)=\frac{1}{2}\underset{k=1}{\overset{(R+1)\times G}{\Sigma }}\frac{{[h_{A,i}\left(k\right)-h_{B,j}\left(k\right)]}^2}{h_{A,i}\left(k\right)+h_{B,j}\left(k\right)}$

其中h_A，i，h_B，j为(2.2.3)中定义的统计直方图，下标A和B表示h_A，i(k)、h_B，j(k)分别是形状A和形状B的统计直方图，c(i，j)表示点p_i和点q_i的特征距离。

通过计算形状A上所有点与形状B上所有点的特征距离，获得N×N的特征距离矩阵{c(i，j)，i＝1，...，N，j＝1，...，N}：

$C=\left(\begin{array}{ccccc}c\left(\mathrm{1,1}\right)& c\left(\mathrm{1,2}\right)& ...& c(1,N-1)& c(1,N)\\ c\left(\mathrm{2,1}\right)& c\left(\mathrm{2,2}\right)& ...& c(2,N-1)& c(2,N)\\ ...& ...& ...& ...& ...\\ c(N-\mathrm{1,1})& c(N-\mathrm{1,2})& ...& c(N-1,N-1)& c(N-1,N)\\ c(N,1)& c(N,2)& ...& c(N,N-1)& c(N,N)\end{array}\right)$

(3.1.2)假设两个序列{p_i，i＝1，...，N}和{q_j，j＝1，...，N}在点p₁和q₁处对齐。运用动态规划方法，求得两个序列的不相似度(距离)D1，其求解过程如下：

①生成一个N×N的空矩阵M，称为动态规划矩阵。

②初始化边际条件：

M(0，0)＝0；

M(i，0)＝γ×i，i＝1，...，N；

M(0，j)＝γ×j，j＝1，...，N；

这些数值不包含在动态规划矩阵M中，因为M中的元素的行索引和列索引的范围均为从1到N的整数。γ为设定的一个标量惩罚因子。

③按照从左到右、从上到下的顺序，依次计算动态规划矩阵M中每个元素的值S(i，j)，i＝1，...，N，j＝1，...，N。计算公式如下：

$M(i,j)=\min \begin{array}{}\end{array}\left(\begin{array}{c}M(i-1,j-1)+c(i,j)\\ M(i-1,j)+\gamma \\ M(i,j-1)+\gamma \end{array}\right)$

其中c(i，j)为点p_i与点q_j之间的特征距离。

④当动态规划矩阵中每个元素的值均计算完毕，则动态规划方法结束。两个序列的不相似度D₁＝M(N，N)。

(3.1.4)重复(3.1.3)的过程，分别假设两个序列{p_i}和{q_i}在p₂与q₁处对齐，p₃与q₁处对齐，......，p_N与q₁处对齐，分别运用动态规划算法求得不相似度(距离)D₂，D₃，...，D_N。

(3.1.5)选取步骤(3.1.3)到(3.1.4)中求得的N个距离中最小的那个，作为形状A，B之间的不相似性度量值(距离)：

D(A，B)＝min(D_i)，i＝1，...，N

(3.2)形状集合中两两形状之间的匹配

对于由输入的查询形状和数据库中的待检索形状所组成的形状集合，利用步骤(3.1)所描述的方法，对集合中的任意两个形状，利用动态规划算法进行匹配，求出其不相似性度量值(距离)。

假设数据库中含有n个待检索形状，n为正整数，输入的查询形状与数据库中的n个形状一起，一共组成了n+1个形状{x_i，i＝1，...，n+1}。根据步骤(3.1)，可以分别求出这n+1个形状两两之间的不相似性度量值(距离)，组成一个不相似性度量矩阵(距离矩阵){D_i，j，i，j＝1，...，n，n+1}：

其中，D_i，j表示第i个形状与第j个形状之间的不相似性度量值(距离)。另外，将输入的查询形状放在这n+1个形状中的第一个，即x₁。

对于数据库中的n个待检索形状，其两两之间的匹配和不相似性度量计算，不用在检索阶段进行，可以事先完成。但如果被匹配的两个形状中包含输入的查询形状，则其匹配和不相似性度量工作，只能在检索阶段完成。也就是说，对于矩阵D，其第一行和第一列的元素值必须在检索阶段计算，其他元素值均可事先计算求得。

(4)根据步骤(3)求得的不相似性度量(距离)矩阵，计算查询形状跟数据库中任意一个待检索形状之间的相似度。

本步骤也就是通过使用内容敏感的形状相似度度量方法获得检索结果，其具体做法如下：

(4.1)定义关系矩阵w_i，j，其计算公式如下：

$w_{i,j}=\exp (-\frac{D_{i,j}^2}{{\lambda }_{i,j}^2})$

其中，D_i，j是步骤(3.2)中获得的不相似度量矩阵(距离矩阵)，λ_i，j为归一化参数，该归一化参数的计算方法如下：

λ_i，j＝α·mean({knnd(x_i)，knnd(x_j)})

在上式中，mean({knnd(x_i)，knnd(x_j)})表示形状x_i，x_j的前b个最近邻距离的平均距离。所谓最近邻距离，是指与该形状的不相似性度量值(距离)中最小的b个距离。参数b和α在实际应用环境中根据经验决定，在本例中b＝10，α＝0.27。

(4.2)定义概率转移矩阵P，该概率转移矩阵通过对w_i，j沿行方向归一化得到，计算公式如下：

$P_{i,j}=\frac{w_{i,j}}{\underset{h=1}{\overset{n+1}{\Sigma }}{w}_{i,h}}$

其中w_i，j为上述的关系矩阵。

(4.3)定义关键函数f，并通过下列递归的过程来求解关键函数：

$f_{t+1}\left(x_i\right)=\underset{j=1}{\overset{n+1}{\Sigma }}{P}_{i,j}{f}_t\left(x_j\right),$i＝2，...，(n+1)

且有

f_t+1(x₁)＝1

其中P_i，j为上述的概率转移矩阵；该递归过程需要经过T次迭代，参数T在实际应用环境中预先决定，本例中T＝5000。

(4.4)使用步骤(4.3)的递归迭代过程得到的关键函数f，结果记作f_T(x_i)，i＝1，...，n，n+1，求解结果是一个n+1行1列的矩阵。去掉f_T(x₁)，所剩余的n行1列的矩阵中，第i行的值表示数据库中的第i个形状与输入查询形状的相似度。

(5)基于(4)中求得的输入查询形状跟数据库中n个待检索形状之间的相似度f_T(x_i)，i＝2，...，n，n+1，确定检索输出结果。

对f_T(x_i)，i＝2，...，n+1中的n行值从大到小进行排序，根据排序以后的顺序，确定数据库中待检索形状的检索输出顺序。例如，第i个值最大，则输出的检索结果，第i-1个形状排在检索结果的第一位，以此类推得到第二位检索结果、第三位检索结果，等等。

检索输出的不是形状轮廓，而是数据库中的原始二值图像。如图10、图11所示。

设定一个参数l，表示检索返回的图像结果的数量。也就是说，检索返回的是数据库中与输入查询图像相似度最大的前l个图像。参数l的值由用户根据实际应用的需求灵活设定，本例中l＝40。

实验结果证明本发明能够提高已有形状匹配方法的检索性能。

表1中给出了在MPEG-7CE-Shape-1数据库上本发明与近10年来发表在国际重要期刊和会议上的主要方法的比较，本发明取得了91.61％的检索精度，是目前在该数据库上取得的结果中最高的。

表2中给出了在Kimia99数据集上本发明与近年来的重要方法的结果并进行了比较，结果显示，本发明的方法在各个阶上的结果均高于其他方法。

在具体实施方式(4.1)中，存在着两个参数b和α，表3给出了在不同的参数下系统能够达到的检索精度，可以看到，在微调参数的情况下，本发明的最高检索精度可以达到92.57％。

图9中给出的是在MPEG-7数据库上直接使用内距离形状上下文方法的检索率(圆圈标记的曲线)和使用本发明方法的检索率(“*”号标记的曲线)的比较。可以看到本发明给出的方法效果明显优于直接使用内距离形状上下文方法。

图10给出的是在MPEG-7数据库上检索的结果，第一列是待检索的形状，右边10列是直接使用内距离形状上下文方法(奇数行)的检索结果和本发明方法(偶数行)的检索结果，图中给出了前10个最相近的结果。可以看到本发明给出的方法效果明显优于直接使用内距离形状上下文方法。

图11给出的是带局部丢失的形状检索实验。第一列为丢失了一个部分的待检索图像，右边10列是直接使用内距离形状上下文方法(奇数行)进行检索和使用本发明方法(偶数行)进行检索得到的检索结果，图中给出了前10个最相似的检索结果。

表1不同方法在MPEG-7数据集上的检索率(bull’s eyes)

表2Kimia 99数据集的检索结果

表3在不同参数下的bull’s eye检索率

  b＝3  b＝5  b＝7  b＝9  α＝0.1  83.9％  88.11％  89.26％  89.84％  α＝0.15  84.33％  88.67％  89.66％  90.31％  α＝0.2  85.77％  90.29％  91.34％  91.84％  α＝0.25  88.71％  92.17％  92.57％  92.56％  α＝0.3  89.69％  91.16％  91.41％  91.16％  α＝0.35  89.03％  90.39％  90.30％  90.20％  α＝0.4  88.74％  89.99％  89.97％  89.84％

本发明不仅局限于上述具体实施方式，本领域一般技术人员根据本发明公开的内容，可以采用其它多种具体实施方式实施本发明，因此，凡是采用本发明的设计结构和思路，做一些简单的变化或更改的设计，都落入本发明保护的范围。