禁忌搜索算法

摘要:隨著網絡應用不斷廣泛，網絡數據也呈幾何級增長。基于內容的圖像搜索算法成為一個很好的解決方案。該文為圖像提取方法提供了一個新的高效的框架，該算法框架相對于以前所使用的基于流形的方法具有明顯的優勢:本方法框架可以直接對圖像數據評定相關性并返回相關性最高的圖像數據，而以往的基于流形的方法必須要從特征空間到一個不清晰的語義流形空間做一個映射，并對這個映射進行學習。

關鍵詞:圖像;CUDA;熵;流形

中圖分類號:TP391.41文獻標識碼:A 文章編號:1009-3044(2009)27-7748-03

Active Tabu Search

JI Min-hui

(College of Software Engineering， Southeast University， Nanjing 210096， China)

Abstract:With the extensive of network applications， network-level data is growing geometrically. Content-based image search algorithm is a good solution. A novel framework is proposed for image retrieval in this paper. Our framework has an clear advantage over pervious manifold based methods: our method can directly rank and return relevant images and does not need to learn a mapping from the feature space to the unclear semantic manifold space， further avoiding the unnecessary exploration on the dimensionality of the semantic space.

Key words: image; CUDA; manifold

隨著信息技術的日益發展，有一樣東西以無可遏制的速度增長著，這就是數據。21世紀初多媒體硬件和軟件技術得到迅速發展，多媒體已廣泛地應用于多個領域，如公共信息業、廣告、教育、醫學、商業及娛樂等。可獲取的圖像等多媒體數據急劇增長。如何組織、表達、存儲、管理、查詢和檢索這些海量的數據，是對傳統數據庫技術的一個重大挑戰。由于圖像具有形象、直觀、內容豐富等特點，接近人們的認知方式，成為不可或缺的多媒體內容。如果沒有對圖像等多媒體數據有效存儲、檢索的方法，大量信息將淹沒在數據的海洋之中，而無法被人們識別和利用。因此，如何將數字圖像處理、模式識別技術、計算機視覺技術與傳統數據庫技術結合起來，建立高效的圖像檢索機制成為迫切需要解決的問題。

1 算法提出的背景

CBIR(Content Based Image Retrieval)，即基于內容的圖像檢索，是指直接采用圖像內容進行圖像信息查詢的檢索，即在圖像數據庫中檢索與用戶所提交樣本圖像在內容上一致或相似的圖像集合的過程，通過對圖像底層特征的比較來實現檢索。該技術是當前較為熱門的話題。相對于基于文本的搜索引擎而言，CBIR是在幾何空間上進行搜索，而非基于文本搜索引擎的圖形空間。目前，盡管CBIR技術已經取得了一些成果，但其尚遠遠不能滿足人們的需要。其難點在于缺乏對圖形和語義空間足夠的描述。最近一段時間，用于圖像檢索的基于流形表示圖形的方法引起了人們的關注。大多數此類方法都將圖形特征空間認為是一個嵌入式的流形，并試圖找到流形與特征空間之間的映射關系[2]。然而，從低維的特征空間到高維的語義空間的映射屬性仍然不夠清晰。為了避免這個問題，我們提出一種新的圖像檢索的框架。

幾何流形熵(GEOMEN)是這個框架的基礎。該熵值描述的是相關數據間的聯系。因此我們需要找到GEOMEN的最小值，以便使圖像檢索更快捷。active tabu search (ATS)算法便可計算出這個最小值。名字中的‘active’是指該算法可以按照一個有意義的方向查找，從而提高速度。該算法在計算大規模組合最優化的問題上具有很高的效率。

1.1 幾何流形熵

幾何流形熵以及如何求解該熵值的最小值是本算法的基礎，同時也是圖像檢索能否成功的關鍵。在本文中，我們將使用數據節點的三維空間位置以及流形的離散曲率作為流形的幾何表示。這個表示就被稱為幾何流形熵(geometric manifold entropy)，也就是GEOMEN。

給定一個m維空間上的無序數據集X={Xi│Xi∈Rm，i=1，2， …，n}，我們首先定義一個沒有自交的封閉路徑為一個長度是n的圓周(cycle)。這個圓周上的每一個數據節點都同兩個相鄰節點連接，而這種相連的序列O可表示為O=(o1，o2， …，on，o1)，因此，集合X上的幾何流形熵GEOMEN可以表示為兩部分的和:三維空間位置P(X，O)以及幾何位置G(X，O)，也即:

S(X，O)=P(X，O)+G(X，O) (1)

