瑞の資訊備忘錄

一、論文稱名： A New Algorithm For N-Dimensional Hilbert Scanning

二、論文作者： Sei-ichiro Kamata, Richard O.Eason and Yukihiro Bandou 

三、期刊名稱： IEEE TRANSACTIONS ON IMAGE PROCESSING. VOL. 8 NO.7 JULY 1999 

四、說明：Hilbert curve是一種盡可能維持鄰近點相鄰的情況下將N維的空間維度轉換至一維空間維度

               的方法(即轉換至一維空間後其任兩個相鄰空間的漢明距離(Hamming distance)必須為1)，

               而該方法有許多不同的應用面例如影像處理及影像壓縮……等。

五、定義：

    5-1、於1981由Hilbert提出下列的2D曲線： (a)  2x2     (b) 4xx4     (c) 8x8

5-2 、在相同維度下有不同路徑的Hilbert curve： (a) 2-Dimensional (3) 3-Dimensional

六、演算法說明：

    Hilbert Scanning於1891年被提出來至今已有許多不同實作的演算法而該論文主要強調一種新的、

    簡單的、非遞迴式的演算法即是對於N-維度的空間使用look-up table的方式來加快計算的速度及提

    供容易實作的優點。所謂的look-up table即是將原本大範圍的N維空間持續的分割成2^N個N維度

    子空間直到將該空間分割至基本的單位空間如4-2所示。最後透過組合不同的基本單位搜尋順序組合成

    大範圍的空間。

七、演算法執行步驟：

該演算法執行可分為兩大部份：

        (1) Terminal Rule：說明如何建立基本單位空間的不同搜尋路徑。

        (2) Induction Rule：說明如何將大的空間依照基本單位空間的掃描方式來進行組合掃描。

    7-1、Terminal Rule 主要有下列三個步驟：

       7-1.1、定義Start Addresses：

          在基本單位空間中決定不同路徑的起始位置；而因為該演算法是透過不同基本單位的搜尋路徑

          來組合成指定的空間大小，因此結束位置必定是連接下一個起始位置所每個起始位置必須符合

          下列兩項條件：          

               1.1 每個起始定址的第一個位置與第N個位置之間的漢明距離(Hamming distance)必須為1。

     (為了滿足連接兩個基本單位的搜尋路徑)

               1.2 任兩個不同的起始定址之間的第一個位置必須為漢明距離(Hamming distance)的偶數。

                    (連接兩個基本單位之間必定有一個End Point)

          依下列的作法來滿足上述的條件：        

               2.1 使用N-bit二元值來表示N維度的空間中每個位址的值並使用下列公式來建立第一個

                     起始定址：

   EX:  a (1,1) = {0,1}

                          a (1,2) = {0 {0,1},1{1,0}}

                          a (1,3) = {0{00,01,11,10} , 1 {10,11,01,00}}

               2.2 根據上述1.2條件，將2.1所產生出來的第一個起始定址依奇、偶數位置分割成兩個群組；

                     因此每個群組共有N^(N-1)個不同的值：                  

                        2D:  A：{00,11}                     B：{01 ,10} 

3D : A：{000,011,110,101}   B：{001,010,111 100}

               2.3 使用A群組來做為每個起始定址的第一個位置。

     7-1.2、定義End Addresses：

             使用下列公式來滿足上述1.1的條件 一

             在N維空間中每個起始定址可以得到N個不同的第N個位置，因此總共可以得到N*2^(N-1) 個

             不同的起始路徑 一

              EX:   1-1 (000,…,100)   1-2.(000,…, 010)   1-3.(000,…,001)

                      2-1 (110,…,010)   1-2.(110,…, 100)   1-3.(110,…,111)

                      3-1 (101,…,001)   1-2.(000,…, 111)   1-3.(000,…,100)

                      4-1 (011,…,111)   1-2.(011,…, 001)   1-3.(011,…,010)

     7-1.3、定義Remaining Addresses：

         3.1 使用上述兩個步驟得到每個路徑的第一個和第N個位置並套用下列的公式來求出第2到第N個路徑

               中2到N-1個位址 一

             公式中的 表示由2.2所產生的第一個路徑中的第i個位置的值與

             第k個位置的值是否相等； 表示Exclusive OR 的位元運算。

    EX：a1 - {000,001,011,010,110,111,101,100}    

                  a2 - {000,001,101,100,110,111,011,010}

