R3-[Q-Shape] - Research: Extracting Shape Representation from Perception

Extracting shape representation from perception (LRF data)

Shape is represented as jointly boundary-based and structural representation.

  • Boundary-based matching techniques yield excellent results
  • Structure establishes an even wider spatial context, bridging to qualitative & topological information. It is exploited in the assignment of visual parts.


All data is shown with a grid of size 1 meter. Click on the images to view a larger one. The data has been recorded by Dr.-Ing. Thomas Röfer at the University of Bremen using a SICK LMS200 laser.


LRF data is acquired, mapping scan points to the Euclidean plane in a local coordinate system.

The perceived shape is said to be composed out of individual visual parts, which are polylines. Visual parts are determined by a grouping of the scan points. Object transitions are hypothesized wherever two consecutive scan points are farer apart than a threshold (20cm is used). A polyline is intantiated from the scan points.

As details about the connection between the individual features is unknown, these links are represented only in a qualitative manner, namely ordering information.

Hence, a perceived shape can be represented as a vector of polylines. This links to structural representations of shape (e.g., skeletons). However, this approach employs a preceding decomposition.

Polylines obtained are simplified to cancel out noise and to make the data more compact, thus, allowing for efficiency in subsequent processing. Simplification is realized by means of Discrete Curve Evolution, a context-sensitive process of vertex deletion that eliminates noise while preserving important shape features.

An illustration of the process is given as a small animation.

The resulting, simplified polylines serve as primitives in our system.


L.J. Latecki, R. Lakämper, and D. Wolter: Shape Similarity and Visual Parts. Proc. Int. Conf. on Discrete Geometry for Computer Imagery (DGCI), November 2003

L.J. Latecki and R. Lakämper: Shape Similarity Measure Based on Correspondence of Visual Parts. IEEE Trans. Pattern Analysis and Machine Intelligence (PAMI) 22(10), pp. 1185-1190, October 2000