《電子技術(shù)應(yīng)用》
您所在的位置:首頁 > 其他 > 業(yè)界動態(tài) > 基于掃描線轉(zhuǎn)換的快速等值線填充算法

基于掃描線轉(zhuǎn)換的快速等值線填充算法

2008-06-10
作者:鄧 飛1,王美平1,,周 杲2

  摘 要: 提出了一種基于掃描線轉(zhuǎn)換的等值線" title="等值線">等值線快速填充算法,。與現(xiàn)有的逐點掃描法和區(qū)域填充算法相比,該算法既不需要進行逐點插值" title="插值">插值計算,,也不需要追蹤等值區(qū)域,,判斷區(qū)域包含關(guān)系,因而填充速度很快,,且填充結(jié)果與區(qū)域填充法結(jié)果一致,。實踐證明該算法可以在毫秒級完成等值線圖的填充。
  關(guān)鍵詞: 等值線 掃描線 填充


  等值線圖在地質(zhì),、物探,、水文等許多工程領(lǐng)域都有廣泛的應(yīng)用,因此等值線圖的自動生成問題一直是人們研究的熱點,。一般等值線圖的生成分為等值線生成和等值線填充兩個部分,。目前,等值線的生成方法已經(jīng)很成熟,最常用的是等值線追蹤算法" title="等值線追蹤算法">等值線追蹤算法,。近年來關(guān)于等值線填充算法的研究也很多,,大致可分為掃描填充和區(qū)域填充兩類。其中掃描填充法出現(xiàn)較早,,它通過插值計算每個待填充點的顏色值,,進行逐點填充。算法簡單,、可靠,,但是填充速度慢,,而且與追蹤法生成的等值線存在一些細(xì)微差異,,因此目前關(guān)于掃描填充的研究已經(jīng)不多了。區(qū)域填充算法出現(xiàn)較晚[1],,是研究的熱點,。算法的基本思想是尋找等值區(qū)域,然后利用圖形庫的多邊形填充函數(shù)進行充填,。該算法對于填充大幅等值線圖效果明顯,,但是由于需要追蹤等值區(qū)域并且判斷區(qū)域包含關(guān)系,因此算法比較復(fù)雜,,而且對于等值線較多的情況,,處理速度也較慢。
  考慮到前面兩種算法的不足,,本文借鑒了圖形學(xué)中關(guān)于多邊形快速填充的經(jīng)典算法——掃描線轉(zhuǎn)換算法" title="轉(zhuǎn)換算法">轉(zhuǎn)換算法[2],,提出了一種利用掃描線填充等值線圖的快速算法。該算法利用掃描線與等值線的拓?fù)潢P(guān)系確定填充顏色,,并充分利用掃面線間的相關(guān)性快速填充,。無需計算每個填充點的顏色值,也無需尋找等值區(qū)域后再進行多邊形填充,,因此速度明顯優(yōu)于前兩類填充算法,,而且填充效果與區(qū)域填充算法一致。
