Liikumishinnangu simulaator

Simuleeri kaadritevahelist liikumishinnangut, plokkide sobitamist, otsingumustreid ja pakkimise jääke.

Näidisarvutus — Liikumishinnangu simulaator

Keskmine SAD ploki kohta	1693
Keskmine vektori suurus	1.54 px
Otsitud punktid ploki kohta	14400 punkti (225.0 ploki kohta)

Need on väärtused, mida kalkulaator lehe avamisel näitab. Muuda ülal mõnda sisendit, et need ümber arvutada.

Interaktiivse simulatsiooni laadimine...

Kiire otsing ei vaata suuremat osa aknast kunagi 🖖

Liikumishinnang on videokompressiooni kitsaskoht. 16x16 suurust makroplokki võrreldakse võrdluskaadris otsinguakna piires kandidaadiga, millel on väikseim absoluutsete erinevuste summa (SAD). Ammendav täisotsing hindab kõiki (2r+1)² positsiooni, mis on aeglane. Kiired algoritmid nagu teemant- ja kuusnurkne otsing hindavad ainult murdosa punktidest, nihutades otsingukeskust korduvalt ja lõpetades, kui miinimum jääb mustri keskele. Vii hiir mis tahes ploki kohale, et näha selle otsinguakent ja kandidaatide hindamisi reaalajas.

Miks saata liikumine, mitte pikslid 🖖

Järjestikused videokaadrid on peaaegu identsed, seega ei salvesta koodek iga kaadrit tervikuna, vaid kirjeldab praegust kaadrit eelmise nihkunud tükkidena. Iga 16×16 plokk saab liikumisvektori, mis osutab parimale vastele, ning väikese jääksignaali kõige jaoks, mida nihe seletada ei suutnud. Point: sujuvad kaamerapanoraamid pakitakse suurepäraselt, sest üksainus vektor asendab tuhandeid piksleid.

Liikumisvektorid pole tegelik liikumine 🖖

Kodeerija ei küsi kunagi, mis tegelikult liikus — ta otsib vaid plokki väikseima SAD-iga. Seepärast võib ühtlastes või mürarikastes piirkondades võidukas vektor osutada täiesti absurdselt, mitte sugugi tegeliku nihke suunas. Tõsta müra liugurit ja vaata, kuidas vektoriväli kaoseks laguneb. Just seetõttu sobivad liikumisvektorid halvasti optiliseks vooks, kuid suurepäraselt pakkimiseks: nad teenivad bitikiirust, mitte füüsikat.

ÜKS ASTE AHELAST — MIS SAABUB, MIS VÄLJUB JA MIS EDASPIDI KATKEB

Kus see kodeerimiskonveieris asub

Videokodeerija ei ole üks algoritm, vaid kaheksa astet kindlas järjekorras — ja järjekord ei ole suvaline: iga aste on olemas seetõttu, et eelmine tegi tema töö võimalikuks. See tööriist modelleerib neist üht. Allolev ahel viitab ülejäänud seitsmele.

Liikumishinnangu simulaator — leiab, kuhu iga blokk liikus, ja kodeerib bloki asemel erinevuse

Mis saabub: P- või B-kaader koos oma viitekaadritega.
Mis väljub: Liikumisvektor iga bloki kohta ja jääk — täpselt see, mille ennustus valesti sai.
Mida järgmine aste eeldab: Kvantimine saab jäägi, mitte pildi. Jäägid on peaaegu kõikjal nulli lähedal ja just seetõttu on nende kvantimine odav.
Mis siin valesti läheb: Halb vaste ei anna vale pilti, vaid kalli pildi. Jääk kannab rohkem energiat ja sama kvantija seadistus väljastab selle jaoks rohkem bitte. See aste muudab väljundi suurust, mitte ühtki selle seadistust.

Eelmine aste: GOP-struktuur Järgmine aste: Kvantimine

Ülesanne täielikult lahendatud

