Compression of 3D Scientific Data for Archival ...



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

(

Giovanni Motta, Francesco Rizzo, James A. Storer, and Bruno Carpentieri

Abstract—We propose a compression algorithm based on Partitioned Vector Quantization targeted to 3D scientific data, remote sensing and hyperspectral imagery. Along one of its dimensions, the input data is treated as a single vector that is partitioned into subvectors of (possibly) different lengths, each quantized separately. Quantization indices and residual errors are 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, improves 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, on such data, state of the art lossless compression, it provides near-lossless and lossy capabilities (that could be used for fast browsing and broadcasting on limited bandwidth communication channels), it is scalable to arbitrary data size, and it allows fast classification and target detection in the compressed domain.

Index Terms — Image coding, Image processing, Pattern classification, Hyperspectral imaging.

INTRODUCTION

A

n increasing number of scientific instruments produce high volume of data in the form of two-dimensional matrices of high dimensionality vectors, also called data cubes. Typical examples are biomedical images, multi, hyper and ultra spectral imagery, measurements of volumetric parameters like atmospheric temperature and pressure via microwaves sounders. Compressing these data presents a challenge for the currently standardized general purpose 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 supporting lossless, near lossless, and lossy compression 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 acquisition and transmission process and due to the fact that original data may be needed for unforeseen analyses or 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.

Traditional approaches to the compression of hyperspectral imagery are based on differential prediction via DPCM ([1]-[3]), vector quantization ([4]-[7]), or dimensionality reduction through principal component analysis ([8]-[9]). An inter-band linear prediction approach based on least square optimization is presented in [10]; this compression method optimizes, for each sample, the parameters of a linear predictor with spatial and spectral support. A more complex least square optimized scheme combined with a vector quantizer has been recently presented in [11].

In [12] 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 of 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 the compressed domain, with considerable speed up 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. The proposed algorithms have been verified experimentally on the lossless and near lossless compression of NASA AVIRIS images where, under conservative assumptions, is able to improve the naïve classification of a factor of five or more.

Section II discusses the communication paradigm under consideration. Section III introduces the necessary notation and briefly reviews the proposed algorithm. Section IV discusses compression experiments with LPVQ.

The problem of classification and the necessary notation is introduced in Section V. In this same section experimental results on the classification error introduced by LPVQ lossy and near lossless compression modes are discussed first. Building on these experimental observations, we describe 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 are performed on typical AVIRIS images 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 are 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 events evolving in a specific geographic area, such as hurricanes, storms, flooding and volcanic eruptions. The collected data have to be transmitted to a land based central station that analyzes the data, applies some form of enhancement, further compresses the data 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 has to 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]

1 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 ([13]-[14]). Partitioning the vectors in consecutive, non-overlapping subvectors is a common solution to this problem (see the book of Gersho and Gray [15]). 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 generally not a possibility since, in this context, 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: 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 programming approach, 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 by Matsuyama in [16]. 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 in this paper (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, see Linde, Buzo and Gray [17]).

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]

Data Compression with LPVQ

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 lossless coding is required, quantization residuals have to be 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 by 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.

1 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 [18], or by seeding the dictionary with vectors having special properties [19]. Adding structure to the VQ can also simplify encoding at the price of a limited degradation of the output quality [15]. 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 the platform used for the remote acquisition with an encoder that is 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 [19], with a number of vectors randomly selected from the image itself, with a dictionary designed for another image, or with any dictionary that is 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, at time instant t, a few iterations of LBG may be necessary to refine the dictionary, to adjust the partition boundaries and to improve compression. The refined version of the dictionary is transmitted back to the remote platform and is used for the encoding of the scene acquired at time t+1. Later in this section 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 VI, to extract important information on the nature of the original pixel vectors.

2 Experimental results

