於Hilbert曲線中求範圍查詢之方法

專利類型

發明

專利國別 (專利申請國家)

中華民國

專利申請案號

099110590

專利證號

I 398828

專利獲證名稱

於Hilbert曲線中求範圍查詢之方法

專利所屬機關 (申請機關)

國立中山大學

獲證日期

2013/06/11

技術說明

Space-filling curve是一種線段，可以走過2^n×2^n平面的每一個點，而且每個點只可走過一次。它可以將2維座標轉換為1維座標，也就是可以幫2維的資料決定一個全域索引。Hilbert curves是最具代表性，因可以有效的保存空間的locality，已經廣泛的應用在多種的領域上，如影像處理及壓縮(image processing and compression)、空間查詢(spatial query)及無線廣播系統(wireless broadcast system)等。在影像上，若依照Hilbert curve行走的路徑，可以發現它每次都行走至它相鄰的點，這種依Hilbert index大小次序行走的路徑，我們稱為Hilbert scan，不少的影像壓縮方法是以Hilbert scan為基礎來發展。在影像資料庫的應用中，window query 是一個很重要的查詢功能。假設已壓縮的影像大小為T×T，window的大小為n1×n2，左下角座標為(x, y)，window query就是要求出window所表示範圍的子影像(sub-image)。最簡單的方法就是將影像解壓縮後再做window query，若是影像很大(如衛星地圖等)，將浪費很多解壓縮的時間。另外也可以直接利用Liu等學者的方法計算出window中所有Hilbert indexes，所需時間複雜度為O(n1n2log T)。Chung等學者針對以Hilbert scan的壓縮影像，提出快速window query的方法，他們利用maximal blocks 分割方法及Liu等學者的Hilbert index相互轉換的方法，求出window 中所有的Hilbert indexes，所需時間複雜度為O(n log T)，n為window的最長邊。為了有效減少執行時間，我們利用Hilbert curves的特性，提出四等份切割法(Quad-Splitting)來計算window中的所有Hilbert index的值。雖然我們的方法所需時間複雜度雖與Chung教授等學者的方法同為O(nlog T)，但我們的方法不須額外的排序與合併的步驟，可以有效減少執行時間。經實驗證明我們的方法比Chung等學者的方法可以減少92-98%的時間。

備註

本部(收文號1050019735)同意該校105年3月21日中產營字第1051400266號函申請終止維護專利

連絡單位 (專責單位/部門名稱)

產學營運及推廣教育處

連絡電話

(07)525-2000#2651

網址