Blog · November 2026 · 9 min read Blog · Novembre 2026 · 9 min de lectureالمدونة · نوفمبر 2026 · 9 دقائق قراءة

Inside a video encoder: DCT, motion vectors and a one-word bug Dans un encodeur vidéo : DCT, vecteurs de mouvement et un bug d'un seul motداخل مشفّر فيديو: DCT ومتجهات الحركة، وخطأ من كلمة واحدة

A simplified MPEG-4 encoder in Python, step by step: how 20 frames go from 1,620 KB to 62 KB. And how changing a single word, floor to round, gave better quality and almost twice the compression at the same time. Un encodeur MPEG-4 simplifié en Python, étape par étape : comment 20 images passent de 1 620 Ko à 62 Ko. Et comment changer un seul mot, floor en round, a donné à la fois une meilleure qualité et presque deux fois plus de compression.مشفّر MPEG-4 مبسّط بلغة Python، خطوة بخطوة: كيف تنتقل 20 صورة من 1620 كيلوبايت إلى 62 كيلوبايت. وكيف أعطى تغيير كلمة واحدة، floor إلى round، جودة أفضل وضغطاً يقارب الضعف في الوقت نفسه.

The projectLe projetالمشروع

For the multimedia course of my Master's at USTHB, a classmate and I wrote a simplified MPEG-4-like encoder in Python with NumPy and SciPy: frames in, a compressed .bin file out, and a decoder that rebuilds the frames. The test video is 20 synthetic frames of 192 × 144 pixels: a gradient background with a square moving right and a circle moving down. Raw, that is 1,620 KB. Pour le module Multimédia de mon Master à l'USTHB, nous avons écrit à deux un encodeur simplifié de type MPEG-4 en Python avec NumPy et SciPy : des images en entrée, un fichier .bin compressé en sortie, et un décodeur qui reconstruit les images. La vidéo de test fait 20 images synthétiques de 192 × 144 pixels : un fond en dégradé, un carré qui se déplace vers la droite et un cercle qui descend. Brute, elle pèse 1 620 Ko.في مقياس الوسائط المتعددة ضمن الماستر في جامعة هواري بومدين، كتبت مع زميل مشفّراً مبسّطاً شبيهاً بـ MPEG-4 بلغة Python مع NumPy وSciPy: صور في المدخل، وملف .bin مضغوط في المخرج، ومفكّك يعيد بناء الصور. فيديو الاختبار 20 صورة اصطناعية بحجم 192 × 144 بكسل: خلفية متدرجة، ومربع يتحرك نحو اليمين، ودائرة تنزل. وحجمه الخام 1620 كيلوبايت.

YCbCr4:2:0
→
DCT 8×8I-framesimages Iصور I
→
MotionMouvementالحركةP-framesimages Pصور P
→
QuantiseQuantifierالتكميمQ(i, j)
→
zlibvideo.bin

Step 1: throw away colour the eye does not seeÉtape 1 : jeter la couleur que l'œil ne voit pasالخطوة 1: التخلص من الألوان التي لا تراها العين

Our eyes are much more sensitive to brightness than to colour. So the first step converts each frame from BGR to YCbCr (brightness Y, plus two colour channels), then keeps the colour channels at half width and half height: 4:2:0 subsampling. Each colour channel shrinks to a quarter, so the frame goes from 3 values per pixel to 1.5. Half the data is gone before any real compression, and nobody notices. Nos yeux sont beaucoup plus sensibles à la luminosité qu'à la couleur. La première étape convertit donc chaque image de BGR en YCbCr (la luminance Y, plus deux canaux de couleur), puis garde les canaux de couleur à demi-largeur et demi-hauteur : c'est le sous-échantillonnage 4:2:0. Chaque canal de couleur tombe au quart, donc l'image passe de 3 valeurs par pixel à 1,5. La moitié des données disparaît avant toute vraie compression, sans que personne ne le remarque.أعيننا أكثر حساسية للإضاءة منها للألوان بكثير. لذلك تحوّل الخطوة الأولى كل صورة من BGR إلى YCbCr (الإضاءة Y، مع قناتين للألوان)، ثم تُبقي قناتي الألوان بنصف العرض ونصف الارتفاع: إنه الاختزال 4:2:0. تنكمش كل قناة لون إلى الربع، فتنتقل الصورة من 3 قيم لكل بكسل إلى 1.5. يختفي نصف البيانات قبل أي ضغط حقيقي، دون أن يلاحظ أحد.

Step 2: I-frames, from pixels to frequenciesÉtape 2 : les images I, des pixels aux fréquencesالخطوة 2: صور I، من البكسلات إلى الترددات

