A Matlab Implementation of a Flat Norm Motivated Polygonal Edge Matching Method using a Decomposition of Boundary into Four 1-Dimensional Currents

Simon P. Morgan, Wotao Yin, Kevin R. VixiearXiv 2008 · arXiv

Introduction

Matching polygonal shapes in computer vision and geometry requires distance metrics that are robust to slight deformations and partial occlusions. A common mathematical framework for this is the flat norm, which treats shape boundaries as "currents" (oriented curves or surfaces). However, standard flat norm implementations often suffer from "cancellation" effects: opposite edges of thin structures—such as a slender arm—can effectively subtract to zero, causing the algorithm to ignore significant geometric features.

This paper presents a robust matching method implemented in Matlab that avoids this cancellation by decomposing boundaries into four distinct 1-dimensional currents: Top, Bottom, Left, and Right. This approach preserves sensitivity to slender protrusions and nearby boundaries that do not perfectly overlap.

Methodology

The proposed algorithm follows a five-step pipeline to compute a matching score between two polygons:

  1. Bitmap Conversion: Polygons are first converted into logical pixel matrices ($M1, M2$), where 1 represents the interior and 0 the exterior.
  2. Edge Decomposition: The boundary is split into four "difference matrices" based on transition direction.
  3. Top (DT): Detects transitions from outside to inside (top-down).
  4. Bottom (DB): Detects transitions from inside to outside (top-down).
  5. Left (DL): Detects horizontal transitions into the shape.
  6. Right (DR): Detects horizontal transitions out of the shape.
The four-current decomposition scheme for polygonal edges.
  1. Gaussian Smoothing: To account for edges that are near but not perfectly aligned, each edge matrix is convolved with a Gaussian kernel. This "blurring" enables the algorithm to find matches between proximal boundaries.
  2. Pointwise Matching: The smoothed matrices for both polygons are multiplied pointwise (e.g., $Top_1 \times Top_2$). This step identifies regions where both shapes share similar edge orientations.
  3. Total Score Calculation: A final scalar matching score is derived using a Euclidean metric that combines the net vertical and horizontal matching components.

Key Insights and Results

The core innovation of this approach is anti-cancellation. By matching "top to top" and "left to left" independently, the method retains information about the thickness and specific orientation of slender regions that would otherwise be lost in a standard oriented flat norm calculation.

Decomposition of two polygons into four oriented edge matrices, demonstrating sensitivity to specific edge directions.

The method is particularly effective at matching "slender protrusions" that are disjoint but close in space. Qualitative results demonstrate that even when two polygons share a boundary, the algorithm correctly identifies a non-match if the edge orientations differ (e.g., a "top" edge for one polygon vs. a "bottom" edge for the other).

Discussion and Future Work

While the method provides a highly sensitive matching score, it is currently a pixel-based approach, making its computational cost dependent on grid resolution. Furthermore, the current implementation provides a matching score rather than a full registration routine. Future work could involve wrapping this score within an optimization loop (such as gradient descent) to handle rigid transformations like rotation and scaling. The authors have provided the full Matlab source code to facilitate such integrations.

Summary updated

Abstract

We describe and provide code and examples for a polygonal edge matching method.
BibTeX
@misc{morgan2008matlab,
  author = {Simon P. Morgan and Wotao Yin and Kevin R. Vixie},
  title = {{A Matlab Implementation of a Flat Norm Motivated Polygonal Edge Matching Method using a Decomposition of Boundary into Four 1-Dimensional Currents}},
  year = {2008},
  eprint = {0812.0340},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/0812.0340},
}
Figure