王家潤(rùn)，任 菲，榮 明，羅童心

(1.華北計(jì)算技術(shù)研究所 基礎(chǔ)三部，北京 100083； 2. 國(guó)防大學(xué) 信息作戰(zhàn)與指揮訓(xùn)練教研部，北京 100091)

0 引言

人類的視覺大部分來自于形狀及顏色等視覺感知因素[1]。在軍事作戰(zhàn)符號(hào)體系中，不同國(guó)家對(duì)作戰(zhàn)符號(hào)顏色的使用等都有明確的規(guī)定[2-3]，作戰(zhàn)符號(hào)顏色的漸變填充具有重要的視覺增強(qiáng)作用：增強(qiáng)與背景的對(duì)比度，更加突出顯示作戰(zhàn)符號(hào)；增強(qiáng)進(jìn)攻類作戰(zhàn)符號(hào)等的作戰(zhàn)方向意圖的視覺表現(xiàn)等。

在二維圖形QT(一種跨平臺(tái)C++圖形用戶界面軟件)或圖形設(shè)備接口(Graphics Device Interface, GDI+)中，一般提供常用的中心徑向漸變、線性漸變等顏色漸變填充效果，但在三維圖形中沒有該類算法(一般采用掃描線種子填充算法等)，而且針對(duì)比較復(fù)雜的形狀，這些填充算法無法較好地實(shí)現(xiàn)沿形狀的主要延伸方向的顏色漸變填充效果。骨架(或中軸)能較好地表達(dá)形狀(或區(qū)域)的整體延伸趨勢(shì)，描述形狀的主要幾何特征，反映形狀的整體拓?fù)浣Y(jié)構(gòu)[4]；因此，針對(duì)復(fù)雜形狀的研究，通過其骨架可得到較大的簡(jiǎn)化。文獻(xiàn)[5]對(duì)骨架提取進(jìn)行了比較全面的論述；文獻(xiàn)[6]對(duì)在地理信息系統(tǒng)(Geographic Information System, GIS)中基于約束Delaunay三角剖分(Constrained Delaunay Triangulation, CDT)提取骨架進(jìn)行了比較研究；文獻(xiàn)[7]對(duì)圖像處理中的骨架提取算法進(jìn)行了分類并比較了優(yōu)缺點(diǎn)。骨架提取算法中存在的共性問題是骨架對(duì)輪廓細(xì)節(jié)過于敏感，從而產(chǎn)生很多的細(xì)小分枝[8-10]，這些細(xì)小分枝的存在給實(shí)際應(yīng)用帶來較大的困難，因此，冗余分枝的裁剪成為骨架提取研究中的難點(diǎn)。文獻(xiàn)[11]采取符合視覺特性的彎曲度比率(Bending Potential Ratio, BPR)抑制分枝，大部分的骨架提取算法采用的策略與之類似：在提取的過程中對(duì)骨架分枝按照一定的規(guī)則進(jìn)行裁剪。本文的主要工作有：

1)基于骨架路徑評(píng)價(jià)向量的骨架冗余分枝裁剪。

基于視覺顯著性評(píng)價(jià)向量，優(yōu)選出少量的骨架路徑，較好地抑制了骨架的冗余分枝。這種基于骨架路徑的整體選優(yōu)策略，與常用的基于骨架分枝進(jìn)行局部裁剪的方法不同。

2)基于形狀主骨架的顏色漸變填充。

對(duì)主骨架進(jìn)行顏色漸變計(jì)算，并將顏色計(jì)算拓展到整個(gè)形狀區(qū)域，實(shí)現(xiàn)了沿形狀延伸變化的漸變填充。而常用的中心徑向、線性漸變等填充樣式，一般較難實(shí)現(xiàn)該種效果。

1 形狀主骨架優(yōu)化及顏色漸變填充算法

1.1 算法整體流程

約束條件：限定形狀(或區(qū)域)為無洞的簡(jiǎn)單多邊形[4]；形狀的邊界點(diǎn)依次相連構(gòu)成封閉多邊形。

1) 輸入形狀的邊界點(diǎn)集合；顏色漸變開始與結(jié)束顏色。

2)過程如下：

①分解復(fù)雜區(qū)域?yàn)檩^簡(jiǎn)單區(qū)域；

②對(duì)各區(qū)域進(jìn)行約束Delaunay三角剖分；

③對(duì)三角形進(jìn)行分類，采用三角形中線法提取骨架構(gòu)建骨架二叉樹；

④采用路徑棧及搜索棧，提取骨架路徑集合；

⑤依據(jù)視覺顯著性評(píng)價(jià)向量，對(duì)骨架路徑進(jìn)行評(píng)價(jià)；

⑥依據(jù)評(píng)價(jià)結(jié)果，優(yōu)選出主骨架；

⑦對(duì)主骨架進(jìn)行幾何調(diào)整優(yōu)化；

⑧對(duì)主骨架進(jìn)行顏色漸變插值計(jì)算；

⑨依據(jù)主骨架，將區(qū)域邊界點(diǎn)分類，采用分組計(jì)算及點(diǎn)到線段的投影插值進(jìn)行漸變顏色拓展映射計(jì)算；

⑩將各區(qū)域進(jìn)行整體合成。

3)輸出與形狀的邊界點(diǎn)集合對(duì)應(yīng)的顏色集合。

1.2 算法詳細(xì)解析

