汪善義，馬 煜* ，汪源源

1．復(fù)旦大學(xué)專用集成電路與系統(tǒng)國(guó)家重點(diǎn)實(shí)驗(yàn)室(上海，200433)

2．復(fù)旦大學(xué)電子工程系(上海，200433)

基于SIFT特征和近似最近鄰算法的醫(yī)學(xué)CT圖像檢索

汪善義1，2，馬 煜1，2*，汪源源2

1．復(fù)旦大學(xué)專用集成電路與系統(tǒng)國(guó)家重點(diǎn)實(shí)驗(yàn)室(上海，200433)

2．復(fù)旦大學(xué)電子工程系(上海，200433)

針對(duì)醫(yī)學(xué)X線計(jì)算機(jī)斷層(Computed Tomography，CT)圖像，提出了一種基于尺度不變特征變換(Scale Invariant Feature Transform，SIFT)特征和近似最近鄰算法的檢索方法。首先通過(guò)SIFT算法得到圖像的特征點(diǎn)和相應(yīng)的特征向量，再采用近似最近鄰算法進(jìn)行SIFT特征向量的匹配搜索，得到數(shù)據(jù)庫(kù)中與參考圖像最相似的圖像序列。實(shí)驗(yàn)結(jié)果表明，該法能檢索到與目標(biāo)圖像細(xì)節(jié)相符的結(jié)果，大大提高了檢索速度。與傳統(tǒng)的基于紋理的檢索方法相比，查準(zhǔn)率和檢索結(jié)果與目標(biāo)圖像的相似程度方面更佳，符合醫(yī)學(xué)CT圖像檢索的要求。

圖像檢索，CT圖像，SIFT特征，近似最近鄰算法

0 引言

隨著計(jì)算機(jī)斷層(Computed Tomography，CT)成像技術(shù)的發(fā)展和普及，對(duì)大規(guī)模的CT醫(yī)學(xué)圖像數(shù)據(jù)庫(kù)進(jìn)行有效地管理和檢索，在臨床診斷和治療中具有重要意義。目前，基于內(nèi)容的圖像檢索(Content Based Image Retrieval，CBIR)［1］技術(shù)彌補(bǔ)了傳統(tǒng)的基于文本檢索(Text Based Image Retrieval，TBIR)的不足，在醫(yī)學(xué)圖像的輔助診斷中具有更好的應(yīng)用前景，近年來(lái)也取得了一些較好的應(yīng)用［2］。

在典型的CBIR系統(tǒng)中，對(duì)于待檢索的目標(biāo)圖像和圖像庫(kù)中的圖像，需要提取各自的特征形成特征向量。通過(guò)在特征空間中進(jìn)行快速的匹配搜索來(lái)判斷圖像間的相似度，從而返回相似度最高的一組圖像序列作為檢索結(jié)果。用于檢索的傳統(tǒng)特征有灰度統(tǒng)計(jì)信息，紋理，形狀等，其中用于表述圖像細(xì)節(jié)的主要是紋理特征。這些特征本身對(duì)圖像內(nèi)容的刻畫(huà)描述能力將很大程度上影響圖像檢索的性能。尺度不變特征變換(Scale Invariant Feature Transform，SIFT)算法［3，4］產(chǎn)生的特征向量作為一種局部特征描述算子，獨(dú)特性好，信息量豐富，對(duì)旋轉(zhuǎn)、尺度變換、視角改變、噪聲等具有較強(qiáng)的魯棒性，能很好地應(yīng)用于基于內(nèi)容的圖像檢索中［5］。但由于SIFT特征向量是高維向量，其匹配過(guò)程相當(dāng)于高維空間中的最近鄰搜索問(wèn)題，對(duì)于大規(guī)模數(shù)據(jù)庫(kù)中的檢索，計(jì)算量太大。為解決這一問(wèn)題，可以采用一些優(yōu)化的搜索算法來(lái)提高速度。

