No Feature Data Analytics: Compression Pattern Recognition

Abstract

Similarity matrix shows the similarity degree between each data pairs, it actually plays a core role in a number of dimensionality reduction methods, since the objective function builds upon this matrix. While compression-based similarity measures are effectively employed in applications on diverse data types as basically parameter free approach, a fast compression distance (FCD) metric has been proved to be able to achieve similar classification performance comparing with the Normalized Compression Distance (NCD) method, regarding small- to medium- size datasets [1]. The FCD is claimed as combining a fast speed without skipping the joint compression step which obtains better performance compared with NCD [2]. The idea behind is: the LZW algorithm extracts a dictionary D(x) from each image patch, and encode into a string x, in ascending order. The definition of FCD is defined as an operation which mainly takes account of the joint number of patterns within two dictionaries D(x) and D(y). In this research, we use FCD together with t-SNE to visualize a large semantic annotated TerraSAR-X dataset as a study case. The dataset contain image patches from 288 TerraSAR-X images with a total number of over 60,000 individual image patches. The visualizations represent the annotated semantic labels in such an intuitive way which helps us to better understand the relationships between their annotated semantics and how their actual similarities are in manifold space. Our obtained results show that the FCD based similarity matrix effectively provides us a fast yet performance preserved insights in high-dimensional datasets with a non-parametric distance metric. Via the visualization on TerraSAR-X dataset, we have gained quick intuition and better understanding of the connections between the annotated semantics and the relationships within the data which is revealed as similarities in manifold space. The visualization interpretation is based on a vega-style interactive tool, which allows user zoom in, zoom out for processing large amount of data points. Change Detection methods are dependent on the extracted image features and measures of similarity used for the comparison of the observed scene at different time moment. The NCD has an important advantage; it does not use features and compares the intrinsic data information. The change detection is thus an un-polarized estimator for temporal changes. The method is validated on two areas with visible changes such as flooding and tsunami effects. The results are compared with the ground truth data. The influence of natural disasters, as well as climate warming of the global environment increased in the past decades. Therefore, the detection of changes in a satellite image time series is a trivial task [3]. In order to do this, the calculation processes can be divided into several phases. The first represents the preprocessing, which includes an alignment of all images as well as the creation of patches in a region of interest. We propose here to use the Sentinel-1 SAR data. The second phase encloses the generation of a distance matrix of the patches from two images. In the last phase a threshold is applied to the created matrix, in order to show the changes in a binary way as binary change map (BCM). The results show that a compression-based approach is working with very good results on SAR data. Moreover, a visual evaluation of the resulting images shows that the compression-based approach detects the flooded areas within a region. Furthermore, if the input is reordered with the Burrows and Wheeler transformation [4], the resulting image is better in some areas that the base method. This shows the robustness of NCD. [1] C. Daniele and M. Datcu, “A fast compression-based similarity measure with applications to content-based image retrieval,” Journal of Visual Communication and ImageRepresentation, vol. 23, pp. 293–302, February 2012. [2] M. Li, X. Chen, X. Li, Ma. B., and P.M.B. Vitanyi, “The similarity metric,” IEEE Transaction of Information Theory, vol. 50, pp. 3250–3264, 2004. [3] M. Coca, A. Anghel, M. Datcu, “Normalized compression distance for SAR image change Detection”, pp. 1-3, 2018. [4] R. Giancarlo, A. Restivo, M. Sciortino, “From first principles to the Burrows and Wheeler transform and beyond, via combinatorial optimization”, Elsevier Theoretical Computer Science, vol. 387, pp. 236-248, 2007.