1.2.1 CDT三角形中線法骨架提取

1)約束Delaunay三角剖分。

針對(duì)復(fù)雜形狀，可采用區(qū)域分解策略分解為比較簡(jiǎn)單的形狀[4]。在三維中的簡(jiǎn)單多邊形，如果存在凹點(diǎn)則不能進(jìn)行正確的渲染，需要進(jìn)行凸分解。三角形是最簡(jiǎn)單的凸多邊形，而且在三維圖形中渲染時(shí)，三角形是最基本的處理單元，顯卡也對(duì)三角形處理有一定的優(yōu)化。約束Delaunay三角剖分較好地解決了凹多邊形的凸分解問題，在計(jì)算機(jī)圖形中有廣泛的應(yīng)用，相關(guān)理論及算法也比較成熟[4,12]，而且Delaunay三角形的最小角最大特性使剖分產(chǎn)生的三角形避免了狹長(zhǎng)三角形，趨向等邊三角形，較大程度上保證了剖分的趨向均勻性，可使提取出的骨架抖動(dòng)性較小，更好地逼近理想的骨架。

2)CDT三角形中線法骨架提取。

CDT產(chǎn)生的三角形分為三種類型：Ⅰ類型，只有一條邊與其他三角形相鄰(虛線表示該邊與其他三角形相鄰)，如圖1(a)；Ⅱ類型，只有兩條邊與其他三角形相鄰，如圖1(b)；Ⅲ類型，每條邊都與其他三角形相鄰，如圖1(c)。基于上述分類，采用三角形中線(或重心)法提取三角形的骨架，參見圖1中三類三角形內(nèi)部各骨架線段，其中Ⅲ類型內(nèi)部含三段骨架線段。

從圖2中內(nèi)部較粗的骨架線可看出，骨架的端點(diǎn)是Ⅰ類三角形的邊界頂點(diǎn)；骨架的連接點(diǎn)是Ⅱ類三角形非邊界的內(nèi)部邊中點(diǎn)；骨架的分枝點(diǎn)是Ⅲ類三角形的重心。由文獻(xiàn)[12]可知，該方法提取的骨架不是嚴(yán)格意義上的骨架(或中軸)，只是近似骨架，但與三角形外心法骨架提取方法相比，該方法可保證骨架點(diǎn)在三角形內(nèi)部。使用角平分線方法[4]提取的骨架，一般在每一個(gè)凸點(diǎn)產(chǎn)生一個(gè)細(xì)小骨架分枝，圖2中至少會(huì)有8個(gè)細(xì)小骨架分枝，而CDT三角形中線法提取的骨架分枝則僅有3個(gè)，這說明CDT對(duì)骨架冗余分枝具有一定的裁剪能力。總體來看，CDT三角形中線法骨架提取方法具有計(jì)算簡(jiǎn)單、冗余骨架分枝較少、逼近理論骨架等優(yōu)點(diǎn)。

圖2 CDT三角形中線法提取骨架的示意圖 Fig. 2 Skeleton extraction by CDT triangular midline

1.2.2 骨架二叉樹構(gòu)建及遍歷

從CDT三角形中線法可看出，骨架在Ⅰ、Ⅱ類三角形內(nèi)部以一線段(該線段稱為骨架線段，線段的端點(diǎn)稱為骨架點(diǎn))表示，在Ⅲ類三角形內(nèi)部由3個(gè)線段組成。下面采用骨架節(jié)點(diǎn)對(duì)骨架線段進(jìn)行邏輯表達(dá)，骨架節(jié)點(diǎn)與骨架點(diǎn)、骨架線段、所在的三角形及出入邊等有關(guān)，整個(gè)骨架在邏輯上可組織為二叉樹。

1)骨架節(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)。

SkeletonNode

{

/*骨架節(jié)點(diǎn)所在的約束三角形索引，用于建立骨架節(jié)點(diǎn)與約束三角形的關(guān)聯(lián)*/

unsigned int triIndex;

/*骨架節(jié)點(diǎn)的2個(gè)端點(diǎn)在骨架點(diǎn)集中的索引，用于建立骨架節(jié)點(diǎn)與骨架點(diǎn)集的聯(lián)系*/

unsigned int skIndex1;

unsigned int skIndex2;

/*骨架線段方向標(biāo)志：當(dāng)所在的三角形為Ⅰ類型，從頂點(diǎn)到對(duì)邊置為1，否則為-1；當(dāng)所在的三角形為Ⅲ類型，從中心點(diǎn)到對(duì)邊置為-1，否則為1*/

int flag;

/*當(dāng)所在的三角形為Ⅱ類型，用ed1記錄入邊信息，ed2記錄出邊信息；當(dāng)所在的三角形為Ⅰ、Ⅲ類型時(shí)，只使用ed1，用于建立骨架節(jié)點(diǎn)與所在的三角形邊的聯(lián)系*/

Edge ed1;

Edge ed2;

//父子節(jié)點(diǎn)指針

SkeletonNode* pParent;

SkeletonNode* pLeft;

SkeletonNode* pRight;

//是否訪問標(biāo)志

bool visited;

}

2)骨架二叉樹的構(gòu)建。

a) //設(shè)置隊(duì)列qe，用于廣度優(yōu)先遍歷

std:: queue< SkeletonNode *> qe.