LPVQ has been tested on a set of five AVIRIS images ([20]). 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 20 x 20 meters area (high altitude) or 4 x 4 meters area (low altitude). The spectral response of the reflected light is decomposed into 224 contiguous bands (or channels), approximately 10nm wide, 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 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 can be downloaded from the NASA web site (JPL [20]) and the scenes belonging to the same flight are 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 [19], 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 ([20]). 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 this five images an average compression of 3.14:1. This is 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., [pic]. 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 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).

3 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 the 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 already quite stable after 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.

We also experimented with different schemes that instead of using LPVQ design stage, generate and use random dictionaries to quantize data. The results suggest that taking a careful sample of the input data is enough to obtain compression performances reasonably close (10% lower at most) to the locally optimal solution produced by the full fledged LPVQ design, and that the non-uniform partitioning is much more effective at high compression.

Fast Classification with LPVQ

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 the 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.

1 Effect of Coding Error on the Classification

As we did in the case of 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 10-12, 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 13, 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.

2 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. First: 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. Second: 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 14 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 14 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 15-17 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).

Finally, we have shown how classification, directly applied to the lossy compressed bit stream generated by LPVQ, can achieve accuracy higher than 97 percent. When absolute accuracy is necessary, we can generalize this method into a fast classification algorithm that works with only partial decompression of the data. Careful exploitation of the structure of the LPVQ compressed bit stream, leads to the exact classification of 90 percent of the spectral signatures by using table lookup on the lossy information only. Remaining pixels require partial decompression of the data in order to recover the residual information and resolve classification ambiguity.

Besides the big memory savings determined by operating on compressed or partially decompressed data, the fast classification speeds up the naïve approach by at least a factor of five. This figure is obtained by assuming that multiplication and addition have the same cost, which represents for us the worst case. In scenarios arising in practice, the speed up is likely to be substantially higher since the probability [pic] will be almost always below its maximum which corresponds to an operating point having scarce practical interest.

References

1] G. P. ABOUSLEMAN, "COMPRESSION OF HYPERSPECTRAL IMAGERY USING HYBRID DPCM/DCT AND ENTROPY CONSTRAINED TRELLIS CODED QUANTIZATION," PROCEEDINGS DATA COMPRESSION CONFERENCE, IEEE COMPUTER SOCIETY PRESS, 322-331, 1995.

2] B. Aiazzi, L. Alparone, and S. Baronti. "Near-lossless Compression of 3-D Optical Data," IEEE Transactions on Geoscience and Remote Sensing 39:11 (November), 2547-2557, 2001

3] G. P. Abousleman, T. T. Lam, and L. J. Karam. "Robust Hyperspectral Image Coding with Channel-Optimized Trellis-Coded Quantization," IEEE Transaction on Geosciences and Remote Sensing 40:4 (April), 820-830, 2002.

4] M. J. Ryan and J. F. Arnold. "The Lossless Compression of AVIRIS Images By Vector Quantization," IEEE Transactions on Geosciences and Remote Sensing 35:3 (May), 546-550, 1997.

5] M. Manohar and J. C. Tilton. "Browse Level Compression of AVIRIS Data Using Vector Quantization on a Massively Parallel Machine," Proc. AVIRIS Airborne Geosciences Workshop, 2000.

6] M. Pickering and M. Ryan. "Efficient Spatial-Spectral Compression of Hyperspectral Data," IEEE Transaction on Geosciences, and Remote Sensing 39:7, 1536-1539, 2001.

7] J. Mielikäinen and P. Toivanen. "Improved Vector Quantization for Lossless Compression of AVIRIS Images," Proceedings of the XI European Signal Processing Converence, EUSIPCO-2002, EURASIP (September), Toulouse, France.

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

9] M. H. Sharp [2002]. "Noise-Constrained Hyperspectral Data Compression", SPIE Optical Engineering 41:9, 1-10.

10] J. Mielikäinen, A. Kaarna, and P. Toivanen. "Lossless Hyperspectral Image Compression via Linear Prediction," Proceedings SPIE 4725:8, 600-608, 2002.

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] 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.

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

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

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

