Целочисленные косинусные преобразования для высокоэффективного кодирования изображений и видео
Рассмотрены матричные методы построения однонормовых целочисленных косинусных преобразований порядков 8, 16. Предложены однонормовые целочисленные преобразования порядков 8, 16 и разработаны их быстрые алгоритмы низкой вычислительной сложности, которая меньше в 3–5 раз, чем в известных алгоритмах,...
Збережено в:
| Дата: | 2016 |
|---|---|
| Автор: | |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2016
|
| Назва видання: | Кибернетика и системный анализ |
| Теми: | |
| Онлайн доступ: | http://dspace.nbuv.gov.ua/handle/123456789/142024 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Целочисленные косинусные преобразования для высокоэффективного кодирования изображений и видео / Л.А. Гнатив // Кибернетика и системный анализ. — 2016. — Т. 52, № 5. — С. 161-176. — Бібліогр.: 18 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-142024 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-1420242018-09-21T01:23:09Z Целочисленные косинусные преобразования для высокоэффективного кодирования изображений и видео Гнатив, Л.А. Программно-технические комплексы Рассмотрены матричные методы построения однонормовых целочисленных косинусных преобразований порядков 8, 16. Предложены однонормовые целочисленные преобразования порядков 8, 16 и разработаны их быстрые алгоритмы низкой вычислительной сложности, которая меньше в 3–5 раз, чем в известных алгоритмах, и в 10 раз — чем в стандарте Н.265. Розглянуто матричні методи побудови однонормових цілочисельних косинусних перетворень порядків 8, 16. Запропоновано однонормові цілочисельні перетворення порядків 8, 16 та розроблено їхні швидкі алгоритми низької обчислювальної складності, яка менша в 3–5 разів, ніж у відомих алгоритмів, та в 10 разів менша, ніж у стандарті Н.265. Matrix methods of constructing one-norm integer cosine transforms of order-8,16 are considered. The one-norm order-8 and 16 integer transforms are proposed and their fast algorithms of low computational complexity are developed whose computational complexity is 3 to 5 time less than that in the well-known algorithms and is 10 time less than one in standard H.265. 2016 Article Целочисленные косинусные преобразования для высокоэффективного кодирования изображений и видео / Л.А. Гнатив // Кибернетика и системный анализ. — 2016. — Т. 52, № 5. — С. 161-176. — Бібліогр.: 18 назв. — рос. 0023-1274 http://dspace.nbuv.gov.ua/handle/123456789/142024 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 |
Рассмотрены матричные методы построения однонормовых целочисленных косинусных преобразований порядков 8, 16. Предложены однонормовые целочисленные преобразования порядков 8, 16 и разработаны их быстрые алгоритмы низкой вычислительной сложности, которая меньше в 3–5 раз, чем в известных алгоритмах, и в 10 раз — чем в стандарте Н.265. |
| format |
Article |
| author |
Гнатив, Л.А. |
| author_facet |
Гнатив, Л.А. |
| author_sort |
Гнатив, Л.А. |
| title |
Целочисленные косинусные преобразования для высокоэффективного кодирования изображений и видео |
| title_short |
Целочисленные косинусные преобразования для высокоэффективного кодирования изображений и видео |
| title_full |
Целочисленные косинусные преобразования для высокоэффективного кодирования изображений и видео |
| title_fullStr |
Целочисленные косинусные преобразования для высокоэффективного кодирования изображений и видео |
| title_full_unstemmed |
Целочисленные косинусные преобразования для высокоэффективного кодирования изображений и видео |
| title_sort |
целочисленные косинусные преобразования для высокоэффективного кодирования изображений и видео |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| publishDate |
2016 |
| topic_facet |
Программно-технические комплексы |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/142024 |
| citation_txt |
Целочисленные косинусные преобразования для высокоэффективного кодирования изображений и видео / Л.А. Гнатив // Кибернетика и системный анализ. — 2016. — Т. 52, № 5. — С. 161-176. — Бібліогр.: 18 назв. — рос. |
| series |
Кибернетика и системный анализ |
| work_keys_str_mv |
AT gnativla celočislennyekosinusnyepreobrazovaniâdlâvysokoéffektivnogokodirovaniâizobraženijivideo |
| first_indexed |
2025-07-10T13:59:06Z |
| last_indexed |
2025-07-10T13:59:06Z |
| _version_ |
1837268698269745152 |
| fulltext |
ÓÄÊ 681.391, 681.3, 621.372.397
Ë.À. ÃÍÀÒÈÂ
ÖÅËÎ×ÈÑËÅÍÍÛÅ ÊÎÑÈÍÓÑÍÛÅ
ÏÐÅÎÁÐÀÇÎÂÀÍÈß ÄËß ÂÛÑÎÊÎÝÔÔÅÊÒÈÂÍÎÃÎ
ÊÎÄÈÐÎÂÀÍÈß ÈÇÎÁÐÀÆÅÍÈÉ È ÂÈÄÅÎ
Àííîòàöèÿ. Ðàññìîòðåíû ìàòðè÷íûå ìåòîäû ïîñòðîåíèÿ îäíîíîðìîâûõ öå-
ëî÷èñëåííûõ êîñèíóñíûõ ïðåîáðàçîâàíèé ïîðÿäêîâ 8, 16. Ïðåäëîæåíû îä-
íîíîðìîâûå öåëî÷èñëåííûå ïðåîáðàçîâàíèÿ ïîðÿäêîâ 8, 16 è ðàçðàáîòàíû
èõ áûñòðûå àëãîðèòìû íèçêîé âû÷èñëèòåëüíîé ñëîæíîñòè, êîòîðàÿ ìåíüøå
â 3–5 ðàç, ÷åì â èçâåñòíûõ àëãîðèòìàõ, è â 10 ðàç — ÷åì â ñòàíäàð-
òå Í.265.
Êëþ÷åâûå ñëîâà: äèñêðåòíîå êîñèíóñíîå ïðåîáðàçîâàíèå, öåëî÷èñëåííîå êî-
ñèíóñíîå ïðåîáðàçîâàíèå, ôàêòîðèçàöèÿ, áûñòðîå ïðåîáðàçîâàíèå, ìàñøòàáè-
ðîâàííîå ïðåîáðàçîâàíèå, ýôôåêòèâíîñòü êîäèðîâàíèÿ, êîýôôèöèåíò ñæàòèÿ,
âû÷èñëèòåëüíàÿ ñëîæíîñòü, âèäåîêîäèðîâàíèå, Í.264, H.265, HEVÑ, AVS.
ÂÂÅÄÅÍÈÅ
 ïîñëåäíèå äåñÿòèëåòèÿ ìíîãî ïóáëèêàöèé áûëî ïîñâÿùåíî ñæàòèþ èçîáðà-
æåíèé è âèäåîêîäèðîâàíèþ íà îñíîâå ïðåîáðàçîâàíèé. Ýôôåêòèâíûìè èíñò-
ðóìåíòàìè êîìïðåññèè äëÿ óñòðàíåíèÿ èçáûòî÷íîñòè â èçîáðàæåíèÿõ è âèäåî-
ñèãíàëàõ ÿâëÿþòñÿ ìåòîäû ñæàòèÿ ðåçóëüòàòîâ ïðåîáðàçîâàíèÿ èçîáðàæåíèÿ,
ò.å. ìåòîäû êîäèðîâàíèÿ ñ ïðåîáðàçîâàíèåì.
Äëÿ ìàðêîâñêîãî ïðîöåññà ïåðâîãî ïîðÿäêà îïòèìàëüíûì ÿâëÿåòñÿ ïðåîáðà-
çîâàíèå Êàðóíåíà–Ëîåâà (ÏÊË). Íàèëó÷øèì ïðèáëèæåíèåì ê ÏÊË åñòü äèñ-
êðåòíîå êîñèíóñíîå ïðåîáðàçîâàíèå (ÄÊÏ). Õàðàêòåðèñòèêè ÄÊÏ ïðèáëèæàþòñÿ
ê ÏÊË, êîãäà êîýôôèöèåíò êîððåëÿöèè ñòðåìèòñÿ ê åäèíèöå.  îòëè÷èå îò äðó-
ãèõ ïîäîáíûõ ïðåîáðàçîâàíèé ÄÊÏ îáåñïå÷èâàåò óïàêîâêó íàèáîëüøåãî êîëè-
÷åñòâà èíôîðìàöèè â íàèìåíüøåå ÷èñëî êîýôôèöèåíòîâ (äëÿ áîëüøèíñòâà ðå-
àëüíûõ èçîáðàæåíèé), à òàêæå ìèíèìèçèðóåò ýôôåêò ïîÿâëåíèÿ áëî÷íûõ ñòðóê-
òóð, íàçûâàåìûõ áëî÷íûìè èñêàæåíèÿìè, êîãäà íà èçîáðàæåíèè ñòàíîâÿòñÿ
çàìåòíûìè ãðàíèöû ìåæäó ñîñåäíèìè áëîêàìè. Êðîìå òîãî, ÄÊÏ îáåñïå÷èâàåò
ëèíåéíîñòü ôàçû, ðåàëüíûå êîýôôèöèåíòû è èìååò áûñòðûå àëãîðèòìû. Êîäèðî-
âàíèå íà îñíîâå áëîêîâ ñ èñïîëüçîâàíèåì ÄÊÏ ïîðÿäêà 8 ÿâëÿåòñÿ âàæíîé òåõ-
íîëîãèåé âèäåîêîäèðîâàíèÿ, êîòîðîå èñïîëüçóåòñÿ â ñòàíäàðòàõ H.261, H.263,
JPEG, MPEG-2 è MPEG-4 visual. Áîëåå íîâûå ñòàíäàðòû, òàêèå êàê MPEG-4
AVC/H.264 [1], VC-1 [2] è AVS [3, 4], ïðèìåíÿþò öåëî÷èñëåííîå êîñèíóñíîå
ïðåîáðàçîâàíèå (ÖÊÏ) ïîðÿäêîâ 4, 8 è 16. Ýòî îáúÿñíÿåòñÿ òåì, ÷òî ÖÊÏ âûïîë-
íÿåòñÿ âû÷èñëåíèåì áåç ïëàâàþùåé çàïÿòîé. Åãî ÿäðî ñîäåðæèò òîëüêî öåëûå
è óïàêîâûâàåò ýíåðãèþ ïîäîáíî ÄÊÏ. Â íàñòîÿùåå âðåìÿ ïîÿâèëñÿ íîâûé ñòàí-
äàðò âûñîêîýôôåêòèâíîãî âèäåîêîäèðîâàíèÿ High Efficiency Video Coding
(HEVC èëè Í.265) [5], ãäå ïðèìåíåíû öåëî÷èñëåííûå ïðåîáðàçîâàíèÿ ðàçìåðàìè
â ïðåäåëàõ îò 4 äî 32, ïðåäëîæåííûå ðàçðàáîò÷èêàìè ôèðì Cisco Systems
è Texas Instruments [6]. Îäíàêî ÖÊÏ, êîòîðûå èñïîëüçóþòñÿ â ñòàíäàðòå Í.265,
íå èìåþò áûñòðûõ àëãîðèòìîâ, ÷òî ïðèâîäèò ê áîëüøåé âû÷èñëèòåëüíîé ñëîæ-
íîñòè. Áûëî ïðåäëîæåíî ðÿä ïðîñòûõ öåëî÷èñëåííûõ ïðåîáðàçîâàíèé ïîðÿäêà
16 ñ áûñòðûìè àëãîðèòìàìè íèçêîé ñëîæíîñòè [7–11].
 ðàáîòàõ [12–14] ïðåäëîæåíà öåëî÷èñëåííàÿ àïïðîêñèìàöèÿ ÄÊÏ ñ áûñò-