本文提出了一種基于SIFT特征的醫(yī)學(xué)X線CT圖像檢索方法，并采用基于隨機(jī)KD樹(shù)、分層K均值樹(shù)的近似最近鄰(Approximate Nearest Neighbor，ANN)搜索算法，在不顯著降低匹配精度的情況下，提高SIFT特征向量匹配搜索的速度。實(shí)驗(yàn)結(jié)果表明，該方法能較好地應(yīng)用在醫(yī)學(xué)CT圖像檢索中，與傳統(tǒng)的基于紋理的方法相比具有更好的效果。

1 SIFT特征提取和匹配

1．1 SIFT 特征提取

SIFT特征提取主要分為以下四個(gè)步驟:尺度空間極值點(diǎn)的檢測(cè)，特征點(diǎn)位置的確定，特征點(diǎn)主方向的提取，特征描述子的生成。

1．1．1 尺度空間極值點(diǎn)的檢測(cè)

為獲得尺度不變性，SIFT算法在尺度空間中查找極值點(diǎn)。對(duì)于二維圖像I(x，y)，在不同尺度下的表示，記為L(zhǎng)(x，y，σ)，可由圖像與高斯核卷積得到:

其中σ為尺度空間因子，*為卷積運(yùn)算，G(x，y，σ)為尺度可變的高斯函數(shù):

為了得到尺度不變的特征點(diǎn)，SIFT算法使用了高斯差分(Difference of Gaussian，DoG)尺度空間。通過(guò)對(duì)圖像進(jìn)行尺度增量式的高斯卷積，建立一個(gè)高斯圖像金字塔，再將高斯空間中同一組的相鄰兩層相減得到高斯差分金字塔。即:

其中，D(x，y，σ)為差分尺度空間函數(shù)，k為尺度因子的常量系數(shù)。

為了使特征點(diǎn)具有較好的獨(dú)特性和穩(wěn)定性，SIFT算法在圖像的二維平面空間和DoG尺度空間中同時(shí)檢測(cè)局部極值點(diǎn)。每個(gè)采樣點(diǎn)需要和它的所有相鄰點(diǎn)(共26個(gè)點(diǎn))進(jìn)行比較，包括同尺度的8個(gè)相鄰點(diǎn)和上下相鄰尺度對(duì)應(yīng)的9×2個(gè)點(diǎn)，以確保在尺度空間和二維圖像空間都檢測(cè)到極值點(diǎn)。

1．1．2 特征點(diǎn)位置的確定

為了精確定位極值點(diǎn)，SIFT算法通過(guò)DoG函數(shù)的二階Taylor展開(kāi)式來(lái)得到特征點(diǎn)位置和尺度坐標(biāo)的精確值。D(x，y，σ)在局部極值點(diǎn)(x0，y0，σ0)處的泰勒展開(kāi)式為:

其中，x=(x，y，σ)T表示采樣點(diǎn)和特征點(diǎn)之間的位置、尺度偏移量。

同時(shí)，SIFT算法對(duì)低對(duì)比度的候選點(diǎn)和邊緣相應(yīng)點(diǎn)進(jìn)行過(guò)濾，以增強(qiáng)匹配的穩(wěn)定性，并提高抗噪聲能力。

1．1．3 特征點(diǎn)主方向的提取

為消除因?yàn)樾D(zhuǎn)變換而產(chǎn)生的不一致，SIFT算法計(jì)算出每個(gè)特征點(diǎn)的主方向，并使特征向量建立在主方向上。特征點(diǎn)的梯度幅值和方向的計(jì)算公式為:

其中，m(x，y)為梯度模值，θ(x，y)為梯度方向。

得到主方向以后，在特征點(diǎn)的鄰域進(jìn)行采樣，統(tǒng)計(jì)梯度方向直方圖。梯度方向直方圖中，每10°分為一個(gè)格子，再將鄰域內(nèi)的每個(gè)采樣點(diǎn)按梯度方向歸入適當(dāng)?shù)母褡樱蕴荻鹊姆底鳛槠湄暙I(xiàn)的權(quán)重。再選擇直方圖中的主峰值作為特征點(diǎn)的主方向，如果有峰值達(dá)到主峰值80%以上，則作為輔方向。一個(gè)特征點(diǎn)可以具有多個(gè)方向，這樣可以增強(qiáng)特征點(diǎn)匹配時(shí)的魯棒性。

