邊緣圖像自適應編碼方法

高異凡，諶德榮，宮久路

（北京理工大學，北京100081）

0 引言

邊緣作為圖像的重要特征，是無人系統用于目標識別、視覺測量等的重要信息。Edwin［1］使用Canny算子來提取儀表盤和指針邊緣，實現了利用機器視覺識別儀表讀數。Ling［2］借助包裹的輪廓邊緣特征來識別快遞包裹尺寸。

在無線網絡和運載火箭遙測等無線信道容量有限的無人系統中，為了最大限度傳輸重要信息，通常將系統設計為2個子系統［3?4］：前端進行圖像采集和預處理等計算復雜度較低的處理，同時有效減少數據量；后端進行識別和測量等計算復雜度較高的處理。研究表明［4］，在前端進行邊緣特征提取，只將邊緣圖像發送到后端，是平衡計算資源和數據量的合理方式。

邊緣圖像可以通過數據壓縮方法進一步減少數據量，以降低無人系統中數據傳輸和存儲的壓力。由于測量任務的精度要求，系統只能使用無損壓縮的方式［5?6］。常用的邊緣圖像無損壓縮算法包括邊緣打包法和鏈碼編碼法［7］。邊緣打包法將邊緣數據按照每8個像素為一組，并打包成1字節進行編碼壓縮；鏈碼編碼法利用Freeman 8?方向鏈碼對邊緣數據進行編碼壓縮。對由以上2種方法獲取的數據，還可以通過LZ4［7］等通用壓縮算法進一步提高編碼壓縮比。

邊緣打包法計算復雜度較低，適用范圍廣；鏈碼編碼法對邊緣稀疏圖像壓縮效率高，但計算復雜度較高。針對上述問題，本文提出一種邊緣圖像自適應編碼算法，通過使用Logistic回歸模型，快速選擇邊緣打包法或鏈碼編碼法，以獲得比單一方法更優的壓縮結果。

1 邊緣圖像的直接編碼

1.1 邊緣圖像獲取

本文參考Canny邊緣檢測方法，設計了如圖1所示的邊緣獲取流程。具體流程如下：

圖1 邊緣圖像獲取流程Fig.1 Flow chart for edge image acquisition

1）利用Gauss濾波對輸入圖像進行去噪處理。當圖像背景比較單一或目標輪廓清晰時，Gauss濾波核的標準差應稍大些，以避免噪聲干擾。

2）利用一階微分算子計算圖像在水平和垂直方向上的微分，并計算梯度。

3）沿著梯度方向進行非極大值抑制，去除弱響應點。

4）進行雙閾值檢測，獲取單像素邊緣。

5）刪除孤立點和噪聲，得到邊緣圖像。

1.2 邊緣打包法

在邊緣圖像中，用1和0表示某點是否為邊緣點。邊緣打包法首先將二維邊緣圖像表示為一維數據流，下面以圖2為例進行詳細說明。

圖2 邊緣打包法示例Fig.2 Example of edge packing

從左上方像素點開始，按照從左至右、從上至下的順序依次將每8個像素作為一組，并打包成1字節。由于圖2每行有12個像素，并不是8的整數倍，這種情況有2種處理方式：1）行尾填充 “0”；2）將圖像按行展開成一維向量。在使用第2種方法時，圖2可表示為（16進制）：［0x40 0x20 0x02 0x10 0x40 0x88 0x05 0x00 0x20］。

由于打包后的一維數據流仍然存在冗余信息，綜合考慮計算資源和數據量的限制，選用LZ4算法對打包后的邊緣數據進行進一步壓縮。邊緣打包法流程如圖3所示。

圖3 邊緣打包法流程圖Fig.3 Flow chart for edge packing

LZ4屬于字典編碼，是LZ77的一種改進算法。LZ77維護一個滑動窗口，從已編碼的數據流中查找是否存在待搜索緩存，并用匹配串的索引表示。而LZ4借助Hash表來存儲滑動窗口中的數據索引，改善待搜索緩存的匹配速度，在保證較高壓縮比的同時極大地縮短了壓縮時間［8］。

