基于Hadoop 的圖像存儲和檢索的研究與實現

徐振濤，林清瀅

（韓山師范學院計算機與信息工程學院，潮州521041）

0 引言

移動互聯網的發展和智能手機的普及，使得圖像數據開始快速增長，無論是圖像存儲還是圖像處理都將面臨著巨大的挑戰，然而，如何實現在大規模的圖像數據中檢索出與目標圖像高度相似的圖像是一個熱門問題。隨著云計算模式的普及和發展，各種云計算平臺也就相繼出現。其中，Hadoop 就是一個開源的云計算平臺，它有兩個核心子項目HDFS 和MapReduce，主要用于對海量數據的分布式存儲和處理，其設計思想來源于Google 的GFS 和MapReduce。

本文首先利用SIFT 算法提取圖像特征，獲得大量圖像特征點。然后利用K-means 算法對圖像特征點進行聚類，降低特征點數量，提高圖像檢索效率。此外，利用TF-IDF 算法對圖像聚類中心進行量化，獲取聚類中心的TF-IDF 值，優化圖像檢索結果。最后利用HDFS 對海量圖像數據進行分布式存儲，利用MapReduce 實現了之前的相關算法。分布式的圖像檢索方法可以大大減少圖像檢索系統所耗費的時間，對分布式圖像檢索的發展有巨大的推動。

1 相關算法

1.1 構建高斯差分金字塔，檢查極值點

金字塔是模仿不同尺度的圖像，大尺度圖像相當于近距離觀察實體的圖像，比較清晰，顯示的是細節信息。小尺度圖像相當于遠距離觀察實體，比較模糊，顯示的是輪廓信息。接著利用不同參數的高斯模板對金字塔的每一層圖像進行模糊處理，使得金字塔的每一層具有多張高斯圖像，金字塔每層的所有圖像被稱為八度。當前八度的底層圖像是前一個八度的倒數第三層圖像，且需要對圖像進行降采樣法。

金字塔層數計算公式如下：

n：金 字 塔 的 層 數；(M,N)：原 圖 像 的 尺 寸；t：log2min( m,n)-1 min( m,n )＞1；(m,n)：頂 端 圖 像 的尺寸；

二維空間正態分布方程公式如下：

m*n：二維模板大小；(x,y)：模板元素；

尺度空間理論的思想是在視覺信息處理模型中引入一個連續變化的尺度參數，獲得不同尺度下的視覺信息，然后綜合這些信息深入地挖掘圖像本質特征[1]。

尺度計算公式如下：

σ：某八度的某層尺度；σ0：初始尺度；o：第幾個八度；s：八度中第幾層S：在高斯差分金字塔的八度中只有S 層能求極值點；O：八度的數量；S+3：高斯金字塔八度的層數；

構建高斯金字塔公式如下：

圖1 高斯金字塔

L( x,y ,σ)：尺度空間；G( x,y ,σ)：高斯函數；I( x,y )：圖像；*：卷積運算；

構建高斯差分金字塔公式如下：

圖2 高斯差分金字塔

根據Lowe 論文，像素點要在三維中比較。因此可知，尺度空間理論中S 表示高斯差分金字塔的八度中只有S 層能求極值點，所以高斯差分金字塔的八度有S+2 層，又因為高斯差分金字塔是由高斯金字塔八度相鄰層相減得到的，所以高斯金字塔的八度有S+3 層。

圖3 像素點在三維中比較

1.2 關鍵點的精確定位，去除低對比度的點，消除邊緣響應

離散空間的極值點不是真正的極值點，如圖4所示。

圖4 離散空間極值點與連續空間極值點的差別

利用已知離散空間極值點插值得到連續空間極值點的方法叫做子像素插值[2]。為了提高關鍵點的穩點性，需要對DOG 函數進行曲線擬合，DOG 函數的泰勒展開式[3]：

對D(X)求導，并令其等于0，可得到極值點的偏移量：

邊緣圖像與二次型函數曲面等高線圖像相對應，其中二次型函數的Hessian 矩陣也可以通過對二次型函數進行偏導數得到，我們只需要判斷該點Hessian 矩陣的特征值是否相差較大，來判斷是否是邊緣點。

該點Hessian 矩陣公式如下：

假設α 為較大特征值，β 為較小特征值，令α=rβ。

成立則保留關鍵點，不成功則剔除。根據Lowe 論文，取r=10。

1.3 特征點方向分配，特征點描述子生成，根據SIFT進行匹配

為了使圖像不受旋轉變化的影響，采用梯度的公式，計算特征點局部窗口的一個基準方向，局部窗口的半徑為3×1.5×σ_oct，公式如下：

利用上述公式計算高斯圖像特征點局部窗口內像素的梯度方向和模值，然后采用梯度方向直方圖進行統計，根據Lowe 論文，梯度模值m( )x,y 需要按σ=0.5σ_oct 進行高斯加權。在特征點領域梯度信息圖像中，縱橫線段表示像素點，圓表示高斯加權范圍。在梯度方向直方圖中，縱坐標表示梯度模值累加，橫坐標表示梯度方向，把360 度分為36 個方向，為了簡化，筆者只畫出8 個方向，實踐編程是以36 個方向。梯度方向直方圖最高柱表示特征點的主方向，大于最高柱80%的柱表示次方向，一個特征點可以有很多個方向，這樣可以提高圖像匹配的穩定性。為了使梯度方向直方圖的方向角更加準確，需要進行插值擬合。