An I-frame is compressed on its own, like a JPEG. Each channel is cut into 8 × 8 blocks, shifted by −128, and transformed with the discrete cosine transform (DCT). The DCT does not compress anything by itself; it rewrites the block as a mix of patterns, from flat (top-left) to fine detail (bottom-right). In a natural image, almost all the energy ends up in the few top-left coefficients. Une image I est compressée seule, comme un JPEG. Chaque canal est découpé en blocs de 8 × 8, décalé de −128, puis transformé avec la transformée en cosinus discrète (DCT). La DCT ne compresse rien toute seule : elle réécrit le bloc comme un mélange de motifs, du plat (en haut à gauche) aux détails fins (en bas à droite). Dans une image naturelle, presque toute l'énergie se retrouve dans les quelques coefficients en haut à gauche.تُضغط صورة I وحدها، مثل JPEG. تُقطَّع كل قناة إلى كتل 8 × 8، وتُزاح بـ −128، ثم تُحوَّل بتحويل جيب التمام المتقطع (DCT). لا يضغط DCT أي شيء وحده؛ بل يعيد كتابة الكتلة كمزيج من الأنماط، من المسطّح (أعلى اليسار) إلى التفاصيل الدقيقة (أسفل اليمين). وفي صورة طبيعية، تتجمع كل الطاقة تقريباً في المعاملات القليلة أعلى اليسار.

The real loss happens next, in quantisation: each coefficient is divided by a step from a matrix, and only the integer is kept. The course formula makes the step grow with frequency, so fine details are divided by bigger numbers and mostly become 0. The factor Fq is the quality knob. La vraie perte arrive ensuite, à la quantification : chaque coefficient est divisé par un pas tiré d'une matrice, et on ne garde que l'entier. La formule du cours fait grandir le pas avec la fréquence : les détails fins sont divisés par de plus grands nombres et deviennent surtout des 0. Le facteur Fq est le bouton de qualité.تحدث الخسارة الحقيقية بعد ذلك، في التكميم: يُقسم كل معامل على خطوة مأخوذة من مصفوفة، ولا يُحتفظ إلا بالعدد الصحيح. وصيغة المقياس تجعل الخطوة تكبر مع التردد، فتُقسم التفاصيل الدقيقة على أعداد أكبر وتصبح في الغالب أصفاراً. والمعامل Fq هو زر الجودة.

def get_q_matrix(fq=1.0):
    # Q(i, j) = 1 + (1 + i + j) * Fq : bigger steps for higher frequencies
    return np.fromfunction(lambda i, j: 1 + (1 + i + j) * fq, (8, 8)).astype(np.float32)

block  = padded[i*8:(i+1)*8, j*8:(j+1)*8] - 128.0
coeffs = dctn(block, norm="ortho")
blocks[i, j] = np.floor(coeffs / q_matrix).astype(np.int16)   # remember this line

Step 3: P-frames, sending only what movedÉtape 3 : les images P, n'envoyer que ce qui a bougéالخطوة 3: صور P، إرسال ما تحرّك فقط

Two consecutive frames are almost identical. So in each group of 5 frames, only the first is an I-frame; the next four are P-frames, predicted from the frame before. For each 16 × 16 macroblock, the encoder searches the previous frame within ±8 pixels, so 17 × 17 = 289 candidate positions, and keeps the one with the smallest mean squared error. That gives a motion vector. What is left, the difference between the block and its prediction, is the residual: mostly zeros, coded with the same DCT and quantisation. Deux images consécutives sont presque identiques. Donc dans chaque groupe de 5 images, seule la première est une image I ; les quatre suivantes sont des images P, prédites à partir de l'image d'avant. Pour chaque macrobloc de 16 × 16, l'encodeur cherche dans l'image précédente à ±8 pixels, soit 17 × 17 = 289 positions candidates, et garde celle avec la plus petite erreur quadratique moyenne. Ça donne un vecteur de mouvement. Ce qui reste, la différence entre le bloc et sa prédiction, c'est le résidu : surtout des zéros, codé avec la même DCT et la même quantification.صورتان متتاليتان متطابقتان تقريباً. لذلك في كل مجموعة من 5 صور، الأولى فقط صورة I؛ والأربع التالية صور P، متوقَّعة من الصورة السابقة. لكل كتلة كبيرة 16 × 16، يبحث المشفّر في الصورة السابقة ضمن ±8 بكسل، أي 17 × 17 = 289 موضعاً مرشحاً، ويحتفظ بالموضع ذي أصغر متوسط مربع للخطأ. وهذا يعطي متجه حركة. وما يتبقى، أي الفرق بين الكتلة وتوقّعها، هو البقايا: أصفار في الغالب، تُرمَّز بـ DCT والتكميم نفسيهما.

