劉 鋰，段芃芃

(成都理工大學(xué) 工程技術(shù)學(xué)院，四川 樂(lè)山 614007)

0 引 言

邊緣檢測(cè)算法在模式識(shí)別、圖像處理、遙感應(yīng)用、人工智能以及聚類(lèi)數(shù)據(jù)的處理中有著廣泛的應(yīng)用?；镜倪吘墮z測(cè)算法包括凸殼算法[1-3]和凹包算法。

凸殼算法的研究有卷包裹法、格雷厄姆方法、分治算法、圖像目標(biāo)外接多邊形及凸殼的一種構(gòu)造方法[4]、平面海量散亂點(diǎn)集凸殼算法[5]和坐標(biāo)排序的離散點(diǎn)凸包生成算法[6]等。凸殼是幾何圖形的一種基本結(jié)構(gòu)，凸殼算法在實(shí)現(xiàn)邊界檢測(cè)和數(shù)據(jù)分析中有著重要的作用，凸殼求取的是覆蓋所有點(diǎn)的凸多邊形，由于限定了一定是凸多邊形，適用于點(diǎn)群全局結(jié)構(gòu)的描述，可以很好地描述點(diǎn)群的作用邊界，但是很難準(zhǔn)確地體現(xiàn)出凹多邊形的點(diǎn)群作用區(qū)域的邊界。

凹包算法可以準(zhǔn)確地反映多邊形的點(diǎn)群作用區(qū)域的邊界。對(duì)于凹包(concave hull)來(lái)說(shuō)，與凸殼的區(qū)別是，凸殼是明確定義了幾何形狀為凸多邊形，而凹包沒(méi)有明確的幾何定義，針對(duì)的是不規(guī)則的點(diǎn)集，可以有各種各樣的凹包，也可以看成是一種廣義的參數(shù)化的凸包。目前凹包算法的研究有Alpha shape算法[7-8]、基于Delaunay三角化算法[9]、滾邊算法(edge pivoting)和滾球法(ball pivoting)。凹包算法能準(zhǔn)確地實(shí)現(xiàn)離散點(diǎn)群的邊界檢測(cè)，但是具有較大的局限性，在數(shù)據(jù)量不大的情況下有較好的實(shí)現(xiàn)效果，離線(xiàn)點(diǎn)的幾何距離也有一定的限制。為此李雯靜等研究了《凸殼內(nèi)縮法進(jìn)行多密度離散點(diǎn)群邊界檢測(cè)》[10]，采用該方法可以突破以上的限制，該方法利用角度進(jìn)行凸殼內(nèi)縮，較好地實(shí)現(xiàn)了離散點(diǎn)的邊緣檢測(cè)[11-15]，但是只針對(duì)高密的點(diǎn)群數(shù)據(jù)，沒(méi)有考慮到出現(xiàn)離散點(diǎn)內(nèi)存在距離較大跨度時(shí)的情況。文中提出一種基于角度搜索和距離判定的凸殼內(nèi)縮算法，解決了上述問(wèn)題，較好地實(shí)現(xiàn)了離散點(diǎn)群邊緣檢測(cè)。

1 算法思想

1.1 建立凸殼

設(shè)離散點(diǎn)群為N，建立邊界數(shù)組S，以離散點(diǎn)群的上、右、下、左4個(gè)點(diǎn)為邊界頂點(diǎn)建立離散點(diǎn)群凸殼，如圖1所示，并將這4個(gè)點(diǎn)依次添加到邊界數(shù)組中。具體公式如下：

S=[S上,S右,S下,S左]

(1)

其中，S上代表離散點(diǎn)群N中y坐標(biāo)最大的點(diǎn)，S右代表離散點(diǎn)群N中x坐標(biāo)最大的點(diǎn)，S下代表離散點(diǎn)群N中y坐標(biāo)最小的點(diǎn)，S左代表離散點(diǎn)群N中x坐標(biāo)最小的點(diǎn)。即：

S上=(x,ymax)

(2)

S右=(xmax,y)

(3)

S下=(x,ymin)

(4)

S左=(xmin,y)

(5)

圖1 離散點(diǎn)群凸殼

1.2 角度搜索凸殼內(nèi)縮

