Compression of 3D Scientific Data for Archival ...

  • Doc File 624.00KByte



Compression of 3D Scientific Data for Archival, Distribution and Fast Classification

First A. Author, Second B. Author, Jr., and Third C. Author, Member, IEEE

Abstract—In this work, we propose a compression algorithm based on Partitioned Vector Quantization for 3D scientific data, and in particular those generated by remote sensors. One of the dimensions of the input data is treated as a single vector that is partitioned into subvectors of (possibly) different lengths, each quantized separately. Quantization indices and residuals are then entropy coded. Partitioning serves different purposes: vector quantization looses efficiency in high dimension and partitioning is a way of improving it; it allows a better decorrelation of the data in the given dimension, improving compression; the concatenation of the quantization indices can be seen as a projection to a lower dimensional subspace that preserves the original statistical properties of the data; partition indices can be used for fast (remote) browsing and classification. In fact, experimental results with NASA AVIRIS hyperspectral images show that the proposed algorithm achieves state of the art lossless compression on such data, provides near-lossless and lossy capabilities (that could be used for fast browsing and broadcasting on limited bandwidth communication channels), is scalable to arbitrary data size, allows fast classification and target detection in the compressed domain.

Index Terms—About four key words or phrases in alphabetical order, separated by commas. For a list of suggested keywords, send a blank e-mail to keywords@ or visit the IEEE web site at .

INTRODUCTION

A

n increasing number of scientific instruments produce high volume of data in the form of two-dimensional matrices of vectors, also called data cubes. Typical examples are biomedical images, multi, hyper and ultra spectral images, measurements of volumetric parameters like atmospheric temperature and pressure by way of microwaves sounders. Compressing these data presents a challenge for the currently standardized compressors. Beside the three dimensional nature of the measurements, which exhibit correlation along each dimension, the single measurements have values of 16 bits or more. Current state of the art compressors do not perform well on data sources with large alphabets. Furthermore, it is desirable to have a single compressor that can perform well in all of lossless, near lossless, and lossy modes and can scale to data cubes of arbitrary sizes. Lossless compression is often required for data collection and archiving due to the cost of the data collection and that it may be destined to analysis and further elaboration. However, when data is downloaded by users, a lossy mode can be employed to speed up the transmission, since the final users may not need all measurements at their full precision, and in any case, can request further precision only when needed.

In [1] we propose a compression algorithm based on Partitioned Vector Quantization, where one dimension of the cube is treated as a single vector, partitioned and quantized. Partitioning the vector into subvectors of (possibly) different lengths is necessary because the possibly large number of components. Subvectors are individually quantized with appropriate codebooks. The adaptive partitioning uses a novel locally optimal algorithm and provides a tool to reduce the size of the source alphabet. Correlation among the other two dimensions is exploited with methods derived from the image coding domain. Lossless or near-lossless entropy coding can be applied to the residual error. An additional feature of this compression method is the possibility to tightly bound error on a pixel by pixel basis. Due to the hierarchical structure of the data compressed with the proposed algorithm, it is possible to perform classification and target detection directly in compressed domain, with considerable speed and memory savings. The high speed classification and target detection algorithm that we describe here can process 90 percent of the compressed pixels with a simple table lookup, full decompression is only required if exact classification is necessary and it is limited to the 10 percent remaining pixels. Algorithms have been verified experimentally on the lossless and near lossless compression of NASA AVIRIS images.

Section 2 briefly reviews the algorithm in order to introduce the necessary notation. Besides good compression performance, LPVQ presents a number of features that are highly desirable for these kinds of images. A communication paradigm that shows these advantages is outlined and discussed in Section 3.

The problem of classification and the necessary notation is introduced in Section 4. Section 5 presents experimental results on the classification error introduced by LPVQ lossy and near lossless compression modes. Section 6 builds on these experimental observations with an algorithm that speeds up the classification by accepting or rejecting vectors based only on bounds of the VQ error. These error bounds are available at design time or can be extracted from the compressed image. In the same section, the asymptotic behavior is derived. Given a compressed image and a classification threshold, the speed up achieved on the naïve algorithm depends on the acceptance and rejection rates. Experiments on typical AVIRIS images are performed in the same section in order to assess these rates for a number of classification thresholds. The acceptance and rejection rates only depend on the bounds on the quantization error and can be easily derived during the design of the LPVQ. So, these considerations also provide a tool useful to select the quantization parameters (codebook entries and number of partitions) in order to match a desired range of classification speeds.

