以图搜图系统的设计与实现

刘晞远*

（西安电子科技大学通信工程学院，陕西西安，710126）

以图搜图系统的设计与实现

刘晞远*

（西安电子科技大学通信工程学院，陕西西安，710126）

本文主要是解决计算机基于内容图像识别问题，进行图像匹配与选择，寻求最佳最快的匹配方式的过程。本文主要从全局特征和局部特征两个方面着手，全局特征中主要研究了颜色特征和纹理特征，局部特征中分为特征点检测的FAST和HARRIS算法，特征点的描述主要采用了ORB算法和BRIEF算法和局部敏感哈希算法LSH。通过实验，改进了方法，最终设计的算法时间复杂度较低，搜索图片匹配度较高。

图像识别；全局特征；局部特征；算法

引言

基于内容的图片检索（Content Based Image Retrieval,CBIR），也有人称之为以图搜图，是利用机器学习、模式识别、计算机视觉等相关技术对图片的内容进行分析、检测、检索的一种应用。本文针对基于内容的图像检索的基本结构，研究了基于内容的图像检索技术的关键技术，详细研究了图像的特征提取方法、相似性度量方法以及实现的算法。

1 开发工具及方法步骤

1.1 开发工具

MATLAB 2015以上版本 ，包含： Statistics and Machine Learning Toolbox

Image Processing Toolbox ，

1.2 方法步骤

图片解码-图像预处理-图像特征提取-特征相似性度量-特征空间索引

本次实验中，给出一张图片，在已有的图片库中查询与其具有相似度的图片。解码目标图片，对其进行预处理并且使用特征点检测方法检测其最优特征点，并将这些特征点于图片库中的图片的特征点进行相似性度量，借此获取图片库中与之相似的图片。此过程中，使用特征空间索引的方法减少查询消耗的时间空间代价。

1.3 本次实验使用的算法[1]

（1）纹理特征算法——LBP

线性反投影算法（Linear Back Projection，简称 LBP）又称累加法，是最早使用的一种简单（ECT图像重建）成像算法。它将通过某点的所有投影射线进行累加，再反向估算出该点的密度值

（2）颜色熵，颜色矩的计算

颜色直方图：它能简单描述一幅图像中颜色的全局分布，即不同色彩在整幅图像中所占的比例，特别适用于描述那些难以自动分割的图像和不需要考虑物体空间位置的 图像。

颜色矩：图像中任何的颜色分布均可以用它的矩来表示。此外，由于颜色分布信息主要集中在低阶矩中，因此，仅采用颜色的三阶矩就足以表达图像的颜色分布。

（3）Harris角点算法+Brief特征点描述子

Harris角点检测原理是利用移动的窗口在图像中计算灰度变化值，其中关键流程包括转化为灰度图像、计算差分图像、高斯平滑、计算局部极值、确认角点。

BRIEF是对已检测到的特征点进行描述，提供了一种计算二值串的捷径大大的加快了特征描述符建立的速度，同时也极大的降低了特征匹配的时间，是一种非常快速，很有潜力的算法。

（4）局部敏感哈希算法[LSH]

将原始数据空间中的两个相邻数据点通过相同的映射或投影变换（projection）后，这两个数据点在新的数据空间中仍然相邻的概率很大，而不相邻的数据点被映射到同一个桶的概率很小。

2 实验过程

2.1 颜色特征——颜色熵，颜色矩的计算[1]

颜色特征是一种全局特征，描述了图像或图像区域所对应的景物的表面性质。一般颜色特征是基于像素点的特征，此时所有属于图像或图像区域的像素都有各自的贡献。由于颜色对图像或图像区 域的方向、大小等变化不敏感，所以颜色特征不能很好地捕捉图像中对象的局部特征。另外，仅使用颜色特征查询时，如果数据库很大，常会将许多不需要的图像也检索出来。颜色直方图是最常用的表达颜色特征的方法，其优点是不受图像旋转和平移变化的影响，进一步借助归一化还可不受图像尺度变化的影响，基缺点是没有表达出颜色空间分布的信息。

