The Algorithm Design Manual
About the Book
Programming Challenges

The Stony Brook Algorithm Repository

Steven Skiena
Stony Brook University
Dept. of Computer Science

1.6.13 Shape Similarity

Problem Input | Problem Output

INPUT                    OUTPUT


Input Description: Two polygonal shapes, P_1 and P_2.

Problem: How similar are P_1 and P_2?

Excerpt from The Algorithm Design Manual: Shape similarity is a problem that underlies much of pattern recognition. Consider a system for optical character recognition (OCR). We have a known library of shape models representing letters and the unknown shapes we obtain by scanning a page. We seek to identify an unknown shape by matching it to the most similar shape model.

The problem of shape similarity is inherently ill-defined, because what ``similar'' means is application dependent. Thus no single algorithmic approach can solve all shape matching problems. Whichever method you select, expect to spend a large chunk of time tweaking it so as to achieve maximum performance. Don't kid yourself -- this is a difficult problem.


Implementations

  • Shape similarity testing via turning functions (C) (rating 8)
  • SegMatch: Shape Segmentation and Shape Matching (C++) (rating 8)
  • KML: Kernel-Machine Library (C++) (rating 7)
  • SVMlight implementation of Support Vector Machines (C) (rating 7)
  • LIBSVM -- A Library for Support Vector Machines (C++) (rating 7)
  • SNNS - Stuttgart Neural Network Simulator (C) (rating 5)

  • Recommended Books

    Algorithms for Clustering Data by A. Jain and R. Dubes Pattern Classification and Scene Analysis by R. Duda and P. Hart

    Related Problems


      
    Graph Isomorphism
      
    Medial-Axis Transformation



    This page last modified on 2008-07-10 .
    www.algorist.com