An elastic partial shape matching technique. (English) Zbl 1123.68114
Summary: We consider the problem of partial shape matching. We propose to transform shapes into sequences and utilize an algorithm that determines a subsequence of a target sequence that best matches a query. In the proposed algorithm we map the problem of the best matching subsequence to the problem of a cheapest path in a directed acyclic graph. The approach allows us to compute the optimal scale and translation of sequence values, which is a nontrivial problem in the case of subsequence matching. Our experimental results demonstrate that the proposed algorithm outperforms the commonly used techniques in retrieval accuracy.
MSC:
| 68T10 | Pattern recognition, speech recognition |
References:
| [1] | Hoffman, D. D.; Richards, W. A., Parts of recognition, Cognition, 18, 65-96 (1984) |
| [2] | Hoffman, D. D.; Singh, M., Salience of visual parts, Cognition, 63, 29-78 (1997) |
| [3] | L.J. Latecki, A. Gross, R. Melter (Eds.), Special issue on shape representation and dissimilarity for image databases, Pattern Recognition 35(1) (2002).; L.J. Latecki, A. Gross, R. Melter (Eds.), Special issue on shape representation and dissimilarity for image databases, Pattern Recognition 35(1) (2002). · Zbl 0988.00035 |
| [4] | Belongie, S.; Malik, J.; Puzicha, J., Shape matching and object recognition using shape contexts, IEEE PAMI, 24, 509-522 (2002) |
| [5] | Grigorescu, C.; Petkov, N., Distance sets for shape filters and shape recognition, IEEE Trans. Image Process., 12, 9 (2003) · Zbl 1279.94017 |
| [6] | Saber, E.; Xu, Y.; Tekalp, A. M., Partial shape representation by sub-matrix matching for partial matching guided image labeling, Pattern Recogntion, 38, 1560-1573 (2005) |
| [7] | Veltkamp, R.; Tanase, M., Part-Based Shape Retrieval (2005), ACM Multimedia: ACM Multimedia Singapore |
| [8] | Biederman, I., Human image understanding: recent research and a theory, CVGIP, 32, 29-73 (1985) |
| [9] | T. Binford, Visual perception by computer, IEEE Conference on Systems and Control, 1971.; T. Binford, Visual perception by computer, IEEE Conference on Systems and Control, 1971. |
| [10] | Brooks, R., Symbolic reasoning among 3D models and 2D images, Artif. Intell., 17, 285-348 (1981) · Zbl 1497.68485 |
| [11] | Pentland, A., Recognition by parts, Proc. ICCV, 23, 612-620 (1987) |
| [12] | L.J. Latecki, V. Megalooikonomou, Q. Wang, R. Lakaemper, C.A. Ratanamahatana, E. Keogh, Partial elastic matching of time series, in: Proceedings of IEEE International Conference on Data Mining (ICDM05), Houston, TX, USA, November 2005, pp. 701-704.; L.J. Latecki, V. Megalooikonomou, Q. Wang, R. Lakaemper, C.A. Ratanamahatana, E. Keogh, Partial elastic matching of time series, in: Proceedings of IEEE International Conference on Data Mining (ICDM05), Houston, TX, USA, November 2005, pp. 701-704. |
| [13] | L.J. Latecki, R. Lakämper, U. Eckhardt, Shape descriptors for non-rigid shapes with a single closed contour, in: Proceedings of IEEE Conference on Computer Vision and Pattern Recognition (CVPR), Hilton Head Island, South Carolina, June 2000, pp. 424-429.; L.J. Latecki, R. Lakämper, U. Eckhardt, Shape descriptors for non-rigid shapes with a single closed contour, in: Proceedings of IEEE Conference on Computer Vision and Pattern Recognition (CVPR), Hilton Head Island, South Carolina, June 2000, pp. 424-429. |
| [14] | Latecki, L. J.; Lakaemper, R., Shape similarity measure based on correspondence of visual parts, IEEE Trans. Pattern Anal. Mach. Intell., 22, 10, 1185-1190 (2000) |
| [15] | B. Chiu, E. Keogh, S. Lonardi, Probabilistic discovery of sequences motifs, in: Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Washington, 2003.; B. Chiu, E. Keogh, S. Lonardi, Probabilistic discovery of sequences motifs, in: Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Washington, 2003. |
| [16] | E. Keogh, S. Lonardi, C. Ratanamahatana, Towards parameter-free data mining, in: Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Seattle, 2004.; E. Keogh, S. Lonardi, C. Ratanamahatana, Towards parameter-free data mining, in: Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Seattle, 2004. |
| [17] | F. Höppner. Discovery of temporal patterns. Learning rules about the qualitative behavior of sequences, in: Proceedings of the European Conference on Principles and Practice of Knowledge Discovery in Databases, Freiburg, 2001, pp. 192-203.; F. Höppner. Discovery of temporal patterns. Learning rules about the qualitative behavior of sequences, in: Proceedings of the European Conference on Principles and Practice of Knowledge Discovery in Databases, Freiburg, 2001, pp. 192-203. · Zbl 1009.68798 |
| [18] | D. Rafiei, On similarity-based queries for sequences data, in: Proceedings of the International Conference on Data Engineering, Sydney, 1999, pp. 410-417.; D. Rafiei, On similarity-based queries for sequences data, in: Proceedings of the International Conference on Data Engineering, Sydney, 1999, pp. 410-417. |
| [19] | Aach, J.; Church, G., Aligning gene expression sequences with time warping algorithms, Bioinformatics, 7, 495-508 (2001) |
| [20] | V. Megalooikonomou, Q. Wang, G. Li, C. Faloutsos, A multiresolution symbolic representation of time series, in: Proceedings of IEEE International Conference on Data Engineering (ICDE05), 2005, Tokyo, pp. 668-679.; V. Megalooikonomou, Q. Wang, G. Li, C. Faloutsos, A multiresolution symbolic representation of time series, in: Proceedings of IEEE International Conference on Data Engineering (ICDE05), 2005, Tokyo, pp. 668-679. |
| [21] | Sakoe, H.; Chiba, S., Dynamic programming algorithm optimization for spoken word recognition, IEEE Trans. Acoust. Speech Signal Process., 26, 1, 43-49 (1978) · Zbl 0371.68035 |
| [22] | D. Berndt, J. Clifford, Using dynamic time warping to find patterns in sequences, in: Proceedings of AAAI-94 Workshop on Knowledge Discovery and Databases, 1994, pp. 229-248.; D. Berndt, J. Clifford, Using dynamic time warping to find patterns in sequences, in: Proceedings of AAAI-94 Workshop on Knowledge Discovery and Databases, 1994, pp. 229-248. |
| [23] | G. Kollios, M. Vlachos, D. Gunopoulos, Discovering similar multidimensional trajectories, in: Proceedings of the International Conference on Data Engineering, 2002, San Jose, pp. 673-684.; G. Kollios, M. Vlachos, D. Gunopoulos, Discovering similar multidimensional trajectories, in: Proceedings of the International Conference on Data Engineering, 2002, San Jose, pp. 673-684. |
| [24] | S. Chu, E. Keogh, D. Hart, M. Pazzani, Iterative deepening dynamic time warping for sequences, in: Proceedings of SIAM International Conference on Data Mining, 2002.; S. Chu, E. Keogh, D. Hart, M. Pazzani, Iterative deepening dynamic time warping for sequences, in: Proceedings of SIAM International Conference on Data Mining, 2002. |
| [25] | B. Yi, K. Jagadish, C. Faloutsos, Efficient retrieval of similar time sequences under time warping, in: Proceedings of the International Conference on Data Engineering, 1998, pp. 23-27.; B. Yi, K. Jagadish, C. Faloutsos, Efficient retrieval of similar time sequences under time warping, in: Proceedings of the International Conference on Data Engineering, 1998, pp. 23-27. |
| [26] | C.A. Ratanamahatana, E. Keogh, Everything you know about dynamic time warping is wrong, in: Workshop on Mining Temporal and Sequential Data, Seattle, 2004.; C.A. Ratanamahatana, E. Keogh, Everything you know about dynamic time warping is wrong, in: Workshop on Mining Temporal and Sequential Data, Seattle, 2004. |
| [27] | G. Das, D. Gunopoulos, H. Mannila, Finding similar sequences, in: Proceedings of the 1st PKDD Symposium, 2003, pp. 88-100.; G. Das, D. Gunopoulos, H. Mannila, Finding similar sequences, in: Proceedings of the 1st PKDD Symposium, 2003, pp. 88-100. |
| [28] | M. Vlachos, M. Hadjieleftheriou, D. Gunopoulos, E. Keogh, Indexing multi-dimensional time-series with support for multiple distance measures, in: Proceedings of ACM SIGKDD, 2003, Washington, pp. 216-225.; M. Vlachos, M. Hadjieleftheriou, D. Gunopoulos, E. Keogh, Indexing multi-dimensional time-series with support for multiple distance measures, in: Proceedings of ACM SIGKDD, 2003, Washington, pp. 216-225. |
| [29] | Mokhtarian, F.; Bober, M., Curvature Scale Space Representation: Theory, Applications and MPEG-7 Standardization (2003), Kluwer Academic: Kluwer Academic Dordrecht · Zbl 1022.68120 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