1.3 鏈碼編碼法

鏈碼是一種表示曲線的常用編碼技術，其主要方法有方向鏈碼和頂點鏈碼。其中，方向鏈碼分為 4?方向鏈碼和 8?方向鏈碼［7］。Freeman 8?方向鏈碼從某個起始像素點開始，用ci∈｛0，1，…，7｝表示相鄰的8個位置，于是每個鏈碼可用3bit實現存儲。以某點作為起點開始，若當前點存在一個相鄰的像素是邊緣點，則用代表此方向的ci編碼，并將此點設置為當前點，繼續下一輪編碼，直至在8個相鄰方向找不到未編碼點為止。最后，由起始點坐標（x，y）、鏈碼總長度n以及n個ci組成一條完整鏈碼。

為了使用Freeman 8?方向鏈碼表示圖2，設從像素相鄰的正上方開始，順時針依次編碼為0、1、2、…、7。若以（0，1）為起點，余下點編碼為［3 3 3 3 3 1 1 1 1］，則圖2的完整編碼是（16進制）：［0x00 0x01 0x0A 0x6D 0xB6 0x49 0x24］。

與邊緣打包法類似，用LZ4對鏈碼數據進行二次編碼后輸出。此方法為鏈碼編碼法，流程如圖4所示。

圖4 鏈碼編碼法流程圖Fig.4 Flow chart for chain-code coding

值得注意的是，鏈碼編碼法需要用到泛洪填充算法來搜索邊緣圖像中的所有鏈碼，其運行時間遠大于邊緣打包法，這是鏈碼編碼法的不足之處。

2 邊緣圖像自適應編碼

2.1 壓縮性能分析

設圖像長為w，高為h，邊緣打包后的數據量為wh；設其中鏈的條數為k，鏈平均長度為l，假設長、高和最長鏈的長度都不超過216，則鏈碼編碼后的數據量為（3×16+3l）kbit。當不考慮 LZ4壓縮時，邊緣打包法的數據量是固定值，只與圖像的尺寸相關。而鏈碼編碼法的數據量隨著圖像內容的不同而變化，每條鏈碼至少需要48bit的存儲起始點和鏈碼長度，且編碼每個邊緣點所用數據量為打包壓縮法的3倍。如圖5所示，當圖像邊緣稀疏時，采用鏈碼編碼法的壓縮比為6.85（本文中的壓縮比都是以二值圖像來計算壓縮前數據量），而采用邊緣打包法時為5.24。如圖6所示，當圖像中存在大量短邊緣時，采用鏈碼編碼法的壓縮比為0.80，而采用邊緣打包法時為1.52，即采用鏈碼編碼法反而增加了數據量。

圖5 邊緣稀疏圖像Fig.5 Image with sparse edges

圖6 含大量短邊緣的圖像Fig.6 Image with plenty edges

在實際應用中，為盡可能減小輸出碼率，同時盡可能減少計算量，如何快速從兩種編碼方法中選擇其一，是下面要解決的問題。該問題可以看作一個二分類問題，本文引入Logistic回歸建立分類模型以實現編碼方法的自適應快速選擇。

2.2 Logistic回歸

Logistic回歸也叫對數幾率回歸，是一種基于Sigmoid函數的有監督分類模型，主要研究多個自變量與一個因變量之間的多元回歸關系。它的優點是［9］：1）無需事先假設數據分布；2）不僅可得到分類，還能得到近似概率；3）對數幾率函數是任意階可導的凸函數，有很好的數學性質，許多數值優化算法可以直接用于求解最優值。