16] 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.

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

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

19] 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

20] JPL [2002]. NASA Web site:

21] 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.

[pic]

Figure 1: Communication model.

[pic]

Figure 2: Error contributions for two adjacent partitions.

[pic]

Figure 3: LPVQ lossless encoder.

[pic]

Figure 4: Partition sizes and alignment.

|[pic] |[pic] |

|Figure 5: PMAE for near-lossless coding with constant Maximum |Figure 6: PMAE for near-lossless coding with quasi-constant PMAE. |

|Absolute Error. | |

|[pic] |[pic] |

|Figure 7: SQNR for near-lossless coding with quasi-constant SQNR.|Figure 8: PMAE for near-lossless coding with quasi-constant SQNR. |

|[pic] |[pic] |

|[pic] |[pic] |

|Figure 9: Moffett Field RMS/C.R. vs LPVQ iterations. RMSE(p) and C.R.(p) values indicates that the starting dictionary was the one of the |

|previous scene, rather than random vectors. |

|[pic] |[pic] |

|Figure 10: Cuprite, classification errors in near-lossless |Figure 11: LowAltitude, classification errors in near-lossless |

|compressed images. |compressed images. |

|[pic] |[pic] |

|Figure 12: MoffetField, classification errors in near-lossless |Figure 13: Classification error in LPVQ lossy compressed images. |

|compressed images. | |

| |

|Input: |

|[pic]; // Target vector |

|[pic]; // Quantized image |

|[pic] and [pic] // Min/Max error for |

|// component k and |

|// centroid l |

|Output: |

|[pic] // Classification |

| |

|For each centroid [pic] with [pic] // Precomputation |

|For each partition [pic] with [pic] |

|Compute [pic] from [pic] |

|Compute [pic] from [pic] |

| |

|For each pixel [pic] |

|[pic] |

|[pic] |

|If [pic] |

|[pic] = 0; // Not in the class [pic] |

|Else if [pic] |

|[pic] = 1; // In the class [pic] |

|Else |

|[pic] = [pic]; // Use the error |

Figure 14: Fast classification algorithm.

[pic]

Figure 15: Image Cuprite. Percentage of vectors that are not classified by the simplified test. Results averaged for 100 random targets. Quantizers have 256, 512 and 1024 levels.

[pic]

Figure 16: Image Low Altitude. Percentage of vectors that are not classified by the simplified test. Results averaged for 100 random targets. Quantizers have 256, 512 and 1024 levels.

[pic]

Figure 17: Image Moffet Field. Percentage of vectors that are not classified by the simplified test. Results averaged for 100 random targets. Quantizers have 256, 512 and 1024 levels.

|AVIRIS |Lossless |Indices Only |

| |gzip |bzip2 |JPEG-LS |

