面向書脊圖像的特征提取與匹配技術研究*

喬 笑 任明武

（南京理工大學計算機科學與工程學院 南京 210094）

1 引言

近年來，隨著科學技術的迅猛發展，圖像匹配技術已成為近代信息處理特別是圖像信息處理領域中的重要技術。尺度不變特征變換（Scale-invariant Feature Transform，SIFT）［1～2］就是圖像匹配領域內的一種用于描述圖像局部特征的算法，被人們廣為使用。由于我們目標圖像是書架上的書脊，存在拍攝圖像與數據庫存儲的書脊圖像，具有尺寸、傾斜方向、拍攝亮度和角度都不一樣的特點，所以我們選擇Sift算法作為特征提取算法。它與其他特征提取算子的區別在于，特征信息具有旋轉不變，尺度不變，亮度不變等特點，并且提取的特征信息量豐富，獨特性好，準確率高。但是SIFT算子具有一個顯著的缺點，就是其算法的復雜度十分高，從而導致提取特征信息的耗時過長，在一些具有實時性要求的應用場景下，不太能滿足要求。隨著時代的發展，之后出現了基于SIFT算子改進的許多變種算法［3～8］，但都存在一些性能問題或者穩定性問題，都不能直接取締SIFT算法。隨著GPU［9～10］處理技術的飛速發展，它具有非常強大的計算能力，提高算法并行能力，從而使得SIFT算法加速成為可能［11～13］。

本文實現了基于統一計算設備架構（Compute Unified Device Architecture，CUDA）［14］下 加 速 的SIFT特征提取算法和特征匹配，并應用于書脊圖像匹配中，使得圖像匹配的實時性得到保證。

2 SIFT特征提取算法

SIFT特征點提取主要分成三大步驟：1）特征點位置定位；2）特征點方向賦值；3）特征點描述。首先為了滿足SIFT算子的尺度不變性，要構造出多種尺度空間下的圖像，例如地圖上的比例尺。比例尺小、觀測點距離景物近、景物更大、細節特征更多；比例尺大、離景物遠、景物更小只能看到宏觀的輪廓特征。尺度不變性就是無論在什么尺度空間觀測，都能夠辨認出目標。

多尺度空間的圖像通常使用高斯金字塔表示形式，如圖1。

圖1 高斯金字塔

圖像金字塔是通過將一張圖像在它的不同的分辨率下的結果組成的。而對于相互緊挨的兩層來說，上一層的圖像是使用下一層的圖像通過降采樣的方式得出的。高斯函數可以對圖像進行卷積操作，從而達到模糊的效果，并且應用互不相同的高斯核，通過計算可以得出模糊度不一樣的圖像組，由這些圖像組進而可以形成一張圖像的高斯尺度空間，具體公式如式（1）所示：

其中，式（1）中G(x,y,σ)是高斯核函數，具體的高斯核函數見公式如式（2）。

σ代表尺度空間因子，它的意義在于表示高斯正態分布的標準差。我們可以控制這個值來讓控制圖像被模糊化的程度。如果它的值越大，則代表圖像被模糊的程度越大，相對應的尺度也就越大。L(x,y,σ)就代表著圖像的高斯尺度空間。

構建完圖像的多尺度空間后，要進行特征點的檢測，科學家經過研究認為LoG［15～17］算子是提取圖像特征的效果較好的算子，它的原理是通過高斯濾波去除噪聲影響，然后提取圖像邊緣最強的點作為特征點，這也符合生活中線條輪廓越粗、顏色越分明的物體越容易被看清和辨別的規律。雖然使用LoG算子可以更加好地檢測出圖像中存在的特征點，但是它的計算量也非常大，所以一般使用差分高 斯（Difference of Gaussina，DoG）來 近 似 計 算LoG。設k為相鄰兩個高斯尺度空間的比例因子，則DoG的定義如式（3）：

由上述公式可以推斷，將兩幅相鄰的高斯空間圖像相減，即可得到狗的高斯差分圖像。在SIFT算法中，需要提取的特征點是差分圖像中的極值點。為了找到這些尺度空間中的所有極值點，必須將圖片上的每個像素與其圖像域和尺度域中的所有相鄰點進行比較。當像素值大于或小于所有相鄰點時，這就是一個極值點。極值點比較示意圖如圖2所示，中間的監測點，要在其圖像域與3×3個鄰域的8個像素點進行比較，并且在尺度域中要與上下兩側的3×3領域18個像素點進行比較。

圖2 相鄰尺度域和圖像域示意圖