1 等值線追蹤算法
  等值線追蹤是生成等值線圖的第一步,。目前等值線追蹤算法的研究已經(jīng)比較成熟,,根據(jù)追蹤的原始數(shù)據(jù)不同,分為規(guī)則矩形網(wǎng)格追蹤[3]和三角網(wǎng)追蹤[4]兩類,。其中常用的等值線繪制軟件Surfer就是基于矩形數(shù)據(jù)網(wǎng)格的,。當(dāng)然矩形網(wǎng)格不能用于不規(guī)則的圖形,因此后來又出現(xiàn)了基于三角網(wǎng)的等值線追蹤方法,。本文主要介紹等值線填充算法,,因為填充算法僅需要利用等值線追蹤的結(jié)果,而與具體采用何種追蹤方法無關(guān),因此這里不過多討論等值線追蹤算法,,僅以矩形網(wǎng)格追蹤為例進行簡要說明,。
  等值線追蹤的第一步是,計算出所有對應(yīng)某一值的等值點在網(wǎng)格邊線上的坐標(biāo),。這對于矩形網(wǎng)格來說比較簡單:先判斷網(wǎng)格邊線上是否存在等值點,,如果存在則利用線性插值計算等值點在網(wǎng)格上的坐標(biāo)。得到全部邊線上的等值點后就需要使用一種追蹤策略,,將孤立的等值點連接在一起形成等值線,。一般先追蹤開曲線,即起止于網(wǎng)格邊界線上的等值線,。追蹤開曲線可以順著四個邊界進行,,對于某個邊界任意選取一個等值點作為開始點,追蹤下一個等值點,,直到追蹤到的下一個等值點也是邊界上的點,,就完成了一條等值線的追蹤。
  要從一個等值點追蹤到下一個等值點,,這通常是利用上一次的追蹤方向來確定的,。對于矩形網(wǎng)格來說追蹤方向有4種,即向下,、向左,、向上和向右。如果上一次等值點所在網(wǎng)格的列比本次等值點所在列小1,,則追蹤方向向右,。對于每一種追蹤方向可能出現(xiàn)的情況有兩種。這里以向右追蹤為例進行說明,,其余方向可以類推,。向右追蹤時,如果網(wǎng)格其他三個邊上僅有一邊存在等值點,,則選擇它作為下一個點,;如果其他三邊均存在等值點則從相鄰的上、下邊中選取,,計算上一個等值點到上,、下邊中待選等值點的距離,取距離小的作為下一個等值點,。利用上面的" title="面的">面的追蹤方法追蹤等值線一般都符合實際情況,,并且不會出現(xiàn)交叉現(xiàn)象。
  當(dāng)追蹤出一個等值點后需要將它刪除,,這樣追蹤完一條等值線后就不會重復(fù)追蹤該等值線上的點了,。當(dāng)某一邊界已沒有等值點可以追蹤后,就完成了該邊界的開曲線追蹤,對于矩形網(wǎng)格需要在四個邊界上都進行開曲線追蹤,。開曲線追蹤完畢后,,可能還存在一些等值點,它們將構(gòu)成封閉的閉曲線,,可以任取一點進行追蹤,,直至回到該點則完成追蹤。如果所有等值點都被追蹤過了,,則關(guān)于該等值的等值線就全部追蹤完畢了,。圖1是使用網(wǎng)格法追蹤生成的等值線圖。后面的填充算法將對它進行快速填充,。
  利用追蹤算法得到的等值線,,在網(wǎng)格比較稀疏的情況下顯得不夠平滑,往往還需要采用一種擬合方法對等值線進行圓滑,。一般可以使用三次參數(shù)樣條曲線或三次B樣條曲線[2]來擬合加密曲線,,達(dá)到圓滑的效果。不過為了保證曲線通過原有等值點,,使用這兩種擬合方式時都需要求解線性方程組,速度比較慢,,但是圓滑效果很好,,因為能夠保證二階連續(xù)。如果需要提高速度則可以采用HB曲線[5],。該方法不需要求解方程,,可以保證一階連續(xù),對于大多數(shù)情況都可以取得滿意的效果,,圖1中的等值線就使用了該方法進行圓滑,。


2 掃描線轉(zhuǎn)換算法
  利用等值線追蹤算法已經(jīng)得到了全部的等值線,現(xiàn)在的問題是如何選擇一組色標(biāo)并充填整幅等值線圖,。色標(biāo)中的顏色數(shù)應(yīng)等于等值線的級數(shù),。由于人眼對灰度等級分辨能力不高,通常只有十幾個等級,,因此應(yīng)當(dāng)選擇多個鍵色內(nèi)插形成色標(biāo),。另外為了提高填充速度,應(yīng)當(dāng)將內(nèi)插形成的色標(biāo)顏色組存儲下來,,以便按等級數(shù)提取相應(yīng)的填充顏色,。
