結合空間關係之正交基底Multiple-Instance影像擷取方法 Content-Based Image Retrieval Based on Feature Spatial Structure (FSS) 本論文將將以碎形正交基底為影像編碼方式,並利用MIL有效判斷影像搜尋條件,最後將加入影像在空間上的關係 以建立一套有效的影像搜尋系統 研究生：賴勤寧 指導教授：蔣依吾 博士 國立中山大學資訊工程學系

影像搜尋基本模型 (顏色, 形狀, 紋理) 針對影像資料庫中,每一張影像進行特徵擷取,特徵擷取方法有顏色形狀紋理等方法, 利用這些被擷取的特徵當作影像對應的索引檔,以進行影像索引比對 接下來將簡單描述顏色..特徵擷取方法 (顏色, 形狀, 紋理)

影像特徵擷取方法-顏色(Color) Color Histogram [Ballard91] [Novak92][Swain94] Reference Color Table Method [Mehtre95][Mital98] 柳丁 橘子 橘紅 蘋果 紅 青 利用一個直方圖,紀錄影像中所有像素的顏色分佈, 由於RGB各以0~255表示,顏色代表過於精細, 利用一個COLOR TABLE對顏色進行分類,再將影像中所有顏色以這些主要顏色取代，並計算主要顏色比例， 搜尋結果不受尺寸、位移及旋轉改變 無法精細檢索,且缺乏空間域的觀念 好的索引條件不論從影像端對應到索引端,還是…,應該都必須保持一一對應,若不能維持此種情況,會造成搜尋影像時趙成混淆,結果與使用者要求不同 顏色力矩(Color moment)特徵描寫著影像的顏色與空間的相關資訊 累積式（Cumulated）的統計圖，以克服稀疏對於雜訊敏感的問題，另外也提出顏色矩量（Color Moments）的方法， 這個方法認為任何顏色的分佈均可由它的moments來加以區分，而且大部分的資訊是集中在低階的部分，所以只要儲存抽取的第一階矩量（平均--mean）及二、三兩階矩量（變異數--variance 及偏離值-- skewness）的資料即可。 事物不相似卻有相似顏色;同一件事物有不同顏色代表之

影像特徵擷取方法-形狀(Shape) Sobel Edge Detection [Shu87][Chan92] Chain Code [Gam82][Kaneko85] 金字塔 籃球 橘子 這種方式是希望用多邊形去逼近所要表示的輪廓，因為是用多邊行，所以只要存較少的資料夠 這種方式是對輪廓上所有的點 (x,y) 一連串的把它們儲存下來。 不同物體有相當形狀，如橘子與球形狀皆是圓形 無法滿足良好索引應具備之性質 事物不相似卻有相似形狀;同一件事物有不同形狀代表之

影像特徵擷取方法-紋理(Texture) 影像具重複性週期性出現之特徵單元以區分影像 Co-occurrence Matrix [Haralick70][Argenti90] Tamura Texture[Tamura78][Bae97] 影像中具有重複性週期性出現之特徵代表, 在紋理的研究方面 這些具紋理的外觀，其實只要任取其中一小樣本，再經某種形式（規則或不規則）的組合後，就可得到類似的外觀 Co-occurrence Matrix:從影像圖點位置與距離的矩陣資料中抽取有意義的統計資料作為該圖形紋理數據的代表 從心理學研究角度提出視覺上紋理的特質：粗糙（Coarseness）、對比（Contrast）、方位（Directionality）、近似線（linelikeness）、規則（regularity）以及凹凸起伏（Roughness），作為該特徵的代表。此點與Haralick最大的不同在於他們提出的這六項均有視覺上的意義，而並行矩陣有些則沒有（例如熵） 只適用在純紋理的影像

影像搜尋應用: 多數影像搜尋系統不會只使用單一方法擷取特徵，例如：QBIC: 提供顏色、形狀、空間關係； QBIC是IBM公司研究中心發展出的一套系統,顧名思義就是以影像內容為主之搜尋系統，是一套線上使用的影像搜尋系統， 以顏色或簡單的文字敘述就能夠進行有效的圖像瀏覽。 以顏色搜尋的系統，提供一個調色盤讓使用者選擇要搜尋的研究，被選中的顏色加到右邊，系統再依使用者選擇顏色做比對 配置系統會考慮顏色的相對位置提供一個畫版及調色盤，讓使用者在上面畫上有顏色的圓或矩形 上述所建立索引檔資訊仍不能明確代表影像

使用碎形正交基底技術，具良好索引性質(Z.Z.Tsai,2003) 單一張影像進行檢索條件不明確 輸入多張影像，透過Multiple-Instance Learning 法則自動找出影像特徵，使搜尋條件更為明確。 進行檢索時仍難以只根據單一張影像

Multiple-Instance Learning 3張正相關影像 共有特徵為： 瀑布、岩石。 負相關影像特徵有： 藍天、白雲、草原、岩石。 Concept(3+,1-) ={瀑布,岩石}–{藍天,白雲,草原,岩石} ={瀑布} 使用MIL會產生找不到特徵問題

