Surface trees – Representation of boundary surfaces using a tree descriptor

• Surface trees are presented as a new method to represent discrete surfaces.
• This new 3D descriptor is coded as a chain using an alphabet of eleven symbols.
• Morphological transformation to the surface are made as simple grammatical techniques.
• Surface trees description offers a set of properties that allow data analysis.
• A compact lossless representation of surfaces is a direct contribution of this work.

Many applications in fields as diverse as computer graphics, medical imaging or pattern recognition require the usage of the boundary of digital objects, or discrete surface. A discrete surface is a set of orthogonal quadrilaterals connected to each other that is typically represented either as a face adjacency graph or as a polygon mesh. In this work we propose a new method, named surface trees, to represent discrete surfaces. Surface trees allow the representation of any discrete surface by coding a tree structure contained in the face adjacency graph. This method uses an alphabet of nine symbols, in addition to the parenthesis notation, to codify trees of maximum degree four. Surface trees are a compact way of representing any discrete surface at the same time they preserve geometrical information and provide invariance under translation and rotation. We demonstrate our method on synthetic surfaces as well as others obtained from real data.