ðûìè àëãîðèòìàìè ìåíüøåé ñëîæíîñòè, ÷åì â ñòàíäàðòå Í.265 [6].  [11] ïðåä-
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 5 161
© Ë.À. Ãíàòèâ, 2016
ëîæåíû ïðîñòûå ÖÊÏ ïîðÿäêîâ 8 è 16 ñ áûñòðûìè àëãîðèòìàìè, êîòîðûå, â îò-
ëè÷èå îò èçâåñòíûõ [14, 13], èìåþò â 1,43 è 1,7 ðàçà ìåíüøóþ âû÷èñëèòåëüíóþ
ñëîæíîñòü è â 2,9 ðàçà — ÷åì ïðåîáðàçîâàíèå â ñòàíäàðòå Í.265. Êðîìå òîãî,
áûëî ïðåäëîæåíî íåñêîëüêî äðóãèõ ýôôåêòèâíûõ ñïîñîáîâ óìåíüøåíèÿ ñëîæ-
íîñòè êîäåðà, òàêèõ êàê óëó÷øåííîå intra-êîäèðîâàíèå èçîáðàæåíèé (intrapicture)
è óïðîùåííûå VLC êîýôôèöèåíòû [15].
 íàñòîÿùåé ñòàòüå ðàññìîòðåíû ìàòðè÷íûå ìåòîäû ïîñòðîåíèÿ îäíîíîðìî-
