(3.230.143.40) 您好！臺灣時間：2021/04/23 16:06

### 詳目顯示:::

:

• 被引用:0
• 點閱:253
• 評分:
• 下載:9
• 書目收藏:0
 過去，有許多植基於希耳伯特曲線的運算被提出，但是這些運算全部都受限於影像大小必需是2^r*2^r的限制。本篇論文提出了一個植基於蛇行掃瞄的有效演算法將一個任意大小的影像編碼成其對應的希耳伯特曲線，打破了這個長久以來的限制。假設所給予的影像其大小為I_1*I_2，我們所提出的編碼演算法花費了O(k+logU)的時間求得一個像素所對應的希耳伯特次序，這裡k代表四分形的個數，U=min(I_1,I_2)。接著，我們提出了一個節省記憶體花費的希耳伯特曲線表示法，用來表示被編碼的希耳伯特曲線。這個表示法我們稱之為HCGL表示法，而這個HCGL表示法需要花費O((L^2)*logL)的時間來建構。最後，對於以HCGL表示法表示的任意大小影像，我們提出了一個在其上進行視窗查詢應用的演算法，這個演算法花費了O((M*logL)+P)的時間，這裡M代表所產生的最大四分樹區塊的個數，P表示輸出碼的個數。實驗結果證明我們提出的演算法優於一些現今存在的演算法。
 Previously, several efficient Hilbert scan--based operations were developed, but they all suffer from the constraint that the image size must be of size 2^r*2^r. Considering an image with arbitrary size I_1*I_2, this paper first presents an efficient snack scan-based algorithm for coding the Hilbert curve of the given image. The proposed coding algorithm takes O(k+logU) time to code the Hilbert order of one pixel where k denotes the number of the quadrants and U=min(I_1,I_2). Next, a memory-saving Hilbert curve representation called the HCGL is presented for representing the encoded Hilbert curve and the proposed HCGL representation can be constructed in O((L^2)*log L) time. Based on the proposed HCGL representation for arbitrary-sized image, an application to window query is presented and the proposed window query algorithm takes O((M*logL)+P) time where M denotes the number of generated maximal quadtree blocks and P denotes the number of output codes. Experimental results demonstrate that our proposed algorithms outperform some existing related algorithms.
 1 Introduction 1.1 Background 1.2 Organization of the thesis 2 The Past Work by Liu and Schrack 3 The Proposed Snack Scan-Based Coding Algorithm 3.1 Encoding arbitrary-sized image into a set of Hilbert curves 3.2 Concatenating encoded Hilbert curves to form a complete Hilbert curve 3.3 The proposed coding scheme 4 Memory—Saving Hilbert Curve Representation: HCGL 5 Window Query Application 6 Experimental Results 7 Conclusion
 [1] W. G. Aref and H. Samet, “Efficient processing of window queries in the pyramid data,” in Proc. 9th ACM-SIGMOD Symposium Principles Database Systems, pp. 265-272, April 1990.[2] W. G. Aref and H. Samet, “Decomposing a window into maximal quadtree blocks,”Acta Informatica, vol. 30, no. 5, pp. 425-439, 1993.[3] T. Asano, D. Ranjan, T. Roos, and E. Welzl, “Space-lling curves and their use in the design of geometric data structures,” Theoretical Computer Science, vol. 181, no.1, pp. 3-15, 1997.[4] T. Bially, “Space-lling curves: Their generation and their application to bandwidth reduction,” IEEE Trans. Information Theory, vol. IT-15, no. 6, pp. 658-664, 1969.[5] N. Bourbakis and C. Alexopoulos, “Picture data encryption using scan patterns,” Pattern Recognition, vol. 25, no. 6, pp. 567-581, 1992.[6] G. Cantor, “Ein Beitrag zur Mannigfaltigkeitslehre,” Crelle Journal., vol. 84, pp. 242-258, 1878.[7] K. L. Chung, Y. H. Tsai, and F. C. Huang, “Space-lling approach for fast window query on compressed images,” IEEE Trans. Image Processing, vol. 9, no. 12, pp. 2109-2116, 2000.[8] T. H. Cormen, C. E. Leiserson, and R. L. Rivest, Introduction to Algorithms, Cambridge, MA: MIT Press, 1990.[9] J. D. Foley, A. Dam, S. K. Feiner and J. F. Hughes, Computer Graphics: Princiles and Practice, 2nd ed., Addison-Wesley, New York, 1996.[10] D. Hilbert, “ Uber die stetige Abbildung einer Linie auf ein Flachenstuck,” Mathematische Annalen, vol. 38, pp. 459-460, 1891.[11] H. V. Jafadish, “Analysis of the Hilbert curve for representing two-dimensional space,” Information Processing Letters, vol. 62, no. 1, pp. 17-22, 1997.[12] F. C. Jian, “Hilbert curves and its applications on image processing,” M.S. thesis, Dept. Elect. Eng., Nat. Taiwan Univ., Taiwan, R.O.C., June 1996.[13] R. Johnsonbaugh, Discrete Mathematics, 5th Edition, Prentice Hall, N. J., 2001.[14] W. de Jonge, P. Scheuerman, and A. Schijf, “S^+-Tree: An efficient structure for the representaion of large picture,” CVGIP: Image Understanding, 59, pp. 265-280,1994.[15] S. Kamata, M. Niimi, and E. Kawaguchi, “A method of an interactive analysis for multi-dimensional images using a Hilbert curve,” IEICE Trans., vol. J77-D-II, no.7, pp. 1255-1264, 1993.[16] S. Kamata, R. O. Eaxon, and E. Kawaguchi, “An implementation of the Hilbert scanning algorithm and its application to data compression,” IEICE Trans. Informationand Systems, vol. E76-D, no. 4, pp. 420-428, 1993.[17] S. Kamata, M. Niimi, and E. Kawaguchi, “A gray image compression using a Hilbert scan,” in Proceedings of the 13th International Conference on Pattern Recognition, vol. 3, pp. 905-909, August 1996.[18] H. Lebesgue, Lecons sur l''Integration et la Recherche des Fonctions Primitives. Paris, France: Gauthier-Villars, pp. 44-45, 1904.[19] X. Liu and G. F. Schrack, “Encoding and decoding the Hilbert order,” Software Practice and Experience, vol 26, no. 12, pp.1335-1346, 1996.[20] X. Liu and G. F. Schrack, “An algorithm for encoding and decoding the 3-D Hilbert order,” IEEE Trans. Image Processing, vol. 6, no. 9, pp. 1333-1337, 1997.[21] E. H. Moore, “On certain crinkly curves,” Transactions of American Mathematical Society, vol. 1, pp. 72-90, 1900.[22] E. Nardelli, “Efficient secondary memory processing of window queries on spatial data,” Information Sciences, vol. 84, no. 1-2, pp. 67-83, 1995.[23] E. Nardelli and G. Proietti, “Time and space ecient secondary memory representation of quadtrees,” Information Systems, vol. 22, no. 1, pp. 25-37, 1997.[24] G. Peano, “Sur une courbe qui remplit toute une aire plane,” Mathematische Annalen, vol. 36, pp. 157-160, 1890.[25] G. Proietti, “An optimal algorithm for decomposing a window into maximal quadtree blocks,” Acta Informatica, vol. 36, no. 4, pp. 257-266, 1999.[26] M. K. Quweider and E. Salari, “Peano scanning partial distance search for vector quantization,” IEEE Signal Processing Letters, vol. 2, no. 9, pp. 169-171, 1995.[27] C. S. Refazzoni and A. Teschioni, “A new approach to vector median ltering based on space lling curves,” IEEE Trans. Image Processing, vol. 6, no. 7, pp. 1025-1037,1997.[28] H. Sagan, Space-Filling Curves, New York: Springer-Verlag, 1994.[29] R. J. Stevens, A. F. Lehar, and F. H. Preston, “Manipulation and presentation of multidimensional image data using the peano scan,” IEEE Trans. Pattern Analysis andMachine Intelligence, vol. PAMI-5, no. 5, pp. 520-526, 1983.[30] Y. H. Tsai, K. L. Chung, and W. Y. Chen, “A strip-splitting-based optimal algorithm for decomposing a query window into maximal quadtree blocks,” IEEE Trans. Knowledge and Data Engineering, vol. 16, no. 5, pp. 519-523, 2004.[31] Y.Wang, Y.Wang, and H. Kuroda, “A globally adaptive pixel—decimation algorithm for block-motion estimation,” IEEE Trans. Circuits Syst. Video Technol., vol. 10, pp.1006-1011, 2000.[32] Y. F. Zhang, “Space-lling curve ordered dither,” Computers & Graphics, vol. 22, no. 4, pp. 559-563, 1998.
 電子全文
 國圖紙本論文
 推文當script無法執行時可按︰推文 網路書籤當script無法執行時可按︰網路書籤 推薦當script無法執行時可按︰推薦 評分當script無法執行時可按︰評分 引用網址當script無法執行時可按︰引用網址 轉寄當script無法執行時可按︰轉寄

 1 在Hilbert曲線中有效率資料擷取的方法

 無相關期刊

 1 利用希爾伯特曲線將資料嵌入在半色調影像 2 植基於四分樹與二分樹之視窗查詢和影像演算法 3 偵測不同形狀的有效影像演算法之設計及其實作 4 一個以垂直線來解決單雙色反向最近鄰居之物件移動的漸進式方法 5 觀看電影預告片之腦電波訊號反應 6 汽油價格緩漲對台灣汽油產業影響之分析－轉換函數和向量自我迴歸模型之應用 7 以基因演算法為基礎的適應性灰預測模型求解短期需求預測問題 8 新生兒及新住民子女人數對國小教育之影響－以屏東縣某國小為例 9 以應變規應用於呼吸位移補償系統之補償精度改善及實驗驗證 10 雌激素低下加劇壓迫對大腦體感覺皮質錐狀細胞樹突的影響 11 運用多項式回歸分析財務指標以預測股票價格的波動 12 仙人掌圖的強邊著色數 13 離散正交諧波轉換 14 應用ARIMAX及ANFIS模型於福山森林集水區逕流模擬之研究 15 在Hilbert曲線中有效率資料擷取的方法

 簡易查詢 | 進階查詢 | 熱門排行 | 我的研究室