One detail matters more than it looks: the reference is the reconstructed previous frame, not the original. The decoder never sees the original, only what it rebuilt. If the encoder predicted from originals, the small errors of each frame would pile up on the decoder side and the video would drift further from the truth until the next I-frame. Un détail compte plus qu'il n'y paraît : la référence est l'image précédente reconstruite, pas l'originale. Le décodeur ne voit jamais l'originale, seulement ce qu'il a reconstruit. Si l'encodeur prédisait à partir des originales, les petites erreurs de chaque image s'accumuleraient côté décodeur, et la vidéo dériverait de plus en plus jusqu'à la prochaine image I.هناك تفصيل أهم مما يبدو: المرجع هو الصورة السابقة المعاد بناؤها، لا الأصلية. فالمفكّك لا يرى الأصلية أبداً، بل ما أعاد بناءه فقط. ولو توقّع المشفّر انطلاقاً من الصور الأصلية، لتراكمت الأخطاء الصغيرة لكل صورة عند المفكّك، ولانحرف الفيديو أكثر فأكثر حتى صورة I التالية.

ref     = reconstructed[-1]                 # what the decoder will have, not the original
encoded = encode_pframe(frame, ref, fq=fq)
recon   = decode_pframe(encoded, ref)       # decode right away, inside the encoder
reconstructed.append(recon)                 # becomes the reference for the next frame

Step 4: packing the bitsÉtape 4 : ranger les bitsالخطوة 4: ترتيب البتات

Real MPEG-4 reads each block in zigzag order, run-length codes the long runs of zeros, then uses Huffman or arithmetic coding. To keep the project focused, we serialised everything and compressed it with zlib at level 9. zlib still finds the repeated zeros, which is why quantisation matters so much: the more zeros it produces, the smaller the file. Le vrai MPEG-4 lit chaque bloc en zigzag, code les longues suites de zéros par plages, puis utilise un codage de Huffman ou arithmétique. Pour garder le projet ciblé, nous avons tout sérialisé et compressé avec zlib au niveau 9. zlib trouve quand même les zéros répétés, et c'est pour ça que la quantification compte autant : plus elle produit de zéros, plus le fichier est petit.يقرأ MPEG-4 الحقيقي كل كتلة بترتيب متعرج، ويرمّز سلاسل الأصفار الطويلة بترميز الأطوال، ثم يستعمل ترميز هوفمان أو الترميز الحسابي. ولإبقاء المشروع مركّزاً، سلسلنا كل شيء وضغطته بـ zlib في المستوى 9. ومع ذلك يجد zlib الأصفار المتكررة، ولهذا يهم التكميم كثيراً: كلما أنتج أصفاراً أكثر، صغر الملف.

With the default settings (Fq = 1, groups of 5 frames), the result was 62.5 KB: 26 times smaller, at 33.4 dB PSNR. Raising Fq gave more compression and lower quality, which looked exactly like the expected trade-off: Avec les réglages par défaut (Fq = 1, groupes de 5 images), le résultat faisait 62,5 Ko : 26 fois plus petit, avec un PSNR de 33,4 dB. Augmenter Fq donnait plus de compression et moins de qualité, exactement le compromis attendu :بالإعدادات الافتراضية (Fq = 1، مجموعات من 5 صور)، كانت النتيجة 62.5 كيلوبايت: أصغر بـ 26 مرة، مع PSNR يساوي 33.4 ديسيبل. ورفع Fq أعطى ضغطاً أكثر وجودة أقل، وهو بالضبط التوازن المنتظر:

FqCompressionCompressionالضغطPSNR
1× 26.133.37 dB
2× 28.831.23 dB
4× 31.727.48 dB

The one-word bugLe bug d'un seul motالخطأ ذو الكلمة الواحدة