1．1．4 特征描述子的生成

首先將坐標(biāo)軸旋轉(zhuǎn)為特征點(diǎn)的方向，以確保匹配時(shí)的旋轉(zhuǎn)不變性;再以特征點(diǎn)為中心取16×16的鄰域作為采樣窗口，并對(duì)該區(qū)域內(nèi)的采樣點(diǎn)進(jìn)行高斯加權(quán)以增強(qiáng)穩(wěn)定性;再將這個(gè)區(qū)域分為16個(gè)小塊，小塊的大小為4×4。計(jì)算每個(gè)小塊內(nèi)的8個(gè)方向的梯度方向直方圖，統(tǒng)計(jì)每個(gè)方向的累加值，用這來(lái)表示該小塊，并稱之為一個(gè)種子點(diǎn)。由于在采樣窗口中共有16個(gè)種子點(diǎn)，而每個(gè)種子點(diǎn)有8個(gè)方向，這就得到了128維的SIFT特征向量。

此時(shí)得到的SIFT特征向量已經(jīng)去除了尺度變化、旋轉(zhuǎn)等幾何形變因素的影響。為了進(jìn)一步減少光照或圖像灰度變化的影響，最后得到的特征向量需要?dú)w一化。

1．2 SIFT特征點(diǎn)匹配

SIFT特征點(diǎn)的匹配采用特征向量的歐氏距離作為相似性判斷度量。特征點(diǎn)p和q的特征向量分別記為Dp和Dq，則d(p，q)為Dp和Dq的歐氏距離:

其中，符號(hào)〈·〉表示內(nèi)積。由于Dp和Dq是幅值歸一化的，即:〈Dp，Dp〉=1，〈Dq，Dq〉=1，該歐氏距離可以通過(guò)兩者的內(nèi)積來(lái)得到:

對(duì)于圖像A中的任意特征點(diǎn)a，在圖像B中與它具有最小歐氏距離的兩個(gè)特征點(diǎn)b1，b2稱為最近鄰和次近鄰。通過(guò)查找每個(gè)特征點(diǎn)的最近鄰和次近鄰，再按距離比率準(zhǔn)則來(lái)判斷匹配是否成立［3］。只有當(dāng)d(a，b1)和d(a，b2)的比值小于預(yù)設(shè)的閾值時(shí)才接受d(a，b1)為一對(duì)匹配點(diǎn)。

2 最近鄰及近似最近鄰算法

SIFT特征點(diǎn)匹配實(shí)際上要解決特征向量的最近鄰搜索(Nearest Neighbor，NN)問(wèn)題，即在D維的度量空間RD中，給定一個(gè)包含n個(gè)點(diǎn)的數(shù)據(jù)集合S?RD，對(duì)于一個(gè)給定的一個(gè)查詢點(diǎn)q，q∈RD，從S中尋找與q的度量距離最近的點(diǎn)［6］。最近鄰搜索在模式識(shí)別與分類、數(shù)據(jù)挖掘、機(jī)器學(xué)習(xí)等領(lǐng)域有著非常廣泛的應(yīng)用。而k－近鄰搜索(k－Nearest Neighbors，k－NN)則是在空間RD中，查找出k個(gè)與查詢點(diǎn)q最為接近的數(shù)據(jù)點(diǎn)。當(dāng)k為1時(shí)，得到的就是查詢點(diǎn)的最近鄰。

但在檢索中，對(duì)于大規(guī)模數(shù)據(jù)庫(kù)，這種最近鄰搜索的計(jì)算量太大。為解決這一問(wèn)題，可以采用近似最近鄰搜索(Approximate Nearest Neighbor，ANN)算法。ANN算法并不直接得到最近鄰值，而是在搜索中返回對(duì)最近鄰的估計(jì)。對(duì)于大多數(shù)情況，能夠得到實(shí)際上的最近鄰。相對(duì)于最近鄰的窮舉搜索法，采用ANN算法可以在不顯著降低匹配精度的情況下，降低算法的復(fù)雜度，速度相比準(zhǔn)確搜索有數(shù)量級(jí)上的提高［7］。

