基于内容的SIFT+LSH管道缺陷检索算法研究

, ，， ，，

(1.中国计量大学 机电工程学院，杭州 310018; 2.中国科学院 成都计算机应用研究所，成都 610041;3.浙江省特种设备检验研究院，杭州 310018

0 引言

随着计算机视觉的发展以及在地下管道检测的成功应用，再结合地下待检测管道的本身特点，如数量多、长度大，每次检测都会出现大量的管道检测图像数据，如何对这些管道图像数据进行整理、处理和检索成为管道检测部门的最大难题。检测部门人员对同一条管道不同时间的内部情况进行对比分析，记录这条管道的使用情况。

早期对于管道使用情况是基于文字检索的，就是检测人员使用检测仪器沿着管道路径行走，使用相关的仪器，如：漏水检测仪等进行人工检测，检测完将检测的结果手动记入数据库以待后期查看，这种方法只能记录管道是否出现问题，但是无法判断管道内部具体的情况，也无法判断隐形隐患。随着计算机视觉的发展[1]，同时也为了对管道更好的管理，也有很多的研究者将视觉相关的检测方法应用到了管道的检测中，但仅限于实验室研究。大体思路都是设计一套检测装置获得管道内部图片，传输到PC端，采用各种方法进行实时检测。他们的不足就是在实际应用中管道会很长，检测装置一边行进一边检查会消耗很多时间，从而会影响居民的使用。在管道缺陷检测过程中，大部分的管道都是正常的，所以存在缺陷或者泄露的地方是少量的，因此无需对每时每刻获得的管道内部图片进行处理，只需要判断含有缺陷的地方损坏程度，同时记录管道内部的具体情况，还可以对未来检测的时间进行预测。

基于此，本文自主研发了一套检测装置，同时充分利用了SIFT(Scale Invariant Feature Transform)局部特征在场景识别领域表现出的出色性能和敏感位置哈希算法在大规模图像检索[2]中体现的性能优化，提出了基于SIFT局部特征[3-5]和敏感位置哈希[6-7]算法的管道缺陷检索。

1 系统设计方案

本文主要包括两个部分：检测装置设计和算法设计。检测装置主要用来获取管道内部情况图像。另外在检测的过程中如果检测装置在管道内部发生卡管的时候能知道检测装置的位置。基于此，设计了一套集多层球壳、内部主板、微处理器、摄像摄影探头、三轴加速度计、角速度计、低频发射器、高效能电池、数据存储器、照明装置等多个零部件集成为一个微小的球形装置。结构图如图1所示。

图1 检测装置结构示意图

装置完成以后就建立管道缺陷数据库，将管道里面可能出现的各种情况建立成一个数据库。检索流程如图2所示。首先选取特征描述对拍摄的某一条管道内部所有图片进行特征提取，建立特征库；然后在管道缺陷数据库中依次传入一张管道缺陷图片，用相同的方法对其进行特征提取，得到相应的特征向量；最后，选取一种度量两幅图像相似度的标准，如欧氏距离、汉明距离等，计算管道缺陷图像与该条管道拍摄的图像的特征库的各个特征相似度的大小，并按照相似度的大小进行排序，按照一定的要求输出检索结果图片。这些图片就是该管道出现问题的地方，根据这些图片就知道该管道损坏的程度，如果损坏程度小，根据图片可以预估一个下次检测时间，将危险防患于未然。如果管道已经损坏，可以根据检测装置里面的行进记录仪和该图片的帧数判断管道出现损坏的地方。基于内容的管道缺陷图像检索主要是将管道图像的表征特征和相似度的衡量方法交给计算机进行自行处理，很大程度上克服了检测人员的主观判断，大大提高了整个检索系统的效率。从某种意义上说，这是管道缺陷检测技术的蜕变。管道缺陷检索流程如图2所示。

图2 检索流程图

2 SIFT+LSH算法

2.1 SIFT特征提取算法

2.1.1 背景介绍

由于管道图像的模糊性和不均匀行，所以很难对图像的角点和边界进行检测。早期的一些学者研究了一些角点检测方法都具有旋转不变的特性，但如果对图像进行缩放，那么角点很有可能会发生变化。例如，如果对一幅尺寸比较小的图片放在一个尺度也很小的区域中时，可以很明显定位到角点，但把这幅图像的尺寸放大时，就会出现角点“消失”的情况。

SIFT是Lowe在1999年提出来的算法，在2004年又将该算法进一步完善，这是计算机视觉领域的重大突破。SIFT描述方法不仅具有尺度缩放不变性，而且在对图形进行明暗或者方位变换时，对图像的最终检测都不会有很大的影响。

总体而言，SIFT特征描述算法具有如下的特性：

1)SIFT特征是图像的局部特征，它对旋转平移、尺度变换、亮度变化保持不变性，对视角变化和噪声也能够保持一定的稳定性。