The Communication Model

An application for which our algorithms were designed is the encoding of information collected by a remote sensing device having limited computational power (satellite, airplane, biomedical imager) and losslessly transmitted to a powerful central server (see Figure 1). The central server decompresses and elaborates the data, performing all necessary adjustments and corrections. Then, re-codes the data in a more compact representation and distributes the result among a number of users that may subscribe the service at different quality levels. A common example is weather information collected by geostationary satellites. The satellites observe of events evolving in a specific geographic area, such as hurricanes, storms, flooding and volcanic eruptions. The collected data have to be faithfully transmitted to a land based central station that analyzes the data, applies some form of enhancement, compressed the data further and sends the result back to the satellite in order to broadcast it to the final users. In this setting, the same satellite is used for both acquisition and broadcasting. More common is the case of the central server performing the transmission. While the compression hardware used in the satellite must be simple and require very low power to function, there is typically little or no limitation to the computational power of the base station.

Definitions

We model a three dimensional data cube as a discrete time, discrete values, bi-dimensional random source [pic] that emits pixels that are [pic]-dimensional vectors [pic]. Each vector component [pic], [pic], is drawn from a finite alphabet [pic] and is distributed according to a space variant probability distribution that may depend on other components. We assume that the alphabet has the canonical form [pic].

Our encoder is based on a Partitioned Vector Quantizer (or PVQ), which consists of [pic] independent, [pic]-levels, [pic]-dimensional exhaustive search vector quantizers [pic], such that [pic] and:

• [pic] is a finite indexed subset of [pic] called codebook. Its elements [pic] are the code vectors.

• [pic] is a partition of [pic] and its equivalence classes (or cells) [pic] satisfy:

[pic] and [pic] for [pic].

• [pic] is a function defining the relation between the codebook and the partition as [pic] if and only if [pic].

The index [pic] of the codeword [pic], result of the quantization of the [pic]-dimensional subvector [pic], is the information that is sent to the decoder.

With reference to the previously defined [pic] vector quantizers [pic], a Partitioned Vector Quantizer can be formally described by a triple [pic] where:

• [pic] is a codebook in[pic];

• [pic] is a partition of[pic];

• [pic] is computed on an input vector [pic] as the concatenation of the independent quantization of the [pic] subvectors of [pic]. Similarly, the index vector sent to the decoder is obtained as a concatenation of the [pic] indices.

The design of a Partitioned VQ aims at the joint determination of the [pic] partition boundaries [pic] and at the design of the [pic] independent vector quantizers having dimension [pic], [pic].

In the following, given a source vector [pic], we indicate the [pic] subvector of boundaries [pic] and [pic] with the symbol [pic] (for simplicity, the [pic] and [pic] spatial coordinates are omitted when clear from the context). The mean squared quantization error between the vector [pic] and its quantized representation [pic], is given by

[pic]

where [pic] is the codeword of the [pic] codebook minimizing the reconstruction error on [pic], and:

[pic]

A Locally Optimal PVQ Design

The complexity of building a quantizer that scales to vectors of arbitrary dimension is known to be computationally prohibitive. Furthermore, the efficiency of a VQ decreases with its dimensionality: the fraction of the volume of a hypersphere inscribed in a hypercube of the same dimension d goes to zero when d goes to infinity ([2]-[3]). Partitioning the vectors in consecutive, non-overlapping subvectors is a common solution to this problem (see the book of Gersho and Gray [4]). While a partitioned VQ leads to a sub-optimal solution in terms of Mean Squared Error (MSE) because it does not exploit correlation among subvectors, the resulting design is practical and coding and decoding present a number of advantages in terms of speed, memory requirements and exploitable parallelism.

In a Partitioned VQ, we divide the input vectors into [pic] subvectors and quantize each of them with an [pic]-levels exhaustive search VQ. Having [pic] subvectors of the same dimension (except perhaps one, if [pic] does not divide [pic]) is not a possibility here, since we assume that the components of [pic] may be drawn from different alphabets. In this case their distributions may be significantly different and partitioning the [pic] components uniformly into [pic] blocks may not be optimal. We wish to determine the size of the [pic] sub vectors (of possibly different size) adaptively, while minimizing the quantization error, measured for example in terms of MSE. Once the [pic] codebooks are designed, input vectors are encoded by partitioning them into [pic] subvectors of appropriate length, each of which is quantized independently with the corresponding VQ. The index of the partitioned vector is given by the concatenation of the indices of the [pic] subvectors.

