Image Retrieval Based on Fractal Signature 蔣依吾 國立中山大學 資訊工程學系 E-mail: chiang@cse.nsysu.edu.tw Web: http://image.cse.nsysu.edu.tw

資料庫 傳統資料庫 影像資料庫 資料庫中主要資料為文字 資訊描述容易 搜尋正確性高 昔日以文字描述 資訊不易描述 搜尋正確性低 文字具有明確性，所以使用文字對資料庫搜尋，能得到正確結果 影像則否 左上圖可以描述成一顆樹，一個人，一隻貓 更詳細，一顆紅樹在左後方，一個女孩在前方，一隻黑貓在右後方 下圖描述困難

Block Diagram of Image retrieval System

Ideal Image Retrieval 相似之影像有相似之索引檔 (a) 高相關度影像資訊有高相關索引檔 (b) 索引檔相關度高，其影像資訊相關度高 不相似之影像有不相似之索引檔 (c) 索引檔相關度低，其影像資訊相關度低 (d) 影像資訊相關度低，其索引檔相關度低

Feature used for querying Text, color, shape, texture , spatial relations Image Retrieval Systems： IBM QBIC： color , texture, shape Berkeley BlobWorld： color, texture, location and shape of region (blobs) Columbia VisualSEEK: text, color , texture, shape, spatial relations

使用顏色 Babu[1995] 選出主要顏色，以主要顏色取代原本顏色 計算每種顏色的頻率f1,f2,…,fn，成為特徵，I=(f1,f2,…,fn) 計算相似度Dq,i=[(Iq-Id)2]1/2

使用顏色

使用形狀 S. Berretti[1999] 將形狀沿反曲點切開 記錄毎個曲線曲率及軸線角度 要以簡單資訊描述一個物體形狀有困難，所以要將形狀分割成個曲線

使用形狀

使用內容物 Jim [2000] 以影像組成元素為搜尋特徵 將組成物分成背景，紋理，物體 Category Background Texture Object Number of colors Normal Few or normal Normal or many Edge information Less long lines Many short lines or few long lines Color similarity High Low 現實生活中對許多事物並無明確定義，對人類而言，可以依感覺來處理或判斷，但這些資訊交由電腦處理前，需先量化，多少比例邊可稱為多，顏色數目多少才能歸類為背景？這些問題成了首先需要解決地問題，若無法處理這類問題，要以內容物建立索引，便成為一項艱鉅任務

使用內容物

影像尺寸 Albuz [2001] 使用小波轉換中的高頻濾波器及低頻濾波器

影像尺寸

影像位移 Wang [2000] 索引圖檔及資料庫圖檔之關係分為三種: 關係一 關係二 關係三 關係一 關係二 關係三 影像位移不變就是在一張影像中，使用者有興趣之部分影像，例如影像中之蝴蝶，搜尋之結果不受到蝴蝶在影像中之位置而改變

影像旋轉 Gaurav [2002] 先將影像做影像分割，把要紀錄之重要物體切割出來 將物體正規化後之形狀、角度、方向紀錄下來

影像旋轉

碎形編碼 何謂碎形 Fisher覺出一個列子，有一部特殊影印機 縮小為原來二分之一，放置在上，左下，右下

碎形編碼 若以一個三角型輸入特殊影印機多次將產生像這樣的結果

碎形（fractal）一詞則是Mandelbrot 引用由Hausdorff 在1919 年所提出之碎形維（fractal dimension）觀念所命名而來。 1982 年，MIT 的Pentland 教授把碎形維或次元或分維（fractal dimension）作為影像理解（image understanding）的特徵量（feature）而應用到電腦視覺領域中。 Mandelbrot 開啟一個名為碎形幾何(fractal geometry)的研究浪潮[Mandelbrot 1982]。它在數位影像處理的應用上包括影像切割、影像分析、影像合成、以及影像壓縮等。 Barnsley 是第一個使用碎形技術作影像壓縮的人。截至目前為止，他的演算法一直沒有公諸於世。目前所看到影像壓縮法主要是由他的一為博士班學生Jacquin 所發表出來[Jacquin 1989]，以及後來許多改良版[Fisher 1991][ Jacquin 1993]。

碎形起源 1967 年 Benoit Mandelbrot ：「英國的海岸線有多長？」 靈感來自於英國數學家 Lewis Fry Richardson 書上在估計同一個國家的海岸線長度時，有百分之二十 的誤差。 誤差是因為使用不同長度的量尺所導致的

什麼是碎形? Fractals Everywhere M. Barnsley, Academic Press, 1989

碎形特性 自我相似 碎形維度 疊代

史賓斯基三角形 產生 Sierpinski Gasket 方法如下： 　　第零步驟：畫出實心的正三角形 　　第一步驟：將三角形每一邊的中點連線，會分割成四 個小正三角形，把中央正三角形拿掉，會 剩下其餘的三個正三角形 　　第二步驟：將每一個實心小角形　都重複第一步驟 　　第三步驟：重複第二步驟 　　接下來的步驟，即重複地疊代下去………………