2)独特性好，信息量丰富，适用于海量特征数据库中进行快速、准确的匹配。

3)多量性，即使少数的几个物体也可以产生大量的SIFT特征向量。

4)高速性，经优化的SIFT匹配算法甚至可以达到实时的要求。

5)可扩展性，可以很方便的与其他形式的特征向量进行联合。

正是由于SIFT特征描述算法具备这些特点，所以选择SIFT算法来提取管道图像的特征。

2.1.2 具体实现

在提取SIFT特征之前，需要构建尺度空间来保证SIFT的稳定性和独立性。同时也因为被描述的特征实体只有在确定的尺度空间才会有意义。例如我们可以看到桌上的一本书，但是如果将粉笔放在整个银河系中，我们将无法发现这本书。尺度空间的构建过程如下：

L(x,y,σ)=G(x,y,σ)*I(x,y)

(1)

其中：L(x,y,σ)是模糊的图像；G(x,y,σ)是高斯模糊算子；I(x,y)是原始图像；(x,y)是尺度空间位置坐标；σ即使尺度参数，又是高斯模糊算子的方差，σ值越大，图像越粗糙，分辨率低，反之，图像越精细，分辨率越高。

构建完尺度空间之后，接下来就进行SIFT特征提取。提取步骤如下:

1)尺度空间的极值检测。

尺度空间的构建和高斯差分的计算主要用于确定图像的极值点，首先粗略的图像的极大值和极小值。主要通过遍历图像的每一个像素点和其相邻的像素点进行比较，其中相邻的像素点包括图像的8个相邻的像素点和上下相邻尺度图像的9*2个像素点，共26个像素点，确保每一个极值点不仅是二维图像空间中的极值点，也是尺度空间中的极值点。

2)除去不好的像素点。

通过尺度空间检测出的极值点只是“近似的”，因为有的极值点几乎不会完全位于像素点上，可能位于像素之间，但是我们根本无法访问“像素间”的数据，因此我们必须在数学上定义像素的位置。用可用的像素生成子像素值，然后进行泰勒展开，实现步骤如下：

(1)空间尺度泰勒展开式如下：

(2)

对式(2)求导，并令其等于0，得到子像素的位置:

(3)

(2)删除对比度低的特征点

对于对比度低的特征点只需要检查它的强度，将式(3)代入式(2)，保留前两项即可。

(4)

(3)边缘响应的去除

不同位置的极值点可能有不同的主曲率，主曲率通过一个2乘以2的Hessian矩阵H求出：

(5)

设H的特征值为α和β，那么：

Tr(H)=Dxx+Dyy=α+β

Det(H)=DxxDyy-(Dxy)2=αβ

(6)

令α=γβ，则

(7)

当α=β即γ=1时，7式取得最小值，因此，γ只需满足如下公式：

(8)

即如果(α+β)/αβ>(1+γ)2/γ，那么就将该特征点丢弃。

3)特征点方向确定。