Given the number of partitions N and the number of levels per codebook L, it is possible to find the partition boundaries achieving minimum distortion with a brute-force approach. We first determine, for every [pic], the distortion [pic] that an [pic]-levels vector quantizer achieves on the input subvectors of boundaries [pic] and[pic]. Then, with a dynamic program, we traverse the matrix [pic] and find the [pic] costs corresponding to the input partition of boundaries [pic] and whose sum is minimal. A more sophisticated approach to partitioned vector quantization is discussed in Matsuyama [5]. It uses dynamic programming at each step to decide the current optimal partition, instead of designing one vector quantizer for each possible partition configuration first and then applying dynamic programming. Nevertheless, even this approach is computational intensive.

The locally optimal partitioning algorithm that we propose here (LPVQ) provides an efficient alternative to dynamic programming, while performing comparably in most applications. Our partitioning algorithm is based on a variation of the Generalized Lloyd Algorithm (or GLA, Linde, Buzo and Gray [6]).

Unconstrained vector quantization can be seen as the joint optimization of an encoder (the function [pic] described before) and a decoder (the determination of the codewords for the equivalence classes of the partition[pic]). GLA is an iterative algorithm that, starting from the source sample vectors chooses a set of codewords (also called centroids) and optimizes in turns encoder and decoder until improvements on the predefined distortion measure are negligible. In order to define our PVQ, the boundaries of the vector partition [pic] have to be determined as well. Our design follows the same spirit of the GLA. The key observation is that, once the partition boundaries are kept fixed, the Mean Square Error (the distortion we use in our application) is minimized independently for each partition by applying the well-known optimality conditions on the centroids and on the cells. Similarly, when the centroids and the cells are held fixed, the (locally optimal) partitions boundaries can be determined in a greedy fashion. The GLA step is independently applied to each partition. The equivalence classes are determined as usual, but as shown in Figure 2, the computation keeps a record of the contribution to the quantization error of the leftmost and rightmost components of each partition:

[pic]and [pic]

Except for the leftmost and rightmost partition, two extra components are also computed:

[pic]and [pic]

The reconstruction values used in the expressions for [pic] and [pic] are determined by the classification performed on the components[pic]. The boundary [pic] between the partitions [pic] and [pic] is changed according to the criteria

[pic]= min([pic],[pic],[pic])

if ([pic]=[pic])

[pic]

else if ([pic]=[pic])

[pic]

Entropy Coding

The partitioned vector quantizer is used here as a tool to reduce the dimensionality of the source vectors. Dependence between the other two dimensions has to be exploited by means of an entropy coder. Furthermore, when a lossless coding is required, quantization residuals have to be encoded as well, entropy coded with a conditioning on the subvector indices.

The index vectors [pic] and the codewords [pic], with [pic] and [pic], are sufficient to a lossy reconstruction of the data. When higher accuracy is needed, the compressed data can be augmented with the quantization error:

[pic]

where, for each [pic]:

[pic]

The unconstrained quantizers work independently from each other and independently on each source vector and an entropy encoder must be used to exploit this residual redundancy. In particular, each VQ index [pic] is encoded conditioning its probability with respect to a set of causal indices spatially and spectrally adjacent. The components of the residual vector [pic] are entropy coded with their probability conditioned on the VQ index [pic]. In near-lossless applications, a small, controlled error can be introduced at this stage. Figure 3 depicts a diagram of the LPVQ encoder.

Computational Complexity

Vector Quantization is known to be computationally asymmetrical, in the sense that encoding has a computational complexity which is orders of magnitude higher than decoding. Even more time consuming is the design of the dictionary which is also not guaranteed to converge into an easily predictable number of iterations. Numerous methods have been designed to speed up the convergence, for example, by constraining the search of the closest codeword like in [7], or by seeding the dictionary with vectors having special properties [8]. Adding structure to the VQ can also simplify encoding at the price of a limited degradation of the output quality [4]. All these improvements clearly apply to our method as well; furthermore, practical scenarios arise in which our algorithm can be applied as is without the computational complexity being an obstacle.

