陶雪嬌，闞 洪，張曉穎，王 越

(1. 重慶工程學(xué)院軟件學(xué)院，重慶 400056；2. 重慶理工大學(xué)，重慶 400054)

1 引言

分形插值是在迭代函數(shù)體系的基礎(chǔ)上提出的一種構(gòu)造分形曲線的方法。其原理是在給定的插值點(diǎn)上構(gòu)造相應(yīng)的 IFS，使 IFS的吸引子作為函數(shù)圖通過這組插值點(diǎn)。分形幾何有別于傳統(tǒng)幾何，具有其獨(dú)特之處。第一，分形幾何體整體上是處處不規(guī)則的。但在不同的尺度下，圖形又有相同的規(guī)則。以海岸線為例，從遠(yuǎn)處來看，它的外形極為不規(guī)則，完全無法用傳統(tǒng)的規(guī)則幾何學(xué)來描繪它。在近距離觀察其局部時，其局部形狀又與整體具有某種幾何相似性[1]。然而，并非所有的分形幾何都是完全自相似的，其中有一些是用于描述混沌、非線性系統(tǒng)或一般隨機(jī)現(xiàn)象。分形幾何實(shí)際上就是自然幾何，而分形插值函數(shù)就是利用自然中的許多現(xiàn)象具有精細(xì)的自相似結(jié)構(gòu)這一特征來擬合波動較大的曲線，現(xiàn)在已經(jīng)被證明是非常有效的工具。

分形插值算法經(jīng)過幾十年的發(fā)展，已在數(shù)據(jù)擬合，函數(shù)逼近，計算機(jī)視覺等領(lǐng)域得到了廣泛的應(yīng)用。GIS中的分形插值技術(shù)能夠?yàn)榈匦文M、地圖曲線插值、繪圖等應(yīng)用提供技術(shù)支撐。經(jīng)典的分形插值算法有布朗運(yùn)動，隨機(jī)中點(diǎn)位移，仿射變換等。對實(shí)際自然幾何體的插值來說，這些分形插值算法雖然能有效地生成分形幾何體，并且能夠模擬自然幾何曲線的分形特性，但都是以自然幾何曲線為單純的幾何對象，通常采用的是整體均衡插值算法，而不受自然幾何曲線彎曲特性的限制，實(shí)現(xiàn)了自然幾何曲線的分形插值。地圖上自然幾何曲線并不是單純的幾何圖形，它更是一種典型元素，體現(xiàn)了真實(shí)的自然地理特征形態(tài)。在自然幾何曲線上的海岸線表現(xiàn)為多個海岸單元的特征，如彎度、彎度等，不同海岸單元的幾何形狀、復(fù)雜性、分維等特征是不一樣的，若不仔細(xì)辨別而進(jìn)行整體分形內(nèi)部插入，上述地理特征信息就容易丟失[2]。

針對傳統(tǒng)的分形插值算法存在的問題，提出了一種新的基于幾何細(xì)節(jié)的地理彎曲特征分割和幾何細(xì)節(jié)層次的分形插值約束，在考慮地理彎曲特性約束的情況下，實(shí)現(xiàn)了可控分形插值，并且對比分析與比例相同的實(shí)際目標(biāo)海岸線要素形態(tài)，驗(yàn)證了所提算法的有效性和合理性。

2 曲線信息隱藏特征約束可控分形插值算法設(shè)計

由于四叉樹結(jié)構(gòu)在支持多分辨率地形網(wǎng)格模型快速生成的同時，可以很自然地對地形進(jìn)行分割，使其在地形建模和繪制方面具有廣泛的應(yīng)用。所以設(shè)計了一種曲線信息隱藏特征約束控制分形插值算法，在分形迭代生成曲線時采用四叉樹結(jié)構(gòu)實(shí)現(xiàn)地形分割，具體分割過程如圖1所示。

圖1 四叉樹曲線劃分示意圖

