Detekce kvality videa přes FFT

29.9.2009 00:58 | Přečteno: 1251× | programování | poslední úprava: 29.9.2009 12:27

Konečně jsem si našel čas si vrátit se k Fourierově transformaci a image processingu. Malý experiment jak "ohodnotit objektivně" kvalitu encodovaného videa.

Smyslem bylo najít nějaký objektivnější způsob jak klasifikovat kvalitu výstupního videa než metoda P-V (podívám-vidím). Abych to nekomplikoval, vymyslel jsem si celkem jednoduchou definici: má minimum artefaktů ("čtverečků"; ty způsobeny kompresí nebo motion compensation v rychle se pohybujících scénách). Příklad (zvětšeno 3x):

K FFT cesta dlouhá

Myslel jsem, že největší problém bude rozpomenout se věci kolem FFT a image processingu (je to už pár let). Jenže než jsem se dostal k FFT, už bylo nezbytné řešit drobnosti:

• zdrojové video nemusí mít 1:1 pixel aspect ratio (šířka pixelu), rescalingem se trochu ovlivní frekvence (lanczos filtr by to měl udělat celkem snesitelně). Výstupní video soubory mají pixel aspect 1:1.
• zdrojové video může být interlacované, deinterlacing taky mírně ovlivní frekvence
• výstupy se časově liší, požadovaný frame z výstupu mencoderu jsem musel hledat ručně (i když rozdíl byl snad jen pár framů), proto ten výslední zázrak negrabuje framy přímo z videa

Pak mě trocha zarazil matplotlib, který -infinity zobrazuje jako bílou, což je mírně matoucí v grayscale (pravý obrázek):

Pravá dolní matice je m3_fft:

>>> import matplotlib.pyplot as plt
>>> import numpy as np
>>> m3 = np.arange(64).reshape((8,8))
>>> print m3
[[ 0  1  2  3  4  5  6  7]
 [ 8  9 10 11 12 13 14 15]
 [16 17 18 19 20 21 22 23]
 [24 25 26 27 28 29 30 31]
 [32 33 34 35 36 37 38 39]
 [40 41 42 43 44 45 46 47]
 [48 49 50 51 52 53 54 55]
 [56 57 58 59 60 61 62 63]]
>>> m3_fft=np.log(abs(np.fft.fft2(m3)))
>>> print m3_fft
[[ 7.60887063  4.42628308  3.81230949  3.54490949  3.4657359   3.54490949
   3.81230949  4.42628308]
 [ 6.50572462        -Inf        -Inf        -Inf        -Inf        -Inf
         -Inf        -Inf]
 [ 5.89175103        -Inf        -Inf        -Inf        -Inf        -Inf
         -Inf        -Inf]
 [ 5.62435104        -Inf        -Inf        -Inf        -Inf        -Inf
         -Inf        -Inf]
 [ 5.54517744        -Inf        -Inf        -Inf        -Inf        -Inf
         -Inf        -Inf]
 [ 5.62435104        -Inf        -Inf        -Inf        -Inf        -Inf
         -Inf        -Inf]
 [ 5.89175103        -Inf        -Inf        -Inf        -Inf        -Inf
         -Inf        -Inf]
 [ 6.50572462        -Inf        -Inf        -Inf        -Inf        -Inf
         -Inf        -Inf]]

Testovací obrázky

Čtyři testovací obrázky jsou z traileru Baader Meinhof Komplex, z rychle pohybující se scény. Zleva doprava, shora dolů: originál, ffmpeg VBR, ffmpeg CBR, mencoder VBR, všechno via x264 @ bitrate 900 kbps (plus nějaké další optiony různě):

Začal jsem rovnou s FFT celého obrázku. I když lepší by to bylo po menších blocích (8x8 nebo 16x16), ale to by zas nebyla taková sranda. Po několika pokusech něco rozumného vykoukat z celého Fourierovho obrazu jsem přešel na různé hrano-detekční filtry (Laplace, Sobel, ...). Laplace nějaký účinek měl, hrany artefaktů najde, i když už artefakty musí být dost viditelné. Viz zoomnutou vlajku v grafu napravo nahoře (FFMpeg CBR):