A possible way of mapping the LPVQ algorithm to the communication model described in Section II is to equip platform used for the remote acquisition with an encoder able to download a dictionary transmitted from the central server (see Figure 1). This dictionary can be, for the very first scene, bootstrapped as described in [8], with a number of vectors randomly selected from the image itself, with a dictionary designed for another image or with any dictionary that believed to be statistically significant. Due to the nature of our algorithm, the choice of the first dictionary will only impact the compression ratio of the very first transmission.

Once the central server receives a scene, let’s say at time instant t, a few iterations of LBG may be necessary to refine the dictionary, adjust the partition boundaries and improve compression. The refined version of the dictionary is transmitted back to the remote platform and used for the encoding of the scene acquired at time t+1. In Section VIII we report on experiments intended to assess the performance degradation derived from a mismatched dictionary.

It has been observed in [1] that if the codewords in each codebook are sorted according to their energy, the [pic] planes constituted by the indices retain important information on the structure of the original image. These planes alone can be used to browse and select areas of interest and, as we show in section XX, to extract important information on the nature of the original pixel vectors.

Experimental results

LPVQ has been tested on a set of five AVIRIS images ([9]). AVIRIS images are obtained by flying a spectrometer over the target area. They are 614 pixels wide and typically have a height on the order of 2,000 pixels, depending on the duration of the flight. Each pixel represents the light reflected by a 20m x 20m area (high altitude) or 4m x 4m area (low altitude). The spectral response of the reflected light is decomposed into 224 contiguous bands (or channels), approximately 10nm wide and spanning from visible to near infrared light (400nm to 2500nm). Each of these vectors provides a spectral signature of the area. Spectral components are acquired in floating point 12-bit precision and then scaled and packed into signed 16 bit integers. After acquisition, AVIRIS images are processed to correct for various physical effects (geometrical distortion due to the flight trajectory, time of day, etc.) and stored in scenes of 614 by 512 pixels each (when the image height is not a multiple of 512, the last scene will be smaller). All files for each of the 5 test images were downloaded from the NASA web site (JPL [9]) and the scenes belonging to the same flight merged together to form a complete image.

Several experiments have been performed for various numbers of partitions and for different codebook sizes. The results that we describe here were obtained for [pic] partitions and [pic] codebook levels. The choice of the number of levels makes also practical the use of off-the-shelf image compression tools that are fine-tuned for 8 bit data. The LPVQ algorithm trains on each image independently and the codebooks are sent to the decoder as side information. The size of the codebook is negligible with respect the size of the compressed data (256 x 224 x 2 bytes = 112 KB) and its cost is included in the reported results.

The partition boundaries for each of the five images are depicted in Figure 4. While similarities exist, the algorithm converges to different optimal boundaries on different input images. This is evidence that LPVQ adapts the partitions to input statistics. Starting with a codebook obtained by random image pixels, we have found that adaptation is fairly quick and boundaries converge to their definitive values in less than one hundred iterations.

If LPVQ is bootstrapped with the method described in [8], which populates the dictionary with the vector with highest norm and then adds the vector whose minimum distance from the current dictionary is maximum, the algorithms shows a much faster convergence. Furthermore, the constrained search for the closest codeword is generally faster by a factor of 2.

LPVQ performances are analyzed in terms of Compression Ratio (defined as the size of the original file divided by the size of the compressed one), Signal to Quantization Noise Ratio, Maximum Absolute Error and Percentage Maximum Absolute Error.

The Signal to Quantization Noise Ratio (SQNR) is defined here as:

[pic]

The correction factor [pic] is introduced to take into account the error introduced by the 12 bit analog-to-digital converter used by the AVIRIS spectrometer ([9]). This solution also avoids unbounded values in the case of a band perfectly reconstructed.

The Maximum Absolute Error (MAE) is defined in terms of the MAE for the [pic] band as[pic], where [pic] is:

[pic]

The average Percentage Maximum Absolute Error (PMAE) for the [pic] band having canonical alphabet [pic] is defined as:

[pic]

