基于顏色方差的圖像相似檢索算法研究*

尹玉梅，彭 藝，祁俊輝

（昆明理工大學(xué) 信息工程與自動(dòng)化學(xué)院，云南 昆明 650000）

0 引 言

圖像相似檢索指對(duì)指定圖像進(jìn)行相似圖像的匹配工作，是圖像處理領(lǐng)域的一項(xiàng)綜合研究。特別是隨著互聯(lián)網(wǎng)時(shí)代的發(fā)展，圖像數(shù)據(jù)愈來(lái)愈多，圖像相似檢索被廣泛應(yīng)用于目標(biāo)識(shí)別、照片過濾等場(chǎng)景。

2001年，Ton Kalker[1]等人提出感知哈希（Perceptual Hashing）的概念，并吸引了很多學(xué)者[2-4]。后期也有很多學(xué)者對(duì)其進(jìn)行了改進(jìn)工作，如Swaminathan A[5]等人提出一種基于圖像邊緣的感知哈希算法；張慧[6]、趙玉鑫[7]等人基于小波變換對(duì)其進(jìn)行改進(jìn)，提出了一種結(jié)構(gòu)化數(shù)字簽名的方法；Khelifi F[8]等人提出了一種基于分塊灰度直方圖的感知哈希算法，建議挑選圖像塊的灰度統(tǒng)計(jì)屬性，如均值、方差，生成感知哈希序列。近幾年，也出現(xiàn)了類似于差異值哈希（Deference Hash）的算法，如黃嘉恒[9]等人針對(duì)多種哈希算法進(jìn)行對(duì)比工作；李雨佳[10]等人對(duì)感知哈希中DCT矩陣進(jìn)行改進(jìn)；宋博[11]等人將快速特征提取方法與感知哈希相結(jié)合，以提升執(zhí)行效率。不僅如此，干麗萍[12]、王寧邦[13]、魏輝[14]、張洪帥[15]等人還將感知哈希應(yīng)用于作業(yè)相似檢測(cè)、資產(chǎn)圖片核對(duì)、艦船圖片相似度檢索、場(chǎng)景分類等領(lǐng)域。

就目前大部分圖像相似檢索算法而言，多數(shù)是對(duì)圖像進(jìn)行壓縮、量化等工作提取圖像的特征，進(jìn)而比較圖像之間的差異。針對(duì)均值哈希算法而言，在對(duì)圖像進(jìn)行處理時(shí)，往往會(huì)造成圖像內(nèi)容信息嚴(yán)重丟失、圖像特征難以區(qū)分等情況?；诖?，本文考慮到一行數(shù)據(jù)或一列數(shù)據(jù)的波動(dòng)程度可以用方差表示，為盡可能提高圖像相似檢索的準(zhǔn)確性，提出了顏色方差算法。

1 均值哈希算法介紹

均值哈希算法（Average Hash，AHash）是一種相似性距離度量方法，主要用來(lái)處理相似圖像的檢索工作。均值哈希通常將圖像按照一定規(guī)則生成Hash值，針對(duì)不同圖像計(jì)算其Hash值確定是否相似。

算法1：均值哈希算法

輸入：圖像X。

輸出：圖像X的AHash值A(chǔ)HashX。

步驟1：將圖像X的大小壓縮至M×M，通常令M=8；

步驟2：將壓縮后的圖像X轉(zhuǎn)化為256階灰度圖像，并表示為矩陣形式IX，其中IX(i, j),i∈[1,M],j∈[1,M]為矩陣元素值；

步驟3：通過式（1）計(jì)算矩陣IX的元素平均值uX；

步驟4：根據(jù)式（2）生成新矩陣TX，其中TX(i, j),i∈[1,M], j∈[1,M]為矩陣元素值；

步驟5：將矩陣TX按照從上至下（i=1→M）、從左至右（j=1→M）的規(guī)則，連接生成圖像X的AHash 值 AHashX。

通常，由算法1將圖像生成AHash值后存儲(chǔ)至數(shù)據(jù)庫(kù)中，在進(jìn)行相似圖像檢索時(shí)，只需計(jì)算圖像的AHash值之間海明距離，即可確定圖像之間是否相似。

