TUD Logo

TUD Home » ... » Results of student work » Minor Theses » S. Broecker

Computer Graphics

Minor Thesis of Stefan Broecker

Segmentation of 3D-Models

Study Course: Media Computer Science, Winter Semester 2005/2006
Institute: Software and Multimedia Technology
Lab: Computer Graphics and Visualization

Professor & Tutor: Prof. Dr. Stefan Gumhold

Contents

  • Introduction
  • Task
  • Method
  • Realization
  • Description of the Application
  • Download

Introduction

In computer graphics, objects can be described with polygonal meshes. They are fast to visualize and there are a lot of refinement tools existing. The texturing of polygonal meshes offers a possibility to visualize detailed objects, as well. Therefore, image files are wrapped around the mesh. With this method, for example color and surface details can be represented. To use different file textures, it can be necessary to divide the mesh into several parts. For instance, a human model would be divided into arms, legs, torso and head. Segmentation means to divide complex polygonal meshes into several meaningful parts. To illustrate this, we can observe pictures. A picture of a wanderer in a landscape could be divided into the foreground (wanderer) and the background (landscape).

One general idea of segmentation is to group similar elements of an object. Therefore, one observes their features. Elements with similar features can be grouped together. In image processing, one can observe grey scale values to group pixels. For 3D-models, one can use space coordinates or normals to group faces. Quality measures can be used to evaluate the result of a segmentation in an objective manner. These measures are based on the observed features.

Task

This work pursues the aim to divide 3D-models automatically into primitives. For instance, a cube should be divided into six parts, whereas every part is one of the six planar surfaces of the cube. On the other hand, a can should be divided into bottom, top and can body. For that, an existing segmentation method should be extended.

Method

To divide a 3D-model into parts (clusters) of simple shape, similar faces are grouped. So every cluster forms a certain shape. These shapes should be similar to primitive objects. To achieve this, we use reference objects. These so-called proxies are used to compare ideal shapes to cluster shapes. Every cluster has a proxy assigned to. The more similar the clusters are to their proxies, the better they approximate the shape of a primitive.

Proxies can be represented by quadratic functions. With these quadrics, one has the possibility to approximate for example planar, ellipsoid- and cylinder-shaped areas. The problem is to find the optimal shape and placement of the proxies. Once this optimum is found, the mesh will be divided into clusters with an approximated shape of their proxies.

The so-called Lloyd-segmentation offers one possible solution. Here, the segmentation problem is considered as an optimization problem. The error between the clusters and their proxies should be optimized respectively minimized. The idea is to initialize the proxies randomly at the beginning and then to search iteratively for the optimal shape and placement. Therefore, the algorithm is divided into two parts. In the first phase, the clusters are optimized for fixed proxies. In the second phase, the proxies are optimized for fixed clusters. By alternating these phases, the clusters and the proxies come closer to each other until a minimum is reached. In the sense of an optimization problem, an optimal segmentation is found then .

Screenshot
Left: 3D-model without segmentation, right: model with segmentation (every cluster is represented by another color)

Realization

The application was developed with Microsoft Visual Studio .NET 2003 in C++. It is based on the CGV-Template-Library of Dr. Gumhold. The GUI and the rendering with OpenGL and certain routines were still implemented. An existing segmentation method, using planes as proxies, was still implemented, as well.

A short Description of the Application

The program can be executed with the file "MeshSegmentor.exe". To load a 3D-model, click in the right window at "Mesh" (optionally Strg+M) and then at "PM". Now, a menu will open up. Pressing the upper "Execute"-button, a dialog will appear to load model data. Some example models can be found in the folder "Meshes_Polygonal".

In the 3D-view, the angle of view can be controlled with the mouse and additionally with the Alt-button. Options for the segmentation procedure can be found in the right window under "MeshSegm" (optionally Strg+X). The most important options are listed below.

  • nrClusters: the number of clusters, into the model should be divided
  • showProxies/showProxyNr: displays the proxy of every cluster after a segmentation
  • clusterMeasure: determines, which features will be observed during the segmentation process / For this work, the following measures are relevant:
    • normal: use face normals as feature / planes as proxies
    • normalTayl: use face normals as feature / quadrics as proxies
    • distance: use space coordinates as feature / planes as proxies
    • distTayl: use space coordinates as feature / quadrics as proxies
  • build clustering: executes the whole segmentation procedure

Another possibility to use the application is to press F1 in the 3D-view to activate hot keys. These hot keys can be used to modify the options.

Screenshot
Left: 3D-view, right: options for the segmentation procedure

Download

  • Executable program (.zip): Download (8,14 MB)
  • Paper (.pdf): Download (2,53 MB)
  • Lecture foils (.pdf): Download (0,75 MB)
Last modified: 1st Feb 2010, 2.40 PM
Author: Dipl.-Medieninf. cand. Johannes Richter