王 拓 于徐紅 劉志杰

(貴州師范大學(xué)貴州省信息與計(jì)算科學(xué)重點(diǎn)實(shí)驗(yàn)室， 貴陽 550025)

?

哈?？焖賵D像匹配算法研究

王 拓 于徐紅 劉志杰

(貴州師范大學(xué)貴州省信息與計(jì)算科學(xué)重點(diǎn)實(shí)驗(yàn)室， 貴陽 550025)

如何快速有效地在大量數(shù)據(jù)中將圖片篩選匹配出來，是圖像匹配技術(shù)研究的重點(diǎn)課題之一。通過分析感知哈希算法及Surf算法各自的優(yōu)點(diǎn)，提出用感知哈希算法進(jìn)行初步圖片搜索，利用Surf算法提取相似圖片局部特征，從而更精準(zhǔn)地確定最相似圖片，增加圖片匹配的魯棒性。實(shí)驗(yàn)結(jié)果表明，在對圖片進(jìn)行處理后，哈?？焖賵D像匹配算法仍能快速地從本地圖片庫中將最相似圖片搜索出來。

感知哈希算法； DCT變換； Surf算法； 指紋數(shù)據(jù)

近年來，隨著計(jì)算機(jī)、手機(jī)等電子產(chǎn)品的不斷發(fā)展和普及，圖片已成為我們記錄生活的一種重要方式。據(jù)Facebook官方公布，現(xiàn)在每天上傳的圖片數(shù)量約20億張，并且這個數(shù)字還在不斷增加。同時，人們也不再僅僅局限于使用文字來搜索圖片，“以圖搜圖”在這種情況下應(yīng)運(yùn)而生。目前應(yīng)用“以圖搜圖”的主要是互聯(lián)網(wǎng)圖像搜索引擎網(wǎng)站，例如Google、百度、搜狗、Picitup、Bing、TinEye、Incogno等。大部分人的手機(jī)、電腦或其他存儲設(shè)備里面也有成千上萬張圖片，如何在自己的圖片庫里快速找出想要查看的圖片也是一個急需解決的問題。因此，如何將大量的圖片進(jìn)行數(shù)據(jù)處理與存儲已成為大數(shù)據(jù)時代面臨和必須解決的一個重要難題[1]。

目前，對圖片進(jìn)行特征提取應(yīng)用最多的還是在Sift算法基礎(chǔ)上，先對圖像進(jìn)行特征提取，然后根據(jù)提取特征對圖像進(jìn)行哈希編碼，生成這個圖像的“指紋”特征。Sift算法的優(yōu)點(diǎn)是對圖像的旋轉(zhuǎn)、變換等都有很好的魯棒性，缺點(diǎn)是復(fù)雜度比較高。此次研究基于Sift算法的改進(jìn)算法——Surf算法，并基于哈希編碼規(guī)則來提升圖片的搜索比對速度[3-4]。

1 算法描述

1.1 感知哈希算法

哈希算法是一種將圖片生成一組“指紋”數(shù)據(jù)的方法。在進(jìn)行圖片搜索比對時，首先對圖片進(jìn)行特征信息提取，并生成一組二維數(shù)組即圖片指紋。通過對目標(biāo)圖像進(jìn)行處理得到“指紋”后，將其與哈希圖像庫中的圖片直接進(jìn)行“指紋”比對。相對于其他形式的特征值對比，二維數(shù)組有更高的時效性優(yōu)點(diǎn)。

感知哈希算法(perceptual hash algorithm，簡寫為pHash)。其流程圖見圖1。

圖1 感知哈希算法流程圖

pHash對一幅圖片的處理過程如下：

(1) 縮小尺寸。pHash將圖片縮小成N*N。這樣做的目的是簡化了DCT的計(jì)算，去除各種圖片尺寸和圖片比例的差異, 只保留結(jié)構(gòu)、明暗等基本信息。一般情況下，N的值設(shè)置為32。

(2) 簡化色彩。將圖片轉(zhuǎn)化成灰度圖像，進(jìn)一步簡化計(jì)算量。

(3) 計(jì)算平均灰度。計(jì)算圖片中所有像素的灰度平均值。

(4) 計(jì)算平均值。如同均值哈希算法一樣，計(jì)算DCT的均值。

