Сжатие изображений

Ñîâðåìåííàÿ òåîðèÿ èíôîðìàöèè Ëåêöèÿ 8. Ñæàòèå èçîáðàæåíèé. ×àñòü 1. Evgeny Belyaev (ITMO University) Modern Information Theory 10 íîÿáðÿ 2021 ã. 1 / 64 Ñîäåðæàíèå ëåêöèè 1 Öèôðî-àíàëîãîâîå ïðåîáðàçîâàíèå èçîáðàæåíèé. 2 Îñíîâíûå ïðèíöèïû ñæàòèÿ èçîáðàæåíèé. 3 Ïðåîáðàçîâàíèå öâåòîâîãî ïðîñòðàíñòâà. 4 Êîäèðîâàíèå ñ ïðåäñêàçàíèåì. 5 Êîäèðîâàíèå ñ ïðåîáðàçîâàíèåì. 6 Àëãîðèòì JPEG Evgeny Belyaev (ITMO University) Modern Information Theory 10 íîÿáðÿ 2021 ã. 2 / 64 Öèôðî-àíàëîãîâîå ïðåîáðàçîâàíèå èçîáðàæåíèé Àíàëîãîâûå è öèôðîâûå ñèãíàëû Ïîä ñèãíàëîì ïîíèìàåòñÿ ôèçè÷åñêèé ïðîöåññ (íàïðèìåð, èçìåíÿþùååñÿ âî âðåìåíè íàïðÿæåíèå), îòîáðàæàþùèé íåêîòîðóþ èíôîðìàöèþ èëè ñîîáùåíèå. Àíàëîãîâûå ñèãíàëû - ýòî íåïðåðûâíûå ôóíêöèè íåïðåðûâíîãî àðãóìåíòà, íàïðèìåð òàêîãî êàê âðåìÿ è/èëè ïðîñòðàíñòâî. Äèñêðåòíûå ñèãíàëû ìîãóò áûòü äèñêðåòíûìè ïî ìíîæåñòâó çíà÷åíèé ôóíêöèè èëè ïî ìíîæåñòâó çíà÷åíèé àðãóìåíòà. Íàïðèìåð, åñëè çíà÷åíèÿ àíàëîãîâîãî ñèãíàëà âçÿòû ÷åðåç îïðåäåëåííûå èíòåðâàëû âðåìåíè, òî òàêîé ñèãíàë íàçûâàåòñÿ äèñêðåòíûì ïî âðåìåíè; Åñëè ó äèñêðåòèçîâàííîãî ïî âðåìåíè ñèãíàëà îòñ÷åòû òàêæå ïðèíèìàþò çíà÷åíèÿ èç íåêîòîðîãî äèñêðåòíîãî ìíîæåñòâà çíà÷åíèé, òî òàêîé ñèãíàë íàçûâàåòñÿ öèôðîâûì. Evgeny Belyaev (ITMO University) Modern Information Theory 10 íîÿáðÿ 2021 ã. 3 / 64 Öèôðî-àíàëîãîâîå ïðåîáðàçîâàíèå èçîáðàæåíèé Äèñêðåòèçàöèÿ ïî âðåìåíè è ïî óðîâíþ Äëÿ òîãî, ÷òîáû ïîìåñòèòü àíàëîãîâûé (íåïðåðûâíûé ñèãíàë) â öèôðîâîå óñòðîéñòâî íåîáõîäèìî ïðåîáðàçîâàòü åãî â öèôðîâîé ñèãíàë. Àíàëîãî-öèôðîâîå ïðåîáðàçîâàíèå (ÖÀÏ) âêëþ÷àåò â ñåáÿ äâå îñíîâíûå îïåðàöèè: Îïåðàöèÿ äèñêðåòèçàöèè èëè âçÿòèÿ îòñ÷åòîâ íåïðåðûâíîãî ñèãíàëà (êâàíòîâàíèå ïî âðåìåíè); Îïåðàöèÿ êâàíòîâàíèÿ íåïðåðûâíîãî ñèãíàëà ïî óðîâíþ. Evgeny Belyaev (ITMO University) Modern Information Theory 10 íîÿáðÿ 2021 ã. 4 / 64 Öèôðî-àíàëîãîâîå ïðåîáðàçîâàíèå èçîáðàæåíèé Âûáîð ÷àñòîòû äèñêðåòèçàöèè ïî âðåìåíè 1 sin(6πt) * * 0.8 0.6 0.4 0.2 * * * * * t −0.2 −0.4 −0.6 −0.8 * −1 0.2 * sin(2πt) 0.4 0.6 0.8 1 1.2 1.4 1.6 1.8 2 Êàê ïðàâèëüíî âûáðàòü èíòåðâàë äèñêðåòèçàöèè ïî âðåìåíè? Evgeny Belyaev (ITMO University) Modern Information Theory 10 íîÿáðÿ 2021 ã. 5 / 64 Öèôðî-àíàëîãîâîå ïðåîáðàçîâàíèå èçîáðàæåíèé Ñïåêòð íåïðåðûâíîãî ñèãíàëà Ïóñòü x(t)  íåïðåðûâíàÿ îäíîìåðíàÿ ôóíêöèÿ. Ïðåîáðàçîâàíèå Ôóðüå (ñïåêòð) äëÿ x(t) îïðåäåëÿåòñÿ ñëåäóþùèì îáðàçîì: Z ∞ X (f ) = x(t)e −jωt dt, −∞ ãäå ω = 2πf  êðóãîâàÿ ÷àñòîòà. Ýòà êîìïëåêñíàÿ ôóíêöèÿ ìîæåò áûòü ïðåäñòàâëåíà â âèäå X (f ) = A(f )e jϕ(f ) , ãäå |A(f )| íàçûâàåòñÿ àìïëèòóäíûì ñïåêòðîì ñèãíàëà èëè àìïëèòóäíî-÷àñòîòíîé õàðàêòåðèñòèêîé ñèãíàëà, à ϕ(f ) íàçûâàåòñÿ ôàçîâûì ñïåêòðîì èëè ôàçîâî-÷àñòîòíîé õàðàêòåðèñòèêîé. Âîññòàíîâèòü ñèãíàë ïî åãî ñïåêòðó ìîæíî ïðè ïîìîùè îáðàòíîãî ïðåîáðàçîâàíèÿ Ôóðüå: Z ∞ x(t) = X (f )e −jωt df . −∞ Evgeny Belyaev (ITMO University) Modern Information Theory 10 íîÿáðÿ 2021 ã. 6 / 64 Öèôðî-àíàëîãîâîå ïðåîáðàçîâàíèå èçîáðàæåíèé Òåîðåìà Êîòåëüíèêîâà-Íàéêâèñòà x(t) è å¼ ñïåêòð èìååò âèä:  Z ∞  X (f ) = x(t)e −j 2πft dt, åñëè |f | ≤ f0 . −∞  X (f ) = 0, åñëè |f | > f0 . Ïóñòü çàäàíà ôóíêöèÿ Òîãäà ýòà ôóíêöèÿ ïîëíîñòüþ îïðåäåëÿåòñÿ ñâîèìè ìãíîâåííûìè 1 çíà÷åíèÿìè â ìîìåíòû, îòñòîÿùèå äðóã îò äðóãà íà ñåêóíä: 2f0 x(t) = X  k  sinπ(2f0 t − k) x . 2f0 π(2f0 t − k) k Evgeny Belyaev (ITMO University) Modern Information Theory 10 íîÿáðÿ 2021 ã. 7 / 64 Öèôðî-àíàëîãîâîå ïðåîáðàçîâàíèå èçîáðàæåíèé Ïðîñòðàíñòâåííûé ñïåêòð èçîáðàæåíèÿ Ñïåêòð L(ωx , ωy ) l(x, y ), îïðåäåëÿåòñÿ ñëåäóþùèì îáðàçîì: èçîáðàæåíèÿ, îïèñûâàåìîãî ôóíêöèåé ÿðêîñòè Z ∞ Z ∞ L(ωx , ωy ) = −∞ ãäå ωx è ωy l(x, y )e −j(ωx x+ωy y ) dxdy , −∞  êðóãîâûå ïðîñòðàíñòâåííûå ÷àñòîòû ñïåêòðà â íàïðàâëåíèè îñåé x è y. Ñïåêòðàëüíàÿ èíòåíñèâíîñòü èçîáðàæåíèÿ: S(ωx , ωy ) = ãäå x0 y0 1 x0 y0 |L(ωx , ωy )|2 ,  ïëîùàäü ïðÿìîóãîëüíèêà, â êîòîðîå âïèñàíî èçîáðàæåíèå. Âîññòàíîâèòü ôóíêöèþ ÿðêîñòè ïî åãî ñïåêòðó ìîæíî ïðè ïîìîùè îáðàòíîãî äâóìåðíîãî ïðåîáðàçîâàíèÿ Ôóðüå: Z ∞ Z ∞ l(x, y ) = −∞ Evgeny Belyaev (ITMO University) L(ωx , ωy )e j(ωx x+ωy y ) dωx dωy . −∞ Modern Information Theory 10 íîÿáðÿ 2021 ã. 8 / 64 Öèôðî-àíàëîãîâîå ïðåîáðàçîâàíèå èçîáðàæåíèé Ïðîñòðàíñòâåííûé ñïåêòð èçîáðàæåíèÿ Ðåàëüíûå èçîáðàæåíèÿ â îñíîâíîì ñîñòîÿò èç âåðòèêàëüíûõ èëè ãîðèçîíòàëüíûõ îáúåêòîâ. Evgeny Belyaev (ITMO University) Modern Information Theory 10 íîÿáðÿ 2021 ã. 9 / 64 Öèôðî-àíàëîãîâîå ïðåîáðàçîâàíèå èçîáðàæåíèé Òåîðåìà Êîòåëüíèêîâà-Íàéêâèñòà äëÿ èçîáðàæåíèÿ Ïóñòü çàäàíà ôóíêöèÿ ÿðêîñòè èçîáðàæåíèÿ l(x, y ) ñî ñïåêòðîì  Z ∞Z ∞  L(ω , ω ) = l(x, y )e −j(2πfx x+2πfy y ) dxdy , |fx | ≤ fx0 , |fy | ≤ fy0 . x y −∞ −∞  L(ωx , ωy ) = 0, èíà÷å. Òîãäà ýòà ôóíêöèÿ ïîëíîñòüþ îïðåäåëÿåòñÿ ñâîèìè ìãíîâåííûìè çíà÷åíèÿìè â ìîìåíòû, îòñòîÿùèå äðóã îò äðóãà íà èíòåðâàëû 1 1 ∆x = 0 è ∆y = 0 â íàïðàâëåíèè îñåé x è y : 2fx 2fy l(x, y ) = XX n L(n∆x , k∆y ) k Evgeny Belyaev (ITMO University) sin2πfx0 (x − n∆x ) sin2πfy0 (y − k∆y ) · 2πfx0 (x − n∆x ) 2πfy0 (y − k∆y ) Modern Information Theory 10 íîÿáðÿ 2021 ã. 10 / 64 Öèôðî-àíàëîãîâîå ïðåîáðàçîâàíèå èçîáðàæåíèé Ïðèìåð íàðóøåíèÿ òåîðåìû (aliasing) Evgeny Belyaev (ITMO University) Modern Information Theory 10 íîÿáðÿ 2021 ã. 11 / 64 Öèôðî-àíàëîãîâîå ïðåîáðàçîâàíèå èçîáðàæåíèé Ðàâíîìåðíîå ñêàëÿðíîå êâàíòîâàíèå Íàèáîëåå ïðîñòîé ñïîñîá àïïðîêñèìàöèè ïîñëåäîâàòåëüíîñòè ñîîáùåíèé x = {x1 , ..., xn } ìîæåò áûòü ðåàëèçîâàí ïðè ïîìîùè ïðîöåäóðû ðàâíîìåðíîãî ñêàëÿðíîãî êâàíòîâàíèÿ, êîòîðàÿ êàæäîìó ñèìâîëó xi ñîïîñòàâëÿåò íîìåð êâàíòà  |xi | + ∆/2 zi = sign(xi ) , ∆  ãäå ∆ - øàã êâàíòîâàíèÿ, bxc - îçíà÷àåò îïåðàöèþ îêðóãëåíèÿ äî áëèæàéøåãî öåëîãî, íå ïðåâûøàþùåãî èíà÷å x , sign(xi ) = −1, sign(xi ) = 1. Ïðè ýòîì, àïïðîêñèìèðóþùåå ìíîæåñòâî y = {y1 , ..., yn } åñëè xi < 0, âû÷èñëÿåòñÿ êàê yi = ∆ · zi . Evgeny Belyaev (ITMO University) Modern Information Theory 10 íîÿáðÿ 2021 ã. 12 / 64 Öèôðî-àíàëîãîâîå ïðåîáðàçîâàíèå èçîáðàæåíèé Ðàâíîìåðíîå ñêàëÿðíîå êâàíòîâàíèå yi xi ∆ Z Ñðåäíÿÿ îøèáêà êâàíòîâàíèÿ ∞ ε= (xi − yi )2 f (xi ) ≈ −∞ Evgeny Belyaev (ITMO University) Modern Information Theory ∆2 12 . 10 íîÿáðÿ 2021 ã. 13 / 64 Öèôðî-àíàëîãîâîå ïðåîáðàçîâàíèå èçîáðàæåíèé Öèôðî-àíàëîãîâàÿ èíòåãðàëüíàÿ ìèêðîñõåìà Ñâåòî÷óâñòâèòåëüíàÿ ìàòðèöà  öèôðî-àíàëîãîâàÿ èíòåãðàëüíàÿ ìèêðîñõåìà, ñîñòîÿùàÿ èç ôîòîäèîäîâ (ñâåòî÷óâñòâèòåëüíûõ ýëåìåíòîâ). Evgeny Belyaev (ITMO University) Modern Information Theory 10 íîÿáðÿ 2021 ã. 14 / 64 Öèôðî-àíàëîãîâîå ïðåîáðàçîâàíèå èçîáðàæåíèé Öèôðîâîå ïðåäñòàâëåíèå èçîáðàæåíèé â ôîðìàòå RGB24 (B,R,G) (B,R,G) (B,R,G) (B,R,G) (B,R,G) (B,R,G) ... (B,R,G) (B,R,G) (B,R,G) (B,R,G) (B,R,G) (B,R,G) (B,R,G) (B,R,G) ... (B,R,G) (B,R,G) (B,R,G) (B,R,G) (B,R,G) (B,R,G) (B,R,G) (B,R,G) ... (B,R,G) (B,R,G) (B,R,G) (B,R,G) (B,R,G) (B,R,G) (B,R,G) (B,R,G) ... (B,R,G) (B,R,G) ... ... ... ... ... ... (B,R,G) (B,R,G) (B,R,G) (B,R,G) (B,R,G) (B,R,G) R, G , B ∈ [0, ..., 255] or Evgeny Belyaev (ITMO University) 24 áèò ... ... ... (B,R,G) (B,R,G) íà ïèêñåëü. Modern Information Theory 10 íîÿáðÿ 2021 ã. 15 / 64 Îñíîâíûå ïðèíöèïû ñæàòèÿ èçîáðàæåíèé Èçáûòî÷íîñòü â ïðåäñòàâëåíèè èçîáðàæåíèé Êîäîâàÿ èçáûòî÷íîñòü âîçíèêàêåò èç-çà èñïîëüçîâàíèÿ êîäîâ, êîòîðûå íå ìèíèìèçèðóþò ñðåäíþþ äëèíó êîäîâîãî ñëîâà (ðàâíîìåðíûé êîä âìåñòî Õàôôìàíà è ò.ä.). Ìåæïèêñåëüíàÿ èçáûòî÷íîñòü ñâÿçàíà ñ òåì, ÷òî ïèêñåëü èëè ãðóïïû ïèêñåëåé ïîõîæè äðóã íà äðóãà. I Ñòàòèñòè÷åñêàÿ çàâèñèìîñòü öâåòîâûõ êîìïîíåíò (R, G è B). I Ëîêàëüíàÿ ñõîæåñòü ñîñåäíèõ ïèêñåëåé (local similarity). I Ñõîæåñòü óäàë¼ííûõ ãðóïï ïèêñåëåé (non-local similarity). Ïñèõîâèçóàëüíàÿ èçáûòî÷íîñòü çðèòåëüíàÿ ñèñòåìà ÷åëîâåêà èìååò ðàçíóþ ÷óâñòâèòåëüíîñòü ê âèçóàëüíîé èíôîðìàöèè (ðàçíîå âîñïðèÿòèå âåðòèêàëüíûõ, ãîðèçîíòàëüíûõ è äèàãîíàëüíûõ ëèíèé, ïðèîðèòåò îäíèõ ó÷àñòêîâ (ëèö) èçîáðàæåíèÿ íàä äðóãèìè. Ìàøèííàÿ èçáûòî÷íîñòü  àíàëîãè÷íî, åñëè ïðåäïîëàãàåòñÿ, ÷òî èçîáðàæåíèå ïåðåäà¼òñÿ äëÿ ìàøèííîé îáðàáîòêè, à íå äëÿ ÷åëîâåêà. Evgeny Belyaev (ITMO University) Modern Information Theory 10 íîÿáðÿ 2021 ã. 16 / 64 Îñíîâíûå ïðèíöèïû ñæàòèÿ èçîáðàæåíèé Ëîêàëüíàÿ è íå ëîêàëüíàÿ ñõîæåñòü ñîñåäíèõ ïèêñåëåé γ(∆n) = A(∆n) , A(0) A(∆n) = 1 N−X 1−∆.n N − ∆n f (x)f (x + ∆n). x=0 Ðèñ.: a) Èçîáðàæåíèå, b) Ãèñòîãðàììà c) Àâòîêîððåëÿöèÿ äëÿ îäíîé ñòðîêè 1 1 R.Gonzalez, R.Woods, Digital Image Processing, 2001. Evgeny Belyaev (ITMO University) Modern Information Theory 10 íîÿáðÿ 2021 ã. 17 / 64 Îñíîâíûå ïðèíöèïû ñæàòèÿ èçîáðàæåíèé Ñæàòèå áèíàðíûõ èçîáðàæåíèé 1 1024×343 ìîíîõðîìíîå èçîáðàæåíèå ïðåîáðàçóåòñÿ â áèíàðíîå2 ; 2 Êàæäàÿ ëèíèÿ ïðåäñòâëÿåòñÿ ïàðàìè wi (gi , wi ), ãäå gi  çíà÷åíèå è  êîëè÷åñòâî ïîâòîðåíèé (äëèíà ñåðèè). 3 Äëÿ ëèíèè 100 äîñòàòî÷íî 88 äëÿ ïðåäñòàâëåíèÿ ñòðîêè èç 1024 çíà÷åíèé. 4 Êàæäàÿ ñåðèÿ ïðåäñòâëÿåòñÿ 11 áèòàìè, âñåãî êîäèðóåòñÿ 1266 ñåðèé. 5 2 CR = 1024·343·1 1266·11 = 2.63 R.Gonzalez, R.Woods, Digital Image Processing, 2001. Evgeny Belyaev (ITMO University) Modern Information Theory 10 íîÿáðÿ 2021 ã. 18 / 64 Îñíîâíûå ïðèíöèïû ñæàòèÿ èçîáðàæåíèé Thatcher eect Evgeny Belyaev (ITMO University) Modern Information Theory 10 íîÿáðÿ 2021 ã. 19 / 64 Îñíîâíûå ïðèíöèïû ñæàòèÿ èçîáðàæåíèé Thatcher eect Evgeny Belyaev (ITMO University) Modern Information Theory 10 íîÿáðÿ 2021 ã. 20 / 64 Îñíîâíûå ïðèíöèïû ñæàòèÿ èçîáðàæåíèé 3 Region-of-interest coding Ðèñ.: a) JPEG2000 b) JPEG2000+ROI 3 A. Nguyen et. all, Gaze Tracking for Region of Interest Coding in JPEG2000, 2005. Evgeny Belyaev (ITMO University) Modern Information Theory 10 íîÿáðÿ 2021 ã. 21 / 64 Îñíîâíûå ïðèíöèïû ñæàòèÿ èçîáðàæåíèé Îöåíêà êà÷åñòâà èçîáðàæåíèé Èñïîëüçóþòñÿ îáúåêòèâíûå è ñóáúåêòèâíûå îöåíêè êà÷åñòâà èçîáðàæåíèé. Îáúåêòèâíûå ìåòðèêè (MSE, PSNR) I Ñðåäíåêâàäðàòè÷åñêàÿ îøèáêà (MSE). MSE = 1 MN M− X1 N− X1 [f (x, y ) − fˆ(x, y )]2 . x=0 y =0 I Ïèêîâîå îòíîøåíèå ñèãíàëà ê øóìó (Peak signal-to-noise ratio, PSNR). PSNR = 10 lg |fmax (x, y )|2 , MSE ãäå fmax (x, y )  ìàêñèìàëüíî âîçìîæíîå çíà÷åíèå ÿðêîñòè. Äëÿ 8-áèòíîãî èçîáðàæåíèÿ fmax (x, y ) Evgeny Belyaev (ITMO University) = 255. Modern Information Theory 10 íîÿáðÿ 2021 ã. 22 / 64 Îñíîâíûå ïðèíöèïû ñæàòèÿ èçîáðàæåíèé Ñóáüåêòèâíàÿ îöåíêà êà÷åñòâà èçîáðàæåíèé Âèçóàëüíîå ñðàâíåíèå äâóõ èçîáðàæåíèé: {−3, −2, −1, 0, 1, 2, 3} = {much worse, worse, slightly worse, the same, slightly better, better, much better}; Îöåíêà îäíîãî èçîáðàæåíèÿ ïî øêàëå: 4 4 Methodology for the Subjective Assessment of the Quality of Television Pictures, ITU-R Rec.BT.500-13, 2012 Evgeny Belyaev (ITMO University) Modern Information Theory 10 íîÿáðÿ 2021 ã. 23 / 64 Îñíîâíûå ïðèíöèïû ñæàòèÿ èçîáðàæåíèé Ôóíêöèÿ ñêîðîñòü-èñêàæåíèå Evgeny Belyaev (ITMO University) Modern Information Theory 10 íîÿáðÿ 2021 ã. 24 / 64 Îñíîâíûå ïðèíöèïû ñæàòèÿ èçîáðàæåíèé Îáùàÿ ñõåìà ñæàòèÿ èçîáðàæåíèé Encoder Rate controller Compression ratio Encoding parameters Image Interpixel redundancy removal Quantization Lossless symbol (entropy) encoding Image Image reconstruction Inverse Quantization Lossless symbol (entropy) decoding Bit stream Channel encoder,…, Channel, …, Channel decoder Decoder Evgeny Belyaev (ITMO University) Modern Information Theory 10 íîÿáðÿ 2021 ã. 25 / 64 Îñíîâíûå ïðèíöèïû ñæàòèÿ èçîáðàæåíèé Îáùàÿ ñõåìà ñæàòèÿ èçîáðàæåíèé Óñòðàíåíèå èçáûòî÷íîñòè, ñâÿçàííîé ñî ñõîæåñòüþ ïèêñåëåé: I Ïðåîáðàçîâàíèå öâåòîâîãî ïðîñòðàíñòâà; I Êîäèðîâàíèå ñ ïðåäñêàçàíèåì; I Êîäèðîâàíèå ñ ïðåîáðàçîâàíèåì. Êâàíòîâàíèå (ïðè ñæàòèè ñ ïîòåðÿìè); Àäàïòèâíîå êîäèðîâàíèå ïîëó÷åííûõ äàííûõ: I Êîäèðîâàíèå äëèí ñåðèé; I Ïîáóêâåííîå êîäèðîâàíèå (Õàôôìàí); I Êîíòåêñòíîå àäàïòèâíîå àðèôìåòè÷åñêîå êîäèðîâàíèå. Evgeny Belyaev (ITMO University) Modern Information Theory 10 íîÿáðÿ 2021 ã. 26 / 64 Ïðåîáðàçîâàíèå öâåòîâîãî ïðîñòðàíñòâà Ôîðìàò YCbCr Íàèáîëåå ÷àñòî èñïîëüçóåòñÿ ïðåîáðàçîâàíèå èç ôîðìàòà RGB24 â ôîðìàò YCbCr 4:2:0: Ïðÿìîå ïðåîáðàçîâàíèå:   Y = 0.299 · R + 0.587 · G + 0.114 · B, Cb = (B − Y ) · 0.5643 + 128,  Cr = (R − Y ) · 0.7132 + 128. Îáðàòíîå ïðåîáðàçîâàíèå:   G = Y − 0.714 · (Cr − 128) − 0.334 · (Cb − 128), R = Y + 1.402 · (Cr − 128),  B = Y + 1.772 · (Cb − 128). Evgeny Belyaev (ITMO University) Modern Information Theory 10 íîÿáðÿ 2021 ã. 27 / 64 Ïðåîáðàçîâàíèå öâåòîâîãî ïðîñòðàíñòâà Ïðèìåð Original Image Original image Evgeny Belyaev (ITMO University) R G Luma (Y) Modern Information Theory B Chroma (Cb, Cr) 10 íîÿáðÿ 2021 ã. 28 / 64 Ïðåîáðàçîâàíèå öâåòîâîãî ïðîñòðàíñòâà Äåöèìàöèÿ öâåòîðàçíîñòíûõ êîìïîíåíò Cb è Cr (Y1 , U 1 , V1 ) (Y3 , U 3 , V3 )  U= (Y2 , U 2 , V2 ) (Y1 , U , V ) (Y2 , U , V ) (Y4 , U 4 , V4 ) (Y3 , U , V ) (Y4 , U , V ) U1 + U2 + U3 + U4 + 2 4 Evgeny Belyaev (ITMO University)   ,V = V1 + V2 + V3 + V4 + 2 Modern Information Theory 4 10 íîÿáðÿ 2021 ã.  . 29 / 64 Ïðîñòîé êîäåê èçîáðàæåíèé Ìîíîõðîìíîå èçîáðàæåíèå. Êàæäûé ïèêñåëü Evgeny Belyaev (ITMO University) xi ∈ {0, 1, ..., 255}. Modern Information Theory 10 íîÿáðÿ 2021 ã. 30 / 64 Ïðîñòîé êîäåê èçîáðàæåíèé Êâàíòîâàíèå è ýíòðîïèéíîå êîäèðîâàíèå. 1 Íà âõîäå ìîíîõðîìíîå èçîáðàæåíèå X = {x1 , x2 , ...}, xi ∈ {0, 1, ..., 255}. 2 Êîäåð  xi + ∆/2 . ∆ Êîäèðîâàíèå {z1 , z2 , ..} (íàïðèìåð, êîäîì Õàôôìàíà). X Áèòðåéò R ìîæíî îöåíèòü êàê: R ≈ H(Z ) = − pj log2 (pj ),  1 2 3 Êâàíòîâàíèå: zi = ãäå pj j ýòî âåðîÿòíîñòü 3 zi = j . Äåêîäåð 1 Äåêîäèðîâàíèå 2 Âîññòàíîâëåíèå Evgeny Belyaev (ITMO University) {z1 , z2 , ..}. x̂i = ∆ · zi . Modern Information Theory 10 íîÿáðÿ 2021 ã. 31 / 64 Ïðîñòîé êîäåê èçîáðàæåíèé Êâàíòîâàíèå è ýíòðîïèéíîå êîäèðîâàíèå Êâàíòîâàíèå  íåîáðàòèìàÿ îïåðàöèÿ, ïîýòîìó Evgeny Belyaev (ITMO University) Modern Information Theory H(Q(X )) < H(X ). 10 íîÿáðÿ 2021 ã. 32 / 64 Êîäèðîâàíèå ñ ïðåäñêàçàíèåì Îáùàÿ èäåÿ Ðèñ.: Ãèñòîãðàììà X , H(X ) = 7.44 Ðèñ.: Èñõîäíîå èçîáðàæåíèå Êîä Õàôôìàíà äëÿ äàííîãî ðàñïðåäåëåíèÿ îáåñïå÷èò íå áîëåå H(X ) = 7.44 áèò íà ïèêñåëü (áåç ñæàòèÿ  8 áèò). Evgeny Belyaev (ITMO University) Modern Information Theory 10 íîÿáðÿ 2021 ã. 33 / 64 Êîäèðîâàíèå ñ ïðåäñêàçàíèåì Îáùàÿ èäåÿ Ïîñòðîèì ðàñïðåäåëåíèå ïèêñåëÿ xi ïðè çàäàííîì ïèêñåëå xi−1 . H(Xi |50) = 4.56, H(Xi |100) = 4.57, H(Xi |200) = 4.27. R(Xi |Xi−1 ) ≈ H(Xi |Xi−1 ) = 255 X p(s)H(Xi |s) = 4.54 < H(Xi ) = 7.44. s=0 Êîä Õàôôìàíà ïîòðåáóåò 256 êîäîâûõ òàáëèö! Evgeny Belyaev (ITMO University) Modern Information Theory 10 íîÿáðÿ 2021 ã. 34 / 64 Êîäèðîâàíèå ñ ïðåäñêàçàíèåì Îáùàÿ èäåÿ Ðèñ.: Ãèñòîãðàììà îøèáêè ïðåäñêàçàíèÿ, H(E ) = 5.07 Ðèñ.: Îøèáêà ïðåäñêàçàíèÿ ei = xi − xi−1 Evgeny Belyaev (ITMO University) Modern Information Theory 10 íîÿáðÿ 2021 ã. 35 / 64 Êîäèðîâàíèå ñ ïðåäñêàçàíèåì Íåïðàâèëüíûé àëãîðèòì êîäèðîâàíèÿ Êîäåð 1 Íàêîïëåíèå îøèáêè â äåêîäåðå: Âû÷èñëåíèå îøèáêè 1 Ïóñòü ei = xi − xi−1 .   ei + ∆/2 Êâàíòîâàíèå: zi = . ∆ Êîäèðîâàíèå zi . 2 e1 = x1 − x0 , (x0 = x1 − e1 ) 3 ê1 = ∆ · z1 = e1 + δ1 4 x̂1 = x0 + ê1 = x0 + e1 + δ1 = x1 + δ1 5 e2 = x2 − x1 , (x1 = x2 − e2 ) ïðåäñêàçàíèÿ: 2 3 Äåêîäåð 1 Äåêîäèðîâàíèå zi . 2 Äåêâàíòîâàíèå: êi = ∆ · zi . 3 Âîññòàíîâëåíèå: x̂i = x̂i−1 + êi . x̂0 = x0 6 ê2 = ∆ · z2 = e2 + δ2 7 x̂2 = x̂1 + ê2 = x1 + δ1 + e2 + δ2 = x2 + δ1 + δ2 n X x̂n = xn + δk . 8 k=1 Evgeny Belyaev (ITMO University) Modern Information Theory 10 íîÿáðÿ 2021 ã. 36 / 64 Êîäèðîâàíèå ñ ïðåäñêàçàíèåì Êîäèðîâàíèå ñ ïðåäñêàçàíèåì è êâàíòîâàíèåì Îøèáêà â äåêîäåðå: Êîäåð 1 Âû÷èñëåíèå îøèáêè 3 ei =xi − x̂i−1 .  ei + ∆/2 Êâàíòîâàíèå: zi = . ∆ Êîäèðîâàíèå zi . 4 Âîññòàíîâëåíèå: ïðåäñêàçàíèÿ: 2 x̂i = x̂i−1 + êi = x̂i−1 + zi · ∆. Äåêîäåð 1 2 3 zi . Äåêâàíòîâàíèå: êi = ∆ · zi . Âîññòàíîâëåíèå: x̂i = x̂i−1 + êi . Äåêîäèðîâàíèå Evgeny Belyaev (ITMO University) 1 e1 = x1 − x0 , (x0 = x1 − e1 ) 2 ê1 = ∆ · z1 = e1 + δ1 3 x̂1 = x0 + ê1 = x0 + e1 + δ1 = x1 + δ1 4 e2 = x2 − x̂1 , (x̂1 = x2 − e2 ) 5 ê2 = ∆ · z2 = e2 + δ2 6 x̂2 = x̂1 + ê2 = x̂1 + e2 + δ2 = x2 + δ2 . 7 x̂n = xn + δn . Modern Information Theory 10 íîÿáðÿ 2021 ã. 37 / 64 Êîäèðîâàíèå ñ ïðåäñêàçàíèåì Ñðàâíåíèå êîäèðîâàíèÿ ñ ïðåäñêàçàíèåì è áåç ïðåäñêàçàíèÿ Evgeny Belyaev (ITMO University) Modern Information Theory 10 íîÿáðÿ 2021 ã. 38 / 64 Êîäèðîâàíèå ñ ïðåäñêàçàíèåì Ñðàâíåíèå êîäèðîâàíèÿ ñ ïðåäñêàçàíèåì è áåç ïðåäñêàçàíèÿ Evgeny Belyaev (ITMO University) Modern Information Theory 10 íîÿáðÿ 2021 ã. 39 / 64 Êîäèðîâàíèå ñ ïðåäñêàçàíèåì Îáùàÿ ñõåìà xi - ei zi Quantization pi + yi Inverse quantization Prediction 1 Âû÷èñëåíèå îøèáêè ïðåäñêàçàíèÿ:  2 Êâàíòîâàíèå: zi = 3 Êîäèðîâàíèå zi . 4 Äåêâàíòîâàíèå: 5 6 ei + q/2 q ei = xi − pi .  . yi = êi + pi = zi · q + pi . Âû÷èñëåíèå ïðåäñêàçàòåëÿ: pi+1 = f (y0 , y1 , ..., yi ). Ïðîñòåéøèé ñëó÷àé: pi+1 = yi . Evgeny Belyaev (ITMO University) Modern Information Theory 10 íîÿáðÿ 2021 ã. 40 / 64 Êîäèðîâàíèå ñ ïðåäñêàçàíèåì Ñòàíäàðò JPEG-LS 5 JPEG-LS ðàáîòàåò â äâóõ ðåæèìàõ: regular mode è run-length mode. Âû÷èñëåíèå ãðàäèåíòà:   d1 = d − b, d2 = b − c,  d3 = c − a. Åñëè d 1 = d 2 = d 3 = 0, òî êîäåð ïåðåõîäèò â ðåæèì êîäèðîâàíèÿ äëèí ñåðèé äî òåõ ïîð, ïîêà íå ïðîèçîéä¼ò a 6= x , ëèáî íå áóäåò äîñòèãíóò êîíåö ñòðîêè. Äëèíà ñåðèè ïåðåäà¼òñÿ ìîíîòîííûì êîäîì (Rice-Golomb code) è êîäåð âîçâðàùàåòñÿ â regular mode. 5 ISO/IEC 14495-1, ITU Recommendation T.87, Information technology - Lossless and near-lossless compression of continuous-tone still images, 1999. Evgeny Belyaev (ITMO University) Modern Information Theory 10 íîÿáðÿ 2021 ã. 41 / 64 Êîäèðîâàíèå ñ ïðåäñêàçàíèåì Ñòàíäàðò JPEG-LS. Regular mode Ïèêñåëè îáðàáàòûâàþòñÿ â ðàñòðîâîì ïîðÿäêå; Âû÷èñëåíèå ïðåäñêàçàòåëÿ:   min(a, b) if c ≥ max(a, b), max(a, b) if c ≤ min(a, b) px ←  a + b − c otherwise. Êîððåêöèÿ ïðåäñêàçàòåëÿ: px ← px + ∆p(d 1, d 2, d 3). Îøèáêà ïðåäñêàçàíèÿ ex ← x − px êîäèðóåòñÿ ìîíîòîííûì êîäîì (Rice-Golomb code). Evgeny Belyaev (ITMO University) Modern Information Theory 10 íîÿáðÿ 2021 ã. 42 / 64 Êîäèðîâàíèå ñ ïðåäñêàçàíèåì Îáùàÿ ñõåìà ñòàíäàðòà JPEG-LS 6 Òàáëèöà: Áèòû íà ïèêñåëü äëÿ Lena 6 CALIC JPEG-LS JPEG2000 lossless WinRAR 4.121 4.237 4.330 5.135 M. Weinberger, G. Seroussi, G. Sapiro, The LOCO-I Lossless Image Compression Algorithm: Principles and Standardization into JPEG-LS. Evgeny Belyaev (ITMO University) Modern Information Theory 10 íîÿáðÿ 2021 ã. 43 / 64 Êîäèðîâàíèå ñ ïðåîáðàçîâàíèåì Îñíîâíàÿ èäåÿ Äåëèì èçîáðàæåíèå íà íåïåðåñåêàþùèåñÿ áëîêè ðàçìåðîì Âûïîëíÿåì ïðåîáðàçîâàíèå n×n n × n; äëÿ êàæäîãî áëîêà: I Ïðåîáðàçîâàíèå äîëæíî äåêêîðåëèðîâàòü çíà÷åíèÿ â áëîêå èëè ïðåäñòàâèòü èíôîðìàöèþ î áëîêå â íàèìåíüøåì êîëè÷åñòâå êîýôôèöèåíòîâ ïðåîáðàçîâàíèÿ. I Ïðåîáðàçîâàíèå äîëæíî áûòü îðòîíîðìàëüíûì (èñêàæåíèå â îáëàñòè êîýôôèöèåíòîâ ïðåîáðàçîâàíèÿ äîëæíî áûòü ðàâíî èñêàæåíèþ â îáëàñòè ñèãíàëà). I Ïðåîáðàçîâàíèå äîëæíî èìåòü íåáîëüøóþ âû÷èñëèòåëüíóþ ñëîæíîñòü (íàïðèìåð, áûòü ñåïàðàáåëüíûì). Êâàíòîâàíèå óñòðàíÿåò íàèìåíåå èíôîðìàòèâíûå êîýôôèöèåíòû ïðåîáðàçîâàíèÿ. Ýíòðîïèéíîå êîäèðîâàíèå ïðèìåíÿåòñÿ ê êâàíòîâàííûì êîýôôèöèåíòàì ïðåîáðàçîâàíèÿ. Evgeny Belyaev (ITMO University) Modern Information Theory 10 íîÿáðÿ 2021 ã. 44 / 64 Êîäèðîâàíèå ñ ïðåîáðàçîâàíèåì Âûáîð ïðåîáðàçîâàíèÿ Ïðÿìîå ïðåîáðàçîâàíèå T (u, v ) = N− X1 X1 N− f (x, y )g (x, y , u, v ), x=0 y =0 u, v = 0, 1, 2, ..., N − 1. Îáðàòíîå ïðåîáðàçîâàíèå f (x, y ) = N− X1 N− X1 T (x, y )h(x, y , u, v ). u=0 v =0 Ñåïàðàáåëüíîå ïðåîáðàçîâàíèå: g (x, y , u, v ) = g1 (x, u) · g2 (y , v ). Ñèììåòðè÷íîå ïðåîáðàçîâàíèå: g (x, y , u, v ) = g1 (x, y ) · g1 (u, v ). Evgeny Belyaev (ITMO University) Modern Information Theory 10 íîÿáðÿ 2021 ã. 45 / 64 Êîäèðîâàíèå ñ ïðåîáðàçîâàíèåì Âûáîð ïðåîáðàçîâàíèÿ Âîçìîæíûå êàíäèäàòû: Ïðåîáðàçîâàíèå Êàðóíåíà-Ëîåâà (Karhunen-Loeve Transform, KLT); I Ãàðàíòèðóåò, ÷òî êîýôôèöèåíòû íå êîððåëèðîâàíû. I Îïòèìàëüíûé áàçèñ çàâèñèò îò âõîäíûõ äàííûõ, ò.å., åãî íóæíî ïåðåäàâàòü äåêîäåðó. I Âûñîêàÿ âû÷èñëèòåëüíàÿ ñëîæíîñòü; Äèñêðåòíîå ïðåîáðàçîâàíèå Ôóðüå (Discrete Fourier Transform, DFT); I Èìååò èçáûòî÷íûå (ìíèìûå) êîýôôèöèåíòû; Äèñêðåòíîå êîñèíóñíîå ïðåîáðàçîâàíèå (Discrete Cosine Transform, DCT); Äèñêðåòíîå ïðåîáðàçîâàíèå Óîëøà-Àäàìàðà (Walsh-Hadamard transform, WHT); Evgeny Belyaev (ITMO University) Modern Information Theory 10 íîÿáðÿ 2021 ã. 46 / 64 Êîäèðîâàíèå ñ ïðåîáðàçîâàíèåì Ïðåîáðàçîâàíèå Óîëøà-Àäàìàðà g (x, y , u, v ) = h(x, y , u, v ) = where bi (x)  çíà÷åíèå áèòà â 1 N x (−1)(bi (x)pi (u) + bi (y )pi (v )) , N = 2m , íà ïîçèöèè i. p0 (u) = bn−1 (u), p1 (u) = bn−1 (u) + bn−2 (u), p2 (u) = bn−2 (u) + bn−3 (u), ... pn−1 (u) = b1 (u) + b0 (u). Evgeny Belyaev (ITMO University) Modern Information Theory 10 íîÿáðÿ 2021 ã. 47 / 64 Êîäèðîâàíèå ñ ïðåîáðàçîâàíèåì Äèñêðåòíîå êîñèíóñíîå ïðåîáðàçîâàíèå  g (x, y , u, v ) = h(x, y , u, v ) = a(u)a(v ) cos (2x + 1)uπ 2N   cos (2y + 1)v π 2N   1   √ ,u = 0 N a(u) = 2   √ , u 6= 0. N Evgeny Belyaev (ITMO University) Modern Information Theory 10 íîÿáðÿ 2021 ã. 48 / 64 Êîäèðîâàíèå ñ ïðåîáðàçîâàíèåì Äèñêðåòíîå ïðåîáðàçîâàíèå Ôóðüå 50 50 100 100 150 150 200 200 250 250 300 300 350 350 400 400 450 450 500 500 100 Ðèñ.: FFT 128 200 × 128 300 400 500 100 200 300 400 500 ïîñëå óäàëåíèå 90% êîýôôèöèåíòîâ ñ íàèìåíüøåé àìïëèòóäîé, Y-PSNR=31.23 äÁ Evgeny Belyaev (ITMO University) Modern Information Theory 10 íîÿáðÿ 2021 ã. 49 / 64 Êîäèðîâàíèå ñ ïðåîáðàçîâàíèåì Äèñêðåòíîå ïðåîáðàçîâàíèå Óîëøà-Àäàìàðà 50 50 100 100 150 150 200 200 250 250 300 300 350 350 400 400 450 450 500 500 100 Ðèñ.: WHT 128 200 × 128 300 400 500 100 200 300 400 500 ïîñëå óäàëåíèå 90% êîýôôèöèåíòîâ ñ íàèìåíüøåé àìïëèòóäîé, Y-PSNR=30.40 äÁ Evgeny Belyaev (ITMO University) Modern Information Theory 10 íîÿáðÿ 2021 ã. 50 / 64 Êîäèðîâàíèå ñ ïðåîáðàçîâàíèåì Äèñêðåòíîå êîñèíóñíîå ïðåîáðàçîâàíèå 50 50 100 100 150 150 200 200 250 250 300 300 350 350 400 400 450 450 500 500 100 Ðèñ.: DCT 128 200 × 128 300 400 500 100 200 300 400 500 ïîñëå óäàëåíèå 90% êîýôôèöèåíòîâ ñ íàèìåíüøåé àìïëèòóäîé, Y-PSNR=34.15 äÁ Evgeny Belyaev (ITMO University) Modern Information Theory 10 íîÿáðÿ 2021 ã. 51 / 64 Êîäèðîâàíèå ñ ïðåîáðàçîâàíèåì Âûáîð ïðåîáðàçîâàíèÿ 40 39 Y−PSNR, dB 38 37 36 35 34 DCT WHT FFT 33 32 4x4 8x8 16x16 32x32 64x64 Transform size 128x128 256x256 512x512 Ðèñ.: Y-PSNR ïîñëå óäàëåíèå 80% êîýôôèöèåíòîâ ñ íàèìåíüøåé àìïëèòóäîé Evgeny Belyaev (ITMO University) Modern Information Theory 10 íîÿáðÿ 2021 ã. 52 / 64 Ñòàíäàðò JPEG Îñíîâíûå ýòàïû 7 1 Ïðåîáðàçîâàíèå öâåòîâîãî ïðîñòðàíñòâà èç RGB24 â YCbCr 4:2:0; 2 Ðàçáèåíèå ÿðêîñòíîé è öâåòîðàçíîñòíîé êîìïîíåíòû íà áëîêè 8 × 8; 3 Ïðèìåðåíèå 2-D DCT äëÿ êàæäîãî áëîêà; 4 Êâàíòîâàíèå DCT êîýôôèöèåíòîâ; 5 DC êîýôôèöèåíò èç òåêóùåãî áëîêà ïðåäñêàçûâàåòñÿ ïðè ïîìîùè DC êîýôôèöèåíòà ïðåäûäóùåãî áëîêà è êîäèðîâàíèå ðàçíîñòè êîäîì Ëåâåíøòåéíà ñ êîäîì Õàôôìàíà â ïåðâîé ÷àñòè êîäîâîãî ñëîâà. 6 Ñêàíèðîâàíèå AC êîýôôèöèåíòîâ â 'çèãçàãîîáðàçíîì' ïîðÿäêå. 7 Îäíîìåðíûé âåêòîð AC êîäèðóåòñÿ äëèíàìè ñåðèé è êîäîì Õàôôìàíà. 7 Digital compression and coding of continuous-tone still images, ITU-T and ISO/IEC JTC1, 1992. Evgeny Belyaev (ITMO University) Modern Information Theory 10 íîÿáðÿ 2021 ã. 53 / 64 Ñòàíäàðò JPEG Ïðèìåð Èñõîäíûé áëîê 8       X =      × 8: 168 161 161 150 154 168 164 154 171 154 161 150 157 171 150 164 171 168 147 164 164 161 143 154 164 171 154 161 157 157 147 132 161 161 157 154 143 161 154 132 164 161 161 154 150 157 154 140 161 168 157 154 161 140 140 132 154 161 157 150 140 132 136 128 Evgeny Belyaev (ITMO University) Modern Information Theory             10 íîÿáðÿ 2021 ã. 54 / 64 Ñòàíäàðò JPEG Ïðèìåð Áëîê ïîñëå âû÷èòàíèÿ 128 è âûïîëíåíèÿ 2-D DCT:  214 49 −3 20  34 −25 11 13   −6 −4 8 −9   8 − 10 4 4 Y =  −12 5 −1 −2   5 9 −8 3   2 −2 3 −1 −1 1 2 Evgeny Belyaev (ITMO University) −10 −1 1 5 −3 15 3 −3 5 −15 10 6 −15 9 −5 4 −7 −14 1 3 −3 3 −2 −4 Modern Information Theory  −6 −6   10   6   −1   2   −4  −2 10 íîÿáðÿ 2021 ã. 55 / 64 Ñòàíäàðò JPEG Ïðèìåð Áëîê ïîñëå ñêàëÿðíîãî êâàíòîâàíèÿ:       Z =      Evgeny Belyaev (ITMO University) 13 4 1 3 −2 1 1 1 1 −1 Modern Information Theory             10 íîÿáðÿ 2021 ã. 56 / 64 Ñòàíäàðò JPEG Ïðèìåð Êîýôôèöèåíòû ñêàíèðóþòñÿ â çèãçàãîîáðàçíîì ïîðÿäêå: 1 2 3 4 5 6 7 1 2 3 4 5 6 7 Ïîñëå ñêàíèðîâàíèÿ Z = {13, 4, 3, 0, −2, 0, 1, 1, 0, 1, −1, −1, 1, 1, 0, ..., 0}; Evgeny Belyaev (ITMO University) Modern Information Theory 10 íîÿáðÿ 2021 ã. 57 / 64 Ñòàíäàðò JPEG Ïðèìåð Z = {13, 4, 3, 0, −2, 0, 1, 1, 0, 1, −1, −1, 1, 1, 0, ..., 0}; Ïåðâûé êîýôôèöèåíò 13 (DC coecient) ïðåäñêàçûâàåòñÿ ïî DC êîýôôèöèåíòó èç ïðåäûäóùåãî (ñëåâà) áëîêà, çàòåì àìïëèòóäà îøèáêè ïðåäñêçàíèÿ êîäèðóåòñÿ ìîíîòîííûì êîäîì, â êîòîðîì ïåðâàÿ ÷àñòü êîäèðóåòñÿ êîäîì Õàôôìàíà. Äîïîëíèòåëüíûé áèò èñïîëüçóåòñÿ äëÿ ïåðåäà÷è çíàêà äëÿ íåíóëåâûõ çíà÷åíèé. n → huff(DC | {zbit} . {z bits)} bin(DC) | {z } one | sign DC bit size DC Evgeny Belyaev (ITMO University) Modern Information Theory 10 íîÿáðÿ 2021 ã. 58 / 64 Ñòàíäàðò JPEG Ïðèìåð Z = {13, 4, 3, 0, −2, 0, 1, 1, 0, 1, −1, −1, 1, 1, 0, ..., 0}; Îñòàâøèåñÿ êîýôôèöèåíòû (AC coecients) ïðåäñòàâëÿþòñÿ ïàðàìè [run, level], ãäå run  ÷èñëî íóëåé ïåðåä íåíóëåâûì level  çíà÷åíèå íåíóëåâîãî êîýôôèöèåíòà. êîýôôèöèåíòîì,  íàøåì ñëó÷àå: [0, 4],[0, 3],[1, −2],[1, 1],[0, 1],[1, 1],[0, −1],[0, −1],[0, 1],[0, 1]. [run, level] → Huffman bin(|level|) | {z } | {zbit} . | {z } one sign level [run, level bit size] Åñëè ïàðà [run,level ] íå ïðèñóòâóåò â êîäîâîé òàáëèöå Õàôôìàíà, òî ïåðåäà¼òñÿ ESC-ñèìâîë, ïîñëå ÷åãî run è level ïåðåäàþòñÿ ðàâíîìåðíûì êîäîì. End-of-block (EOB) ñèìâîë ïåðåäà¼òñÿ êîäîì Õàôôìàíà, åñëè â çèã-çàãå äàëåå ñëåäóþò òîëüêî íóëè. Evgeny Belyaev (ITMO University) Modern Information Theory 10 íîÿáðÿ 2021 ã. 59 / 64 Ñòàíäàðò JPEG Ïðèìåð Áëîê ïîñëå äåêîäèðîâàíèÿ êîäîì Õàôôìàíà, îáðàòíîãî ïðîõîäà ïî çèã-çàãó, äåêâàíòîâàíèÿ, îáðàòíîãî ïðåîáðàçîâàíèÿ è ïðèáàâëåíèÿ 128:       X̂ =       171 160 149 149 158 166 166 162 174 164 155 154 160 164 161 156 171 164 157 156 158 158 151 145 161 157 154 154 155 151 144 137 156 155 155 156 156 152 145 140 159 160 160 160 157 153 148 145 161 161 160 156 150 144 141 139 159 158 155 148 139 132 129 128 Evgeny Belyaev (ITMO University) Modern Information Theory             10 íîÿáðÿ 2021 ã. 60 / 64 Ñòàíäàðò JPEG Áëîêîâûå àðòåôàêòû Ïðè áîëüøèõ çíà÷åíÿõ Evgeny Belyaev (ITMO University) ∆ âîçíèêàþò õîðîøî âèäèìûå ãðàíèöû áëîêîâ: Modern Information Theory 10 íîÿáðÿ 2021 ã. 61 / 64 Ëàáîðàòîðíàÿ ðàáîòà 2. Òðàíñêîäåð äëÿ ôîðìàòà jpg Evgeny Belyaev (ITMO University) Modern Information Theory 10 íîÿáðÿ 2021 ã. 62 / 64 Ëàáîðàòîðíàÿ ðàáîòà 2. Òðàíñêîäåð äëÿ ôîðìàòà jpg Òåñòîâûå èçîáðàæåíèÿ è ðàçìåðû ôàéëîâ ôîðìàòà JPG Èçîáðàæåíèå Ðàçìåð JPEG, QF=80 JPEG, QF=30 airplane × 512 594 × 400 512 × 512 490 × 733 512 × 512 1118 × 1105 768 × 512 512 × 512 768 × 512 512 × 512 510 × 383 768 × 512 629 × 794 768 × 512 1024 × 768 44079 19207 26569 12080 88465 36113 81974 35902 arctichare baboon cat fruits frymire girl lena monarch peppers pool sails serrano tulips watch Evgeny Belyaev (ITMO University) 512 45303 17646 440857 200860 59979 24310 43872 17578 64055 28501 47929 18746 14492 7467 105830 45512 138167 58288 85764 37972 101074 46741 Modern Information Theory 10 íîÿáðÿ 2021 ã. 63 / 64 Ëàáîðàòîðíàÿ ðàáîòà 2. Òðàíñêîäåð äëÿ ôîðìàòà jpg Òðåáîâàíèÿ ê ïðîãðàììå è îò÷åòó Òðåáîâàíèÿ ê ïðîãðàììå: 1 Íàïèñàòü êîäåð è äåêîäåð, êîòîðûå ðàáîòàþò êàê îòäåëüíûå ïðîãðàììû. 2  êà÷åñòâå ïàðàìåòðà íà âõîä êîäåðà ïîäà¼òñÿ èìÿ òðàíñêîäèðóåìîãî ôàéëà â ôîðìàòå jpg. Íà âûõîäå ïðîãðàììà âûäà¼ò ôàéë ñî ñæàòûìè äàííûìè. 3 Íà âõîä äåêîäåðà ïîäà¼òñÿ ôàéë ñî ñæàòûìè äàííûìè. Íà âûõîäå äåêîäåð âûäà¼ò ôàéë, êîòîðûé èäåíòè÷åí èñõîäíîìó ôàéëó â ôîðìàòå jpg (áèò â áèò). 4 Àëãîðèòìû, îòíîñÿùèåñÿ íåïîñðåäñòâåííî ê êîäèðîâàíèþ è äåêîäèðîâàíèþ äîëæíû áûòü ðåàëèçîâàíû áåç èñïîëüçîâàíèÿ ñòîðîííèõ áèáëèîòåê. 5 Ïðè óëó÷øåíèè ñæàòèÿ íà 2% è áîëåå äëÿ QF=30, íà÷èñëÿåòñÿ 10 áàëëîâ. Ïðè óëó÷øåíèè ñæàòèÿ íà 2% è áîëåå äëÿ QF=80, íà÷èñëÿåòñÿ 10 áàëëîâ. Òðåáîâàíèÿ ê îò÷åòó: 1 Îò÷åò â pdf ôîðìàòå, êîòîðûé âêëþ÷àåò â ñåáÿ: I ÔÈÎ ñòóäåíòà, íîìåð ãðóïïû è çàäàíèÿ. I Îïèñàíèå àëãîðèòìà êîäèðîâàíèÿ è äåêîäèðîâàíèÿ. I Äëÿ êàæäîãî èç 15-òè èçîáðàæåíèé óêàçàòü ðàçìåð ñæàòîãî ôàéëà â áàéòàõ. Äàííûå ïðåäñòàâèòü â âèäå òàáëèöû. I Ñóììàðíîå çíà÷åíèå ñæàòîãî ðàçìåðà âñåõ ôàéëîâ â áàéòàõ. 2 Èñõîäíûé êîä êîäåðà è äåêîäåðà. 3 Èñïîëíÿåìûå ïðîãðàììû êîäåðà è äåêîäåðà, ãîòîâûìè ê çàïóñêó íà Windows 10. Evgeny Belyaev (ITMO University) Modern Information Theory 10 íîÿáðÿ 2021 ã. 64 / 64