Discrete surface representation and 3D border tracking algorithm

Yukiko Kenmochi
(Laboratoire A2SI, France)

There already exist various border tracking algorithms of objects in a 2D/3D digital image. One of basic and useful ideas to solve the border tracking problem in 2D is to use a curve structure of the border of a 2D object. The simple extension of the border tracking in 3D will be then to use a surface structure of the border of a 3D object. However, it is actually difficult to find a good definition or representation of 2D surfaces in a 3D discrete space such as a 3D digital image (actually, even in the Euclidean space, there is no "good" definition of 2D surfaces).

In the talk, we first give the overview and classification of various approaches for defining 2D discrete surfaces in a 3D discrete space. We also analyze the difficulty of the problem caused by the spatial discreteness and discuss the advantages and disadvantages of each approach. For our discrete surface representation which provide a good solution for the border tracking problem, we apply some basic ideas of combinatorial topology and algebraic topology, which are also used in some of previous work (but in a different way). After obtaining a discrete surface representation, we consider an algorithm for tracking the border which is always guaranteed to have a surface structure. We also gives some interesting properties of our tracked border and make comparison with the results by other border tracking algorithms.