Table I shows that LPVQ achieves on the five images we have considered an average compression of 3.14:1, 45% better than the 1-D lossless compressor bzip2 when applied on the plane–interleaved images (worse results are achieved by bzip2 on the original pixel–interleaved image format) and 55% better than the standard lossless image compressor JPEG-LS. We also compared LPVQ with the method published in [11], even though it reports experiments on a subset of our data set. The algorithm in [11] uses LBG to cluster data. An optimized predictor is computed for each cluster and for each band. Prediction error is computed and entropy coded, along with side information regarding the optimized predictors. The resulting method outperforms LPVQ, while sharing time complexity similar to the design stage of LPVQ and lacking any extra feature provided by the latter, like lossy and near-lossless mode, fast browsing and classification, et cetera. The last column of Table I reports, as a reference, the compression and the SQNR when only the indices are encoded and the quantization error is fully discarded. As we can see from the table, on average we achieve 55:1 compression with 25.27dB of SQNR.

More interesting and practical are the results obtained with the near-lossless settings, shown in Table II. At first, the introduction of a small and constant quantization error across each dimension is considered; that is, before entropy coding, each residual value x is quantized by dividing x adjusted to the center of the range by the size of the range; i.e., q(x) = ((x+()/(2(+1)(. This is the classical approach to the near-lossless compression of image data and results into a constant MAE across all bands. With this setting, it is possible to reach an average compression ratio ranging from 4:1 with the introduction of an error [pic] and a [pic] to 10:1 with and error of [pic] and [pic]. While the performance in this setting seem to be acceptable for most applications and the SQNR is relatively high even at high compression, the analysis of the contribution to the PMAE of the individual bands shows artifacts that might be unacceptable. In particular, while the average PMAE measured across the 224 bands of the AVIRIS cube is low, the percentage error peaks well over 50% on several bands (see Figure 5). Since the PMAE is relevant in predicting the performance of many classification schemes, we have investigated two different approaches aimed at overcoming this problem. In both approaches we select a quantization parameter that is different for each band and it is inversely proportional to the alphabet size (or dynamic). In general, high frequencies, having in AVIRIS images higher dynamic, will be quantized more coarsely than low frequencies. We want this process to be governed by a global integer parameter [pic].

The first method, aiming at a quasi–constant PMAE across all bands, introduces on the [pic]band a distortion [pic] such that:

[pic]

Since the [pic] band has alphabet [pic] we must have:

[pic]

The alternative approach, aims at a quasi–constant SQNR across the bands. If we allow a maximum absolute error [pic] on the [pic] band, it is reasonable to assume that the average absolute error on that band will be[pic]. If we indicate with [pic] the average energy of that band and with [pic] the target average maximum absolute error, then the absolute quantization error allowed on each band is obtained by rounding to the nearest integer the solution of this system of equations:

[pic]

As can be seen from Table II, the three methods for near-lossless coding of AVIRIS data are equivalent in terms of average SQNR at the same compression. However, the quasi-constant PMAE method is indeed able to stabilize the PMAE across each band (Figure 6). The small variations are due to the lossless compression of some bands and the rounding used in the equations. The average SQNR is not compromised as well. Similar results are observed for the quasi-constant SQNR approach. The SQNR is almost flat (Figure 7), except for those bands that are losslessly encoded and those with small dynamic. The PMAE is also more stable than the constant MAE method (Figure 8).

LPVQ and Random Dictionaries

In order to evaluate the proposed approach in the framework described in Section II, we performed the following experiments for each scene of the Moffett Field image:

1) we compute compression ratio and RMSE at each step of the LPVQ algorithm, starting with a random dictionary;

2) same except that the starting dictionary is the locally optimal one for the previous scene.

As we can see from Figure 9, compression performance is quite stable already after just 50 iterations. The compression ratio is slightly lower when LPVQ is fed with the dictionary from the previous scene, while RMSE, on the other hand, is much lower. This suggests that the entropy coder needs to be tuned-up for this case and that the lossy compression is slightly better when only few iterations are allowed.

A different experimental setting uses six different schemes to generate random dictionaries. One hundred dictionaries for each scheme are used with PVQ (i.e., the dictionary is not refined with the proposed LBG-like scheme to obtain a locally optimal one) and with both uniform and optimal partitions. Compression results for each scheme are box-plotted in Figure 10. The results suggest that taking a small sample of the input data is enough to obtain compression performances reasonably close to the locally optimal solution produced by LPVQ, and that the non-uniform partitioning is much more effective at high compression.

The Problem of Classification

Let each image pixel be a [pic]-dimensional vectors [pic] divided into [pic] disjoint subvectors as [pic], the [pic]-th partition having dimension [pic], for [pic]. For simplicity the boundaries are omitted here.

Upon quantization each vector is represented by an [pic]-dimensional vector of indices [pic] and by [pic], a [pic]-dimensional vector representing the quantization error. Each component [pic] indexes one of the [pic] codebook centroids for the VQ corresponding to the partition [pic], [pic]. If [pic] is the quantized value for [pic], LPVQ decomposes each component of an input vector [pic] into as [pic], where [pic].

Given a target vector [pic], a distortion measure [pic] and a classification threshold [pic], we wish to determine, for every image pixel [pic], whether [pic]. When this condition is satisfied, we say that the pixel [pic] is a member of the class [pic].

The Euclidean Distance [pic] is distortion measures commonly used in classification.

The classification threshold [pic], plays an important role since it determines whether the classification is used to detect a rare pixel instance, eventually present in the image (problem commonly referred to as target detection) or whether the objective of the classification is the determination of a thematic map, where almost every pixel belongs to one of several classes.

Effect of Coding Error on the Classification

As we did in the case of the compression we used AVIRIS hyperspectral images to assess the effect of the coding error on classification. Classification and target detection are algorithms frequently applied to hyperspectral images; when the images are lossily encoded, it is licit to ask whether and in which measure the coding error affects the results of these algorithms.

In order to assess the classification errors introduced by LPVQ lossy modes, we have experimented with the standard images for various errors and threshold parameters. It is important to notice that, while the lossy results are peculiar of our algorithm, the near lossless apply to any compression scheme that bounds the maximum absolute error on each vector component. The results for three images, Cuprite, Moffet Field and Low Altitude, are presented here. Results on the other two images were very similar.

In our experiments, the absolute error introduced by LPVQ in near lossless mode is respectively bounded to a maximum of 1, 2, 4 and 8 units. The classification uses Euclidean Distance with an average threshold per band [pic]; typically, values in the range [pic] are of some interest in practical applications. The figures show the percentage of errors in the classification of 8 targets selected from each image. The targets are hand picked from the reduced resolution image constituted by the index planes and are meant to represent targets of common interest (buildings, roads, water, vegetation, etc...). The lossless encoding is used as a reference for the classification and the error percentages reflect the sum of all false positive (classifications that were not classified in the lossless), false negative (vectors classified in the lossless and not classified in the lossy) and misclassifications (different clusters in lossless and lossy).

As it is possible to see from Figures 11-13, in near lossless, the classification is fundamentally unaffected; even for an error of [pic], the percentage of classification errors is, in the worst case, below 0.1%. This is sufficient for most applications. Smaller coding errors, achieve even lower percentages. For the compression parameters used in Section VII (i.e., 256 code vectors and 16 partitions) the indices and the code vectors alone (Figure 14, lossy case) achieve a classification error always lower than 3%. While this error rate may be unsuitable for some applications, as we show in the next section, it is possible to take advantage of this characteristic to design a faster classifier.

Speeding up the Classification

Since the LPVQ indices provide most of the information necessary to classify the pixels, we designed a simple algorithm that, bounding the minimum and maximum quantization error for each component and for each cluster, can decide the classification of most pixels without inspecting their error vector [pic]. Bounds on the quantization error are available at design time or can be inferred from the encoded image. The advantages of this algorithm are twofold. Firstly, the number of partitions and the number of centroids are typically small, so pre-computed values can be arranged into a lookup table. If most vectors can be classified without the need of the error, this will result into a substantial speed up. Secondly, we can imagine a user on the field, browsing and trying different classifications on the LPVQ indices instead of the whole image. Then, when a parameterization of interest is found, the user can query the server for the error vectors necessary to resolve any classification ambiguity.

Given a threshold [pic], a target vector [pic] and a distortion measure [pic], we wish to determine, from the quantization indices of a pixel [pic], two quantities [pic] and [pic], respectively lower and upper bounding the distortion [pic].

Since [pic] belongs to the class [pic] only if [pic], we can observe that:

• If [pic], the pixel [pic] clearly does not belong to the class [pic];

• If [pic], the pixel [pic] trivially belongs to the class [pic];

• If [pic] then the quantization indices and the bounds on the error are not sufficient to decide the classification. In this case, and only in this case, it is necessary to access the error vector and compute [pic].

Figure 15 shows the pseudocode that implements this scheme. The main assumption is that the quantities [pic] and [pic] can be computed by summing the individual contributions of each vector component [pic], upper and lower bounded by the minimum and maximum of the quantization residuals [pic] and [pic].

This is clearly the case of Euclidean Distance, here defined as:

[pic]

Changing the threshold [pic] into [pic], we can focus on the contribution of [pic] and [pic] to the individual terms of the sum. For a given component [pic], [pic], in the partition [pic], [pic] we have:

[pic].

If [pic] has been quantized with the centroid [pic],[pic]:

[pic]

and

[pic].

Summing these bounds over all components of the partition [pic] we obtain [pic] and [pic]. These quantities are precomputed in the algorithm in Figure 15 by the two nested “for” loops. Since there are only [pic] possible values and [pic] and [pic] are typically small ([pic] and [pic] in Section VII), [pic] and [pic] can be stored in a lookup table indexed by [pic] and [pic]. The computation of [pic] and [pic] requires a total of [pic] lookups and [pic] sums. If one of the two comparisons [pic] and [pic] succeeds, then the pixel [pic] is classified from its indices only, with a number of operations proportional to [pic].

Otherwise, the error vector [pic] must be retrieved, [pic] exactly reconstructed as [pic] and finally [pic] computed. This requires a sum a subtraction and a product for each component and [pic] sums to accumulate the result, i.e. a total of [pic] subtractions, [pic] sums and [pic] products, a number of operations proportional to [pic] (for AVIRIS images, [pic]).

The speed of the new classification algorithm depends on the probability that the two tests fail and that we have to use the error vector in order to classify. Let this probability be:

[pic]

If [pic], [pic] and [pic] are respectively the times to perform a subtraction, a sum and a multiplication on a given computing platform, the total running time of the new classification is:

[pic]

Figures 16-18 show an experimental assessment of the quantity [pic] for three AVIRIS images. They have been classified using 100 randomly selected targets. Average results are reported for thresholds [pic] and quantizers having 256, 512 and 1024 levels. It is possible to see how the percentage of vectors on which the simplified test fails to classify the points reaches a maximum between 7.5% and 11% for a 1024 levels quantizer and 12% to 18% for a 256 level quantizer. Practical figures are typically better. Problems like target detection are solved by applying a low threshold, while classification requires a high one; in these regions of the curve, the percentages may be much lower than the maxima. These results can be used in two ways. Given an image encoded with LPVQ, we can improve the speed the naïve classification with the use of a lookup table. Alternatively, we can use this as a tool to select the number of quantization levels and match a desired average classification speed

Conclusions

We have presented an extension of the GLA algorithm to the locally optimal design of a partitioned vector quantizer (LPVQ) for the encoding of source vectors drawn from a high dimensional source on[pic]. It breaks down the input space into independent subspaces and for each subspace designs a minimal distortion vector quantizer. The partition is adaptively determined while building the quantizers in order to minimize the total distortion. Experimental results on lossless and near-lossless compression of hyperspectral imagery have been presented, and different paradigms of near-lossless compression are compared. Aside from competitive compression and progressive decoding, LPVQ has a natural parallel implementation and it can also be used to implement search, analysis and classification in the compressed data stream. High speed implementation of our approach is made possible by the use of small independent VQ codebooks (of size 256 for the experiments reported), which are included as part of the compressed image (the total size of all codebooks is negligible as compared to the size of the compressed image and our experiments include this cost). Decoding is no more than fast table look-up on these small independent tables. Although encoding requires an initial codebook training, this training may only be necessary periodically (e.g., for successive images of the same location), and not in real time. The encoding itself involves independent searches of these codebooks (which could be done in parallel and with specialized hardware).

References

1] G. MOTTA, F. RIZZO, AND J.A. STORER, “COMPRESSION OF HYPERSPECTRAL IMAGERY,” IN PROCEEDINGS DATA COMPRESSION CONFERENCE, J.A. STORER AND M. COHN, EDS. 2003, PP. 333-342, IEEE COMPUTER SOCIETY PRESS.

2] D. Landgrebe, “Hyperspectral Image Data Analysis,” in IEEE Signal Processing Magazine, January 2002, pp. 17–28