角度搜索就是設(shè)置一個(gè)最佳閾值角度，根據(jù)角度進(jìn)行判斷，內(nèi)縮方法求凹多邊形的頂點(diǎn)，根據(jù)凹包的幾何特性，通常情況下閾值角度值的范圍在[0.5π，π)之間。依次取出邊界數(shù)組中兩個(gè)相鄰邊界點(diǎn)a、b，若點(diǎn)群中某點(diǎn)O與a、b所成角度大于閾值角度α(經(jīng)過(guò)文中數(shù)據(jù)驗(yàn)證的最佳閾值角度α=0.575π)，并且該點(diǎn)的角度是其他所有點(diǎn)與a、b所成角度中最大的一個(gè)，如圖2(a)所示。則該點(diǎn)為a、b的中間邊界點(diǎn)，該點(diǎn)為內(nèi)縮凹多邊形的頂點(diǎn)，如圖2(b)所示。并將該點(diǎn)添加到邊界數(shù)組S中，依次循環(huán)邊界數(shù)組S直到不存在O點(diǎn)為止，找到了所有的離散邊界點(diǎn)，如圖2(c)所示。

圖2 角度法凸殼內(nèi)縮過(guò)程

為角度檢驗(yàn)設(shè)置固定的閾值的原因在于，如不設(shè)置閾值，任意兩點(diǎn)a、b都會(huì)存在一個(gè)點(diǎn)O與a、b兩點(diǎn)所成角度是所有點(diǎn)中的最大值，因此在實(shí)際的運(yùn)算中會(huì)出現(xiàn)無(wú)限死循環(huán)的情況。

具體的計(jì)算公式如下：

(6)

(7)

(8)

(9)

其中，ab為點(diǎn)a、b間的距離，ob為點(diǎn)o、b間的距離，oa為點(diǎn)o、a間的距離；(xa,ya)代表a點(diǎn)坐標(biāo)，(xb,yb)代表b點(diǎn)坐標(biāo)，(xo,yo)代表o點(diǎn)坐標(biāo)；cosaob為點(diǎn)a、o、b之間的夾角余弦值。

a、o、b之間的夾角計(jì)算公式為：

α=arccosaob

(10)

邊界點(diǎn)角度判定條件為：

α>0.575π&&α>αmax

(11)

其中，αmax表示其他所有點(diǎn)與a、b所成角度的最大值。

1.3 距離判斷檢驗(yàn)二次內(nèi)縮

文中采用的實(shí)驗(yàn)數(shù)據(jù)是針對(duì)樂(lè)山市市中區(qū)商業(yè)中心聚類(lèi)分析的離散點(diǎn)數(shù)據(jù)，由于研究的是整個(gè)城市區(qū)域，出現(xiàn)了離散數(shù)據(jù)之間大距離跨度的問(wèn)題，采用角度法凸殼內(nèi)縮，實(shí)現(xiàn)的邊緣檢測(cè)效果如圖3所示。

從圖3中可看出，樂(lè)山市區(qū)的城市建設(shè)都是圍繞著綠心公園進(jìn)行的，直接導(dǎo)致了樂(lè)山市區(qū)的整體分布呈現(xiàn)整體內(nèi)凹的特點(diǎn)。整體內(nèi)凹是相對(duì)于局部?jī)?nèi)凹而言的，所謂整體內(nèi)凹是數(shù)據(jù)的總體分布是呈現(xiàn)向內(nèi)凹陷的特點(diǎn)，局部?jī)?nèi)凹則是在某一小區(qū)域呈現(xiàn)向內(nèi)凹陷。在采用角度法進(jìn)行內(nèi)縮之后會(huì)出現(xiàn)圖3所示的情況。因此，對(duì)應(yīng)用角度法產(chǎn)生的邊界提出了二次距離檢驗(yàn)即邊長(zhǎng)檢驗(yàn)。對(duì)圖3進(jìn)行分析可以發(fā)現(xiàn)，異常邊ab的長(zhǎng)度遠(yuǎn)遠(yuǎn)大于其他正常邊的長(zhǎng)度，并且其他所有點(diǎn)與a、b所成角度最大的點(diǎn)O'點(diǎn)的角度αmax小于角度判定閾值0.575π，因此，這兩點(diǎn)之間實(shí)際上并不存在一個(gè)O點(diǎn)(O點(diǎn)與a、b兩點(diǎn)所成的角度大于0.575π，且是其他所有點(diǎn)與ab所成角度的最大值)。造成這種現(xiàn)象的原因在于分析數(shù)據(jù)呈現(xiàn)整體內(nèi)凹的特點(diǎn)，而a、b兩點(diǎn)又剛好存在于內(nèi)縮部分的兩個(gè)頂點(diǎn)位置，這就使得所有數(shù)據(jù)都呈現(xiàn)出了一種遠(yuǎn)離a、b兩點(diǎn)的趨勢(shì)。而當(dāng)兩點(diǎn)固定第三點(diǎn)未知的情況下的時(shí)候，第三點(diǎn)與a、b兩點(diǎn)的距離遠(yuǎn)會(huì)造成a、b兩點(diǎn)與第三點(diǎn)所成角度也會(huì)存在變小的趨勢(shì)。

