Project topics and materials
Get Complete Project Material File(s) Now! »
Recent Feature Extraction Methods
Standard methods extract features from the images which are either global, region-based or pixel-based. In all of these cases, the parameters are computed using the full set of pixels composing the images, with the difference residing in the amount of data which is considered for the estimation of each parameter.
Recent approaches have been defined which operate in a different way, by extracting ”interesting” points from the image, making local decisions at every image point whether there is a feature of a given type at that point or not. The resulting features will be subsets of the image domain, often in the form of isolated points, continuous curves or connected regions; the remaining points are discarded.
The most representative of these approaches, quite popular during the last decade and not treated here extensively, is the Scale Invariant Feature Transform (SIFT), which extracting diverse parameters related to salient points to provide a feature description of the image (Lowe, 1999). SIFT descriptors are invariant to scale, rotation and affine distortion, and partially invariant to illumination conditions.
Other recent methods are GLOH (Gradient Location and Orientation Histogram) (Mikolajczyk & Schmid, 2005), a SIFT-like descriptor that considers more spatial regions for the histograms, reducing the higher dimensionality of the descriptor through principal components analysis (PCA), and SURF (Speeded Up Robust Features) (Bay et al., 2006), a robust image detector and descriptor inspired by SIFT and based on sums of 2D wavelet coefficients; recently, the region-based LESH (Local Energy based Shape Histogram) has been defined, which encodes the salient shapes in the image by accumulating local energy along several filter orientations (Sarfraz & Hellwich, 2008).
Clustering
Extracting the parameters which describe the image content, as presented so far, generate additional data related to each image, making very hard to handle the full set of features in practice for each image element, especially if different kinds of primitives (color, texture, shape) are aggregated. To solve this problem, systems often adopt methods to reduce or compactly represent the feature space, which can be attributed to the general concept of clustering.
Clustering is a method of unsupervised learning, in which data points which are similar according to some criteria are grouped together. Instead of storing the full information about the data instances, therefore, only this compact information is taken into consideration to enable fast queries on the image content.
Clustering algorithms are many and can be classified in different groups. Algorithms which split the data recursively until a stopping criterion is met are divisive, while algorithms which initialize each cluster with a single pattern and successively merge clusters together are agglomerative. Clustering can be monothetic or polythetic if the features are considered sequentially or simultaneously, and hard or fuzzy if the elements are assigned to each cluster in a definitive way or with a certain degree of membership, respectively. They can be deterministic or stochastic, and incremental or not depending on computing resources constraints (Jain et al., 1999).
A popular clustering algorithm is k-means (Steinhaus, 1956), which assigns each data point to the cluster whose center is nearest, where the center is the average of all the data values in the cluster. With this algorithm the number of classes must be specified in advance, and since the clusters centers are randomly generated and then updated iteratively, k-means is not guaranteed to produce the same output if run twice on the same data. A well-known variation of k-means is the ISODATA algorithm (Ball & Hall, 1965), based on repetitive merging and splitting of the clusters.
Image Indexing and Retrieval and Data Compression
The domain of image compression is in constant development in the internet era, in order to overcome the problem posed by bandwidth and storage limitations. In parallel to the studies on the extraction of the right parameters from the data, many efforts have been made to represent the data in a compact form, and sometimes the fields of image compression and image parametrization for indexing and retrieval intersect. The merging of compressed data representation and feature extraction has come in the years with different motivations and from different ideas, which we can categorize in two trends. The first one comes from the idea of reducing computation time in retrieval systems by accessing directly the compressed content, skipping the decompression step. This is achieved either by using compression coefficients as features, either by using parameters, previously extracted to enable a compact encoding of the images, as features which can be randomly accessed to characterize the informational content of the objects.
The second, more recent trend, enables the direct comparisons of two images or general objects. In this approach the compression is not thought as a way to save storage space and/or transmission time, but as a way to quantify the information shared by the objects, estimated through data compression solutions via an implicit pattern matching process. Recently systems have been defined that couple these two aspects of compression to jointly compress and index scientific datasets.
While a general introduction to compression techniques and compression-based classification methods is contained in the next chapter, we briefly analyze here some interesting works on these topics.
Indexing in Compressed Content
It is very unlikely nowadays to transmit and store data in uncompressed format, and every algorithm accessing the content of an image must first uncompress the data, consuming time and resources. Therefore, the idea came of indexing directly in the compressed content, to enable fast queries on the objects content, skipping the decompression step. Methods to retrieve patterns within compressed text files have been proposed by Farach and Toroup (1998) and by Grossi and Vitter (2000), while a recent variant of the LZ-77 compressor (ref. 2.3.1.1) enabling random access to the compressed content is defined by Kreft and Navarro (2010).
At the same time, compression features have been considered for direct image indexing, even though in recent years the interest in this research area has dropped, with the last comprehensive overviews on image indexing in the compressed domain being (Mandal et al., 1999) and (Wang et al., 2003). Zhang et al. (1995) propose to extract information from fractal codes (Jacquin, 1993), exploiting the similarities between regions of the image at different resolutions. Zhu et al. (2002) use as images features the codebooks computed by compressing the image using Vector Quantization (ref. 2.3.2.1); a similar approach is used with the wavelet coefficients (Idris & Panchanathan, 1995) and the Discrete Cosine Transform (DCT) coefficients employed by JPEG (ref. 2.3.2.2) (Podilchuk & Zhang, 1998). In a similar way, Tabesh et al. (2005) use as image features the code lengths of each band of the wavelet transform used by JPEG2000 (ref. 2.3.2.2). Features related to shapes are considered by Swanson et al. (1996), who embed geometrical information within the compressed file by first segmenting the image and then separately coding each region with a codebook of DCT coefficients, storing the region’s position; in this way a single segment is described by its DCT coefficients, and may be directly accessed without decompression.
It has to be remarked that the considered compression features characterize mainly the textural information.
Table of contents :
R´esum´e
Abstract
Contents
Acknowledgments
Introduction
1 Image Retrieval Systems
1.1 Content-based Image Retrieval Systems
1.1.1 Feature Extraction
1.1.1.1 Color
1.1.1.2 Texture
1.1.1.3 Shape
1.1.1.4 Recent Feature Extraction Methods
1.1.2 Clustering
1.1.3 Computation of Similarity
1.1.4 Conclusions
1.2 Image Indexing and Retrieval and Data Compression
1.2.1 Indexing in Compressed Content
1.2.2 Compressing through Prediction
1.2.3 Compression-based Retrieval Systems
1.2.3.1 Joint Compression and Indexing
1.3 Proposed Concepts
2 From Shannon to Kolmogorov and Compression
2.1 Information and Complexity
2.1.1 Shannon Entropy
2.1.1.1 Shannon-Fano Code
2.1.1.2 Kullback-Leibler Divergence
2.1.2 Kolmogorov Complexity
2.1.2.1 Shannon’s Lacuna
2.1.2.2 Definition of Algorithmic Complexity
2.1.3 Relations Shannon/Kolmogorov
2.1.4 Normalized Information Distance
2.1.5 Relations of AIT with other Areas
2.1.5.1 Minimum Message Length
2.1.5.2 Minimum Description Length
2.1.5.3 Bayesian Model Comparison
2.1.5.4 Occam’s Razor
2.1.5.5 An example: the Copernican vs. the Ptolemaic Model
2.1.6 Conclusions
2.2 Normalized Compression Distance
2.2.1 Approximating AIT by Compression
2.2.2 Definition of Normalized Compression Distance
2.2.3 Computational Complexity of NCD
2.2.4 Other Compression-based Similarity Measures
2.3 Basics of Compression
2.3.1 Lossless Compression
2.3.1.1 Dictionary Coders
2.3.1.2 Compression with Grammars
2.3.1.3 Entropy Encoders
2.3.1.4 Delta Compression
2.3.1.5 Specific Compressors
2.3.2 Lossy Compression
2.3.2.1 Quantization
2.3.2.2 JPEG, JPEG2000 and JPEG-XR
2.3.3 Impact of Compressor’s Choice in NCD
2.4 Summary
3 Contributions to Algorithmic Information Theory: Beyond NCD
3.1 Algorithmic Relative Complexity
3.1.1 Cross-entropy and Cross-complexity
3.1.2 Relative Entropy and Relative Complexity
3.1.3 Compression-based Computable Approximations
3.1.3.1 Computable Algorithmic Cross-complexity
3.1.3.2 Computable Algorithmic Relative Complexity
3.1.3.3 Relative Entropy, Revised
3.1.3.4 Symmetric Relative Complexity
3.1.4 Applications
3.1.4.1 Authorship Attribution
3.1.4.2 Satellite Images Classification
3.1.5 Conclusion
3.2 Relation PRDC – NCD
3.2.1 Definition of PRDC
3.2.2 Link with NCD
3.2.3 Normalizing PRDC
3.2.4 Delta Encoding as Conditional Compression
3.3 Beyond NCD: Compression with Grammars
3.3.1 Complexity Approximation with Grammars
3.3.2 Summary
4 New Compression-based Methods and Applications
4.1 Fast Compression Distance
4.2 Content-based Image Retrieval System
4.2.1 1 Dimensional Encoding
4.2.1.1 Speed Comparison with NCD
4.2.2 Image Retrieval and Classification
4.2.2.1 The COREL Dataset
4.2.2.2 The LOLA Dataset
4.2.2.3 An Application to a Large Dataset: Stewenius-Nister
4.2.2.4 Image Classification
4.2.3 Authorship Attribution
4.2.4 Summary
4.2.5 Conclusions
4.3 Applications to Remote Sensing
4.3.1 Hierarchical Clustering – Optical Data
4.3.2 Hierarchical Clustering – SAR Data
4.3.2.1 Estimation of the Optimal Equivalent Number of Looks .
4.3.3 Satellite Images Classification
4.3.4 Semantic Compressor
4.3.5 Conclusions
4.4 Applications to Environmental Projects
4.4.1 Wild Animals Protection
4.4.1.1 Fawns Detection with FCD
4.4.2 Vulcanology
4.5 Conclusions
5 Conclusions and Discussion
List of Abbreviations
Bibliography
