基于四叉樹算法的智能實時圖像識別模型設計與分析

酈麗華LI Li-hua

（浙江育英職業技術學院，杭州 310018）

0 引言

Pearlma WA等人提出了將編碼思想和快速小波變換為基礎的SPIHT算法，作為現代國際圖像變換編碼的領先方法，此算法基于分割排序和零樹集合，使待量化編碼小波系數劃分成為3個集合列表，利用排序、初始化、量化、細化步長對子過程進行更新，實現編碼嵌入。SPIHT編碼結構簡單，并且不需要任何的訓練，還能夠支持多碼率。然而，通過理論分析與實驗結果分析，此算法也存在部分問題，例如：在小波變換時，要求結合圖像數據開展卷積運算，計算比較復雜，需要的內存空間比較大；分割排序與零數集合復雜，信噪比較高；存在較大的計算量，提高編碼速度；算法編碼階段關聯模型比較簡單，通過有限關聯信息對節點狀態進行預測，影響壓縮能力[1]。因此，本文提出了基于四叉樹算法的圖像實時識別模型[2]，通過此算法定義SPIHT編碼算法和小波變換，解決多級樹集合分裂（Set Partitioning in Hierarchical Trees，SPIHT）編碼算法的編碼速度慢等問題。實驗結果表示，此算法圖像復原質量、編碼速度等技術指標比SPIHT等編碼算法要優，應用前景廣闊。

1 四叉樹的算法分析

1.1 四叉樹分解算法

四叉樹分解能夠劃分原始圖像為多個小塊，在同個小塊中劃分一致性像素，此小塊大部分都是方塊，只有少部分為三角形或者長方形。通過圖像歸一化實現圖像四叉樹分解，利用簡單縮放使圖像轉變為方形，像素點數為2的整數次冪，對四叉樹進行分解。

分解四叉樹的具體過程如下：將原始圖像劃分成為原始子塊，如果子塊能夠滿足使一致性標準要求，則存儲整體子塊像素值，否則把方形原始圖像劃分成為大小相同的4個子方塊。現代一致性的檢驗標準多，包括紋理特征與QRH。本文使用標準差為一致性校驗標準，此算法復雜度比較低，并且算法比較簡單，能夠將子塊中圖像邊緣算法等優勢展現出來，分割效果如圖1所示。

圖1 圖像的分割效果

1.2 四叉樹結構編碼

在存儲四叉樹時，要保存四叉樹結構信息和葉子節點顏色信息。指針中各節點要對指針場進行存儲，在存儲三元組時，要將每個節點層次L和此層的位置（X，Y）指出。但是此方法要求大量的存儲空間。

為了解決原四叉樹結構編碼中模版只能夠代表有限的結構類型，并且樹深度最多只能夠達到三層等問題，本文對算法進行了改進，得到超過兩次的四叉樹分解，思想表示為：首先，對目前塊進行四叉樹分解，直到將全部進行分解；其次，根據上述編碼規則實現分解。數的編碼結構如圖2所示，Layer1中的模塊（D0，D1，d1，d2，d3，d4）和圖中110011對應。并且d1，d2，d3，d4不是葉子節點，而用于表示是否又子樹。如果為1，那么子樹的數量就是4棵，節點為另外4棵樹的根。如果圖片需要分解，最終編碼為110011000100000。

圖2 數的編碼示意圖

在實現樹結構編碼信息之后，通過簡單層次遍歷使其轉變成為物理存儲方式。在實際編碼過程中，對最后一層0結構信息不進行存儲，以便壓縮存儲空間。經過實驗驗證，對于一個需要兩次及兩次以上分解的圖像，平均每個結點的顏色信息僅需要0.03bit就可以存儲其位置信息。如果圖像要分解兩次以下，此方法退化成為原本算法，也就是每個節點顏色信息存儲信息位置[3]。

2 基于四叉樹的圖像特征提取

2.1 區域分割

在分割圖像區域過程中，利用四叉樹分裂合并的方法實現圖像區域的分割，圖3為四叉樹分解。假如R表示整幅數字圖像，那么將R分解成為4個大小一樣的子區域Ri（i=1，2，3，4）。針對此區域，圖像并沒有某種相同屬性，說明此區域劃分成為4個相同區域Rij（i=1，2，3，4；j=1，2，3，4），依次實現各子區域的分裂，直到無法再分裂。在分裂過程中，針對相鄰子區域，假如具備某種相同屬性，就要合并區域，避免某屬性子區域劃分成為不同區域，直到無法合并和分裂，實現圖像分割。

圖3 四叉樹分解

2.2 圖像特征提取

算法思想指的是對尺度空間極值點進行檢測，確定尺度與位置，實現特征點描述子的生成。將算法思想為基礎實現SIF特征向量的生成，對兩幅圖像中關鍵點相似性的生成，此種判定指的是通過兩幅圖像特征向量歐式距離進行度量。在判定兩個關鍵點的時候，根據目前歐氏距離和最小距離相除，假如比設定值要小，那么匹配兩個關鍵點。逐漸降低設定閾值，滿足匹配關鍵點也會降低，但是會更加穩定。

通過四叉樹分裂合并與局部特征算法特點提出了基于特征融合與四叉樹的圖像識別措施，利用四叉樹對圖像區域進行分割，之后提取分割圖像的顏色直方圖信息，根據局部特征SIFT算法提取特征精度，實現特征信息的融合，對圖像特征具有更好的辨識[4]。

3 基于四叉樹的圖像編碼算法

