一種大數據背景下的圖像特征提取算法

常俊生+劉慧青+張永杰

【摘 要】提出一種基于中軸變換的圖像骨架特征提取算法，結合Hausdoff距離方法與二次誤差度量方案，對圖像數據進行簡化，最終獲得簡潔魯棒的骨架特征。使用自定義的數據集進行驗證，實驗證明，使用中軸變換的圖像骨架提取方法對邊界噪聲具有良好的抵抗性，在不明顯影響提取骨架速度的同時，能夠保證圖像骨架的精度。

【關鍵詞】大數據 圖像處理 中軸變換 圖像骨架特征

An Image Feature Extraction Algorithm Based on Big Data

[Abstract] An image feature extraction algorithm of image contour based on medial axis transform was proposed in this paper. Combined with Hausdoff distance method and quadric error metric， the image data can be simplified to get the concise robust contour feature. Experiments demonstrate by the custom data set that， on one hand， the proposed method has the good resistance to the boundary noise； on the other hand， it guarantees the accuracy of image contour without apparently impact on the contour extraction speed.

[Key words]big data image processing medial axis transform image contour feature

1 引言

大數據的飛速發展對海量數據的高效處理提出了很高的要求。圖像數據是大數據的重要組成部分，因為圖像通常為高維數據，并且含有豐富的信息，因此對海量圖像數據的存儲、傳輸、處理等來說都是重要課題。因此，對海量圖像進行處理，通常通過聚類分析進行特征學習得到目標圖像。

在圖像處理領域內，骨架便是一種良好的圖像特征。目前對于骨架尚無統一的定義，通常認為骨架是與目標圖像的拓撲結構相一致的細曲線。它能夠反映圖像數據的拓撲結構，除此以外，圖像數據骨架特征在圖像匹配、圖像檢索、數據壓縮、形狀變換等應用中也發揮著重要作用。

本文提出一種基于中軸變換的圖像數據骨架特征提取算法，聯合Hausdoff距離方法與二次誤差度量方法，對初始計算的中軸變換進行進一步處理，最終得到簡潔魯棒的骨架特征。

2 相關工作

大數據技術的發展給傳統圖像領域帶來了巨大的技術變革。隨著互聯網的發展，圖片數據指數式增長，在海量的圖片數據中獲取目標信息圖片，這是一項艱巨的任務[1]。分布式處理、云計算、機器學習等領域技術的發展給海量數據的處理帶來了新的機遇與挑戰。數據量的增加給圖像檢索等應用增加了難度[2-3]。因此，需要一種簡潔、便于存儲傳輸、檢索的表達方式表示圖像數據。其中，骨架便是一種能夠反映圖像骨架拓撲信息的良好的表達方式。

在圖像處理領域內，目前骨架還沒有明確統一的定義，常用中軸對骨架進行精確定義，因此本文對于骨架與中軸不加區分。骨架是對象檢測的一個重要信息，它描述了對象各個部分之間的聯系，即它與對象的拓撲是一致的[3-5]。從預分割的圖像中提取骨架是一個熱門的課題，提取的骨架特征能夠運用在基于形狀的對象匹配和識別中[6]。

本文提出一種使用中軸變換的圖像骨架特征提取方法。在預分割的圖片上，提取出目標對象輪廓，再計算輪廓的中軸變換。得到中軸后，先通過單邊Hausdoff距離方法去除毛刺中軸，再通過改進的二次誤差邊折疊方法對其進行簡化，最終得到簡潔魯棒的骨架。

3 使用中軸變換的圖像特征提取算法

3.1 中軸的基本定義

Blum在1967年提出中軸的概念，中軸描述為模型內最大內切圓圓心與半徑所組成的集合。如圖1所示，（a）圖為目標圖像輪廓，（b）圖為中軸的定義，其中藍色的圓即為最大的內切圓，（c）圖中粉色的線即為通過計算輪廓的Voronoi圖得到的中軸，（d）圖中粉色的線即為骨架。由圖1（c）可以看出，計算輪廓邊界得到的中軸含有很多噪聲，稱之為毛刺。這些毛刺，不利于骨架的應用，因此，需要對這些毛刺進行簡化處理。