2.1 填充掃描線
  選定填充色標(biāo)后,就需要用色標(biāo)中的顏色來填充等值線圖了,。但在介紹掃描線轉(zhuǎn)換算法之前,,先考慮一下如何填充一條掃描線。圖2表示了一條水平掃描線與等值線相交的拓?fù)潢P(guān)系。這里假設(shè)等值線從0開始,,間隔為10米,,[0,10)對應(yīng)顏色為c0,,[30,,40)對應(yīng)顏色為c3,以此類推,。算法首先需要求出掃描線與所有等值線的交點,,并按照X坐標(biāo)的大小排序,接著根據(jù)等值線間的拓?fù)潢P(guān)系,,確定相鄰兩個交點間應(yīng)該填充的顏色,。觀察圖2可以發(fā)現(xiàn)相鄰交點有兩類情況:(1)前后交點的等高值不同,相差一個等級,,如p0,、p1交點對;(2)前后交點的等高值相同,,如p3,、p4交點對。


  對于第(1)種情況,,顏色的確定比較容易,,如p0、p1交點對,,因為前后等值線的等值不同且必然相差一個等級,,因此填充顏色應(yīng)當(dāng)取為[30,40)區(qū)段對應(yīng)的顏色c3,。在實際計算中可以計算相鄰交點對應(yīng)等高值的平均值v,,并令填充顏色為v對應(yīng)顏色。
  第(2)種情況要復(fù)雜一些,,因為前后兩個交點不存在級差,,因此無法直接判斷填充顏色,如p3,、p4和p4,、p5交點對。這時需要利用前一段填充的顏色來輔助判斷,,例如填充p3,、p4交點對時,考慮到p2,、p3交點對對應(yīng)的等高值為50,、60,,而當(dāng)前填充交點對對應(yīng)的等高值為60、60,,說明當(dāng)前交點對對應(yīng)的顏色應(yīng)當(dāng)比上一段高一個色階,,因而取為c6。這樣就可以利用前一段的色階推斷等高值相同的后一段對應(yīng)的填充顏色,。在實際計算中,,可以記下前一段的顏色等級g0,并且用當(dāng)前交點對中任意交點對應(yīng)的等高值計算出顏色等級g1,。如果g0<g1,,則令g0=g1,當(dāng)前顏色取為cg0,,否則取g0=g0-1,,取當(dāng)前顏色為cg0。
  前面討論了第一次出現(xiàn)等高值相同交點對的情況,,但是有時候等高值相同的交點對會連續(xù)出現(xiàn),,例如p3、p4交點對后面的p4,、p5交點對等高值也相同,,這時是否可以繼續(xù)使用前面的算法呢?不妨用前面的算法試一下,,p3,、p4交點對使用填充色c6,即g0=6,,p5對應(yīng)的顏色等級g1=6,按照前面的算法g0不小于g1,,因此取g0=6-1=5,,顏色取c5,恰巧正確,。這是因為根據(jù)等值線不會相交的特點,,如果連續(xù)出現(xiàn)等高值相同的交點對,那么交點對的顏色取值將會是交替變化的,。利用前面的算法處理連續(xù)相同的交點對,,也會得到交替變化的顏色,測試對于其他情況前面的算法也都是成立的,。
