一种基于区间权值的相似性度量方法

1.一种基于区间权值的相似性度量方法，具体步骤为：首先，检索系统事先离线对图像库中的所有图像进行预处理和特征提取，得到库中所有图像的特征向量，形成图像的特征向量库；然后再由用户输入查询图像，检索系统对查询图像进行预处理和特征提取，获取查询图像的特征向量，并将查询图像的特征向量和图像特征向量库中的特征向量进行相似度匹配，将与查询图像最相似的图像返回给用户；其特征在于：所述的将查询图像的特征向量和图像特征向量库中的特征向量进行相似度匹配的具体方法如下：
假设待匹配的两幅图像的特征向量分别为A、B，特征向量A＝{ai}，特征向量B＝{bi}；ai为特征向量A的第i维分量，bi为特征向量B的第i维分量，i的取值为0，1，.......，L-1，L为特征向量的长度，取整数；
1)对两幅图像的特征向量A、B对应的每维分量ai、bi(i＝0，1，.......，L-1)求差值，即ai-bi，然后采用如下公式对每维分量间的差值进行归一化：
βi＝|ai-bi|/max(|ai|，|bi|，|ai-bi|)，i＝0，1，.......，L-1
其中：βi为对ai-bi归一化后的值，其取值范围为[0，1]；
2)对[0，1]区间进行不均匀或均匀划分，并给每个划分的区间分配一个权值：
首先，将[0，1]不均匀或均匀划分为N个区间，N的取值为4～8之间的整数，即：K0＝[0，K1)、[K1，K2)、......、[Kk-1，Kk)，......，[KN-1，KN＝1]，然后，为每个区间[Kk-1，Kk)分配一个权值Wk，其中：Wk的取值范围为0～10，k＝1，2，......，N；
3)确定归一化后的图像特征分量间的差值βi所对应的权值Qi：
如果归一化后的图像特征分量间的差值βi∈[Kk-1，Kk)，则差值βi所对应的权值Qi为步骤2)中区间[Kk-1，Ki)所分配的权值，即Qi＝Wk；其中：i的取值为0，1，.......，L-1；k的取值为1，2，......，N；
4)对步骤3)中得到的所有权值进行累加求均值，得到特征向量A、B之间的相似性度量值SA，B为：
$S_{A,B}=\frac{1}{L}\underset{i=0}{\overset{L-1}{\Sigma }}{Q}_i.$