通過以上步驟，在不同的尺度上找到了所有的特征點。接下來，為了實現算法的圖像旋轉不變性，需要對檢測到的特征點的方向進行分配。方向參數由特征點場中像素的梯度分布確定，然后利用圖像的梯度直方圖得到關鍵點局部結構的穩定方向。通過這個特征點，就可以找到該特征點的尺度σ，也就是可以得到該特征點所屬于的尺度圖像。接著計算以特征點為中心、以3×1.5σ為半徑的區域圖像的幅角和幅值，每個點L(x,y)的梯度的模m(x,y)以及方向θ(x,y)可以通過式（4）和式（5）求得：

經過以上所有步驟，就可以找到SIFT特征點的位置、尺度和方向信息。下一個任務是使用一組向量來描述這些關鍵點。這一步一般稱為生成特征點描述符。該描述符不僅包含特征點，還包含對它們有貢獻的特征點周圍的像素。為了保證匹配的準確性，描述符必須具有高度的獨立性。生成特征描述子的步驟一般包括三個步驟，如下所示。

1）校正旋轉主方向，確保旋轉不變性；

2）生成描述子，最終形成一個128維的特征向量；

3）為了去掉光照不均對特征點的影響，進行對特征向量長度進行歸一化操作。

3 基于CUDA的SIFT特征提取

3.1 CUDA架構簡介

CUDA［18］架構主要是針對具有大規格并行計算需求的問題的解決方案。在具有大量異構計算并且具有復雜性資源的領域問題下，使用CUDA架構是否有益。在該架構下，一般CUDA程序構架又兩大部分組成：主機端和設備端。通常來說，主機端一般指的是CPU，而設備端一般指的是GPU。只有遇到需要并行計算任務時，才會放入GPU中執行，其他一般都在CPU上執行。遇到了并行任務，CUDA框架就會把該任務編譯成GPU能夠識別運行的程序，此程序在CUDA框架里稱做核（kernel）。在實際計算的過程中，主機端控制臺會根據需要計算的任務進行分類，將一些需要并行計算的任務與其相關數據拷貝到顯存中，另一些邏輯計算的任務則留在主機端設備進行運算。需要并行計算的任務由顯卡設備控制進行計算，等并行計算任務完成后，顯卡設備會將計算結果送回主機端的存儲中，并用于下一次計算輸入。

1）線程層次模型

在GPU中所執行的線程具體結構如圖3所示。它們一共有三種不同的類型，分別為一維、二維和三維。線程格（grid）常用于表示具有相同維度類型和存儲大小的線程塊組成。在相同的線程格內的線程具有高效的協作效率，數據通信十分方便快捷，它們擁有相同的指令地址，所以不僅可以并行地進行執行任務，而且還可以通過一些共享存儲器來共享它們的數據，并同步其執行來協調存儲器訪問。CUDA框架中有一個非常經典的線程模型，指的是不需要進行通信的任務部分一般以線程塊劃分，而需要進行通信的任務，將它設計到同一個線程塊，這樣的話，任務之間通信會非常高效。所以一般設計并行計算任務時，會將一大塊任務根據相關性分成可以獨立并行計算的子任務，接著繼續劃分下去，變成一塊塊更小的子任務，它們之間可以進行通信來解決問題，這樣就可以提高程序的并發度。

圖3 CUDA線程層次結構示意圖

2）存儲器層次模型

CUDA設備中一般擁有多種類型獨立的存儲空間，其存儲空間的基本結構如圖4所示，它們的存儲功能都不一樣。在應用程序里，每個線程塊都擁有一大塊共享存儲器，該存儲器提供給塊內的線程使用。除了這個共享的存儲器，每個線程還擁有獨立的存儲器，除了自己可以控制讀寫，其他線程沒有訪問權限。由于共享存儲器位于多處理器的內部，所以訪問它的速度非常快，與寄存器差不多。在執行并行計算任務時，如何對數據有大量的讀寫需求，就可以使用共享存儲器資源來完成。還有一種類型存儲器，就是全局存儲器，該類型的儲存器不管什么線程都有權限使用它，對存儲在該類型的存儲器中的數據，可以之間訪問與讀寫，十分方便。最后兩種類型則是常量存儲器與紋理存儲器，它們只能提供線程只讀的操作，并且只讀的速率非常迅速。

圖4 存儲空間結構示意圖

3.2 SIFT算法的可并行度分析

可并行度一般用于表示算法中可通過并行計算設計的任務占全部的計算任務的比例。在本文中，測量尺度使用時間來進行分析。假設，該算法全部串行執行一共所需要的時間記為c，而其中可以通過并行方式實現的部分執行時間記為b，如果同時使用m個處理器對它們進行加速優化處理，只在最理想的情況下考慮，那么并行加速后，該算法可以被最大化提高的倍速為T，具體計算公式如式（6）：

這個最大的提高倍速是可以達到的上限。