3] M. G. Kendall, A course in the Geometry of n-Dimensions. New York: Hafner, 1961.

4] A. Gersho and R.M. Gray, Vector Quantization and Signal Compression. Kluwer Academic Press, 1991.

5] Y. Matsuyama. “Image Compression Via Vector Quantization with Variable Dimension”, TENCON 87: IEEE Region 10 Conference Computers and Communications Technology Toward 2000, Aug. 1987, Seoul, South Korea.

6] Y. Linde, A. Buzo, and R. Gray, “An algorithm for vector quantizer design”, IEEE Transactions on Communications 28, 84-95, 1980.

7] Huang, Bi, Stiles, and Harris, in IEEE Transactions on Image Processing, July 1992.

8] I. Katsavounidis, C.-C.J. Kuo, and Z. Zhang, “A New Initialization Technique for Generalized Lloyd Iteration,” in IEEE Signal Processing Letters, vol. 1, no. 10, pp. 144-146, October 1994

9] JPL [2002]. NASA Web site:

10] B. Aiazzi, L. Alparone and S. Baronti, “Near–Lossless Compression of 3–D Optical Data”, IEEE Transactions on Geoscience and Remote Sensing, vol. 39, no. 11, 2001.

11] J. Mielikainen and P. Toivanen, “Clustered DPCM for the Lossless Compression of Hyperspectral Images”, in IEEE Transactions on Geoscience and Remote Sensing, vol. 41, no. 12, pp. 2943-2946, December 2003.

