OPERATIONS ON IMAGES USING QUAD TREES

被引：228

作者：

HUNTER, GM ^{[1
]}

STEIGLITZ, K ^{[1
]}

机构：

[1] PRINCETON UNIV,DEPT ELECT ENGN & COMP SCI,PRINCETON,NJ 08540

来源：

IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE | 1979年 / 1卷 / 02期

关键词：

computer-aided design; encoded raster graphics; Index Terms-Cartography; layout; pattern recognition; picture compaction; picture processing; pyramid; Q-tree; quad tree; rope; scan-line encoding; space planning;

D O I：

10.1109/TPAMI.1979.4766900

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

A quad tree for representing a picture is a tree in which successively deeper levels represent successively finer subdivisions of picture area. An algorithm is given for superposing N quad trees in time proportional to the total number of nodes in the trees. Warnock-type algorithms are then presented for building the quad tree for the picture of the boundary of a polygon, and for coloring the interior of such a polygon. These algorithms take O(v + P + q) time, where V is the number of polygon vertices, p is the polygon perimeter, and q is a resolution parameter. When the resolution q is fixed, these algorithms are asymptotically optimal. Copyright © 1979 by The Institute of Electrical and Electronics Engineers, Inc.

引用

页码：145 / 153

页数：9

共 12 条

[1] Aho A. V., 1974, DESIGN ANAL COMPUTER
[2] PICTURE SEGMENTATION BY A TREE TRAVERSAL ALGORITHM
HOROWITZ, SL
PAVLIDIS, T
[J]. JOURNAL OF THE ACM, 1976, 23 (02) : 368 - 388
[3] COMPUTER ANIMATION SURVEY
HUNTER, GM
[J]. COMPUTERS & GRAPHICS, 1977, 2 (04) : 225 - 229
[4] HUNTER GM, 1975, 182 PRINC U DEP EL E
[5] HUNTER GM, 1978, THESIS PRINCETON U
[6] Klinger A., 1976, COMPUT VISION GRAPH, V5, P68, DOI [10.1016/S0146-664X(76)80006-8, DOI 10.1016/S0146, DOI 10.1016/S0146-664X(76)80006-8]
[7] Knuth, 2010, COMBINATORIAL ALGORI, V4
[8] RASTER SCAN APPROACHES TO COMPUTER GRAPHICS
NEGROPONTE, N
[J]. COMPUTERS & GRAPHICS, 1977, 2 (03) : 179 - 193
[9] Newman W., 1973, PRINCIPLES INTERACTI
[10] Pavlidis T., 1976, ACM Transactions on Mathematical Software, V2, P305, DOI 10.1145/355705.355706

← 1 2 →