Простое целочисленное косинусное преобразование высокого порядка для видеокодирования с высоким разрешением
Предложен матричный метод построения простого целочисленного косинусного преобразования высокого порядка. На его основе построено однонормовое простое целочисленное преобразование порядка 32 и разработаны его быстрые алгоритмы низкой вычислительной сложности, которая меньше в 4,9 раза, чем в известн...
Gespeichert in:
| Datum: | 2018 |
|---|---|
| 1. Verfasser: | |
| Format: | Artikel |
| Sprache: | Russian |
| Veröffentlicht: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2018
|
| Schriftenreihe: | Кибернетика и системный анализ |
| Schlagworte: | |
| Online Zugang: | http://dspace.nbuv.gov.ua/handle/123456789/144879 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Простое целочисленное косинусное преобразование высокого порядка для видеокодирования с высоким разрешением / Л.А. Гнатив // Кибернетика и системный анализ. — 2018. — Т. 54, № 3. — С. 166–177. — Бібліогр.: 17 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-144879 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-1448792019-01-09T01:23:03Z Простое целочисленное косинусное преобразование высокого порядка для видеокодирования с высоким разрешением Гнатив, Л.А. Програмно-технічні комплекси Предложен матричный метод построения простого целочисленного косинусного преобразования высокого порядка. На его основе построено однонормовое простое целочисленное преобразование порядка 32 и разработаны его быстрые алгоритмы низкой вычислительной сложности, которая меньше в 4,9 раза, чем в известных алгоритмах, и в 21,6 раза — чем в стандарте Н.265. Они требуют только целочисленных операций. Это преобразование близко к дискретному косинусному преобразованию и имеет хорошие характеристики кодирования. Запропоновано матричний метод побудови простого цілочисельного косинусного перетворення високого порядку. На його основі побудовано однонормове просте цілочисельне перетворення порядку 32 і розроблено його швидкі алгоритми низької обчислювальної складності, яка менша в 4,9 рази, ніж у відомих алгоритмах, та в 21,6 рази, ніж у стандарті Н.265. Вони потребують тільки цілочисельних операцій. Це перетворення близьке до дискретного косинусного перетворення і має добрі характеристики кодування. A matrix method is proposed for constructing a simple order-32 integer cosine transform. Based on the method proposed, a one-norm simple order-32 integer transform is constructed and its fast algorithms of low computational complexity are developed that require only integer operations and whose computational complexity is 4.9 times less than those of the well-known algorithms and is 21.6 times less than that of the standard H.2 65. This transform is close to the discrete cosine transform and has good coding performance. 2018 Article Простое целочисленное косинусное преобразование высокого порядка для видеокодирования с высоким разрешением / Л.А. Гнатив // Кибернетика и системный анализ. — 2018. — Т. 54, № 3. — С. 166–177. — Бібліогр.: 17 назв. — рос. 1019-5262 http://dspace.nbuv.gov.ua/handle/123456789/144879 681.391, 681.3, 621.372.397 ru Кибернетика и системный анализ Інститут кібернетики ім. В.М. Глушкова НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| topic |
Програмно-технічні комплекси Програмно-технічні комплекси |
| spellingShingle |
Програмно-технічні комплекси Програмно-технічні комплекси Гнатив, Л.А. Простое целочисленное косинусное преобразование высокого порядка для видеокодирования с высоким разрешением Кибернетика и системный анализ |
| description |
Предложен матричный метод построения простого целочисленного косинусного преобразования высокого порядка. На его основе построено однонормовое простое целочисленное преобразование порядка 32 и разработаны его быстрые алгоритмы низкой вычислительной сложности, которая меньше в 4,9 раза, чем в известных алгоритмах, и в 21,6 раза — чем в стандарте Н.265. Они требуют только целочисленных операций. Это преобразование близко к дискретному косинусному преобразованию и имеет хорошие характеристики кодирования. |
| format |
Article |
| author |
Гнатив, Л.А. |
| author_facet |
Гнатив, Л.А. |
| author_sort |
Гнатив, Л.А. |
| title |
Простое целочисленное косинусное преобразование высокого порядка для видеокодирования с высоким разрешением |
| title_short |
Простое целочисленное косинусное преобразование высокого порядка для видеокодирования с высоким разрешением |
| title_full |
Простое целочисленное косинусное преобразование высокого порядка для видеокодирования с высоким разрешением |
| title_fullStr |
Простое целочисленное косинусное преобразование высокого порядка для видеокодирования с высоким разрешением |
| title_full_unstemmed |
Простое целочисленное косинусное преобразование высокого порядка для видеокодирования с высоким разрешением |
| title_sort |
простое целочисленное косинусное преобразование высокого порядка для видеокодирования с высоким разрешением |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| publishDate |
2018 |
| topic_facet |
Програмно-технічні комплекси |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/144879 |
| citation_txt |
Простое целочисленное косинусное преобразование высокого порядка для видеокодирования с высоким разрешением / Л.А. Гнатив // Кибернетика и системный анализ. — 2018. — Т. 54, № 3. — С. 166–177. — Бібліогр.: 17 назв. — рос. |
| series |
Кибернетика и системный анализ |
| work_keys_str_mv |
AT gnativla prostoeceločislennoekosinusnoepreobrazovanievysokogoporâdkadlâvideokodirovaniâsvysokimrazrešeniem |
| first_indexed |
2025-07-10T20:25:21Z |
| last_indexed |
2025-07-10T20:25:21Z |
| _version_ |
1837292991855722496 |
| fulltext |
Ë.À. ÃÍÀÒÈÂ
ÓÄÊ 681.391, 681.3, 621.372.397 ÏÐÎÑÒÎÅ ÖÅËÎ×ÈÑËÅÍÍÎÅ ÊÎÑÈÍÓÑÍÎÅ
ÏÐÅÎÁÐÀÇÎÂÀÍÈÅ ÂÛÑÎÊÎÃÎ ÏÎÐßÄÊÀ
ÄËß ÂÈÄÅÎÊÎÄÈÐÎÂÀÍÈß Ñ ÂÛÑÎÊÈÌ
ÐÀÇÐÅØÅÍÈÅÌ
Àííîòàöèÿ. Ïðåäëîæåí ìàòðè÷íûé ìåòîä ïîñòðîåíèÿ ïðîñòîãî öåëî÷èñëåí-
íîãî êîñèíóñíîãî ïðåîáðàçîâàíèÿ âûñîêîãî ïîðÿäêà. Íà åãî îñíîâå ïîñòðî-
åíî îäíîíîðìîâîå ïðîñòîå öåëî÷èñëåííîå ïðåîáðàçîâàíèå ïîðÿäêà 32 è ðàç-
ðàáîòàíû åãî áûñòðûå àëãîðèòìû íèçêîé âû÷èñëèòåëüíîé ñëîæíîñòè, êîòî-
ðàÿ ìåíüøå â 4,9 ðàçà, ÷åì â èçâåñòíûõ àëãîðèòìàõ, è â 21,6 ðàçà — ÷åì
â ñòàíäàðòå Í.265. Îíè òðåáóþò òîëüêî öåëî÷èñëåííûõ îïåðàöèé. Ýòî ïðå-
îáðàçîâàíèå áëèçêî ê äèñêðåòíîìó êîñèíóñíîìó ïðåîáðàçîâàíèþ è èìååò
õîðîøèå õàðàêòåðèñòèêè êîäèðîâàíèÿ.
Êëþ÷åâûå ñëîâà: äèñêðåòíîå êîñèíóñíîå ïðåîáðàçîâàíèå, öåëî÷èñëåííîå
êîñèíóñíîå ïðåîáðàçîâàíèå, ìàñøòàáèðîâàííîå ïðåîáðàçîâàíèå, ôàêòîðèçà-
öèÿ, áûñòðîå ïðåîáðàçîâàíèå, ýôôåêòèâíîñòü êîäèðîâàíèÿ, âû÷èñëèòåëüíàÿ
ñëîæíîñòü, êîýôôèöèåíò ñæàòèÿ, âèäåîêîäèðîâàíèå, Í.264, H.265, AVS.
ÂÂÅÄÅÍÈÅ
Öåëî÷èñëåííûå êîñèíóñíûå ïðåîáðàçîâàíèÿ (ÖÊÏ) ýôôåêòèâíî èñïîëüçîâàíû
â òàêèõ ñîâðåìåííûõ âèäåîñòàíäàðòàõ, êàê Í.264/AVC [1, 2], VC-1 [3], AVS [4],
H.265/HEVC [5, 6]. Ýôôåêòèâíîñòü ïðèìåíåíèÿ ÖÊÏ êàê èíñòðóìåíòà äëÿ
óñòðàíåíèÿ èçáûòî÷íîñòè â èçîáðàæåíèÿõ è âèäåîñèãíàëàõ àðãóìåíòèðîâàíî
è ïîäðîáíî èçëîæåíî â [7]. Ïðè ñîçäàíèè íîâîãî ñòàíäàðòà âèäåîêîäèðîâàíèÿ
H.265/HEVC ðàññìàòðèâàëîñü ìíîãî öåëî÷èñëåííûõ ïðåîáðàçîâàíèé ñ áûñòðûìè
àëãîðèòìàìè.  ðàáîòàõ [8–10] ïðåäëîæåíû ïðåîáðàçîâàíèÿ íà îñíîâå öåëî÷èñ-
ëåííîé àïïðîêñèìàöèè äèñêðåòíîãî êîñèíóñíîãî ïðåîáðàçîâàíèÿ (ÄÊÏ) ñ áûñò-
ðûìè àëãîðèòìàìè ìåíüøåé âû÷èñëèòåëüíîé ñëîæíîñòè, ÷åì â ñòàíäàðòå
Í.265 [6]. Â ðàáîòàõ [7, 11] ðàññìîòðåí ìåòîä ïîñòðîåíèÿ ÖÊÏ âûñîêîãî ïîðÿäêà
ñ áûñòðûìè àëãîðèòìàìè íèçêîé âû÷èñëèòåëüíîé ñëîæíîñòè, êîòîðàÿ â îòëè÷èå
îò èçâåñòíûõ [9, 10] ìåíüøå â 3,24 ðàçà è â 15,6 ðàçà ìåíüøå, ÷åì â ñòàíäàðòå
Í.265. Â ðàáîòå [12] ïðåäëîæåí ìåòîä ïîñòðîåíèÿ ïðîñòîãî ÖÊÏ ïîðÿäêà 32
ñ áûñòðûìè àëãîðèòìàìè, êîòîðûå èìåþò ìåíüøóþ â 4,3 ðàçà âû÷èñëèòåëüíóþ
ñëîæíîñòü, ÷åì â èçâåñòíûõ, è â 19 ðàç ìåíüøóþ, ÷åì â ñòàíäàðòå Í.265.
 íàñòîÿùåé ñòàòüå ðàññìîòðåí ìàòðè÷íûé ìåòîä ïîñòðîåíèÿ ïðîñòîãî ÖÊÏ