[pic] |CR |RMSE |SQNR |MAE |PMAE |CR |RMSE |SQNR |MAE |PMAE |CR |RMSE |SQNR |MAE |PMAE | |1 |4.64 |0.82 |42.06 |1,00 |0.45 |3.92 |0.81 |46.82 |0,65 |0.01 |3.91 |0.79 |46.90 |0,63 |0.01 | |2 |5.62 |1.41 |37.65 |2,00 |0.89 |4.44 |1.64 |43.15 |1,61 |0.03 |4.43 |1.60 |43.18 |1,58 |0.03 | |3 |6.54 |1.98 |34.82 |3,00 |1.34 |4.99 |2.44 |40.43 |2,58 |0.06 |5.05 |2.40 |40.16 |2,58 |0.06 | |4 |7.48 |2.52 |32.81 |4,00 |1.79 |5.51 |3.25 |38.35 |3,57 |0.09 |5.58 |3.19 |38.12 |3,54 |0.09 | |5 |8.48 |3.01 |31.33 |5,00 |2.23 |6.00 |4.04 |36.71 |4,54 |0.12 |6.12 |3.99 |36.35 |4,55 |0.12 | |6 |9.53 |3.46 |30.21 |6,00 |2.68 |6.50 |4.86 |35.27 |5,54 |0.15 |6.56 |4.78 |35.09 |5,52 |0.15 | |7 |10.57 |3.87 |29.35 |7,00 |3.12 |6.92 |5.68 |34.18 |6,54 |0.18 |7.04 |5.61 |33.91 |6,56 |0.18 | |8 |11.57 |4.25 |28.66 |8,00 |3.54 |7.39 |6.49 |33.15 |7,56 |0.21 |7.49 |6.37 |33.01 |7,50 |0.21 | |9 |12.54 |4.62 |28.10 |8,98 |3.86 |7.86 |7.22 |32.34 |8,53 |0.24 |8.06 |7.10 |32.03 |8,53 |0.25 | |10 |13.47 |4.97 |27.63 |9,95 |4.13 |8.43 |7.91 |31.50 |9,57 |0.27 |8.58 |7.77 |31.32 |9,55 |0.28 | |11 |14.35 |5.31 |27.22 |10,92 |4.39 |8.92 |8.49 |30.94 |10,54 |0.30 |9.12 |8.37 |30.73 |10,54 |0.31 | |12 |15.19 |5.64 |26.88 |11,89 |4.65 |9.48 |9.03 |30.39 |11,54 |0.33 |9.64 |8.89 |30.26 |11,51 |0.34 | |13 |16.00 |5.96 |26.57 |12,87 |4.93 |10.04 |9.50 |29.92 |12,55 |0.36 |10.23 |9.35 |29.77 |12,54 |0.38 | |14 |16.80 |6.27 |26.30 |13,84 |5.19 |10.50 |9.90 |29.58 |13,52 |0.39 |10.79 |9.75 |29.37 |13,52 |0.41 | |15 |17.58 |6.58 |26.06 |14,78 |5.38 |11.04 |10.26 |29.25 |14,54 |0.42 |11.38 |10.10 |29.01 |14,54 |0.44 | |16 |18.34 |6.88 |25.85 |15,71 |5.56 |11.63 |10.56 |28.87 |15,54 |0.46 |11.81 |10.40 |28.78 |15,50 |0.47 | |17 |19.10 |7.17 |25.65 |16,63 |5.72 |12.20 |10.81 |28.55 |16,54 |0.49 |12.45 |10.66 |28.44 |16,50 |0.51 | |18 |19.85 |7.45 |25.47 |17,52 |5.85 |12.66 |11.04 |28.34 |17,52 |0.52 |12.99 |10.89 |28.16 |17,53 |0.55 | |19 |20.60 |7.72 |25.31 |18,40 |5.96 |13.13 |11.25 |28.12 |18,54 |0.55 |13.50 |11.10 |27.94 |18,54 |0.58 | |20 |21.33 |7.99 |25.17 |19,27 |6.04 |13.59 |11.42 |27.91 |19,54 |0.59 |13.93 |11.28 |27.78 |19,54 |0.61 | |

Table II: Average Compression Ratio (CR), Root Mean Squared Error (RMSE), Signal to Quantization Noise Ratio (SQNR), average Maximum Absolute Error (MAE) and Percentage Maximum Absolute Error (PMAE) achieved by the near-lossless LPVQ on the test set for different [pic].

Giovanni Motta is with the Computer Science Dept., Brandeis University, Waltham, MA 02454-9110 USA (e-mail: gim@).

Francesco Rizzo is with the Dipartimento di Informatica ed Applicazioni, Università di Salerno, Baronissi, ITALY (e-mail: frariz@)

James A. Storer is with the Computer Science Dept., Brandeis University, Waltham, MA 02454-9110 USA (e-mail: storer@cs.brandeis.edu)

Bruno Carpentieri is with the Dipartimento di Informatica ed Applicazioni, Università di Salerno, Baronissi, ITALY (e-mail: bc@dia.unisa.it)

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

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download