Rereading the code, one line bothered me: quantisation used np.floor. Floor always rounds down, towards minus infinity. For positive coefficients that is a small loss. For negative ones it is worse: floor(-0.3) is -1, not 0. Every small negative coefficient, which should have vanished, became a −1. That means two problems at once: En relisant le code, une ligne m'a gêné : la quantification utilisait np.floor. Floor arrondit toujours vers le bas, vers moins l'infini. Pour les coefficients positifs, c'est une petite perte. Pour les négatifs, c'est pire : floor(-0.3) vaut -1, pas 0. Chaque petit coefficient négatif, qui aurait dû disparaître, devenait un −1. Ça fait deux problèmes à la fois :عند إعادة قراءة الشيفرة، أزعجني سطر واحد: كان التكميم يستعمل np.floor. الدالة floor تقرّب دائماً نحو الأسفل، نحو سالب ما لا نهاية. بالنسبة للمعاملات الموجبة، هذه خسارة صغيرة. أما السالبة فالأمر أسوأ: floor(-0.3) تساوي -1، لا 0. فكل معامل سالب صغير، كان يجب أن يختفي، صار −1. وهذا يعني مشكلتين في آن واحد:

  • Fewer zeros, so zlib has less to compress, and the file is bigger.Moins de zéros, donc zlib a moins à compresser, et le fichier est plus gros.أصفار أقل، فيجد zlib ما يضغطه أقل، ويكبر الملف.
  • A biased error. With rounding, the error is between −½ and +½ step and averages to zero. With floor, it is always in the same direction, up to a full step, so it adds up instead of cancelling out, and it grows with Fq.Une erreur biaisée. Avec un arrondi, l'erreur est entre −½ et +½ pas et vaut zéro en moyenne. Avec floor, elle va toujours dans le même sens, jusqu'à un pas entier : elle s'additionne au lieu de s'annuler, et elle grandit avec Fq.خطأ منحاز. مع التقريب، يكون الخطأ بين −½ و+½ خطوة ويساوي صفراً في المتوسط. أما مع floor، فهو دائماً في الاتجاه نفسه، حتى خطوة كاملة، فيتراكم بدل أن يتلاشى، ويكبر مع Fq.

I replaced np.floor with np.round in both quantisers (I-frames and residuals), and ran the exact same pipeline on the same 20 frames: J'ai remplacé np.floor par np.round dans les deux quantificateurs (images I et résidus), et relancé exactement la même chaîne sur les mêmes 20 images :عوّضت np.floor بـ np.round في دالتي التكميم كلتيهما (صور I والبقايا)، وأعدت تشغيل السلسلة نفسها تماماً على الصور الـ 20 نفسها:

Fqfloorround
1× 26.1 · 33.37 dB× 33.0 · 34.71 dB
2× 28.8 · 31.23 dB× 40.6 · 34.46 dB
4× 31.7 · 27.48 dB× 50.1 · 33.86 dB

Better on both axes, every time. At Fq = 4, the rounded version is 50 times smaller and still looks better than the floor version at Fq = 1. Most of the "trade-off" in our original table was not a trade-off at all: it was the bias of floor growing with the step size. Mieux sur les deux axes, à chaque fois. À Fq = 4, la version arrondie est 50 fois plus petite et reste meilleure que la version floor à Fq = 1. L'essentiel du « compromis » de notre tableau d'origine n'en était pas un : c'était le biais de floor qui grandissait avec le pas.أفضل على المحورين، في كل مرة. عند Fq = 4، النسخة المقرّبة أصغر بـ 50 مرة وتبقى أفضل من نسخة floor عند Fq = 1. ومعظم «التوازن» في جدولنا الأصلي لم يكن توازناً أصلاً: بل كان انحياز floor الذي يكبر مع حجم الخطوة.

Why did we not see it? Because nothing looked broken. 33 dB is a reasonable score, the frames looked fine, and quality going down when compression goes up is what every textbook predicts. A bug that produces plausible numbers is the hardest kind to find. Pourquoi nous ne l'avons pas vu ? Parce que rien n'avait l'air cassé. 33 dB est un score correct, les images avaient l'air bonnes, et une qualité qui baisse quand la compression monte, c'est exactement ce que prédit chaque manuel. Un bug qui produit des chiffres plausibles est le plus difficile à trouver.لماذا لم نره؟ لأن لا شيء بدا معطوباً. 33 ديسيبل نتيجة معقولة، والصور بدت جيدة، وانخفاض الجودة عند ارتفاع الضغط هو بالضبط ما يتوقعه كل كتاب. والخطأ الذي ينتج أرقاماً معقولة هو الأصعب في الاكتشاف.

Where the bytes goOù partent les octetsأين تذهب البايتات

Compressing each part of the bitstream separately gives a rough picture of the file (Fq = 1): Compresser séparément chaque partie du flux donne une idée approximative du contenu du fichier (Fq = 1) :ضغط كل جزء من التدفق على حدة يعطي صورة تقريبية عن محتوى الملف (Fq = 1):

PartPartieالجزءSharePartالنسبة
P-frame luma residualsRésidus de luminance des images Pبقايا الإضاءة في صور P41%
P-frame colour channelsCanaux de couleur des images Pقنوات الألوان في صور P36%
I-frame lumaLuminance des images Iالإضاءة في صور I11%
I-frame colour channelsCanaux de couleur des images Iقنوات الألوان في صور I9%
Motion vectorsVecteurs de mouvementمتجهات الحركة2%

