Salta al contenuto
Note per Studenti Esercizio - Stima del movimento, GOP e bit-rate del video (domande ed esercizi del corso)

Esercizio - Stima del movimento, GOP e bit-rate del video (domande ed esercizi del corso)

In questa pagina 4

Teoria: Codifica video - stima del moto, MPEG e H.264Un video non compresso costa da centinaia di Mbit/s a decine di Gbit/s; la compressione toglie prima di tutto la ridondanza temporale (immagini consecutive molto simili) con la stima del movimento per block-matching, $\mathbf v^*=\arg\min_{\mathbf v},d(B_k^{(\mathbf p)},B_h^{(\mathbf p+\mathbf v)})+\lambda R(\mathbf v)$, e la compensazione del movimento; l'errore di predizione (sparso) si codifica come in JPEG. I fotogrammi sono di tipo I (intra), P (predetti da un riferimento) e B (da due riferimenti, passato e futuro), organizzati in GOP di $N$ immagini con ancore ogni $M$; le I sono 3-5 volte più grandi delle P e 10-20 volte delle B. Il codificatore ibrido contiene un Decoded Frame Buffer per ripetere la predizione del decodificatore. Standard: MPEG-2, H.264/AVC (2003), H.265/HEVC (2013), H.266/VVC (2021), VP9 e AV1: ciascuno dimezza circa il tasso del precedente. Il tasso medio di un GOP I+$N$P è $R_C=fB_I\frac{1+\alpha N}{1+N}$.Codifica video - stima del moto, MPEG e H.264 → (block-matching, GOP, tasso medio RC=fBI1+αN1+NR_C=fB_I\frac{1+\alpha N}{1+N}, buffer del client). Fonte: domande a risposta multipla ed esempi di preparazione, slide e demo di stima del movimento del corso di Reti di Calcolatori, Ing. Informatica UniPD 2025-26. Conti verificati in Python.

1. Bit-rate dei vettori di movimento

Domanda 1. In un video HD (1920×10801920\times1080, 30 immagini/s) si fa la stima del movimento con block-matching. Nel primo caso si usano blocchi 32×3232\times32 con vettori codificati con 2 bit/vettore; nel secondo blocchi 16×1616\times16 con 2,5 bit/vettore. Quale affermazione è esatta? (a) nel primo caso i vettori richiedono 121,5 kbit/s, (b) nel secondo caso richiedono 8100 bit/s, (c) nel primo caso richiedono 4 volte più bit che nel secondo.