b) /*從CDT三角形集合中查找一個(gè)Ⅰ類三角形，取骨架線段，建立骨架節(jié)點(diǎn)pRoot，作為骨架二叉樹根節(jié)點(diǎn)，并將該骨架根節(jié)點(diǎn)入隊(duì)列qe*/

pRoot =createRootNode(CDT三角形集合);

qe.push(pRoot).

c) while(qe非空)

{

//獲取隊(duì)列前端節(jié)點(diǎn)指針

SkeletonNode* pCurNode = qe.front();

//隊(duì)列前端節(jié)點(diǎn)出隊(duì)列

qe.pop();

/*從節(jié)點(diǎn)pCurNode出發(fā)，依骨架走向，檢查相鄰的三角形：Ⅰ、Ⅱ類型生成1個(gè)骨架節(jié)點(diǎn)；Ⅲ類型生成3個(gè)骨節(jié)點(diǎn)，依據(jù)骨架生成走向?qū)⑷攵卧O(shè)為父節(jié)點(diǎn)，其余2段設(shè)為子節(jié)點(diǎn)。建立與節(jié)點(diǎn)pCurNode的父子關(guān)系，并將生成的節(jié)點(diǎn)加入到隊(duì)列qe中*/

pushSkeletonNode(pCurNode, qe).

}

3)骨架二叉樹的遍歷。

a) //設(shè)置棧sk，用于深度優(yōu)先遍歷

std::stack sk.

b)//將骨架二叉樹根節(jié)點(diǎn)入棧

sk.push(pRoot);

c)while(sk非空)

{

//獲取棧頂節(jié)點(diǎn)指針

SkeletonNode* pCurNode = sk.top();

//棧頂節(jié)點(diǎn)出棧

sk.pop();

//右子節(jié)點(diǎn)入棧

sk.push(pCurNode->pRight);

//左子節(jié)點(diǎn)入棧

sk.push(pCurNode->pLeft);

//訪問節(jié)點(diǎn)pCurNode中的信息

//pCurNode->visited…

}

1.2.3 骨架路徑雙棧跟蹤提取

骨架路徑[10]可采用骨架節(jié)點(diǎn)隊(duì)列、骨架點(diǎn)列等表示。從骨架二叉樹中根節(jié)點(diǎn)的選擇可看出，根節(jié)點(diǎn)只有1個(gè)孩子節(jié)點(diǎn)，從幾何的角度來看骨架的各分枝端點(diǎn)，骨架根節(jié)點(diǎn)與葉子節(jié)點(diǎn)是相同的，因此提取骨架路徑時(shí)把根節(jié)點(diǎn)與葉子節(jié)點(diǎn)等同處理。

1)骨架路徑提取。

兩節(jié)點(diǎn)之間的骨架路徑雙棧跟蹤提取過程如下。

a) std::vector< SkeletonNode*> path，保存輸出的骨架徑上的節(jié)點(diǎn)；std::stack ps(用于跟蹤骨架路徑，簡(jiǎn)稱路徑棧)；std::stack ss(用于放置搜索節(jié)點(diǎn)，簡(jiǎn)稱搜索棧)。

b) 骨架路徑的雙棧跟蹤提取基本流程，如圖3所示。

c) 補(bǔ)充說明。

對(duì)節(jié)點(diǎn)pNext進(jìn)行雙棧出入操作：

對(duì)pNext設(shè)置已訪問標(biāo)志；將pNext入路徑棧ps；將pNext未訪問過的所有相鄰節(jié)點(diǎn)加入到搜索棧ss。

雙棧相鄰檢查：

檢查路徑棧ps棧頂節(jié)點(diǎn)與搜索棧ss棧頂節(jié)點(diǎn)是否相鄰，如果非相鄰，將ps棧頂節(jié)點(diǎn)出棧，直至ps棧頂節(jié)點(diǎn)與ss棧頂節(jié)點(diǎn)相鄰為止。

雙棧過濾處理：

如果ps非空，檢查ps棧頂節(jié)點(diǎn)pTmp；ps出棧；ps非空，檢查ps棧頂pPre，檢查ss的棧頂pSS，如果pPre不是pTmp的子節(jié)點(diǎn)且pSS不是pTmp的子節(jié)點(diǎn)，將pTmp重新入棧ps。該處理主要是消除骨架分枝點(diǎn)的干擾，因?yàn)樵冖箢惾切沃?，有三段骨架線段，因此需要沿骨架路徑的走向，過濾掉不符合走向的骨架線段。

圖3 骨架路徑的雙棧跟蹤提取流程 Fig. 3 Flow chat of extracting skeleton path by double stacks

2)骨架路徑表達(dá)方式轉(zhuǎn)換。

在1)中獲取的是采用骨架節(jié)點(diǎn)表示的骨架路徑，在骨架繪制等應(yīng)用中也采用骨架點(diǎn)列的表示方式。從骨架路徑中的開始節(jié)點(diǎn)開始，按骨架節(jié)點(diǎn)中的骨架線段的走向及骨架端點(diǎn)信息，跟蹤出每一骨架線段的骨架端點(diǎn)索引，因?yàn)槊恳幌噜徆羌茳c(diǎn)重復(fù)兩次，故最后需要把中間的重復(fù)點(diǎn)索引刪除，即得到骨架路徑的骨架點(diǎn)列表示。

1.2.4 骨架路徑評(píng)價(jià)向量