âûõ ÖÊÏ ïîðÿäêîâ 8 è 16 ñ áûñòðûìè öåëî÷èñëåííûìè ïðåîáðàçîâàíèÿìè.
ÎÄÍÎÍÎÐÌÎÂÎÅ ÖÊÏ ÏÎÐßÄÊÀ 8
Ðàññìîòðèì ìåòîä ïîñòðîåíèÿ îäíîíîðìîâîãî ÖÊÏ ïîðÿäêà 8, ïðåäñòàâëåííûé
â ðàáîòå [16], à òàêæå ìàòðèöó ICT8
* ðàçìåðà 8 8� ÖÊÏ ñ ïåðåñòàâëåíûìè ñòðî-
êàìè, êîòîðàÿ ïîëó÷åíà èç ìàòðèöû ICT8 ïåðåñòàíîâêîé ñòðîê íà îñíîâå äâîè÷-
íî-èíâåðñíûõ ïåðåñòàíîâîê (ÄÈÏ) è ïåðåñòàíîâîê ïî êîäó Ãðåÿ (ÏÊÃ) [17]:
ICT P P ICT8 8 8 8
* � � , (1)
ãäå P8 — ìàòðèöà 8 8� ÄÈÏ, �P8 — áëî÷íî-äèàãîíàëüíàÿ ìàòðèöà 8 8� , ñîäåð-
æàùàÿ ìàòðèöû 4 4� G4 ÏÊÃ è P4 ÄÈÏ, � �P G P8 4 4diag [ , ], G I I4 2 2� diag [ , ],
P I4 21 1� diag [ , , ], I 2
1
1
�
�
�
�
�
.
Ìàòðèöà ICT8
* ðàçìåðà 8 8� ÖÊÏ ñ ïåðåñòàâëåííûìè ñòðîêàìè ìîæåò áûòü
ïðåäñòàâëåíà ìàòðèöåé ÿäðà ÖÊÏ:
ICT B C8 8 8
* * *� , (2)
ãäå B8
* — äèàãîíàëüíàÿ ìàòðèöà 8 8� êîýôôèöèåíòîâ íîðìèðîâàíèÿ, C8
* —
ìàòðèöà 8 8� ÿäðà ÖÊÏ ñ ïåðåñòàâëåííûìè ñòðîêàìè. Ìàòðèöà C8
* ìîæåò
áûòü ïðåäñòàâëåíà ðåêóððåíòíî [11]:
C C Q H8 4 4 8
* * *[ , ]� diag , C G P C4 4 4 4
* � , (3)
ãäå H 8
* — ôàêòîð-ìàòðèöà 8 8� ñ íåíóëåâûìè ýëåìåíòàìè �1,
H
I I
I I
8
4 4
4 4
* �
�
�
�
�
�
, I I4 4� antidiag [ ],
I 4 , I 4 — åäèíè÷íàÿ è àíòèäèàãîíàëüíàÿ ìàòðèöû 4 4� ; C4
* — ìàòðèöà 4 4�
ÿäðà ÖÊÏ ñ ïåðåñòàâëåííûìè ñòðîêàìè íà îñíîâå ÄÈÏ è ÏÊÃ; Q4 — ìàòðè-
öà 4 4� , êîòîðàÿ ìîæåò áûòü ïðåäñòàâëåíà ìàòðèöåé ÿäðà ÖÊÏ-IV,
Q C I4 4 4� IV , (4)
C
4
IV — ìàòðèöà ÿäðà ÖÊÏ-IV ñ öåëûìè ýëåìåíòàìè �a , b, � c, d, e, � f ,
� �g h, è ïåðåñòàâëåííûìè ñòðîêàìè íà îñíîâå ÄÈÏ. Ïðè ýòîì
Q
d c b a
h g f e
e f g h
a b c d
4 �
� � �
�
� �
�
�
�
�
�
�
�
, C
a b c d
e f g h
h g f e
d c b a
4
IV �
� � �
�
� �
�
�
�
�
�
�
�
, I 4
1
1
1
1
�
�
�
�
�
�
�
�
, (5)
162 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 5
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 k
8 �
� � � �
� � � �
� � � �
� � � �
� � � �
� � � �
� � � �
�
�
�
�
�
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
�
�
�
�
�
�
�
�
, (6)
ãäå a b c d
, i j
, g e h f
.
Èìåþò ìåñòî ñîîòíîøåíèÿ
a d e
a d h
� �
� �
�
�
�
,
,
b c g
b c f
� �
� �
�
�
�
,
,
a d b c
e h f g
2 2 2 2
2 2 2 2 2
� � � �
� � � �
�
�
�
�
�
,
.
ÀËÃÎÐÈÒÌ ÁÛÑÒÐÎÃÎ ÏÐßÌÎÃÎ ÖÊÏ ÏÎÐßÄÊÀ 8
Ìàòðèöà Q4 ìîæåò áûòü ïðåäñòàâëåíà ïðîèçâåäåíèåì äâóõ ìàòðèö:
Q H T4 4
0
4� , (7)
ãäå H
4
0 — áëî÷íî-äèàãîíàëüíàÿ ôàêòîð-ìàòðèöà 4 4� ñ ýëåìåíòàìè 1 è ìàòðè-
öåé Àäàìàðà H 2 ,
H H
4
0
21 1� diag [ , , ], H 2
1 1
1 1
�
�
�
�
�
�
; (8)
T4 — ìàòðèöà 4 4� ñ öåëûìè ýëåìåíòàìè � � �a b c d, , , ,
T
d c b a
d c b a
a b c d
a b c d
4 �
� �
� �
� �
�
�
�
�
�
�
�
. (9)
Ìàòðèöà T4 ìîæåò áûòü ïðåäñòàâëåíà êàê ïðîèçâåäåíèå äâóõ ìàòðèö:
T H R4 4 4� , H H H4 2 2� diag [ , ], H 2
1 1
1 1
�
��
�
�
�
, (10)
H 4 — áëî÷íî-äèàãîíàëüíàÿ ôàêòîð-ìàòðèöà 4 4� , ñîäåðæàùàÿ ìàòðèöû H 2 è
H 2 ; R4 — ôàêòîð-ìàòðèöà ðàñòÿãèâàíèÿ 4 4� , êîòîðàÿ ñîäåðæèò íà îñíîâíîé
äèàãîíàëè öåëûå ýëåìåíòû �c è d , à íà äðóãîé äèàãîíàëè — öåëûå ýëåìåíòû
�a è b. Ïðè ýòîì
H 4
1 1
1 1
1 1
1 1
�
�
�
�
�
�
�
�
�
�
, R
d a
c b
b c
a d
4 �
�
�
�
�
�
�
�
�
�
. (11)
Òîãäà ìàòðèöà Q4 íà îñíîâàíèè (7) è (10) ìîæåò áûòü ïðåäñòàâëåíà ïðîèçâå-
äåíèåì òðåõ ìàòðèö:
Q H H R4 4
0
4 4� . (12)
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 5 163
Ìàòðèöà C4
* ÿäðà ÖÊÏ ïîðÿäêà 4 ìîæåò áûòü ïðåäñòàâëåíà êàê ïðîèçâåäå-
íèå äâóõ ìàòðèö:
C C C4 2 1
* � , (13)
ãäå C1, C2 — ôàêòîð-ìàòðèöû 4 4� áûñòðîãî ÖÊÏ ïîðÿäêà 4:
C H1 4� * , C T Q2 2 2� diag [ , ], (14)
T
k k
k k
2 �
�
�
�
�
�
, Q
i j
j i
2 �
��
�
�
�
, H
I I
I I
4
2 2
2 2
* �
�
�
�
�
�
.
Ìàòðèöà C8
* íà îñíîâàíèè (3), (12) è ñ ó÷åòîì àëãîðèòìà áûñòðîãî ïðÿìîãî
ÖÊÏ ïîðÿäêà 4 ñîãëàñíî (13) ìîæåò áûòü ôàêòîðèçîâàíî ïðåäñòàâëåíà êàê ïðî-
èçâåäåíèå ÷åòûðåõ ìàòðèö:
C C C C C8 8 4 8 3 8 2 8 1
*
, , , ,� , (15)
ãäå C i8, — i-å, i �1 4, , ôàêòîð-ìàòðèöû 8 8� àëãîðèòìà ïðåäëîæåííîãî áûñòðî-
ãî ïðÿìîãî ÖÊÏ:
C H8 1 8,
*� , C H R8 2 4 4,
*[ , ]� diag ,
C T Q H8 3 2 2 4, [ , , ]� diag , (16)
C I H8 4 4 4
0
, [ , ]� diag .
Äëÿ îäíîíîðìîâîãî ÖÊÏ ìàòðèöà H
4
0 ñîäåðæèò íåíóëåâûå ýëåìåíòû 1 è
� p m/ 2 .
Íà ðèñ. 1 ïðåäñòàâëåí ãðàô àëãîðèòìà ñîãëàñíî (15), (16) ïðåäëîæåííîãî
8-òî÷å÷íîãî áûñòðîãî ïðÿìîãî ÖÊÏ.
164 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 5
Ðèñ. 1. Ãðàô àëãîðèòìà ïðåäëîæåííîãî 8-òî÷å÷íîãî áûñòðîãî ïðÿìîãî ÖÊÏ
X 0
X 4
X 2
X 6
X 5
X 7
X 3
X1
x4
x5
x7
x6
x2
x3
x1
x0
d
k
k
� k
d
a
� c
b
a
c
f
i
j
� i
ÀËÃÎÐÈÒÌ ÁÛÑÒÐÎÃÎ ÎÁÐÀÒÍÎÃÎ ÖÊÏ ÏÎÐßÄÊÀ 8
Ìàòðèöó îáðàòíîãî ïðåîáðàçîâàíèÿ ÖÊÏ C i8 ïîðÿäêà 8 ìîæíî ïîëó÷èòü
òðàíñïîíèðîâàíèåì:
C C ki8 8
� * /T . (17)
Ìàòðèöà C i8 íà îñíîâàíèè (17), (15) è ñ ó÷åòîì ñèììåòðè÷íîñòè ôàê-
òîð-ìàòðèö (H H
8 8
* *T � , H H
4 4
* *T � , H H
4 4
T � , H H
4
0
4
0T � ) ìîæåò áûòü ôàêòîðè-
çîâàíî ïðåäñòàâëåíà êàê ïðîèçâåäåíèå ÷åòûðåõ ìàòðèö:
C C C C Ci i i i i8 8 1 8 2 8 3 8 4� , , , ,
T , (18)
ãäå C i k8 , — k-å, k �1 4, , ôàêòîð-ìàòðèöû 8 8� àëãîðèòìà ïðåäëîæåííîãî áûñò-
ðîãî îáðàòíîãî ÖÊÏ:
C Hi8 1 8,
*� , C H R
i i8 2 4 4,
*[ , ]T Tdiag� , C T Q Hi i i8 3 2 2 4, [ , , ]� diag , (19)
C I Hi8 4 4 4
0
, [ , ]� diag , T T k Hi2 2 2� �/ , Q Q ki2 2� / ,
R
d a
c b
b c
a d
k
i4
T �
�
�
�
�
�
�
�
�
�
/ .
Íà ðèñ. 2 ïðåäñòàâëåí ãðàô àëãîðèòìà ñîãëàñíî (18), (19) ïðåäëîæåííîãî
8-òî÷å÷íîãî áûñòðîãî îáðàòíîãî ÖÊÏ. Ïðè ýòîì ( , , , ) ( , , , ) / ,� � � � �a b c d a b c d k
( , ) ( , ) /� � �i j i j k .
Ýëåìåíòû ìàòðèöû C8 îäíîíîðìîâîãî ìàñøòàáèðîâàííîãî ÖÊÏ ïðèíèìàþò
ñëåäóþùèå çíà÷åíèÿ: a � 45, b � 38, c � 24, d � 9, e � 38, f � 9, g � 44, h � 25,
i � 43, j �14, k � 32.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 5 165
Ðèñ. 2. Ãðàô àëãîðèòìà ïðåäëîæåííîãî 8-òî÷å÷íîãî áûñòðîãî îáðàòíîãî ÖÊÏ
X 0
X 4
X 2
X 6
X 5
X 7
X 3
X1
x4
x5
x7
x6
x2
x3
x1
x0
�d
�d
�a
� �c
�b
�ñ
�i
�j
� �i
�a
Ìàòðèöà C8 ïðåäëîæåííîãî îäíîíîðìîâîãî ìàñøòàáèðîâàííîãî ÖÊÏ èìååò
âèä
C8
32 32 32 32 32 32 32 32
45 38 24 9 9 24 38 45
43 14 14 43 43
�
� � � �
� � � �
� � � �
� � � �
�
14 14 43
38 9 44 25 25 44 9 38
32 32 32 32 32 32 32 32
25 44 9 38 38 9 44 25
14 43 43 14 14 43 43 14
9 24 38 45 45 38 24
� � �
� � � �
� � � �9
�
�
�
�
�
�
�
�
�
�
�
�
�
. (20)
Ñëåäóåò îòìåòèòü, ÷òî êâàäðàòû íîðì áàçèñíûõ âåêòîðîâ ìàòðèöû C8 îäíî-
íîðìîâîãî ìàñøòàáèðîâàííîãî ÖÊÏ ïðèáëèæàþòñÿ ê ÷èñëó ñòåïåíè äâà:
q Ci i i� � �| | | | (%)2 8192 � , i �1 2 3, , , � i � �015 0 7, , % ,
íåîðòîãîíàëüíîñòü ñîñòàâëÿåò 0,2–2 %.
ÐÅÀËÈÇÀÖÈß ÁÅÇ ÌÍÎÆÈÒÅËÅÉ
Ïðåäëîæåííîå öåëî÷èñëåííîå ïðåîáðàçîâàíèå ìîæåò áûòü ðåàëèçîâàíî, èñ-
ïîëüçóÿ â îñíîâíîì îïåðàöèè ñäâèãà è ñëîæåíèÿ. Ïàðíûå óìíîæåíèÿ ïðèìå-
íÿþòñÿ â îïåðàöèÿõ «áàáî÷êà» (butterfly) è âûïîëíÿþòñÿ ïóòåì ñäâèãîâ è ñëî-
æåíèé, à â íåêîòîðûõ ñëó÷àÿõ (ñ öåëüþ óìåíüøåíèÿ âû÷èñëèòåëüíîé ñëîæ-
íîñòè) — ïóòåì óìíîæåíèÿ è ñäâèãà. Â òàáë. 1 ïðåäñòàâëåíà ñõåìà
âûïîëíåíèÿ ñïåöèàëüíûõ ïàðíûõ óìíîæåíèé, èñïîëüçóåìûõ â îïåðàöèÿõ «áà-
áî÷êà» äëÿ ðåàëèçàöèè ïðåäëîæåííîãî 1D 8-òî÷å÷íîãî îäíîíîðìîâîãî öåëî-
÷èñëåííîãî îáðàòíîãî ïðåîáðàçîâàíèÿ.
Äëÿ ðåàëèçàöèè ïðåäëîæåííîãî 1D 8-òî÷å÷íîãî îäíîíîðìîâîãî öåëî÷èñëåí-
íîãî îáðàòíîãî ïðåîáðàçîâàíèÿ òðåáóåòñÿ âûïîëíèòü äâå îïåðàöèè óìíîæåíèÿ,
40 îïåðàöèé ñëîæåíèÿ è 16 îïåðàöèé ñäâèãà.
Âû÷èñëèòåëüíàÿ ñëîæíîñòü ïðåäëîæåííîãî, èçâåñòíûõ [13, 14] è ïðèíÿòîãî
â ñòàíäàðòå Í.265 [5, 6] 2D 8-òî÷å÷íûõ öåëî÷èñëåííûõ îáðàòíûõ ïðåîáðàçîâà-
íèé ïðèâåäåíà â òàáë. 2
166 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 5
Ò à á ë è ö à 1
Çíà÷åíèÿ
ìíîæèòåëåé
Àëãîðèòì âûïîëíåíèÿ
îïåðàöèé
y d x� � ;
z a x� �
Âû÷èñëèòåëüíàÿ ñëîæíîñòü
îïåðàöèé Êîëè÷åñòâî
èñïîëüçóåìûõ
îïåðàöèé
Ñëîæåíèå Ñäâèã Óìíîæåíèå
d � 9 32/ a � 45 32/
x x x1 3� � ( ) ;�
y x� 1 2� ; z x y� �1
2 2 — 2
c � 24 32/ b � 38 32/
y x x� � ( );�2
z x y� � ( )�2
2 2 — 2
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 — 2
p m/ 2 0
x p x1 � � ; y x m� 1� ;
z � 0
— 1 1 2
Âñåãî — 14 16 2
ÎÄÍÎÍÎÐÌÎÂÎÅ ÖÊÏ ÏÎÐßÄÊÀ 16
Èçëîæèì ìåòîä ïîñòðîåíèÿ îäíîíîðìîâîãî ÖÊÏ ïîðÿäêà 16, êîòîðûé ïðåä-
ñòàâëåí â ðàáîòå [16]. Ðàññìîòðèì ICT16
* — ìàòðèöó 16 16� ÖÊÏ ïîðÿäêà 16
ñ ïåðåñòàâëåííûìè ñòðîêàìè, êîòîðàÿ ïîëó÷åíà èç ìàòðèöû ICT16 ïóòåì ïåðå-
ñòàíîâîê ñòðîê íà îñíîâå ÄÈÏ, îáðàòíûõ ïåðåñòàíîâîê è ÏÊÃ:
ICT G P P ICT16 16 16 16 16
* � � , (21)
ãäå P16 — ìàòðèöà 16 16� ÄÈÏ, P16 — áëî÷íî-äèàãîíàëüíàÿ ìàòðèöà 16 16�
ñ åäèíè÷íîé ìàòðèöåé 12 12� I12 è àíòèäèàãîíàëüíîé ìàòðèöåé 4 4� I 4 ,
P I I16 12 4� diag [ , ]; �G16 — áëî÷íî-äèàãîíàëüíàÿ ìàòðèöà 16 16� ñ ìàòðèöàìè
4 4� G4 è P4 , � �G G P G G16 4 4 4 4diag [ , , , ].
Ìàòðèöà ICT16
* ðàçìåðà 16 16� ÖÊÏ ñ ïåðåñòàâëåííûìè ñòðîêàìè ìîæåò
áûòü ïðåäñòàâëåíà ìàòðèöåé ÿäðà ÖÊÏ:
ICT B C16 16 16
* * *� , (22)
ãäå B16
* — äèàãîíàëüíàÿ ìàòðèöà 16 16� êîýôôèöèåíòîâ íîðìèðîâàíèÿ; C16
* —
ìàòðèöà 16 16� ÿäðà ÖÊÏ ñ ïåðåñòàâëåííûìè ñòðîêàìè.
Ìàòðèöà C16
* ìîæåò áûòü ïðåäñòàâëåíà ðåêóððåíòíî [16]:
C C Q H16 8 8 16
* * *[ , ]� diag , (23)
ãäå H16
* — ôàêòîð-ìàòðèöà 16 16� ñ íåíóëåâûìè ýëåìåíòàìè �1 (àíàëîãè÷íà
ìàòðèöå H 8
* (ñì. (3)); Q8 — ìàòðèöà 8 8� , êîòîðàÿ ìîæåò áûòü ïðåäñòàâëåíà
ìàòðèöåé ÿäðà ÖÊÏ-IV:
Q C I8 8 8� IV* . (24)
Çäåñü I 8 , I 8 — åäèíè÷íàÿ è àíòèäèàãîíàëüíàÿ åäèíè÷íàÿ ìàòðèöû 8 8� ,
I I8 8� antidiag [ ]; C
8
IV* — ìàòðèöà 8 8� ÿäðà ÖÊÏ-IV ñ ïåðåñòàâëåííûìè ñòðî-
êàìè, C
8
IV* � �G P P C8 8 8 8
IV, ãäå 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 [ , ].
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 5 167
Ò à á ë è ö à 2
Õàðàêòåðèñòèêà
âû÷èñëèòåëüíîé
ñëîæíîñòè
Îöåíêà ñëîæíîñòè 2D ïðåîáðàçîâàíèé 8 8�
Ïðåäëîæåííîãî Í.265 [5, 6] Èç [13] Èç [14]
Óìåíüøåíèå
îòíîñèòåëüíî
[14] [5, 6]
Óìíîæåíèå 32 352 192 176 Â 5,5 ðàçà Â 11 ðàç
Ñëîæåíèå � ñäâèã 640 � 256 448 � 128 416 464
Íà 93 %
áîëüøå
ñëîæåíèé
Íà 55,5 %
áîëüøå
ñëîæåíèé
×èñëî èòåðàöèé
äëÿ 1D
4 3 4 4 0
Íà îäíó
èòåðàöèþ
áîëüøå
Ïàìÿòü äëÿ
êâàíòîâàíèÿ
— — � — — —
×èñëî áèòîâ
ýëåìåíòà ìàòðèöû
7 8 7 14
Íà 7 áèò
ìåíüøå
Íà 1 áèò
ìåíüøå
Ìàòðèöà C
8
IV* èìååò âèä
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 F 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
�
�
�
�
�
�
�
0
4
6
2
7
3
1
5
, (25)
ãäå A B C D E F G H
.
Ìàòðèöà C
8
IV* ìîæåò áûòü ïðåäñòàâëåíà ÷åðåç ìàòðèöó ÿäðà ÖÊÏ ïîðÿäêà 4
êàê ïðîèçâåäåíèå òðåõ ìàòðèö [16]:
C H T T R
8 8
0
4 4 8
IV diag* * *[ , ]� , (26)
ãäå R8 — ìàòðèöà 8 8� ðàñòÿãèâàíèÿ, êîòîðàÿ íà îñíîâíîé äèàãîíàëè ñîäåðæèò
öåëûå ýëåìåíòû �ri ( , )i �1 4 , à íà äðóãîé äèàãîíàëè öåëûå ýëåìåíòû �si è êî-
òîðàÿ äëÿ ÄÊÏ-IV ïðåäñòàâëÿåò ìàòðèöó âðàùåíèÿ Ãèâåíñà; H
8
0 — ôàêòîð-ìàò-
ðèöà 8 8� ñ íåíóëåâûìè ýëåìåíòàìè �1; T4
*– ìàòðèöà 4 4� ÿäðà ÖÊÏ ñ ïåðå-
ñòàâëåííûìè ñòðîêàìè íà îñíîâå ÄÈÏ è ÏÊÃ, T G P T4 4 4 4
* � . Ïðè ýòîì
R
r s
r s
r s
r s
s r
s r
s r
s r
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
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
,
ãäå r ri i
�1 , s s ii i� ��1 1 4, , ,
T
p p p p
p p p p
s r r s
r s s r
4
* �
� �
� �
� �
�
�
�
�
�
�
�
, r s p n
�, 2 . (27)
Äëÿ îäíîíîðìîâîãî ÖÊÏ ôàêòîð-ìàòðèöà H
8
0 ñîäåðæèò íåíóëåâûå ýëåìåíòû 1
è � pi
mi/ 2 , i �1 2 3, , .
Ìàòðèöà Q8 íà îñíîâàíèè (24) è (26) ìîæåò áûòü ïðåäñòàâëåíà êàê ïðîèçâå-
äåíèå ÷åòûðåõ ìàòðèö:
Q H T T R I8 8
0
4 4 8 8� diag [ , ]* *
(28)
èëè (ñ ó÷åòîì ïðîèçâåäåíèÿ äâóõ ìàòðèö R I R8 8 8� ) êàê ïðîèçâåäåíèå òðåõ
ìàòðèö:
Q H T T R8 8
0
4 4 8� diag [ , ]* * , (29)
168 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 5
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
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
. (30)
Ìàòðèöà C16 ÿäðà ÖÊÏ ïîðÿäêà 16 íà îñíîâàíèè (23)–(25) è ñ ó÷åòîì (6) ìî-
æåò áûòü ïðåäñòàâëåíà êàê
C
k k k k k k k k
A B C D E F G H
a b c d d c b a
A A A A A A A
16
1 2 3 4 5 6 7
�
� � � �
� � � � �
� � � �
� � �
� � � �
�
A
i j j i i j j i
B B B B B B B B
e f g h h g f e
C C
8
1 2 3 4 5 6 7 8
1 2 3 4 5 6 7 8
8 7 6 5 4 3 2 1
� � �
� � � �
� � � �
�
C C C C C C
k k k k k k k k
C C C C C C C C
h g f e e f g h
B B B B B B B B
j i i j j i i j
A A A A
� � �
� � �
� � � �
� �
8 7 6 5 4 3 2 1
8 7 6 5 4 3 2 1A A A A
d c b a a b c d
H G F E D C B A
�
� � � �
� � � �
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
k
H
a
A
i
B
e
C
k
C
h
B
j
A
d
A
k
A
a
A8
8
8
1
1
1
1
�
�
�
�
� i
B
e
C
k
C
h
B
j
A
d
H
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
1
1
8
8
8
. (31)
Ýëåìåíòû ri , si ìàòðèöû R8 ïðèíèìàþò ñëåäóþùèå çíà÷åíèÿ: r1 45� ,
r2 43� , r3 40� , r4 35� , s1 5� , s2 14� , s3 21� , s4 29� . Ýëåìåíòû ìàòðèöû T4
* ïðè-
íèìàþò çíà÷åíèÿ: r � 5, s � 2, p � 4.
Ýëåìåíòû ìàòðèöû C16 ñîãëàñíî (31) ïðåäëîæåííîãî îäíîíîðìîâîãî ìàñ-
øòàáèðîâàííîãî ÖÊÏ ïðèíèìàþò çíà÷åíèÿ: A �180, B �172, C �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
ïðåäñòàâëåíû â òàáë. 3.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 5 169
Ò à á ë è ö à 3
Ýëåìåíòû
Çíà÷åíèå ýëåìåíòîâ ìàòðèöû C16 ïðè 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
Ñëåäóåò îòìåòèòü, ÷òî êâàäðàòû íîðì áàçèñíûõ âåêòîðîâ â ìàòðèöå C16 îä-
íîíîðìîâîãî ìàñøòàáèðîâàííîãî ÖÊÏ ïðèáëèæàþòñÿ ê ÷èñëó ñòåïåíè äâà:
q Ci i i� � �| | | | (%)2 131072 � , i �1 3 5 7, , , , � i � 0,11– 0,28 %, íåîðòîãîíàëüíîñòü
ñîñòàâëÿåò 0,01– 0,26 %.
Òàêèì îáðàçîì, ïðåäëîæåííûå ÖÊÏ èìåþò òàêèå æå ñâîéñòâà, êàê è ïðèíÿ-
òûå â ñòàíäàðòå Í.265: 8 áèò ïðåäñòàâëåíèÿ êîýôôèöèåíòîâ ïðåîáðàçîâàíèÿ; øè-
ðèíà íàêîïèòåëüíîãî ñóììàòîðà äëÿ ìàòðè÷íîãî óìíîæåíèÿ íå ïðåâûøàåò
32 áèò; ñèììåòðè÷íîñòü/àíòèñèììåòðè÷íîñòü ñîîòâåòñòâóåò ÄÊÏ; êîýôôèöèåí-
òû ìàñøòàáèðîâàííîãî ïðåîáðàçîâàíèÿ ÿâëÿþòñÿ áëèçêèìè ê ÄÊÏ; áàçèñíûå
âåêòîðû ïî÷òè îðòîãîíàëüíû; îäèíàêîâàÿ ñõåìà êâàíòîâàíèÿ è äåêâàíòîâàíèÿ
äëÿ ïðåîáðàçîâàíèé âñåõ ðàçìåðíîñòåé, ãäå ìíîæèòåëè çàâèñÿò îò çíà÷åíèé ïàðà-
ìåòðà êâàíòîâàíèÿ QP [18] è ñäâèãè çàâèñÿò òîëüêî îò log 2 N , ãäå N — ðàçìåð-
íîñòü ïðåîáðàçîâàíèÿ; êîýôôèöèåíòû êâàíòîâàíèÿ ìîãóò áûòü ïðåäñòàâëåíû
16 áèòàìè.
ÀËÃÎÐÈÒÌ ÁÛÑÒÐÎÃÎ ÏÐßÌÎÃÎ ÖÊÏ ÏÎÐßÄÊÀ 16
Ìàòðèöà T4
* ìîæåò áûòü ïðåäñòàâëåíà êàê ïðîèçâåäåíèå äâóõ ìàòðèö:
T T T4 4 2 4 1
*
, ,� , (32)
ãäå T i4, — i-å, i �1 2, , ôàêòîð-ìàòðèöû 4 4� :
T H4 1 4,
*� , T T R4 2 2 2, [ , ]� �diag , � �
�
�
�
�
�
T
p p
p p
2 , R
r s
s r
2 �
��
�
�
�
,
�T2 — ìàòðèöà 2 2� , êîòîðàÿ ñîäåðæèò öåëûå � p; R2 — ìàòðèöà ðàñòÿãèâàíèÿ
2 2� , êîòîðàÿ ñîäåðæèò öåëûå ýëåìåíòû � r s, .
Ìàòðèöà C16
* íà îñíîâàíèè (23), (29), (32) è ñ ó÷åòîì àëãîðèòìà áûñòðîãî
ïðÿìîãî ÖÊÏ ïîðÿäêà 8 ñîãëàñíî (15) ìîæåò áûòü ôàêòîðèçîâàíî ïðåäñòàâëåíà
êàê ïðîèçâåäåíèå ïÿòè ìàòðèö:
C C C C C C16 16 5 16 4 16 3 16 2 16 1
*
, , , , ,� , (33)
ãäå C i16, — i-å, i �1 5, , ôàêòîð-ìàòðèöû 16 16� àëãîðèòìà ïðåäëîæåííîãî â [16]
áûñòðîãî ïðÿìîãî ÖÊÏ:
C H16 1 16,
*� , C H R16 2 8 8,
*[ , ]� diag , C H R H H16 3 4 4 4 4,
* * *[ , , , ]� diag ,
(34)
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 .
ÀËÃÎÐÈÒÌ ÁÛÑÒÐÎÃÎ ÎÁÐÀÒÍÎÃÎ ÖÊÏ ÏÎÐßÄÊÀ 16
Ìàòðèöó ÿäðà îáðàòíîãî ÖÊÏ C i16 ïîðÿäêà 16 ìîæíî ïîëó÷èòü òðàíñïîíèðî-
âàíèåì:
C C ki i16 16
� * /T . (35)
Ìàòðèöà C
i16
íà îñíîâàíèè (35), (34) è ñ ó÷åòîì ñèììåòðè÷íîñòè ôàê-
òîð-ìàòðèö (H H
16 16
T * *� , � � �T T
2 2
T , R R
2 2
T � ) ìîæåò áûòü ôàêòîðèçîâàíî ïðåä-
ñòàâëåíà êàê ïðîèçâåäåíèå ïÿòè ìàòðèö:
C C C C C Ci i i i i i16 16 1 16 2 16 3 16 4 16 5
*
, , , , ,
� T T T , (36)
170 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 5
ãäå C
i k16 ,
T — k-å, k �1 5, , òðàíñïîíèðîâàííûå ôàêòîð-ìàòðèöû 16 16� àëãîðèòìà
ïðåäëîæåííîãî áûñòðîãî îáðàòíîãî ÖÊÏ:
C Hi16 1 16,
*� ; C H R
i i16 2 8 8,
*[ , ]T Tdiag� , R R k
i8 8
T T� �/ , � �k k p/ ; (37)
C H R H H
i i16 3 4 4 4 4,
* * *[ , , , ]T Tdiag� ;
C T Q H T R T Ri i i i i i i16 4 2 2 4
0
2 2 2 2, [ , , , , , , ]� � �diag ,
� � � �T T p Hi2 2 2/ , R R pi2 2� / , C I H H
i16 5 4 4
0
8
0
,
[ , , ]T Tdiag� .
Ìàòðèöû R
i8
T è H
8
0T èìåþò âèä:
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 �
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
.
 òàáë. 4 ïðåäñòàâëåíà ñõåìà âûïîëíåíèÿ ñïåöèàëüíûõ ïàðíûõ óìíîæåíèé,
èñïîëüçóåìûõ â îïåðàöèÿõ «áàáî÷êà» äëÿ ðåàëèçàöèè ïðåäëîæåííîãî 1D 16-òî-
÷å÷íîãî îäíîíîðìîâîãî öåëî÷èñëåííîãî îáðàòíîãî ïðåîáðàçîâàíèÿ.
Äëÿ ðåàëèçàöèè ïðåäëîæåííîãî 1D 16-òî÷å÷íîãî îäíîíîðìîâîãî öåëî÷èñ-
ëåííîãî îáðàòíîãî ïðåîáðàçîâàíèÿ òðåáóåòñÿ âûïîëíèòü 8 îïåðàöèé óìíîæåíèÿ,
106 îïåðàöèé ñëîæåíèÿ è 50 îïåðàöèé ñäâèãà. Âû÷èñëèòåëüíàÿ ñëîæíîñòü ïðåä-
ëîæåííîãî, èçâåñòíûõ è ïðèíÿòîãî â ñòàíäàðòå Í.265 [5, 6] 2D 16-òî÷å÷íûõ öå-
ëî÷èñëåííûõ îáðàòíûõ ïðåîáðàçîâàíèé ïðèâåäåíà â òàáë. 5.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 5 171
Ò à á ë è ö à 4
Çíà÷åíèÿ ìíîæèòåëåé
Àëãîðèòì âûïîëíåíèÿ
îïåðàöèé
y s xi� � ;
z r xi� �
Âû÷èñëèòåëüíàÿ ñëîæíîñòü
îïåðàöèé Êîëè÷åñòâî
èñïîëüçóåìûõ
îïåðàöèéÑëîæåíèå Ñäâèã Óìíîæåíèå
s1 5 32� / r1 45 32� /
x x1 2� � ; x x x2 1� � ;
y x� 2 3� ; z x y� �1
2 2 — 2
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 — 2
s3 21 32� / r3 40 32� /
x x1 2� � ; z x x� � 1;
x z2 3� � ; y x x� �2 1( )�
2 3 — 2
s4 29 32� / r4 35 32� /
x x x1 2� � ( );�
y x x� � ( )1 3� ;
z x x� � ( )1 3�
3 2 — 2
r � 5 4/ s � 2 4/ z x� � 1; y x x� � ( )� 2 1 2 — 4
p pi
m
1 1 2 1� / 0
x p x1 1� � ; y x m� 1 1� ;
z � 0
— 1 1 2
p pi
m
2 2 2 2� / 0
x p x1 2� � ; y x m� 1 2� ;
z � 0
— 1 1 2
p pi
m
3 3 2 3� / 0
x p x1 3� � ; y x m� 1 3� ;
z � 0
— 1 1 2
Âñåãî 24 34 6
ÝÊÑÏÅÐÈÌÅÍÒÀËÜÍÛÅ ÐÅÇÓËÜÒÀÒÛ È ÈÕ ÀÍÀËÈÇ
Ýêñïåðèìåíòàëüíûå ðåçóëüòàòû ýôôåêòèâíîñòè êîäèðîâàíèÿ ïî õàðàêòåðèñòè-
êå ñòàíäàðòíîé êîëè÷åñòâåííîé îöåíêè èñêàæåíèé PSNR (äÁ) äëÿ ñæàòûõ òåñ-
òîâûõ èçîáðàæåíèé êëàññà À (HD) (ôîòî, Ñîáîð è ïåéçàæ 1) ñ ðàçðåøàþùåé
ñïîñîáíîñòüþ 1920 1072� ïèêñåëåé è êëàññà Ñ (ôîòî è ïåéçàæ 2) — 1280 720�
ïèêñåëåé ïðè íîðìàëüíîì (22–37) äèàïàçîíå QP è âûñîêîì (36, 42) äèàïàçîíå
QP äëÿ ïðåäëîæåííûõ 2D ïðåîáðàçîâàíèé ïî ñðàâíåíèþ ñ ïðåîáðàçîâàíèÿìè
Í.265 ñ áëîêàìè 8 8� ïðèâåäåíû â òàáë. 6, à ñ áëîêàìè 16 16� — â òàáë. 7. Ðå-
çóëüòàòû ýôôåêòèâíîñòè êîäèðîâàíèÿ ïî êðèòåðèþ îöåíêè ñðåäíåêâàäðàòè÷åñ-
êîãî îòêëîíåíèÿ (ÑÊÎ, â óðîâíÿõ ÿðêîñòè) ðàçíîñòè âõîäíîãî è âîññòàíîâëåí-
íîãî òåñòîâûõ èçîáðàæåíèé â óðîâíÿõ ÿðêîñòè äëÿ ïðåäëîæåííûõ 2D ïðå-
îáðàçîâàíèé ïî ñðàâíåíèþ ñ Í.265 ñ áëîêàìè 8 8� ïðèâåäåíû â òàáë. 6, à ñ áëî-
êàìè 16 16� — â òàáë. 7.
Ýêñïåðèìåíòàëüíûå ðåçóëüòàòû òåñòèðîâàíèÿ ïî õàðàêòåðèñòèêå êîýôôèöèåíòà
ñæàòèÿ K :1äëÿ äâóõ ïðåäëîæåííûõ 2D ïðåîáðàçîâàíèé c áëîêàìè 8 8� (16 16� ) ïðè-
âåäåíû â òàáë. 8. Ðåçóëüòàòû ýôôåêòèâíîñòè êîäèðîâàíèÿ ïî õàðàêòåðèñòèêå êîýô-
ôèöèåíòà ñæàòèÿ K (â ïðîöåíòàõ) äëÿ ïðåäëîæåííûõ ïðåîáðàçîâàíèé ïî ñðàâíåíèþ
ñ ïðåîáðàçîâàíèÿìè Í.265 ñ áëîêàìè 8 8� (16 16� ) ïðèâåäåíû â òàáë. 9. Òàêæå äàíû
ñðåäíèå çíà÷åíèÿ ýêñïåðèìåíòàëüíûõ ðåçóëüòàòîâ ýôôåêòèâíîñòè êîäèðîâàíèÿ ïî
172 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 5
Ò à á ë è ö à 5
Õàðàêòåðèñòèêà
âû÷èñëèòåëüíîé
ñëîæíîñòè
Îöåíêà ñëîæíîñòè 2D ïðåîáðàçîâàíèé 16 16�
Ïðåäëîæåííîãî Í.265 [5, 6] Èç [13] Èç [14]
Óìåíüøåíèå îòíîñèòåëüíî
[14] [5, 6]
Óìíîæåíèå 256 2752 1152 992 Â 3,88 ðàçà Â 10,75 ðàçà
Ñëîæåíèå � ñäâèã 3392 � 1600 3200 � 512 2304 2592
Íà 92,6 %
áîëüøå
ñëîæåíèé
Íà 34,5 %
áîëüøå
ñëîæåíèé
×èñëî èòåðàöèé
äëÿ 1D
5 4 5 6
Íà 1 èòåðà-
öèþ ìåíüøå
Íà îäíó
èòåðàöèþ
áîëüøå
Ïàìÿòü äëÿ
êâàíòîâàíèÿ
— — � — — —
×èñëî áèòîâ
ýëåìåíòà ìàòðèöû
9 8 10 14
Íà 5 áèò
ìåíüøå
Íà 1 áèò
áîëüøå
Ò à á ë è ö à 6
Êëàññ
Èçîáðàæåíèå
ñ áëîêàìè
8 8�
Ðåçóëüòàòû ýôôåêòèâíîñòè êîäèðîâàíèÿ ïî õàðàêòåðèñòèêå
PSNR, äÁ (ÑÊÎ, â óðîâíÿõ ÿðêîñòè) äëÿ QP
22 27 32 37 42
À
1920 1072�
Ôîòî
� 0,095
(0,05)
� 0,017
(� 0,024)
� 0,015
(� 0,038)
� 0,016
(� 0,06)
� 0,01
(� 0,063)
Ñîáîð
� 0,368
(� 0,111)
� 0,146
(� 0,093)
� 0,078
(� 0,106)
� 0,065
(� 0,181)
� 0,05
(� 0,283)
Ïåéçàæ 1
� 0,264
(� 0,19)
� 0,062
(� 0,139)
� 0,039
(� 0,201)
� 0,034
(� 0,326)
� 0,024
(� 0,416)
C
1280 720�
Ôîòî
� 0,104
(� 0,056)
� 0,02
(� 0,027)
� 0,018
(� 0,043)
� 0,021
(� 0,086)
� 0,012
(� 0,084)
Ïåéçàæ 2
� 0,189
(� 0,194)
� 0,047
(� 0,14)
� 0,037
(� 0,264)
� 0,034
(� 0,578)
� 0,022
(� 0,741)
Ñðåäíåå çíà÷åíèå
� 0,204
(� 0,100)
� 0,058
(� 0,085)
� 0,037
(� 0,130)
� 0,034
(� 0,246)
� 0,024
(� 0,317)
õàðàêòåðèñòèêàì PSNR, ÑÊÎ è êîýôôèöèåíòó ñæàòèÿ K ïî ïÿòè òåñòîâûì èçîáðà-
æåíèÿì êëàññîâ À è Ñ ñ áëîêàìè 8 8� (16 16� ).
Ïðåäëîæåííîå öåëî÷èñëåííîå ïðåîáðàçîâàíèå ïîðÿäêà 8 ïî ñðàâíåíèþ ñ ïðå-
îáðàçîâàíèåì â ñòàíäàðòå Í.265 ïî õàðàêòåðèñòèêå PSNR äëÿ ïÿòè òåñòîâûõ èçîáðà-
æåíèé êëàñîâ À è C ïîíèæàåò ñðåäíåå çíà÷åíèå íà 0,204–0,024 äÁ, ïðè ýòîì ñðåäíåå
çíà÷åíèå êîýôôèöèåíòà ñæàòèÿ K óìåíüøàåòñÿ íà 0,058–0,004%.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 5 173
Ò à á ë è ö à 7
Êëàññ
Èçîáðàæåíèå
ñ áëîêàìè
16 16�
Ðåçóëüòàòû ýôôåêòèâíîñòè êîäèðîâàíèÿ ïî õàðàêòåðèñòèêå
PSNR, äÁ (ÑÊÎ, â óðîâíÿõ ÿðêîñòè) äëÿ QP
22 27 32 37 42
À
1920 1072�
Ôîòî
� 0,016
(� 0,011)
� 0,009
(� 0,013)
� 0,004
(� 0,009)
� 0,002
(� 0,008)
� 0,009
(� 0,044)
Ñîáîð
� 0,098
(� 0,036)
� 0,045
(� 0,033)
� 0,033
(� 0,043)
� 0,016
(� 0,045)
� 0,01
(� 0,055)
Ïåéçàæ 1
� 0,056
(� 0,064)
� 0,026
(� 0,068)
� 0,013
(� 0,069)
� 0,008
(� 0,077)
� 0,005
(� 0,077)
C
1280 720�
Ôîòî
� 0,022
(� 0,015)
� 0,008
(� 0,011)
� 0,003
(� 0,008)
� 0,005
(� 0,016)
� 0,009
(0)
Ïåéçàæ 2
� 0,084
(� 0,094)
� 0,034
(� 0,096)
� 0,018
(� 0,122)
� 0,009
(� 0,15)
� 0,004
(� 0,118)
Ñðåäíåå çíà÷åíèå
� 0,055
(� 0,044)
� 0,024
(� 0,044)
� 0,014
(� 0,050)
� 0,008
(� 0,059)
� 0,007
(� 0,059)
Ò à á ë è ö à 8
Êëàññ
Èçîáðàæåíèå
ñ áëîêàìè
8 8� (16 16� )
Êîýôôèöèåíò ñæàòèÿ K:1 äëÿ QP
22 27 32 37 42
À
1920 1072�
Ôîòî 5,62 (6,07) 10,78 (13,87) 23,11 (31,60) 39,95 (66,14) 54,67 (122,70)
Ñîáîð 10,45 (10,79) 14,67 (16,95) 21,98 (26,23) 32,99 (44,42) 47,08 (76,51)
Ïåéçàæ1 2,87 (2,62) 4,11 (4,83) 8,05 (9,29) 16,27 (19,31) 29,11 (40,49)
C
1280 720�
Ôîòî 5,78 (6,29) 10,17 (13,49) 20,56 (27,54) 36,70 (57,97) 52,30 (109,89)
Ïåéçàæ 2 1,91 (2,00) 2,69 (2,73) 3,98 (4,22) 7,62 (8,31) 16,39 (19,20)
Ñðåäíåå çíà÷åíèå 5,326 (5,55) 8,484 (10,37) 15,536 (19,78) 26,706 (39,23) 39,910 (73,76)
Ò à á ë è ö à 9
Êëàññ
Èçîáðàæåíèå
ñ áëîêàìè
8 8�
( )16 16�
Ðåçóëüòàòû ýôôåêòèâíîñòè êîäèðîâàíèÿ ïî õàðàêòåðèñòèêå
êîýôôèöèåíòà ñæàòèÿ K (â %) äëÿ QP
22 27 32 37 42
À
1920 1072�
Ôîòî
� 0,032
(� 0,032)
� 0,016
(� 0,016)
� 0,006
(� 0,006)
� 0,001
(� 0,001)
0
(0)
Ñîáîð
� 0,062
(� 0,022)
0,037
(� 0,013)
� 0,038
(� 0,007)
� 0,012
(� 0,003)
� 0,002
(� 0,002)
Ïåéçàæ 1
� 0,056
(� 0,056)
� 0,04
(� 0,04)
� 0,015
(� 0,015)
� 0,005
(� 0,005)
� 0,003
(� 0,003)
C
1280 720�
Ôîòî
� 0,018
(� 0,018)
� 0,015
(� 0,015)
� 0,006
(� 0,006)
� 0,002
(� 0,002)
0
(0)
Ïåéçàæ 2
� 0,049
(� 0,049)
� 0,04
(� 0,04)
� 0,023
(� 0,023)
� 0,012
(� 0,012)
� 0,002
(� 0,002)
Ñðåäíåå çíà÷åíèå (â %)
� 0,058
(� 0,035)
� 0,034
(� 0,025)
� 0,007
(� 0,011)
� 0,013
(� 0,005)
� 0,004
(� 0,001)
Äëÿ ïðåäëîæåííîãî öåëî÷èñëåííîãî ïðåîáðàçîâàíèÿ ïîðÿäêà 16 ñðåäíåå
çíà÷åíèå ïî õàðàêòåðèñòèêå PSNR ïîíèæàåòñÿ íà 0,055–0,007 äÁ, à ñðåäíåå çíà-
÷åíèå êîýôôèöèåíòà ñæàòèÿ K óìåíüøàåòñÿ íà 0,035–0,001%.
Ñëåäóåò çàìåòèòü, ÷òî âûñîêîêîððåëèðîâàííûå (ÂÊ) èçîáðàæåíèÿ êëàññà À
ñ áëîêàìè 8 8� , òàêèå êàê ôîòî è Ñîáîð, èìåþò â 1,9–3,6 ðàçà áîëüøèé êîýôôèöè-
åíò ñæàòèÿ äëÿ çàäàííîãî ïàðàìåòðà QP, ÷åì íèçêîêîððåëèðîâàííîå (ÍÊ) èçîáðà-
æåíèå òîãî æå êëàññà ïåéçàæ 1, à ÂÊ èçîáðàæåíèå êëàññà Ñ ôîòî èìååò â 3–5 ðàç
áîëüøèé êîýôôèöèåíò ñæàòèÿ äëÿ çàäàííîãî ïàðàìåòðà QP, ÷åì ÍÊ èçîáðàæå-
174 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 5
Ðèñ. 3. Èñõîäíîå èçîáðàæåíèå Ñîáîðà ðàçìåðà 1920 1072� ñ ôðàãìåíòîì ÷àñîâ (à); óâåëè÷åííîå
èñõîäíîå èçîáðàæåíèå ÷àñîâ, ìàñøòàá 2:1 (á); íà îñíîâå êîäèðîâàíèÿ ñ áëîêàìè 8 8�
ïðåäëîæåííûì ÖÊÏ ïðè ñæàòèè 33:1, PSNR � 37 210, äÁ (â); ñ ïðèìåíåíèåì ÖÊÏ (Í.265) ïðè
ñæàòèè 33:1, PSNR � 37 275, äÁ (ã)
à
âá
ã
íèå òîãî æå êëàññà ïåéçàæ 2. Âûñîêîêîððåëèðîâàííûå èçîáðàæåíèÿ êëàññà À
ñ áëîêàìè 16 16� ôîòî è Ñîáîð èìåþò â 3–4 ðàçà áîëüøèé êîýôôèöèåíò ñæàòèÿ
äëÿ çàäàííîãî ïàðàìåòðà QP, ÷åì ÍÊ èçõîáðàæåíèå òîãî æå êëàññà ïåéçàæ 1,
à ÂÊ èçîáðàæåíèå êëàññà Ñ ôîòî èìååò â 3–7 ðàç áîëüøèé êîýôôèöèåíò ñæàòèÿ
äëÿ çàäàííîãî ïàðàìåòðà QP, ÷åì ÍÊ èçîáðàæåíèå òîãî æå êëàññà ïåéçàæ 2.
Íà ðèñ. 3 ïðåäñòàâëåíî èçîáðàæåíèå Ñîáîðà ñ ôðàãìåíòîì ÷àñîâ, êîòîðîå
ñîãëàñíî òàáë. 6 ïðåäñòàâëÿåò íàèáîëüøóþ ðàçíîñòü ïî õàðàêòåðèñòèêå PSNR,
ðàâíóþ 0,065 äÁ äëÿ ÖÊÏ ñ áëîêàìè 8 8� ïðè QP � 37.
Êàê âèäèì èç ðèñ. 3, â, ã, ïðåäëîæåííîå ÖÊÏ ïîðÿäêà 8 îáåñïå÷èâàåò òàêîå
æå âèçóàëüíîå êà÷åñòâî, êàê è ïðåîáðàçîâàíèå èç ñòàíäàðòà Í.265.
ÇÀÊËÞ×ÅÍÈÅ
Ïðåäëîæåíû îäíîíîðìîâûå ÖÊÏ ïîðÿäêîâ 8, 16 è ðàçðàáîòàíû èõ áûñòðûå
àëãîðèòìû íèçêîé âû÷èñëèòåëüíîé ñëîæíîñòè, êîòîðàÿ â 3–5 ðàç ìåíüøå, ÷åì
â èçâåñòíûõ, è â 10 ðàç ìåíüøå, ÷åì â ñòàíäàðòå Í.265. Îíè îáåñïå÷èâàþò òà-
êîå æå âèçóàëüíîå êà÷åñòâî è êà÷åñòâî ïî õàðàêòåðèñòèêàì PSNR, ÑÊÎ êàê
ïðåîáðàçîâàíèÿ â ñòàíäàðòå Í.265.
Òàêèì îáðàçîì, ðàçðàáîòàííûå ïðåîáðàçîâàíèÿ ìîãóò áûòü ïðåäëîæåíû äëÿ
óëó÷øåíèÿ íîâîãî ñòàíäàðòà Í.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. S M P T E Standard 421 M-2006: VC-1 Compressed Video Bitstream Format and Decoding Process,
2006.
3. P R C 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.
4. C h a m W . K . , F o n g C . K . , L i u Y . , C h e n g C . K . M . An investigation of order-16
transform in AVS-M2606 ABT // AVS-M2657, Dec. 2009.
5. H i g h efficiency video coding (HEVC) text specification draft 6 / B. Bross, W.-J. Han,
G.S. Sullivan , J.-R. Ohm, T. Wiegand (Eds.) / Doñ. JCTVC-H1003, San Jos�, CA, USA, Febr.,
2012.
6. F u l d s e t h A . , B j �o n t e g a a r d G . , B u d a g a v i M . , S z e V . CE10: Core transform
design for HEVC // Doc. JCTVC-G495, Geneva, CH, Nov. 2011.
7. M a S . , K u o C . - C . High-definition video coding with supermacroblocks // Proc. SPIE Vis.
Commun. Image Process. — 2007. — 6508. — P. 650816-1–650816-12.
8. F o n g C . K . , C h a m W . K . Simple order-16 integer transform for video coding // Proc. IEEE
Int. Conf. on Image Processing, Sept. 26–29, Hong Kong, 2010. — P. 161–164.
9. à í à ò ³ â Ë . Î . Ìåòîä ïîáóäîâè ïðîñòèõ ö³ëî÷èñåëüíèõ êîñèíóñíèõ ñòóï³í÷àñòèõ ïåðåòâî-
ðåíü ïîðÿäêó 16 äëÿ âèñîêîåôåêòèâíîãî â³äåîêîäóâàííÿ // Ïðàö³ ì³æíàð. ìîëîä³æ. ìàò. øê.
«Ïèòàííÿ îïòèì³çàö³¿ îá÷èñëåíü (ÏÎÎ-2011)», Óêðà¿íà, Êðèì, ñìò. Êàöèâåë³, 22–29 âåðåñíÿ
2011. — Ñ. 37–38.
10. à í à ò ³ â Ë . Î . , Ë ó ö  . Ê . Ïðîñòå ö³ëî÷èñåëüíå êîñèíóñíå ñòóï³í÷àñòå ïåðåòâîðåííÿ ïî-
ðÿäêó 16 íèçüêî¿ ñêëàäíîñò³ äëÿ âèñîêîåôåêòèâíîãî â³äåîêîäóâàííÿ // Ïðàö³ ì³æíàð. ìîëîä³æ.
ìàò. øê. «Ïèòàííÿ îïòèì³çàö³¿ îá÷èñëåíü (ÏÎÎ-2011)», Óêðà¿íà, Êðèì, ñìò. Êàöèâåë³,
22–29 âåðåñíÿ 2011. — Ñ. 39–40.
11. à í à ò è â Ë . À . Öåëî÷èñëåííûå êîñèíóñíûå ïðåîáðàçîâàíèÿ: ìåòîäû ïîñòðîåíèÿ íîâûõ áûñò-
ðûõ ïðåîáðàçîâàíèé ïîðÿäêà 8,16 è èõ ïðèìåíåíèå // Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. —
2014. — 50, ¹ 6. — Ñ. 104–121.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 5 175
12. J o s h i R . , R e z n i k Y . , K a r c z e w i c z M . Efficient large size transforms for high
perfomance video coding // Proc. SPIE Appl. of Digital Image Process. — XXXIII. 2010. — 7798.
— P. 1–7.
13. J o s h i R . , R e z n i k Y . , S o l e J . , K a r c z e w i c z M . Efficient 16 and 32-point transforms //
Doc. JCTVC-D256. — Daegu, KR, Jan. 2011.
14. A l s h i n a E . , A l s h i n A . , K i m I . - K . , T o p i w a l a P . CE10: Full-factorized core
transform proposal by Samsung/FastVDO // Doc. JCTVC-F251, Torino, Italy, July 2011.
15. U g u r K . , A n d e r s s o n K . , F u l d s e t h A . e t a l . High perfomance low complexity video
coding and the emerging HEVC standard // IEEE Trans. Circuits Syst. Video Technol. — 2012. —
20, N 12. — P. 1688–1697.
16. à í à ò ³ â Ë . Î . Ìåòîä ïîáóäîâè øâèäêèõ ö³ëî÷èñåëüíèõ êîñèíóñíèõ ïåðåòâîðåíü âåëèêî¿
ðîçì³ðíîñò³ äëÿ âèñîêîåôåêòèâíîãî êîäóâàííÿ çîáðàæåíü ³ â³äåî // Ïðàö³ ì³æíàð. êîíô. «Ïèòàííÿ
îïòèì³çàö³¿ îá÷èñëåíü (ÏÎÎ-2013)», Óêðà¿íà, Êðèì, ñìò. Êàöèâåë³, 30 âåðåñíÿ 2013. — Ñ. 66–67.
17. Ø å â ÷ ó ê Á . Ì . , Ç à ä ³ ð à ê à Â . Ê . , Ã í à ò ³ â Ë . Î . , Ô ð à º ð Ñ . Â . Òåõíîëîã³ÿ áàãàòî-
ôóíêö³îíàëüíî¿ îáðîáêè ³ ïåðåäà÷³ ³íôîðìàö³¿ â ìîí³òîðèíãîâèõ ìåðåæàõ. — Ê.: Íàóê. äóìêà,
2010. — 378 ñ.
18. Ð è ÷ à ð ä ñ î í ß . Âèäåîêîäèðîâàíèå. H.264 è MPEG-4 — ñòàíäàðòû íîâîãî ïîêîëåíèÿ. —
Ì.: Òåõíîñôåðà, 2005. — 368 ñ.
Íàä³éøëà äî ðåäàêö³¿ 23.12.2015
Ë.Î. Ãíàò³â
Ö²ËÎ×ÈÑÅËÜͲ ÊÎÑÈÍÓÑͲ ÏÅÐÅÒÂÎÐÅÍÍß ÄËß ÂÈÑÎÊÎÅÔÅÊÒÈÂÍÎÃÎ
ÊÎÄÓÂÀÍÍß ÇÎÁÐÀÆÅÍÜ ² ²ÄÅÎ
Àíîòàö³ÿ. Ðîçãëÿíóòî ìàòðè÷í³ ìåòîäè ïîáóäîâè îäíîíîðìîâèõ ö³ëî÷èñåëü-
íèõ êîñèíóñíèõ ïåðåòâîðåíü ïîðÿäê³â 8, 16. Çàïðîïîíîâàíî îäíîíîðìîâ³
ö³ëî÷èñåëüí³ ïåðåòâîðåííÿ ïîðÿäê³â 8, 16 òà ðîçðîáëåíî ¿õí³ øâèäê³ àëãî-
ðèòìè íèçüêî¿ îá÷èñëþâàëüíî¿ ñêëàäíîñò³, ÿêà ìåíøà â 3–5 ðàç³â, í³æ
ó â³äîìèõ àëãîðèòì³â, òà â 10 ðàç³â ìåíøà, í³æ ó ñòàíäàðò³ Í.265.
Êëþ÷îâ³ ñëîâà: äèñêðåòíå êîñèíóñíå ïåðåòâîðåííÿ, ö³ëî÷èñåëüíå êîñèíóñ-
íå ïåðåòâîðåííÿ, ôàêòîðèçàö³ÿ, øâèäêå ïåðåòâîðåííÿ, ìàcøòàáîâàíå ïåðå-
òâîðåííÿ, åôåêòèâí³ñòü êîäóâàííÿ, êîåô³ö³ºíò ñòèñíåííÿ, îá÷èñëþâàëüíà
ñêëàäí³ñòü, â³äåîêîäóâàííÿ, Í.264, H.265, HEVC, AVS.
L.O. Hnativ
²NTEGER COSINE TRANSFORMS FOR HIGH-EFFICIENCY IMAGE AND VIDEO CODING
Abstract. Matrix methods of constructing one-norm integer cosine transforms of
order-8,16 are considered. The one-norm order-8 and 16 integer transforms are
proposed and their fast algorithms of low computational complexity are developed
whose computational complexity is 3 to 5 time less than that in the well-known
algorithms and is 10 time less than one in standard H.265.
Keywords: discrete cosine transform, integer cosine transform, factorization, fast
transform, scaled transform, coding gain, compression ratio, computational
complexity, video coding, Í.264, H.265, HEVC, AVS.
Ãíàòèâ Ëåâ Àëåêñååâè÷,
êàíäèäàò òåõí. íàóê, ñòàðøèé íàó÷íûé ñîòðóäíèê Èíñòèòóòà êèáåðíåòèêè èì. Â.Ì. Ãëóøêîâà ÍÀÍ
Óêðàèíû, Êèåâ, e-mail: levhnativ@gmail.com.
176 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2016, òîì 52, ¹ 5
|