Low-complexity Interpolation Coding for Server-Based Computing

Fei Li, Jason Nieh

Proceedings of the Data Compression Conference (DCC) 2002, Snowbird, UT, April 2-4, 2002, p. 461


In recent years, the growing total cost of ownership has resulted in a shift away from the distributed model of desktop computing toward a more centralized server-based computing (SBC) model. In SBC, all application logic is executed on the server while clients simply process the resulting screen updates sent from the server. To provide good performance, SBC systems employ various techniques to encode the screen updates to minimize the bandwidth and processing requirements of sending the screen updates. However, existing SBC encoding techniques are not able to effectively support multimedia applications. To address this problem, we have developed a family of linear interpolation algorithms for encoding SBC screen updates. We first present an overview of an optimal linear interpolation (OLI) algorithm. Given a rectangular region of pixels to be encoded, OLI represents the region as a one-dimensional function, mapping from the cardinal number of each pixel to the color value of the pixel. OLI converts this function into a piecewise linear representation consisting of points. OLI can provide a precise lossless piecewise linear representation. Alternatively, when network bandwidth is limited, OLI can adapt to the available bandwidth by limiting the value of and recursively iterating through all combinations of pixels in search of an optimal set of points to provide an approximate but lossy representation. The points are sent to the client, which then interpolates through those pixel values to recover the original rectangular region of pixels. While the decoding time on the client is negligible, the encoding time on the server has exponential computational complexity, which limits its utility for SBC. To reduce encoding complexity, we developed two linear interpolation algorithms with linear encoding and decoding computational complexity. The algorithms near optimal linear interpolation (NOLI) and 2-D lossless linear interpolation (2DLI). NOLI is a greedy algorithm that heuristically minimizes the number of pivot points of the piecewise function while maintaining that all pixels within the same segment have pixel values within a bound defined by that segment. Those pivot points are sent to the clients to recover the original rectangular region through linear interpolation. If the bounds for all segments are , NOLI results in a lossless representation, otherwise, it results in a lossy representation. 2DLI is also a greedy algorithm. It tries to minimize the number of pixels that can not be interpolated by gradients with a constant through its neighboring pixels in the rectangular region. Those pixel values that can not be interpolated are delivered to the clients for recovery of the rectangular region through 2-dimensional linear interpolation. We have implemented our linear interpolation algorithms and compared their performance with other approaches on discrete-toned and smoothed-toned images. Our initial results show that 2DLI achieves a good combination of high compression ratios with low coding time. In particular, our results show that 2DLI provides much better compression than JPEG, gzip or VNC on web pages, screen dumps, and instructional videos, and performs second only to JPEG on smooth-toned images, but with much lower coding time.



Columbia University Department of Computer Science