12] F. Rizzo, B. Carpentieri, G. Motta, and J. A. Storer, “High Performance Compression of Hyperspectral Imagery with Reduced Search Complexity in the Compressed Domain”, in Proceedings Data Compression Conference, J.A. Storer and M. Cohn, Eds. 2004, IEEE Computer Society Press.

.

1] G. P. Abousleman [1995]. “Compression of Hyperspectral Imagery Using Hybrid DPCM/DCT and Entropy-Constrained Trellis Coded Quantization”, Proc. Data Compression Conference, IEEE Computer Society Press.

2] B. Aiazzi, L. Alparone, A. Barducci, S. Baronti and I. Pippi [2001]. “Information-Theoretic Assessment of Sampled Hyperspectral Imagers”, IEEE Transactions on Geoscience and Remote Sensing 39:7.

3] .

4] .

5] JPL [2002]. NASA Web site:

6] Y. Linde, A. Buzo, and R. Gray [1980]. “An algorithm for vector quantizer design”, IEEE Transactions on Communications 28, 84-95.

7] M. Manohar and J. C. Tilton [2000]. “Browse Level Compression of AVIRIS Data Using Vector Quantization on Massively Parallel Machine,” Proceedings AVIRIS Airborne Geoscience Workshop.

8] Y. Matsuyama [1987]. “Image Compression Via Vector Quantization with Variable Dimension”, TENCON 87: IEEE Region 10 Conference Computers and Communications Technology Toward 2000, Aug. 25-28, Seoul, South Korea.

