Path-Controlled Graph Grammars for Mutliresolution Image Processing and Analysis
作者： Kunio Aizawa , Akira Nakamura
关键词: Time complexity 、 Graph 、 Quadtree 、 Image processing 、 Computer science 、 Power graph analysis 、 Theoretical computer science 、 Pixel 、 Embedding 、 Rule-based machine translation
摘要: In this paper, we define graph compression rules for the graphs representing two-dimensional rectangular grids with black and white pixels by making use of PCE way embedding. The rewrite four nodes having same label forming a square into node label. It also inserts deletes special labels to preserve neighborhood relations in original image. Then introduce an image algorithm using concept our rules. We show that time complexity is O(Nlog2N), where N number input graph, which as case best quadtree representation.
springer.com
sci-hub.st 参考文章(12)
H. Samet, A Tutorial on Quadtree Research Multiresolution Image Processing and Analysis. pp. 212- 223 ,(1984) , 10.1007/978-3-642-51590-3_15
A. Saoudi, Parallel Recognition of Multidimensional Images Using Regular Tree Grammars ICPIA '92 Proceedings of the Second International Conference on Parallel Image Analysis. pp. 231- 239 ,(1992) , 10.1007/3-540-56346-6_41
Hartmut Ehrig, Grzegorz Rozenberg, M. Nagl, Azriel Rosenfeld, Graph Grammars and Their Application to Computer Science: 3rd International Workshop Warrenton, Virginia, Usa, December 2-6, 1986 ,(1988)
J. P. Mylopoulos, T. Pavlidis, On the Topological Properties of Quantized Spaces, I. The Notion of Dimension Journal of the ACM. ,vol. 18, pp. 239- 246 ,(1971) , 10.1145/321637.321644
Kunio Aizawa, Akira Nakamura, Graph grammars with path-controlled embedding Theoretical Computer Science. ,vol. 88, pp. 151- 170 ,(1991) , 10.1016/0304-3975(91)90079-H
Q. Y. Shi, King-Sun Fu, Parsing and Translation of (Attributed) Expansive Graph Languages for Scene Analysis IEEE Transactions on Pattern Analysis and Machine Intelligence. ,vol. PAMI-5, pp. 472- 485 ,(1983) , 10.1109/TPAMI.1983.4767426
Ming Li, William I Grosky, Ramesh Jain, Normalized quadtrees with respect to translations Computer Graphics and Image Processing. ,vol. 20, pp. 72- 81 ,(1982) , 10.1016/0146-664X(82)90074-0
Hanan Samet, The design and analysis of spatial data structures ,(1989)
Gregory M. Hunter, Kenneth Steiglitz, Operations on Images Using Quad Trees IEEE Transactions on Pattern Analysis and Machine Intelligence. ,vol. 1, pp. 145- 153 ,(1979) , 10.1109/TPAMI.1979.4766900
Kunio Aizawa, Akira Nakamura, Path-controlled graph grammars for syntactic pattern recognition International Journal of Pattern Recognition and Artificial Intelligence. ,vol. 8, pp. 71- 86 ,(1994) , 10.1007/3-540-56346-6_29