如圖1所示，對于每一件自然事物，首先用四叉樹的根節(jié)點(diǎn)表示整個輪廓曲線，然后將它平均分為左上、左下、右上和右下四個部分，并且每個子節(jié)點(diǎn)都代表一個節(jié)點(diǎn)。在四叉樹結(jié)構(gòu)中，每個子節(jié)點(diǎn)繼續(xù)平均細(xì)分為下一層的四個子節(jié)點(diǎn)，并不斷向下細(xì)分，直至滿足細(xì)分約束[3]。從而可生成研究自然事物所對應(yīng)的曲線高度數(shù)據(jù)。根據(jù)得到的曲線數(shù)據(jù)，結(jié)合曲線本身的信息隱藏特性和分形規(guī)律，得到曲線分形插值處理的最終結(jié)果。

2.1 分析曲線信息隱藏特征

信息隱藏即是將保密信息隱藏于另一非保密載體中，曲線信息隱藏的基本原理如圖2所示。

圖2 曲線信息隱藏基本原理圖

因此分析曲線信息的隱含特性首先要得到信息密鑰，然后通過反向解密得到曲線信息。各種自然曲線形態(tài)是在構(gòu)造運(yùn)動、海水動力、生物作用和氣候因素等共同作用下形成的，自然幾何曲線在抽象表達(dá)時表現(xiàn)出不同的彎曲特征[4]。各種地形類型的自然幾何曲線都可以通過它們所表現(xiàn)的幾何彎曲形態(tài)和復(fù)雜性來識別，形狀復(fù)雜且彎曲度大的海岸線通常表示地貌單元，形狀平直且彎曲度小的自然幾何曲線則表示地貌單元。就天然中海岸線曲線而言，海岸線的彎曲特性取決于該區(qū)域內(nèi)海岸地貌特征，提取曲線彎曲特性隱藏特征信息可以看出，全海岸由海蝕地貌單元和海積地貌單元組成。為了實(shí)現(xiàn)不同地形單元的不同插值，首先要按照彎曲特征對海岸線進(jìn)行劃分，對多個特征單元下的曲線隱含彎曲特征進(jìn)行提取，提取結(jié)果如圖3所示。

圖3 曲線隱藏彎曲特征提取示意圖

對圖3中海岸線進(jìn)行彎曲單元提取后的有序集為{C2，7，C8，10，C11，18，C18，22}，其中Ci，j表示提取的彎曲特征點(diǎn)。

2.2 設(shè)置分形插值約束控制參數(shù)

除了提取的隱藏彎曲特征之外，還可提取曲線隱彎的敏感性特征、保單調(diào)性特征和保凸特征，得到曲線信息的綜合隱彎特征提取結(jié)果[5]。假設(shè)給定函數(shù)g(x)插值數(shù)據(jù)點(diǎn)集合為{(xi，fi)}并且滿足如下關(guān)系式

fi≠g(xi)

(1)

φS(x)是三次有理樣條分形插值函數(shù)，φ(x)為經(jīng)典三次有理樣條插值函數(shù)。如果φS(x)大于等于g(x)或小于等于g(x)，則φS(x)是關(guān)于g(x)的約束插值。由此可以得出如下關(guān)系

(2)

式中D0為常數(shù)參量。若要φS(x)小于等于g(x)，則存在

(3)

為了找到合適的約束條件，定義如下不等式

(4)

由于以上不等式對于i屬于任何值都成立，則可以讓隱藏特征向量滿足如下約束條件

(5)

通過式(2)到式(5)的推導(dǎo)便可以得出曲線可控分形插值的信息隱藏特征約束條件[6]。

2.3 計算插值點(diǎn)基值

為了避免數(shù)據(jù)點(diǎn)集中在插值點(diǎn)的一側(cè)，導(dǎo)致誤差增大，采用方位加權(quán)平均法計算插值參考值。插值M點(diǎn)時，將平面分為以M為中心的四個象限，然后將每個象限平均劃分為n個象限，即最終將平面劃分為4n個象限[7]。并在每個區(qū)域中尋找最接近M的點(diǎn)，設(shè)該點(diǎn)的坐標(biāo)為(xi，yi，zi)它到M點(diǎn)的距離為ri。則M點(diǎn)的插值表達(dá)式表示為

(6)

其中參數(shù)ci可以表示為

(7)