為了實(shí)現(xiàn)近似搜索，ANN算法往往基于一些數(shù)據(jù)結(jié)構(gòu)，如:KD樹(shù)，測(cè)度樹(shù)，spill樹(shù)，K均值樹(shù)等［6，8～10］。文獻(xiàn)［7］對(duì)一些相關(guān)的算法進(jìn)行了比較，發(fā)現(xiàn)對(duì)于多數(shù)的數(shù)據(jù)庫(kù)，采用分層K均值樹(shù)和多重隨機(jī)KD樹(shù)具有較好的性能。在實(shí)驗(yàn)中，對(duì)于所采用的圖像數(shù)據(jù)庫(kù)規(guī)模，基于這兩種結(jié)構(gòu)的ANN算法具有較好的性能，顯著提高了SIFT特征向量匹配搜索的速度。

3 灰度直方圖預(yù)篩選法

對(duì)于CT圖像，可以用灰度直方圖作為圖像的灰度特征的描述。在圖像檢索中，基于灰度直方圖的算法是最簡(jiǎn)單的算法之一，容易實(shí)現(xiàn)，檢索速度非?？欤?1］，但缺點(diǎn)在于無(wú)法體現(xiàn)圖像的空間信息。我們通過(guò)灰度直方圖的檢索，先對(duì)不同的灰度分布的圖像進(jìn)行初步的分類篩選，以縮小檢索范圍，降低進(jìn)一步搜索的計(jì)算量。

實(shí)驗(yàn)中采用歸一化直方圖來(lái)進(jìn)行初步篩選，灰度級(jí)總數(shù)N采用256。對(duì)于檢索圖q和圖像庫(kù)中的圖t的歸一化直方圖Hq和Ht，定義相似度為:

其中，Hq(i)和Ht(i)分別為Hq和Ht的第i階灰度的百分比值。

4 流程

本文所采用方法的流程圖如圖1所示。針對(duì)待檢索的目標(biāo)圖像，首先通過(guò)灰度直方圖法在醫(yī)學(xué)CT圖像集中進(jìn)行預(yù)篩選，除去灰度分布差異很大的圖像，以縮小檢索范圍。對(duì)選中的圖像，利用SIFT算法來(lái)提取每幅圖像的特征點(diǎn)，將得到相應(yīng)的特征向量作為特征描述符，并建立相應(yīng)的特征向量數(shù)據(jù)庫(kù)。對(duì)于目標(biāo)圖像，先通過(guò)SIFT算法來(lái)得到它的特征向量，再在特征庫(kù)中用ANN算法進(jìn)行匹配搜索，然后計(jì)算得到每幅圖像和目標(biāo)圖像的相似度。通過(guò)對(duì)相似度的排序，來(lái)得到檢索結(jié)果。

圖1 本方法流程圖Fig．1 Flow chart of our method

對(duì)于醫(yī)學(xué)CT圖像庫(kù)，由SIFT算法得到的特征向量數(shù)據(jù)庫(kù)通常比較龐大，而且特征向量本身具有較高維數(shù)。本文采用基于隨機(jī)KD樹(shù)和分層K均值樹(shù)的ANN算法來(lái)進(jìn)行特征匹配和檢索。對(duì)于目標(biāo)圖像q中的特征點(diǎn)，在特征數(shù)據(jù)庫(kù)中進(jìn)行檢索時(shí)，通過(guò)近似k－近鄰的方式查找到k個(gè)最近鄰(k≥2)。類似SIFT算法中的距離比率準(zhǔn)則，再以與最近距離的比率為閾值來(lái)進(jìn)行判斷，只有條件符合后才被認(rèn)為是匹配點(diǎn)對(duì)。