已有的輪廓曲線演化骨架提取算法[13]中對(duì)邊界的輪廓點(diǎn)給出評(píng)價(jià)，度量該點(diǎn)對(duì)形狀的貢獻(xiàn)度，依據(jù)貢獻(xiàn)度簡(jiǎn)化輪廓。借鑒上述思想，針對(duì)骨架路徑也引入評(píng)價(jià)標(biāo)準(zhǔn)，主要選用骨架路徑面積(A)、骨架路徑長(zhǎng)度[10](L)、骨架路徑跨度(S) 3個(gè)指標(biāo)，組成骨架路徑評(píng)價(jià)向量M=(A,L,S)。

骨架路徑面積：骨架路徑中各節(jié)點(diǎn)所在的三角形的面積之和。特別注意，如果是該骨架節(jié)點(diǎn)所在的三角形是Ⅲ類型，則計(jì)算該骨架節(jié)點(diǎn)所在的三角形重心與關(guān)聯(lián)的邊構(gòu)成的小三角形的面積。

骨架路徑跨度：骨架路徑首尾兩個(gè)端點(diǎn)間的歐氏距離。

設(shè)計(jì)思想如下。

已有的視覺顯著性認(rèn)知研究[14]認(rèn)為：區(qū)域尺寸、突出等，是區(qū)域形狀顯著性的重要特征。骨架面積測(cè)量了該骨架路徑在視覺上占據(jù)的視覺范圍；骨架長(zhǎng)度刻畫了形狀的總體延伸變化；骨架跨度度量了形狀的某延伸方向的伸展程度，該思想來源于凸殼直徑概念。總體來看，這3個(gè)幾何測(cè)量指標(biāo)一定程度上可對(duì)骨架路徑進(jìn)行較好的整體性評(píng)價(jià)。

計(jì)算骨架的所有骨架路徑，計(jì)算出最大長(zhǎng)度、最大面積、最大跨度，對(duì)每條骨架路徑的3個(gè)測(cè)量指標(biāo)進(jìn)行歸一化處理，可使得骨架路徑評(píng)價(jià)向量具有平移、縮放、旋轉(zhuǎn)等不變性。

1.2.5 主骨架的優(yōu)選及幾何優(yōu)化

本文主骨架是指從骨架路徑集合中篩選出的較優(yōu)的骨架路徑，與傳統(tǒng)的已裁剪掉細(xì)小分枝的主骨架不同。

1)視覺顯著度及主骨架優(yōu)選。

從骨架路徑的構(gòu)建可知，骨架路徑的首尾兩個(gè)端點(diǎn)也是形狀的邊界點(diǎn)，因此可通過對(duì)骨架路徑評(píng)價(jià)向量評(píng)價(jià)形狀的邊界點(diǎn)，引入視覺顯著度來測(cè)量形狀上各邊界點(diǎn)的視覺顯著性。形狀上各邊界點(diǎn)的骨架視覺顯著度初始設(shè)為0，將最長(zhǎng)骨架路徑兩個(gè)端點(diǎn)對(duì)應(yīng)的邊界點(diǎn)的視覺顯著度增加1；將最大跨度的骨架路徑兩個(gè)端點(diǎn)對(duì)應(yīng)的邊界點(diǎn)的視覺顯著度增加1；將最大面積的骨架路徑兩個(gè)端點(diǎn)對(duì)應(yīng)的邊界點(diǎn)的視覺顯著度增加1，形狀的各邊界點(diǎn)視覺顯著度≥0。

通過引入邊界點(diǎn)的視覺顯著度，能較好地篩選出較優(yōu)的骨架路徑，輔助用戶更好地選擇出理想的骨架路徑。一般來說，主骨架基本可從視覺顯著度比較高的形狀邊界點(diǎn)篩選出，而這種較優(yōu)的視覺顯著點(diǎn)相對(duì)是比較少的。

2)主骨架的幾何優(yōu)化方法。

從骨架路徑篩選出的主骨架，從幾何的角度來看，主骨架應(yīng)該是形狀的“對(duì)稱軸”，一般針對(duì)主骨架需要進(jìn)一步進(jìn)行幾何調(diào)整優(yōu)化，才能實(shí)現(xiàn)視覺上更好的對(duì)稱。具體有3種幾何優(yōu)化方式。

a)端點(diǎn)刪除：一般主骨架端點(diǎn)附近骨架細(xì)小分枝變化較大，通過端點(diǎn)刪除可消除這類細(xì)小分枝，提取出的主骨架能更好地能反映形狀的主要幾何變化趨勢(shì)。在選擇刪除的端點(diǎn)時(shí)，可參考格式塔理論中的對(duì)稱性原則[1]成對(duì)地進(jìn)行選擇。

b)端點(diǎn)中移：將骨架端點(diǎn)進(jìn)行調(diào)整，如圖4中的A調(diào)整到鄰邊的中點(diǎn)A1、B調(diào)整到B1，從幾何的角度來看，更符合主骨架的“對(duì)稱軸”幾何特點(diǎn)。

c)中間彎曲消除：在主骨架的分枝點(diǎn)附近通常會(huì)有一個(gè)抖動(dòng)，如圖4中的D點(diǎn)，將D點(diǎn)消除，即將骨架線段ED、DF兩段采用新的線段EF替換，在幾何上會(huì)更光順。

圖4 主骨架的幾何優(yōu)化處理示意圖 Fig. 4 Main skeleton geometric optimization processing