3.2 中軸簡化規則

Sun等人[7]使用單邊Hausdoff距離對中軸進行簡化，單邊Hausdoff距離是指所有中軸點到所有輪廓點歐式距離減去半徑之差的最小絕對值的最大值。該距離能夠反映中軸簡化前后模型的改變程度。該方法能夠得到簡潔光滑的骨架，不過該方法在極端簡化情況下，比較耗費時間。

Thiery[8]改進二次誤差度量[9]，并將其運用于三維中軸球的簡化。Li[10]等人使用球二次誤差度量，對中軸網格進行簡化。二次誤差度量方法在中軸簡化過程中，在極端簡化情況下，不能很好地保證中軸的穩定性。所以本文首先使用單邊Hausdoff距離方法對初始中軸進行簡化，因為單邊Hausdoff距離方法在極端簡化情況下不能保證細節特征并且耗時嚴重。考慮到圖像數據的特性，再使用二次誤差度量的方法進行簡化。實驗證明，該方法能夠較高效地提取出簡潔魯棒的圖像骨架特征。邊折疊示意圖如圖2所示：

3.3 改進的二次誤差度量算法

二次誤差度量方法常使用在網格簡化過程中，本節將介紹改進二次誤差度量算法，并將其用在中軸簡化過程中。如圖2所示，每個圓都為中軸圓，（a）圖為簡化前的中軸圖，（b）圖為簡化后的中軸圖，圖中每個中軸圓均由v（x，y，r）組成，其中（x，y）為中軸圓圓心坐標，r為中軸半徑，則線段vivk為一條中軸邊eij，其中L1、L2、L3、L4分別為對應中軸圓的外公切線。圖2（a）中，n1、n2分別為vivj的外公切線的向外單位法向量。圖2（b）中藍色的中軸圓vg為中軸邊eij經過邊折疊后得到，以此達到簡化的目的。簡化過程中的代價函數定義為E（vi，vj）=e12+e22。vivj簡化后得到vg。為了統一計算，單位法向量n，再加一個分量1，即（x，y，1）。

因此，邊折疊代價公式如下：

其中vx即為邊折疊后新中軸圓的位置。由Garland[9]，

對式（1）進行簡化得：

其中，

A=n1.n1T+n2.n2T，

，

。

通過二次誤差最小化，則得到：

3.4 邊折疊算法

根據誤差函數，則每條中軸邊都含有一個折疊代價，對所有邊折疊代價進行排序，選擇最小的折疊代價的邊進行折疊簡化，這樣不停迭代，直到達到指定的簡化程度。

3.5 圖像骨架特征提取算法

本文提出的圖像骨架特征提取算法，在預分割的圖像上首先獲取圖像輪廓，再計算輪廓的中軸變換，得到初始的中軸。由于初始的中軸含有大量的噪聲信息，如圖1（c），因此，需要對得到的中軸進行進一步處理。本文首先通過單邊Hausdoff距離方法，對初始中軸進行簡化，該過程簡化是通過直接去除毛刺，當去除毛刺后，該中軸的Hausdoff距離保持在給定閾值以內。再使用改進的二次誤差度量進行簡化，最終得到簡潔的骨架特征。圖像骨架特征提取算法如下所示：

（1）輸入所有中軸邊以及中軸點集合，給定單邊Hausdoff距離閾值ε，給定二次誤差度量的剩余中軸點個數N。

（2）計算每條中軸邊去除的Hausdoff距離，選取Hausdoff距離最小的邊進行去除，判斷去除后單邊Hausdoff距離是否大于ε。是，跳轉到（3）；否則，跳轉到（2）。

（3）計算每條中軸邊的二次誤差代價，對所有中軸邊進行排序，選取最小的中軸邊進行邊折疊，將該中軸邊的兩個端點中軸圓從中軸圓集合中去除，將新得到的中軸圓加入該集合，更新所有與之相關聯的中軸點的三元組系數。