本文的方法是基于SIFT特征進(jìn)行檢索的，所以兩幅圖像間的相似度不僅與圖像間匹配的點(diǎn)數(shù)有關(guān)，而且也與圖像間匹配點(diǎn)對(duì)應(yīng)的特征向量的歐氏距離有關(guān)。設(shè)查詢圖q與數(shù)據(jù)庫(kù)中圖像t的匹配點(diǎn)對(duì)總數(shù)為m，第i對(duì)匹配點(diǎn)對(duì)的歐氏距離為disti，則距離的均值為∑mi=1disti/m。我們提出了一種復(fù)合相似度指標(biāo)，把兩者結(jié)合起來(lái)作為相似度的度量。對(duì)于圖像q和t兩者的復(fù)合相似度指標(biāo)Ss(q，t)定義為:

這個(gè)相似度指標(biāo)的大小主要是由m的值來(lái)決定，當(dāng)在m相近時(shí)，配對(duì)點(diǎn)歐氏距離的均值起主要決定作用。

實(shí)驗(yàn)中采用最經(jīng)典的查準(zhǔn)率和查全率的評(píng)價(jià)準(zhǔn)則對(duì)檢索結(jié)果進(jìn)行比較。查全率recall和查準(zhǔn)率precision的定義為:

其中，s為一次查詢中檢索到的所有相關(guān)圖像數(shù)目，u為檢索到的不相關(guān)的圖像數(shù)目，r為圖像庫(kù)中和目標(biāo)圖像相關(guān)的但未被檢索到的圖像數(shù)目。

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

5．1 SIFT特征提取結(jié)果

作為例子，對(duì)一幅頭部CT圖像，通過(guò)SIFT進(jìn)行特征提取后，得到每個(gè)特征點(diǎn)的特征描述符，用一個(gè)128維的向量來(lái)表示，其中特征點(diǎn)的位置，方向和所處的尺度如圖2所示。圖中箭頭尾部表示特征點(diǎn)的位置，箭頭方向表示特征點(diǎn)的方向，箭頭的長(zhǎng)度表示特征點(diǎn)所處的尺度。

圖2 SIFT特征提取結(jié)果Fig．2 Feature extraction results

5．2 近似最近鄰搜索和標(biāo)準(zhǔn)最近鄰搜索的比較