圖5 特征點領域梯度信息和梯度方向直方圖

特征點描述子就是一組向量，將高斯圖像特征點附近領域劃分成4×4 個窗口，計算每個窗口8 個方向的梯度信息，并用梯度方向直方圖進行統計，特征點描述子為128 維向量。

SIFT 算法通過構建高斯金字塔，去除了圖像尺度變化的影響，通過對特征點方向分配以及生成特征點描述子，去除了圖像旋轉變化的影響，通過對特征點描述子向量歸一化處理，去除了圖像光照變化的影響，當使用歐氏距離進行相似度度量時，可去除圖像背景混亂和遮擋物的影響，利用一張圖像的所有描述子向量與另一張圖像的所有描述子向量進行歐氏距離計算，求出最近描述子向量除次近描述子向量的值，當該值小于某個閾值則，則接受這個點。在Lowe 論文中ratio=0.8，然而有人通過大量實驗發現，當ratio=0.4 時，特征點匹配精確度最高，當ratio=0.5 時，特征點匹配一般，ratio=0.8 時，特征點匹配數量最多。

歐氏距離：

特征點p 和q 的描述子向量Desp和Desq。

1.4 K-means算法

圖6 特征點聚類

（1）從N 個元素選取k 個初始聚類中心,如S1、S2。

（2）計算每個元素到每個聚類中心的歐氏距離，如A、B、C 距離S1 最近，則A、B、C 屬于S1 簇集。

（3）求誤差平方和，若誤差平方和與上次相同，則結束，否則進行（4）。

（4）計算簇集的平均值，得到新的聚類中心。

（4）重復（2）～（4）。

1.5 TF-IDF算法

TF-IDF 算法是一種信息檢索和數據挖掘的加權算法，用于評估一個詞語在文件集的類別區分能力，通過SIFT 算法提取圖像特征和K-means 算法對特征點聚類，獲得k 個聚類中心，每個聚類中心可以看作一個詞語，所有圖像看作文件集，計算詞語的TF-IDF 值。

TF（詞頻）：表示詞語在文件中出現的次，需要進行歸一化；IDF（逆向文件頻率）：表示含該詞語的文件數除文件總數，得到的商再取對數。

2 基于Hadoop圖像存儲和檢索

2.1 把大量小文件（圖像）合并成大文件上傳到HDFS

輸入：外部圖像數據

處理：把圖像轉化為＜key,value＞形式，key 是圖像名，value 是圖像內容，每個＜key,value＞為一行，形成總字符串后存入HDFS 中

輸出：一個含義所有圖像且以＜key,value＞形式存儲的文件，即順序文件

2.2 利用MapReduce編寫框架提取圖像特征

IPO 描述

Mapper 類

輸入：HDFS 中順序文件

處理：通過SIFT 算法提取圖像特征

中國英語學習者的實驗在被試所在中學或大學的教師辦公室進行，英語母語者分別在各自所在大學的圖書館中進行，一次僅有一個被試在房間中接受測試。被試首先閱讀實驗要求，然后開始測試。在電腦的自測步速閱讀完成后，被試還要做二語水平測試，并填個人語言背景表。二語水平測試題選自Oxford Proficiency Test，共50道語法選擇題，用以檢測學生的二語語法水平。所有學生均未在之前做過這一測試。語法選擇題每題1分，小于30分被界定為低水平;30～35分為低到中等水平;35分以上為中等以上水平。

輸出：＜key,value＞,key 是圖像名，value 是多個描述子向量，即特征文件

Reducer 類

無

2.2 利用MapReduce編寫框架對特征點進行聚類和聚類中心量化

IPO 描述

Mapper 類

輸入：HDFS 中的特征文件

處理：通過K-Means 算法對特征點聚類，再利用TF-IDF 算法計算聚類中心TF 值

輸出：＜key,value＞，key 是圖像名，value 是多個聚類中心和每個聚類中心的TF 值，即圖像總特征文件

Reducer 類

無

2.3 利用MapReduce編寫框架實現匹配算法

先通過SIFT 算法提取檢索圖像的特征，再通過K-means 算法對特征點聚類，然后把檢索圖像的所有聚類中心存入HDFS 文件中，最后編寫MapReduce 程序進行匹配相似圖像。

IPO 描述

Mapper 類

輸入：HDFS 中圖像總特征文件

處理：通過setup 方法獲取HDFS 中檢索圖像的特征文件，利用歐式距離進行計算檢索圖像與圖像總特征文件中圖像的匹配率

輸出：＜key,value＞，key 是圖像名，value 是匹配率

Reducer 類

無

2.4 實驗結果

圖7 檢索結果

圖8 普通檢索和Hadoop檢索效率對比

圖9 普通檢索和Hadoop檢索準確率

3 結語

在圖像檢索方面，本文首先利用SIFT 算法提取圖像特征，獲得大量圖像特征點。然后利用K-means 算法對圖像特征點進行聚類，降低特征點數量，提高圖像檢索效率。此外，利用TF-IDF 算法對圖像聚類中心進行量化，獲取聚類中心的TF-IDF 值，優化圖像檢索結果。在基于Hadoop 的圖像檢索方面，先采用了HDFS對圖像文件進行分布式存儲，然后基于MapReduce 對圖像進行分布式計算處理。