描述颜色主要从颜色熵和颜色矩，颜色熵是以像素点的对数和形式表达的，能够准确反映出颜色直方图特征，颜色矩主要研究的是颜色一、二、三阶矩，其中一阶矩二阶矩分别代表了整张图片的颜色均值和颜色方差，能够较好的比对两幅图片的颜色特征。其次，对于颜色空间的选取也有多种方法，最常用的的一个是RGB，一个是HSV。RGB就是分别分析红绿蓝三种颜色的参数，HSV还加入了颜色深度的概念，所以实际使用起来相对复杂但是性能较好。见图2所示。

图1 港口照片

图2 基于图1的颜色直方图

2.2 纹理特征——LBP算法[2]

纹理是一种反映图像中同质现象的视觉特征，它体现了物体表面的具有缓慢变化或者周期性变化的表面结构组织排列属性。纹理具有三大标志：某种局部序列性不断重复、非随机排列、纹理区域内大致为均匀的统一体。

全局特征中我们还引入了 LBP思想，它研究的是像素点 8领域特征。在待测像素点的8领域中我们按照一个旋转方向将8领域内的像素值二值化处理生成一个 8位二进制编码，再利用MATLAB中内置的shift函数将其不断进行移位处理生成8个编码，然后用函数对这8个编码取最小值作为该像素点的值，将值再生成一个与原图像同维矩阵（边缘点补零后计算）再对这个矩阵进行上述熵、矩的处理。

此处我们使用 LBP算法对纹理特征进行检测和提取。以下图为例。

图3 使用LBP算法密纹理特征进行检测和提取

2.3 局部特征——Harris + Brief[3]

（1）Harris

Harris角点检测原理是利用移动的窗口在图像中计算灰度变化值，其中关键流程包括转化为灰度图像、计算差分图像、高斯平滑、计算局部极值、确认角点。

（2）Brief

BRIEF算法计算出来的是一个二进制串的特征描述符。它是在一个特征点的邻域内，选择n对像素点pi、qi（i=1,2,…,n）。然后比较每个点对的灰度值的大小。

要想描述局部特征，就要明确两个点：一是一张图片有特别多的像素点，哪些点能够代表这些图片？二是怎样用计算机的语言描述这些点的特征？这两个问题涉及到数字图像处理中的检测子和描述子的概念。

特征点检测子是为了检测一幅图像中哪些点是特征点。本文主要采用了Harris 和Fast两种算法，Harris 算法性能较好，Fast算法速度较快，通过实际操作发现，对于1000张参数，两种算法选取相同参数时后者得到的特征点大约是前者的2倍左右（H算法170万个，F算法340万个）而且Fast算法算出来的特征点与希望得到的结果有偏差，这一点在实验过程中会详细解释。Harris算法是通过严谨的数学推导得到类似椭圆的方程，而椭圆的长轴与短轴受参数λ的影响，且与λ成反比关系。这样这个方程的数学意义就成了改变λ1与λ2两个参数使得椭圆锥的形状发生改变，然后研究当xy坐标改变时z坐标的变化率。如果某一个方向上变化缓慢而另一个方向上z变化迅速，则说明该点是图像的边界点；如果z在两个方向上变化均不明显，说明这块区域是图像的“平坦区”即图像内部；如果z在两个方向上变化都很明显，则说明该点是图像的角点。而Fast算法比较简单，它仅仅对比一个像素点与周围像素点的像素值差来确定该点是不是特征点，这种算法的缺点十分明显，接下来的实验过程中会详细提及我们组在实际制作时对该算法的处理。