通过以上两步基本可以确定特征点的稳定性，接下来就要为每一个特征点分配方向，使特征点具有旋转不变性。收集每个特征点周围的梯度方向和幅度，然后将最为突出的方向分配给特征点，以后的计算都是基于这方向进行。计算渐变幅度和方向的公式如下：

m(x,y)=

θ(x,y)=

αtan2((L(x,y+1)-L(x,y-1))/(L(x+1,y)-L(x-1,y)))

(9)

其中：L所用的尺度为每个关键点各自所在的尺度。

通过上面的式子计算特征点周围所有像素点的幅度和方向，并构建直方图[8]统计这些点的像素方向。特征点的方向范围为0～180°，将其分为36组。当对所有的像素点计算完后，直方图就会在某点取到峰值，那么特征点的方向就会被分配相应的峰值方向。

4)关键点描述子的生成。

最终得到的是一个具有128个数字的特征向量，用于唯一标识关键点。以关键点为中心取8乘以8的窗口，通过公式10遍历这些像素点，分别求出每一个像素点的幅度和方向。图像梯度中周围的像素点对于关键点的方向共献不一样，越靠近关键点，共享越大。将图像梯度按照4*4进行划分，分别计算图中8个方向的幅度。对于图像梯度整个区域，使用高斯加权的方式对多个不同的方向进行加权，同时随着关键点的距离增加，权重降低。这样最终就可以得到4*4*8=128维度的特征向量，最后将这个128维度的特征向量进行归一化，形成该特征点的唯一标识。

当通过SIFT特征描述算子提取完两幅图像的特征之后，通过不比较两幅图像中其中最近的一组关键点，如果小于设定的阈值，就认为这是一组匹配点。通过调整阈值的大小，排除错误的匹配点，这样也能使得SIFT算法更加稳定。Lowe在文中推荐阈值取0.8，但在实际应用中，当处理尺度、旋转和光照等很多影响因素时，阈值取0.4到0.6最佳。SIFT提取管道特征的流程如图3所示。

图3 SIST特征提取

2.2 LSH检索算法

LSH(Locality Sensitive Hashing，LSH)也称之为位置敏感哈希算法，是最为常用的最邻近搜索算法之一，尤其在对高维特征向量空间处理时有着出色的表现。它通过哈希函数将高维的特征向量映射到指定的向量中，使原本相邻的数据点经过哈希映射之后能够落入相同的桶中，不相邻的数据点经过映射之后落入到不同的桶中，这样就可以减少需要匹配的数据点的个数，同时增大查找到最邻近的数据点的概率，达到减少遍历空间中点的个数。

基于LSH的管道缺陷检索技术按照步骤可以分为特征提取、哈希编码以及汉明距离排序3个步骤，流程图如图3所示：

1)特征提取：对管道图像主要采取了SIFT局部特征，并将某条管道图像数据库的图像逐一进行特征提取，并将图像文件名与特征图像矩阵一一对应的方式存储到该条管道的图像特征库中。

2)哈希编码：哈希算法种类繁多，先用主成分分析法进行数据降维，然后旋转迭代，使用半监督学习，是每一位比特的方差最大化，并且各自无关。

3)汉明距离计算：等长字符串在对应位置的不同字符个数。

最后，通过计算待查询的管道缺陷图像特征向量与某条管道图像的特征向量逐一计算哈希编码之间的汉明距离，按照规定返回图像的个数进行相似度排序，进而得到检索的结果。

图4 SIFT+LSH管道图像检索

3 实验结果与分析

为了客观准确地评价整个算法的检索性能，选取了图像评价[9-10]的众多评价指标中的两个最具代表性的指标：准确率(Precision，PR)和召回率(Recall Rate，RR)。准确率即查准率，召回率即查全率。具体计算公式如下：

(10)

其中:A表示检索到的结果中相关样本的数量；B表示检索到的样本中不相关样本的数量；C表示样本中未被检索到的样本的数量。