而rl表示的是j和m兩點(diǎn)之間的距離值。如果M點(diǎn)的坐標(biāo)正好與一個原始數(shù)據(jù)點(diǎn)B重合，那么M點(diǎn)的插值就等于B點(diǎn)的值[8]。計算實(shí)際插值點(diǎn)基值時，輸入初始曲線數(shù)據(jù)點(diǎn)和n的值，并確定插值點(diǎn)的地理坐標(biāo)。分別在4n個區(qū)域中尋找到最接近插值點(diǎn)的點(diǎn)，并計算它與插值點(diǎn)之間的距離，利用式(6)計算插值點(diǎn)的值，反復(fù)計算，最終得到全部插值點(diǎn)的值。

2.4 確定分形插值次數(shù)與維數(shù)

根據(jù)原始比例尺和目標(biāo)比例尺之間的插值關(guān)系，結(jié)合各分劃元的彎曲特性，分別計算各分劃元對應(yīng)目標(biāo)分辨率的插值次數(shù)[9-10]。假設(shè)規(guī)則分形插值應(yīng)用于圖4中的線段AB，并且移動方向垂直于要插值的邊緣。

圖4 一維規(guī)則分形插值示意圖

設(shè)原始線段AB的長度為l0，經(jīng)第一個分形插值得到的移位點(diǎn)C與AB之間的角度是θ，即分形偏移角，并且每一次迭代之后產(chǎn)生的移位點(diǎn)與對應(yīng)邊所構(gòu)成的角度都為θ。

利用原比例尺與目標(biāo)比例尺的插值關(guān)系，結(jié)合各分劃單元的彎曲特性，分別計算各分劃單元對應(yīng)目標(biāo)分辨率的插值次數(shù)。此外，式(10)中應(yīng)用分形插值維數(shù)，該參數(shù)的計算公式可表示為

(8)

式中ε表示測量單元的尺寸，而N(ε)為規(guī)則圖形的測量單元數(shù)[11]。

2.5 實(shí)現(xiàn)曲線信息隱藏特征可控分形插值

分形插值函數(shù)產(chǎn)生于一類特殊的迭代函數(shù)系統(tǒng)。在IFS中，當(dāng)映射為仿射變換時，分形插值函數(shù)中，如果平面上的點(diǎn)集連續(xù)函數(shù)f(x)滿足如下關(guān)系式

f(xi)=yi

(9)

則稱f(x)為插值函數(shù)。構(gòu)造IFS為

IFS={R2|ωi}

(10)

其中ωi定義為

(11)

其中，ai、ci、di、ei和fi表示的是實(shí)系數(shù)。設(shè)定i則可求出以上五種實(shí)系數(shù)的實(shí)值，選di為常數(shù)，為保證為壓縮映射，di的取值區(qū)間為[0，1]，那么di為ωi的縱向壓縮因子。一般情況下，分形內(nèi)插曲線的復(fù)雜性主要由縱向壓縮因子di控制，當(dāng)|di|較小時，曲線相對比較平滑。

利用分形插值函數(shù)，在信息隱藏特征約束下，以每個彎曲單元組成的平均線段作為彎曲單元規(guī)則分形的起始邊長，得到了曲線邊長與偏移量的關(guān)系，從而得到了曲線的分形插值結(jié)果[12]。對于非曲線部分，式(12)所示的插值函數(shù)仍可用于分形插值。也就是將各線段的中間點(diǎn)作為移位種子點(diǎn)，彎曲點(diǎn)隨機(jī)分布在與線段方向垂直的線段兩側(cè)。在同一目標(biāo)比例下，偏移值設(shè)置為所有彎曲的最小值，內(nèi)插時間設(shè)置為所有彎曲的最小值。將曲線和非曲線部分分別實(shí)現(xiàn)了分形插值，并按海岸線坐標(biāo)點(diǎn)的順序?qū)⒏鞫蔚牟逯颠B接起來，得到最終插值曲線

3 仿真分析

為了檢測設(shè)計的曲線信息隱藏特征約束可控分形插值算法的分形插值質(zhì)量，設(shè)計仿真。利用 MATLAB數(shù)學(xué)軟件作為仿真的主要運(yùn)行環(huán)境，其運(yùn)行界面如圖5所示。