通過對(duì)主骨架的幾何優(yōu)化，消除了骨架的細(xì)小分枝干擾等，主骨架更加簡(jiǎn)潔，也更加符合人類的視覺感知，可更好地服務(wù)于主骨架的顏色漸變插值計(jì)算。

1.2.6 主骨架的顏色漸變插值計(jì)算

設(shè)置顏色BeginColor、EndColor，對(duì)應(yīng)主骨架的首末端點(diǎn)，顏色采用四維向量(R，G，B，A)描述，分量取值范圍[0,1]，A是透明度。

1) 計(jì)算出主骨架的全長(zhǎng)skL；

2) 計(jì)算主骨架上各骨架點(diǎn)的顏色：

沿主骨架開始點(diǎn)到當(dāng)前骨架點(diǎn)的累加長(zhǎng)度skSum；主骨架上各點(diǎn)的顏色：

Color=BeginColor+(EndColor-BeginColor)*

skSum/skL

即對(duì)主骨架上各點(diǎn)的顏色進(jìn)行線性插值。

1.2.7 主骨架到形狀邊界的顏色映射

借鑒文獻(xiàn)[15]中的雙緩沖區(qū)、文獻(xiàn)[16]中的邊界向量及形態(tài)學(xué)細(xì)化算法[9]處理的思想，設(shè)計(jì)形狀內(nèi)部的主骨架到形狀邊界的整體區(qū)域的顏色填充。基本思想：將形狀的邊界點(diǎn)分為兩類：與主骨架直接關(guān)聯(lián)和非直接關(guān)聯(lián)。對(duì)直接關(guān)聯(lián)采用按關(guān)聯(lián)分組計(jì)算平均顏色的計(jì)算方法，對(duì)非直接關(guān)聯(lián)采用逐步由內(nèi)層向外層拓展的顏色計(jì)算方法；因此，將主骨架到形狀邊界的顏色映射過程也對(duì)應(yīng)劃分為Ⅰ、Ⅱ兩個(gè)階段。

主骨架到形狀邊界的顏色映射過程如下。

1)輸入形狀的邊界點(diǎn)集B；主骨架上各點(diǎn)顏色集C(依據(jù)1.2.6節(jié)，預(yù)先計(jì)算完成)。

2)主骨架到形狀邊界的顏色映射基本流程(包含第Ⅰ、Ⅱ兩個(gè)階段)，如圖5所示。

3)補(bǔ)充說明。

構(gòu)建邊界點(diǎn)pt關(guān)聯(lián)的約束骨架點(diǎn)集S：

在CDT分解的三角形集合中，搜索邊界點(diǎn)pt所在的三角形的邊，構(gòu)建pt關(guān)聯(lián)的約束邊集；在主骨架點(diǎn)集中，篩選出落在pt關(guān)聯(lián)的約束邊集上的主骨架點(diǎn)，構(gòu)建pt關(guān)聯(lián)的約束骨架點(diǎn)集S。

設(shè)置點(diǎn)pt的顏色ptColor為主骨架路徑端點(diǎn)的顏色：

取主骨架端點(diǎn)的顏色，并以該顏色作為C中與pt對(duì)應(yīng)的邊界點(diǎn)的顏色ptColor。

使用S計(jì)算點(diǎn)pt的顏色ptColor：

計(jì)算S中各點(diǎn)對(duì)應(yīng)的主骨架上的各點(diǎn)顏色的平均值，作為pt的顏色ptColor。

構(gòu)建index關(guān)聯(lián)的三角形集合T：

收集index對(duì)應(yīng)點(diǎn)所在的CDT分解三角形，構(gòu)建三角形集合T。

三角形tri中index點(diǎn)的顏色計(jì)算可行性判斷：

三角形tri中除index外的另外兩個(gè)頂點(diǎn)的顏色已全部計(jì)算過，且index對(duì)應(yīng)點(diǎn)的顏色計(jì)算還未完成，則返回True，可進(jìn)行顏色計(jì)算，否則，返回False。

特別注意：三角形tri中另兩個(gè)頂點(diǎn)顏色還沒有完成計(jì)算時(shí)，則無法計(jì)算index點(diǎn)的顏色，暫時(shí)先出隊(duì)列，重新追加到隊(duì)列Q的尾端，延遲這兩個(gè)頂點(diǎn)的顏色計(jì)算完成后再進(jìn)行計(jì)算。上述處理保證了從形狀內(nèi)層往外層逐步擴(kuò)展顏色計(jì)算，主要是解決非主骨架的骨架分枝上的各邊界點(diǎn)的顏色計(jì)算。

插值計(jì)算三角形tri中index點(diǎn)的顏色：

在三角形tri中index點(diǎn)的顏色計(jì)算已可行的前提下，則可直接使用三角形tri中另兩個(gè)頂點(diǎn)的顏色，通過插值計(jì)算index點(diǎn)的顏色ptColor。具體過程：計(jì)算該點(diǎn)到這兩個(gè)點(diǎn)組成線段的最近點(diǎn)，如果最近點(diǎn)是這兩個(gè)點(diǎn)中的某一個(gè)，直接取該點(diǎn)的顏色為ptColor，如果不是端點(diǎn)，則將該點(diǎn)投影到該線段上，在該線段上進(jìn)行顏色插值，計(jì)算出該投影點(diǎn)的顏色ptColor。

