A graph-based approach to skin mole matching incorporating template-normalized coordinates

Hengameh Mirzaalian, Ghassan Hamarneh, Tim K. Lee

Abstract

Early detection of melanoma relies on tracking changes in skin moles over time. However, postural changes between clinical scans introduce non-rigid deformations that challenge standard matching algorithms. This paper presents a novel "human back atlas" that maps moles to a normalized coordinate system based on anatomical landmarks. By combining this normalization with a hypergraph matching framework, the proposed method significantly improves the accuracy and robustness of mole tracking compared to traditional computer vision techniques.

Introduction

Melanoma remains a significant cause of cancer-related mortality, making early detection through periodic full-body scans a critical clinical objective. Dermatologists perform "change detection" by comparing images taken months or years apart to identify new, growing, or morphologically changing moles. This task is complicated by the non-rigid nature of the human body; variations in patient posture between scans cause significant shifts in the pixel coordinates of skin lesions.

Clinical scans of a patient's back taken years apart (a) and a dermoscopic view of a skin mole (b).

Existing automated matching algorithms often struggle with these deformations. This research addresses the problem by integrating medical domain knowledge—specifically human anatomy—into a mathematical matching process to bridge the gap between raw geometric data and clinical reality.

Methodology

The proposed system utilizes a two-stage approach to ensure robust mole matching across temporal scans.

1. The Human Back Template (Atlas)

The core innovation is the creation of a standardized coordinate system for the human back. The system identifies four pairs of anatomical landmarks: the neck-shoulder junction, the shoulder-arm junction, the armpits, and the hips.

Anatomical region of interest on the human back used for landmark-based coordinate normalization.

Using these points, a grid of latitudes and longitudes is established. Moles detected in raw images are "warped" into this normalized template using Thin Plate Splines (TPS). This normalization ensures that a mole's coordinates remain consistent relative to anatomical features, regardless of the patient's posture during the scan.

2. Hypergraph Matching

Following coordinate normalization, the matching problem is modeled as a hypergraph task. Moles are represented as nodes, with spatial relationships forming the edges. The authors adapted a hypergraph matching algorithm and developed a custom objective function that evaluates matches based on:

  • Proximity: Distance between moles in the normalized template.
  • Length Agreement: Consistency of distances between pairs of moles.
  • Angular Agreement: Stability of relative angles between groups of moles.

A multiplicative formulation (an "AND" logic) was found to be superior to a weighted sum, requiring a match to satisfy all geometric constraints simultaneously for high confidence.

Experimental Setup

The algorithm was validated using two datasets:

  • Synthetic Data: Hundreds of point set pairs were generated with controlled noise, simulating mole appearance/disappearance and positional shifts to stress-test the algorithm's limits.
  • Real Clinical Data: 56 pairs of digitized dermatological images from an epidemiologic study, captured three years apart. Ground truth was established by expert dermatologists to provide a realistic benchmark for long-term tracking.

Results and Discussion

The proposed method, ModifiedHyp, was compared against state-of-the-art techniques such as Coherent Point Drift (CPD) and Shape Contexts (SC+TPS).

Key findings include:

  • Accuracy Improvement: Utilizing normalized coordinates instead of raw image coordinates led to substantial accuracy gains across all tested matching methods.
  • Error Reduction: In clinical tests, ModifiedHyp demonstrated significantly lower Hamming Distance Error (HDE) and fewer Incorrect Matches (NIM) than standard hypergraph or spectral techniques.
  • Robustness: The system specifically accounts for "null nodes"—moles that appear or disappear between scans—and remains stable even when the number of common moles is low, a scenario where traditional algorithms like CPD often fail.

Conclusion

This research demonstrates that anchoring computer vision tasks in anatomical context significantly enhances the performance of medical image analysis. While the current system requires some human assistance for landmark detection (particularly for the hips), it represents a major step toward a fully automated, end-to-end mole tracking system. Future work will focus on automating landmark detection and extending the model to 3D body scans to better account for torso curvature.

Summary updated

Abstract

Density of moles is a strong predictor of malignant melanoma. Some dermatologists advocate periodic full-body scan for high-risk patients. In current practice, physicians compare images taken at different time instances to recognize changes. There is an important clinical need to follow changes in the number of moles and their appearance (size, color, texture, shape) in images from two different times. In this paper, we propose a method for finding corresponding moles in patient's skin back images at different scanning times. At first, a template is defined for the human back to calculate the moles' normalized spatial coordinates. Next, matching moles across images is modeled as a graph matching problem and algebraic relations between nodes and edges in the graphs are induced in the matching cost function, which contains terms reflecting proximity regularization, angular agreement between mole pairs, and agreement between the moles' normalized coordinates calculated in the unwarped back template. We propose and discuss alternative approaches for evaluating the goodness of matching. We evaluate our method on a large set of synthetic data (hundreds of pairs) as well as 56 pairs of real dermatological images. Our proposed method compares favorably with the state-of-the-art.
BibTeX
@inproceedings{mirzaalian2009graph,
  author = {Hengameh Mirzaalian and Ghassan Hamarneh and Tim K. Lee},
  title = {{A graph-based approach to skin mole matching incorporating template-normalized coordinates}},
  booktitle = {IEEE/CVF Conference on Computer Vision and Pattern Recognition},
  year = {2009},
  doi = {10.1109/cvpr.2009.5206725},
}
Figure