根據上述對可并行度概念的描述可知，通過這樣一個公式可以得出任何算法的實現是否還存在有提升的余地，并且可以預估出被提高的最大倍速。對于本節的算法下，SIFT算法的主要步驟有構造多尺度空間、檢測并定位關鍵點、賦予關鍵點方向和關鍵點描述子的計算。

構建多尺度空間的主要過程是對輸入圖像進行灰度和下采樣，然后計算每組的組內尺度和各層尺度，最后生成高斯尺度空間和微分尺度空間。上述步驟中，可以通過并行計算實現的部分包括高斯尺度空間的生成和微分尺度空間的生成。需要標準實現的部分包括圖像灰度化、下采樣、各層尺度和組內尺度的計算。

賦予關鍵點方向和關鍵點描述子的計算，都是可以通過并行計算實現加速的。最終分析的并行化結果如圖5所示。

圖5 SIFT算法的可并行度示意圖

4 實驗與結果

本文的應用場景，是面向智能書柜的書脊圖像特征匹配，重點在于快速根據書柜上的書脊圖像，與之前已經構建好的書脊圖像庫中每本書脊，進行匹配，快速匹配出每次減少的書本。在這種場景下，對于匹配的算法，既要求有很高的準確率，又有速度上面的要求。所以基于CUDA的SIFT算法，正好滿足這些要求。

本文中所用的實驗環境都一致，具體配置如表1所示。實驗中，將本文的算法與標準的SIFT算法［19～20］，在特征提取和特征匹配執行效率上做比較。

表1 計算機軟硬件配置

在特征點提取的實驗中，圖6是使用CPU方法和GPU方法分別對四張不同分別率的書脊圖像，實現的SIFT特征點提取效果圖。圖6（a）、（c）、（e）和（g）是在CPU環境下提取的特征點圖，而圖（b）、（d）、（f）和（h）則是在GPU環境提取的，發現GPU實現的算法提取的特征點比CPU實現稍微多一些，在CPU提取出來特征點，絕大部分GPU也提取出來了。

圖6 GPU與CPU SIFT特征點提取效果圖

如表2則展示是每張圖CPU和GPU提取的特征數和公共特征數。由表中數據可知，在4張圖特征提取的結果中，公共提取的特征點占CPU提取的總特征點約95%，也就是說GPU提取的特征點幾乎包含了所用CPU提取的特征點。在使用相同算法參數下，GPU比CPU普遍提取更多的特征點。根據分析實驗結果，大致有兩種因素造成CPU和GPU這兩種實現關于特征點定位精度之間的差異。

表2 GPU與CPU公共SIFT特征點數對比

1）為了讓計算任務更加快速的進行，在具體GPU實現時，采用了大量的CUDA框架下加速庫，使用這些庫函數會帶來精度上損失。

2）在構建高斯金字塔的過程中，高斯函數存在大量的加乘計算，并且這個加乘計算的誤差會累積到下一層中，所以會導致精度上的差異。

雖然存在一些精度上損失，但在大量的特征點中比例還是很小的，對總體算法的可行性沒有太大的影響。所以GPU實現的SIFT特征點提取具有和CPU實現的算法一樣的可靠性和可行性。

在特征匹配實驗中，實驗數據共包含四張書籍圖片，分辨率分別為51×617，1440×1080，94×592，1440×1080，圖7（a），圖7（c）為待匹配書脊圖像，圖7（b）、圖7（d）為搜索圖像。

圖7 待匹配書籍圖像

實驗中，算法的參數設置如下：差分金字塔的層數由分辨率確定，每組層數為5，特征點主方向分配在高斯平滑參數σ為1.6。CPU環境下，特征匹配算法使用的是基于KD樹的近似最近鄰算法匹配。而GPU環境下，則使用的是直接暴力搜索高維向量進行匹配。

從上述表3實驗對比和圖8實驗結果中，可以看出CPU和GPU環境下提取的特征點數量差不多，最終匹配的特征點，CPU環境下略多一些，這可能是由于GPU中浮點運算精度導致的。盡管GPU環境下，使用暴力匹配算法，但最終算法的運行時間是CPU環境下的幾倍。

表3 本文算法與標準SIFT實驗結果對比

圖8 匹配結果

5 結語

本文使用在CUDA框架下實現的SIFT加速算法解決CPU下SIFT算法時間長問題。為了更好更快地實現CUDA框架下的SIFT算法，先分析了該算法的可并行度。在該算法的可靠性和效率性方面，本節對CPU和GPU兩種環境下實現的SIFT算法，在特征提取與特征匹配實驗結果進行分析與對比。根據實驗結果，發現GPU環境下不僅具有可靠性，并且還有更高的效率，提高了該算法的實時性，使應用層面變得更加廣泛。

對于智能書柜這個場景，實時性十分重要。所以此基于CUDA框架下實現的SIFT算法，具有適用性，為用戶帶來極速的用戶體驗。