?？∩?劉慧青+張永杰

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

【關(guān)鍵詞】大數(shù)據(jù) 圖像處理 中軸變換 圖像骨架特征

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 引言

大數(shù)據(jù)的飛速發(fā)展對(duì)海量數(shù)據(jù)的高效處理提出了很高的要求。圖像數(shù)據(jù)是大數(shù)據(jù)的重要組成部分，因?yàn)閳D像通常為高維數(shù)據(jù)，并且含有豐富的信息，因此對(duì)海量圖像數(shù)據(jù)的存儲(chǔ)、傳輸、處理等來(lái)說(shuō)都是重要課題。因此，對(duì)海量圖像進(jìn)行處理，通常通過(guò)聚類(lèi)分析進(jìn)行特征學(xué)習(xí)得到目標(biāo)圖像。

在圖像處理領(lǐng)域內(nèi)，骨架便是一種良好的圖像特征。目前對(duì)于骨架尚無(wú)統(tǒng)一的定義，通常認(rèn)為骨架是與目標(biāo)圖像的拓?fù)浣Y(jié)構(gòu)相一致的細(xì)曲線。它能夠反映圖像數(shù)據(jù)的拓?fù)浣Y(jié)構(gòu)，除此以外，圖像數(shù)據(jù)骨架特征在圖像匹配、圖像檢索、數(shù)據(jù)壓縮、形狀變換等應(yīng)用中也發(fā)揮著重要作用。

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

2 相關(guān)工作

大數(shù)據(jù)技術(shù)的發(fā)展給傳統(tǒng)圖像領(lǐng)域帶來(lái)了巨大的技術(shù)變革。隨著互聯(lián)網(wǎng)的發(fā)展，圖片數(shù)據(jù)指數(shù)式增長(zhǎng)，在海量的圖片數(shù)據(jù)中獲取目標(biāo)信息圖片，這是一項(xiàng)艱巨的任務(wù)[1]。分布式處理、云計(jì)算、機(jī)器學(xué)習(xí)等領(lǐng)域技術(shù)的發(fā)展給海量數(shù)據(jù)的處理帶來(lái)了新的機(jī)遇與挑戰(zhàn)。數(shù)據(jù)量的增加給圖像檢索等應(yīng)用增加了難度[2-3]。因此，需要一種簡(jiǎn)潔、便于存儲(chǔ)傳輸、檢索的表達(dá)方式表示圖像數(shù)據(jù)。其中，骨架便是一種能夠反映圖像骨架拓?fù)湫畔⒌牧己玫谋磉_(dá)方式。

在圖像處理領(lǐng)域內(nèi)，目前骨架還沒(méi)有明確統(tǒng)一的定義，常用中軸對(duì)骨架進(jìn)行精確定義，因此本文對(duì)于骨架與中軸不加區(qū)分。骨架是對(duì)象檢測(cè)的一個(gè)重要信息，它描述了對(duì)象各個(gè)部分之間的聯(lián)系，即它與對(duì)象的拓?fù)涫且恢碌腫3-5]。從預(yù)分割的圖像中提取骨架是一個(gè)熱門(mén)的課題，提取的骨架特征能夠運(yùn)用在基于形狀的對(duì)象匹配和識(shí)別中[6]。

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

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

3.1 中軸的基本定義

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

3.2 中軸簡(jiǎn)化規(guī)則

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

Thiery[8]改進(jìn)二次誤差度量[9]，并將其運(yùn)用于三維中軸球的簡(jiǎn)化。Li[10]等人使用球二次誤差度量，對(duì)中軸網(wǎng)格進(jìn)行簡(jiǎn)化。二次誤差度量方法在中軸簡(jiǎn)化過(guò)程中，在極端簡(jiǎn)化情況下，不能很好地保證中軸的穩(wěn)定性。所以本文首先使用單邊Hausdoff距離方法對(duì)初始中軸進(jìn)行簡(jiǎn)化，因?yàn)閱芜匟ausdoff距離方法在極端簡(jiǎn)化情況下不能保證細(xì)節(jié)特征并且耗時(shí)嚴(yán)重?？紤]到圖像數(shù)據(jù)的特性，再使用二次誤差度量的方法進(jìn)行簡(jiǎn)化。實(shí)驗(yàn)證明，該方法能夠較高效地提取出簡(jiǎn)潔魯棒的圖像骨架特征。邊折疊示意圖如圖2所示：

3.3 改進(jìn)的二次誤差度量算法

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

因此，邊折疊代價(jià)公式如下：

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

對(duì)式（1）進(jìn)行簡(jiǎn)化得：

其中，

A=n1.n1T+n2.n2T，

，

。

通過(guò)二次誤差最小化，則得到：

3.4 邊折疊算法

根據(jù)誤差函數(shù)，則每條中軸邊都含有一個(gè)折疊代價(jià)，對(duì)所有邊折疊代價(jià)進(jìn)行排序，選擇最小的折疊代價(jià)的邊進(jìn)行折疊簡(jiǎn)化，這樣不停迭代，直到達(dá)到指定的簡(jiǎn)化程度。

3.5 圖像骨架特征提取算法

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

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

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

（3）計(jì)算每條中軸邊的二次誤差代價(jià)，對(duì)所有中軸邊進(jìn)行排序，選取最小的中軸邊進(jìn)行邊折疊，將該中軸邊的兩個(gè)端點(diǎn)中軸圓從中軸圓集合中去除，將新得到的中軸圓加入該集合，更新所有與之相關(guān)聯(lián)的中軸點(diǎn)的三元組系數(shù)。

（4）判斷剩余中軸點(diǎn)集合中中軸點(diǎn)個(gè)數(shù)是否小于N。是，結(jié)束；否則，跳轉(zhuǎn)到（3）。

4 實(shí)驗(yàn)設(shè)計(jì)與結(jié)果分析

4.1 實(shí)驗(yàn)設(shè)計(jì)

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

本文在自定義圖片數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，對(duì)得到的圖片進(jìn)行歸一化處理，所有圖片像素均在200×200～

300×300之間，并且得到的輪廓點(diǎn)數(shù)在800～1200。ε取0.05～0.08時(shí)，實(shí)驗(yàn)結(jié)果較好，N取15～25時(shí)，最終得到的骨架準(zhǔn)確性較高。不作特殊說(shuō)明，本文ε取0.05，N取20。

4.2 實(shí)驗(yàn)結(jié)果

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

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

5 結(jié)束語(yǔ)

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

參考文獻(xiàn)：

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

[2] 汪淼，張方略，胡事民. 數(shù)據(jù)驅(qū)動(dòng)的圖像智能分析和處理綜述[J]. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)， 2015，27（11）： 2015-2024.

[3] 劉智慧，張泉靈. 大數(shù)據(jù)技術(shù)研究綜述[J]. 浙江大學(xué)學(xué)報(bào)：工學(xué)版， 2014，48（6）： 957-972.

[4] 張晶，馮林，王樂(lè)，等. MapReduce框架下的實(shí)時(shí)大數(shù)據(jù)圖像分類(lèi)[J]. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)， 2014，26（8）： 1263-1271.

[5] 劉利釗，洪江水，劉莉莉，等. 面向大數(shù)據(jù)圖像處理的尺度空間挖掘算法及應(yīng)用[J]. 上海交通大學(xué)學(xué)報(bào)， 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.