3.1 編碼算法流程

基于四叉樹分割量化的編碼算法步驟為：

其一，對原始圖像的L級整型進行小波變換，得出3L個高頻子帶和1個最低頻子帶；

其二，將最低子帶LL的編碼得到實現，對高頻子帶實現四叉樹分割量化編碼；

其三，根據關聯模型進行算術編碼。

根據SIFT算法實現高頻子帶四叉樹分割量化編碼，但是要對說明部分重新定義，也就是C（i，j）-像素點（i，j），Ts指的是帶s的小波系數四叉樹。Ts[l]（i，j）指的是四叉樹的節點值：

m（i，j）指的是最重要位，s（i，j）指的是四叉樹節點重要性程度。重要性測試函數定義為：

3.2 四叉樹的結構和增長順序

圖4為四叉樹增長與剪枝結構，最上層為原始父節點，第二層為子節點，第三層為孫節點，以此類推。父節點的選擇對最終增長結果并沒有太大的影響，但是會影響到區域增長過程。一般在目標圖像中選擇父節點，對于容易確定的目標圖像可以使圖像分割速度加快。而對于不確定多目標的圖像，沒有分割的原始像素點，一般都能夠作為對應目標的父節點。分割正副圖像，分割結果使背景作為特殊目標，對目標灰度與大小進行判斷，區分背景[5]。

圖4 四叉樹增長與剪枝結構

在四叉樹增長的過程中，要剪除部分沒有滿足進一步增長需求的子節點。要剔除自身為父輩切點的部分子節點。剔除部分為同輩中先增長的節點。通過圖5可以看出來，在增長時的子節點和父輩、同輩的子節點關系。一般剪枝條件如下：

其一，子節點無法滿足繼續增長條件；

其二，子節點中具有父輩節點；

其三，子節點中包括已經增長的同輩子節點。

在全部子節點被剪枝的時候，終止增長過程，從而分割目標。

3.3 局部密度估計

密度估計指的是以樣本集推斷總體概率分布的方法，是數據分析方法之一。密度估計有非參數估計和參數估計兩種方式，參數估計能夠使用少量簡單參數對總體分布進行描述，但是要求得到樣本所屬類別和類條件總體概率密度形式。非參數估計能夠描述未知總體概率密度函數的方式，但是計算比較復雜，存儲空間耗費比較大。在基于四叉樹分塊密度估計模型中，四叉樹分塊算法便于使用單一類別的均勻分布與高斯分布進行描述，能夠對像素灰度值相似性進行保證。如果需要避免全局特征和其他分塊算法在局部特征估計中的樣本類別比較多，降低參數估計描述精準度，就必須使用非參數估計情況[6]。

本文使用單高斯分布描述每塊像素灰度值，單高斯分布對數似然函數：

公式中的X指的是分塊像素集，D指的是圖像通道數，N指的是像素個數。μ參指的灰度均值，∑指的是通道之間的協方差陣。

4 試驗仿真

圖5為仿真樣本，表1為試驗仿真樣本特征值，實現特征值局部離散化并且利用此屬性約簡算法進行約簡。設計網絡結構，使用多輸入單輸出三層結構，輸出層以特征向量輸出設置16個節點，規則層節點設置為10，和需要分類數字一樣，輸出層設置為1，激勵函數為purelin和logsig，學習函數為learngdm，誤差率為0.001，學習速率為0.05。

圖5 仿真樣本

表1 試驗仿真樣本特征值

訓練結果分析：提取特征值通過四叉樹算法約簡前后的維數不同，所以約簡前后網絡訓練曲線不同，對于沒有通過處理和通過處理的樣本訓練[7]。通過仿真結果表示，在誤差精度相同的條件下，利用四叉樹算法的網絡能夠滿足收斂需求，迭代次數為885次，沒有優化的網絡迭代書數為2976次，減少訓練次數，節約大量時間。

4.1 抗噪能力測試

通過訓練樣本與測試集樣本選擇40副圖片，劃分成為4組，每組添加密度0.01、0.02、0.03、0.04的隨機椒鹽噪聲與方差0.01、0.02、0.03、0.04的高斯噪聲，測試添加之后的樣本，表2為抗噪聲能力測試表。

通過表2可以看出來，如果噪聲密度不大，對于污染的圖片具有良好識別效果，表示圖像識別模型抗噪聲能力較強。

表2 抗噪聲能力測試表

4.2 識別速率測試

表3為識別速率測試結果，通過表3可以看出，本文算法的運算速率比其他兩種要優，是因為此算法能夠對冗余特征簡約，降低網絡訓練時間，系統實時性良好。

表3 識別速率測試結果

4.3 自適應性測試

通過訓練樣本與測試集樣本選擇40副圖片劃分成為四組，每組旋轉1°、2°、3°、4°，測試旋轉之后的圖片，表4為旋轉自適應測試表。之后，對每組樣本分別放大1倍、1.5倍和縮小到原來的1/2、1/3，測試放大和縮小的圖片，表5為縮放自適應測試表。通過表4和表5可以看出來，系統對于旋轉和縮放之后的圖片識別效果良好，表示系統具備良好自適應性，所提取特征有效[8]。

表4 旋轉自適應測試表

表5 縮放自適應測試表

5 結語

本文通過四叉樹分裂合并提出了基于四叉樹算法的圖像識別與特征提取方法，能夠通過四叉樹實現圖像區域分割，對圖像區域中的信息提取并且識別。通過對算法模型進行驗證，表示本文的方法能夠滿足實際需求。