2.2 掃描線轉(zhuǎn)換算法快速填充等值線圖
  前面介紹了填充一條掃描線的方法,,如果將一幅等值線圖的所有掃描線都按上面的算法填充,就可以得到填充后的等值線圖,。不過填充的速度比較慢,,因為每條掃描線都需要與全部等值線求交,,并按交點水平坐標(biāo)大小排序,工作量很大,,耗時較多,。然而實際上一條掃描線僅僅會與一些等值線的某個邊相交,并且與上一條掃描線相交的邊一般也會與下一條掃描線相交,,掃描線之間存在著相關(guān)性,。因此可以借鑒圖形學(xué)中填充多邊形的掃描線轉(zhuǎn)換算法,充分利用這些相關(guān)性,,提高填充速度,。下面詳細(xì)介紹掃描線轉(zhuǎn)換算法所需要使用的數(shù)據(jù)結(jié)構(gòu)和算法流程。
  為了有效利用掃描線的相關(guān)性,,在掃描線轉(zhuǎn)換算法中需要建立如下數(shù)據(jù)結(jié)構(gòu):
  (1)等值線Y桶,。等值線Y桶用于記錄等值線的基本信息,桶的長度與掃描線的條數(shù)一樣多,,其編號與掃描線序號一致,。每條等值線都要生成一個桶記錄項,記錄該等值線的最大Y坐標(biāo)ymax,、指向等值線的指針和指向該等值線邊Y桶的指針,。桶記錄項按等值線的最小Y坐標(biāo)插入到桶中。圖3為等值線Y桶數(shù)據(jù)結(jié)構(gòu)的示意圖,。


  (2)有效等值線表AIT,。該表存儲與當(dāng)前掃描線相交的所有等值線在等值線Y桶中的記錄指針。
  (3)邊Y桶,。每條等值線都由一系列的邊組成,,為了利用相關(guān)性,需要建立等值線的邊Y桶,,記錄每條邊的基本信息,。等值線邊Y桶的長度等于與該等值線相交的掃描線的條數(shù)。對于等值線中的每條邊都要產(chǎn)生一個邊記錄,,記錄該邊的最大Y坐標(biāo)ymax,,Y值較小端對應(yīng)的X坐標(biāo)xmin,當(dāng)掃描線增大1時X坐標(biāo)的增量Δx,,以及等值線的值value,。每一個邊記錄按該邊的最小Y坐標(biāo)和整條等值線的最小Y坐標(biāo)的差值存入邊桶中,圖4為邊Y桶數(shù)據(jù)結(jié)構(gòu)的示意圖,。


  (4)有效邊表AET,。該表存儲與當(dāng)前掃描線相交的所有等值線的邊在邊Y桶中的記錄指針。
  利用上面的數(shù)據(jù)結(jié)構(gòu),,一個完整的掃描線轉(zhuǎn)化填充算法如下:
  (1)遍歷所有的等值線,,為每一條等值線生成一個等值線Y桶中的記錄,,并根據(jù)等值線的最小Y坐標(biāo)將該記錄加入到等值線Y桶中。
  (2)將有效等值線表AIT和有效邊表AET初始化為空,。
  (3)對于每一條掃描線i,,它從最小值開始,做以下工作,。①檢查等值線Y桶對于掃描線i是否有新的等值線記錄,,如果有則生成該掃描線對應(yīng)的邊Y桶,并在有效等值線表AIT中加入該掃描線的桶記錄,。②遍歷AIT中的每一條等值線對應(yīng)的桶記錄,,檢查該等值線對應(yīng)的邊Y桶對于掃描線i是否有新的邊記錄加入,如果有則將新的邊記錄按xmin字段的大小加入到有效邊表AET中,。③利用有效邊表AET和掃描線填充算法填充該掃描線,。④遍歷AET,檢查是否有邊記錄的ymax字段等于i,,如果有則刪除該邊記錄,,否則令該邊記錄的xmin=xmin+Δx。⑤遍歷AIT表,,檢查是否有等值線記錄的ymax字段等于i,,如果有則刪除該記錄。
  利用上面的算法可以實現(xiàn)等值線的填充,,由于使用了掃描線轉(zhuǎn)換算法,,其算法復(fù)雜度與多邊形填充一致,因而速度優(yōu)勢很明顯,。圖5和圖6是利用上面算法填充的等值線圖,。其中圖5原始網(wǎng)格數(shù)據(jù)為10行×15列,圖幅450×300像素,,色標(biāo)含35個色階,,由4個鍵色插值生成,在主頻為1.4GHz的電腦上填充時間約為40ms,。圖6原始網(wǎng)格數(shù)據(jù)為215行×330列,圖幅990×645像素,,色標(biāo)含42個色階,,由4個鍵色插值生成,在主頻為1.4GHz的電腦上填充時間約為120ms,。從填充效果來看,,填充結(jié)果與等值線一致,色階正確沒有出現(xiàn)任何誤填和漏填錯誤,。填充結(jié)果與其他填充算法結(jié)果一致,。


  本文介紹了等值線圖生成的一般方法,,并在總結(jié)已有填充方法的基礎(chǔ)上,提出了基于掃描線轉(zhuǎn)換的等值線填充算法,。該方法無需逐點插值填充,,也無需追蹤等值區(qū)域、判斷包含關(guān)系,,而是利用掃描線和等值線的拓?fù)潢P(guān)系確定填充顏色,,并利用快速的掃描線轉(zhuǎn)換算法進行填充,因而速度明顯由于其他填充方法,。經(jīng)實踐證明該方法可以在毫秒級完成一般等值線圖的填充,,而且填充效果與其他算法一致,因而具有很強的實用性,。
參考文獻
1 吳自銀,,高金耀.面向海底成圖基于DTM邊界的等值線填充算法.海洋學(xué)報,2002,;24(1):65~72
2 唐澤圣,,周嘉玉,李新友.計算機圖形學(xué)基礎(chǔ).北京:清華大學(xué)出版社,,1995:106~107
3 孫桂茹,,馬 亮.等值線生成與圖形填充算法.天津大學(xué)學(xué)報,2000,;33(6):816~818
4 成建梅,,陳崇希.三角網(wǎng)格等值線自動生成方法及程序?qū)崿F(xiàn).水利學(xué)報,1998,;22(10):32~36
5 王興波,,李國喜.HB插值樣條曲線曲面.機械強度,1995,;17(4):29~31

本站內(nèi)容除特別聲明的原創(chuàng)文章之外,,轉(zhuǎn)載內(nèi)容只為傳遞更多信息,并不代表本網(wǎng)站贊同其觀點,。轉(zhuǎn)載的所有的文章,、圖片、音/視頻文件等資料的版權(quán)歸版權(quán)所有權(quán)人所有,。本站采用的非本站原創(chuàng)文章及圖片等內(nèi)容無法一一聯(lián)系確認(rèn)版權(quán)者,。如涉及作品內(nèi)容、版權(quán)和其它問題,,請及時通過電子郵件或電話通知我們,,以便迅速采取適當(dāng)措施,避免給雙方造成不必要的經(jīng)濟損失,。聯(lián)系電話:010-82306118,;郵箱:[email protected],。