Whence and what are thou, execrable shape? 

John Milton  (Paradise Lost bk. II, l. 681)

 

This webpage contains links to our papers on shape mining and indexing.

1)  Eamonn Keogh, Li Wei, Xiaopeng Xi, Sang-Hee Lee and Michail Vlachos  (2006) LB_Keogh Supports Exact Indexing of Shapes under Rotation Invariance with Arbitrary Representations and Distance Measures. VLDB 2006.
  • An expanded version of the paper is here.
  • Here are the slides, warning the are large files.  1 slide per page PDF (14 meg), or 6 slides per page PDF (10 Meg), or MS powerpoint (26 Meg). 
  • The paper makes extensive use of envelope based lower bounding with the LB_Keogh, here is a page which lists some other uses of LB_Keogh.

2) Li Wei, Eamonn Keogh and Xiaopeng Xi (2006) SAXually Explicit Images: Finding Unusual Shapes. ICDM 2006. [pdf][Powerpoint][ expanded journal version].

3) Dragomir Yankov and Eamonn Keogh. (2006). Manifold Clustering of Shapes ICDM  2006. [pdf]

4) Ken Ueno, Xiaopeng Xi, Eamonn Keogh, Dah-Jye Lee (2006). Anytime Classification Using the Nearest Neighbor Algorithm with Applications to Stream Mining. ICDM  2006. [pdf] (Note: This paper is not exclusively about shape, but does show how to classify shapes with any anytime algorithm).

5) Xiaopeng Xi, Eamonn Keogh, Li Wei, Agenor Mafra-Neto (2007). (tentative title) Finding Motifs in Database of Shapes. SIAM International Conference on Data Mining (SDM2007).

6) Xiaoyue Wang, Lexiang Ye, Eamonn Keogh and Christian Shelton. (2008). Annotating Historical Archives of Images. JCDL 2008 [pdf]

7) Lexiang Ye, Xiaoyue Wang, Dragomir Yankov and Eamonn Keogh (2008). The Asymmetric Approximate Anytime Join: A New Primitive with Applications to Data Mining. SDM 2008. [pdf] Datasets are here. (Note: This paper is not exclusively about shape, but one experiment does deal with shapes).

  • Here are some video clips that show one possible method to convert shapes to time series. Our examples include a Face, an Oak leaf and a Maple leaf. Thanks to Chotirat (Ann) Ratanamahatana for her help in preparing these examples.
  • Here are some high quality PowerPoint slides that give the visual intuition behind converting shapes to time series.
  • We have done some work of shape matching of petroglyphs

Datasets

  • Here is all the data  needed to replicate the experiments in our VLDB 2006 paper. Warning 120 meg file. The password is paper109, if you are looking for data for classification experiments, then see also this webpage.
  • Here is the Mixed-Bag shape dataset. This dataset was also used in Dr. Vlachos paper. 
  • Here is a collection of 74 primate skull images. They are cached here for your convenience, but remain copyright of Glendale College Anthropology Department.
  • Here is a collection of 781 Diatom contours, from 37 different classes. Thanks to A.C. Jalba for sharing these. Everything you need to know about Diatoms is probably here.

Acknowledgements 

  • Thanks to all the donors of data.
  • Thanks to Jason Dorff and Dr. Eric Johnston of for help with primate skull images. 
  • Thanks to Dr. Longin Jan Latecki for useful suggestions and pointers. 

 

This is a phenogram, not a phylogenetic tree. For the current best phylogenetic tree, see the Tree of Life project, starting at their primate page.
 

 

In this section we expand our discussion of some topics that were briefly treated due to space constraints.
In the paper we note that there are many ways to convert a 2D image into a 1D "time series". Here are just some examples:
In the paper we discuss Landmarking ("The idea of “landmarking” is to find the one “true” rotation and only use that particular alignment as input into the distance measure."). Here we give some additional examples:

Domain Dependent: For hand shapes Cheng et. al.  claims “The principal direction is almost parallel with the direction of finger pointing.” For classifying leaves, Wang et. al. start from the "sharpest corner". 

Domain Independent: Gdalyahu and Weinshall  tried to select a viable start point by using the distribution of optimal rotation parameters necessary to align anchor point
In the paper we discuss Rotation Invariant Features. Here we give some additional examples and pointers:

The paper by Dionisio is a very typical example of what we call in the paper "achieving fast rotation invariant matching by extracting only rotation invariant features and indexing them with a feature vector". The paper by Li et. al. offers an excellent overview of techniques to make shape similarity invariant to a variety of "distortions", including rotation, using Fourier techniques.  A fractal based method is presented by Tao et. al.