寇赫曲線：雪花 產生 Koch Curve 方法如下： 　　第零步驟：畫出一條線段（假設線段長度 L＝1） 　　第一步驟：將這條線段分成三等份，然後以中間的 線段為底邊，製作一個三邊等長的三角 　　　　　　　形，然後拿掉這個正三角形的底邊（此 時，L＝(4/3)1） 　　第二步驟：將曲線中的每一個線段都重複第一步驟 （此時，L＝(4/3)2） 　　第三步驟：重複第二步驟（此時，L＝(4/3)3） 　　接下來的步驟， 即重複地疊代下去（此時，L＝(4/3)n）………………

碎形

碎形編碼 自我相似性 影像分割 Range Block：不重疊 大小8x8 Domain Block：重疊 大小16x16(D>B) Jacquin提出的編碼方法，一張影像中可以找出部份相似的地方，根據這樣的性質可以將影像分割成數個方塊不斷迭代產生影像

Partitioned Iterative Function Systems; PIFS

碎形在影像搜尋的應用 Wang [2000] 使用碎形函數集之係數（a,b,c,d,e,f,g,z）當作搜尋鍵值 定義域不同，比對效果不佳 定義域錯誤

Fractal Orthogonal Basis Vines, Nonlinear address maps in a one-dimensional fractal model, IEEE Trans. Signal Processing,1993. Training Orthonormal basis vectors. Gram-Schmidt method Compression: each image range block (R) decomposed into a linear combination, Using linear combination coefficient as a feature vector。

Proof of Theorem theorem 1： Let f , g is distance space（K，d）functions， Range block length k，f= , g= , i,j 1.. xi‧xj=0 and | xi |=1 , S={s1s2.. } f has fixed point a，S: query image a’s index, T={t1t2… }, g has fixed point b , T: database image b’s index, if a , b is close, then S , T is close； if S , T is close, then a , b is close。

(a) Proof : a , b is close , S , T is close Proof of Theorem 1 (a) Proof : a , b is close , S , T is close a , b is close , then ||a－b|| thus a , b is close , S , T is close

(b) Proof: S , T is close , a , b is close Proof of Theorem 1 (b) Proof: S , T is close , a , b is close S , T is close , then thus S , T is close , a , b is close

Proof of Theorem theorem 2： Let f , g is distance space（K，d）functions， Range block length k，f= , g= , i,j 1.. xi‧xj=0 and | xi |=1 , S={s1s2.. } f has fixed point a，S: query image a’s index, T={t1t2… }, g has fixed point b , T: database image b’s index, if a , b is not close, then S , T is not close； if S , T is not close, then a , b is not close。

(c) Proof : a , b is not close , S , T is not close Proof of Theorem 2 (c) Proof : a , b is not close , S , T is not close by theorem 1, a , b is close S , T is close thus a , b is not close , S , T is not close (d) Proof: S , T is not close , a , b is not close by theorem 1, a , b is close S , T is close thus S , T is not close , a , b is not close

Advantages based on Fractal Orthogonal Basis Compressed data can be used directly as indices for query. Image index satisfy the four properties. Similarity measurement is easy.

Orthonormal Basis Vectors (a) (b) (c) Figure 3. The 64 fractal orthonormal basis vectors of (a) R, (b) G, and (c) B color components, respectively, derived from an ensemble of 100 butterfly database images. The size of each vector is enlarged by two for ease of observation..

Fourier transform vs Fractal Orthonormal basis

Original image Compressed image

Experimental Results Image database The source of images: http://www.thais.it/entomologia/ http://turing.csie.ntu.edu.tw/ncnudlm/index.html http://www.ogphoto.com/index.html http://yuri.owes.tnc.edu.tw/gallery/butterfly http://www.mesc.usgs.gov/resources/education/butterfly/ http://mamba.bio.uci.edu/~pjbryant/biodiv/bflyplnt.htm Image size:320x240 Total of images:1013 Range block size:8x8 Domain block size:8x8 Domain block set: 64 domain blocks in each color plane

Figure 4. An image retrieval example Figure 4. An image retrieval example. The features from R, G, B color components and brightness level of the query image are all selected. The rectangular area in the upper right-hand corner provides an enlarged viewing window for the image retrieved.

Figure 6. Retrieval results based on a sub-region of a query image with scaling factors 0.8 through 1.2 and rotation angles every 30 degrees.

Future work 1. With Multiple Instance Learning, finding “ideal” feature vector, as query feature. 2. Considering spatial relations of sub-regions. 3. Increasing performance.

Multiple Instance Learning To Find a feature vector that is close to a lot from different positive bags and far from all the instances from negative bags. Instance: each of these feature vectors. Bag: the collection of instances for the same example image. Positive: At least one of the instances in the bag should be a close match to the concept. Negative: None of the instances in the bag corresponds to the concept.

Diverse Density Algorithm Looking for a point in the weighted k-dimensional space near with there is a high concentration of positive instances from different bags. For any point t in the feature space, the probability of it being our target point, given all the positive and negative bags, is maximizing Diverse Density : where The DD algorithm makes use of a gradient ascent method with multiple starting points. It starts from every instance from every positive bag and performs gradient ascent from each one to find the maximum.

DD-algorithm Example