Soluzione. Quattro passaggi: pixel per immagine; blocchi per immagine; bit per immagine; bit al secondo.

  • Pixel: 1920⋅1080=2 073 6001920\cdot1080=2\,073\,600.
  • Primo caso: blocchi =2 073 60032⋅32=2025=\frac{2\,073\,600}{32\cdot32}=2025; bit/immagine =2⋅2025=4050=2\cdot2025=4050; bit/s =4050⋅30=121 500=121,5=4050\cdot30=121\,500=\mathbf{121{,}5} kbit/s: (a) vera.
  • Secondo caso: blocchi =2 073 60016⋅16=8100=\frac{2\,073\,600}{16\cdot16}=8100; bit/immagine =2,5⋅8100=20 250=2{,}5\cdot8100=20\,250; bit/s =20 250⋅30=607 500=607,5=20\,250\cdot30=607\,500=607{,}5 kbit/s. (b) falsa: 8100 è il numero di blocchi per immagine, non un bit-rate.
  • (c) falsa: è il contrario; il primo caso richiede 121,5607,5=15\frac{121{,}5}{607{,}5}=\frac15 dei bit del secondo (dimezzare il lato del blocco quadruplica i vettori, e ogni vettore costa un po' di più: 4⋅2,52=54\cdot\frac{2{,}5}{2}=5).

Conferma con la tabella delle slide (immagine CIF 352×288352\times288). Blocchi: 8×8→15848\times8\to1584, 16×16→39616\times16\to396, 32×32→9932\times32\to99. Tasso totale dei vettori: 79387938, 16681668, 368368 bit, cioè 79381584=5,0\frac{7938}{1584}=5{,}0, 1668396=4,2\frac{1668}{396}=4{,}2, 36899=3,7\frac{368}{99}=3{,}7 bit per vettore: con blocchi più piccoli i vettori sono più numerosi e ciascuno costa di più (meno regolari rispetto ai vicini), il tasso totale cresce di 4,84{,}8 volte da 16×1616\times16 a 8×88\times8, il PSNR del predittore sale da 24,5124{,}51 a 26,5326{,}53 dB e il tempo di calcolo 3,53{,}5 volte.

Ricerca three-step. Per una finestra di ricerca 14×14=19614\times14=196 candidati la full search fa 196 confronti; la three-step ne fa 99 (primo passo) +8+8+8+8 (i passi successivi riusano il centro) =25=25: riduzione 1−25196=87%1-\frac{25}{196}=87\%.

2. GOP, ritardo e buffer

Domanda 2. Un codificatore video usa un GOP del tipo IPP…PIPP\dots P con una immagine Intra e NN immagini P. Le Intra sono codificate con Bintra=400B_{\text{intra}}=400 kbit, le P con Binter=αBintraB_{\text{inter}}=\alpha B_{\text{intra}}, α=110\alpha=\frac1{10}, cioè 40 kbit. Il video ha f=25f=25 immagini/s. Dopo la compressione è trasmesso su una connessione di 10 link identici, ciascuno con throughput costante di 2 Mbit/s. Quale affermazione è esatta? (a) il ritardo end-to-end di un'immagine può arrivare fino a non meno di 2 secondi; (b) se N>5N>5 allora da un GOP all'altro il playout buffer del client tende a riempirsi in fase di riproduzione; (c) il minimo throughput (al variare di NN) necessario per supportare la trasmissione video è 10 Mbit/s.

Soluzione.

  • (a) Il ritardo di trasmissione di una Intra su un link è 400 0002⋅106=0,2\frac{400\,000}{2\cdot10^6}=0{,}2 s =200=200 ms; con 10 link in cascata (store-and-forward) il ritardo end-to-end è almeno 10⋅200 ms=210\cdot200\,\text{ms}=2 s, e ancora non si sono contati accodamento, processing e propagazione. Quindi "fino a non meno di 2 secondi" è vera.
  • (b) Il tasso medio del GOP è RC=fBintra1+αN1+N=25⋅400 000⋅1+0,1N1+N=10 Mbit/s⋅1+0,1N1+NR_C=fB_{\text{intra}}\frac{1+\alpha N}{1+N}=25\cdot400\,000\cdot\frac{1+0{,}1N}{1+N}=10\,\text{Mbit/s}\cdot\frac{1+0{,}1N}{1+N}. Il buffer si riempie se RC<S=2R_C<S=2 Mbit/s (la rete usata ai fini del playout è la più lenta: 2 Mbit/s). Tabella: N=5→2,5N=5\to2{,}5 Mbit/s; N=6→2,29N=6\to2{,}29; N=7→2,125N=7\to2{,}125; N=8→2,000N=8\to2{,}000; N=9→1,9N=9\to1{,}9; N=10→1,82N=10\to1{,}82. Condizione: N≥RIntra−SS−RInter=10−22−1=8N\ge\frac{R_{\text{Intra}}-S}{S-R_{\text{Inter}}}=\frac{10-2}{2-1}=8 per avere RC≤SR_C\le S (uguale per N=8N=8: il buffer resta costante); riempimento strettamente per N≥9N\ge9. Per N=6,7N=6,7 il buffer si svuota. (b) falsa.
  • (c) Smin⁡=inf⁡NRC=lim⁡N→∞RC=fαBintra=RInter=1S_{\min}=\inf_NR_C=\lim_{N\to\infty}R_C=f\alpha B_{\text{intra}}=R_{\text{Inter}}=1 Mbit/s (la funzione 1+αN1+N\frac{1+\alpha N}{1+N} è strettamente decrescente). Qualsiasi S>RInterS>R_{\text{Inter}} può sostenere il video purché NN sia abbastanza grande. (c) falsa (10 Mbit/s è RIntraR_{\text{Intra}}, il caso N=0N=0 di tutte intra).
Condizione R_C <= S, con R_Intra = 10 Mbit/s, R_Inter = 1 Mbit/s:
   S <= 1 Mbit/s            : mai soddisfatta
   S >= 10 Mbit/s           : sempre (per ogni N)
   1 < S < 10 Mbit/s        : N >= (10 - S) / (S - 1)       (per S = 2: N >= 8)

Domanda 3 (GOP e riproduzione). Un video ha 30 fps, struttura GOP I+9PI+9P, bit per frame I=300I=300 kbit, rapporto tra bit di una P e bit di una I uguale a 0,20{,}2, throughput S=2S=2 Mbit/s. Quale affermazione è corretta, relativamente al periodo di playout? (a) il buffer tende a svuotarsi, (b) a riempirsi, (c) il sistema è instabile (oscilla), (d) non è determinabile.

Bit per GOP: 300+9⋅0,2⋅300=300+540=840300+9\cdot0{,}2\cdot300=300+540=840 kbit. Il GOP ha 10 frame, quindi dura 1030=13\frac{10}{30}=\frac13 s: in un secondo ci sono 3 GOP, RC=840⋅3=2520R_C=840\cdot3=2520 kbit/s =2,52=2{,}52 Mbit/s >S=2>S=2 Mbit/s. In riproduzione B′=SRC−1=22,52−1=−0,206<0B'=\frac S{R_C}-1=\frac2{2{,}52}-1=-0{,}206<0: il buffer si svuota: (a). (b) falsa perché RC>SR_C>S. (c) l'oscillazione c'è solo dentro il singolo GOP (il buffer cala quando passano le I e risale sulle P), ma l'andamento medio è decrescente. (d) è determinabile.

3. Struttura del GOP (esercizio costruito)

Domanda 4. Con GOP di lunghezza N=12N=12 e distanza tra le ancore M=3M=3, scrivere l'ordine di visualizzazione e di codifica. Soluzione. Visualizzazione: I0 B1 B2 P3 B4 B5 P6 B7 B8 P9 B10 B11 ∣ I12I_0\,B_1\,B_2\,P_3\,B_4\,B_5\,P_6\,B_7\,B_8\,P_9\,B_{10}\,B_{11}\,|\,I_{12}. Ogni coppia di B si predice dalle due ancore che la racchiudono (l'ultima coppia B10,B11B_{10},B_{11} dalla P9P_9 e dalla I12I_{12} del GOP seguente). Codifica: I0 P3 B1 B2 P6 B4 B5 P9 B7 B8 I12 B10 B11I_0\ P_3\ B_1\ B_2\ P_6\ B_4\ B_5\ P_9\ B_7\ B_8\ I_{12}\ B_{10}\ B_{11}. Il decodificatore deve riordinare i frame prima di mostrarli, e il codificatore deve aspettare l'ancora futura per codificare le B: un ritardo di riordino di circa M−1M-1 frame (con M=3M=3 e 25 fps, 80 ms).