圖3 角度法凸殼內(nèi)縮邊界

針對(duì)以上問(wèn)題，提出了邊長(zhǎng)檢驗(yàn)二次內(nèi)縮。當(dāng)ab間距離大于給定的距離閾值時(shí)，邊界判定條件為，依次取出邊界數(shù)組中兩個(gè)相鄰邊界點(diǎn)a、b，若點(diǎn)群中某點(diǎn)O與a、b所成角是其他所有點(diǎn)與a、b所成角度中最大的一個(gè)。具體的公式如下：

當(dāng)Lab>M時(shí)，邊界點(diǎn)角度判定條件為：

α'>αmax

(12)

其中，αmax表示其他所有點(diǎn)與a、b所成角度的最大值。

M為存在較大距離跨度值中的最小值。

M=Min{L1,L2,…,Ln}

采用SPSS 21.0軟件對(duì)數(shù)據(jù)進(jìn)行分析處理，兩組患者的AST、ALT、ALB、AKP、Cr、BUN、DBIL、TBIL水平等計(jì)量資料用（均數(shù)±標(biāo)準(zhǔn)差）表示，用t檢驗(yàn)，檢驗(yàn)水準(zhǔn)α=0.05，以P＜0.05表示差異具有統(tǒng)計(jì)學(xué)意義。

(13)

其中，Ln為較大跨度的距離。

2 算法實(shí)現(xiàn)

(1)獲取數(shù)據(jù)：獲取已知聚類(lèi)分析數(shù)據(jù)的離散點(diǎn)，并將其保存在數(shù)組N中。

(2)建立凸殼，對(duì)數(shù)組N進(jìn)行循環(huán)，通過(guò)式(2)～式(5)計(jì)算上、右、下、左四個(gè)頂點(diǎn)坐標(biāo)，建立初始的凸殼，并將四個(gè)頂點(diǎn)坐標(biāo)值保存在邊界數(shù)組S。

(3)內(nèi)縮算法實(shí)現(xiàn)：

①循環(huán)邊界數(shù)組S。

②取出相鄰的兩個(gè)點(diǎn)a、b。

④找出a、b間的一點(diǎn)o，通過(guò)式(6)～式(10)計(jì)算出ab和α，根據(jù)式(11)進(jìn)行角度判定，若找到滿(mǎn)足角度的點(diǎn)，替換αmax，記錄該點(diǎn)下標(biāo)。若找不到滿(mǎn)足角度的點(diǎn)，則進(jìn)行邊長(zhǎng)的二次驗(yàn)證，根據(jù)式(11)、式(12)進(jìn)行判斷，若滿(mǎn)足條件，替換αmax，記錄該點(diǎn)下標(biāo)。

⑤進(jìn)入下一次離散點(diǎn)集合數(shù)組N循環(huán)。

⑥離散點(diǎn)集合數(shù)組N循環(huán)結(jié)束，將αmax對(duì)應(yīng)點(diǎn)加入到邊界數(shù)據(jù)S中的a、b之間。

⑦進(jìn)入下一次邊界數(shù)組S循環(huán)。

⑧邊界數(shù)組S循環(huán)結(jié)束，即找到了所有的邊界點(diǎn)數(shù)據(jù)，繪制邊界線(xiàn)，進(jìn)行成果顯示。

(4)成果顯示，循環(huán)邊界數(shù)組S，繪制邊界線(xiàn)，進(jìn)行成果展示。