Porovnání s mencoder VBR:

Zvláštní je, že PSD křivka v případě mencoderu je odlišnější od originálu (v porovnání s rozdílem FFMpeg CBR-originál), opticky encodované video mi přijde spíš opačně. (PSD je jednorozměrné, takže "vidí" jenom vertikální hrany, ale při hledání "čtverečků" to nevadí).

FFMpeg CBR přidal nějaké vyšší frekvence navíc, mencoder VBR naopak vyhladil (u mencoder VBR jsem použil kubickou interpolaci při deinterlacu).

PSD na menších blocích 16x16

Na menších blocích je mnohem lépe vidět výsledek encodování a jejich rozdílů, na tvaru křivky by šla založit kvantifikace "kolik a jakých má artefaktů" asi lépe než se to snažit vytáhnout z FFT obrazu celého obrázku. Následující obrázek porovnává výsek s vlajkou (kde má FFMpeg CBR artefakty) a výsek s vzdáleným davem (vysoké frekvence). I tady je vidět, že u FFMpeg CBR přibyly vyšší frekvence, kdežto mencoder je (zřejmě kubickou interpolací) ořezal:

Kód pro vygenerování předchozího obrázku:

import Image
import matplotlib.pyplot as plt

fig = plt.figure()
ax = fig.add_subplot(111)
samples = [
    ("baader_ffmpeg-cbr-12s-256x256.png", (76,92,92,108)), #blue
    ("baader_ffmpeg-cbr-12s-256x256.png", (32,80,48,96)), #green
    ("baader_ffmpeg-12s-256x256.png", (76,92,92,108)), #red
    ("baader_mencoder-12s-256x256.png", (76,92,92,108)), #cyan
    ("baader_original-12s-256x256.png", (76,92,92,108)), #magenta
]

images = [Image.open(fname).crop(rectangle) for (fname, rectangle) in samples]

for image in images:
    ax.psd(image.getdata(0), NFFT=16, scale_by_freq=True)

leg = ax.legend(('FFMpeg CBR - flag', 'FFMpeg CBR - crowd', 
    'FFMpeg VBR - flag', 'Mencoder pp=ci - flag', 'original'),
    'upper center', shadow=True)
plt.show()

Link na zdroják prvního programu (potřebuje matplotlib, numpy, scipy a python imaging library). Lepší je zkoušet obrázky velikosti zaokrouhlenou na nějakou mocninu dvojky.

Je to víc hříčka než než něco co by bylo dotažené do konce (alespoň s tím byla sranda).

       

Komentáře

[gogloid]

Hezký a zajímavý článek, ale toto opravdu je zlý: Zmyslem a znesitelné

[limit_false]

Spíš jsem čekal že někomu bude vadit, že PSD grafy nejsou škálovány na správnou frekvenci (kvůli logaritmickému měřítku na ose y jenom dojde k lineárnímu posunu, tvar je zachován, takže to nějak extrémně nevadí; se správnou frekvencí se pak nevešly popisky na osu x).

Nebo že v prvním kousku kódu zůstaly rovnítka místo většítek (zdejší redakční systém mění entity gt a lt při každém náhledu na většítka/menšítka v textovém okně, takže si to vždy nechávám na finální post a nějak se na to zapomělo).

Holt v jednu ráno po 3 hodinách psaní jsem rád že těch chyb je tam tak málo A nakonec něco z xkcd.

BTW dá se blog editovat ex post? Nikde jsem na to nenašel odkaz/tlačítko, ale zdá se mi že některým lidem se to povedlo.

[Semo]

V pravom stlpci hned prvy odkaz (v mommente, ked mas zobrazeny blog).

[limit_false]