圖5 主骨架到形狀邊界的顏色映射流程 Fig. 5 Color computing from main skeleton to boundary

2 實(shí)驗(yàn)及分析

2.1 實(shí)驗(yàn)環(huán)境

顯卡：NVIDIA GeForce GTX 650 Ti；處理器：Intel Core 2 Quad CPU Q9500，2.83 GHz，內(nèi)存3.00 GB； 三維圖形引擎OSG[17]3.0.1；Visual Studio 2010 C++。

2.2 結(jié)果及分析

參考文獻(xiàn)[2]中的部分軍事作戰(zhàn)符號(hào)，構(gòu)建一般封閉多邊形、單箭頭、雙箭頭、集結(jié)地域等圖形作為實(shí)驗(yàn)對(duì)象。其中，針對(duì)雙箭頭進(jìn)行了形狀分解，利用左右兩部分幾何上的對(duì)稱性，在底部中間進(jìn)行分割，最后對(duì)雙箭頭左右兩部分進(jìn)行合成。

2.2.1 骨架提取及骨架路徑評(píng)價(jià)

1)基于CDT的三角形中線法提取骨架。

采用基于CDT的三角形中線法提取的各圖形骨架，如圖6中的各圖形內(nèi)部黑色粗線所示。

在表1中，角平分線法按邊界凸點(diǎn)數(shù)目統(tǒng)計(jì)骨架分枝，該方法提取的骨架分枝數(shù)目可代表理論骨架分枝的數(shù)目，帶*數(shù)字表示真實(shí)數(shù)值不小于此處值，例如單箭頭中部的彎曲部分還存在凸點(diǎn)等。通過表1中骨架分枝數(shù)目對(duì)比可看出，CDT三角形中線法對(duì)骨架細(xì)小分枝具有一定的裁剪能力。

圖6 骨架提取及視覺顯著性顯示效果 Fig. 6 Skeleton extraction and visual saliency display effects 表1 不同骨架提取算法骨架分枝數(shù)目對(duì)照 Tab. 1 Skeleton branch number of different skeleton extraction methods

形狀名稱角平分線法CDT三角形中線法(相對(duì)比值)一般多邊形83(37.5%)單箭頭5*3(60.0%)雙箭頭(左、右)6*4(66.6%)集結(jié)區(qū)域11*11(100.0%)

基本結(jié)論：提取的骨架基本符合圖形的幾何中軸；骨架提取完整，驗(yàn)證了三角形中線法骨架提取算法的正確性。CDT三角形中線法具有一定的骨架冗余分枝裁剪能力。

2)骨架路徑評(píng)價(jià)及優(yōu)選比。

表2 骨架路徑優(yōu)選前后數(shù)目統(tǒng)計(jì)表Tab. 2 Total number and ratio of optimized skeleton path

基本結(jié)論：通過對(duì)骨架路徑的面積、長(zhǎng)度、跨度等的評(píng)價(jià)，優(yōu)選出的骨架路徑基本符合人們對(duì)主骨架的選擇；較好地消除了大部分的骨架冗余分枝；集結(jié)區(qū)域圖形的優(yōu)選比已達(dá)5.5%，優(yōu)選出的骨架路徑數(shù)目有非常明顯的減少。實(shí)驗(yàn)結(jié)果驗(yàn)證了骨架路徑評(píng)價(jià)向量設(shè)計(jì)的合理性。

2.2.2 主骨架幾何優(yōu)化及顏色漸變插值計(jì)算

從優(yōu)選出的骨架路徑中，用戶可非常方便地選出主骨架。從圖6可看出，骨架端點(diǎn)附近及骨架分枝點(diǎn)附近，骨架抖動(dòng)比較大，為進(jìn)行顏色漸變填充，可進(jìn)一步簡(jiǎn)化，進(jìn)行一定的幾何調(diào)整，該階段可通過人機(jī)交互界面進(jìn)行輔助處理。對(duì)比圖6與圖7中的各對(duì)應(yīng)圖形，可看出幾何優(yōu)化前后的較大差異。具體采用的幾何優(yōu)化措施如下：

在一般多邊形(對(duì)比圖6(a)、圖7(a))中，對(duì)主骨架的兩個(gè)端點(diǎn)進(jìn)行了端點(diǎn)中移，中間的骨架分枝點(diǎn)處進(jìn)行了中間彎曲消除；在單箭頭(對(duì)比圖6(b)、圖7(b))中，在箭頭部分的兩個(gè)骨架端點(diǎn)進(jìn)行了端點(diǎn)刪除，刪除了端點(diǎn)附近的細(xì)小骨架分枝，對(duì)箭頭尾部的骨架端點(diǎn)進(jìn)行了端點(diǎn)中移；在雙箭頭(左)(對(duì)比圖6(c)、圖7(c))，對(duì)箭頭部分的兩個(gè)骨架端點(diǎn)進(jìn)行了端點(diǎn)刪除，對(duì)箭頭尾部的骨架端點(diǎn)進(jìn)行了端點(diǎn)中移；在雙箭頭(右)(對(duì)比圖6(d)、圖7(d))，對(duì)箭頭部分的兩個(gè)骨架端點(diǎn)進(jìn)行了端點(diǎn)刪除，對(duì)箭頭尾部的骨架端點(diǎn)進(jìn)行了端點(diǎn)中移，其中頭部增加了一個(gè)非視覺顯著點(diǎn)的刪除，尾部沒有選擇最優(yōu)的較大球端點(diǎn)，而是選擇了一個(gè)較小球端點(diǎn)，這樣可保證尾部的顏色計(jì)算與雙箭頭(左)的尾部一致；在集結(jié)地域(對(duì)比圖6(e)、圖7(e))中，選擇了接近較長(zhǎng)路徑的端點(diǎn)，明顯可看出原有較多的非顯著骨架路徑端點(diǎn)已被過濾掉。