9] R. E. Roger, J. F. Arnold, M. C. Cavenor and J. A. Richards, [1991]. “Lossless Compression of AVIRIS Data: Comparison of Methods and Instrument Constraints”, Proceedings AVIRIS Airborne Geoscience Workshop.

10] S. R. Tate [1997], “Band ordering in lossless compression of multispectral images”, IEEE Transactions on Computers, April, 477-483.

11] G. Shaw and D. Manolakis [2002], “Signal Processing for Hyperspectral Image Exploitation”, IEEE Signal Processing Magazine 19:1

12] S. Subramanian, N. Gat, A. Ratcliff and M. Eismann [1992]. “Real-Time Hyperspectral Data Compression Using Principal Component Transform”, Proceedings AVIRIS Airborne Geoscience Workshop.

13] G. O. Young, “Synthetic structure of industrial plastics (Book style with paper title and editor),” in Plastics, 2nd ed. vol. 3, J. Peters, Ed. New York: McGraw-Hill, 1964, pp. 15–64.

[1]

[2] NASA, “AVIRIS home page,” , February 2003

[3].

[4].

[5] M. Manohar and J.C. Tilton, “Browse level compression of AVIRIS data using vector quantization on massively parallel machine,” in Proceedings AVIRIS Airborne Geosciences Workshop, 2000.

SPURGARE LE REFERENCES ED AGGIUNGERE

................
................

Online Preview   Download