Combinatorial optimization for fitting of digital line and plane

Rita Zrour (1) , Yukiko Kenmochi (1) , Hugues Talbot (1) , Ikuko Shimizu (2) , Akihiro Sugimoto (3)

1 LIGM - Laboratoire d'Informatique Gaspard-Monge
2 TUAT - Tokyo University of Agriculture and Technology
3 NII - National Institute of Informatics

We present a method for fitting a digital line/plane from a given set of 2D/3D grid points. In the framework of discrete geometry, a digital line or plane is defined as a set of grid points located between two parallel lines or planes separated by a small distance. Our purpose is to identify such a pair of Euclidean lines/planes that represents a given set of points. This problem is formulated as a mixed integer/linear programming problem, with the objective to maximize the number of points between the two lines/planes.

Domaines: Informatique [cs]

Rita Zrour, Yukiko Kenmochi, Hugues Talbot, Ikuko Shimizu, Akihiro Sugimoto. Combinatorial optimization for fitting of digital line and plane. International Workshop on Computer Vision and Its Application to Image Media Processing, Satellite Workshop of the 3rd Pacific-Rim Symposium on Image and Video Technology, Jan 2009, Tokyo, Japan. pp.35-41. ⟨hal-00827895⟩