Dík, právě jsem to před chvílí našel a chybky opravil.

[Jim]

V tom případě doufám, že "Tomášovi poznatky" jsou takto napsané opravdu z nějakého rozumného důvodu ....

[petr_p]

Možná jsem vás nepochopil, ale jaký smysl má hledat hrany v překódovaném obrazu (hrana může být už v originálu nebo naopak překódovaný obrázek může být zbytečně rozmazaný)?

Neměl by se nejprve udělat (absolutní) rozdíl překódovaného a původního obrázku a teprve až pak se ptát, jak budeme rozdíl „objektivně“ algoritmicky hodnotit?

[limit_false]

Neměl by se nejprve udělat (absolutní) rozdíl překódovaného a původního obrázku a teprve až pak se ptát, jak budeme rozdíl „objektivně“ algoritmicky hodnotit?

Ano, presne tak byla myslena jedna varianta (odcitaly by se energie frekvenci z PSD).

Druha varianta by byla metrika nad jednim videem (encodovanym), treba zintegrovat energii vybranych vysokych frekvenci (nebo zintegrovat do vektoru, ktery je indexovan frekvencema). Ta by pak mela vyznam jenom v porovani s jinym encodovanym videem z tehoz zdroje, nebo se zdrojem samotnym.

[limit_false]

Tady je vysledek te druhe varianty (integrace pres energie vysokych frekvenci v subblocich 16x16):

PNG

SVG

Zdrojak

[Grunt]

Smyslem bylo najít nějaký objektivnější způsob jak klasifikovat kvalitu výstupního videa než metoda P-V (podívám-vidím).

Nechci do toho kecat, ale už nějakou dobu se používá metoda PSNR. A i nad ní metoda P-V(i když asi v různých pohledech) naprosto vládne.

Abych to nekomplikoval, vymyslel jsem si celkem jednoduchou definici: má minimum artefaktů ("čtverečků"; ty způsobeny kompresí nebo motion compensation v rychle se pohybujících scénách).

To bych ovšem v současné době nepovažoval příliš za směrodatné. Až se dovalím domů, snad nezapomenu se trošku o tom rozepsat, jelikož sám v podobné oblasti něco málo bádám.

Detekce kvality videa

Prrr, už zas? Chtělo by to konečně vymyslet nějaký vhodnější termín.

[limit_false]

Jj, jsem taky psal, ze jde o "maly experiment". Image processing neni tak uplne muj obor, jenom o tom neco vim a chtel jsem si s tim po dlouhe dobe pohrat ("zaprogramovat si pro radost" )

BTW, nejsou kvantizacni matice JPEG a komprese mp3 taky zalozeny na empirii typu P-V? (nezli na "tvrdem matematickem modelu")

Jinak rozepsani podporuji, zajimalo by me to.

[Grunt]

Jinak rozepsani podporuji, zajimalo by me to.

Tak teda, proč zrovna "čtverečky" (blokové artefakty jak je s oblibou profesionálové nazývají) nepovažuji za směrodatné? Je to přežitek z dob JPEGu. Já bych ten blokový artefakt definoval jako přechod na hraně sítě sekvenčního zpracování obrazu tak velký, že je lidské oko schopno jej rozpoznat. A ty se nacházejí téměř všude, jen je lidské oko při zobrazení 1:1(bez zoomu) není schopno rozpoznat, ale vnímá je jako šum(a nebo hranu nějakého objektu), což ovšem vůbec neznamená, že tam nejsou(většinou viditelné až po zvětšení). Ty viditelné vznikají většinou jako důsledek absence dostatečného počtu AC koeficientů. A to se přihodí(většinou) až u velmi vysokých kompresních poměrů. Navíc vzhledem k existenci in-loop deblocking filteringu(u jiných formátů nepovinný, ovšem u H.264 už povinného – tím se sice hrany, které do výsledku nepatří docela dobře maskují, ovšem za cenu ještě nevzhlednějších fleků) a vzhledem k tomu, že to ze hry vyřazuje formáty které blokové artefakty nevytvářejí(Dirac,Snow,…koneckonců i to H.264 už jen ve velmi omezené míře) mi prostě hledání artefaktů nepřijde moc košer. Proč ne prostá frekvenční analýza? Už jen z toho důvodu, že právě ty přechody a kvantizační šum zavádějí další vysokofrekvenční složky. Komprese není jen prosté ořezání vysokých frekvencí. A navíc není moc vypovídající(ořezání vysokých frekvencí s malou amplitudou namodulovaných na nějakou sinusovku a úplně těch stejných z okolí hrany je přece jen docela rozdíl o kterém frekvenční analýza neřekne ani ň). S PSNR bych to viděl také tak nějak. A co mě k tomu všemu vede?

