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

摘要

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

主权项

一种检索相似性形状的方法，包括下述步骤：（1）提取输入查询图像和数据库中待检索图像的形状轮廓，查询图像称之为查询形状，待检索图像称之为待检索形状；（2）在步骤（1）所提取的查询形状和待检索形状的基础上，计算每个形状轮廓的特征，也就是描述子；（3）在步骤（2）计算得到的形状特征的基础上，对于输入的查询形状和数据库中的待检索形状所组成的形状集合，对集合中的任意两个形状之间进行匹配，求出其两两之间的不相似性度量值，根据求出的不相似性度量值组成不相似性度量矩阵；（4）根据步骤（3）求得的不相似性度量矩阵，计算查询形状跟数据库中任意一个待检索形状之间的相似度；（5）基于（4）中求得的输入查询形状跟数据库中n个待检索形状之间的相似度，确定检索输出结果；步骤（2）包括下述过程：（2.1）对每个形状轮廓进行均匀采样；（2.2）对于每个形状轮廓上的每个采样点pi，i表示采样点的序号，i＝1,...,N，使用内距离形状上下文描述子进行描述，N表示形状轮廓上的采样点的数量；（2.3）重复（2.2）的过程，计算获得某个形状轮廓上每一个采样点的内距离形状上下文描述子，从而获得对该形状的描述；步骤（3）具体包括下述过程：（3.1）两个形状之间的匹配：使用动态规划方法，求解任意两个形状轮廓上采样点的最佳对应关系和这两个形状之间的不相似性度量值，完成形状匹配；（3.2）形状集合中两两形状之间的匹配，得到不相似度量矩阵 {Di,j,i,j＝1,...,n,n+1}：对于由输入的查询形状和数据库中的待检索形状所组成的形状集合，利用步骤（3.1）所描述的方法，对集合中的任意两个形状，利用动态规划算法进行匹配，求出其不相似性度量值；假设数据库中含有n个待检索形状，n为正整数，输入的查询形状与数据库中的n个形状一起，一共组成了n+1个形状{xi,i＝1,...,n+1}；根据步骤（3.1），分别求出这n+1个形状两两之间的不相似性度量值，组成一个不相似度量矩阵{Di,j,i,j＝1,...,n,n+1}： D i , j = D ( 1,1 ) D ( 1,2 ) . . . D ( 1 , n ) D ( 1 , n + 1 ) D ( 2,1 ) D ( 2,2 ) . . . D ( 2 , n ) D ( 2 , n + 1 ) . . . . . . . . . . . . . . . D ( n , 1 ) D ( n , 2 ) . . . D ( n , n ) D ( n , n + 1 ) D ( n + 1,1 ) D ( n + 1,2 ) . . . D ( n + 1 , n ) D ( n + 1 , n + 1 ) 其中，Di，j表示第i个形状与第j个形状之间的不相似性度量值；步骤（4）具体包括下述过程：（4.1）定义关系矩阵wi,j，其计算公式如下： w i , j = exp ( - D i , j 2 λ i , j 2 ) 其中，Di,j是步骤（3.2）中获得的不相似度量矩阵，λi,j为归一化参数，该归一化参数的计算方法如下：λi,j＝α·mean({knnd(xi),knnd(xj)})在上式中，mean({knnd(xi),knnd(xj)})表示形状xi，xj的前b个最近邻距离的平均距离，所谓最近邻距离，是指与该形状的不相似性度量值中最小的b个距离；（4.2）定义概率转移矩阵P，该概率转移矩阵通过对wi，j沿行方向归一化得到，计算公式如下： P i , j = w i , j Σ h = 1 n + 1 w i , h （4.3）定义关键函数f，并通过下列递归的过程来求解关键函数： f t + 1 ( x i ) = Σ j = 1 n + 1 P i , j f t ( x j ) , i = 2 , . . . , ( n + 1 ) 且有ft+1(x1)＝1其中Pi,j为上述的转移概率矩阵；该递归过程需要经过T次迭代，参数T为预先设定的迭代次数；（4.4）使用步骤（4.3）的递归迭代过程得到关键函数f，结果记作fT(xi),i＝1,...,n,n+1，求解结果是一个n+1行1列的矩阵；去掉fT(x1)，所剩余的n行1列的矩阵中，第i行的值表示数据库中的第i个形状与输入查询形状的相似度。