The surprise is the second line. Motion compensation only runs on the brightness channel; in P-frames, the colour channels are coded from scratch, like an I-frame. Reusing the luma motion vectors, halved, to predict the colour channels too is how real codecs do it, and it would attack more than a third of the file. La surprise, c'est la deuxième ligne. La compensation de mouvement ne s'applique qu'à la luminance ; dans les images P, les canaux de couleur sont codés depuis zéro, comme dans une image I. Réutiliser les vecteurs de mouvement de la luminance, divisés par deux, pour prédire aussi la couleur, c'est ce que font les vrais codecs, et ça s'attaquerait à plus d'un tiers du fichier.المفاجأة في السطر الثاني. تعويض الحركة لا يُطبَّق إلا على قناة الإضاءة؛ وفي صور P، تُرمَّز قنوات الألوان من الصفر، كما في صورة I. وإعادة استعمال متجهات حركة الإضاءة، مقسومة على اثنين، لتوقّع الألوان أيضاً هو ما تفعله المرمّزات الحقيقية، وسيستهدف أكثر من ثلث الملف.

What we could do nextCe qu'on pourrait faire ensuiteما يمكن فعله بعد ذلك

  • Motion-compensate the colour channels with the luma vectors, as above.Compenser le mouvement des canaux de couleur avec les vecteurs de la luminance, comme ci-dessus.تعويض حركة قنوات الألوان بمتجهات الإضاءة، كما سبق.
  • A faster search. 289 positions per macroblock is a full search. A three-step or diamond search checks a few dozen positions and usually finds the same vector.Une recherche plus rapide. 289 positions par macrobloc, c'est une recherche exhaustive. Une recherche en trois pas ou en losange teste quelques dizaines de positions et trouve en général le même vecteur.بحث أسرع. 289 موضعاً لكل كتلة كبيرة بحث شامل. والبحث بثلاث خطوات أو بشكل المعيّن يختبر بضع عشرات من المواضع ويجد عادة المتجه نفسه.
  • Real entropy coding: zigzag order, run-length and Huffman instead of zlib over serialised arrays.Un vrai codage entropique : ordre zigzag, codage par plages et Huffman au lieu de zlib sur des tableaux sérialisés.ترميز إنتروبي حقيقي: ترتيب متعرج، وترميز الأطوال، وهوفمان بدل zlib على مصفوفات مسلسلة.
  • Real footage. Synthetic shapes on a smooth gradient are an easy case. Camera noise and complex motion would tell much more.De vraies vidéos. Des formes synthétiques sur un dégradé lisse sont un cas facile. Le bruit d'une caméra et des mouvements complexes en diraient beaucoup plus.فيديو حقيقي. الأشكال الاصطناعية على تدرّج ناعم حالة سهلة. وضجيج الكاميرا والحركة المعقدة سيكشفان أكثر بكثير.

TakeawaysÀ retenirالخلاصة

  • Video compression stacks simple ideas: drop colour detail, move to frequencies, predict from the past, and send only the difference.La compression vidéo empile des idées simples : jeter le détail de couleur, passer aux fréquences, prédire à partir du passé, et n'envoyer que la différence.ضغط الفيديو يكدّس أفكاراً بسيطة: التخلص من تفاصيل الألوان، والانتقال إلى الترددات، والتوقّع من الماضي، وإرسال الفرق فقط.
  • Always predict from what the decoder will have, never from the original.Toujours prédire à partir de ce qu'aura le décodeur, jamais à partir de l'original.توقّع دائماً مما سيملكه المفكّك، لا من الأصل أبداً.
  • Rounding is a design decision. floor, round and truncation give very different errors, especially around zero.L'arrondi est une décision de conception. floor, round et la troncature donnent des erreurs très différentes, surtout autour de zéro.التقريب قرار تصميمي. floor وround والبتر تعطي أخطاء مختلفة جداً، خاصة حول الصفر.
  • When results match your expectations, check them anyway. Plausible numbers can hide a bug.Quand les résultats correspondent à ce qu'on attend, il faut quand même les vérifier. Des chiffres plausibles peuvent cacher un bug.عندما تطابق النتائج توقعاتك، تحقق منها رغم ذلك. فالأرقام المعقولة قد تخفي خطأ.

The code, the figures and the report (in French) are on GitHub. Le code, les figures et le rapport sont sur GitHub.الشيفرة والأشكال والتقرير (بالفرنسية) موجودة على GitHub.