實(shí)驗(yàn)中，我們對(duì)近似最近鄰搜索和標(biāo)準(zhǔn)最近鄰搜索的時(shí)間和匹配結(jié)果進(jìn)行比較。所用到的醫(yī)學(xué)CT圖像取自Visible Human CT Datasets(https://mri．radiology．uiowa．edu//VHDicom/)，實(shí)驗(yàn)在 PC機(jī)上進(jìn)行，CPU 為 Core i5 3．20 GHz，內(nèi)存為3 GB，仿真軟件為Matlab 7．10。所用的圖像庫(kù)中有1200幅圖像，提取SIFT特征后得到的特征數(shù)據(jù)庫(kù)中有284898個(gè)SIFT特征向量，兩種ANN算法的查找準(zhǔn)確率都設(shè)置為0．95，SIFT算法的距離比率閾值設(shè)為0．8，隨機(jī)KD樹(shù)的數(shù)目設(shè)為8，分層K均值樹(shù)的層數(shù)設(shè)為8。

采用ANN算法時(shí)，需要預(yù)先針對(duì)特征數(shù)據(jù)庫(kù)建立相應(yīng)的索引并存儲(chǔ)，如果圖像庫(kù)沒(méi)有變化，則無(wú)需重新建立索引。相對(duì)于大量的檢索來(lái)說(shuō)，建立索引所花的時(shí)間可以忽略。對(duì)于本實(shí)驗(yàn)中得到的特征庫(kù)，基于隨機(jī)KD樹(shù)的ANN算法建立索引的時(shí)間為9．9518 s，基于分層K均值樹(shù)的ANN算法建立索引的時(shí)間為10．0848 s。而標(biāo)準(zhǔn)搜索直接進(jìn)行線性的查找，無(wú)需建立索引。在建立索引并存儲(chǔ)后，隨機(jī)選取10幅圖像分別作為待檢索的目標(biāo)圖像，進(jìn)行近似最近鄰搜索和標(biāo)準(zhǔn)最近鄰搜索的比較，得到的實(shí)驗(yàn)數(shù)據(jù)結(jié)果如表1所示。

表1 近似最近鄰搜索和標(biāo)準(zhǔn)最近鄰搜索的時(shí)間比較Tab．1 Time comparison between NN and ANN

表1中，特征數(shù)目是每幅目標(biāo)圖像通過(guò)SIFT算法得到的特征點(diǎn)數(shù)目，時(shí)間是對(duì)每幅目標(biāo)圖像的所有特征向量完成在特征數(shù)據(jù)庫(kù)中的匹配搜索，并按相似度降序排列后返回檢索到的圖像序列所用的時(shí)間。實(shí)驗(yàn)中圖像庫(kù)并沒(méi)有變化，進(jìn)行這10次目標(biāo)圖像的檢索只需一次建立索引的時(shí)間?？梢钥吹剑捎肁NN算法建立索引后，搜索的時(shí)間相比標(biāo)準(zhǔn)最近鄰搜索有了很大的提高。由于實(shí)驗(yàn)中設(shè)置的查找準(zhǔn)確率較高，為0．95，ANN算法得到的匹配點(diǎn)對(duì)結(jié)果和標(biāo)準(zhǔn)搜索得到的結(jié)果幾乎一致，只在很少的情況可能會(huì)出現(xiàn)個(gè)別匹配點(diǎn)的誤匹配，所以并不影響目標(biāo)圖像的檢索結(jié)果。

5．3 圖像檢索性能的比較

醫(yī)學(xué)CT圖像往往具有較為清晰的紋理，目前針對(duì)醫(yī)學(xué)CT圖像細(xì)節(jié)的檢索主要是使用紋理特征［12～14］。紋理特征通常采用灰度共生矩陣來(lái)表示，通過(guò)灰度共生矩陣得到能量、熵、慣性矩、相關(guān)度的均值和方差，再由它們組成表示紋理的特征向量。我們將本文的方法同這種基于灰度共生矩陣的紋理的方法進(jìn)行了比較。圖4顯示了對(duì)其中一幅目標(biāo)圖像的檢索結(jié)果。(a)為輸入的目標(biāo)圖像。對(duì)于(a)中所示的目標(biāo)圖像，將檢索得到的圖像序列中的前9幅，先從左到右，再?gòu)纳系较路胖?，顯示結(jié)果如(b)和(c)。其中，(b)是基于灰度共生矩陣的紋理方法得到的檢索結(jié)果，(c)是本文方法得到的檢索結(jié)果。

圖3 檢索結(jié)果比較。(a)目標(biāo)圖像;(b)基于紋理的檢索結(jié)果;(c)本方法的檢索結(jié)果Fig．3 Retrieval result comparison．(a)Target image;(b)Retrieval result based on texture;(c)Retrieval result of our method

通過(guò)(b)和(c)的比較可以看出，本文方法得到的檢索結(jié)果圖像序列更符合直觀上的相似度排序。這是因?yàn)橥ㄟ^(guò)灰度共生矩陣得到的紋理雖然能反映出圖像灰度關(guān)于方向、相鄰間隔、幅度變化的綜合信息，但是它對(duì)于圖像之間的局部相似性和圖像細(xì)節(jié)的描述能力不如SIFT特征。SIFT特征本身是一種優(yōu)秀的局部特征描述算子，采用它來(lái)衡量圖像的相似性要比采用傳統(tǒng)的紋理特征更加有效。本文采用的復(fù)合相似度指標(biāo)是基于SIFT特征的，所以和基于紋理方法相比，本文方法檢索出的圖像更符合人眼對(duì)于圖像的相似性判斷。

為了進(jìn)一步評(píng)價(jià)方法的性能，我們進(jìn)行了統(tǒng)計(jì)意義上的定量比較。用圖像集中的40張圖片作為查詢目標(biāo)，占數(shù)據(jù)庫(kù)中圖像總數(shù)的3．3%，計(jì)算每次查詢結(jié)果，得到相應(yīng)的查準(zhǔn)率－查全率曲線，如圖4所示。