建模的第1步是提取模型的特征。考慮到邊緣打包法的計算速度比鏈碼編碼法快很多，首先使用邊緣打包法對邊緣圖像進行編碼，記此時的壓縮率（壓縮比的倒數）為x1。另外，在邊緣提取過程中，加入統計邊緣點個數的功能，并求得邊緣點個數占所有像素的比例，記為x2。

對于回歸問題，常用的特征選擇方法有卡方檢驗、信息增益和分類器錯誤率等。卡方檢驗是一種基于χ2分布的假設檢驗方法，其基本思想是根據樣本數據推斷總體的分布與期望分布是否有顯著性差異，或者推斷2個分類變量是否相關或者獨立。本文使用卡方檢驗對x1、x2進行分析，隨機選取1組數據集，使用scikit?learn中基于卡方檢驗的特征選擇函數chi2，計算得到2個特征的χ2和 p?value，其分別是 56、142 和 6.0×10-14、6.5×10-33。說明特征的顯著性和相關性較好，x1、x2選擇合理。

以x1、x2作為自變量；編碼方法選擇的結果作為因變量，記為y，當y=1時選擇邊緣打包法，當y=0時選擇鏈碼編碼法。將自變量的線性組合z=θTx=θ0+θ1x1+θ2x2帶入到Sigmoid函數中建立概率預測函數

2.3 邊緣圖像自適應編碼流程

邊緣圖像自適應編碼流程如圖7所示，具體流程如下：

1）對輸入圖像按照圖1所示流程提取邊緣。

2）統計邊緣點數量，計算邊緣點比例x2。

3）按照圖3所示流程對邊緣圖像進行邊緣點打包壓縮，并計算壓縮比x1。

4）使用提前訓練好參數的概率預測函數，按照式（1）計算hθ（z）。如果hθ（z）＞50%，表示邊緣打包法的輸出數據量有更大概率小于鏈碼編碼法，直接輸出；如果hθ（z）≤50%，用圖4所示的鏈碼編碼法對邊緣圖像進行編碼輸出。

圖7 邊緣圖像自適應編碼流程框圖Fig.7 Flow chart for adaptive coding method of edge image

3 測試與分析

為了測試邊緣圖像自適應編碼性能，采用VOC2012圖像數據庫［10］作為測試源對算法壓縮比和處理時間進行測試，同時將測試結果與邊緣打包法和鏈碼編碼法進行對比。VOC2012是一個用于目標識別任務的圖像測試集合，包含人物、動物、車輛等20個種類的測試數據，即共約1萬張靜態圖片和一段5min（約9千幀）火箭發射監控視頻。測試環境為Windows 10，64位操作系統，i5?8250U CPU，8G內存。具體測試流程如下：

1）隨機選擇VOC2012中70%的數據作為訓練集，使用python語言的scikit?learn機器學習開發包，訓練系統的Logistic回歸模型，得到最佳參數θ。

2）使用余下的30%數據和視頻對邊緣打包法、鏈碼編碼法和使用參數θ下的自適應編碼算法進行邊緣圖像編碼壓縮。

3）計算不同方法的壓縮比，并統計每種方法的平均處理時間。

4）重復上述測試10次，并計算平均結果。

前2次測試結果和10次測試結果的平均值如表1所示。

表1 不同算法測試結果對比Table 1 Test results comparison of the three methods

從表1可以看出，在不同的θ值下，邊緣圖像自適應編碼法壓縮比相比邊緣打包法提高了約5%，比鏈碼編碼法提高了約20%；計算時間比邊緣打包法提高了約6%，比鏈碼編碼法降低了13%。

4 結論

本文針對無人系統中邊緣圖像高效壓縮問題，提出了一種邊緣圖像自適應編碼算法，該算法利用Logistic回歸建立分類模型，快速自適應地從邊緣打包法和鏈碼編碼法中選擇壓縮比最高的方法對邊緣圖像進行壓縮。對VOC2012圖像數據庫的測試結果表明，自適應編碼算法能提高邊緣圖像壓縮比5%左右，有效降低了數據量。