Domanda 5. Se una Intra pesa 400 kbit e una P 40 kbit, e una B 20 kbit, quanti bit richiede un GOP con N=12N=12, M=3M=3 (1 I, 3 P, 8 B)? 400+3⋅40+8⋅20=680400+3\cdot40+8\cdot20=680 kbit; durata 1225=0,48\frac{12}{25}=0{,}48 s; RC=6800,48=1,417R_C=\frac{680}{0{,}48}=1{,}417 Mbit/s. (Le B pesano meno delle P: a parità di qualità le immagini I sono 3-5 volte le P e 10-20 volte le B.)

Errori tipici

  • Dimenticare il numero di blocchi (si divide per l'area del blocco) o i fotogrammi al secondo nel bit-rate dei vettori.
  • Usare 1 al posto di 1+N1+N come numero di frame del GOP (con I+NI+NP il GOP ha N+1N+1 frame).
  • Confrontare RCR_C con il throughput di un singolo link, anche con più link in serie: conta il minimo (il collo di bottiglia).
  • Confondere la condizione di riempimento (RC<SR_C<S) con quella di equilibrio (RC=SR_C=S): per N=8N=8 nell'esempio il buffer resta costante.
  • Dimenticare che il ritardo end-to-end minimo conta tutti i link in cascata (10 ×\times 200 ms), non uno solo.

Versione ripasso

Bit-rate dei vettori. Blocchi =pixellato2=\frac{\text{pixel}}{\text{lato}^2}; bit/immagine =bit/vettore×blocchi=\text{bit/vettore}\times\text{blocchi}; bit/s =×fps=\times\text{fps}. HD 2 073 6002\,073\,600 pixel, 30 fps: 32×3232\times32, 2 bit: 2025⋅2⋅30=121,52025\cdot2\cdot30=121{,}5 kbit/s (vera); 16×1616\times16, 2,5 bit: 8100⋅2,5⋅30=607,58100\cdot2{,}5\cdot30=607{,}5 kbit/s (8100 è il numero di blocchi, non un bit-rate); il primo caso richiede 15\frac15 del secondo (non 4 volte di più).

Tabella CIF. Blocchi 1584, 396, 99; tasso 7938, 1668, 368 bit ⇒\Rightarrow 5,0, 4,2, 3,7 bit/vettore; 8×88\times8 vs 16×1616\times16: tasso ×4,8\times4{,}8, PSNR +2+2 dB, tempo ×3,5\times3{,}5. Three-step: 25 confronti su 196 ⇒−87%\Rightarrow-87\%.

GOP. II 400 kbit, P=αBI=40P=\alpha B_I=40 kbit, 25 fps, 10 link da 2 Mbit/s.

  • (a) ritardo e2e ≥10⋅400 0002⋅106=10⋅0,2=2\ge10\cdot\frac{400\,000}{2\cdot10^6}=10\cdot0{,}2=2 s: vera.
  • RC=10⋅1+0,1N1+NR_C=10\cdot\frac{1+0{,}1N}{1+N} Mbit/s: N=5→2,5N=5\to2{,}5, 6→2,296\to2{,}29, 7→2,1257\to2{,}125, 8→28\to2, 9→1,99\to1{,}9. Riempimento se RC<2R_C<2: N≥9N\ge9; costante a N=8N=8; svuotamento per N=6,7N=6,7: (b) falsa. Condizione N≥RIntra−SS−RInter=10−22−1=8N\ge\frac{R_{\text{Intra}}-S}{S-R_{\text{Inter}}}=\frac{10-2}{2-1}=8.
  • (c) Smin⁡=inf⁡NRC=RInter=1S_{\min}=\inf_NR_C=R_{\text{Inter}}=1 Mbit/s (non 10): falsa. RC≤SR_C\le S: mai se S≤RInterS\le R_{\text{Inter}}; sempre se S≥RIntraS\ge R_{\text{Intra}}.

I+9P. BI=300B_I=300 kbit, P=0,2BIP=0{,}2B_I, 30 fps, S=2S=2 Mbit/s: bit per GOP 300+9⋅60=840300+9\cdot60=840 kbit; 3 GOP/s ⇒RC=2,52\Rightarrow R_C=2{,}52 Mbit/s >S>S; B′=22,52−1=−0,206B'=\frac{2}{2{,}52}-1=-0{,}206: il buffer si svuota.

GOP N=12N=12, M=3M=3. Visualizzazione I0B1B2P3B4B5P6B7B8P9B10B11∣I12I_0B_1B_2P_3B_4B_5P_6B_7B_8P_9B_{10}B_{11}|I_{12}; codifica I0P3B1B2P6B4B5P9B7B8I12B10B11I_0P_3B_1B_2P_6B_4B_5P_9B_7B_8I_{12}B_{10}B_{11}; riordino ≈M−1\approx M-1 frame. Con I 400, P 40, B 20 kbit: 400+120+160=680400+120+160=680 kbit in 1225\frac{12}{25} s: 1,4171{,}417 Mbit/s.

Errori tipici: non dividere per l'area del blocco o dimenticare i fps; frame del GOP =N+1=N+1; confrontare con il throughput di un solo link invece del minimo; confondere riempimento (RC<SR_C<S) ed equilibrio (RC=SR_C=S); contare un solo link nel ritardo end-to-end.

Teoria: Codifica video - stima del moto, MPEG e H.264Un video non compresso costa da centinaia di Mbit/s a decine di Gbit/s; la compressione toglie prima di tutto la ridondanza temporale (immagini consecutive molto simili) con la stima del movimento per block-matching, $\mathbf v^*=\arg\min_{\mathbf v},d(B_k^{(\mathbf p)},B_h^{(\mathbf p+\mathbf v)})+\lambda R(\mathbf v)$, e la compensazione del movimento; l'errore di predizione (sparso) si codifica come in JPEG. I fotogrammi sono di tipo I (intra), P (predetti da un riferimento) e B (da due riferimenti, passato e futuro), organizzati in GOP di $N$ immagini con ancore ogni $M$; le I sono 3-5 volte più grandi delle P e 10-20 volte delle B. Il codificatore ibrido contiene un Decoded Frame Buffer per ripetere la predizione del decodificatore. Standard: MPEG-2, H.264/AVC (2003), H.265/HEVC (2013), H.266/VVC (2021), VP9 e AV1: ciascuno dimezza circa il tasso del precedente. Il tasso medio di un GOP I+$N$P è $R_C=fB_I\frac{1+\alpha N}{1+N}$.Codifica video - stima del moto, MPEG e H.264 →.

Esercizi su questo argomento

Teoria collegata