实验采用C++语言编写，主要对比了基于SIFT特征+欧氏距离的图像检索方法(结果见图5)，基于SIFT+LSH的图像检索方法(检索结果如图6)，和基于SIFT+SpH图像检索(结果见图7)。

图5 SIFT+欧氏距离

图6 SIFT+LSH哈希算法

图7 SIFT+SpH哈希算法

表1是三中方法的实验结果数据评价，从结果中我们可以看出明显的看出SIFT+欧式距离的检索方法在检索准确度上略微优于其他两种，较SIFT+LSH哈希算法提升了1.95个百分点，较SIFT+SpH哈希[11-12]算法提升了1.5个百分点，总体来说差别不是很大，但是在检索时间上明显不足。尤其对长管道进行检测时会消耗太多时间。SIFT+LSH哈希算法的检索时间较SIFT+欧式距离提升了0.95967 s，SIFT+SpH哈希算法的检索时间较SIFT+欧式距离提升了0.68948。本文提出的基于SIFT+LSH算法的超声图像检索方法能够很大改善现有方法响应时间长的劣势。因此，基于SIFT+LSH算法的图像检索在保证准确率的前提下，能够满足管道图像检索的需求。

表1 3种方法实验结果数据评价

4 结语

本文提出了基于SIFT+LSH的管道缺陷检索算法，从实验结果可以看出在保证准确率的前提下，该方法有效地提高了检索速度。LSH算法有着它在处理大规模信息领域的优势，通过哈希编码计算汉明距离的方法很大程度上提高了运算速度。另外，该方法是先对管道进行内部状况拍摄，然后检索，不需要实时处理，这样就不会太影响城市地下管道的使用。同时，只需要对检索出来的有缺陷的管道图片进行专家评价，判断管道是否可以继续使用，以及对下一次检测的时间给一个评估，不需要对所有的图像进行处理。这种方法解决了传统检测方法消耗时间的久的问题，可以满足检测人员对管道使用情况的评估。

参考文献：

[1] YSyam B, Victor J S R, Rao Y S. Efficient similarity measure via Genetic algorithm for content based medical image retrieval with extensive features[A]. International Multi-Conference on Automation, Computing, Communication, Control and Compressed Sensing[C]. IEEE, 2013:704-711.

[2] Belloulata K, Belallouche L, Belalia A, et al. Region based image retrieval using Shape-Adaptive DCT[J]. International Journal of Multimedia Information Retrieval, 2014, 4(4):1-16.

[3] 刘润杰.基于全局和局部特征的图像检索算法研究[D]. 济南：山东师范大学,2016.

[4] 伯将军,郭书军, 伍淳华. SIFT局部特征描述算法在图像版权搜索中的应用[J].电子设计工程,2012, 20(3):137-141.

[5] 杨 程.图像检索中局部特征的提取和描述及其空间组织研究[D].上海:上海交通大学,2011.

[6] 夏立超.基于哈希算法的图像检索研究[D]. 合肥:合肥工业大学, 2015.

[7] 周建辉.基于半监督哈希算法的图像检索方法研究[D].大连:大连理工大学,2011.

[8] Dalal N, Triggs B. Histograms of oriented gradients for human detection [A].Proceedings of the 2005 IEEE Conference on Computer Vision and Pattern Recognition[C]. Washington D. C., USA: IEEE Computer Society, 2005: 886-893.

[9] 周景超,戴汝为,肖柏华.图像质量评价研究综述[J].计算机科学, 2008, 35(07):1-4.

[10] 贾强槐.图像检索结果质量评价[D].中国科学技术大学, 2015.

[11] Heo J P,Lee Y,He J,et al.Spherical hashing[A].Computer Vision and Pattern Recognition(CVPR),2012 IEEE Conference on[C].IEEE 2012:2957-2964.

[12] Datar M, Immorlica N, Indyk P, et al. Locality-sensitive hashing scheme based on p-stable distributions[A].Twentieth Symposium on Computational Geometry[C].ACM,2004:253-262.