(3.230.143.40) 您好!臺灣時間:2021/04/23 16:06
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:黃翊倫
研究生(外文):Yi-Luen Huang
論文名稱:任意大小影像上的有效希耳伯特曲線編碼演算法與其在視窗查詢上的應用
論文名稱(外文):Efficient Algorithms for Coding Hilbert Curve of Arbitrary-Sized Image and Application to Window Query
指導教授:鍾國亮鍾國亮引用關係
指導教授(外文):Kuo-Liang Chung
學位類別:碩士
校院名稱:國立臺灣科技大學
系所名稱:資訊工程系
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2004
畢業學年度:92
語文別:英文
論文頁數:52
中文關鍵詞:壓縮希耳伯特曲線影像表示法最大四分樹區塊四分形植基於蛇行掃瞄的演算法視窗查詢
外文關鍵詞:CompressionHilbert curveImage representationMaximal quadtree blockQuadrantSnake scan-based approachWindow query
相關次數:
  • 被引用被引用: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. Information
and 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 and
Machine 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.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