No to snad dopíšu až zase budu mít dvě oči.

Image processing neni tak uplne muj obor

A čí jo?

BTW, nejsou kvantizacni matice JPEG a komprese mp3 taky zalozeny na empirii typu P-V? (nezli na "tvrdem matematickem modelu")

No, jak se to vezme. Původní kvantizační matice u standardu (jak se dělali filtrovací banky u MPEG1 netuším) prej dělalo samotné JPEG tak že skenovalo běžné materiály (fotografie, medicínské podklady,…), dělalo právě frekvenční analýzu a výsledky se nějak zprůměrovaly. Tak se prej mimo jiné přišlo na to, že lidský zrak je více citlivý na horizontální frekvence než na vertikální. Do dnešní podoby se dostaly opravdu metodou pokus omyl.

[limit_false]

Dík za info.

Metoda popsaná v předchozím komentáři mi dává celkem rozumné výsledky (i.e. odpovídá celkem tomu co na videu vidím), ješte to vyzkouším zintegrovat nejen na jednom framu, ale na několik tisíc framech (delší úsek videa).

Neznáte náhodou knihu Image Processing, Analysis, and Machine Vision? Údajně je dobrá, uvažoval jsem nad tím, že bych si ji koupil.

A čí jo?

No určitě existuje pár lidí designujících třeba různe medicínske mašiny

 

 

 

[Grunt]

zintegrovat nejen na jednom framu, ale na několik tisíc framech (delší úsek videa).

Pak doporučuji očkem pokukovat po FFTW. Je to fakt špica.(O čemž svědčí i těch pár matematických cen co už získali)

Neznáte

Co to?

Neznáte náhodou knihu Image Processing, Analysis, and Machine Vision? Údajně je dobrá, uvažoval jsem nad tím, že bych si ji koupil.

Já už si pomalu začínám psát seznam. No bohužel trošičku odrazuje cena(teda na to, že je to Taschenbuch), ale co především, tak volný čas. Už tak tu mám pár knížek které jsou ve stavu rozečtené a stejně na ně nemám čas a dokud alespoň ty nedoklepu, tak nebudu nic začínat. Kdyby se tak dal koupit volný čas. No určitě mnohokrát děkuju za zajímavý tip pod stromeček. Slibuju, že až až ten čas bude(a snad dřív než v důchodě), tak bude první které na seznamu zpracuju.

No určitě existuje pár lidí designujících třeba různe medicínske mašiny

A tam bych asi také při zkoumání video/image processingu začal. Já např. nikdy netušil, že ta skleněná svíticí pixle se zmenšujícími se písmenky ve skutečnosti (přeneseně samozřejmě) zkoumá rozlišení oka jedince.

[Grunt]

psát seznam

Psát seznam a na toto zapomenout. No fuj.

[limit_false]

Pak doporučuji očkem pokukovat po FFTW. Je to fakt špica.(O čemž svědčí i těch pár matematických cen co už získali)

