第十二章 影像資料庫檢索.

Presentation on theme: "第十二章 影像資料庫檢索."— Presentation transcript:

1 第十二章 影像資料庫檢索

2 內容 12.1 前言 12.2 色彩檢索法 12.3 邊紋理檢索法 12.4 區域關係檢索法 12.5 圖論式檢索法
前言 色彩檢索法 邊紋理檢索法 區域關係檢索法 圖論式檢索法 植基在彩度動差的檢索法 結論

3 12.1 前言 植基於色彩 植基於紋理 植基於圖論模式 植基於彩度動差
影像檢索之目的在於提供快速且強健式的方法以提供用戶能有效達到影像檢索的需求。影像檢索的方法雖然很多，大致說來，不外乎植基於內容(Content-based)的影像檢索法，它們分別是： 植基於色彩 植基於紋理 植基於圖論模式 植基於彩度動差

4 12.2 色彩檢索法 範例1:[1]何謂色彩影像檢索法？
解答：若查詢影像Q已經被轉換為一色彩柱狀圖(Color Histogram)且影像資料庫中的任一張影像的色彩柱狀圖皆已轉換好。介於兩個色彩柱狀圖之間的斜線區域代表兩張影像的相似度(Similarity)。斜線區域面積愈小代表兩張影像的相似度愈高。 圖 兩張影像的色彩柱狀圖

5 八分樹(Octree)[2]被用來表示影像的彩色資訊。
y z x

6 八分樹表示法。

7 範例3: 可否給一小例子以解釋何謂八分樹的色彩檢索法
範例3: 可否給一小例子以解釋何謂八分樹的色彩檢索法? 解答: 給定 。因為 、 、 ，所以可用011代表這些彩色的範圍，011位於八分樹的樹根之下一層的孩子點上。從這些孩子點往下走訪到下一層編號為001的節點上。依此次序一直走訪到第八層，途中經過的路徑可表示為: 該路徑可表示成圖12.2.2。

8 圖12.2.2 所對應的路徑

9 愈上層的節點給予較高的加權，因為表示是主色。
而每個彩色像素都可用一路徑儲存它。由於分佈不平均，我們不需要完整八分樹，這時可將八分樹由下往上縮減，降低記憶體需求。 而進行影像檢索時，將待查詢的影像轉換成減縮式的八分樹，再將其和影像資料庫中的各個八分樹取交集，交集越多相似度就越高。最後再由相似度高低排出檢索結果。 解答完畢

10 12.3 邊紋理檢索法 (Edge Texture) 首先，取得輸入影像的邊圖(Edge Map) 圖12.3.1 一個輸入的例子
圖 一個輸入的例子 (b) 得到的邊圖

11 五種特徵： 注水時間(Filling Time)  11 分岔數(Fock Count)  3 迴圈數(Loop Count) 1
圖 注水時間的例子 注水時間(Filling Time)  11 分岔數(Fock Count)  3 迴圈數(Loop Count) 1 水流量(Water Amount) 15 框住物體的最小長方形的寬和高 4和6 利用以上五種特徵，可將輸入的邊圖統計出注水時間柱狀圖、分岔數柱狀圖和迴圈柱狀圖等，以方便在影像資料庫的檢索工作。這些柱狀圖的比對工作很類似於色彩柱狀圖的比對工作。

12 (a) 第一順位得到的影像 (b) 第二順位得到的影像 (c) 第三順位得到的影像 圖12.3.3 一個影像檢索的例子

13 12.4 區域關係檢索法 建立影像資料庫時，每張影像需要先得到其區域及記錄區域之間的彼此關係。可利用第四章的區域分割技巧搭配區域的質心等性質予以完成。 圖12.4.1(a) 為原影像，而圖12.4.1(b) 為影像內區域間的關係樹圖。 (a) 原影像 (b) 區域間的關係樹 圖 區域間關係

14 進行查詢時，我們比對區域和區域間關係來檢索影像。有了區域間的關係，可以類似於深先表示式的空間資料結構(參見第九章)來表示之。例如圖12. 4
進行查詢時，我們比對區域和區域間關係來檢索影像。有了區域間的關係，可以類似於深先表示式的空間資料結構(參見第九章)來表示之。例如圖12.4.1(b) 可表示成 ((A1A2))，這裡A1代表黑色三角形及其屬性，而A2代表黑色圓形及其屬性；左括弧 ( 表示經過內部節點，而右括弧 ) 則表示結束時該內部節點再次被拜訪到。 兩個區域R和R΄顏色相似度可表示為 這裡平均值U=U紅、U綠 和 U藍 與標準差σ=σ紅、 σ綠和σ藍。