技术领域\n本发明是一种基于区间权值的相似性度量方法，属于多媒体检索领域。\n背景技术\n相似性度量方法的选择是基于内容的图像检索的一个关键环节。在基于内容的图像检索系统中，首先由用户提交查询图像给系统，系统对查询图像进行特征提取，获取查询图像的特征向量，然后采用相似性度量算法对获得的特征向量和图像特征库中的特征向量进行相似度匹配，最后系统将与查询图像相似的图片返回给用户。常用的相似性度量方法有：街区距离、欧氏距离等等。\n在计算机中存储的各种数字图像，由于在扫描或传输过程引入噪声(例如扫描得到的电子图书)及拍摄过程中光线不同等等而造成相同内容的图像存在一定的差异，此外，相关图像在局部范围内也存在差异，因此，在匹配的过程中，用户希望系统能具有很好的鲁棒性，能忽略这些小的差异而将这些相关的图片检索出来。现有的相似性度量方法并没有对图像特征分量间每维分量的差值进行区间划分及权值分配，以缩小这种差值对整个匹配过程的影响。\n发明内容\n本发明提出了一种基于区间权值的相似性度量方法，该方法通过对每维特征分量间的差值进行区间划分及权值分配，进而能够提高图像检索的检索效率。\n本发明的总体思想如下：本发明是对任意两幅图像的特征向量进行相似性度量。在进行相似性度量的过程中，首先计算这两个特征向量间对应的每维分量的差值，并对所有的分量差值进行[0，1]归一化；再对[0，1]进行区间划分和为每个区间分配一个权值；然后判断所有归一化的差值所落入的区间，获取它们的权值；最后对所有权值进行累加求均值，并将该均值作为这两幅图像特征向量的相似性度量值。\n具体创新点：对两个特征向量间对应的每维分量的差值进行了归一化、区间划分及权值分配，本发明通过区间划分及同一区间给定相同权值，从而忽略了量化到同一区间的分量间的差异，通过各区间的权值分配反映了每一区间对相似性度量的重要性。\n本发明的技术方案为：用于该图像检索系统的检索图像可以是bmp格式(或其他格式)的图像，保存于计算机硬盘或移动存储媒体上，首先由用户选择查询图像，再由计算机进行相应的运算和处理。其主要过程为：计算机系统接收用户输入的查询图像，再由检索系统对其进行处理。\n具体方法步骤为：\n首先，检索系统事先离线对图像库中的所有图像进行预处理和特征提取，得到库中所有图像的特征向量，形成图像的特征向量库。然后再由用户输入查询图像，检索系统对查询图像进行预处理和特征提取，获取查询图像的特征向量，并将查询图像的特征向量和图像特征向量库中的特征向量进行相似度匹配，将与查询图像最相似的图像返回给用户。\n所述的将查询图像的特征向量和图像特征向量库中的特征向量进行相似度匹配的具体方法如下：\n现有待匹配的两幅图像的特征向量A、B，假设已知：特征向量A＝{ai}，特征向量B＝{bi}，其中：ai为特征向量A的第i维分量，bi为特征向量B的第i维分量，i的取值为0，1，.......，L-1，L为特征向量的长度，取整数。采用本发明提出的基于区间权值的相似性度量方法计算特征向量A、B之间的相似度，步骤如下：\n1)对两幅图像的特征向量A、B中所对应的每维分量ai、bi(i＝0，1，.......，L-1)求差值，然后再对差值进行[0，1]归一化：\n先计算对应的每维分量间的差值ai-bi，然后采用如下公式对每维分量间的差值进行归一化：\nβi＝|ai-bi|/max(|ai|，|bi|，|ai-bi|)，i＝0，1，.......，L-1\n其中：βi为对ai-bi归一化后的值，其取值范围为[0，1]。\n2)对[0，1]区间进行不均匀(或均匀)划分，并给每个划分的区间分配一个权值：\n首先，将[0，1]不均匀(或均匀)划分为N个区间(通常N取4～8间的某个整数)，即：[K0＝0，K1)、[K1，K2)、……、[Kk-1，Kk)，……，[KN-1，KN＝1]，然后，为每个区间[Kk-1，Kk)分配一个权值Wk(k＝1，2，......，N，Wk一般取值范围为0～10)，Wk可根据实际情况分配，可取整数也可以取小数。\n3)确定归一化后的图像特征分量间的差值βi∈[0，1]所对应的权值Qi：\n如果归一化后的图像特征分量间的差值βi∈[Kk-1，Kk)，则差值βi所对应的权值为步骤2)中区间[Kk-1，Kk)所分配的权值Wk，即Qi＝Wk，i的取值为0，1，.......，L-1；k的取值为1，2，......，N。\n4)对步骤3)中得到的所有权值进行累加求均值，得到特征向量A、B之间的相似性度量值SA，B：\n$S_{A,B}=\frac{1}{L}\underset{i=0}{\overset{L-1}{\Sigma }}{Q}_i$\n本发明通过区间划分及同一区间给定相同权值，从而忽略了量化到同一区间的分量间的差异，通过各区间的权值分配反映了每一区间对相似性度量的重要性，在相似度匹配的过程中，能够提高图像检索的效率。\n附图说明\n图1图像检索系统整体流程框图\n图2区间权值示意图\n图3(a)系统检索得到的平均查全率\n图3(b)系统检索得到的平均查准率\n具体实施方式\n下面结合附图对本发明作进一步说明：\n本实施例的技术方案如图1所示：\n首先，检索系统事先离线对图像库中的所有图像进行预处理和特征提取，得到库中所有图像的特征向量，形成图像的特征向量库。然后再由用户输入查询图像，检索系统对查询图像进行预处理和特征提取，获取查询图像的特征向量，并将查询图像的特征向量和图像特征向量库中的特征向量进行相似度匹配，将与查询图像最相似的图像返回给用户。\n用于该图像检索系统的检索图像可以是bmp格式(或其他格式)的图像，保存于计算机硬盘或移动存储媒体上，首先由用户选择查询图像，再由计算机进行相应的运算和处理。计算机处理的过程为：计算机系统接收用户输入的查询图像，再由检索系统对其进行处理。本实施例中的计算机为“清华同方微机，Intel(R)Celeron(R)CPU 3.20GHz，1.25G内存，80G硬盘”，采用VC++6.0编程实现。\n本实施例中的将查询图像的特征向量和图像特征向量库中的特征向量进行相似度匹配的具体方法如下：\n采用的图像数据库是由扫描仪扫描得到的文档图像数据库，由密度分布特征提取算法提取文档图像的特征向量，得到的特征向量A、B的长度是：2×图像的分块块数M，即：L＝2M。(在本实施例中，M根据实验过程中具体分块块数不同而改变，本实验系统将给出9个具体的M值。)\n1)设特征向量A＝{ai}，特征向量B＝{bi}；ai为特征向量A的第i维分量，bi为特征向量B的第i维分量，i的取值为0，1，......，L-1，L为特征向量的长度，取整数。对两幅图像的特征向量A、B对应的每维分量ai、bi(i＝0，1，.......，L-1)求差值，然后再将差值归一化到[0，1]内，设归一化后的值为βi，具体归一化方法为：\n先计算对应的每维分量间的差值ai-bi，然后采用如下公式对每维分量间的差值进行归一化：\nβi＝|ai-bi|/max(|ai|，|bi|，|ai-bi|)，i＝0，1，.......，L-1\n其中：βi为对αi-bi归一化后的值，其取值范围为[0，1]。\n2)对[0，1]区间进行划分(此处采用不均匀划分)，并给每个划分的区间分配一个权值：\n首先，将[0，1]划分为4个区间，即：[0，0.02)，[0.02，0.05)，[0.05，0.1)和[0.1，1]，然后，为每个区间分配一个权值Wk(k＝1，2，3，4)，具体为在[0，0.02)内，给定权值W1为5；在[0.02，0.05)内，给定权值W2为2；在[0.05，0.1)内，给定权值W3为1；在[0.1，1]内，给定权值W4为0。\n3)确定归一化后的图像特征分量间的差值βi∈[0，1]所对应的权值Qi：\nβi的取值范围被划分为4个区间，当βi在[0，0.02)内，给定权值Qi为5；βi在[0.02，0.05)内，给定权值Qi为2；βi在[0.05，0.1)内，给定权值Qi为1；βi在[0.1，1]内，给定权值Qi为0，则特征向量A与特征向量B的距离SA，B为：\n$S_{A,B}=\frac{1}{L}\underset{i=0}{\overset{L-1}{\Sigma }}{Q}_i$\n$Q_i=\left\{\begin{array}{cc}5& {\beta }_i\in \left[\mathrm{0,0.02}\right)\\ 2& {\beta }_i\in \left[\mathrm{0.05,0.05}\right)\\ 1& {\beta }_i\in \left[\mathrm{0.05,0.1}\right)\\ 0& {\beta }_i\in \left[\mathrm{0.1,1}\right]\end{array}\right.$\n图2给出了计算特征向量A与特征向量B之间距离的区间权值示意图。\n在本实施实例的文档图像数据库中共有900幅图片，每幅图片都有9幅由同一文档图像经过各种变换处理得到的相关图像，每次检索返回13幅图片。图3给出了本系统随机抽取若干幅图像，分别采用街区距离、欧式距离及本发明给出的基于区间权值的相似性度量方法，测得的每幅图像的平均查全率和查准率。查全率和查准率的定义如下：\n查全率(recall)用R表示，查准率(precision)用P表示。\n$R=\frac{N_A}{N_A+N_C}$\n$P=\frac{N_A}{N_B+N_A}$\n其中：NA为检索返回的相关图像数目，NB为检索返回的不相关的图像数目，NC为图像库中没有检索出来的相关图像数目。\n在图3(a)和(b)中，其横坐标取值范围所对应的一维数组count1＝[1，2，3，4，5，6，7，8，9]，它表示分别把图像划分为不同的块数，所对应的块数数组是：count2＝[1×1，2×2，4×4，8×8，12×12，16×16，24×24，32×32，48×48]，即：横坐标中的数值1表示不对图像划分即1块，M＝1；横坐标中的数值2表示把图像划分为2×2即4块，M＝4；横坐标中的数值3表示把图像划分为4×4即16块，M＝16；依次类推根据横坐标就可以知道此次基于密度分布特征的实验把图像划分成了几块，得到M值。\n从图3中可以看出，本发明提出的基于区间权值的相似性度量方法在给出的9种分块方式下，得到的查全率和查准率始终优于欧式距离。由于查全率和查准率在本实验系统中得到的分布曲线相似，且采用欧式距离得到的查全率和查准率始终最低，因此，此处只对实验系统采用本发明所提出的基于区间权值的相似性度量方法和街区距离得到的查全率分布图进行分析。\n从图3(a)中的查全率分布曲线可以看出，只有在图像分为48×48块时，采用本发明给出的基于区间权值的相似性度量方法得到的查全率略低于街区距离，其他时候均优于或等同于街区距离。尤其是把文档图像划分为2×2块时，本发明提出的基于区间权值的相似性度量方法的查全率可以高达到92.3％，而此时街区距离的查全率仅为5.3％。\n实验结果表明，本发明结合某些特征提取算法，能够提高图像检索的效率。\n下面对本发明作进一步说明：\n1)本发明算法的简化：当用于相似度匹配的特征向量为归一化的特征向量时，即特征向量A与特征向量B的每维分量ai，bi均归一化到[0，1]内，该算法可简化为βi＝|ai-bi|，算法的后续步骤如上。简化后的算法由于计算过程中省去了除法运算，可以极大地提高运算速度。\n2)βi所在的[0，1]区间的划分：根据各区间段对相似度影响的特性来划分，但不宜分得太细。通常4～8个区间即可，既能保证相似度度量的一定准确性又减少了运算量。\n3)区间的权值分配：根据区间对相似度的重要程度来分配，可根据实验经验来分配，也可以通过其他优化算法来进行分配。\n4)本发明提出的相似性度量方法主要运用于多媒体检索等高维特征值相似度比较方面。