幾何流形熵代表了序列O上圓周的光滑度與銳度，同時，它也是流形數據混亂度以及相似度的一個度量值。由于流形的評估可認為是對一個L維空間提取流形值的問題，因此我們可以僅在L維曲線上計算GEOMEN值。

如果嵌入的流形是一個L維的曲線，那么GEOMEN的三維空間部分就可以用歐幾里德距離來表示:

(2)

公式中d(xi，ji)=?襓xi-xj?襓代表xi與xj之間的歐幾里德距離，符號(xi，xj)表示xi，xj在序列O中互相連接。這樣，GEOMEN可被看作是由兩部分組成:曲線的曲率k以及一個正規式p。用方程表示如下:

(3)

這里(i，j，k)以及(i，j，k，l)的含義與前面所述的(i，j)的含義相同。

在一個連續空間中，光滑曲線的曲率由曲線上每一點的密切圓的曲率而定。而在離散空間中，我們用如下的一種發發確定在一個特定點xj 處數據的曲率k:

(4)

由于離散曲線的曲率易受影響，因此，為了增加本算法的健壯性，我們引入一個幾何元素:

(5)

通過公式(4)和(5)我們可以得出:

1.2 使用禁忌算法求熵的最小值

通過GEOMEN的定義我們可以得知，當熵值足夠小的時候，那么序列中的數據節點都是足夠有序的。

通過最小化熵值求得有序圓周。(a)圖:輸入數據取樣自一個圓周上;(b)圖:當熵值較高時，數據節點間的連接是隨機的;(c)圖:當熵為最小值0.384314時，數據節點間的連接是最優化的，也就是說，該圓周是最優化的。

例如，一個集合上的數據分布在一個圓周上，如圖1(a)所示，從而容易得知當序列就是該圓周時其熵值最小，如圖1(c)所示。在其他可能的組合中，例如圖1(b)所示，可以看出這時的情況是無序的，并有更高的熵值。因此，我們的目標是找出最小的熵值，即可找出最有序的序列。所以我們需要找出GEOMEN的最小值。

(6)

1.2.1 積極禁忌搜索

尋找公式(6)的最優解是一個NP問題，若圓周上存在n(n>=3)個數據節點時，那么就會有(n-1)!/2種可能的組合。而這里提出的積極禁忌搜索便可得出這個最優解的近似值。積極禁忌搜索是在普通禁忌搜索的基礎上使用積極學習技術優化后而得出的。該搜索算法通過縮小搜索空間而使得搜索更智能化，更高效。在本搜索算法中，我們需要設計的是鄰接表以及禁忌表H。

鄰接表表明了圓周上數據連接從一種形式到另一種形式的變換。變換包括3種:1)在圓周上交換一對數據節點;2)在圓周上將一個節點平移到另外一個位置;3)將圓周上特定的數據片段翻轉。例如，一個圓周上有n個數據節點，其序列O為:

O=(o1，o2， …，on，o1)

通過交換節點o1和o4我們可以得到序列:

O=(o4，o2，o3，o3，o5 …，on，o4)

通過平移o1到o4和o5之間我們可以得到序列:

O=(o2，o3，o4，o1，o5 …，on，o4)

通過翻轉o1到o4之間的片段我們可以得到

O=(o4，o3，o2，o1，o5 …，on，o4)

禁忌表H在短時間內存放以上幾種變換的表示，用于避免之前的變換被重復執行。也就是說，在接下來短時間內的幾次迭代中，禁忌表H中的變換是不允許被執行的。這個短時間就被稱為是禁忌時間，用變量tabu-time表示。當一個新的變換被加入到禁忌表H中時，它的禁忌時間被初始化為0。

在鄰接表中且不在禁忌表H中的所有元素可以組成一個候選集CSS. 通過在這個候選集CSS中搜索，我們就可以得到這次迭代中的最佳候選O，即Obest，從而可以的到最小的熵值以及最優化的變換形式。在一次迭代結束前，我們需要增加每一個變換形式的禁忌時間，并在禁忌表H中去除那些禁忌時間已經達到設定限制的變換形式。一次迭代結束后，相對應的最佳變換形式Obest就被添加到禁忌表H中。例如，在一次迭代中，通過計算得知可以通過交換oi和oj得到最佳變換形式Obest，那么我們就添加swapping(oi，oj)到禁忌表H中。