特征点描述子是为了描述像素特征点的特征。主要有HOG，Brief算法和ORG算法。Brief算法是在像素点周围选取512个像素点对，每个点对第一个大于第二个记为1，小于记为0，然后形成一个512位的二进制编码来描述特征点。但是这种方法不具有旋转不变性，当图像旋转时，选取点对的相对位置也发生了改变，特征点的描述子与之前不同，这样就出现一个特征点对应多个描述子的问题。为了解决这个问题，采用了Streer brief算法，规定了一个坐标轴方向。这个方向是由该特征点与特征点领域内的像素质心点的连线决定的，这样就解决了旋转不变性。但是这却带来了新的问题，原先Brief算法中每个描述子的方差很大，即特征点的辨识度很高，优化后的Steer brief算法描述子的方差反而缩小了，这样导致用该算法描述特征点时图像的辨识度下降。出现这个问题的主要原因是Steer brief算法各个维度的相关性很大，有代表性意义的维度数量不足。为了解决这个问题采用了ORG算法，ORG算法是在特征点的31*31领域内先进行去燥处理，将一个5*5的方格计算出平均像素值看做是一个格子。这样就得到27*27的领域，在这个领域内我们随机选取一个点对，计算300个特征点中该点对的均值，然后确定一个阈值来判断两个点对之间的相关性，如果两个点对的均值差大于阈值，则我们认为这两个点对不相关，反之相关。这样我们在c27 27（组合数）中最终选取256个不相关的点对，如果不够256或者多余256个就调整阈值来满足。这 256个点对最终构成该特征点描述子的256个维度。HOG算法的有点是善于捕捉人脸上的特征点，所以当最终的描述子参考了HOG算法后对含人的图片辨识度大大增加。

下图为局部特征实例：

图4 局部特征实例

2.4 索引生成——LSH

颜色特征设为索引

纹理特征设为索引

局部特征设为索引

局部敏感哈希算法LSH[4]，这个算法主要解决了缩小寻找范围的问题。我们先以任意四个维度为一组构造一层哈希桶，然后将每一个特征点对应放入哈希桶中。然后再选取其余四个维度构造第二层哈希桶，以此类推。这样，同一个特征点可能出现在不同桶内，但是每层有且仅有一次。最后，我们将与特征点在同一个桶中的描述子取出，并逐一计算其与特征点的汉明距离，然后选取汉明距离最短的20个描述子或者确定一个阈值，选取汉明距离在该阈值内的所有特征点作为匹配项。如果利用这层哈希得到的数据仍然比较大或者哈希桶中的特征点数量过于多，这样我们就需要建立二层哈希，二层哈希与一般的哈希算法一样。

3 成果展示

3.1 代码模块结构[5]

3.2 成果展示

（1）全局特征检索图片

首先是读入图片。在所给的1000张图片中有一张灰度图片造成读入错误，我们的解决办法是进行一次判断，如果不是灰度图像则转化成灰度图像处理。

然后是全局特征，我们在做完颜色特征后进行了一次检测，效果不好。但是当我们加入纹理特征后，图像识别能力大大提高。这与原先猜想的内容有很大不同，之前猜想的是局部特征才能准确识别图像。

图5 全局特征检索图

（2）局部特征检索图片

再次是局部特征。这里我们遇到一个小问题，即数组角标与矩阵角标的差别导致数组越界。我们一开始是采取附空值，结果导致了在250维之后随机值越界数组不完整。发现问题后马上对代码进行了更正。

但是当我们用上述算法分析完1000张图片后发现特征点数量远远超过预期，用 Harris 算法得到了 170万个特征点，Fast算法得到了340万个。造成计算机分析困难。我们小组讨论后决定，将特征点数量控制在50万个之内解决起来比较现实。于是对算法的阈值进行调整。但是调整后发现特征点数量虽然在 50万个之内，但是所选取的特征点并不是最合适的特征点。以水立方图片为例，图片上水立方为淡蓝色，而下方的湖面有亮黄色的磷光，且因为水立方是一个整体，所以只有边界处有特征点，原先处理方法中湖面处的特征点检测出来的较多而水立方上面较少。阈值提高后，条件变得苛刻，所有水立方上面的特征点失效只留下湖面处的特征点，这样的处理方法显然不能完成图形匹配。由此可见，并不是某一个像素点与周围像素点的像素值差别越大越有意义。此外，我们又分析了之前的算法为什么会导致如此多的特征点。我们通过调试发现，对于有对称性的规则图片，比如床单。床单上的特征点特别多而且对称分布。所以解决特征点太多的问题不应该简单地提高阈值处理，而应该判别某一块区域内是否有过多的特征点以及一张图片中是不是有数量特别多且描述子的汉明距离比较小的特征点，应该对这类特征点进行处理。

