Control of Polygonal Mesh Resolution for 3-D Computer Vision

Andrew E. Johnson, Martial HebertGraph. Model. Image Process 1998 · DOI

TL;DR

This paper introduces a novel algorithm for controlling the resolution of 3D polygonal meshes, crucial for computer vision tasks. It achieves this by iteratively normalizing edge lengths while preserving the object's shape, addressing the limitations of existing methods that often prioritize rendering speed over accurate geometric representation for vision applications.

What Problem Does This Paper Address?

In 3D computer vision, polygonal meshes are a common way to represent objects, but their "resolution" – the spacing of vertices – is often uneven due to how 3D data is acquired. This unevenness makes it difficult to perform consistent local measurements (like calculating curvature) across the mesh, which is essential for many computer vision tasks such as registration, segmentation, and surface reconstruction. Existing mesh simplification techniques, primarily developed for computer graphics, focus on reducing the number of polygons for faster rendering and don't adequately address the need for uniform vertex distribution for accurate geometric analysis. This paper aims to bridge this gap by providing a method to control mesh resolution in a way that's beneficial for computer vision.

Methods

The core of the proposed method is an iterative algorithm that normalizes edge lengths within a mesh while preserving its shape. It uses two primary operations:

  • Edge-split: Used to shorten edges that are too long. This operation is shape-neutral.
  • Edge-collapse: Used to shorten edges that are too short. This operation can alter shape.

The algorithm prioritizes operations based on a combination of:

  • Shape Change Measure: A novel metric that quantifies the difference between the mesh before and after an edge operation. This measure is designed to be less conservative than previous methods, allowing operations on sharp features like ridges and creases.
  • Edge Length Weight: A function that assigns higher weight to edges that are further from the desired resolution.

These two factors are combined to order edges in a priority queue. The algorithm iteratively processes edges from the queue, performing splits or collapses. To prevent drastic shape distortion, it also incorporates:

  • Accumulated Shape Change: Tracks the total shape change an edge has undergone over multiple operations.
  • Global Shape Change Bound (CMAX): A limit on the total allowable shape change for the entire mesh.

The algorithm also includes specific handling for mesh boundaries to ensure their preservation.

Datasets

The paper demonstrates its algorithm's effectiveness on various 3D datasets from different sensing modalities, including:

  • Computed Tomography (CT) data (e.g., a femur bone).
  • Range images (e.g., an industrial scene with I-beams, pipes, and a water heater tank).
  • Data generated from Marching Cubes algorithm (e.g., a rubber ducky model).
  • Digital elevation maps (e.g., a facility model).

The paper does not introduce new benchmark datasets but rather showcases the algorithm's versatility on existing types of data.

Key Insights and Ideas

  • Computer Vision Needs Uniform Resolution: Unlike computer graphics, where mesh simplification is about rendering speed, computer vision requires meshes with evenly distributed vertices for reliable local geometric analysis.
  • Novel Shape Change Measure: The proposed distance-based shape change measure is more robust to sharp features (ridges, creases) than traditional methods, enabling more aggressive simplification without sacrificing critical geometric details.
  • Balancing Shape and Resolution: The algorithm effectively balances the need to normalize edge lengths with the imperative to preserve the object's shape by carefully ordering operations and bounding accumulated shape change.
  • Hierarchical Representations: The algorithm naturally generates mesh hierarchies, which are valuable for coarse-to-fine approaches in computer vision.

Key Results

The algorithm successfully generates normalized meshes with a much tighter distribution of edge lengths compared to the original meshes. This is visually demonstrated through wireframe and shaded views, as well as edge length histograms.

  • Improved Resolution Control: The algorithm can produce meshes of arbitrary resolution by adjusting input parameters.
  • Shape Preservation: The method effectively preserves the shape of objects, including those with complex features like ridges and boundaries, as shown in examples like the femur bone and the industrial scene.
  • Handling Diverse Data: The algorithm demonstrates generality by working on meshes from CT scans, range images, and volumetric data.
  • Efficiency: The overall computational complexity is O(N log N), where N is the number of edges in the original mesh, making it practical for many applications.

Limitations and Future Work

  • Limitations:
    • The algorithm assumes simple, triangular input meshes. Non-triangular faces need to be triangulated first.
  • While shape preservation is a primary goal, some shape change is unavoidable when edges are removed.
  • The paper focuses on geometric properties; incorporating texture or other surface properties is not addressed.
  • Future Work:
    • Representing mesh hierarchies as continuous streams of operations for on-demand resolution generation and gradual transmission.
  • Extending the algorithm to incorporate texture and other surface properties during normalization.
  • Introducing topology-changing operations (e.g., hole filling, patch merging) to further reduce edge count while maintaining desired resolution.

Summary updated

BibTeX
@article{johnson1998control,
  author = {Andrew E. Johnson and Martial Hebert},
  title = {{Control of Polygonal Mesh Resolution for 3-D Computer Vision}},
  journal = {Graph. Model. Image Process.},
  year = {1998},
  doi = {10.1006/gmip.1998.0474},
}
Figure