基于分形壓縮理論的目標檢測

【摘要】 圖像的目標檢測一直是一個十分重要的問題，利用目標局部與整體之間的相似性可以對目標進行檢測。主要依據圖像分形壓縮理論，借助于目標圖像的局部塊之間的相似性，可以構造出一個局部函數迭代系統，作為對目標的一個描述用來檢測目標。

【關鍵詞】 分形壓縮 函數迭代系統 目標檢測

一、引言

本文嘗試使用分形壓縮的方法實現對目標的檢測。分形圖像壓縮的提出者之一Barnsley就曾經揚言，他實現過10000：1的壓縮比。分形壓縮的基本思想是利用數據的自相似或自仿射特征，構造相應的局部迭代函數系統，從而只需要少量的數據就可以恢復與原圖象相近的圖象，達到壓縮圖形數據的目的。為提高編碼性能，相繼提出了一些變換域變換編碼的方法，提高編碼性能的同時也就提高了檢測速度。通過自相似性構造目標圖像的描述，用此方法來檢測目標。由于分形壓縮的解壓縮非常快，所以編碼的快慢并不影響檢測的速度。針對目標檢測問題的特點，研究者們采用了多種學習算法進行了嘗試。Papageorgiou采用基于冗余小波特征的支持向量機（SVM）來構建檢測算法。Schneiderman提出了一個基于多尺度小波變換的貝葉斯分類器來進行檢測。Rowley在人臉檢測系統中使用的是神經網絡的方法。Viola和Jones則提出了一個基于級聯結構的AdaBoost分類器，級聯結構由多級分類器組成，每一級的分類器都采用AdaBoost算法進行訓練。

二、分形壓縮算法

2.1 分形圖像壓縮的基本理論

標準的分形圖像壓縮的基礎是收縮映射定理、IFS（迭代函數系統）定理和拼貼定理。

定理1（收縮映射定理） 設（X，d）是完備的度量空間，f：X→X是集合X上的收縮映射，那么，f有且只有一個不動點，即f（x）=x有且只有一個解。

定理2（IFS的收縮映射定理） 設{X，ω，i=1，2，…N}是一個收縮因子為λ的IFS，H（X）是（X，d）完備度量空間上的非空緊子集，則由：

W（X）=ω（B），[∨] B[∪]H（X）

定義的變換：W：H（X）→H（X）是完備度量空間[H（X），h（d）]的一個收縮變換，即是W一個上Rn的收縮變換，其收縮因子為λ，其中h（d）為Hausdorf距離。

定理3（Hausdorf空間的拼貼定理） 設（X，d）為一完備度量空間，給定圖像I[∪]H（X），ε>0，選一個壓縮因子0<λ<1的IFS（X，W），W={ω1，ω2，…，ωN}，使得h（I，W）≤ε，h（d）為Hausdorf度量，則

h（I，A）≤

其中，A為IFS系統的吸引子。

2.2 基本圖像分形壓縮算法

分形壓縮的基本原理就是找到最優的IFS，使得IFS的吸引子與原始圖像一致或近似。但是對于自然圖像而言，如果采用是一個IFS去逼近它是不可能的，因為大多數圖像不具備嚴格的自相似性。但是若將圖像分成小塊后，各小塊之間可能存在自相似性，可以利用這一點進行圖像壓縮。Jacquin就利用了局部迭代函數理論，提出了一種基于塊的全自動的分形圖像壓縮方法，使分形圖像壓縮從人工處理轉變為自動編碼。此后各種改進的方法也不斷被提出，從DCT的變換域中尋找自相似性的方法來加提高編碼速度。各種改進算法很多，但是都以標準的算法為基礎，幾乎都是對于標準算法中編碼時采用全局檢測而導致速度過慢提出的。但是無論是何種算法，解碼速度都是很快的。

具體的壓縮算法是將圖像劃分為值域塊Ri和定義域塊Di兩大類，值域塊不重疊，且比定義域塊要小，定義域塊可以重疊。在局部函數迭代系統的作用下，對于每一個值域塊Ri都尋找在一個定義域塊Di，使得定義域塊在收縮仿射變換ωi下與值域塊的誤差最小，即

Di=argmin（Dj-Ri）2

在尋找最佳檢測定義域塊的同時，也確定了局部迭代函數系統。壓縮映射的選取可以設計8種[3]，稱為反射-旋轉變換。首先對選定的定義域進行收縮變換，變換后的圖像與值域塊大小一致；然后對變換后的定義域塊進行基本的8種旋轉和反射變換；最終利用圖像的灰度變換計算出與值域塊之間有最小誤差的對比度和閾值。具體計算如下：

假設dij（i=1，2，…N，j=1，2，…M）是定義域塊經過收縮仿射變換后的圖像塊的像素值，rij（i=1，2，…N，j=1，2，…M）是值域塊的像素值，最佳的灰度變換應該使下式最小：

為使ε達到最小，分別對s和σ求導，并令其導數為零，可得

找出具有最小誤差的值域塊和定義域塊的位置和收縮映射參數，然后找出所有值域塊的迭代參數即可完成圖像的壓縮。相比于壓縮算法解壓縮很簡單，只是將上述過程反過來即可。

三、目標檢測算法及實驗

利用上述分形壓縮方法，先從模板圖像上計算出該模板的IFS，保存作為描述子，然后在含有該目標的圖像上，使用保存的描述子在該圖像上的每一分塊區域上做以此分形解碼運算，若某一區域迭代前和迭代后沒有差別或者處理前后差別很小，即可認為該區域就是含有目標的區域。具體算法為：

（1）將模板圖像分為不重疊N×M塊值域，然后求出IFS；（2）在待檢測圖像中，以一定尺寸n×m的窗在圖像上掃過，窗每次移動所覆蓋的區域為I0，將I0分為N×M塊值域，然后使用IFS作用于該圖像塊，若迭代一次后與迭代前相差不大，則可認為該區域是目標；（3）如果掃完整幅圖像，則轉（2），將尺寸擴大1.5倍后再檢測，直至尺寸與待檢測圖像大小相等。

當然上述算法運行起來極其耗時，若能使用顏色信息預先得知目標的大致區域，則可以達到事半功倍的效果。圖1是使用上述算法得到的實驗結果。

四、結論

本文提出的一種基于分形壓縮的目標檢測方法，雖然原始的算法運行起來有點慢，但是使用顏色等信息輔助檢測，速度可以得到很大提高。算法對目標的較大的傾斜或旋轉無法處理，這也是以后要改進的方向，但作為一種檢測方法仍有一定的發展空間。

參 考 文 獻

[1] 周友兵. 分形圖像編碼的原理及其發展趨勢[J]. 現代電子技術，2003，（8）

[2] 羅瑜，游志勝，董天罡. 基于DCT的快速分形圖像壓縮算法[J]. 計算機應用，2004，（24）

[3] 趙健，雷蕾，蒲小勤. 分形理論及其在信號處理中的應用[M]. 北京：清華大學出版社，2008.61-63