Jj, FFTW znam, i scipy (nedavno) pouzival FFTW. Prave jsem si napsal udelatko pro framegrabber + integraci pres framy z nejakeho casoveho useku videa a jiz na nekolikasekundovym useku na 480*252 videu je to k*va pomale. Nicmene vystupy z udelatka celkem odpovidaji tomu co vidim (jeste jsem to neporovnaval "rucno-ocne" frame po framu):

Pohybliva scena, 7-13 s (PNG)
Mix scen, pomale i pohyblive, 1-13 s (PNG)

Nad iterpretaci se budu muset trocha zamyslet a podivat se na jednotlive framy, ale je videt ze ffmpeg s pouzitymi parametry rozhodne pridava sum a hrany, mencoder spis smeruje k blur-u (vsechen encoding zatim je single-pass, zkusim to i s 2-pass).

[Grunt]

A co mě k tomu všemu vede?

Jednoho dne jsem se vzbudil s otázkou: Co je efektivnější, zmenšit rozlišení nebo zvětšit kompresní poměr? No to znělo jako výzva na test. Použil jsem tento vzorek(uvádím ho záměrně, třeba se k němu ještě jednou vrátím až budu povídat o drzosti výrobců fotoaparátů). Toto jsem vyhrabal v historii:

$ export W=1440
$ export H=900
$ touch compressed_100.jpg; c=280;for ((b=100;`ls -sk compressed_100.jpg | cut -d' ' -f1`>$c;b--));do convert original.jpg -quality $b% compressed_100.jpg && echo "100%:$b"; done; b=9;b=$((b+1)); for ((a=99;a>0;a--)); do convert -resize $a% original.jpg -quality $b compressed_$a.jpg && echo "$a%: $b,`ls -sk compressed_$a.jpg | cut -d' ' -f1`kB";if [ `ls -sk compressed_$a.jpg | cut -d' ' -f1` -lt $c ];then for((;`ls -sk compressed_$a.jpg | cut -d' ' -f1`<=$c && $b != 100; b++));do convert -resize $a% original.jpg -quality $b compressed_$a.jpg && echo "$a%: $b,`ls -sk compressed_$a.jpg | cut -d' ' -f1`kB"; done ;if [ $b -ne 100 ]; then b=$(($b-2));convert -resize $a% original.jpg -quality $b compressed_$a.jpg && echo "$a%: $b,`ls -sk compressed_$a.jpg | cut -d' ' -f1`kB - final";fi;fi; done
$ touch testik.yuv
$ for((a=1;a<100;a++));do convert -resize 3072x2304\! -crop $Wx$H+0+0 -gravity Center compressed_$a.jpg -quality 05 temp.png && composite label:"Scale: $a%" -gravity SouthEast temp.png temp.yuv && echo temp.yuv >> testik.yuv && echo $a;done && for((a=101;a>0;a--));do convert -resize 3072x2304\! compressed_$a.jpg -quality 05 temp.png && composite label:"Scale: $a%" -gravity SouthEast temp.png temp.yuv && echo temp.yuv >> testik.yuv && echo $a;done
$ mplayer testik.yuv -demuxer rawvideo -rawvideo fps=25:w=$W:h=$H:i420 -loop 0 -fs

(Psal jsem to přímo v editoru a ještě jsem to ke všemu netestoval. Snad to bude fungovat. No hlavní je pokud bude pochopeno co vlastně vůbec básník chtěl říct.)

Já jsem si z toho ještě vykreslil PSNR graf a neočekávaně dostal úplný nesmysl. To mě vede k tomu, že PSNR prostě ne(je to matematické čudo, které nedostatečně zohledňuje vlastnosti lidského zraku). Stejně tak se u toho dobře pozoruje u jakého měřítka se začínají teprve objevovat právě ty artefakty a jak se to vlastně po kompresi celé chová. Doporučuji si pár takových testů provést(nejen s úměrností QP, měřítko). Pak nezbude nic jiného než na otázku jak objektivně vyzkoumat tu kvalitu vypustit: Ufff…

(No na druhou stranu je to určitě o něco lepší než samotné PSNR)