3 實(shí)驗(yàn)分析

以樂(lè)山市市中區(qū)156平方公里為研究對(duì)象區(qū)域，研究數(shù)據(jù)共有12類(lèi)不同的要素的屬性數(shù)據(jù)，數(shù)據(jù)信息近12余萬(wàn)條，要素信息有商業(yè)區(qū)、行政單位、住宿小區(qū)、醫(yī)院、加油站、街道、公交路線(xiàn)、學(xué)校、大型購(gòu)物中心、車(chē)站、城市綠地、酒店等。測(cè)試數(shù)據(jù)為對(duì)研究對(duì)象進(jìn)行商業(yè)聚類(lèi)分析的離散數(shù)據(jù)，采用文中方法對(duì)聚類(lèi)分析的數(shù)據(jù)進(jìn)行邊緣的檢測(cè)和邊界的描繪。具體的數(shù)據(jù)分析如表1所示。

表1 數(shù)據(jù)分析

由表1數(shù)據(jù)可以看出，當(dāng)判定閾值增大時(shí)，邊界點(diǎn)的數(shù)量減少且繪制的實(shí)際邊界圖的邊界也變得更加的“粗糙”。如圖4(a)，當(dāng)邊界判定閾值為0.5π時(shí)，實(shí)現(xiàn)的邊界效果較好，但是邊界過(guò)于銳利不能很好地反映離散數(shù)據(jù)的實(shí)際邊界情況；當(dāng)邊界判定閾值大于0.6π時(shí)，如圖4(d)所示，邊界又過(guò)于粗糙，并且隨著判定閾值的增加粗糙程度還在不斷增加。圖4(b)和圖4(c)當(dāng)判定閾值為0.55π和0.575π時(shí)，邊界數(shù)據(jù)相對(duì)較好，在繪制的數(shù)據(jù)邊界相對(duì)圓滑，也能較好地反映聚類(lèi)數(shù)據(jù)的邊界。因此，文中將0.575π作為最終的判定閾值。

圖4 不同角度的邊界效果

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

提出的基于角度搜索和距離判定的凸殼內(nèi)縮算法，考慮了不同程度離散數(shù)據(jù)的情況，同時(shí)也考慮了存在距離跨度較大的情況，針對(duì)距離跨度較大導(dǎo)致角度法內(nèi)縮失效的情況，進(jìn)行了數(shù)據(jù)的分析和研究，通過(guò)設(shè)定距離的閾值對(duì)距離驗(yàn)證和判斷進(jìn)行了二次內(nèi)縮，較好地實(shí)現(xiàn)了離散數(shù)據(jù)的邊界檢測(cè)。通過(guò)具體的實(shí)驗(yàn)數(shù)據(jù)驗(yàn)證，采用該方法實(shí)現(xiàn)的效果較好，繪出的邊界數(shù)據(jù)精準(zhǔn)度較高。在該算法中，根據(jù)凹邊形的幾何特性，采用角度法和邊長(zhǎng)的二次驗(yàn)證進(jìn)行邊界的判斷，簡(jiǎn)化了凹包算法的復(fù)雜度，算法簡(jiǎn)潔高效，便于實(shí)現(xiàn)。通過(guò)實(shí)際的數(shù)據(jù)證明，該算法在不同程度的離散數(shù)據(jù)的情況下，邊界數(shù)據(jù)檢測(cè)精度高，異常數(shù)據(jù)小，邊界間區(qū)別明顯，能夠準(zhǔn)確甄別出區(qū)域邊界；在出現(xiàn)較大跨度的離散數(shù)據(jù)的情況下，該算法能夠適應(yīng)存在較大距離跨度的空間分布的特點(diǎn)，并能得到準(zhǔn)確的邊界精度。但是在執(zhí)行該算法時(shí)，還存在一些問(wèn)題，對(duì)判斷的閾值角度和判定的邊長(zhǎng)距離需要進(jìn)行多次試驗(yàn)才能求出最佳值，因此下一步將重點(diǎn)研究閾值角度和判定的邊長(zhǎng)距離的最優(yōu)解方法，以進(jìn)一步簡(jiǎn)化數(shù)據(jù)實(shí)驗(yàn)的過(guò)程。