ïîðÿäêà 32 íà îñíîâå ÖÊÏ ïîðÿäêà 16, êîòîðûé îáîáùàåò ìåòîä, ïðåäëîæåííûé
â ðàáîòå [13]. Ýòî ïðåîáðàçîâàíèå ÿâëÿåòñÿ àëüòåðíàòèâîé ïðîñòîãî ÖÊÏ, ïðåä-
ëîæåííîãî â [12], è åãî áûñòðûå àëãîðèòìû èìåþò íà 17 % ìåíüøóþ âû÷èñëè-
òåëüíóþ ñëîæíîñòü ïðè õîðîøèõ õàðàêòåðèñòèêàõ êîäèðîâàíèÿ. Ïîñòðîåíî îä-
íîíîðìîâîå ïðîñòîå ÖÊÏ ïîðÿäêà 32 è ðàçðàáîòàíû àëãîðèòìû áûñòðûõ öåëî-
÷èñëåííûõ ïðåîáðàçîâàíèé, êîòîðûå ïðèâîäÿò ê ñóùåñòâåííîìó ñîêðàùåíèþ
âû÷èñëåíèé, ò.å. èìåþò íèçêóþ âû÷èñëèòåëüíóþ ñëîæíîñòü. Ýêñïåðèìåíòàëü-
íûå ðåçóëüòàòû ïîêàçàëè, ÷òî ýòî ïðåîáðàçîâàíèå èìååò õîðîøèå õàðàêòåðèñòè-
êè êîäèðîâàíèÿ è àíàëîãè÷íû õàðàêòåðèñòèêàì ÄÊÏ.
166 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2018, òîì 54, ¹ 3
© Ë.À. Ãíàòèâ, 2018
ÌÅÒÎÄ ÏÎÑÒÐÎÅÍÈß ÏÐÎÑÒÎÃÎ ÖÅËÎ×ÈÑËÅÍÍÎÃÎ ÊÎÑÈÍÓÑÍÎÃÎ
ÏÐÅÎÁÐÀÇÎÂÀÍÈß ÂÛÑÎÊÎÃÎ ÏÎÐßÄÊÀ
Ïîñòðîèì ìàòðèöó ïðîñòîãî öåëî÷èñëåííîãî êîñèíóñíîãî ïðåîáðàçîâàíèÿ ïîðÿä-
êà 32, â êîòîðîé ñòðîêè ñ íå÷åòíûìè íîìåðàìè ïðåäñòàâëÿþò ïðîñòûå êîñèíóñíûå
ôóíêöèè, à ñòðîêè ñ ÷åòíûìè íîìåðàìè ïðåäñòàâëÿþò áàçèñíûå ôóíêöèè ÖÊÏ.
Ðàññìîòðèì ìàòðèöó ICT32
� ðàçìåðà 32 32� ïðîñòîãî ÖÊÏ ñ ïåðåñòàâëåííû-
ìè ñòðîêàìè, êîòîðàÿ ïîëó÷åíà èç ìàòðèöû ICT32 ïåðåñòàíîâêîé ñòðîê ñíà÷àëà
íà îñíîâå äâîè÷íî-èíâåðñíûõ ïåðåñòàíîâîê (ÄÈÏ), à çàòåì ïðîñòûõ ñîâåðøåí-
íûõ ïåðåñòàíîâîê (ÏÑÏ), îáðàòíûõ (èíâåðñíûõ) ïåðåñòàíîâîê (ÎÏ) è ïåðåñòàíî-
âîê ïî êîäó Ãðåÿ (ÏÊÃ) [14]:
ICT P P P P P P ICT32 5 4 3 2 1 32 32
� � , (1)
ãäå P32 — ìàòðèöà 32 32� ÄÈÏ, P1 — áëî÷íî-äèàãîíàëüíàÿ ìàòðèöà 32 32�
ñ åäèíè÷íîé ìàòðèöåé 17 17� I17 è ìàòðèöåé 15 15�
~
P15 ÏÑÏ, P2 — áëî÷-
íî-äèàãîíàëüíàÿ ìàòðèöà 32 32� , ñîäåðæàùàÿ ìàòðèöû 6 6�
~
P6 ÏÑÏ, 10 10�
~
P10
ÏÑÏ, åäèíè÷íóþ ìàòðèöó 4 4� I 4 è åäèíèöó; P3 — áëî÷íî-äèàãîíàëüíàÿ ìàò-
ðèöà 32 32� , ñîäåðæàùàÿ ìàòðèöó 7 7�
~
P7 ÏÑÏ, ìàòðèöó 4 4� G4 ÏÊÃ, åäè-
íè÷íóþ ìàòðèöó 20 20� I 20 è åäèíèöó; P4 — áëî÷íî-äèàãîíàëüíàÿ ìàòðèöà
32 32� , ñîäåðæàùàÿ ìàòðèöû 4 4�
~
P4 ÏÑÏ, I 4 ÎÏ, ìàòðèöû 3 3� I 3 ÎÏ, åäè-
íè÷íóþ ìàòðèöó 12 12� I12 è åäèíèöó; P5 — áëî÷íî-äèàãîíàëüíàÿ ìàòðèöà
32 32� ñ ìàòðèöàìè 4 4� P4 ÄÈÏ è G4 :
P I P1 17 15� diag [ ,
~
]; P P P2 2 2 2 1� , , , P I P2 1 21 10 1, [ ,
~
, ]� diag ,
P I P I2 2 17 6 9, [ ,
~
, ]� diag ;
P I P G3 20 7 41� diag [ ,
~
, , ]; P I I I P I I4 12 4 3 4 3 41 1� diag [ , , , ,
~
, , , ];
P G P G I P5 4 8 4 2 8� � � �diag [ , , , ]; � �P P G8 4 4diag [ , ].
Ïðè ýòîì
~
P
I I
I
I I
k k6
3
0
3
1
3
1
3
0
� �
�
�
�
, k �1 4 9, , ,
~
P
I I
I I
6
3
0
3
1
3
1
3
0
�
�
�
�
,
~
P4
1
1
1
1
�
�
�
�
, P4
1
1
1
1
�
�
�
�
,
G4
1
1
1
1
�
�
�
�
, I
3
0
0
1
0
�
�
�
�
, I
3
1
1
0
1
�
�
�
�
, I Ik k� antidiag [ ], I k �
�
�
�
1
1
1
�
.
Çäåñü I k — àíòèäèàãîíàëüíàÿ åäèíè÷íàÿ ìàòðèöà k k� .
Ìàòðèöà ICT32
� ðàçìåðà 32 32� ïðîñòîãî ÖÊÏ (1) ñ ïåðåñòàâëåííûìè ñòðîêà-
ìè ìîæåò áûòü ïðåäñòàâëåíà ìàòðèöåé ÿäðà ïðîñòîãî ÖÊÏ:
ICT B C32 32 32
� �� , (2)
ãäå C32
� — ìàòðèöà 32 32� ÿäðà ìàñøòàáèðîâàííîãî ïðîñòîãî ÖÊÏ ñ ïåðåñòàâëåí-
íûìè ñòðîêàìè, B32 — äèàãîíàëüíàÿ ìàòðèöà 32 32� êîýôôèöèåíòîâ íîðìèðîâàíèÿ.
Ìàòðèöà C32
� (2) ìîæåò áûòü ïðåäñòàâëåíà ðåêóððåíòíûì ìåòîäîì:
C C I T H32 16 16 16 32
� � �� diag [ ,
~
] , (3)
ãäå C16
� — ìàòðèöà 16 16� ÿäðà ÖÊÏ ñ ïåðåñòàâëåííûìè ñòðîêàìè íà îñíîâå
ÄÈÏ, ÎÏ è ÏÊÃ; T16 — ìàòðèöà 16 16� ÿäðà ïðîñòîãî ÖÊÏ òèïà IV (ÖÊÏ-IV)
ñ ïåðåñòàâëåííûìè ñòðîêàìè;
~
I16 — äèàãîíàëüíàÿ åäèíè÷íàÿ ìàòðèöà 16 16�
ñ åäèíè÷íûìè ìàòðèöàìè 12 12� I12 è 4 4� � I 4 ,
~
[ , ]I I I16 12 4� �diag ; H 32
* —
ôàêòîð-ìàòðèöà 32 32� ñ íåíóëåâûìè ýëåìåíòàìè �1,
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2018, òîì 54, ¹ 3 167
168 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2018, òîì 54, ¹ 3
H
I I
I I
32
16 16
16 16
� �
�
�
�
�
, I I16 16� antidiag [ ],
(4)
I16 , I16 — åäèíè÷íàÿ è àíòèäèàãîíàëüíàÿ åäèíè÷íàÿ ìàòðèöû 16 16� .
Ìàòðèöà T16 ìîæåò áûòü ïðåäñòàâëåíà ðåêóððåíòíî êàê ïðîèçâåäåíèå òðåõ
ìàòðèö:
T Q T H P16 8 8 16 16� � �diag [ , ] , (5)
ãäå �H16 — ôàêòîð-ìàòðèöà 16 16� ñ íåíóëåâûìè ýëåìåíòàìè �1; � � � �H H I16 2 8 ,
� �
�
�
�
�
H 2
1 1
1 1
, I 8 — åäèíè÷íàÿ ìàòðèöà 8 8� , � — îïåðàöèÿ êðîíåêåðîâñêîãî
ïðîèçâåäåíèÿ ìàòðèö; �P16 — ìàòðèöà 16 16� îáðàòíûõ ñîâåðøåííûõ ïåðåñòà-
íîâîê [15], � �P16 0 15 0 2 4 14 1 3 15( , ) ( , , , , , , , , )� � ; Q T8 8, — ìàòðèöû 8 8� , êîòî-
ðûå ìîãóò áûòü ïðåäñòàâëåíû ìàòðèöåé ÿäðà ÖÊÏ òèïà IV (ÖÊÏ-IV)
è ÖÊÏ-²² (ÖÊÏ) ñîîòâåòñòâåííî:
Q C I8 8 8� �IV , T I C8 8 8�
~ * . (6)
Çäåñü C8
� — ìàòðèöà 8 8� ÿäðà ÖÊÏ ñ ïåðåñòàâëåííûìè ñòðîêàìè íà îñíîâå
ÄÈÏ è ÏÊÃ, C G P C8 8 8 8
� �
~
,
~
G8 — áëî÷íî-äèàãîíàëüíàÿ ìàòðèöà 8 8� ñ ìàòðè-
öàìè 4 4� G4 , P4 ;
~
[ , ]G G P8 4 4� diag ; P8 — ìàòðèöà 8 8� ÄÈÏ,
~
I 8 — äèàãî-
íàëüíàÿ ìàòðèöà 8 8� ñ ìàòðèöàìè 4 4� � I 4 ;
~
[ , ]I I I8 4 4� �diag , I 8 — àíòèäè-
àãîíàëüíàÿ åäèíè÷íàÿ ìàòðèöà 8 8� ; C
8
IV� — ìàòðèöà ÿäðà ÖÊÏ-IV ñ ïåðå-
ñòàâëåííûìè ñòðîêàìè íà îñíîâå ÄÈÏ è ÏÊÃ:
C G P P C
8 8 8 8 8
IV IV� � � , (7)
ãäå P8 — áëî÷íî-äèàãîíàëüíàÿ ìàòðèöà 8 8� ñ ìàòðèöàìè 4 4� I 4 è I 4 ;
P I I8 4 4� diag [ ]; �G8 — áëî÷íî-äèàãîíàëüíàÿ ìàòðèöà 8 8� ñ ìàòðèöàìè 4 4� G4 ,
� �G G G8 4 4diag [ , ].
Îòìåòèì, ÷òî ìàòðèöà T16 ñîãëàñíî (5) è ñ ó÷åòîì (6) ìîæåò áûòü ïðåäñòàâ-
ëåíà ñëåäóþùèì îáðàçîì:
T C I I C H P16 8 8 8 8 16 16� � �� �diag IV[ ,
~
] . (8)
Ìàòðèöà C8
� ÿäðà ÖÊÏ ñîäåðæèò öåëûå ýëåìåíòû � a, � b, � c, � d, � � �e f g, , ,
� h, � k , à ìàòðèöà C
8
IV� ÿäðà ÖÊÏ-IV (7) ñîäåðæèò öåëûå ýëåìåíòû �A, � B, �C,
D E F G H Ai, , , , ,� � � , � �B Ci i, , i �1 8, .
Ìàòðèöû C8è C
8
IV� ìîãóò áûòü ïðåäñòàâëåíû ñëåäóþùèì îáðàçîì [15]:
C
k k k k k k k k
a b c d d c b a
i j j i i j j i
e f g h h g f e
k k8 �
� � � �
� � � �
� � � �
� � � �
� � � �
� � � �
� � � �
�
k k k k k k
h g f e e f g h
j i i j j i i j
d c b a a b c d
�
�
, (9)
C
A B C D E F G H
C C C C C C C C
A A A A A A A
8
8 7 6 5 4 3 2 1
8 7 6 5 4 3
IV� �
� � � �
� � � 2 1
1 2 3 4 5 6 7 8
1 2 3 4 5 6
A
B B B B B B B B
H G F E D C B A
C C C C C C C
� � �
� � � �
� � � 7 8
1 2 3 4 5 6 7 8
8 7 6 5 4 3 2 1
�
� � � � �
� � �
�
C
A A A A A A A A
B B B B B B B B
�
�
, (10)
ãäå a b c d� � � , i j� , g e h f� � � , A B C D E F G H� � � � � � � .
Ìàòðèöà C16 ÿäðà ÖÊÏ ïîðÿäêà 16 ïðåäñòàâëåíà â ðàáîòå [15]. Ìàòðèöà C32
ÿäðà ïðîñòîãî ÖÊÏ ïîðÿäêà 32 íà îñíîâàíèè (3)–(6), (8) ñ ó÷åòîì (9), (10) è ìàò-
ðèöû C16 èç [15] ìîæåò áûòü ïðåäñòàâëåíà ñëåäóþùèì îáðàçîì:
(11)
Ýëåìåíòû ìàòðèöû C32 ñîãëàñíî (11) ïðåäëîæåííîãî îäíîíîðìîâîãî ìàñ-
øòàáèðîâàííîãî ïðîñòîãî ÖÊÏ ñ ó÷åòîì îäíîíîðìîâîãî ìàñøòàáèðîâàííîãî
ÖÊÏ ïîðÿäêà 16 èç ðàáîòû [15] ïðèíèìàþò ñëåäóþùèå çíà÷åíèÿ: À �180,
 �172, Ñ �160, D �140, E �116, F � 84, G � 56, H � 20, a �180, b �152, c � 96,
