二維Hilbert曲線構造與繪制

施志林

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

關鍵詞：Hilbert曲線 遞歸 自相似

中圖分類號：G64 文獻標識碼：A 文章編號：1674-098X（2015）01（c）-0217-01

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

1 二維Hilbert曲線結構

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

2 圖像旋轉

圖像旋轉即是將一個圖像以某個點為旋轉中心，逆時針（或順時針）旋轉一定角度，得到的一個圖形。這個圖形仍然保持與原始圖像的形狀相同。假設圖像左上角坐標為（left，top），右下角坐標為（right，bottom），則圖像上任意一點（x，y）繞其中心（xcenter，ycneter）逆時針旋轉θ角度后，新的坐標位置（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為圖像的高度。通過上面的數學公式就可以通過程序編碼，然后得出我們需要的坐標等信息。

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

3 二維hilbert繪制算法

首先就是要注意各部分的方向，也就是他們與第一個圖形的角度，按逆時針算起，然后才可以確定正弦和余弦值。然后在遞歸調用就可以出現我們需要的那些朝向上下左右的基本圖形單元，然后用直線將相鄰部分連接起來就可以達到我們的目標。算法流程圖如圖3所示。

4 結語

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

參考文獻

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

[2] 林雪輝，蔡利棟.基于Hilbert曲線的數字圖像置亂方法研究[J].中國體視學與圖像分析，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] 孫家廣.計算機圖形學[M].北京：清華大學出版社，1990.