（3）图片去噪处理

对噪声点进行平滑处理，对比椒盐去燥和高斯去燥后发现椒盐去燥得到的图像较为清楚，这一点与资料相悖。详细分析后我们发现我们的图片是加过椒盐噪声的所以高斯去燥效果不显著，对于普通的图片因为其噪声点分布大致吻合高斯分布，所以用高斯去燥效果更好一些。经过我们的试验发现当去燥的领域选择为3的时候去燥效果较好且不至于因去燥而使得图片过于模糊。另外我们也尝试了网上的恢复算法，但是效果并不明显。

4 结束语

本文针对基于内容的图像识别问题，进行图像匹配与选择，寻求最佳最快的匹配方式的过程。采用了全局特征及局部特征的算法，研究了颜色特征选取、纹理特选取、试验了图片局部特征检测子两种算法Harris 算法和Fast算法、特征点描述子HOG，Brief算法和ORG算法和局部敏感哈希算法LSH，结果如下：

（1）颜色特征后进行了一次检测，效果不好。但是当我们加入纹理特征后，图像识别能力大大提高。可以识别粽子，水立方，小龙虾床单等图片。

（2）解决特征点太多的问题不应该简单地提高阈值处理，而应该判别某一块区域内是否有过多的特征点以及一张图片中是不是有数量特别多且描述子的汉明距离比较小的特征点，应该对这类特征点进行处理。

（3）对于普通的图片因为其噪声点分布大致吻合高斯分布，所以用高斯去燥效果更好一些。经过我们的试验发现当去燥的领域选择为 3的时候去燥效果较好且不至于因去燥而使得图片过于模糊。

（4）在打开系统时就对所有图片建立索引并且一直用该索引结果，可降低时间复杂度。

[1]舒禹程. 基于特征描述子的图像匹配算法研究[D]. 华中科技大学博士学位论文,2015： 45-52.

[2]牛一帆. 基于内容的图像识别检索技术研究与系统实现[D]. 西安理工大学硕士学位论文,2007： 33-38.

[3]谢凤英,等. 数字图像处理及应用[M]. 电子工业出版社,2014：308-317.

[4]A.Gionis,P.Indyk and R.Motwani. Similarity Search in High Dimension via Hashing,CVPR 2012： 518-529.

[5]刑树军等译. MATLAB编程.34-50,185-197.

Design and Realization on Search by Image System

LIU Xiyuan*
(University of Electronic Science and Technology XIAN,School of Information and Communication Engineering,Shanxi province,710126,China)

Aiming at the content-based image recognition resolving problem，methods of searching and matching pictures is introduced in this paper. Global feature and local feature have been researched in this paper.Colour feature and textural feature have been studied among global feature,FAST and HARRIS algorithm of feature point detection have been adopted in local feature. ORB,BRIEFand local sensitivity algorithm (LSH) have been adopted.We have improved the method,and the final design algorithm has low time complexity,search pictures have higher matching degree.

image recognition; global feature; local feature; algorithm

TP391

A

1672-9129(2017)06-0033-04

10.19551/j.cnki.issn1672-9129.2017.06.011

刘晞远. 以图搜图系统的设计与实现[J]. 数码设计,2017,6(6)： 33-36.

Cite：LIU Xiyuan. Design and Realization on Search by Image System[J]. Peak Data Science,2017,6(6)： 33-36.

2017-02-08；

2017-03-12。

刘晞远（1997.01-），男，陕西西安，安西安电子科技大学，通信工程学院，本科，研究方向：通信与计算机。

Email：2209282216@qq.com