Similarity Analysis of Digital Image with Nonparametric Tests on Time Series
Abstract
Similarity search is concerned with efficiently locating subsequences or whole sequences in large archives of sequences. Since the multimedia data can be easily represented as a time series the concept of time series similarity search can be easily extended to compute the similarity between two digital images. Several distance measures such as Euclidean distance, Earth Mover’s Distance (EMD), etc have been used in finding the similarity between two given time series. In the proposed work, time series similarity analysis that uses nonparametric test statistics is adopted to find similarity between the given images. Initially the given images are transformed into time series and its dimensionality is reduced. The resultant time series is represented as clusters by the use of k-means clustering and the similarity distance between two images is found using NonParametric Tests (NPT). Also, a Composite Similarity Measure (CSM) that comprises of EMD and nonparametric tests is proposed. The experimental results show that the proposed measure is well suited for measuring the subjective similarity between two images.
Keywords
Full Text:
PDFReferences
R. Agarwal, Christos Faloutsos, and Arun N. Swami, “Efficient, similarity search in sequence databases”, Proc. of the 4th International Conference of Foundations of Data, Organization and Algorithms (FODO), Chicago, Illinois, pp. 69–84, 1993.
R. Agarwal, K. Lin, H.S. Sawhney , and K. Shim, “Fast similarity search in the presence of noise, scaling and translation in time series database”, In Proc. 6th String Processing and Information Retrieval Symposium, SPIRE, 1995, pp. 16–23.
Christos Theoharatos, Nikolaos A. Laskaris, George Economou, and Spiros Fotopoulos, “A Generic Scheme for Color Image Retrieval Based on the Multivariate Wald-Wolfowitz Test”, IEEE Trans. Knowledge and Data Engineering, vol. 17, no. 6, pp. 808 – 819, 2005.
Durga Toshniwal, and R.C. Joshi, “Similarity Search in Time Series Data using Time Weighted Slope”, Informatica, vol. 29, pp.79–88, 2005.
C. Faloutsos, M. Ranganathan, A.O. Mendelzon, and T. Milo, “A signature technique for similarity-based queries”, in Proc. ACM SIGMOD International Conference on Management of Data, 1994 pp. 419–429.
Florence Duchene, Catherine Garbay and Vincent Rialle, “Learning recurrent behaviors from heterogeneous multivariate time-series”, Artificial Intelligence in Medicine, vol.39, pp. 25 – 47, 2007
Francesc Serratsa and Alberto Sanfeliu, “Signature versus histogram: Definitions, distances and algorithms”, Pattern Recognition, vol.39, pp.921-934, 2006.
George Kollios, Dimitrios Gunopulos, Nick Koudas, and Stefan Berchtold, “Efficient Biased Sampling for Approximate Clustering and Outlier Detection in Large Data Sets”, IEEE Trans. Knowledge and Data Engineering, vol. 15, no. 5, pp. 1170–1181, 2000.
Hung Chim and Xiaotie Deng, “Efficient Phrase-Based Document Similarity for Clustering”, IEEE Trans. Knowledge and Data Engineering, vol.20, no.9, pp. 1217–1229, 2008.
Hyo-Sang Lim, Kyu-Young Whang, and Yang-Sae Moon, “Similar Sequence Matching supporting variable-length and variable-tolerance continuous queries on time series data stream”, International Journal on Information Sciences, vol. 178, pp. 1461–1478, 2008.
Jorge Caiado, Nuno Crato, and Daniel Pena, “A periodogram-based metric for time series classification”, Computational Statistics and Data Analysis, vol.50, pp. 2668 – 2684, 2006.
E.J. Keogh, and M. Pazzani, “Relevance feedback retrieval of time series data”, in Proc. 22th Annual International ACM-SIGIR Conference on Research and Development in Information Retrieval, 1999. pp 183-190.
E.J. Keogh and M.J. Pazzani, “An enhanced representation of time series which allows fast and accurate classification, clustering and relevance feedback”, in Proc. 4th International Conference on Knowledge Discovery and Data Mining, KDD, 1999, pp.239-243.
C.R. Kothari, “Research Methodology”, 2nd Edn, New age international publishers, New Delhi, 2008.
Kristen Grauman and Trevor Darrell, “Fast Contour Matching using Approximate Earth Mover’s Distance”, in Proc. IEEE Conference on Computer Vision and Pattern Recognition, Washington DC, 2004, vol.1.
Lei Chen and M.Tamer Ozsu, “Similarity based Retrieval of Time Series Data Using Multi-Scale Histograms”, Technical Report, University of Waterloo, CS-2003-31, 2003.
P.B. Patil, U.P. Verma, “Numerical Computational Methods”, 2nd Edn, Narosha publications, New Delhi, 2009.
S. Peleg, M. Werman, and H. Rom, “A unified approach to the change of resolution: Space and gray-level”, IEEE Trans. pattern Analysis and Machine Intelligence, vol. 11, pp. 739-74, 1999.
Rawshan Basha and Jamal Ameen, “Unusual Sub-Sequence Identifications in Time Series with Periodicity”, International Journal of Innovative computing, Information and Control, vol.3, no.2, pp. 471- 480, 2007.
Sangjun Lee, Dongseop Kwon and Sukho Lee, “Minimum distance queries for time series data”, Journal of Systems and Software, vol.69, pp.105 -113, 2004.
J. Scargle, B. Jackson and J. Norris, “Adaptive Piecewise Constant modeling of signals in Multidimensional spaces”, PHYSTAT, pp. 157 – 161, 2003.
Srivatsan Laxman, and P.S. Sastry, “Survey of temporal data mining”, Sadhana, vol.31, Part 2, pp.173-198, 2006.
Sung-Hyuk Cha and Sargur N. Srihari, “On measuring the distance between histograms”, Pattern Recognition, vol.35, pp.1355-1370, 2002.
Xiaojun Wan, “A novel document similarity measure based on earth mover’s distance”, International Journal for Information Sciences, vol.177, pp.3718-3730, 2007.
Xiaoyan Liu, Zhenjiang Lin and Huaiqing Wang, “Novel online methods for time series segmentation”, IEEE Trans. Knowledge and Data Engineering, vol.20, no.12, pp. 1618-1626, 2008.
Yan-Ping Huang, Chung-Chian Hsu and Sheng-Hsuan Wang, “Pattern recognition in time series database: A case study on financial database”, Expert Systems with Applications, vol.33, pp.199-205, 2006.
Yong Rui and Thomas S. Huang (1999) , “Image Retrieval: Current Techniques, Promising Directions, and Open Issues”, Journal of Visual Communication and Image Representation, 10, pp. 39-62, available: http://www.idealibrary.com on
Yossi Rubner, Carlo Tomasi and Leonidas J. Guibas, “The Earth Mover’s Distance as a Metric for Image Retrieval”, International Journal of Computer Vision, vol.40, pp.99-121, 2000.
Refbacks
- There are currently no refbacks.
This work is licensed under a Creative Commons Attribution 3.0 License.