2 顏色方差算法介紹

雖然均值哈希算法使用時(shí)非常簡(jiǎn)便，但在實(shí)踐中往往達(dá)不到預(yù)有的效果。究其原因，根本原因有兩點(diǎn)：

（1）該算法需將圖像的大小壓縮至M×M（通常令M=8），在進(jìn)行平均值對(duì)比時(shí)會(huì)造成圖像內(nèi)容信息嚴(yán)重丟失；

（2）該算法基于海明距離判斷圖像之間是否相似，若生成的AHash值長(zhǎng)度較短，則圖像特征將難以區(qū)分。

基于此，考慮到一行數(shù)據(jù)或一列數(shù)據(jù)的波動(dòng)程度可以用方差表示，為盡可能提高圖像相似檢索的準(zhǔn)確性，提出了顏色方差算法。

算法2：顏色方差算法

輸入：圖像X。

輸出：圖像X的橫向方差向量Varc-X、縱向方差向量Varl-X。

步驟1：將圖像X的大小壓縮至M×M，通常令M=8；

步驟2：將壓縮后的圖像X轉(zhuǎn)化為256階灰度圖像，并表示為矩陣形式IX，其中IX(i, j),i∈[1,M],j∈[1,M]為矩陣元素值；

步驟3：通過式（3）計(jì)算矩陣IX的行元素平均值uc-X(i),i∈[1,M]、列元素平均值ul-X( j), j∈[1,M]；

步驟4：將矩陣按照從左至右（j=1→M）的規(guī)則，根據(jù)式（4）進(jìn)行方差計(jì)算，得到矩陣IX的橫向方差向量Varc-X，其中Varc-X( j), j∈[1,M]為向量元素值；

步驟5：將矩陣按照從上至下（i=1→M）的規(guī)則，根據(jù)式（5）進(jìn)行方差計(jì)算，得到矩陣IX的縱向方差向量Varl-X，其中Varl-X( i),i∈[1,M]為向量元素值。

通常，由算法2將圖像生成橫向方差向量、縱向方差向量后存儲(chǔ)至數(shù)據(jù)庫(kù)中，在進(jìn)行相似圖像檢索時(shí)，只需通過向量距離度量方法計(jì)算圖像的橫向方差向量、縱向方差向量之間距離，即可確定圖像之間是否相似。

算法3：相似度量算法

輸入：圖像A、B的橫向方差向量Varc-A、Varc-B和縱向方差向量Varl-A、Varl-B。

輸出：圖像A、B的相似度Sim(A,B)。

步驟1：通過式（6）計(jì)算圖像A、B之間基于橫向方差向量的相似度Simc(A,B)；

步驟2：通過式（7）計(jì)算圖像A、B之間基于縱向方差向量的相似度Siml(A,B)：

步驟3：通過式（8）對(duì)基于橫向方差向量的相似度Simc(A,B)和基于縱向方差向量的相似度Siml(A,B)進(jìn)行整合歸一，得到圖像A、B的相似度Sim(A,B)。

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

為驗(yàn)證本文提出的基于顏色方差的圖像相似檢索算法的準(zhǔn)確性、有效性、適應(yīng)性以及效率性，本文設(shè)計(jì)了以下實(shí)驗(yàn)。實(shí)驗(yàn)的主要目的在于通過與對(duì)現(xiàn)有其他算法的比較，考察本算法對(duì)圖像相似檢索的有效性、準(zhǔn)確性、效率性以及本算法是否能夠更準(zhǔn)確、完整地檢索所有相似圖像。

3.1 實(shí)驗(yàn)數(shù)據(jù)

實(shí)驗(yàn)采用10 000張大小為256×256、各不相同的鮮花圖像作為基準(zhǔn)圖，在其右下角分別加上如表1所示的水印生成水印圖，共計(jì)70 000張圖像，并編號(hào)為1～70 000，其中1～10 000為原圖。