d � 36, e �152, f � 36, g �176, h �100, i �172, j � 56, k �128. Çíà÷åíèÿ ýëåìåíòîâ
Ai , Bi , Ci (i �1 8, ) ïðåäñòàâëåíû â òàáë. 1.
Áàçèñíûå âåêòîðû ìàòðèöû C32 èìåþò íîðìó, êâàäðàò êîòîðîé ïðèáëèæàåò-
ñÿ ê ÷èñëó ñòåïåíè äâà: q Ci i i� � �| | | | 2 524288 � (� i (%) — îòêëîíåíèå ïàðà-
ìåòðà qi ), � i � 0,11–0,7, i �1 31, .
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2018, òîì 54, ¹ 3 169
Ò à á ë è ö à 1
Ýëåìåíòû
ìàòðèöû C32
Çíà÷åíèÿ ýëåìåíòîâ ìàòðèöû C32 ïðè i
1 2 3 4 5 6 7 8
Ai 174 116 18 87 159 180 139 48
Bi 160 11 138 173 55 117 181 85
Ci 141 82 172 16 181 53 161 113
Òàêèì îáðàçîì, ïðåäëîæåííîå ïðîñòîå ÖÊÏ èìååò òàêèå æå ñâîéñòâà, êàê
è ÖÊÏ, ïðèíÿòîå â ñòàíäàðòå Í.265: êîýôôèöèåíòû ïðåîáðàçîâàíèÿ ïðåäñòàâëåíû
8 áèòàìè; áèòîâàÿ øèðèíà íàêîïèòåëüíîãî ñóììàòîðà äëÿ ìàòðè÷íîãî óìíîæåíèÿ
íå ïðåâûøàåò 32 áèò; ñèììåòðè÷íîñòü/àíòèñèììåòðè÷íîñòü òàêàÿ æå, êàê â ÄÊÏ;
êîýôôèöèåíòû ìàñøòàáèðîâàííîãî ïðåîáðàçîâàíèÿ áëèçêè ê ÄÊÏ; íåîðòîãîíàëü-
íîñòü áàçèñíûõ âåêòîðîâ ñîñòàâëÿåò 0,01–0,26 %; îäèíàêîâàÿ ñõåìà êâàíòîâàíèÿ è
äåêâàíòîâàíèÿ äëÿ ïðåîáðàçîâàíèé âñåõ ðàçìåðíîñòåé; ìíîæèòåëè çàâèñÿò îò çíà-
÷åíèé ïàðàìåòðà êâàíòîâàíèÿ QP [16] è ñäâèãè çàâèñÿò òîëüêî îò log 2 N , ãäå N —
ðàçìåðíîñòü ïðåîáðàçîâàíèÿ; êîýôôèöèåíòû êâàíòîâàíèÿ ìîãóò áûòü ïðåäñòàâëå-
íû 16 áèòàìè.
ÀËÃÎÐÈÒÌ ÁÛÑÒÐÎÃÎ ÏÐßÌÎÃÎ ÖÊÏ ÏÎÐßÄÊÀ 8
Ìàòðèöà C8
* ìîæåò áûòü ôàêòîðèçîâàíî ïðåäñòàâëåíà êàê ïðîèçâåäåíèå ÷åòû-
ðåõ ìàòðèö:
C C C C C8 8 4 8 3 8 2 8 1
*
, , , ,� , (12)
ãäå C i8, , — i-å, i �1 4, , ôàêòîð-ìàòðèöû 8 8� àëãîðèòìà áûñòðîãî ïðÿìîãî ÖÊÏ
èç ðàáîòû [15]:
C H8 1 8, � � , C H R8 2 4 4, [ , ]� �diag , (13)
C T Q H8 3 2 2 4, [ , , ]� diag , C I H8 4 4 4
0
, [ , ]� diag ,
R
d a
c b
b c
a d
4 �
�
�
�
�
�
, H4
1 1
1 1
1 1
1 1
�
�
�
�
�
�
, T
k k
k k2 �
�
�
�
�
, Q
i j
j i2 �
��
�
�
, H4
0
1
1 1
1 1
1
�
�
�
�
�
.
Çäåñü H k2
� — ôàêòîð-ìàòðèöà 2 2k k� ñ íåíóëåâûìè ýëåìåíòàìè �1,
H
I I
I I
k
k k
k k
2
� �
�
�
�
�
, k � 2 4, .
Äëÿ îäíîíîðìîâîãî ÖÊÏ ìàòðèöà H
4
0 ñîäåðæèò íåíóëåâûå ýëåìåíòû 1 è � p m/ 2 .
ÀËÃÎÐÈÒÌ ÁÛÑÒÐÎÃÎ ÏÐßÌÎÃÎ ÏÐÎÑÒÎÃÎ ÖÊÏ ÏÎÐßÄÊÀ 16
Ìàòðèöà C16
� ìîæåò áûòü ôàêòîðèçîâàíî ïðåäñòàâëåíà êàê ïðîèçâåäåíèå ïÿòè
ìàòðèö:
C C C C C C16 16 5 16 4 16 3 16 2 16 1
� � , , , , , , (14)
ãäå C i16, — i-å, i �1 5, , ôàêòîð-ìàòðèöû 16 16� àëãîðèòìà áûñòðîãî ïðÿìîãî
ÖÊÏ èç ðàáîòû [15]:
C H16 1 16, � � , C H R16 2 8 8, [ , ]� �diag , C H R H H16 3 4 4 4 4, [ , , , ]� � � �diag ,
(15)
C T Q H T R T R16 4 2 2 4 2 2 2 2, [ , , , , , , ]� � �diag , C I H H16 5 4 4
0
8
0
, [ , , ]� diag ,
R
s r
s r
s r
s r
r s
r s
r s
r s
8
1 1
2 2
3 3
4 4
4 4
3 3
2 2
1 1
�
�
�
�
�
�
�
�
, H
8
0
1 0
1 1
1 0 1
1 1 0
0 1
1 1
0 1 1
1 0 1
�
�
�
�
�
�
�
, (16)
170 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2018, òîì 54, ¹ 3
� �
�
�
�
�
T
p p
p p
2 , R
r s
s r
2 �
��
�
�
, r s� , r ri i� �1, p n� 2 , s si i� �1, i �1 4, .
Ýëåìåíòû ri , si , i �1 4, , ìàòðèöû R8 ïðèíèìàþò ñëåäóþùèå çíà÷åíèÿ: r1 45� ,
r2 43� , r3 40� , r4 35� , s1 5� , s2 14� , s3 21� , s4 29� ; ýëåìåíòû ìàòðèö R2 , �T2
ïðèíèìàþò çíà÷åíèÿ r � 5, s � 2 è p � 4.
Äëÿ îäíîíîðìîâîãî ÖÊÏ ìàòðèöà H
8
0 ñîäåðæèò íåíóëåâûå ýëåìåíòû: åäè-
íèöó è � pi
mi/ 2 , i �1 3, .
ÀËÃÎÐÈÒÌ ÁÛÑÒÐÎÃÎ ÏÐßÌÎÃÎ ÏÐÎÑÒÎÃÎ ÖÊÏ ÏÎÐßÄÊÀ 32
Ìàòðèöà T8 íà îñíîâàíèè (6) è ñ ó÷åòîì (12), (13) ìîæåò áûòü ïðåäñòàâëåíà
êàê ïðîèçâåäåíèå ÷åòûðåõ ìàòðèö:
T T T T T8 8 4 8 3 8 2 8 1� , , , , , (17)
ãäå T i8, — i-e, i �1 4, , ôàêòîð-ìàòðèöû 8 8� :
T I H H8 1 8 8 8,
~
� �� , T Ck k8 8, ,� , k � 2 3 4, , , H
I I
I I
8
4 4
4 4
�
�
�
�
�
.
(18)
Ìàòðèöà Q8 èç (6) ìîæåò áûòü ïðåäñòàâëåíà êàê ïðîèçâåäåíèå òðåõ ìàòðèö [15]:
Q H T T R8 8
0
4 4 8� � �diag [ , ] , (19)
ãäå R8 — ìàòðèöà 8 8� ðàñòÿãèâàíèÿ (äëÿ ÄÊÏ-IV ïðåäñòàâëÿåò ìàòðèöó âðà-
ùåíèÿ Ãèâåíñà ïðè r si i
2 2 1� � ), êîòîðàÿ íà îñíîâíîé äèàãîíàëè ñîäåðæèò öåëûå
ýëåìåíòû �si , à íà äðóãîé äèàãîíàëè — öåëûå ýëåìåíòû �ri ( , )i �1 4 ; H
8
0 —
ôàêòîð-ìàòðèöà 8 8� ñ íåíóëåâûìè ýëåìåíòàìè �1; T4
� — ìàòðèöà 4 4� ÿäðà
ÖÊÏ ñ ïåðåñòàâëåííûìè ñòðîêàìè íà îñíîâå ÄÈÏ è ÏÊÃ è ñîäåðæèò öåëûå
ýëåìåíòû � r, �s è ð, T G P T4 4 4 4
� � .
Màòðèöà T4
� èìååò ñëåäóþùèé âèä:
T
p p p p
p p p p
s r r s
r s s r
4
� �
� �
� �
� �
�
�
�
. (20)
Ìàòðèöà T4
* ìîæåò áûòü ïðåäñòàâëåíà êàê ïðîèçâåäåíèå äâóõ ìàòðèö:
T T T4 4 2 4 1
� � , , , (21)
ãäå T i4, — i-å, i �1 2, , ôàêòîð-ìàòðèöû 4 4� :
T H4 1 4, � � , T T R4 2 2 2, [ , ]� �diag . (22)
Çäåñü R2 — ìàòðèöà 2 2� ðàñòÿãèâàíèÿ, êîòîðàÿ ñîäåðæèò öåëûå ýëåìåíòû �r
è s. Ìàòðèöû R2 è �T2 ïðåäñòàâëåíû â (16).
Ìàòðèöà Q8 íà îñíîâàíèè (19) è ñ ó÷åòîì (21), (22) ìîæåò áûòü ïðåäñòàâëå-
íà êàê ïðîèçâåäåíèå ÷åòûðåõ ìàòðèö:
Q Q Q Q Q8 8 4 8 3 8 2 8 1� , , , , , (23)
ãäå Q i8, — i-å, i �1 4, , ôàêòîð-ìàòðèöû 8 8� :
Q R8 1 8, � , Q H H8 2 4 4, [ , ]� � �diag , Q T R T R8 3 2 2 2 2, [ , , , ]� � �diag , Q H8 4 8
0
, � .(24)
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2018, òîì 54, ¹ 3 171
Îòìåòèì, ÷òî ìàòðèöà T16 íà îñíîâàíèè (5) è ñ ó÷åòîì (17), (23), (24) ìîæåò
áûòü ïðåäñòàâëåíà êàê ïðîèçâåäåíèå øåñòè ìàòðèö:
T T T T T T T16 16 6 16 5 16 4 16 3 16 2 16 1� , , , , , , , (25)
ãäå T i16, — i-å, i �1 6, , ôàêòîð-ìàòðèöû 16 16� :
T P16 1 16, � � , T H16 2 16, � � , T R H16 3 8 8, [ , ]� diag ,
T H H H R16 4 4 4 4 4, [ , , , ]� � � �diag , T T R T R T Q H16 5 2 2 2 2 2 2 4, [ , , , , , , ]� � �diag , (26)
T H I H16 6 8
0
4 4
0
, [ , , ]� diag .
Ìàòðèöà C32
� íà îñíîâàíèè (3), (25), (26) è ñ ó÷åòîì àëãîðèòìà áûñòðîãî
ïðÿìîãî ÖÊÏ ïîðÿäêà 16 ñîãëàñíî (14), (15) ìîæåò áûòü ôàêòîðèçîâàíî ïðåä-
ñòàâëåíà êàê ïðîèçâåäåíèå ñåìè ìàòðèö:
C C C C C C C C32 7 6 5 4 3 2 1
* � , (27)
ãäå Ci — i-å, i �1 7, , ôàêòîð-ìàòðèöû 32 32� ïðåäëîæåííîãî àëãîðèòìà áûñòðî-
ãî ïðÿìîãî ïðîñòîãî ÖÊÏ:
C H1 32� � , C I P2 16 16� �diag [ , ],
C C Tk k k� � �diag [ , ], ,16 2 16 1 , k � 3 7, .
ÀËÃÎÐÈÒÌ ÁÛÑÒÐÎÃÎ ÎÁÐÀÒÍÎÃÎ ÏÐÎÑÒÎÃÎ ÖÊÏ ÏÎÐßÄÊÀ 32
Ìàòðèöó C i32 ÿäðà îáðàòíîãî ïðîñòîãî ÖÊÏ ïîðÿäêà 32 ìîæíî ïîëó÷èòü
òðàíñïîíèðîâàíèåì:
C C ki32 32
� � T / . (28)
Ìàòðèöó C i32 íà îñíîâàíèè (28), (27) è ñ ó÷åòîì ñèììåòðè÷íîñòè ôàêòîð-ìàò-
ðèö (H H
32 32
� ��T , H H
4 4
� ��T , R R
4 4
T � , H H
4 4
T � , T T
2 2
T � , R R
2 2
T � , Q Q
2 2
T � )
ïðåäñòàâèì êàê ïðîèçâåäåíèå ñåìè ìàòðèö:
C C C C C C C Ci i i i i i i i32 1 2 3 4 5 6 7
� T T T T ,
ãäå C
ki
T — k-å, k �1 7, , òðàíñïîíèðîâàíûå ôàêòîð-ìàòðèöû 32 32� àëãîðèòìà
ïðåäëîæåííîãî áûñòðîãî îáðàòíîãî ïðîñòîãî ÖÊÏ:
C Hi1 32� � , C I Pi2 16 16
� �diag T[ , ],
C C T
ki i k i k
T T Tdiag�
� �
[ , ]
, ,16 2 16 1
, k � 3 7, .
Çäåñü C
i k16 ,
T — k-å òðàíñïîíèðîâàííûå ôàêòîð-ìàòðèöû 16 16� àëãîðèòìà áû-
ñòðîãî îáðàòíîãî ÖÊÏ, êîòîðûå ïðåäñòàâëåíû â [15]. Ïðè ýòîì òðàíñïîíèðî-
âàííûå ìàòðèöû ïîðÿäêà 8 è 4 èìåþò âèä
R
s r
s r
s r
s r
r s
r s
r s
r s
i8
1 1
2 2
3 3
4 4
4 4
3 3
2 2
1 1
T �
�
�
�
�
�
�
�
�/ k , H
8
0
1 0
1 1
1 0 1
1 1 0
0 1
1 1
0 1 1
1 0 1
T �
�
�
�
�
�
�
,
172 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2018, òîì 54, ¹ 3
R
d a
c b
b c
a d
k
i4
T �
�
�
�
�
�
/ , H
I I
I I8
4 4
4 4
T �
��
�
�
.
Äëÿ îäíîíîðìîâîãî îáðàòíîãî ïðåîáðàçîâàíèÿ ìàòðèöà H
8
0T ñîäåðæèò íå-
íóëåâûå ýëåìåíòû: åäèíèöó è � pki
mk/ 2 , k �1 3, , pki — öåëûå.
ÐÅÀËÈÇÀÖÈß ÁÛÑÒÐÎÃÎ ÖÅËÎ×ÈÑËÅÍÍÎÃÎ ÏÐÅÎÁÐÀÇÎÂÀÍÈß
ÁÅÇ ÌÍÎÆÈÒÅËÅÉ
Ïðè ðåàëèçàöèè áûñòðûõ öåëî÷èñëåííûõ ïðåîáðàçîâàíèé èñïîëüçóþòñÿ îïåðà-
öèè «áàáî÷êà» (butterfly), ãäå âûïîëíÿþòñÿ ïàðíûå óìíîæåíèÿ, êîòîðûå ìîãóò
áûòü ðåàëèçîâàíû îïåðàöèÿìè òîëüêî ñäâèãà è ñëîæåíèÿ, íî â íåêîòîðûõ ñëó-
÷àÿõ (â öåëÿõ óìåíüøåíèÿ âû÷èñëèòåëüíîé ñëîæíîñòè) è îïåðàöèè óìíîæåíèÿ.
Äëÿ ðåàëèçàöèè ïðåäëîæåííîãî 1D 32-òî÷å÷íîãî áûñòðîãî îäíîíîðìîâîãî
ïðîñòîãî öåëî÷èñëåííîãî êîñèíóñíîãî ïðåîáðàçîâàíèÿ èñïîëüçóþòñÿ â îñíîâíîì
îïåðàöèè ñäâèãà, ñëîæåíèÿ è â íåêîòîðûõ ñëó÷àÿõ óìíîæåíèÿ.
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2018, òîì 54, ¹ 3 173
Ò à á ë è ö à 2
Ìíîæèòåëè îïåðàöèé
«áàáî÷êà»
Àëãîðèòì âûïîëíåíèÿ
îïåðàöèé:
y s xi� � ;
z r xi� �
×èñëî îïåðàöèé
äëÿ ðåàëèçàöèè
«áàáî÷êà»
Êîëè÷åñòâî
èñïîëüçóåìûõ
îïåðàöèé
Ñëîæåíèå Ñäâèã
Óìíî-
æåíèå
d � 9 32/ a � 45 32/
x x x1 3� � ( )� ;
y x� 1 2� ; z x y� �1
2 2 — 4
c � 24 32/ b � 38 32/
y x x� � ( )� 2 ;
z x y� � ( )� 2
2 2 — 4
i � 43 32/ j � 14 32/
x x x1 3� � ( )� ; z x� 1 1� ;
x x x2 1� � ;
y x x� �1 2 2( )�
3 3 — 4
s1 5 32� / r1 45 32� /
x x1 2� � ; x x x2 1� � ;
y x� 2 3� ; z x y� �1
2 2 — 4
s2 14 32� / r2 43 32� /
x x x1 3� � ( );� y x� 1 1� ;
x x x2 1� � ; z x x� �1 2 2( )�
3 3 — 4
s3 21 32� / r3 40 32� /
x x1 2� � ; z x x� � 1;
x z2 3� � ; y x x� �2 1( )�
2 3 — 4
s4 29 32� / r4 35 32� /
x x x1 2� � ( );�
y x x� � ( )1 3� ;
z x x� � ( )1 3�
3 2 — 4
r � 5 4/ s � 2 4/ z x� �1; y x x� � ( )� 2 1 2 — 8
p pi
m� / 2 0
x p x1 � � ; y x m� 1� ;
z � 0
— 1 1 4
p pi
m
1 1 2 1� / 0
x p x1 1� � ; y x m� 1 1� ;
z � 0
— 1 1 4
p pi
m
2 2 2 2� / 0
x p x1 2� � ; y x m� 1 2� ;
z � 0
— 1 1 4
p pi
m
3 3 2 3� / 0
x p x1 3� � ; y x m� 1 3� ;
z � 0
— 1 1 4
Âñåãî îïåðàöèé 76 100 16 —
 òàáë. 2 ïðåäñòàâëåíà ñõåìà âûïîëíåíèÿ ñïåöèàëüíûõ ïàðíûõ óìíîæåíèé,