圖7 主骨架幾何優(yōu)化及顏色漸變效果 Fig. 7 Main skeleton geometric optimization and color gradient filling

基本結(jié)論：通過比較幾何優(yōu)化前后效果，可看出這幾種幾何調(diào)整方式的合理性：經(jīng)過幾何優(yōu)化后，消除了較多的細(xì)小骨架分枝，幾何對(duì)稱性較好，主骨架更加簡(jiǎn)潔、對(duì)稱、美觀，符合對(duì)稱性美學(xué)原則，也滿足格式塔理論中的對(duì)稱性原則[1]，更加符合人類視覺感知，基本擬合形狀的主要延伸變化趨勢(shì)。

2.2.3 形狀整體的顏色漸變填充

1)單顏色透明度漸變填充。

采用紅色且只對(duì)透明度變化(雙顏色漸變處理過程相同)，參見圖8效果。

圖8 單顏色的形狀顏色透明度漸變效果 Fig. 8 Single color gradient filling effect

2)漸變填充樣式效果比較。

基于主骨架的漸變填充與線性漸變填充比較，參見圖9中虛線范圍部分。圖9(a)采用了基于主骨架的漸變填充，箭頭部分漸變自然，而且兩個(gè)箭頭頭部的顏色保證了一致性，滿足了實(shí)際應(yīng)用中箭頭部分顏色要求一致的需求；而圖9(b)中使用了從上到下的顏色線性漸變，兩個(gè)箭頭顏色無法保證，線性漸變填充在表達(dá)這種效果時(shí)比較困難。圖9(c)采用主骨架線性漸變，顏色變化沿主骨架走向變化，比較自然，符合人類的視覺感知；而圖9(d)中的顏色從右到左線性漸變，尾部的透明度變化沒有沿箭頭彎曲方向。從整體來看，圖9(c)的漸變填充效果比圖9(d)的效果更好。

圖9 兩種顏色漸變填充方法對(duì)比 Fig. 9 Comparison of main skeleton and linear color gradient filling methods

基本結(jié)論：基于主骨架的顏色漸變填充能擬合形狀的延伸走勢(shì)，驗(yàn)證了形狀的顏色漸變計(jì)算的合理性。與線性漸變填充相比，基于主骨架的顏色漸變填充對(duì)彎曲的條帶類等復(fù)雜區(qū)域的漸變填充效果更自然，但處理過程相對(duì)比較復(fù)雜，尤其是主骨架的選擇及幾何調(diào)整環(huán)節(jié)，需要較多的人機(jī)交互參與處理。在實(shí)際使用中，使用者可根據(jù)實(shí)際情況選擇適配的顏色漸變填充算法：形狀接近圓或矩形等，可采用中心徑向、線性漸變等顏色漸變填充；彎曲條帶類等復(fù)雜區(qū)域，宜采用基于主骨架的顏色漸變填充算法。

3 結(jié)語

本文基于CDT三角形中線法提取骨架，較好地裁剪了部分骨架冗余分枝；采用雙棧跟蹤技術(shù)提取出了骨架的全部路徑，基于提取的骨架路徑評(píng)價(jià)向量，對(duì)骨架路徑評(píng)價(jià)優(yōu)選，較好地抑制了骨架的冗余分枝，給骨架提取算法中冗余分枝裁剪這一共性難點(diǎn)的研究提供了一種新的思路；通過引入視覺顯著性，對(duì)主骨架進(jìn)行符合視覺感知的幾何優(yōu)化調(diào)整，并由主骨架的顏色漸變逐步外拓到整個(gè)區(qū)域的顏色映射，實(shí)現(xiàn)了一種基于主骨架的顏色漸變填充新樣式，具有較好的沿形狀延伸方向的顏色漸變填充效果。實(shí)驗(yàn)結(jié)果也進(jìn)一步驗(yàn)證了本文方法的有效性，但是基于主骨架的顏色漸變填充，處理過程相對(duì)復(fù)雜，應(yīng)用條件也有一定的局限，下一階段將主要研究：1)主骨架幾何優(yōu)化調(diào)整的自動(dòng)化處理，減少了人機(jī)交互，進(jìn)一步降低了復(fù)雜性；2)帶孔洞等復(fù)雜區(qū)域的顏色漸變填充，需將骨架的二叉樹拓展為更加通用的圖，以便進(jìn)一步拓展適用范圍。

參考文獻(xiàn)(References)

[1] 陳為,沈則潛,陶煜波.數(shù)據(jù)可視化[M].北京:電子工業(yè)出版社,2014: 47-81. (CHEN W, SHEN Z Q, TAO Y B. Data Visualization [M]. Beijing: Publishing House of Electronics Industry, 2014:47-81.)