a3 - {000,100,110,010,011,111,101,001}   

3.2  使用下列的公式來計算其他N+1到N*2(N-1)路徑中的2到N-1個位址 一  i
             

         i = 1,2,…,2^N-1      i' = 2,3,…,2^(N-1) -1

         j = 1,2,…,N             j' = N(i'-1)+j 

             EX：a4 - {011,010,000,001,101,100,110,111} reference by a1 

                   a5 - {011,010,110,111,101,100,000,001} reference by a2

                   a6 - {011,111,101,001,000,100,110,010} reference by a3

                   a7 - {110,111,101,100,000,001,011,010} reference by a4

                   a8 - {110,111,011,010,000,001,101,100} reference by a5

                   a9 - {110,010,000,100,101,001,011,111} reference by a6

                   a10 - {101,100,110,111,011,010,000,001} reference by a7

                   a11 - {101,100,000,001,011,010,110,111} reference by a8

                   a12 - {101,001,011,111,110,010,000,100} reference by a9 

      7.2、The formula of Induction Rules：

         7.2.1 Induction Rules的觀念說明 一

                 Induction Rule是該演算法的核心部份，該演算法主要是先將指定的空間大小先分

           割成2^Dimensional後再對每一個子空間再進行一次分割直到基本空間大小為止。而該

           步驟即是說明如何正確的掃描每一個子空間使其可以正確的與其他的子空間進行連接。

           連接方式如下圖所示：

             如果要將上圖中的a1(m,2)再進行分割時則必須使用以s1為開始和e1為結束的路徑。            

         7.2-2 The formula of Induction Rules 一               

            EX:

                以3-Dimensional為列，下列數字表示其選擇的路徑相關的內容請參考上述7-1.3的範例 一

                  Level 0 : 1

          Level 1 : 3 2 4 8 12

                  Level 2 : 3 --> 1 2 9 5 10

                              2 --> 3 1 11 7 6

                              4 --> 6 5 1 11 9

                              8 --> 9 7 5 1 12

                            12 --> 10 11 6 8 1

       7-3 ：如何產生掃描順序 一

           必須使用深度優先搜尋法由上而下組合induction Rules中每個路徑的點來產生掃描順序，因此本文

           使用遞迴關係式來減化組合的步驟。

           EX:

                Level 0: 1 ==> {000,001,011,010,110,111,101,100 }

                Level 1: 3 ==> {000,{000,100,110,010,011,111,101,001 }}

                Level 2: 1 ==> {000,{000,{000,001,011,010,110,111,101,100}}}

            merge result ==> {{(000)(000)(000)},{(000)(000)(001)},{(000)(000)(011)},……}

            convert to dimensional index ==>

                    {(000)(000)(000)} ==> (000,000,000) ==> (0,0,0)

                    {(000)(000)(001)} ==> (000,000,001) ==> (0,0,1)

                    {(000)(000)(011)} ==> (000,001,001) ==> (0,1,1)

            在Terminal Rules中每個路徑內的值所表示的bit，表示在該相同位置維度的bit值,而每當有新增的

            位元時則先向左移一位元後再將新的位元加入。

八、檢查最後產生的結果是否符合Hilbert Scanning的順序：

       Hilbert Scanning必須符合下列三個條件：

        8-1、任兩個相鄰點的值其漢明距離(Hamming distance)必須為1

        8-2、任兩個點其值必不相同。

        8-3、最終產生點的數量必須符合如右所示公式： 1<< (Dimensional * Space Size)

               EX: Dimensional : 3  Space Size : 2  ==> Total Count = 1 << ( 3 * 2) = 64

Download： HilbertScanning.rar

Result：

     Hilbert Scanning :

       (1) HilbertScanning -d 3 -s 3 -p 0 -n 

       (2) HilbertScanning -d 3 -s 3 -p 0 > 3-3.hs

   CheckResult : CheckResult -d 3-3.hs