èñïîëüçóåìûõ â îïåðàöèÿõ «áàáî÷êà», äëÿ ðåàëèçàöèè ïðåäëîæåííîãî 1D 32-òî-
÷å÷íîãî áûñòðîãî îáðàòíîãî öåëî÷èñëåííîãî ïðåîáðàçîâàíèÿ. Äëÿ òàêîé ðåàëè-
çàöèè òðåáóåòñÿ âûïîëíèòü 16 îïåðàöèè óìíîæåíèÿ, 248 îïåðàöèé ñëîæåíèÿ
è 100 îïåðàöèé ñäâèãà.
Âû÷èñëèòåëüíàÿ ñëîæíîñòü ïðåäëîæåííîãî, èçâåñòíûõ [9,10] è èñïîëüçóå-
ìîãî â ñòàíäàðòå Í.265 [5, 6] 2D 32-òî÷å÷íûõ öåëî÷èñëåííûõ îáðàòíûõ ïðåîáðà-
çîâàíèé îòðàæåíà â òàáë. 3.
ÝÊÑÏÅÐÈÌÅÍÒÀËÜÍÛÅ ÐÅÇÓËÜÒÀÒÛ È ÈÕ ÀÍÀËÈÇ
Èñõîäíûå èçîáðàæåíèÿ êëàññîâ À è Â äëÿ òåñòèðîâàíèÿ ïðåäñòàâëåíû â ðàáî-
òå [7]. Â òàáë. 4 äàíû ýêñïåðèìåíòàëüíûå ðåçóëüòàòû ýôôåêòèâíîñòè êîäèðî-
âàíèÿ ïî õàðàêòåðèñòèêå ñòàíäàðòíîé êîëè÷åñòâåííîé îöåíêè èñêàæåíèé
PSNR (äÁ) äëÿ ñæàòûõ òåñòîâûõ èçîáðàæåíèé êëàññà À ñ ðàçðåøàþùåé ñïî-
ñîáíîñòüþ 2560 1600� ïèêñåëåé è êëàññà Â — 1920 1056� ïèêñåëåé ïðè íîð-
ìàëüíîì (22–37) äèàïàçîíå QP è çíà÷åíèÿõ (37, 42) âûñîêîãî äèàïàçîíà QP
äëÿ ïðåäëîæåííîãî 2D ïðåîáðàçîâàíèÿ ñ áëîêàìè 32 32� . Ýòè ðåçóëüòàòû
ïðåäñòàâëÿþò ðàçíîñòü íà îñíîâå ïðåäëîæåííîãî ïðåîáðàçîâàíèÿ è íà îñíîâå
ïðåîáðàçîâàíèÿ Í.265. Äèàïàçîíû ïàðàìåòðà QP íèçêèé (1–13), íîðìàëüíûé
(22–37) è âûñîêèé (36–51) îïðåäåëåíû â [16].
Ðåçóëüòàòû ýôôåêòèâíîñòè êîäèðîâàíèÿ ïî êðèòåðèþ îöåíêè ñðåäíåêâàäðà-
òè÷åñêîãî îòêëîíåíèÿ (ÑÊÎ, â óðîâíÿõ ÿðêîñòè) ðàçíîñòè âõîäíîãî è âîññòàíîâ-
ëåííîãî èçîáðàæåíèé äëÿ ïðåäëîæåííîãî 2D ïðåîáðàçîâàíèÿ ñ áëîêàìè 32 32� ,
ïðåäñòàâëÿþùèå ðàçíîñòü íà îñíîâå ïðåîáðàçîâàíèÿ Í.265 è íà îñíîâå ïðåäëî-
æåííîãî ïðåîáðàçîâàíèÿ ïðèâåäåíû â òàáë. 5.
Ýêñïåðèìåíòàëüíûå ðåçóëüòàòû êîäèðîâàíèÿ ïî êîýôôèöèåíòó ñæàòèÿ K :1
äëÿ ïðåäëîæåííîãî 2D ïðåîáðàçîâàíèÿ ñ áëîêàìè 32 32� ïðèâåäåíû â òàáë. 6. Ðå-
çóëüòàòû ýôôåêòèâíîñòè êîäèðîâàíèÿ ïî êîýôôèöèåíòó ñæàòèÿ K (â %), ïðåä-
ñòàâëÿþùèå ðàçíîñòü íà îñíîâå ïðåäëîæåííîãî ïðåîáðàçîâàíèÿ è íà îñíîâå
ïðåîáðàçîâàíèÿ Í.265, ïðèâåäåíû â òàáë. 7.
174 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2018, òîì 54, ¹ 3
Ò à á ë è ö à 3
Îïåðàöèè è
õàðàêòåðèñòèêà
âû÷èñëèòåëüíîé
ñëîæíîñòè
Îöåíêà âû÷èñëèòåëüíîé ñëîæíîñòè
2D îáðàòíûõ ïðåîáðàçîâàíèé
ñ áëîêàìè 32 32�
Ñðàâíèòåëüíûé àíàëèç
õàðàêòåðèñòèê
ïðåîáðàçîâàíèé
Ïðåäëî-
æåííîå
ïðåîáðàçîâàíèå
Èçâåñòíûå ïðåîáðàçîâàíèÿ
Í.265
èç [5, 6]
èç [9] èç [10]
îòíîñèòåëüíî
[9] ([10])
îòíîñèòåëüíî
Í.265
Óìíîæåíèå 1024 21888 5888 5568
 5,44