為驗(yàn)證方便，實(shí)驗(yàn)數(shù)據(jù)中編號(hào)為i的圖像，其生成的水印圖編號(hào)為10 000q+i,q∈[1,6]，且算法2中設(shè)置圖像壓縮大小M=8。編號(hào)為1的圖像及其加水印生成的相似圖像如圖1所示。

表1 水印信息

3.2 實(shí)驗(yàn)過程

實(shí)驗(yàn)采用編號(hào)為1～10 000的圖像進(jìn)行相似圖像的檢索，遍歷數(shù)據(jù)庫(kù)中所有圖像得到結(jié)果，并與傳統(tǒng)的均值哈希算法（AHash）、感知哈希算法（PHash）、差異值哈希算法（DHash）等進(jìn)行對(duì)比，考察本算法對(duì)圖像相似檢索的有效性、準(zhǔn)確性、效率性以及本算法是否能夠更準(zhǔn)確、完整地檢索所有相似圖像。實(shí)驗(yàn)結(jié)果如表2所示，其中“檢索出相似圖像的個(gè)數(shù)”指對(duì)相似度進(jìn)行從大至小排序后，前20張圖像中所包含的正確相似水印圖像的個(gè)數(shù)，錯(cuò)誤相似水印圖像不計(jì)入內(nèi)。

圖1 編號(hào)為1的圖像及其加水印生成的相似圖像

由于測(cè)試數(shù)據(jù)較大，取樣本編號(hào)為1～100的實(shí)驗(yàn)樣本繪制折線圖，其檢索出相似圖像的個(gè)數(shù)對(duì)比圖及運(yùn)行時(shí)間對(duì)比圖分布如圖2、圖3所示。

從圖2可以直觀看出，本算法檢索出的相似圖像個(gè)數(shù)明顯比均值哈希算法（AHash）、感知哈希算法（PHash）、差異值哈希算法（DHash）更完整，具體檢索完整性應(yīng)為“本算法＞感知哈希算法＞差異值哈希算法＞均值哈希算法”。結(jié)合表2數(shù)據(jù)及圖3可知，本算法的平均運(yùn)行時(shí)間為1.329 3 s，而均值哈希算法（AHash）、感知哈希算法（PHash）、差異值哈希算法（DHash）的平均運(yùn)行時(shí)間分別為1.781 8 s、2.700 7 s及0.750 8 s。雖然四種算法的時(shí)間復(fù)雜度均為O(N)，但具體運(yùn)行時(shí)間應(yīng)為“差異值哈希算法＞本算法＞均值哈希算法＞感知哈希算法”。

綜合實(shí)驗(yàn)結(jié)果說(shuō)明，本算法的執(zhí)行效率較均值哈希算法提升了25.4%左右，且檢索完整性比均值哈希算法、感知哈希算法、差異值哈希算法都要高。

表2 實(shí)驗(yàn)所得結(jié)果

圖2 本算法與傳統(tǒng)AHash/PHash/DHash算法檢索出相似圖像的個(gè)數(shù)對(duì)比

圖3 本算法與傳統(tǒng)AHash/PHash/DHash算法運(yùn)行時(shí)間對(duì)比

4 結(jié) 語(yǔ)

文中針對(duì)均值哈希算法中存在的圖像內(nèi)容信息嚴(yán)重丟失、圖像特征難以區(qū)分等造成的檢索準(zhǔn)確度不高的情況，提出了基于顏色方差的圖像相似檢索算法。算法分別對(duì)行元素、列元素進(jìn)行灰度值方差求解，生成圖像的橫向方差向量和縱向方差向量，再通過余弦定理對(duì)其進(jìn)行相似度計(jì)算。

實(shí)驗(yàn)結(jié)果表明，該算法在圖像相似檢索中執(zhí)行效率較均值哈希算法提升了25.4%左右，且較均值哈希算法、感知哈希算法、差異值哈希算法能夠更準(zhǔn)確、完整地檢索所有相似圖像，具體檢索完整性為“本算法＞感知哈希算法＞差異值哈希算法＞均值哈希算法”，運(yùn)行效率為“差異值哈希算法＞本算法＞均值哈希算法＞感知哈希算法”。