15 形狀相似度可表示為 C(R)代表區域R的質心，而C(R΄)代表區域R΄的質心。當然讀者可引入更多的幾何特徵以提高形狀相似度的強健性。 給定一待查詢影像，首先將其轉換成關係深先表示式，然後將其和影像資料庫中的各個關係深先表示式相比，若彼此匹配的程度愈高代表相似度愈高，檢索出來的機會越高。

16 12.5 圖論式檢索法 圖12.5.1中， 代表臉部； 代表左眼，而 代表右眼。現在考慮物件的周長和物件之間的水平角度可進一步增加檢索的考慮面。令周長為 L，而水平角度為θ，這裏θ的範圍介於0和1之間。例如： 和 為水平方位上的兩眼， 。如此一來，圖12.5.1的屬性關係可表示如圖12.5.2所示 圖 簡單的例子

17 圖12.5.2中， 代表人臉的中心和右眼的角度為36°； 代表人臉的中心和左眼的角度為144 °。符號 C 代表臉包含了眼睛，而符號 U 代表兩眼沒有包含或交集關係。
圖 圖12.5.1的屬性圖

18 現在將模組影像所對應的屬性關係圖視為一點，假若影像資料庫有n 張模組影像，那麼就有 n 個屬性關係圖，也就是有 n 個點。接著，我們在這 n 個點當中挑選出二個點，Va 和Vb ，並且確定這二個點的距離最遠，也就是 D(Va ,Vb )=Dab 為最大。今以Va 和Vb 拉出一直線。我們這裏所謂的 D(Va ,Vb )之算法乃依循前面所說的編輯距離之算法。 扣除掉Va 和Vb二點，假設Vi 為剩餘 (n-2) 個點中的一個點，三者的關係如下圖所示

19 由上面的圖形中，可得到 由上二式可推得 假想有一超平面(Hyper-plane) H垂直直線 ，令 為 投影在 H 的點。這裡，我們可以假設 H為二維的超平面，而且原先的 (n-2) 個點皆已投影在 H 上了。可得 [可事先算出;續降維度]

20 12.6 植基在彩度動差的檢索法 CIE XYZ彩色系統可透過式(12.6.1)中的RGB彩色系統來得到
12.6 植基在彩度動差的檢索法 CIE XYZ彩色系統可透過式(12.6.1)中的RGB彩色系統來得到 (12.6.1) 上式所得到的X、Y和Z，可以再用下式可得到彩度的分量(x, y) (12.6.2)

21 C (x, y) =RGB彩色系統中對應到彩度 (x, y) 的像素個數
Paschos等人 [10] 的影像資料庫檢索法，首先將彩色影像的像素轉換成彩度 (x, y)，並可將其量化(Quantize)成若干層級。換言之，彩度 (x, y) 可對應到層級 (Xl, Yl)， 。 y 在上面的對應示意圖中，RGB彩色系統中常常會發生好幾個像素對應到同一個彩度 (x, y) 的情形。這種多對一的對應關係，我們可用陣列 C 來儲存二維彩度陣列 (x, y) 上的投票情形。 陣列 C 可被定義為： C (x, y) =RGB彩色系統中對應到彩度 (x, y) 的像素個數

22 解答:在第九章的9.4.2節中，我們在式(9.4.2.1)中定義過(p+q)階動差為
範例3: 何謂彩度動差? 解答:在第九章的9.4.2節中，我們在式( )中定義過(p+q)階動差為 上式中的 代表位於位置 的像素灰階值。這裡談的彩度動差被定義為 (12.6.3) 一般來說，我們都只用到低階的彩度動差，例如 等。 解答完畢

23 範例4：如何利用式(12.6.3)所定義的彩度動差來進行影像檢索？
解答：令查詢影像(Query Image)的彩度動差為 ；令影像資料庫中的模型影像(Model Image)之彩度動差為 。利用彩度動差 和 ，查詢影像和模型影像的差異大小可利用下列的距離來量度： (12.6.4) 解答完畢

24 12.7 結論 在12.2節中介紹的影像檢索方法中，其本質屬於色彩式的檢索法。在 [5] 中，學者結合人類對顏色的辨識和動態匹配法也得到很好的一個色彩式影像檢索法。在 [6] 中，學者也提出一個很有效率的國旗影像檢索法，其中使用到的方法頗值得一讀。