Diverse Density (DD)[Maron98] 5張正相關影像， 標示為1~5； 3張負相關影像 ， 標示為6~8 共有特徵 1.找不出正相關影像間共有特徵 2.找出正相關影像間共有特徵，但和負相關影像中某特徵是相似的。 找出空間上一特徵點t 距離positive bags較近，且盡量和negative bags距離得較遠，計算t 靠近bags之機率， 找出最符合特徵者

影像加入空間限制 無法詮釋影像在空間上的關係 特徵間的空間關係: 比例大小、位置、方向 資料庫影像1 搜尋影像 資料庫影像2 無法有效判斷相似特徵在空間上相關資訊（比例大小、位置、方向），比對結果可能會產生與使用者觀點不相符之情形。 本論文提出影像中有效判斷空間關係

影像中物件表示 MBR (Minimum Bounding Rectangle) 2. 2d-SS string = y x 2d-strings就是將影像圖片分別投影至對應X軸與Y軸之投影量值 為了簡化問題，對於圖像中特徵處理採用MBR（Minimum Bounding Rectangle）技術。表示出所擷取特徵最小矩形。再藉由影像中特徵群最小矩形為代表，以推導出圖片中兩兩物件間空間關係。(圖示口述) b x 2d-x string: aL, bL ,aR, bR 2d-y string: bW ,bH , aW , aH =

空間關係推理技術 (2) (1) (3) [2001] [97] [2001] [91] [97] [2001] [88] [87] [92] [92] [2005] [2004] [88] (3) [2001] [95] [99] [91] [2005]

Completely Spatial relationships on 1D 13 7 種空間關係 推論出169(13*13)種空間關係 on 2D

由於169空間關係過於複雜，對於真實影像限制過於嚴格。(SBA,2005) 缺點: 無法判斷物件間在空間上方位關係

本論文將提出另一空間關係以解決上述類似問題 由於SBA對於空間關係定義過於簡單， 空間關係視為相同 本論文將提出另一空間關係以解決上述類似問題

本論文提出之空間關係定義 分成兩類討論: (1)Non-overlap: 20 (2)Overlap: 17 1.MBR extend overlap: 4 2.Truly overlap: 13

(1)Non-overlap: 20 a b a b 6.5 6

(2)Overlap: 17 MBR Object Extent Overlaps: 4 a a b b b a a b b a Rank: 2 Rank: 4 a b b a Rank: 8 Rank: 6

Truly Overlaps: 13 Rank value: (X, Y) X: 方位 Y: 重疊 b a Rank_ab: (8, 1)

b a Rank: (1, 1) Rank: (8, 1) Rank: (2, 1) Rank: (3, 1) Rank: (4, 1)

影像物件在空間上相似性測量 碎形正交基底相似性測量 物件方位關係 物件個數 大小 顏色分類 距離 特徵區域分散程度 特徵群比例 特徵群結構 {橘紅60%,白40%} {橘紅80%,白20%} 碎形正交基底相似性測量 相似性量測值分成兩種混和比對 空間上的判斷5 碎形正交基底向量值3 特徵區域分散程度 特徵群比例 特徵群結構

影像資料庫建立 影像尺寸不限, 熱帶魚影像數目:3138

比較方法4: Multiscale Entropy(2000) 本論文系統模型 比較方法1: SSR(2004) “相同特徵表示”+“相異空間限制” “相異特徵表示”+“相同空間限制” 比較方法2: SBA(2005) 比較方法3: Vector quantization(1997) 比較方法4: Multiscale Entropy(2000)

實驗結果 Precision: Recall: 相似影像輸出數 相似影像輸出數 搜尋輸出影像總數 所屬搜尋影像類別之總數 在依序排名的影像張數中 相似影像張數所佔的比例 在資料庫中此類相似影像總數中 相似影像張數所佔的比例 應該被檢索出來的影像張數Retrieved (a+c) 應該被檢索出來的影像中 檢索出來在排名(相關的)中的影像總數Relevant (a+b) 被排名出來的影像 被搜尋(檢索)出來排名的情況 YES被排名出來相似的影像張數 NO在排名中不相似的影像張數 YES

Example : Clownfish (小丑魚) 所屬搜尋影像類別總數: 21

相異特徵表示 + 相同空間限制(2d-SS) FSS method 碎形正交基底 比較方法1: VQ method 相異特徵表示 + 相同空間限制(2d-SS) FSS method 碎形正交基底 前18張中符合空間關係者較多於VQ 紅色圈選者 比較方法1: VQ method R,G,B Codebook訓練 by LBG algoruthm.

相異特徵表示 + 相同空間限制(2d-SS) FSS method 碎形正交基底 比較方法2: ME method 相異特徵表示 + 相同空間限制(2d-SS) FSS method 碎形正交基底 比較方法2: ME method Wavelet transform

相異空間限制 相同特徵表示(fractal)+ FSS method Overlap: 17 Non-Overlap: 20 比較方法3: SSR method Overlap: 9 Non-Overlap: 8

相異空間限制 相同特徵表示(fractal)+ FSS method Overlap: 17 Non-Overlap: 20 比較方法4: SBA method Overlap: 5 Non-Overlap: 2

結論 -明確清楚使用者所欲搜尋特徵 -空間關係 直觀認知特徵 及特徵間方位 未來工作 -進行連續影像(影片)比對 -找出更適合的空間關係定義