圖4 兩種方法查準(zhǔn)率－查全率曲線的比較Fig．4 Comparison of the results using the precision－recall curves

可以看到在查全率較小的時(shí)候，本文的方法具有很好的效果，查準(zhǔn)率明顯高于傳統(tǒng)的基于紋理的方法。但隨著查全率的增大，查準(zhǔn)率快速下降。實(shí)驗(yàn)中，當(dāng)查全率大于0．7時(shí)，基于SIFT算法的檢索方法查準(zhǔn)率反而較差。這是因?yàn)槟繕?biāo)圖像本身能提取得到的SIFT特征數(shù)目是有限的，這些SIFT特征在特征數(shù)據(jù)庫(kù)中進(jìn)行匹配搜索后，能建立起的匹配點(diǎn)對(duì)的總數(shù)也是有限的。圖像庫(kù)中的圖像和目標(biāo)圖像越相似，就具有越多的匹配點(diǎn)對(duì)，通過(guò)本文定義的復(fù)合相似度指標(biāo)可以很好地將它們找到。所以在查全率較小時(shí)，本文的方法有很好的查準(zhǔn)率。但隨著查全率的增大，需要查找的相關(guān)圖像數(shù)目增多，其中的一些圖像與目標(biāo)圖像間的匹配點(diǎn)對(duì)數(shù)目因?yàn)橄嗨瞥潭鹊慕档投兩佟ｋS著相關(guān)圖像和目標(biāo)圖像的匹配點(diǎn)對(duì)數(shù)目接近不相關(guān)圖像和目標(biāo)圖像的匹配點(diǎn)對(duì)數(shù)目，不相關(guān)圖像的影響變得顯著，也就導(dǎo)致檢索效果變差。

在實(shí)際應(yīng)用中，通常最重要的是盡可能快地檢索出與目標(biāo)圖像最相似的一部分圖像，而不是找出類似的所有圖像，要求查全率在70%以上的情況并不多，因此本文方法在實(shí)際應(yīng)用中更加有效。

6 結(jié)論

本文提出了一種基于SIFT特征和近似最近鄰算法的醫(yī)學(xué)CT圖像檢索方法。該方法首先利用SIFT算法來(lái)提取醫(yī)學(xué)CT圖像的特征點(diǎn)，將得到相應(yīng)的特征向量作為特征描述符，并建立相應(yīng)的特征向量數(shù)據(jù)庫(kù)。由于特征向量的高維特性，對(duì)于大規(guī)模的特征向量數(shù)據(jù)庫(kù)，在匹配檢索的過(guò)程中，采用準(zhǔn)確的線性搜索的方法會(huì)比較耗時(shí)。而近似最近鄰算法則可以在不明顯損失精度的情況下解決這方面的問(wèn)題，本文主要采用了基于KD樹(shù)和基于K均值樹(shù)的ANN算法。實(shí)驗(yàn)結(jié)果表明，相比于準(zhǔn)確的線性搜索方法，采用這兩種算法后，檢索速度有了很大的提升，同時(shí)檢索的效果基本上一致。和傳統(tǒng)的基于灰度共生矩陣的紋理檢索方法的相比，本文的方法具有更好的性能，得到的檢索結(jié)果圖像和目標(biāo)圖像具有更好的直觀上的相似程度，同時(shí)在檢索精度上也有一定的優(yōu)勢(shì)。該方法在大規(guī)模醫(yī)學(xué)CT圖像數(shù)據(jù)庫(kù)中的檢索中具有應(yīng)用價(jià)值，而在其它類型醫(yī)學(xué)圖像的檢索中的應(yīng)用也具有研究潛力。

［1］趙晨光，莊天戈．基于內(nèi)容的醫(yī)學(xué)圖像檢索［J］．國(guó)外醫(yī)學(xué)(生物醫(yī)學(xué)工程分冊(cè))，2004，27(2):83－86．

