曲線信息隱藏特征約束可控分形插值算法仿真

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

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

1 引言

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

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

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

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

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

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

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

2.1 分析曲線信息隱藏特征

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

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

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

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

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

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

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

fi≠g(xi)

(1)

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

(2)

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

(3)

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

(4)

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

(5)

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

2.3 計算插值點基值

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

(6)

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

(7)

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

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

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

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

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

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

(8)

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

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

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

f(xi)=yi

(9)

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

IFS={R2|ωi}

(10)

其中ωi定義為

(11)

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

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

3 仿真分析

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

圖5 仿真運行界面

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

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

圖6 仿真對象彎曲結構單元

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

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

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

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

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

表2 仿真測試對比結果

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

4 結束語

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