基于分形壓縮理論的目標(biāo)檢測

【摘要】 圖像的目標(biāo)檢測一直是一個(gè)十分重要的問題，利用目標(biāo)局部與整體之間的相似性可以對目標(biāo)進(jìn)行檢測。主要依據(jù)圖像分形壓縮理論，借助于目標(biāo)圖像的局部塊之間的相似性，可以構(gòu)造出一個(gè)局部函數(shù)迭代系統(tǒng)，作為對目標(biāo)的一個(gè)描述用來檢測目標(biāo)。

【關(guān)鍵詞】 分形壓縮 函數(shù)迭代系統(tǒng) 目標(biāo)檢測

一、引言

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

二、分形壓縮算法

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

標(biāo)準(zhǔn)的分形圖像壓縮的基礎(chǔ)是收縮映射定理、IFS（迭代函數(shù)系統(tǒng)）定理和拼貼定理。

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

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

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

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

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

h（I，A）≤

其中，A為IFS系統(tǒng)的吸引子。

2.2 基本圖像分形壓縮算法

分形壓縮的基本原理就是找到最優(yōu)的IFS，使得IFS的吸引子與原始圖像一致或近似。但是對于自然圖像而言，如果采用是一個(gè)IFS去逼近它是不可能的，因?yàn)榇蠖鄶?shù)圖像不具備嚴(yán)格的自相似性。但是若將圖像分成小塊后，各小塊之間可能存在自相似性，可以利用這一點(diǎn)進(jìn)行圖像壓縮。Jacquin就利用了局部迭代函數(shù)理論，提出了一種基于塊的全自動的分形圖像壓縮方法，使分形圖像壓縮從人工處理轉(zhuǎn)變?yōu)樽詣泳幋a。此后各種改進(jìn)的方法也不斷被提出，從DCT的變換域中尋找自相似性的方法來加提高編碼速度。各種改進(jìn)算法很多，但是都以標(biāo)準(zhǔn)的算法為基礎(chǔ)，幾乎都是對于標(biāo)準(zhǔn)算法中編碼時(shí)采用全局檢測而導(dǎo)致速度過慢提出的。但是無論是何種算法，解碼速度都是很快的。

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

Di=argmin（Dj-Ri）2

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

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

為使ε達(dá)到最小，分別對s和σ求導(dǎo)，并令其導(dǎo)數(shù)為零，可得

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

三、目標(biāo)檢測算法及實(shí)驗(yàn)

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

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

當(dāng)然上述算法運(yùn)行起來極其耗時(shí)，若能使用顏色信息預(yù)先得知目標(biāo)的大致區(qū)域，則可以達(dá)到事半功倍的效果。圖1是使用上述算法得到的實(shí)驗(yàn)結(jié)果。

四、結(jié)論

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

參 考 文 獻(xiàn)

[1] 周友兵. 分形圖像編碼的原理及其發(fā)展趨勢[J]. 現(xiàn)代電子技術(shù)，2003，（8）

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

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