This paper proposes a new approach for the discovery of common patterns in multiple images by region matching. The issues in feature robustness, matching robustness and noise artifact are addressed to delve into the potential of using regions as the basic matching unit. We novelly employ the many-to-many (M2M) matching strategy, specifically with the Earth Mover's Distance (EMD), to increase resilience towards the structural inconsistency from improper region segmentation of a pattern as a result of various geometric and photometric transformations. However, the matching pattern of M2M is dispersed and unregulated in nature, leading to the challenges of mining a common pattern while identifying the underlying transformation. To avoid analysis on unregulated matching, we propose monolithic matching for the collaborative mining of common pattern from multiple images. The patterns are refined iteratively using the Expectation-Maximization algorithm by taking advantage of the crowding phenomenon in the EMD flows. Experiment results show that our approach is robust and can effectively handle images with background clutter. To pinpoint the potential of CPD, we further use image retrieval as an example to show the application of CPD for pattern learning in relevancy feedback.



  • Hung-Khoon Tan and Chong-Wah Ngo
    Common Pattern Discovery using Earth Mover's Distance and Local Flow Maximization
    International Conference on Computer Vision (ICCV), 2005.
    Full Text: [PDF]
  • Hung-Khoon Tan and Chong-Wah Ngo
    Localized Matching Using Earth Mover's Distance Towards Discovery Of Common Patterns From Small Image Samples
    Image and Vision Computing (IVC), 27(10), 1470:1483, January 2009. Full Text: [PDF]


    For this project, we have created a data set to enable a comprehensive evaluation for CPD tasks. The database is composed of 868 images with 14 common patterns. The common patterns are shot under different background clutters, at varying viewpoints, rotation, scale and lighting changes. The set of 200 negative images randomly selected from the Corel dataset are not included in the attachment owing to copyright issues. Dataset: [readme.txt, vireo_cpd_dataset.rar],