(5) 計(jì)算hash值。這是最主要的一步，根據(jù)DCT變換得到的32*32矩陣中，因?yàn)榻^大部分信息包含在左上角8*8的系數(shù)子矩陣中，并且為了簡化計(jì)算，在計(jì)算時只取其左上角8*8的系數(shù)子矩陣，然后將其設(shè)置成0或1的64位的hash值，大于等于DCT均值的設(shè)為“1”，小于DCT均值的設(shè)為“0”。組合在一起，就構(gòu)成了一個64位的整數(shù)，即為這張圖片的指紋。

本算法中，根據(jù)矩陣中8*8的系數(shù)子矩陣得出二維離散余弦變換(DCT)：

(1)

u≥0,v

式中:g——N*N圖像像素點(diǎn)；

G——N*N矩陣中閾矩陣；

α—— 余弦系數(shù)矩陣。

對一張圖片進(jìn)行DCT變換后，便可將其像素信息以矩陣形式輸出。若代表矩陣形式，式(1)可簡化為：

F(u,v)=Af(x,y)AT

在利用pHash算法生成圖片指紋后，就可比對不同圖片的指紋來確定出最相似圖片。首先要計(jì)算出8*8矩陣中圖片信息生成的64位中有多少位是不一樣的。如果不相同的數(shù)據(jù)位數(shù)不超過5, 就說明兩張圖片很相似, 如果超過10, 說明它們是兩張不同的圖片[5]。

感知哈希算法在處理大量圖片時的時效性很高，然而該算法針對的是圖片的整體特征，不能對局部特征進(jìn)行提取和細(xì)致的識別，這就需要在局部特征提取方面來加強(qiáng)算法的魯棒性。

1.2 Surf算法

1999年，David Lowe提出尺度不變特征變換(scale-invariant feature transform，簡寫為Sift)，Sift算法有以下特點(diǎn)：

(1) 尺度不變特征檢測；

(2) 特征匹配和索引；

(3) 獨(dú)特性好，信息量豐富；

(4) 高速性；

(5) 可擴(kuò)展性。

利用Sift算法進(jìn)行圖片特征提取，可很好地避免光照強(qiáng)度變化、目標(biāo)遮擋及其他因素干擾對圖片特征的影響。但由于其計(jì)算復(fù)雜度較高，因此，研究選取Surf算法代替Sift算法來提取圖片特征[6]。

Surf算法是Sift算法的一個提升，其借鑒了Sift算法中簡化近似的思想，將DoH中的高斯二階微分方程模板進(jìn)行了簡化，使得模板對圖像的濾波只需要進(jìn)行幾個簡單的加減法運(yùn)算。

在對一幅圖片進(jìn)行特征提取時，Surf算法借助積分圖像原理，首先將目標(biāo)圖像通過高斯二階微分模板濾波，然后轉(zhuǎn)化為對積分圖像的加減運(yùn)算。因?yàn)閳D像由若干個像素點(diǎn)構(gòu)成的，因此，若假設(shè)以左上角為原點(diǎn)構(gòu)建像素坐標(biāo)系，對于圖像中的任意一個點(diǎn)(I,i),其值假設(shè)為ii(I,j)表示為原圖像左上角到點(diǎn)(j,j)相應(yīng)的對角線區(qū)域灰度值的總和，即為：

式中：p(r,c) —— 圖像中點(diǎn)(r,c)的灰度值。

接下來構(gòu)建Hessian矩陣，并將提取的灰度信息生成所有興趣點(diǎn)，用于特征的提取。其Hessian矩陣如下：

式中：f(x,y) —— 圖像函數(shù)。

為了找出當(dāng)前關(guān)鍵位置點(diǎn)，要將圖像f(x,y)經(jīng)過高斯濾波，對圖像信息進(jìn)行提取。其Hessian矩陣為：

圖像信息在經(jīng)過高斯濾波以后，假設(shè)L(x,t)表示在不同解析度下的一幅圖像，可利用高斯核G(t)與圖像函數(shù)I(x)在點(diǎn)x處的卷積來實(shí)現(xiàn)，其卷積計(jì)算公式如下：

L(x,t)=G(t)*I(x,t)

其中高斯核G(t)為：

