A video compression scheme with optimal bit allocation among segmentation, motion, and residual error

Guido M. Schuster*, Aggelos K. Katsaggelos

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

34 Scopus citations


In this paper, we present a theory for the optimal bit allocation among quadtree (QT) segmentation, displacement vector field (DVF), and displaced frame difference (DFD). The theory is applicable to variable block size motion-compensated video coders (VBSMCVC), where the variable block sizes are encoded using the QT structure, the DVF is encoded by first-order differential pulse code modulation (DPCM), the DFD is encoded by a block-based scheme, and an additive distortion measure is employed. We derive an optimal scanning path for a QT that is based on a Hilbert curve. We consider the case of a lossless VBSMCVC first, for which we develop the optimal bit allocation algorithm using dynamic programming (DP). We then consider a lossy VBSMCVC, for which we use Lagrangian relaxation, and show how an iterative scheme, which employs the DP-based solution, can be used to find the optimal solution. We finally present a VBSMCVC, which is based on the proposed theory, which employs a DCT-based DFD encoding scheme. We compare the proposed coder with H.263. The results show that it outperforms H.263 significantly in the rate distortion sense, as well as in the subjective sense.

Original languageEnglish (US)
Pages (from-to)1487-1502
Number of pages16
JournalIEEE Transactions on Image Processing
Issue number11
StatePublished - 1997


  • Dynamic programming
  • Lagrangian relaxation
  • Optimal bit allocation
  • Rate distortion theory
  • Video compression

ASJC Scopus subject areas

  • Software
  • Computer Graphics and Computer-Aided Design


Dive into the research topics of 'A video compression scheme with optimal bit allocation among segmentation, motion, and residual error'. Together they form a unique fingerprint.

Cite this