二維Hilbert曲線構(gòu)造與繪制

施志林

摘 要：Hilbert是一種經(jīng)典的空間填充曲線，具有嚴(yán)格的自相似性，可以將他劃分成一些很小的單元，只是方向不一。且具有良好的空間聚集特性，應(yīng)用也很廣泛，譬如在圖像置亂加密，數(shù)據(jù)壓縮，數(shù)據(jù)索引編碼等。Hilbert曲線比其他的填充曲線如Z-Ordering、Gray更能保持原始數(shù)據(jù)的性能。因此詳細(xì)了解Hilbert曲線原理并使用一種自己熟悉的計算機語言來繪制Hilbert有很大的意義。因此，該文主要介紹二維Hilbert曲線的構(gòu)造及原理并用C#編程語言將它實現(xiàn)。

關(guān)鍵詞：Hilbert曲線 遞歸 自相似

中圖分類號：G64 文獻(xiàn)標(biāo)識碼：A 文章編號：1674-098X（2015）01（c）-0217-01

Hilbert曲線是由德國數(shù)學(xué)家David Hilbert發(fā)現(xiàn)的一種可以填滿整個正方形的分形曲線。當(dāng)階數(shù)達(dá)到一定程度的時候，這條曲線可以填滿整個正方形。目前被應(yīng)用于很多方面，如圖像置亂，數(shù)據(jù)加密，數(shù)據(jù)壓縮等且效果不錯。Hilbert曲線也具有很好的聚集效果，當(dāng)給每個端點按順序編號之后，我們可以發(fā)現(xiàn)編碼相近的地方，大多情況下，他們的實際距離也是相近，少部分編碼相差大一些的也是距離很近。但總體來說，Hilbert空間填充比其他的填充曲線如Z-Ordering、Gray更能保持原始數(shù)據(jù)的性能。

1 二維Hilbert曲線結(jié)構(gòu)

圖1是用代碼自動生成的一階，二階，三階曲線，從中我們可以發(fā)現(xiàn)，當(dāng)我們把中間的二階曲線填充的正方形分成四塊的時候，分割下來最原始的就是圖2中的四個圖形，我們可以發(fā)現(xiàn)四塊中各部分的形狀跟一階曲線相同，只是開口方向不一樣，再將三階劃分，發(fā)現(xiàn)又跟二階一樣，只是方向不同，由此可見，Hilbert曲線是由一個最基本的結(jié)構(gòu)組成，繪制完的Hilbert曲線就是一階的重復(fù)繪制，然后連接起來。而且角度也全是相差90°，可以通過圖像旋轉(zhuǎn)來繪制出每個部分。

2 圖像旋轉(zhuǎn)

圖像旋轉(zhuǎn)即是將一個圖像以某個點為旋轉(zhuǎn)中心，逆時針（或順時針）旋轉(zhuǎn)一定角度，得到的一個圖形。這個圖形仍然保持與原始圖像的形狀相同。假設(shè)圖像左上角坐標(biāo)為（left，top），右下角坐標(biāo)為（right，bottom），則圖像上任意一點（x，y）繞其中心（xcenter，ycneter）逆時針旋轉(zhuǎn)θ角度后，新的坐標(biāo)位置（x1，y1）的計算公式為：

xcenter=（width+1）/2+left；

ycenter=（hight+1）/2+top；

x1=（x-xcenter）cosθ-（y-ycenter）sinθ+xcenter；

y1=（x-xcenter）sinθ+（y-ycenter）cosθ+ycenter；

其中width為圖像的寬度，hight為圖像的高度。通過上面的數(shù)學(xué)公式就可以通過程序編碼，然后得出我們需要的坐標(biāo)等信息。

該文所述算法里面關(guān)鍵的地方就是需要利用旋轉(zhuǎn)來繪制其他相同的部分，今兒生成整條Hilbert曲線。

3 二維hilbert繪制算法

首先就是要注意各部分的方向，也就是他們與第一個圖形的角度，按逆時針?biāo)闫穑缓蟛趴梢源_定正弦和余弦值。然后在遞歸調(diào)用就可以出現(xiàn)我們需要的那些朝向上下左右的基本圖形單元，然后用直線將相鄰部分連接起來就可以達(dá)到我們的目標(biāo)。算法流程圖如圖3所示。

4 結(jié)語

Hilbert曲線的各部分構(gòu)造相同，只是他們各部分的開口方向一樣，因此，不管是多少維的Hilbert曲線都比較好實現(xiàn)，只是實現(xiàn)他們的算法簡單或復(fù)雜、快或慢、高效或低效的區(qū)別。二維相對來說簡單一些，考慮的相對少一些，不過這可以為生成后面的高維曲線作鋪墊。下面的研究方向是對三維Hilbert曲線的繪制算法進(jìn)行研究。

參考文獻(xiàn)

[1] 謝耀華，湯曉安，孫茂印，等.基于分類重排LZW的圖像無損壓縮算法[J].中國圖象圖形學(xué)報，2010（2）：236-241.

[2] 林雪輝，蔡利棟.基于Hilbert曲線的數(shù)字圖像置亂方法研究[J].中國體視學(xué)與圖像分析，2004（4）：224-227.

[3] LinShen-Yi，Chen，Chih-Shen，LiuLi，et al.Tensor Product Formulation for Hilbert Space-Filling Curves[J].J.Inf.Sci.Eng.2008（24）：261-275.

[4] 孫家廣.計算機圖形學(xué)[M].北京：清華大學(xué)出版社，1990.