式中：g(t) —— 高斯函數(shù)；

t—— 高斯方差。

為平衡準(zhǔn)確值與近似值間的誤差，引入權(quán)值。權(quán)值隨尺度變化，則H矩陣判別式可表示為：

det(Happrox)=DxxDyy-(0.9Dxy)2

通過Hessian矩陣可以找出當(dāng)前比周圍其他更亮或者更暗的關(guān)鍵位置點(diǎn)，也就是特征提取[7-8]。

2 哈希快速圖像匹配算法設(shè)計(jì)

哈?？焖賵D像匹配算法是利用感知哈希算法復(fù)雜度低的優(yōu)點(diǎn)，并結(jié)合Surf算法對局部特征及噪聲的敏感性好等優(yōu)點(diǎn)設(shè)計(jì)出的一種新算法，旨在提高圖片搜索速度的基礎(chǔ)上，保證檢索出的圖片的魯棒性。該算法步驟如下：

(1) 歸一化處理：首先將原始圖像進(jìn)行不同角度的旋轉(zhuǎn)以及不同比例縮放后，生成相同的8*8尺寸。

(2) 對生成的圖片進(jìn)行DCT變換，通過設(shè)定閾值將矩陣生成64位的一維向量。

(3) 根據(jù)生成的初步指紋，利用Hamming距離方法，標(biāo)記系列近相似圖片。

(4) 利用Surf算法對標(biāo)記的近相似圖片進(jìn)行特征提取，利用Hamming距離作為相似度度量，找出最近似的圖片[9-11]。

3 實(shí)驗(yàn)結(jié)果分析

在對圖像進(jìn)行分析前，首先對圖像的色彩進(jìn)行提取，找出色彩分布區(qū)域。圖2為目標(biāo)圖像的顏色分布圖。然后利用DCT算法對圖片進(jìn)行整理，得出感知哈希序列指紋。

圖2 目標(biāo)圖像的顏色分布圖

目標(biāo)圖像顏色直方圖見圖3。首先對圖片進(jìn)行分析，得出其顏色分布區(qū)域，然后根據(jù)顏色分布進(jìn)行DCT變換，并根據(jù)圖像信息設(shè)定閾值，通過對閾值的比較生成8*8矩陣，并將其變換成一維64位數(shù)組，并將指紋數(shù)據(jù)以文本格式存放在本地文件中。

經(jīng)過感知哈希算法處理后，便可通過第一次粗篩選。在此基礎(chǔ)上，利用Surf算法對篩選出的圖像信息進(jìn)行二次比較，并利用特征點(diǎn)選取的方法進(jìn)行二次篩選。利用Surf算法對圖片進(jìn)行特征提取示意圖見圖4。利用Surf算法，右面被馬賽克處理過的圖片也被找出特征相似點(diǎn)，從而在本地文件中找出最相似圖片。局部特征點(diǎn)的提取示意圖見圖5。盡管圖像被其他軟件處理，該算法亦能通過排除干擾找出最相似圖片[12]。

圖3 目標(biāo)圖像顏色直方圖

圖4 利用Surf算法對圖片進(jìn)行特征提取

圖5 局部特征點(diǎn)提取示意圖

通過上述比較可知，此次研究中提出的感知哈希算法和Surf結(jié)合算法的時效性與文獻(xiàn)[11]中提出的算法不相上下，唯一不足的就是在利用Surf算法時，由于要提高算法的速度，從而需減少匹配點(diǎn)數(shù)量。另外，本算法在利用雙重定位方法的基礎(chǔ)上，延續(xù)了尺度不變的特性，對于圖像的翻轉(zhuǎn)變換、明暗等變化都有良好的抗噪聲效果，并能夠?qū)⑵錅?zhǔn)確匹配搜索出。

4 結(jié) 語

哈?？焖賵D像匹配算法使用VS2013對圖像進(jìn)行處理編程，在對圖像進(jìn)行處理及編碼指紋提取方面有了很大的改進(jìn)，提高了速度，并且摒棄了哈希算法對局部不敏感等缺點(diǎn)，利用由粗到細(xì)的圖像檢索方法，實(shí)現(xiàn)圖片快速準(zhǔn)確的匹配。通過大量實(shí)驗(yàn)表明，該算法比利用Sift算法速度更快，并且能夠保證圖片的對比精度，快速準(zhǔn)確地找到所需圖片。

