PARA'04 State-of-the-Art
in Scientific Computing
June 20-23, 2004 (Home page)
Updated: 18 February 2004

COMPRESSING 3D MEASUREMENT DATA UNDER INTERVAL UNCERTAINTY

Olga Kosheleva, Sergio Cabrera, and Brian Usevitch
Electrical & Comp. Eng.
U. of Texas, El Paso
TX 79968, USA
email: olgak@utep.edu

FORMULATION OF THE PROBLEM. At present, so much data is coming from measuring instruments that it is necessary to compress this data before storing and processing. We can gain some storage space by using lossless compression, but often, this gain is not sufficient, so we must use lossy compression as well.

In the last decades, there has been a great progress in image and data compression. In particular, the JPEG2000 standard uses the wavelet transform methods together with other efficient compression techniques to provide a very efficient compression of 2D images.

In principle, it is possible to use these compression techniques to compress 2D measurement data as well. It is also possible to compress 3D measurement data $f(x,y,z)$ - e.g., meteorological measurements taken in different places $(x,y)$ at different heights z. One possibility is simply to apply the 2D JPEG compression to each horizontal layer $f(x,y,z_0)$. Another possibility, in accordance with Part 2 of JPEG2000 standard, is to first apply the KLT transform to each vertical line.

The problem with this approach is that for compressing measurement _data_, we use _image_ compression techniques. The main objective of image compression is to retain the quality of the image. From the viewpoint of visual image quality, the image distortion can be reasonably well described by the mean square difference MSE (a.k.a. L$^2$-norm) between the original image $I(x,y)$ and the compressed-decompressed image $I'(x,y)$. As a result, sometimes, under the L$^2$-optimal compression, an image may be vastly distorted at some points $(x,y)$ - and this is OK as long as the overall mean square error is small.

When we compress measurement results, however, our objective is to be able to reproduce each individual measurement result with a certain guaranteed accuracy. In such a case, reconstruction that only guaranteed mean square error over the data set is unacceptable: for example, if we use the meteorological data to plan a best trajectory for a plane, what we really want to know are the meteorological parameters such as wind, temperature, and pressure along the trajectory. If along this line, the values are not reconstructed accurately enough, the plane may crash - and the fact that on average, we get a good reconstruction, does not help. What we need is a compression that guarantees the given accuracy for all pixels, i.e., that guarantees that for each $(x,y)$, the difference $\Vert f(x,y,z)-f'(x,y,z)\Vert$ is bounded by a given value D - i.e., that the actual (somewhat modified) value $f(x,y,z)$ belongs to the interval $[f'(x,y,z)-D,f'(x,y,z)+D]$ of given width 2D.

WHAT WE HAVE DONE. We have developed a new algorithm that uses JPEG2000 to compress 3D measurement data with guaranteed accuracy. We are following the general idea of Part 2 of JPEG2000 standard; our main contribution is designing an algorithm that selects bitrates leading to a minimization of the sup norm max $\Vert f(x,y,z)-f'(x,y,z)\Vert$ as opposed to the usual L$^2$-norm.

Specifically, it is difficult to compute the exact value of the sup-norm, we only get an upper bound (enclosure). In order to decrease the sup-norm, it is therefore reasonable to minimize this upper bound. In this talk, we describe a new algorithm for minimizing this upper bound, and we show that this algorithm indeed leads to a reasonable decrease in the sup-norm - and thus, to a better quality data compression under interval uncertainty.

Home page