Generating compact representations of static scenes by means of 3D object hierarchies

Angel Domingo Sappa, Miguel Angel Garcia

    Research output: Contribution to journalArticleResearchpeer-review

    1 Citation (Scopus)


    This paper presents a new heuristic algorithm for computing a compact hierarchical representation of the objects contained in a 3D static scene. The algorithm first builds a fully-connected adjacency graph that keeps the costs of grouping the different pairs of objects of the scene. Afterward, the graph's minimum spanning tree is computed and its edges sorted in ascending order according to their cost. Next, from that sorted list, a cost-based clustering technique is applied, thus generating new objects at a higher level in the hierarchy. A new object can be defined after merging two or more objects according to their corresponding linking costs. The algorithm starts over by generating a new adjacency graph from those new objects, along with the objects that could not be merged before. The iterative process is applied until an adjacency graph with a single object is obtained. The latter is the root of the hierarchical representation. Balance and coherence of the hierarchy, in which spatially close objects are also structurally close, is achieved by defining an appropriate cost function. The proposed technique is evaluated upon several 3D scenes and compared to a previous technique. In addition, the benefits of the proposed technique with respect to techniques based on octrees and kd-trees are analyzed in terms of a practical application. © Springer-Verlag 2007.
    Original languageEnglish
    Pages (from-to)143-154
    JournalVisual Computer
    Issue number2
    Publication statusPublished - 1 Feb 2007


    • Hierarchical representation
    • Minimum distance computation
    • Minimum spanning tree
    • Object clustering
    • World modeling


    Dive into the research topics of 'Generating compact representations of static scenes by means of 3D object hierarchies'. Together they form a unique fingerprint.

    Cite this