[2] 王飛,吳官祥,閔連權(quán),等.軍用地圖與軍事要圖[M].北京:解放軍出版社,2013:213-215.(WANG F, WU G X, MIN L Q, et al. Military Map and Military Plotting [M]. Beijing: Chinese Peoples Liberation Army Publishing House, 2013: 213-215.)

[3] ESRI. Military analyst and Military OverLay Editor (MOLE)[EB/OL].[2017- 07- 03]. http://www.esri.com/industries/defense.

[4] 周培德.計(jì)算幾何——算法設(shè)計(jì)與分析[M].北京:清華大學(xué)出版社,2005: 43-206.(ZHOU P D. Computational Geometry—the Design and Analysis of Computer Algorithms [M]. Beijing: Tsinghua University Press, 2005:43-206.)

[5] 廖志武.2-D骨架提取算法研究進(jìn)展[J].四川師范大學(xué)學(xué)報(bào)(自然科學(xué)版),2009,32(5):676-688.(LIAO Z W. A survey of 2-D skeletonization algorithm [J]. Journal of Sichuan Normal University (Natural Science), 2009, 32(5): 676-688.)

[6] 邵春麗.GIS中多邊形中軸問題和算法研究[D].武漢:武漢大學(xué),2004:12-39.(SHAO C L. Problems of medial axis of a simple polygon in GIS and its algorithm [D]. Wuhan: Wuhan University, 2004: 12-39.)

[7] 刁智華,吳貝貝,毋媛媛,等.基于圖像處理的骨架提取算法的應(yīng)用研究[J].計(jì)算機(jī)科學(xué),2016,43(6A): 232-235.(DIAO Z H, WU B B, WU Y Y, et al. Application research of skeleton extraction algorithm based on image processing[J]. Computer Science, 2016, 43(6A): 232-235.)

[8] 孫德超,辛士慶,周亞訓(xùn),等.重要性驅(qū)動(dòng)的中軸線[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào),2016,28(12):2107-2113.(SUN D C, XIN S Q, ZHOU Y X, et al. Importance driven medial axis [J]. Journal of Computer-Aided Design & Computer Graphics, 2016, 28(12): 2107-2113.)

[9] 王婉心,賈立鋒.骨架提取中的毛刺去除方法[J].廣東工業(yè)大學(xué)學(xué)報(bào),2014,31(4):90-94.(WANG W X, JIA L F. The method of removing burrs in skeleton extraction [J]. Journal of Guangdong University of Technology, 2014, 31(4): 90-94.)

[10] 鄭加寬.基于骨架特征的形狀識(shí)別方法研究[D].南昌:南昌航空大學(xué),2014:1-44.(ZHENG J K. Research on shape recognition method based on skeleton features [D]. Nangchang: Nanchang Hangkong University, 2014:1-44.)

[11] 周丹鳳.視覺顯著性特征約束下的形狀骨架提取與分解研究[D].合肥:合肥工業(yè)大學(xué),2013:10-45.(ZHOU D F. Shape skeleton extraction and shape decomposition based on visual saliency features [D]. Hefei: Hefei University of Technology, 2013:10-45.)

[12] 王曉燕,羅靜,郭光毅,等.一種構(gòu)建復(fù)雜平面圖形中軸的方法[J].地理空間信息,2015, 13(4):120-122.(WANG X Y, LUO J, GUO G Y, et al. Constructing method for approximate medial axis of planar free-form shape [J]. Geospatial Information, 2015, 13(4): 120-122.)

[13] 高立青,王延章.基于截線法的快速骨架提取算法[J].自動(dòng)化學(xué)報(bào), 2016, 42(7): 1100-1112.(GAO L Q, WANG Y Z. A fast algorithm of skeleton extraction based on secant line method [J]. Acta Automatica Sinica, 2016, 42(7): 1100-1112.)

[14] 劉雨.基于邊界特征點(diǎn)提取的網(wǎng)格分割[D].長(zhǎng)春:吉林大學(xué),2016:1-31.(LIU Y. Mesh segmentation via boundary feature points extraction [D]. Changchun: Jilin University, 2016: 1-31.)

[15] 劉小鳳,吳艷蘭,胡海.面狀要素的多層次骨架線提取[J].測(cè)繪學(xué)報(bào),2013,42(4):588-594.(LIU X F, WU Y L, HU H. A method of extraction multiscale skeletons for polygonal shapes [J]. Acta Geodaetica et Cartographica Sinica, 2013, 42(4): 588-594.)

[16] 胡斯淼,任洪娥,于鳴,等.基于向量?jī)?nèi)積的新型骨架提取方法[J].液晶與顯示,2015,30(5):844-850.(HU S M, REN H E, YU M, et al. A new skeleton extraction method based on vector inner production [J]. Chinese Journal of Liquid Crystals and Displays, 2015, 30(5): 844-850.)

[17] OpenSceneGraph (OSG) [EB/OL]. [2017- 07- 03]. http://www.openscenegraph.com.

This work is partially supported by the National Natural Science Foundation of China (61703412), the China Postdoctoral Science Foundation (2016M602996).

WANGJiarun, born in 1968, M. S., senior engineer. His research interests include virtual reality, high performance computing, data visualization.

RENFei, born in 1985, M. S., engineer. Her research interests include virtual reality, data visualization.

RONGMing, born in 1978, Ph. D., lecturer. His research interests include war simulation, strategic war game, weapons and equipment system simulation.

LUOTongxin, born in 1994, M. S. candidate. Her research interests include virtual reality, data visualization.