然而，挑選出Obest是非常耗時的，特別是對于大規模數據集而言。因為為了挑選處Obest，就需要對候選集CSS做完全搜索。所以我們在這里引入了積極學習方法來改進效率[3]。使用該方法可以在候選集CSS中隨機抽取一個固定大小的子集L并在此子集中搜索，從而避免在整個候選集CSS中搜索。在這種情況下，#L<<#CSS，這里#代表集合的大小。這里，我們假定必須滿足兩個條件:(1)從子集L中選取的最佳變換形式Obest是候選集CSS的前ρ%最佳變換形式的可能性是η%;(2)子集L中至少有一個候選結果是在前ρ%最佳變換形式的可能性是1-(1-ρ%)#l。因此，#L可以通過ρ%和η%兩個式子計算得出:

(7)

從上式可以看出，#L是同#CSS完全獨立的。另外，為了避免熵值出現局部最優化，我們在算法中引入一個操作稱為“越界”。也就是說，當熵值局部趨同時，我們便隨機取出CSS中的一個子集來打亂現有的序列Ocur。同時，我們使用越界時間這個變量來限制打亂序列這項操作。

給定一個數據集X，積極禁忌搜索可以描述如下:

步驟1:初始化禁忌時間和越界時間為預設值，初始化輸入數據的圓周為隨機序列，初始化禁忌表H為空集。設Ocur=O，當前的熵值Scur=S(X，O)，最優序列Oopt=Ocur，Ocur并且設最佳熵值Sopt=Scur。

步驟2:構建Ocur的鄰接表，并計算CSS(Ocur)。然后從CSS(Ocur)中隨機選取候選數據構建子集L。

步驟3:優化L中的候選數據并找出Obest。如果Scur>S(X，Obest)，那么設置Ocur =Obest，Scur=S(X，Obest)。

步驟4:增加禁忌表H中每一個元素的禁忌時間，并且如果元素的禁忌時間超過界限，那么從禁忌表H中除去這些元素。

步驟5:若熵值是趨同的，那么轉到步驟6，否則轉到步驟2. 這里我們假定若熵值在500次迭代中都沒有改變，那么我們認為此時熵值是趨同的。

步驟6:如果Sopt>Scur，那么更新Oopt=Ocur，并且設最佳熵值Sopt=Scur。如果越界時間等于0，則轉到步驟7;否則，減小越界時間的值并執行越界操作。然后設置Scur=S(X，Ocur)。轉到步驟2.

步驟7:返回Oopt和Sopt。

不同迭代次數中熵值的分布。當熵值趨同時則在圖中可以看到曲線的波動。由于我們將越界時間設置為4，所以在圖中共有4次曲線的波動。

1.2.2 積極禁忌搜索算法的實例

圖2展示了如何在有32個輸入數據的序列上尋找最小熵值的過程。該過程直觀地展示了積極禁忌搜索算法是如何工作的。由于在等式(7)中我們期望更低的ρ%值和更高的η%值，因此我們取ρ=0.9，并且取η=99，得出的#L=512. 然后我們設禁忌時間已經越界時間都等于4. 積極禁忌搜索算法找到的最佳有序圓周如圖1(c)所示。 圖2展示了熵值最小化的過程。曲線上的一次波動代表執行一次越界操作。最終經過180次迭代后得到趨同的熵值為0.384314.

2 結論

本文為圖像提取方法提供了一個新的高效的框架。圖像提取的方法變成了在一個圖像數據庫中搜索一個有序環的過程。而最優化的環可以通過ATS算法中的最小化幾何流形熵來得到。、本算法框架相對于以前所使用的基于流形的方法具有明顯的優勢:本方法框架可以直接對圖像數據評定相關性并返回相關性最高的圖像數據，而以往的基于流形的方法必須要從特征空間到一個不清晰的語義流形空間做一個映射，并對這個映射進行學習。更進一步，使用本框架可以避免在語義空間的維度上進行的無謂的研究。

參考文獻:

[1] 張李秋.一種基于紋理特征提取的圖像檢索方法[D].電子科技大學碩士論文，2007.

[2] NVIDIA. Compute Unified Device Architecture: Programming Guide[J]， version 2.1， Nov 2008.

[3] H.J.Zhang and D.Zhong. A schema for visual feature-based image indexing. Proc of SPIE: Storage and Retrieval for image and video databases III，pp36-46， San Joe， Feb.1995

[4] 李向陽，魯東明，潘云鶴.基于色彩的圖像數據庫檢索方法的研究[J].計算機研究與發展，1999(03):104-108.

[5] Cai D， He X， Han J. Regularized regression on image manifold for retrieval[J].