Název: | Function-trees: an efficient data structure for compact binary pictures |
Autoři: | Gallo, Giovanni Spampinato, Daria |
Citace zdrojového dokumentu: | Journal of WSCG. 1997, vol. 5, no. 1-3, p. 144-152. |
Datum vydání: | 1997 |
Nakladatel: | Václav Skala - UNION Agency |
Typ dokumentu: | článek article |
URI: | http://wscg.zcu.cz/wscg1997/wscg97.htm http://hdl.handle.net/11025/15892 |
ISSN: | 1213-6972 (print) 1213-6980 (CD-ROM) 1213-6964 (online) |
Klíčová slova: | struktura dat;3D krajina;trapézové regiony;algoritmy |
Klíčová slova v dalším jazyce: | data structure;3D scene;trapezoidal regions;algorithms |
Abstrakt v dalším jazyce: | In the representation of binary images or of binary three-dimensional scenes two principal paradigms have been introduced: boundary representation and hierarchical decomposition. The data-structure introduced in this paper, called function-tree or function-octree for a 3D scene, is an elementary generalization of the standard quadtree and octree. It combines the compactness of a boundary representation of spatial data with the nice recursive properties of a tree representation. This is achieved by decomposing regularly an image into rectangular sub-images whose black regions are trapezoidal regions. A trapezoidal region (defined in detail in the paper) is a region below the graph of a function. Trapezoidal regions can be, in turn, efficiently encoded with a boundary representation. Efficient algorithms to construct the function-tree are described in the paper. The time complexities of such algorithms are O (n2) for a n × n binary picture and O (n3) for a n × n × n binary scene. The algorithms have been implemented. A final quick review of the possible applications of the proposed structures concludes the paper. |
Práva: | © Václav Skala - UNION Agency |
Vyskytuje se v kolekcích: | Volume 5, number 1-3 (1997) |
Soubory připojené k záznamu:
Soubor | Popis | Velikost | Formát | |
---|---|---|---|---|
Gallo_97.pdf | Plný text | 1,31 MB | Adobe PDF | Zobrazit/otevřít |
Použijte tento identifikátor k citaci nebo jako odkaz na tento záznam:
http://hdl.handle.net/11025/15892
Všechny záznamy v DSpace jsou chráněny autorskými právy, všechna práva vyhrazena.