（4）判斷剩余中軸點集合中中軸點個數是否小于N。是，結束；否則，跳轉到（3）。

4 實驗設計與結果分析

4.1 實驗設計

本文實驗是在Windows7 Intel i7 8 GB內存上使用VS2013 C++完成的。實驗中，使用OpenCV對圖像進行輪廓提取。得到目標圖像輪廓后，使用CGAL中Delaunay三角化函數計算初始中軸。最后，通過單邊Hausdoff距離方法對得到的中軸進行簡化。簡化到給定閾值的時候，再使用二次誤差度量法進行簡化，最終得到簡潔魯棒的骨架。由于計算單邊Hausdoff距離的時間復雜度是O（n2），故本實驗時間復雜度即為O（n2）。

本文在自定義圖片數據集上進行實驗，對得到的圖片進行歸一化處理，所有圖片像素均在200×200～

300×300之間，并且得到的輪廓點數在800～1200。ε取0.05～0.08時，實驗結果較好，N取15～25時，最終得到的骨架準確性較高。不作特殊說明，本文ε取0.05，N取20。

4.2 實驗結果

圖3給出了本文算法與基于單邊Hausdoff距離方法的實驗比較結果。表1給出了算法執行的相關參數以及數據。從表1可看出，單邊Hausdoff距離方法簡化中軸比較耗費時間。另外，在極端簡化的情況下，本文算法能夠在不耗費太多時間的同時，提取得到簡潔魯棒的骨架特征。

另外，在簡化過程中，首先使用單邊Hausdoff距離再使用改進的二次誤差度量方法。這兩者之間切換時間，實驗證明，剩余中軸點數在初始中軸點數的10%時進行切換，此時ε在0.05～0.08之間取值。

5 結束語

移動媒體與互聯網的發展促進了圖像大數據的指數式增長。為了能夠高效地處理、檢索、存儲這些海量數據，需要對它們進行進一步處理。對原始圖片數據進行特征提取，這樣便于處理檢索存儲。本文提出的基于中軸變換的圖像特征提取算法能夠簡化圖像，得到簡潔魯棒的骨架特征，為后續的處理提供了便利。在保持精度的同時，也能保持圖像特征的魯棒性。

參考文獻：

[1] 趙銳. 基于大數據背景下的圖形處理技術變革探索[J]. 電子測試， 2014（20）： 143-144.

[2] 汪淼，張方略，胡事民. 數據驅動的圖像智能分析和處理綜述[J]. 計算機輔助設計與圖形學學報， 2015，27（11）： 2015-2024.

[3] 劉智慧，張泉靈. 大數據技術研究綜述[J]. 浙江大學學報：工學版， 2014，48（6）： 957-972.

[4] 張晶，馮林，王樂，等. MapReduce框架下的實時大數據圖像分類[J]. 計算機輔助設計與圖形學學報， 2014，26（8）： 1263-1271.

[5] 劉利釗，洪江水，劉莉莉，等. 面向大數據圖像處理的尺度空間挖掘算法及應用[J]. 上海交通大學學報， 2015，49（11）： 1731-1735.

[6] Demirci M F， Shokoufandeh A， Keselman Y， et al. Object recognition as many-to-many feature matching[J]. International Journal of Computer Vision， 2006（2）： 203-222.

[7] Sun F， Choi Y K， Yu Y， et al. Medial meshes for volume approximation[J]. Computer Science， 2013.

[8] Thiery J M， Guy ?， Boubekeur T. Sphere-Meshes： shape approximation using spherical quadric error metrics[J]. ACM Transactions on Graphics （TOG）， 2013（6）： 178.

[9] Garland M， Heckbert P S. Surface simplification using quadric error metrics[A]. Proceedings of the 24th annual conference on computer graphics and interactive techniques[C]. 1997： 209-216.

[10] Li P， Wang B， Sun F， et al. Q-MAT： Computing Medial Axis Transform By Quadratic Error Minimization[J]. ACM Transactions on Graphics （TOG）， 2015（1）： 8.