圖5 仿真運(yùn)行界面

另外將 OpenGL開放圖庫作為實(shí)驗(yàn)樣本的主要來源，為實(shí)驗(yàn)提供足夠的數(shù)據(jù)樣本，以保證實(shí)驗(yàn)結(jié)果的準(zhǔn)確性。OpenGL設(shè)置編譯環(huán)境，編譯 OpenGL時，首先要添加 OpenGL的庫文件，其中主要包括 OpenGL核心庫和 OpenGL實(shí)用庫，核心庫以1開頭，包含100多個圖形處理函數(shù)為矩陣變換光照效果，以及物體的顏色添加等效果操作，而實(shí)用庫 glu核心庫則使用圖形處理函數(shù)對地形的紋理映射坐標(biāo)變化進(jìn)行操作，等等。編寫程序時，需要將這兩個庫文件添加到頭文件中，以便在圖形處理時添加各種圖形處理函數(shù)，以便于繪圖。

仿真期間，OpenGL數(shù)據(jù)庫選取了一條曲線作為實(shí)驗(yàn)樣本，選取沿海城市的海岸線數(shù)據(jù)，該樣本對象長約45 km，尺度為1：200萬。將所設(shè)計的曲線信息隱藏特征約束可控分形插值算法與傳統(tǒng)分形插值算法及文獻(xiàn)[9]中提出的多元多項(xiàng)式插值算法進(jìn)行了比較，并與實(shí)際的1∶100萬和1∶50萬等要素海岸線數(shù)據(jù)進(jìn)行了形態(tài)化和精度對比分析。一是對海岸線進(jìn)行彎曲單元劃分；圖6顯示了實(shí)驗(yàn)對象彎曲結(jié)構(gòu)的基本單元。

圖6 仿真對象彎曲結(jié)構(gòu)單元

同理可以得出其它曲線樣本的選擇與設(shè)置情況，其中部分樣本的設(shè)置數(shù)據(jù)如表1所示。

表1 仿真樣本參數(shù)設(shè)置表

通過三種分形插值算法的運(yùn)行，分別得出曲線處理結(jié)果如圖7所示。

圖7 曲線1：100萬分形插值結(jié)果對比圖

為了實(shí)現(xiàn)對分形插值結(jié)果質(zhì)量的量化對比，將圖7的插值處理結(jié)果轉(zhuǎn)化成坐標(biāo)點(diǎn)，并與收集的坐標(biāo)點(diǎn)進(jìn)行對比，從而得出插值結(jié)果與實(shí)際結(jié)果之間的誤差，并計算出插值處理后研究樣本曲線的分維數(shù)，經(jīng)過相關(guān)參數(shù)的計算與對比，得出仿真結(jié)果如表2所示。

表2 仿真測試對比結(jié)果

綜合圖7中顯示的直觀插值結(jié)果和表2中的量化對比結(jié)果可以看出，相比于兩個對比插值算法，設(shè)計算法得出的結(jié)果更加接近實(shí)際的1：100萬曲線數(shù)據(jù)，且插值前后曲線的分維數(shù)相近，說明設(shè)計的分形插值算法能夠最大程度的保留曲線的分形特征。

4 結(jié)束語

按照曲線所呈現(xiàn)的不同彎曲特征對曲線進(jìn)行地貌單元劃分，將傳統(tǒng)的整體分形插值轉(zhuǎn)換為將曲線分形特征作為劃分單元的差分分段插值組合，分形內(nèi)插每個單元，并結(jié)合每個劃分單元的彎曲特性對分形參數(shù)進(jìn)行約束控制，從而實(shí)現(xiàn)曲線不同單元的彎曲特性約束。在實(shí)際的制圖工作中，采用所設(shè)計的分形插值算法，能有效地保留真實(shí)地形特征，保證了制圖結(jié)果信息的完整性和準(zhǔn)確性。但仿真中，設(shè)定的插值目標(biāo)比較單一，所選實(shí)驗(yàn)樣本數(shù)目較少，所得到的實(shí)驗(yàn)結(jié)果可信度不高，針對這一問題，今后仍需進(jìn)一步優(yōu)化和補(bǔ)充。