Fast motion detection for thin client compression

State-of-the-art lossless compression methods have enabled thin client computing across wide area networks which is rapidly gaining momentum. While these compression methods exploit redundancies typically found in synthetic images, none of them exploits large blocks often occurring verbatim in sequences of display updates because detecting movements of such blocks is computationally demanding. In this paper, we present a novel algorithm for detecting block movements in image sequences that is fast enough for interactive logins. We also integrate our algorithm into TCC, the best previously known codec for thin client computing. In the presence of motion, our new codec, TCC-M, typically compresses 50 to 950 times more efficiently than TCC. It also reduces the end-to-end latency of scrolling Web pages at DSL speeds by a factor of 5.