[1] YANG B, GU F,NIU X. Block Mean Value Based Image Perceptual Hashing [C] //Proc of IEEE International Conference on IIH-MSP. USA:IEEE,2006:167-172.

[2] XIANG S, KIM H J, HUANG J. Histogram-based Image Hashing Scheme Robust Against Geometric Deformations [C] //Proc of the 9th ACM Workshop on Multimedia and Security. USA: ACM，2007:121-128.

[3] 孫銳，閆曉星，高雋. 基于SIFT和PCA的圖像感知哈希方法[J].電路與系統(tǒng)學(xué)報(bào)，2013，18(1): 274-278.

[4] 杜京義，胡益民，劉宇程. 基于區(qū)域分塊的SIFT圖像匹配技術(shù)研究與實(shí)現(xiàn)[J].光電工程，2013，40(8): 52-58.

[5] MONGA V, EVANS B L. Robust Perceptual Image Hashing Using Feature Point [C]∥Proceedings of IEEE International Conference on Image Processing(ICIP). Singapore: IEEE,2004:677-680.

[6] 趙璐璐，耿國華，李康，等. 基于SURF和快速近似最近鄰搜索的圖像匹配算法[J].計(jì)算機(jī)應(yīng)用研究，2013，30(3): 921-923.

[7] BAY H,TUYTEPLAARS T, VAN G L. Speeded-up Robust Features(SURF)[J]. Computer Vision and Image Understanding,2008,110(3):346-359.

[8] ZAUNER C. Implementation and Benchmarking of Perceptual Image Hash Functions [D] . Upper Austria: Upper Austria University, 2010.

[9] MATTHEW B, DAVID L. Invariant Features from Interest Point Groups[C]. Cardiff: British Machine Vision Conference, 2002(23)：1-10.

[10] 王阿川，陳海濤. 基于離散余弦變換的魯棒感知圖像哈希技術(shù)[J].中國安全科學(xué)學(xué)報(bào)，2009，19(4): 91-96.

[11] 邱麗君，唐加山. 一種快速的兩步驟圖像匹配新算法[J].計(jì)算機(jī)技術(shù)與發(fā)展，2015，25(8): 67-70.

[12] ANGELIS A D, MOSCHITTA A, RUSSO F, et al. Image Quality Assessment: An Overview and Some Metrological Considerations[C]∥International Workshop on Advanced Methods for Uncertainty Estimation in Measurement. Trento: IEEE,2007：47-52.

Fast Image Matching Algorithm Base on Hash

WANGTuoYUXuhongLIUZhijie

(Key Laboratory of Information and Computing Science of Guizhou Province, Guizhou Normal University, Guiyang 550025, China)

Nowadays, data and image update each minute. How to match the image quickly and effectively is the key issue in image matching technology and research. By analyzing the merits of the perceptual hash algorithm and Surf algorithm, this paper proposes a preliminary image search using the perceptual hash algorithm, and then uses Surf algorithm to extract the local characteristics of similar images to determine the most similar images more accurately and increase the robustness for image matching. Experimental results show, when the image is processed, the Hash Fast Image Matching algorithm can still quickly search the most similar images from the local gallery.

perceptual Hash Algorithm; DCT transform; Surf Algorithm; fingerprint Data

2016-11-29

貴州省科學(xué)技術(shù)基金項(xiàng)目“基于Nutch的單位內(nèi)部網(wǎng)絡(luò)智能搜索引擎研究”(黔科合J字LKS[2009]17號)；貴州省經(jīng)濟(jì)和信息化委員會資助項(xiàng)目“大規(guī)模點(diǎn)模型的并行化真實(shí)感實(shí)時渲染技術(shù)研究”(1158號)；貴州省科技廳攻關(guān)項(xiàng)目“海龍囤申報(bào)世界文化遺產(chǎn)關(guān)鍵性技術(shù)研究”(黔科合SY字LKS[2014]3072號)

王拓(1991 — )，男，貴州師范大學(xué)在讀碩士研究生，研究方向?yàn)閳D形圖像處理。

TP391.41

A

1673-1980(2017)03-0075-04