［2］郝欣，曹穎，夏順仁．基于醫(yī)學(xué)圖像內(nèi)容檢索的計(jì)算機(jī)輔助乳腺X線影像診斷技術(shù)［J］．中國(guó)生物醫(yī)學(xué)工程學(xué)報(bào)，2009，28(6):922－930．

［3］Lowe DG．Object recognition from local scale－invariant features［C］．IEEE International Conference on Computer Vision，1999:1150－1157．

［4］Lowe DG．Distinctive image features from scale－invariant keypoints［J］．International Journal of Computer Vision，2004，60(2):91－110．

［5］吳銳航，李紹滋，鄒豐美．基于SIFT特征的圖像檢索［J］．計(jì)算機(jī)應(yīng)用研究，2008，25(2):478－481．

［6］Liu T，Moore AW，Gray A，et al．An investigation of practical approximate nearest neighbor algorithms［C］．Ad-vances in Neural Information Processing Systems，2004:825－832．

［7］Muja M，Lowe DG．Fast approximate nearest neighbors with automatic algorithm configuration［C］．International Conference on Computer Vision Theory and Applications，2009:331－340．

［8］Arya S，Mount D，Netanyahu N，et al．An optimal algorithm for approximate nearest neighbor searching fixed dimensions［J］．Journal of the ACM，1998，45(6):891－923．

［9］Kanungo T，Mount DM，Netanyahu NS，et al．An efficient k－means clustering algorithm:analysis and implementation［J］．IEEE Transactions on Pattern Analysis and Machine Intelligence，2002，24(7):881－892．

［10］Silpa－Anan C，Hartley R．Optimised KD－trees for fast image descriptor matching［C］．IEEE Conference on Computer Vision and Pattern Recognition，2008:1－8．

［11］張恒博，歐宗瑛．一種基于色彩和灰度直方圖的圖像檢索方法［J］．計(jì)算機(jī)工程，2004，30(10):20－22．

［12］Zhu Xinzhong，Zhao Jianmin，Yuan Jie，et al．A fuzzy quantization approach to image retrieval based on color and texture［C］．International Conference on Ubiquitous Information Management and Communication，2009:141－149．

［13］Lin CH，Chen RT，Chan YK．A smart content－based image retrieval system based on color and texture feature［J］．Image and Vision Computing，2009，27(6):658 －665．

［14］Liu Chunying，Pan Zhigeng，Dong Jinxiang．Texture content－based image retrieval for necktie pattern［C］．International Joint Conference on INC，IMS and IDC，2009:1743－1746．

CT Image Retrieval Using SIFT Features and Approximate Nearest Neighbor Algorithm

Wang Shanyi1，Ma Yu1*，Wang Yuanyuan2
1．State Key Laboratory of ASIC ＆ System，F(xiàn)udan University(Shanghai，200433)
2．Department of Electronic Engineering，F(xiàn)udan University(Shanghai，200433)

A medical X －ray computed tomography(CT)image retrieval method is proposed by using Scale Invariant Feature Transform(SIFT)features and approximate nearest neighbor algorithm．First，the keypoints and corresponding feature vectors are extracted by SIFT algorithm．Then the approximate nearest neighbor algorithm is used to match the feature vectors．Finally the most similar images to the reference one are obtained．Experimental results show that the method can return the required images with good precision．Meanwhile，the approximate nearest neighbor algorithm increases the retrieval speed greatly．It has better performance than the conventional method based on textures，using the criteria of retrieval precision and the similarity between the retrieval results and the target image．It may meet the requirements of medical CT image retrieval．

image retrieval;CT images;SIFT features;approximate nearest neighbor algorithm

TP391

A

1674－1242(2011)03－0123－07

10．3969/j．issn．1674 －1242．2011．03．001

復(fù)旦大學(xué)專用集成電路與系統(tǒng)國(guó)家重點(diǎn)實(shí)驗(yàn)室自主項(xiàng)目(09MS015)

馬煜，E －mail:mayu@fudan．edu．cn

2011－06－09)