施志林

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

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

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

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

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

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

2 圖像旋轉(zhuǎn)

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

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為圖像的高度。通過(guò)上面的數(shù)學(xué)公式就可以通過(guò)程序編碼，然后得出我們需要的坐標(biāo)等信息。

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

3 二維hilbert繪制算法

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

4 結(jié)語(yǔ)

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

參考文獻(xiàn)

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

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