225 positsioonist ploki kohta tuletatud otsinguaken 5 sammu
Täielik liikumisotsing kontrollib 225 positsiooni ploki kohta, kokku 14 400. Arvuta selle põhjal otsinguaken ja see, mida kiire otsing juurde annab.
1. 225 on täisruut ja see ongi vihje: otsing on ruudukujuline aken mõõtmetega 15 korda 15 kandidaatnihet, mis tähendab −7 kuni +7 pikslit igas suunas.
  
  $full search over \pm 7 px in each axis : 15 \times 15 = 225 positions per block$
2. Koguarvu jagamisel plokipõhise arvuga saadakse plokkide arv, milleks kaader jaotati.
  
  $\frac{14 400}{225} = 64 blocks$
3. Kulu kasvab otsinguraadiuse ruuduga, seega akna laiendamine muutub kiiresti kulukaks: raadius 7 maksab 225 positsiooni, raadius 15 maksab 961, raadius 31 maksab 3969.
  
  $cost \propto (2 R + 1)^{2} : R = 7 \Rightarrow 225, R = 15 \Rightarrow 961, R = 31 \Rightarrow 3969$
4. See ruutsõltuvus ongi põhjus, miks kiired otsingud olemas on. Kolmesammuline otsing võtab proovid üheksast punktist, täpsustab ja kordab — 27 positsiooni 225 asemel.
  
  $three-step search : 3 stages \times 9 points = 27$
5. Kaheksa korda odavam, kuid mitte samaväärne: see laskub kohaliku miinimumi poole ning võib tegelikust parimast kattest mööda minna, kui veapind sisaldab rohkem kui ühte süvendit.
  
  $\frac{225}{27} = 8.3 \times fewer, and it can miss the true minimum$
Vastus

Tööriist näitab, et läbi vaadati 14400 punkti, 225,0 punkti ploki kohta. Selle valiku ees seisab kogu praktiline videokodeerimine: täielik otsing annab optimaalse tulemuse, kuid selle töömaht kasvab võrdeliselt otsinguraadiuse ruuduga. Seepärast kasutavad kõik kodeerijad heuristikat ja lepivad võimalusega, et vahel valitakse kehvem vektor. Eksimuse hinda näitab osaliselt rida Jääkenergia (MSE): halb vektor jätab suurema jäägi, mille kodeerimiseks kulub rohkem andmeid. Kiire liikumisotsing ei ole pelgalt aja säästmiseks tehtud lähendus. See põhineb eeldusel, et ebatäpsete vektorite tõttu lisandub vähem bitte, kui vabanenud ressursiga mujal kokku hoida saab.

$full search is O (R^{2}) per block; fast searches trade optimality for 8 \times$

Allikad (2)

Block matching and motion vectors as the standard uses them: T. Wiegand, G. J. Sullivan, G. Bjontegaard and A. Luthra, "Overview of the H.264/AVC video coding standard." IEEE Transactions on Circuits and Systems for Video Technology 13(7), 560–576, 2003.
The diamond search this tool implements alongside full search: S. Zhu and K.-K. Ma, "A new diamond search algorithm for fast block-matching motion estimation." IEEE Transactions on Image Processing 9(2), 287–290, 2000.

42Mathi meeskond · Uuendatud 2026-05-29

Kontrollitud avaldatud allikate põhjal. Parandused on teretulnud. Toimetamispõhimõtted · Parandused

Kõik Arvutustehnika õppetunnid →

Näiteülesanded

Aeglane panoraam - Aeglane horisontaalne panoraam: jääk on peaaegu null, liikumisvektorid osutavad ühtlaselt paremale
Kiire panoraam - Kiire panoraam: suurem SAD otsingupiiril, kõrge energiaga jäägid servades
Lahknev suum - Sissesuumimise liikumine: vektorid hajuvad keskpunktist, ükski üksik nihkevektor ei sobi
Müraga käeshoitav kaamera - Müraga kaamera: kõrge SAD hoolimata õigetest vektoritest — müra energia domineerib jäägis