Hoang D.T., Vitter J.S. Efficient Algorithms for MPEG Video Compression

Издательство John Wiley, 2002, -194 pp.In today's information-driven society, video and other forms of information are being increasingly generated, manipulated, and transmitted in digital form. This trend is manifested in the increased level of automation in businesses, the ubiquity of personal computers, the explosive growth of the Internet and the World Wide Web, and the growing library of multimedia software that incorporates digital audio, images, and video. Within the past decade, we have seen secondary storage on desktop personal computers mushroom from a mere 20 megabytes to tens of gigabytes and beyond. Modem technology has pushed the transmission bandwidth through plain telephone lines from 300 bits/second to 56,000 bits/second, and with asynchronous digital subscriber line we can attain transmission speeds of megabits per second on existing phone lines. Even with technological improvements in transmission bandwidth and storage capacity, the information explosion is quickly making current technologies seem inadequate. For example, application software that once fit onto a few oppy disks now demands multi-megabytes of disk space.
Crucial to the management of digital information are data compression techniques that help make more efficient use of the limited transmission and storage resources available. For storage applications, data compression increases the e_ective storage space, allowing more data to be stored on a given storage device. For transmission applications, data compression increases the effective bandwidth, allowing a higher volume of data to be transmitted over a given transmission medium. Data compression can be viewed as a logical transformation of the data and is independent of the underlying transmission or storage technology. Data compression will not be made obsolete by advances in these technologies, as there will be an ever-present need for even more storage and even greater bandwidth.
A basic idea in data compression is that most information sources of practical interest are not random, but possess some structure. Recognizing and exploiting structure is a major theme in data compression. The amount of compression that is achievable depends upon the amount of redundancy or structure present in the data that can be recognized and exploited. For example, by noting that certain letters or words in English texts appear more frequently than others, we can represent them using fewer bits than the less frequently occurring letters or words. This principle is used in Morse Code, where letters are represented using a varying number of dots and dashes. The recognition and exploitation of statistical properties of a data source form the basis for much of lossless data compression and entropy coding.Preliminaries
Lexicographic Bit Allocation Framework
Optimal Bit Allocation under CBR Constraints
Optimal Bit Allocation under VBR Constraints
Implementation of Lexicographic Bit Allocation
A More Efficient Dynamic Programming Algorithm
Real-Time VBR Rate Control
Extensions of the Lexicographic Framework