(â 5,75) ðàçà
ìåíüøå
 21,4 ðàçà
ìåíüøå
Ñëîæåíèå � ñäâèã 22272 25856 11904 14656
Íà 51,96 %
(íà 87 %)
áîëüøå
ñëîæåíèé
Íà 16,1 %
ìåíüøå
ñëîæåíèé
×èñëî èòåðàöèé
äëÿ 1D
6 5 7 8
Íà 1 (íà 2)
èòåðàöèþ
ìåíüøå
Íà 1 èòåðà-
öèþ áîëüøå
×èñëî áèòîâ
ýëåìåíòà
ìàòðèöû
9 8 11 14
Íà 2 (íà 5)
áèòà ìåíüøå
Íà 1 áèò
áîëüøå
Îáùåå
óìåíüøåíèå
—
 4,9 (â 4,88)
ðàçà ìåíüøå
 21,6 ðàçà
ìåíüøå
 òàáëèöàõ äàíû ñðåäíèå çíà÷åíèÿ ýêñïåðèìåíòàëüíûõ ðåçóëüòàòîâ ýôôåê-
òèâíîñòè êîäèðîâàíèÿ ïî õàðàêòåðèñòèêàì PSNR, ÑÊÎ è êîýôôèöèåíòó ñæàòèÿ K
ïî ÷åòûðåì òåñòîâûì èçîáðàæåíèÿì êëàññîâ À è Â.
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2018, òîì 54, ¹ 3 175
Ò à á ë è ö à 4
Êëàññ
Èçîáðàæåíèå
ñ áëîêàìè 32 32�
Ðåçóëüòàòû ýôôåêòèâíîñòè êîäèðîâàíèÿ
ïî õàðàêòåðèñòèêå PSNR (äÁ) äëÿ QP
22 27 32 37 42
À
2560 1600�
Ôîòî 1 � 0,43 � 0,42 � 0,35 � 0,25 � 0,15
Õðàì � 0,33 � 0,44 � 0,53 � 0,54 � 0,47
B
1920 1056�
Ôîòî 2 � 0,22 � 0,22 � 0,24 � 0,22 � 0,14
Ïåéçàæ � 0,09 � 0,14 � 0,25 � 0,35 � 0,33
Ñðåäíåå çíà÷åíèå � 0,268 � 0,305 � 0,343 � 0,340 � 0,273
Ò à á ë è ö à 5
Êëàññ
Èçîáðàæåíèå
ñ áëîêàìè 32 32�
Ðåçóëüòàòû ýôôåêòèâíîñòè êîäèðîâàíèÿ
ïî õàðàêòåðèñòèêå ÑÊÎ (â óðîâíÿõ ÿðêîñòè) äëÿ QP
22 27 32 37 42
À
2560 1600�
Ôîòî 1 � 0,21 � 0,31 � 0,47 � 0,54 � 0,53
Õðàì � 0,25 � 0,72 �1,81 � 4,04 � 7,15
B
1920 1056�
Ôîòî 2 � 0,18 � 0,34 � 0,56 � 0,75 � 0,70
Ïåéçàæ � 0,11 � 0,38 �1,32 � 3,48 � 5,54
Ñðåäíåå çíà÷åíèå � 0,188 � 0,438 �1,040 � 2,203 � 3,480
Ò à á ë è ö à 6
Êëàññ
Èçîáðàæåíèå
ñ áëîêàìè 32 32�
Ðåçóëüòàòû êîäèðîâàíèÿ ïî êîýôôèöèåíòó
ñæàòèÿ K :1 äëÿ QP
22 27 32 37 42
À
2560 1600�
Ôîòî 1 11,27 23,36 45,21 91,32 177,94
Õðàì 3,91 5,74 8,92 16,06 31,62
Â
1920 1056�
Ôîòî 2 5,93 14,40 34,87 82,17 179,86
Ïåéçàæ 2,49 4,45 8,49 18,57 43,37
Ñðåäíåå çíà÷åíèå 5,900 11,988 24,373 52,030 108,198
Ò à á ë è ö à 7
Êëàññ
Èçîáðàæåíèå
ñ áëîêàìè 32 32�
Ðåçóëüòàòû ýôôåêòèâíîñòè êîäèðîâàíèÿ ïî êîýôôèöèåíòó
ñæàòèÿ K (â %) äëÿ QP
22 27 32 37 42
À
2560 1600�
Ôîòî 1 � 0,78 � 0,22 � 0,05 0,0 0,01
Õðàì � 2,94 � 2,13 � 1,23 � 0,51 � 0,12
Â
1920 1056�
Ôîòî 2 � 0,89 � 0,35 � 0,10 0,01 0,01
Ïåéçàæ � 2,01 � 1,71 �1,05 � 0,32 � 0,02
Ñðåäíåå çíà÷åíèå �1,655 �1,102 � 0,607 � 0,205 � 0,03
Ïðåäëîæåííîå ïðîñòîå öåëî÷èñëåííîå êîñèíóñíîå ïðåîáðàçîâàíèå ïîðÿä-
êà 32 ïî ñðàâíåíèþ ñ ïðåîáðàçîâàíèåì â ñòàíäàðòå Í.265 ïî õàðàêòåðèñòèêå
PSNR äëÿ ÷åòûðåõ òåñòîâûõ èçîáðàæåíèé êëàñîâ À è  ïîíèæàåò ñðåäíåå çíà÷å-
íèå íà 0,268–0,343 äÁ, à ïî õàðàêòåðèñòèêå ÑÊÎ ïîâûøàåò ñðåäíåå çíà÷åíèå íà
0,188–3,48 óðîâíåé ÿðêîñòè. Ïðè ýòîì ñðåäíåå çíà÷åíèå êîýôôèöèåíòà ñæàòèÿ K
óìåíüøàåòñÿ íà 0,03–1,655 %. Ñîãëàñíî ïðèíÿòîãî Êîìèòåòîì MPEG èñïîëüçóå-
ìîãî ñóáúåêòèâíîãî ïîðîãà PSNR � 0,5 äÁ ïðè ïðèíÿòèè êîäîâîé îïòèìèçàöèè
ñ÷èòàåòñÿ, ÷òî óâåëè÷åíèå èëè óìåíüøåíèå PSNR íà ýòó âåëè÷èíó áóäåò çàìåòíî
âèçóàëüíî [17], à ïðè PSNR � 0,5 äÁ — çðèòåëüíî íå îùóùàåòñÿ. Òàêèì îáðàçîì,
ïîíèæåíèå íàèáîëüøåãî ñðåäíåãî çíà÷åíèÿ PSNR íà 0,343 äÁ áóäåò çðèòåëüíî
íåçàìåòíî, ò.å. ñîõðàíÿåòñÿ âèçóàëüíîå êà÷åñòâî èçîáðàæåíèÿ.
ÇÀÊËÞ×ÅÍÈÅ
Ïðåäëîæåí ìåòîä ïîñòðîåíèÿ ïðîñòîãî öåëî÷èñëåííîãî êîñèíóñíîãî ïðåîáðàçî-
âàíèÿ âûñîêîãî ïîðÿäêà. Íà îñíîâå ïðåäëîæåííîãî ìåòîäà ïîñòðîåíî îäíîíîð-
ìîâîå ïðîñòîå öåëî÷èñëåííîå ïðåîáðàçîâàíèå ïîðÿäêà 32 è ðàçðàáîòàíû åãî
áûñòðûå àëãîðèòìû íèçêîé âû÷èñëèòåëüíîé ñëîæíîñòè, êîòîðàÿ â 4,9 ðàçà
ìåíüøå, ÷åì â èçâåñòíûõ àëãîðèòìàõ [8, 9], è â 21,6 ðàçà ìåíüøå, ÷åì â ñòàí-
äàðòå Í.265. Ýòî ïðåîáðàçîâàíèå áëèçêî ê ÄÊÏ è èìååò õîðîøèå õàðàêòåðèñòè-
êè êîäèðîâàíèÿ: ñðåäíåå çíà÷åíèå ïîíèæåíèÿ ïî õàðàêòåðèñòèêå èñêàæåíèé
PSNR ñîñòàâëÿåò 0,268–0,343 äÁ, à ñðåäíåå çíà÷åíèå ïîâûøåíèÿ ïî õàðàêòåðèñ-
òèêå ÑÊÎ ñîñòàâëÿåò 0,188–3,48 óðîâíåé ÿðêîñòè. Ïðè ýòîì ñðåäíåå çíà÷åíèå
êîýôôèöèåíòà ñæàòèÿ óìåíüøàåòñÿ íà 0,03–1,655 %. Ñîãëàñíî àíàëèçó ïðåäëî-
æåííîå ïðåîáðàçîâàíèå îáåñïå÷èâàåò òàêîå æå âèçóàëüíîå êà÷åñòâî è êà÷åñòâî
ïî õàðàêòåðèñòèêàì PSNR, ÑÊÎ è êîýôôèöèåíòó ñæàòèÿ, êàê è ïðåîáðàçîâàíèå
â ñòàíäàðòå Í.265.
Òàêèì îáðàçîì, ðàçðàáîòàííîå ïðîñòîå öåëî÷èñëåííîå ïðåîáðàçîâàíèå ïî-
ðÿäêà 32 ìîæåò áûòü èñïîëüçîâàíî äëÿ óëó÷øåíèÿ íîâîãî ñòàíäàðòà Í.265 â öå-
ëÿõ óâåëè÷åíèÿ áûñòðîäåéñòâèÿ è óìåíüøåíèÿ âû÷èñëèòåëüíûõ è ýíåðãåòè÷åñ-
êèõ çàòðàò.
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. ITU-T Rec. H.264|ISO/IEC 14496-10: 2009. Information technology — Coding of audio-visual
objects. Part 10: Advanced video coding, 2009.
2. Ðè÷àðäñîí ß. Âèäåîêîäèðîâàíèå. Í.264 è MPEG-4 — ñòàíäàðòû íîâîãî ïîêîëåíèÿ. Ìîñêâà:
Òåõíîñôåðà, 2005. 368 ñ.
3. SMPTE standard 421 M-2006: VC-1 compressed video bitstream format and decoding process, 2006.
4. PRC National Standard (AVS Working Group) GB/T 20090.2-2006. Information technology —
advanced coding of audio and video. Part 2: Video, Chinese AVS standard, 2006.
5. ITU-T Rec. H.265|ISO/IEC 23008-2: 2013. Information technology — High efficiency coding and
media delivery in heterogeneous environments. Part 2: High efficiency video coding, 2013.
6. Fuldseth A., Bj �întegaard G., Budagavi M., Sze V. CE10: Core transform design for HEVC.
Doc. JCTVC-G495. Geneva, CH, Nov. 2011.
7. Ãíàòèâ Ë.À. Öåëî÷èñëåííîå êîñèíóñíîå ïðåîáðàçîâàíèå âûñîêîãî ïîðÿäêà: ìåòîä ïîñòðîåíèÿ
è áûñòðûå àëãîðèòìû äëÿ êîäèðîâàíèÿ èçîáðàæåíèé è âèäåî ñ âûñîêèì ðàçðåøåíèåì. Êèáåð-
íåòèêà è ñèñòåìíûé àíàëèç. 2017. Ò. 53, ¹ 4. Ñ. 141–154.
8. Joshi R., Reznik Y., Karczewicz M. Efficient large size transforms for high perfomance video
coding. Proc. SPIE Appl. of Digital Image Process. XXXIII. 2010. Vol. 7798. P. 779831–1–7.
9. Joshi R., Reznik Y., Sole J., Karczewicz M. Efficient 16 and 32-point transforms. Doc. JCTVC- D256.
Daegu, KR, Jan. 2011.
10. Alshina E., Alshin A., Kim I-K, Topiwala P. CE10: Full-factorized core transform proposal by
Samsung/FastVDO. Doc. JCTVC-F251. Torino, Italy, July 2011.
176 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2018, òîì 54, ¹ 3
11. Ãíàò³â Ë.Î. Ìåòîä ïîáóäîâè øâèäêèõ ö³ëî÷èñåëüíèõ êîñèíóñíèõ ïåðåòâîðåíü âåëèêî¿
ðîçì³ðíîñò³ äëÿ âèñîêîåôåêòèâíîãî êîäóâàííÿ çîáðàæåíü ³ â³äåî. Ïð. ì³æíàð. êîíô. «Ïèòàí-
íÿ îïòèì³çàö³¿ îá÷èñëåíü (ÏÎÎ-2013)», Óêðà¿íà, Êðèì, ñìò. Êàöèâåë³, âåðåñåíü 2013.
Ñ. 66–67.
12. Ãíàòèâ Ë.À. Ìåòîä ïîñòðîåíèÿ ïðîñòîãî öåëî÷èñëåííîãî êîñèíóñíîãî ïðåîáðàçîâàíèÿ áîëüøîé
ðàçìåðíîñòè äëÿ êîäèðîâàíèÿ èçîáðàæåíèé è âèäåî ñ âûñîêèì ðàçðåøåíèåì. Êèáåðíåòèêà
è ñèñòåìíûé àíàëèç. 2016. T. 52, ¹ 6. Ñ. 143–155.
13. Ãíàòèâ Ë.À. Öåëî÷èñëåííûå êîñèíóñíûå ïðåîáðàçîâàíèÿ: ìåòîäû ïîñòðîåíèÿ íîâûõ áûñòðûõ
ïðåîáðàçîâàíèé ïîðÿäêà 8, 16 è èõ ïðèìåíåíèå. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. 2014.
Ò. 50, ¹ 6. Ñ. 104–121.
14. Øåâ÷óê Á.Ì., Çàä³ðàêà Â.Ê., Ãíàò³â Ë.Î., Ôðàºð Ñ.Â. Òåõíîëîã³ÿ áàãàòîôóíêö³îíàëüíî¿ îáðîá-
êè ³ ïåðåäà÷³ ³íôîðìàö³¿ â ìîí³òîðèíãîâèõ ìåðåæàõ. Êè¿â: Íàóê. äóìêà, 2010. 378 ñ.
15. Ãíàòèâ Ë.À. Öåëî÷èñëåííûå êîñèíóñíûå ïðåîáðàçîâàíèÿ äëÿ âûñîêîýôôåêòèâíîãî êîäèðîâà-
íèÿ èçîáðàæåíèé è âèäåî. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. 2016. Ò. 52, ¹ 5. Ñ. 161–176.
16. Fuldseth A., Bj �ontegaard G., Sadafale M., Budagavi M. Transform design for HEVC with 16 bit
intermediate data representation. Doc. JCTVC-E243, Geneva, CH, Mar. 2011.
17. Ñýëîìîí Ä. Ñæàòèå äàííûõ, èçîáðàæåíèé è çâóêà. Ìîñêâà: Òåõíîñôåðà, 2004. 368 ñ.
Íàä³éøëà äî ðåäàêö³¿ 03.01.2017
Ë.Î. Ãíàò³â
ÏÐÎÑÒÅ Ö²ËÎ×ÈÑÅËÜÍÅ ÊÎÑÈÍÓÑÍÅ ÏÅÐÅÒÂÎÐÅÍÍß ÂÈÑÎÊÎÃÎ ÏÎÐßÄÊÓ
ÄËß Â²ÄÅÎÊÎÄÓÂÀÍÍß ÂÈÑÎÊί ÐÎÇIJËÜÍί ÇÄÀÒÍÎÑÒ²
Àíîòàö³ÿ. Çàïðîïîíîâàíî ìàòðè÷íèé ìåòîä ïîáóäîâè ïðîñòîãî ö³ëî÷èñåëü-
íîãî êîñèíóñíîãî ïåðåòâîðåííÿ âèñîêîãî ïîðÿäêó. Íà éîãî îñíîâ³ ïîáóäî-
âàíî îäíîíîðìîâå ïðîñòå ö³ëî÷èñåëüíå ïåðåòâîðåííÿ ïîðÿäêó 32 ³ ðîçðîáëå-
íî éîãî øâèäê³ àëãîðèòìè íèçüêî¿ îá÷èñëþâàëüíî¿ ñêëàäíîñò³, ÿêà ìåíøà
â 4,9 ðàçè, í³æ ó â³äîìèõ àëãîðèòìàõ, òà â 21,6 ðàçè, í³æ ó ñòàíäàðò³ Í.265.
Âîíè ïîòðåáóþòü ò³ëüêè ö³ëî÷èñåëüíèõ îïåðàö³é. Öå ïåðåòâîðåííÿ áëèçüêå
äî äèñêðåòíîãî êîñèíóñíîãî ïåðåòâîðåííÿ ³ ìຠäîáð³ õàðàêòåðèñòèêè êîäó-
âàííÿ.
Êëþ÷îâ³ ñëîâà: äèñêðåòíå êîñèíóñíå ïåðåòâîðåííÿ, ö³ëî÷èñåëüíå êîñèíóñíå
ïåðåòâîðåííÿ, ìàñøòàáîâàíå ïåðåòâîðåííÿ, ôàêòîðèçàö³ÿ, øâèäêå ïåðåòâîðåí-
íÿ, åôåêòèâí³ñòü êîäóâàííÿ, îá÷èñëþâàëüíà ñêëàäí³ñòü, êîåô³ö³ºíò ñòèñíåííÿ,
â³äåîêîäóâàííÿ, Í.264, H.265, AVS.
L.O. Hnativ
SIMPLE HIGH-ORDER INTEGER COSINE TRANSFORM FOR HIGH-RESOLUTION
VIDEO CODING
Abstract. A matrix method is proposed for constructing a simple order-32
integer cosine transform. Based on the method proposed, a one-norm simple
order-32 integer transform is constructed and its fast algorithms of low
computational complexity are developed that require only integer operations and
whose computational complexity is 4.9 times less than those of the well-known
algorithms and is 21.6 times less than that of the standard H.2 65. This
transform is close to the discrete cosine transform and has good coding
performance.
Keywords: discrete cosine transform, integer cosine transform, scaled transform,
factorization, fast transform, coding gain, computational complexity, compression
ratio, video coding, H.264, H.265, AVS.
Ãíàòèâ Ëåâ Àëåêñååâè÷,
êàíäèäàò òåõí. íàóê, ñòàðøèé íàó÷íûé ñîòðóäíèê Èíñòèòóòà êèáåðíåòèêè èì. Â.Ì. Ãëóøêîâà ÍÀÍ
Óêðàèíû, Êèåâ, e-mail: levhnativ@gmail.com.
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2018, òîì 54, ¹ 3 177
|