USPTO invited talk, "structures in video coding"

This week I had the honour of presenting an invited talk to examiners at the US Patent and Trademark Office in Washington DC:

The topic of my talk was "structures in video coding". I explained how video codec structures have evolved from simple, repetitive 16x16 macroblocks in early standards such as MPEG-1....

..... to complex hierarchies of blocks in recent standards such as HEVC:

I examined the effects of increasingly complex block structures. These changes have led to dramatic improvements in compression performance but also increasing computational demands. I left the audience with a question: after 25+ years of intensive research and development, why do mainstream video codecs still rely on rectangular block structures?

- Iain Richardson

7 important video compression concepts that are more than 20 years old

The latest MPEG / ITU video compression standard, H.265 or HEVC, was published in 2013. HEVC is a significant technical achievement, but it's partly based on fundamental work carried out many decades ago.

An HEVC video codec includes the basic building blocks of:

• Prediction : create an estimate or prediction of a current block of video data
• Transform : convert a block of samples into a spatial frequency representation
• Entropy coding : encode video information into a compressed bitstream

Here are seven important research papers and patents dating back to the 1950s that helped to shape present day video coding technology.

Key:

1. “A Method for the Construction of Minimum Redundancy Codes”, D A Huffman, Proceedings of the I.R.E., September 1952

- Variable length binary codes for data compression.

2. “Transform coding of image difference signals”, M R Schroeder, US Patent 3679821, 1972

- Coding moving images using frame differencing, i.e. simple inter-frame prediction.

3.  “Discrete Cosine Transform”, Ahmed, Natarajan and Rao, IEEE Transactions on Computers, Jan 1974

- The classic paper on the DCT, widely used in image and video compression.

4. “Generalized Kraft inequality and arithmetic coding”, J J Rissanen, IBM J. Res. Dev. 20, May 1976

- Arithmetic coding, a forerunner of H.264 and HEVC’s CABAC.

5. “Displacement measurement and its application in interframe image coding”, J R Jain and A K Jain, IEEE Trans. Communications, December 1981

- An early description of motion compensated prediction for video coding.

6. “Variable size block matching motion compensation with applications to video coding”, M H Chan, Y B Yu and A G Constantinides, IEE Proceedings Vol 137, August 1990

- Motion compensated prediction with variable size blocks.

7. “MPEG: A video compression standard for multimedia applications”, D Le Gall, Communications of the ACM, Vol 34 No 4, April 1991

- Bidirectional prediction as used in the MPEG-1 video compression standard.