isaacnewton.dev
← Back

A shape descriptor based on statistics of Euclidean distances

20/06/2018 · 6 min

In computer vision, a shape descriptor turns an object's contour into a feature vector a classifier can separate. This work proposes a descriptor built from statistics of the Euclidean distances between contour points.

The method

  • Compute Euclidean distances between every pair of contour points, forming the N × N matrix D.
  • Subdivide D into submatrices according to a parameter arrangement T, giving different observation scales of the shape.
  • Within each submatrix, compute per-column mean, standard deviation and minimum distance.
  • Reduce each submatrix to six features: mean and standard deviation of each of those three vectors.
  • Concatenate the features of every submatrix into the final vector Ω, the shape signature.
Figure 4.4 — computer vision pipeline: segmentation, the proposed descriptor and validation.
Figure 4.4 — computer vision pipeline: segmentation, the proposed descriptor and validation.
Figure 4.1 — sample classes from the generic shapes dataset.
Figure 4.1 — sample classes from the generic shapes dataset.
Figure 4.3 — sample classes from the fish dataset.
Figure 4.3 — sample classes from the fish dataset.

Experimental methodology

  • Image datasets: generic shapes (shapes with occlusion, articulation, rotation and missing parts) and fish (1,100 classes, 10 images per class, 11,000 images with varying scale and rotation).
  • MATLAB pipeline in three stages: morphological segmentation to obtain the contour, extraction of the proposed descriptor, and validation.
  • Supervised classification with Linear Discriminant Analysis (LDA) and leave-one-out cross-validation; the metric is mean accuracy.
  • Parameter evaluation: the arrangement T was varied to maximise class discrimination, keeping the same configuration on both datasets to allow comparison.

Results

  • Proposed descriptor: 100% (generic shapes) and 99.22% (fish).
  • Fourier descriptors: 83.84% and 99.07%.
  • Zernike moments: 91.92% and 12.23%.
  • Curvature: 76.77% and 97.55%.
  • Multiscale Fractal Dimension: 87.88% and 37.32%.
  • Curvature Scale Space: 71.72% and 43.52%.

Accuracy stayed close to the maximum even with arrangements producing fewer descriptors (12, 18 and 24), indicating robustness to deformed and occluded contours and invariance to rotation, scale and translation. The main drawback is complexity: computing all pairwise distances is O(N²), versus O(N log N) for Fourier and Zernike.

Table 5.2 — accuracy of the proposed descriptor against Fourier, Zernike, Curvature, MFD and CSS.
Table 5.2 — accuracy of the proposed descriptor against Fourier, Zernike, Curvature, MFD and CSS.

Future work identified: reducing signature complexity, applying feature selection or optimisation given the large number of descriptors, and using only a subset of the line segments.

Federal University of Ceará, Computer Engineering, June 2018. Supervisor: Jarbas Joaci de Mesquita Sá Junior.
Federal University of Ceará, Computer Engineering, June 2018. Supervisor: Jarbas Joaci de Mesquita Sá Junior.
Download the full paper (PDF, PT)PDF · PT ↓