Fast and compact volume rendering in the compressed transform domain
Potentially, data compression techniques may have a broad impact in computing not only by decreasing storage and communication costs, but also by speeding up computation. For many image processing applications, the use of data compression is so pervasive that we can assume the inputs and outputs are in a compressed domain, and it is intriguing to consider doing computations on the data entirely in the compressed domain. In this paper, we speed up processing by doing computations, including dot product and convolution on vectors and arrays, in a compressed transform domain. To do this, we make use of sophisticated algebraic techniques for evaluation and interpolation of sparse polynomials. We illustrate the basic methodology by applying these techniques to image processing problems, and in particular to speed up the well known splatting algorithm for volume rendering. The splatting algorithm is one of the most efficient of existing high quality volume rendering algorithms; it takes as input three dimensional volume sample data of size N3 and outputs an N × N image in O(N3f) time, where f is a parameter known as footprint size (which often is hundreds of pixels in practice). Assuming that the original sample data and the resulting image are stored in the transform domain and can be lossily compressed by a factor ρ with small error, we show that the rendering of the image can be done entirely in the compressed transform domain in decreased time O(ρN3 log N). Hence we obtain a significant speedup over the splatting algorithm when f ≫ ρ log N. The same methodology of computing in compressed transform domain can be applied to speed up other algorithms for image processing problems.
