Целочисленное косинусное преобразование высокого порядка: метод построения и быстрые алгоритмы для кодирования изображений и видео с высоким разрешением

Предложен матричный метод построения однонормового целочисленного косинусного преобразования высокого порядка. Построено однонормовое целочисленное преобразование порядка 32 и разработаны его быстрые алгоритмы низкой вычислительной сложности (меньшей в 3,24 раза, чем в известных алгоритмах, и в 15,6...

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Datum:	2017
1. Verfasser:	Гнатив, Л.А.
Format:	Artikel
Sprache:	Russian
Veröffentlicht:	Інститут кібернетики ім. В.М. Глушкова НАН України 2017
Schriftenreihe:	Кибернетика и системный анализ
Schlagworte:	Програмно-технічні комплекси
Online Zugang:	http://dspace.nbuv.gov.ua/handle/123456789/144781
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:	Целочисленное косинусное преобразование высокого порядка: метод построения и быстрые алгоритмы для кодирования изображений и видео с высоким разрешением / Л.А. Гнатив // Кибернетика и системный анализ. — 2017. — Т. 53, № 4. — С. 141–154. — Бібліогр.: 19 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-144781
record_format	dspace
spelling	irk-123456789-1447812019-01-04T01:23:22Z Целочисленное косинусное преобразование высокого порядка: метод построения и быстрые алгоритмы для кодирования изображений и видео с высоким разрешением Гнатив, Л.А. Програмно-технічні комплекси Предложен матричный метод построения однонормового целочисленного косинусного преобразования высокого порядка. Построено однонормовое целочисленное преобразование порядка 32 и разработаны его быстрые алгоритмы низкой вычислительной сложности (меньшей в 3,24 раза, чем в известных алгоритмах, и в 15,6 раз — чем в стандарте Н.265), и они требуют только целочисленных операций. Это преобразование не только наиболее близкое к дискретному косинусному преобразованию, но и имеет превосходные характеристики кодирования. Запропоновано матричний метод побудови однонормового цілочисельного косинусного перетворення високого порядку. Побудовано однонормове цілочисельне перетворення порядку 32 і розроблено його швидкі алгоритми низької обчислювальної складності (яка менша в 3,24 рази, ніж у відомих алгоритмах, та в 15,6 разів, ніж у стандарті Н.265), і вони потребують тільки цілочисельних операцій. Це перетворення не тільки найближче до дискретного косинусного перетворення, але також має відмінні характеристики кодування. Matrix method of constructing one-norm high integer cosine transform is proposed. The one-norm order-32 integer transform is constructed and its fast algorithms of low computational complexity are developed, whose computational complexity is 3.24 times less than that in the well-known algorithms and is 15.6 times less than one in standard H.265 and requires integer operations only. This transform is not only very close to the discrete cosine transform, but also has excellent coding performance. 2017 Article Целочисленное косинусное преобразование высокого порядка: метод построения и быстрые алгоритмы для кодирования изображений и видео с высоким разрешением / Л.А. Гнатив // Кибернетика и системный анализ. — 2017. — Т. 53, № 4. — С. 141–154. — Бібліогр.: 19 назв. — рос. 0023-1274 http://dspace.nbuv.gov.ua/handle/123456789/144781 681.391, 681.3, 621.372 ru Кибернетика и системный анализ Інститут кібернетики ім. В.М. Глушкова НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Russian
topic	Програмно-технічні комплекси Програмно-технічні комплекси
spellingShingle	Програмно-технічні комплекси Програмно-технічні комплекси Гнатив, Л.А. Целочисленное косинусное преобразование высокого порядка: метод построения и быстрые алгоритмы для кодирования изображений и видео с высоким разрешением Кибернетика и системный анализ
description	Предложен матричный метод построения однонормового целочисленного косинусного преобразования высокого порядка. Построено однонормовое целочисленное преобразование порядка 32 и разработаны его быстрые алгоритмы низкой вычислительной сложности (меньшей в 3,24 раза, чем в известных алгоритмах, и в 15,6 раз — чем в стандарте Н.265), и они требуют только целочисленных операций. Это преобразование не только наиболее близкое к дискретному косинусному преобразованию, но и имеет превосходные характеристики кодирования.
format	Article
author	Гнатив, Л.А.
author_facet	Гнатив, Л.А.
author_sort	Гнатив, Л.А.
title	Целочисленное косинусное преобразование высокого порядка: метод построения и быстрые алгоритмы для кодирования изображений и видео с высоким разрешением
title_short	Целочисленное косинусное преобразование высокого порядка: метод построения и быстрые алгоритмы для кодирования изображений и видео с высоким разрешением
title_full	Целочисленное косинусное преобразование высокого порядка: метод построения и быстрые алгоритмы для кодирования изображений и видео с высоким разрешением
title_fullStr	Целочисленное косинусное преобразование высокого порядка: метод построения и быстрые алгоритмы для кодирования изображений и видео с высоким разрешением
title_full_unstemmed	Целочисленное косинусное преобразование высокого порядка: метод построения и быстрые алгоритмы для кодирования изображений и видео с высоким разрешением
title_sort	целочисленное косинусное преобразование высокого порядка: метод построения и быстрые алгоритмы для кодирования изображений и видео с высоким разрешением
publisher	Інститут кібернетики ім. В.М. Глушкова НАН України
publishDate	2017
topic_facet	Програмно-технічні комплекси
url	http://dspace.nbuv.gov.ua/handle/123456789/144781
citation_txt	Целочисленное косинусное преобразование высокого порядка: метод построения и быстрые алгоритмы для кодирования изображений и видео с высоким разрешением / Л.А. Гнатив // Кибернетика и системный анализ. — 2017. — Т. 53, № 4. — С. 141–154. — Бібліогр.: 19 назв. — рос.
series	Кибернетика и системный анализ
work_keys_str_mv	AT gnativla celočislennoekosinusnoepreobrazovanievysokogoporâdkametodpostroeniâibystryealgoritmydlâkodirovaniâizobraženijivideosvysokimrazrešeniem
first_indexed	2025-07-10T20:08:14Z
last_indexed	2025-07-10T20:08:14Z
_version_	1837291905551958016
fulltext	ÓÄÊ 681.391, 681.3, 621.372 Ë.À. ÃÍÀÒÈÂ ÖÅËÎ×ÈÑËÅÍÍÎÅ ÊÎÑÈÍÓÑÍÎÅ ÏÐÅÎÁÐÀÇÎÂÀÍÈÅ ÂÛÑÎÊÎÃÎ ÏÎÐßÄÊÀ: ÌÅÒÎÄ ÏÎÑÒÐÎÅÍÈß È ÁÛÑÒÐÛÅ ÀËÃÎÐÈÒÌÛ ÄËß ÊÎÄÈÐÎÂÀÍÈß ÈÇÎÁÐÀÆÅÍÈÉ È ÂÈÄÅÎ Ñ ÂÛÑÎÊÈÌ ÐÀÇÐÅØÅÍÈÅÌ Àííîòàöèÿ. Ïðåäëîæåí ìàòðè÷íûé ìåòîä ïîñòðîåíèÿ îäíîíîðìîâîãî öåëî- ÷èñëåííîãî êîñèíóñíîãî ïðåîáðàçîâàíèÿ âûñîêîãî ïîðÿäêà. Ïîñòðîåíî îäíî- íîðìîâîå öåëî÷èñëåííîå ïðåîáðàçîâàíèå ïîðÿäêà 32 è ðàçðàáîòàíû åãî áûñò- ðûå àëãîðèòìû íèçêîé âû÷èñëèòåëüíîé ñëîæíîñòè (ìåíüøåé â 3,24 ðàçà, ÷åì â èçâåñòíûõ àëãîðèòìàõ, è â 15,6 ðàç — ÷åì â ñòàíäàðòå Í.265), è îíè òðå- áóþò òîëüêî öåëî÷èñëåííûõ îïåðàöèé. Ýòî ïðåîáðàçîâàíèå íå òîëüêî íàèáî- ëåå áëèçêîå ê äèñêðåòíîìó êîñèíóñíîìó ïðåîáðàçîâàíèþ, íî è èìååò ïðåâîñ- õîäíûå õàðàêòåðèñòèêè êîäèðîâàíèÿ. Êëþ÷åâûå ñëîâà: äèñêðåòíîå êîñèíóñíîå ïðåîáðàçîâàíèå, öåëî÷èñëåííîå êî- ñèíóñíîå ïðåîáðàçîâàíèå, ìàñøòàáèðîâàííîå ïðåîáðàçîâàíèå, ôàêòîðèçàöèÿ, áûñòðîå ïðåîáðàçîâàíèå, ýôôåêòèâíîñòü êîäèðîâàíèÿ, âû÷èñëèòåëüíàÿ ñëîæ- íîñòü, êîýôôèöèåíò ñæàòèÿ, âèäåîêîäèðîâàíèå, Í.264, H.265, AVS. ÂÂÅÄÅÍÈÅ Ýôôåêòèâíûìè èíñòðóìåíòàìè äëÿ óñòðàíåíèÿ èçáûòî÷íîñòè â èçîáðàæåíèÿõ è âèäåîñèãíàëàõ ÿâëÿþòñÿ ìåòîäû ñæàòèÿ, îñíîâàííûå íà ìîäèôèêàöèè è ñæàòèè ðåçóëüòàòîâ ïðåîáðàçîâàíèÿ, èëè òàê íàçûâàåìûå ìåòîäû òðàíñôîð- ìàöèîííîãî êîäèðîâàíèÿ [1]. Ñèñòåìû êîäèðîâàíèÿ ñ ïðåîáðàçîâàíèåì, îñíî- âàííûå íà ðàçëè÷íûõ äèñêðåòíûõ ïðåîáðàçîâàíèÿõ, äîñòàòî÷íî õîðîøî èññëå- äîâàíû è èçó÷åíû. Âûáîð íàèëó÷øåãî ïðåîáðàçîâàíèÿ äëÿ êîíêðåòíîãî ïðè- ëîæåíèÿ çàâèñèò îò âåëè÷èíû äîïóñòèìîé îøèáêè âîññòàíîâëåíèÿ è îò èìåþùèõñÿ âû÷èñëèòåëüíûõ ðåñóðñîâ. Ñæàòèå æå âîçíèêàåò íå â ïðîöåññå ïðåîáðàçîâàíèÿ, à íà ýòàïå êâàíòîâàíèÿ ïîëó÷åííûõ êîýôôèöèåíòîâ. Ñòàíäàðòû ñæàòèÿ âèäåîäàííûõ ðàñøèðÿþò òðàíñôîðìàöèîííûå ìåòîäû ñæàòèÿ íåïîäâèæíûõ èçîáðàæåíèé ïóòåì ñîêðàùåíèÿ âðåìåííîé èëè ìåæêàäðî- âîé èçáûòî÷íîñòè. Õîòÿ â íàñòîÿùåå âðåìÿ èìåþòñÿ ðàçëè÷íûå ñòàíäàðòû êîäè- ðîâàíèÿ, òåì íå ìåíåå áîëüøèíñòâî èç íèõ îñíîâàíî íà èñïîëüçîâàíèè ïîäîáíûõ ìåòîäîâ ñæàòèÿ âèäåîäàííûõ. Öåëü ýòàïà ïðåîáðàçîâàíèÿ ïðè îáðàáîòêå âèäåî- êîäåêîì — îòîáðàæåíèå öèôðîâûõ äàííûõ ïîëíûõ èëè îñòàòî÷íûõ êàäðîâ â äðóãóþ êîîðäèíàòíóþ îáëàñòü (îáëàñòü ïðåîáðàçîâàíèÿ). Âûáîð òàêîãî ïðåîá- ðàçîâàíèÿ îïðåäåëÿåòñÿ ïî ìíîãèì êðèòåðèÿì [2]. 1. Öèôðîâûå äàííûå, îòîáðàæàåìûå â îáëàñòü ïðåîáðàçîâàíèÿ, äîëæíû áûòü äåêîððåëèðîâàííûìè è êîìïàêòíûìè (ò.å. áîëüøàÿ ÷àñòü ýíåðãèè ïðåîáðà- çîâàííûõ äàííûõ äîëæíà áûòü ñêîíöåíòðèðîâàíà â ìàëîì ÷èñëå êîýôôèöèåíòîâ ïðåîáðàçîâàíèÿ). 2. Ïðåîáðàçîâàíèå äîëæíî áûòü îáðàòèìûì. 3. Ïðåîáðàçîâàíèå äîëæíî áûòü ýôôåêòèâíûì îòíîñèòåëüíî åãî âû÷èñëè- ìîñòè (ìàëûé îáúåì òðåáóåìîé ïàìÿòè, âîçìîæíîñòü ðåàëèçàöèè â àðèôìåòèêå ñ îãðàíè÷åííîé òî÷íîñòüþ âû÷èñëåíèé, ìàëîå ÷èñëî àðèôìåòè÷åñêèõ îïåðàöèé â àëãîðèòìå è ò.ä.) Äëÿ ñæàòèÿ èçîáðàæåíèé è âèäåî ñóùåñòâóåò ìíîãî ïðåîáðàçîâàíèé, íî âñå îíè ðàçäåëÿþòñÿ íà äâå êàòåãîðèè: ïðåîáðàçîâàíèÿ íà îñíîâå áëîêîâ è ïðåîáðà- çîâàíèÿ íà îñíîâå èçîáðàæåíèé. Ïðèìåðàìè ïðåîáðàçîâàíèé íà îñíîâå áëîêîâ ÿâëÿþòñÿ ïðåîáðàçîâàíèÿ Êà- ðóíåíà–Ëîýâà (KLT), ðàçëîæåíèå ïî ñèíãóëÿðíûì ÷èñëàì (SVD) è íàèáîëåå èç- âåñòíîå äèñêðåòíîå êîñèíóñíîå ïðåîáðàçîâàíèå (ÄÊÏ). Â êàæäîì òàêîì ïðåîá- ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2017, òîì 53, ¹ 4 141 © Ë.À. Ãíàòèâ, 2017 ðàçîâàíèè èñïîëüçóþòñÿ áëîêè N N� ñýìïëîâ èñõîäíîãî èëè îñòàòî÷íîãî èçî- áðàæåíèÿ. Áëîêîâûå ïðåîáðàçîâàíèÿ èìåþò íèçêèå òðåáîâàíèÿ ê îáúåìó ïàìÿòè è ÿâëÿþòñÿ ýôôåêòèâíûìè ïðè ñæàòèè îñòàòî÷íûõ èçîáðàæåíèé, ïîëó÷åííûõ íà îñíîâå áëîêîâîé êîìïåíñàöèè äâèæåíèÿ. Îäíàêî îíè óÿçâèìû äëÿ àðòåôàêòîâ, âîçíèêàþùèõ íà ñòûêå áëîêîâ, ÷òî ïðèâîäèò ê ïîÿâëåíèþ áëî÷íîñòè. Ïðåîáðàçîâàíèÿ íà îñíîâå èçîáðàæåíèé ðàáîòàþò ñ öåëûì êàäðîì (èëè áîëü- øîé ÷àñòüþ èçîáðàæåíèÿ). Èç òàêîãî òèïà ïðåîáðàçîâàíèé íàèáîëåå èçâåñòíûì ÿâ- ëÿåòñÿ äèñêðåòíîå âåéâëåò-ïðåîáðàçîâàíèå (ÄÂÏ). Òàêèå ïðåîáðàçîâàíèÿ èçîáðàæå- íèé ïðåâîñõîäÿò áëîêîâûå ïðåîáðàçîâàíèÿ ïðè ñæàòèè íåïîäâèæíûõ èçîáðàæåíèé, íî ïðè ýòîì òðåáóåòñÿ áîëüøîé îáúåì ïàìÿòè (ïîñêîëüêó íåîáõîäèìî õðàíèòü öå- ëèêîì âåñü êàäð èëè áîëüøóþ åãî ÷àñòü), è îíè ïëîõî ñî÷åòàþòñÿ ñ êîìïåíñàöèåé äâèæåíèÿ íà îñíîâå áëîêîâ. Ïðåîáðàçîâàíèÿ ÄÊÏ è ÄÂÏ ðåàëèçîâàíû â ñòàíäàðòå MPEG-4 Visual [2]. Â çàâèñèìîñòè îò ïðåäíàçíà÷åíèÿ ñòàíäàðòû ïîäðàçäåëÿþòñÿ íà äâå áîëüøèå ãðóïïû: ñòàíäàðòû äëÿ âèäåîêîíôåðåíöèé è ìóëüòèìåäèéíûå ñòàíäàðòû. Ñîâðåìåííûå âèäåîñòàíäàðòû, òàêèå, êàê Í.264/AVC [2, 3], VC-1 [4], AVS [5], Í.265/HEVC [6, 7], èñïîëüçóþò öåëî÷èñëåííûå êîñèíóñíûå ïðåîáðàçîâàíèÿ (ÖÊÏ) ðàçìåðîâ â ïðåäåëàõ îò 4 äî 32. Ñðåäè èçâåñòíûõ ïðåîáðàçîâàíèé äèñêðåòíîå êîñèíóñíîå ïðåîáðàçîâàíèå îáåñïå÷èâàåò óïàêîâêó íàèáîëüøåãî êîëè- ÷åñòâà èíôîðìàöèè â íàèìåíüøåå ÷èñëî êîýôôèöèåíòîâ (äëÿ áîëüøèíñòâà ðåàëü- íûõ èçîáðàæåíèé), à òàêæå ìèíèìèçèðóåò ýôôåêò ïîÿâëåíèÿ áëî÷íîé ñòðóêòóðû (èñêóññòâåííûõ èñêàæåíèé), íàçûâàåìîé áëîêîâûìè èñêàæåíèÿìè (àðòåôàêòàìè), êîãäà íà èçîáðàæåíèè ïðîÿâëÿþòñÿ ãðàíèöû ìåæäó ñîñåäíèìè áëîêàìè. Êðîìå ýòîãî, ÄÊÏ èìååò áûñòðûå àëãîðèòìû âû÷èñëåíèÿ. Ñîâðåìåííûå ñòàíäàðòû âè- äåîêîäèðîâàíèÿ ïðèìåíÿþò öåëî÷èñëåííóþ ðåàëèçàöèþ ÄÊÏ. Ýòî ñâÿçàíî ñ òåì, ÷òî âû÷èñëåíèå ÖÊÏ âûïîëíÿåòñÿ áåç ïëàâàþùåé çàïÿòîé è åãî ÿäðî ñîäåðæèò òîëüêî öåëûå è óïàêîâûâàåò ýíåðãèþ ïîäîáíî ÄÊÏ. Îäíàêî ïðåîáðàçîâàíèÿ, èñ- ïîëüçóåìûå â ñòàíäàðòå Í.265, íå èìåþò áûñòðûõ àëãîðèòìîâ, ÷òî ïðèâîäèò ê çíà- ÷èòåëüíûì âû÷èñëèòåëüíûì çàòðàòàì ïðè áîëüøèõ ðàçìåðàõ 2D ïðåîáðàçîâàíèÿ. Â ðàáîòàõ [8–10] ðàññìîòðåíû ïðåîáðàçîâàíèÿ, îñíîâàííûå íà öåëî÷èñëåííîé àïïðîêñèìàöèè ÄÊÏ ñ áûñòðûìè àëãîðèòìàìè ìåíüøåé âû÷èñëèòåëüíîé ñëîæ- íîñòè, ÷åì ïðåîáðàçîâàíèÿ â ñòàíäàðòå Í.265. Â [11] ïðåäëîæåí ìåòîä ïîñòðîåíèÿ ÖÊÏ ñ áûñòðûìè àëãîðèòìàìè, à â [12] ïðåäëîæåíî ÖÊÏ ïîðÿäêà 32 ñ áûñòðûìè àëãîðèòìàìè íèçêîé âû÷èñëèòåëüíîé ñëîæíîñòè, êîòîðàÿ ìåíüøå â 1,5 è 2,7 ðàçà, ÷åì ñîîòâåòñòâåííî â èçâåñòíûõ àëãîðèòìàõ èç [9] è èç [10], è â 13 ðàç ìåíüøå, ÷åì â ñòàíäàðòå Í.265 [7]. Â [13, 14] ïðåäëîæåí ìåòîä ïîñòðîåíèÿ ÖÊÏ ïîðÿäêîâ 8 è 16 ñ áûñòðûìè àë- ãîðèòìàìè, êîòîðûå â îòëè÷èå îò èçâåñòíûõ àëãîðèòìîâ [9, 10] èìåþò â 3–5 ðàç ìåíüøóþ âû÷èñëèòåëüíóþ ñëîæíîñòü è â 10 ðàç ìåíüøóþ, ÷åì ïðåîáðàçîâàíèÿ â ñòàíäàðòå Í.265. Â [15] áûëî ïðåäëîæåíî íåñêîëüêî ýôôåêòèâíûõ ìåòîäîâ óìåíüøåíèÿ ñëîæíîñòè êîäåðà, òàêèõ, êàê óëó÷øåííîå êîäèðîâàíèå intra-picture è óïðîùåííûå VLC êîýôôèöèåíòû. Â íàñòîÿùåé ñòàòüå ïðåäëîæåí ìàòðè÷íûé ìåòîä ïîñòðîåíèÿ îäíîíîðìîâîãî öåëî÷èñëåííîãî êîñèíóñíîãî ïðåîáðàçîâàíèÿ âûñîêîãî ïîðÿäêà è íà åãî îñíîâå ïî- ñòðîåíî îäíîíîðìîâîå ÖÊÏ ïîðÿäêà 32 ñ àëãîðèòìàìè áûñòðûõ öåëî÷èñëåííûõ ïðåîáðàçîâàíèé, êîòîðûå ïðèâîäÿò ê ñóùåñòâåííîìó ñîêðàùåíèþ âû÷èñëåíèé, ò.å. èìåþò íèçêóþ âû÷èñëèòåëüíóþ ñëîæíîñòü. Ýêñïåðèìåíòàëüíûå ðåçóëüòàòû ïîêàçà- ëè, ÷òî ýòî ïðåîáðàçîâàíèå èìååò òàêèå æå ïðåâîñõîäíûå õàðàêòåðèñòèêè êîäèðîâà- íèÿ, êàê è ïðåîáðàçîâàíèå â ñòàíäàðòå Í.265, ò.å. áîëåå áëèçêîå ê ÄÊÏ. ÌÅÒÎÄ ÏÎÑÒÐÎÅÍÈß ÎÄÍÎÍÎÐÌÎÂÎÃÎ ÖÅËÎ×ÈÑËÅÍÍÎÃÎ ÊÎÑÈÍÓÑÍÎÃÎ ÏÐÅÎÁÐÀÇÎÂÀÍÈß ÏÎÐßÄÊÀ 32 Ðàññìîòðèì ìåòîä ïîñòðîåíèÿ îäíîíîðìîâîãî ÖÊÏ ïîðÿäêà 32, êîòîðûé ïðåä- ñòàâëåí â ðàáîòå [11]. Ïóñòü ìàòðèöà ICT32 * ðàçìåðà 32 32� ÖÊÏ ñ ïåðåñòàâëåííûìè ñòðîêàìè ïî- ëó÷åíà èç ìàòðèöû ICT32 ïåðåñòàíîâêîé ñòðîê ñíà÷àëà íà îñíîâå äâîè÷íî-èí- 142 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2017, òîì 53, ¹ 4 âåðñíûõ ïåðåñòàíîâîê (ÄÈÏ), à çàòåì îáðàòíûõ (èíâåðñíûõ) ïåðåñòàíîâîê (ÎÏ) è ïåðåñòàíîâîê ïî êîäó Ãðåÿ (ÏÊÃ) [16]: ICT P P P ICT32 2 1 32 32 � � , (1) ãäå P32 — ìàòðèöà 32 32� ÄÈÏ; P1 — áëî÷íî-äèàãîíàëüíàÿ ìàòðèöà 32 32� ñ åäèíè÷íûìè ìàòðèöàìè I12 ðàçìåðà 12 12� , I 8 ðàçìåðà 8 8� , ìàòðèöàìè îáðàò- íûõ ïåðåñòàíîâîê I 4 ðàçìåðà 4 4� è I 8 ðàçìåðà 8 8� ; P I I I I1 12 4 8 8� diag [ , , , ], I Ik k� antidiag [ ], k � 4 8, , I 4 , I 8 — àíòèäèàãîíàëüíûå åäèíè÷íûå ìàòðèöû ðàçìåðà 4 4� è 8 8� ; P2 — áëî÷íî-äèàãîíàëüíàÿ ìàòðèöà, ñîäåðæàùàÿ ìàòðèöû G4 ðàçìåðà 4 4� ÏÊÃ è P4 ÄÈÏ, G I I4 2 2� diag [ , ], P I4 21 1� diag [ , , ], I 2 — ìàòðèöà ðàçìåðà 2 2� ÎÏ, P G I G I G2 8 2 4 2 8� � � � �diag [ , , ], � �G G P8 4 4diag [ , ], I 2 1 1 � � � �� . Çäåñü ñèìâîë � îçíà÷àåò îïåðàöèþ êðîíåêåðîâñêîãî ïðîèçâåäåíèÿ ìàòðèö, I 2 — åäèíè÷íàÿ ìàòðèöà 2 2� , �G8 — áëî÷íî-äèàãîíàëüíàÿ ìàòðèöà 8 8� , ñîäåðæàùàÿ ìàòðèöû G4 è P4 . Ìàòðèöà ICT32 � ðàçìåðà 32 32� ÖÊÏ ñ ïåðåñòàâëåííûìè ñòðîêàìè ìîæåò áûòü èçîáðàæåíà ìàòðèöåé ÿäðà ÖÊÏ: ICT B C32 32 32 � �� , (2) ãäå C32 � — ìàòðèöà 32 32� ÿäðà ÖÊÏ ñ ïåðåñòàâëåííûìè ñòðîêàìè, B32 — äè- àãîíàëüíàÿ ìàòðèöà 32 32� êîýôôèöèåíòîâ íîðìèðîâàíèÿ. Ìàòðèöà C32 � ìîæåò áûòü ïðåäñòàâëåíà ðåêóððåíòíûì ìåòîäîì [11]: C C Q H32 16 16 32 � � �� diag [ , ] , (3) ãäå C16 � — ìàòðèöà 16 16� ÿäðà ÖÊÏ ñ ïåðåñòàâëåííûìè ñòðîêàìè íà îñíîâå ÄÊÏ, ÏÊÃ è ÎÏ; H 32 * — ôàêòîð-ìàòðèöà 32 32� ñ íåíóëåâûìè ýëåìåíòàìè 1; Q16 — ìàòðèöà 16 16� , êîòîðàÿ ìîæåò áûòü ïðåäñòàâëåíà ìàòðèöåé ÖÊÏ òè- ïà IV (ÖÊÏ-IV): Q C I16 16 16� IV* , I I16 16� antidiag [ ], (4) ãäå C 16 IV� — ìàòðèöà 16 16� ÿäðà ÖÊÏ-IV ñ ïåðåñòàâëåííûìè ñòðîêàìè, I16 — àíòèäèàãîíàëüíàÿ åäèíè÷íàÿ ìàòðèöà 16 16� . Ìàòðèöà C 16 IV� ìîæåò áûòü ïðåäñòàâëåíà ÷åðåç ìàòðèöó ÖÊÏ òèïà ²² (ÖÊÏ-²²) [12]: C H T T R T G P T 16 16 0 8 8 16 8 8 8 8 IV diag� � � �� [ , ] , , (5) ãäå T8 � — ìàòðèöà 8 8� ÿäðà ÖÊÏ-²² (èëè ÖÊÏ) ñ ïåðåñòàâëåííûìè ñòðîêàìè íà îñíîâå ÄÈÏ è ÏÊÃ, P8 — ìàòðèöà 8 8� ÄÈÏ, H 16 0 — ôàêòîð-ìàòðèöà 16 16� ñ íåíóëåâûìè ýëåìåíòàìè 1, êîòîðàÿ íà îñíîâíîé äèàãîíàëè èìååò åäèíè÷íûå ìàòðèöû I 8 ðàçìåðà 8 8� è I 4 ðàçìåðà 4 4� , à íà äðóãîé äèàãî- íàëè — ìàòðèöû G 8 0 è ~ G 8 0 ðàçìåðà 8 8� , G G I 8 0 4 0 4� diag [ , ], ~ [ , ]G G I 8 0 4 0 4= diag � , ~ G 8 0 , G 8 0 — áëî÷íî-äèàãîíàëüíûå ìàòðèöû 8 8� ñ ìàòðè- öàìè G 4 0 ðàçìåðà 4 4� è I 4 , G I 4 0 20 1� diag [ , , ]. Çäåñü R16 — ìàòðèöà 16 16� ðàñòÿãèâàíèÿ (äëÿ ÄÊÏ-IV ïðåäñòàâëÿåò ìàòðèöó âðàùåíèÿ Ãèâåíñà), êîòîðàÿ íà îñíîâíîé äèàãîíàëè ñîäåðæèò öåëûå ýëåìåíòû ri , à íà äðóãîé äèàãîíàëè — öåëûå ýëåìåíòû si , ïðè÷åì r r r r i s si i i i1 2 1 12 7� � � �� , , , ; , i �1 7, . ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2017, òîì 53, ¹ 4 143 Îòìåòèì, ÷òî R r s r s r s r s r s r s r s r s s r s r s r 16 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 8 8 7 7 6 � � � � 6 5 5 4 4 3 3 2 2 1 1 s r s r s r s r s r � � � � � � � � � � � � � � � � � � � � � � � � � � � � . Ìàòðèöà Q16 íà îñíîâàíèè (4) è (5) ìîæåò áûòü ïðåäñòàâëåíà êàê ïðîèçâåäå- íèå ÷åòûðåõ ìàòðèö: Q H T T R I16 16 0 8 8 16 16� � �diag [ , ] (7) èëè ñ ó÷åòîì ïðîèçâåäåíèÿ äâóõ ìàòðèö R I R16 16 16� êàê ïðîèçâåäåíèå òðåõ ìàòðèö: Q H T T R16 16 0 8 8 16� � �diag [ , ] , (8) ãäå R s r s r s r s r s r s r s r s r r s r s r s 16 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 8 8 7 7 6 � � � � 6 5 5 4 4 3 3 2 2 1 1 � � � � � � � � r s r s r s r s r s � � � � � � � � � � � � � � � � � � � � , (9) 144 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2017, òîì 53, ¹ 4 H I I I I 32 16 16 16 16 � � � � � � � , H G I I G I I I 16 0 4 0 8 4 4 0 4 4 4 � � � � � � � � � � � , (6) G 4 0 0 1 1 1 � � � � � � � � , I 4 1 1 1 1 � � � � � � � � , T g g g g g g g g g g g g g g g g f e e f 8 � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � f e e f e f f e e f f e a b c d d c b a � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � b d a c c a d b c a d b b d a c d c b a � � � � � � � � � � � � � � � � � �a b c d , çäåñü � � � � � � �a b c d , e f' '� , � �g n2 . Ìàòðèöà C 16 IV� ÿäðà ÖÊÏ-IV ïîðÿäêà 16 ñîäåðæèò öåëûå ýëåìåíòû �c i2 1, i �1 16, , ai , bi , di , ei , f i , gi , hi è èìååò âèä: Ñ c c c c c c c c c c c c c ñ c c 16 1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 IV* � h h h h h h h h h h h h h h h h d 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 16 � � � � � � � � � � � � � � � � � d d d d d d d d d d d d d d d e e e 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 1 2 3 4 � � � � � � � e e e e e e e e e e e e e b b b b b5 6 7 8 9 10 11 12 13 14 15 16 1 2 3 4 5 6 � � � � � � � � b b b b b b b b b b b g g g g g g � � � � � � � � g g g g g g g g g g f f f f f 7 8 9 10 11 12 13 14 15 16 16 15 14 13 12 f f f f f f f f f f f a a a a a a a 11 10 9 8 7 6 5 4 3 2 1 16 15 14 13 12 11 1 � � � � � � 0 9 8 7 6 5 4 3 2 2 31 29 27 25 23 21 19 1 � � � � � � � � a a a a a a a a a c c c c c c c c 7 15 13 11 9 7 5 3 1 1 2 3 4 5 6 7 8 9 10 c c c c c c c c h h h h h h h h h h � � � � � � � � � h h h h h h d d d d d d d d d d d 11 12 13 14 15 16 1 2 3 4 5 6 7 8 9 10 11 � � � � � � � � � � � � � � � � � � d d d d d e e e e e e e e e 12 13 14 15 16 16 15 14 13 12 11 10 9 8 � � � � � � � � � e e e e e e e b b b b b b b b b b 7 6 5 4 3 2 1 16 15 14 13 12 11 10 9 8 7 b b b b b b g g g g g g g g g g g 6 5 4 3 2 1 16 15 14 13 12 11 10 9 8 7 6 � � � � � � � � �g g g g g f f f f f f f f f f f f f 5 4 3 2 1 1 2 3 4 5 6 7 8 9 10 11 12 13 � � � � � � � � � � f f f a a a a a a a a a a a a a 14 15 16 1 2 3 4 5 6 7 8 9 10 11 12 13 � � � � � � � � � � �a a a14 15 16� � � � � � � � � � � � � � � � � � � � � � � � � , (10) ãäå c c c ci i1 3 2 1 2 1� �� , , i � 2 15, . Äëÿ îäíîíîðìîâîãî ïðåîáðàçîâàíèÿ ìàòðèöà H 16 0 ñîãëàñíî (6) ñîäåðæèò íå- íóëåâûå ýëåìåíòû 1 è Pi mi/ 2 , i �1 3, , Pi — öåëûå. ÖÅËÎ×ÈÑËÅÍÍÎÅ ÊÎÑÈÍÓÑÍÎÅ ÏÐÅÎÁÐÀÇÎÂÀÍÈÅ ÏÎÐßÄÊÀ 16 Ïðåäñòàâèì ìàòðèöó C16 ÿäðà ÖÊÏ ïîðÿäêà 16 [13]: 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 A i 8 8 8 1 1 1 1 � � � � � � � � � � � � � � � � � � � � � � � � � � � � � B e C k C h B j A d H 1 1 8 8 8 � � � � � � � � � � � � � . (11) Òàêèì îáðàçîì, ìàòðèöà C32 ÿäðà ÖÊÏ íà îñíîâàíèè (3), (4) è ñ ó÷åòîì (10), (11) ìîæåò áûòü ïðåäñòàâëåíà êàê ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2017, òîì 53, ¹ 4 145 (12) ãäå c c1 3� , c c ii i2 1 2 1 2 15� �� , , , A B C D E F G H� � � � � � � , a b c d� � � , g e h f� � � , i j� . Ýëåìåíòû ìàòðèöû C32 ïðåäëîæåííîãî îäíîíîðìîâîãî ìàñøòàáèðîâàííîãî ÖÊÏ c i2 1� , ai , bi , di , ei , f i , gi è hi ïðåäñòàâëåíû â òàáë. 1, à ýëåìåíòû ìàòðèöû C16 îäíîíîðìîâîãî ìàñøòàáèðîâàííîãî ÖÊÏ ïîðÿäêà 16 èç ðàáîòû [13], êîòî- ðûå ÿâëÿþòñÿ ýëåìåíòàìè ìàòðèöû C32 , ïðèíèìàþò ñëåäóþùèå çíà÷åíèÿ: À �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 ïðåäñòàâëåíû â òàáë. 2. 146 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2017, òîì 53, ¹ 4 Ò à á ë è ö à 1 Ýëåìåíòû ìàòðèöû C32 Çíà÷åíèÿ ýëåìåíòîâ ìàòðèöû C32 ïðè i 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 c i2 1� 180 180 176 168 164 156 144 136 120 108 92 80 64 44 24 8 ai 206 133 110 111 53 8 49 127 167 139 148 204 176 100 65 31 bi 202 111 50 34 128 133 147 182 105 8 64 168 205 140 98 50 di 170 89 24 132 182 143 47 82 162 174 111 13 122 180 158 59 ei 164 44 106 180 123 27 154 171 61 94 179 135 2 147 176 74 fi 126 13 190 120 20 198 155 38 143 139 69 148 85 90 210 76 gi 119 68 210 32 129 156 90 147 20 188 140 75 143 10 199 87 hi 133 110 156 73 173 45 179 11 182 25 176 59 164 93 145 122 Îòìåòèì, ÷òî ýëåìåíòû ìàòðèöû R16 ñîãëàñíî (6) ïðèíèìàþò ñëåäóþùèå çíà÷åíèÿ: r r1 2 45� � , r3 44� , r4 42� , r5 41� , r6 39� , r7 36� , r8 34� , s1 2� , s2 6� , s s s s3 4 5 611 16 20 23� � � �, , , , s s7 827 30� �, , à ýëåìåíòû ìàòðèöû T8 � ñîãëàñíî (9) ïðèíèìàþò çíà÷åíèÿ: � �a 5, � �b 3, � �c 2, � �d 1, � �e 5, � �f 2, � �g 4. Ñëåäóåò îòìåòèòü, ÷òî êâàäðàòû íîðì áàçèñíûõ âåêòîðîâ ìàòðèöû C32 îäíîíîð- ìîâîãî ìàñøòàáèðîâàííîãî ÖÊÏ ïðèáëèæàþòñÿ ê ÷èñëó ñòåïåíè äâà: q ci i i� � \| \| \| \| 2 524288 � (� i (%) — îòêëîíåíèå ïàðàìåòðà qi ), � i � 0,01–0,43, i �1 3 5 15, , , ,� ; � 2i � 0,11–0,28, i �1 3 5 7, , , ; � 4i � 0,15–0,7. Òàêèì îáðàçîì, ïðåäëîæåííîå öåëî÷èñëåííîå ïðåîáðàçîâàíèå èìååò òàêèå æå ñâîéñòâà, êàê è ïðåîáðàçîâàíèå, ïðèíÿòîå â ñòàíäàðòå Í.265: êîýôôèöèåíòû ïðåîáðà- çîâàíèÿ ïðåäñòàâëÿþò 8 áèò; øèðèíà íàêîïèòåëüíîãî ñóììàòîðà äëÿ ìàòðè÷íîãî óìíîæåíèÿ íå ïðåâûøàåò 32 áèò; ñèììåòðè÷íîñòü/àíòèñèììåòðè÷íîñòü ñîîòâåòñòâóåò ÄÊÏ; êîýôôèöèåíòû ìàñøòàáèðîâàííîãî ïðåîáðàçîâàíèÿ äîñòàòî÷íî áëèçêè ê ÄÊÏ; áàçèñíûå âåêòîðû ïî÷òè îðòîãîíàëüíû; îäèíàêîâàÿ ñõåìà êâàíòîâàíèÿ è äåêâàíòîâà- íèÿ äëÿ ïðåîáðàçîâàíèé âñåõ ðàçìåðîâ; ìíîæèòåëè çàâèñÿò îò ïàðàìåòðà êâàíòîâàíèÿ QP [2] è ñäâèãè çàâèñÿò òîëüêî îò log 2 N , ãäå N — ðàçìåðíîñòü ïðåîáðàçîâàíèÿ; êî- ýôôèöèåíòû êâàíòîâàíèÿ ìîãóò ïðåäñòàâëÿòü 16 áèò. ÀËÃÎÐÈÒÌ ÁÛÑÒÐÎÃÎ ÏÐßÌÎÃÎ ÖÊÏ ÏÎÐßÄÊÀ 32 Ìàòðèöà T8 * ñîãëàñíî (9) ìîæåò áûòü ôàêòîðèçîâàíî ïðåäñòàâëåíà êàê ïðîèç- âåäåíèå òðåõ ìàòðèö: T T T T8 8 3 8 2 8 1 � � , , , , (13) ãäå T i8, — i-e, i �1 3, , ôàêòîð-ìàòðèöû 8 8� àëãîðèòìà áûñòðîãî ïðÿìîãî ÖÊÏ èç ðàáîòû [17]: T H8 1 8, � � , T H T8 2 4 4, [ , ]� �diag , T T Q R8 3 2 2 4, [ , , ~ ]� . (14) Ïðè ýòîì H I I I I k k k k k 2 � � � � � � � , k � 2 3, , T q q q q 4 1 0 1 0 1 1 1 1 0 1 0 1 � � � � � � � � � � � � , ~ R r s r s s r s r 4 � � � � � � � � � � , T g g g g 2 � � � � � � � � �� , Q e f f e 2 � � � � � � � � �� , ãäå q � 1, r s� . Ìàòðèöà Q16 íà îñíîâàíèè (8) è ñ ó÷åòîì (13), (14) ìîæåò áûòü ôàêòîðèçîâà- íî ïðåäñòàâëåíà êàê ïðîèçâåäåíèå ïÿòè ìàòðèö: Q T T T T T16 16 5 16 4 16 3 16 2 16 1� , , , , , , (15) ãäå T i16, — i-å, i �1 5, , ôàêòîð-ìàòðèöû 16 16� ÿäðà ÖÊÏ-IV: T R16 1 16, � ; T I T kk k16 1 2 8 1 3, , , ,� � � � ; T H16 5 16 0 , � . (16) Ìàòðèöà C16 � ñîãëàñíî (9) ìîæåò áûòü ôàêòîðèçîâàíî ïðåäñòàâëåíà êàê ïðî- èçâåäåíèå ïÿòè ìàòðèö: ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2017, òîì 53, ¹ 4 147 Ò à á ë è ö à 2 Ýëåìåíòû ìàòðèöû C16 Çíà÷åíèÿ ýëåìåíòîâ ìàòðèöû 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 C C C C C C16 16 5 16 4 16 3 16 2 16 1 � � , , , , , , (17) ãäå C i16, — i-å, i �1 5, , ôàêòîð-ìàòðèöû 16 16� àëãîðèòìà áûñòðîãî ïðÿìîãî ÖÊÏ èç ðàáîòû [13]. Òàêèì îáðàçîì, ìàòðèöà C32 � íà îñíîâàíèè (3), (15), (16) è ñ ó÷åòîì àëãîðèò- ìà áûñòðîãî ïðÿìîãî ÖÊÏ ïîðÿäêà 16 ñîãëàñíî (17) ìîæåò áûòü ôàêòîðèçîâàíî ïðåäñòàâëåíà êàê ïðîèçâåäåíèå øåñòè ìàòðèö: C C C C C C C32 6 5 4 3 2 1 � � , (18) ãäå Ci — i-å, i �1 6, , ôàêòîð-ìàòðèöû 32 32� àëãîðèòìà áûñòðîãî ïðÿìîãî ÖÊÏ, ïðåäëîæåííîãî â [11, 12]: C H1 32� � ; C C R2 16 1 16� diag [ , ], ; C C I Tk k k2 16 1 2 8� �� diag [ , ], , , k �1 3, ; C C H6 16 5 16 0� diag [ , ], . (19) ÀËÃÎÐÈÒÌ ÁÛÑÒÐÎÃÎ ÎÁÐÀÒÍÎÃÎ ÖÊÏ ÏÎÐßÄÊÀ 32 Ìàòðèöó C i16 îáðàòíîãî ÖÊÏ ïîðÿäêà 16 ìîæíî ïîëó÷èòü òðàíñïîíèðîâàíèåì: C C ki32 32 � � T / . (20) Ìàòðèöà C i32 íà îñíîâàíèè (20), (18), (19) è ñ ó÷åòîì ñèììåòðè÷íîñòè ôàê- òîð-ìàòðèöû (H H 32 32 � ��T ) ìîæåò áûòü ôàêòîðèçîâàíî ïðåäñòàâëåíà ïðîèçâåäå- íèåì øåñòè ìàòðèö: C C C C C C Ci i i i i i i32 1 2 3 4 5 6 � T T T T T , (21) ãäå C ki T — k-å, k �1 6, , òðàíñïîíèðîâàííûå ôàêòîð-ìàòðèöû 32 32� àëãîðèòìà áûñòðîãî îáðàòíîãî ÖÊÏ: C Hi1 32� � , C C R i i i2 16 1 16 T T Tdiag� [ , ] , ; (22) C C I T k i i k i k( ) , , [ , ] 2 16 1 2 8� � � �T T Tdiag , k �1 3, ; C C H i i i6 16 5 16 0T T Tdiag� [ , ] , ; R R k i16 16 T T� �/ , � � �k k g/ ; ~ ~ /R R g i4 4 T T� �, T T g H i i2 2 2 T � � �/ , Q Q Q g i i2 2 2 T � � �/ , T T i4 4 T T� . Ïðè ýòîì R s r s r s r s r s r s r s r s r r s r s 16 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 8 8 7 7 T � � � � � � r s r s r s r s r s r s 6 6 5 5 4 4 3 3 2 2 1 1 � � � � � � � � � � � � � � � � � � � � � � � � � , (23) 148 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2017, òîì 53, ¹ 4 H G I I G I I I 16 0 4 0 8 4 4 0 4 4 4 T � � � � � � � � � � � , ~ R r s r s s r s r 4 T � � � � � � � � � � , T q q q q 4 1 0 1 0 1 1 1 1 0 1 0 1 T � � � � � � � � � � � � . Äëÿ îäíîíîðìîâîãî îáðàòíîãî ïðåîáðàçîâàíèÿ ìàòðèöà H 16 0T ñîäåðæèò íåíóëå- âûå ýëåìåíòû 1 è Pki mk/ 2 , k �1 3, , Pki — öåëûå. ÐÅÀËÈÇÀÖÈß ÁÛÑÒÐÎÃÎ ÖÅËÎ×ÈÑËÅÍÍÎÃÎ ÏÐÅÎÁÐÀÇÎÂÀÍÈß ÁÅÇ ÌÍÎÆÈÒÅËÅÉ Ïðè ðåàëèçàöèè áûñòðûõ öåëî÷èñëåííûõ ïðåîáðàçîâàíèé èñïîëüçóþòñÿ îïåðà- öèè òèïà «áàáî÷êà» («butterfly»), ãäå âûïîëíÿþòñÿ ïàðíûå óìíîæåíèÿ, êîòî- ðûå ìîãóò áûòü ðåàëèçîâàíû ñ âûïîëíåíèåì îïåðàöèé òîëüêî ñäâèãà è ñëîæå- íèÿ, à â íåêîòîðûõ ñëó÷àÿõ (ñ öåëüþ óìåíüøåíèÿ âû÷èñëèòåëüíîé ñëîæíîñòè) è îïåðàöèé óìíîæåíèÿ. Äëÿ ðåàëèçàöèè ïðåäëîæåííîãî 1D 32-òî÷å÷íîãî öåëî÷èñëåííîãî êîñèíóñ- íîãî ïðåîáðàçîâàíèÿ èñïîëüçóþòñÿ â îñíîâíîì îïåðàöèè ñäâèãà, ñëîæåíèÿ è íåêîòîðûå îïåðàöèè óìíîæåíèÿ. Â òàáë. 3 ïðåäñòàâëåíà ñõåìà âûïîëíåíèÿ ñïåöèàëüíûõ óìíîæåíèé, èñïîëü- çóåìûõ â îïåðàöèÿõ «áàáî÷êà», äëÿ ðåàëèçàöèè ïðåäëîæåííîãî 1D 32-òî÷å÷íîãî áûñòðîãî îáðàòíîãî öåëî÷èñëåííîãî ïðåîáðàçîâàíèÿ. ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2017, òîì 53, ¹ 4 149 Ò à á ë è ö à 3 Çíà÷åíèÿ ìíîæèòåëåé Àëãîðèòì âûïîëíåíèÿ îïåðàöèé y s xi� � ; z r xi� � Âû÷èñëèòåëüíàÿ ñëîæíîñòü îïåðàöèé ×èñëî èñïîëüçóåìûõ îïåðàöèé Ñëîæåíèå Ñäâèã Óìíî- æåíèå s1 2 32� / r1 45 32� / y x� � 4; x x x1 1� � ( )� ; z x x� �1 1 4( )� 2 3 — 2 s2 6 32� / r2 45 32� / x x x1 1� � ( );� y x� 1 3� ; z x y� �1 1( )� 2 3 — 2 s3 11 32� / r3 44 32� / x x x1 2� � ( );� z x x� � ( );1 1� y z� � 2 2 3 — 2 s4 16 32� / r4 42 32� / x x x1 2� � ( );� z x x� � ( );1 2� y x� �1 2 3 — 2 s5 20 32� / r5 41 32� / x x x1 2� � ( );� y x� 1 1� ; z x x� �1 5( )� 2 3 — 2 s6 23 32� / r6 39 32� / x x x1 3� � ( );� z x x� � ( );1 2� y z x� � ( )�1 3 3 — 2 s7 27 32� / r7 36 32� / z x x� � ( );� 3 y z z� � ( )� 2 2 2 — 2 s8 30 32� / r8 34 32� / x x1 4� � ; y x x� � 1; z x x� � 1 2 1 — 2 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 Âñåãî — 34 56 14 — Äëÿ ðåàëèçàöèè 1D 16-òî÷å÷íîãî áûñòðîãî îáðàòíîãî öåëî÷èñëåííîãî ïðå- îáðàçîâàíèÿ, ïðåäëîæåííîãî â ðàáîòå [13], òðåáóåòñÿ âûïîëíèòü 8 îïåðàöèé óìíîæåíèÿ, 106 îïåðàöèé ñëîæåíèÿ è 50 îïåðàöèé ñäâèãà. Äëÿ ðåàëèçàöèè 1D 8-òî÷å÷íîãî áûñòðîãî îáðàòíîãî öåëî÷èñëåííîãî ïðåîáðàçîâàíèÿ T i8 * ñîãëàñ- íî (13), (14) òðåáóåòñÿ âûïîëíèòü 34 îïåðàöèè ñëîæåíèÿ è 8 îïåðàöèé ñäâè- ãà [17]. Âñåãî äëÿ ðåàëèçàöèè ïðåäëîæåííîãî 1D 32-òî÷å÷íîãî áûñòðîãî îáðàò- íîãî öåëî÷èñëåííîãî ïðåîáðàçîâàíèÿ òðåáóåòñÿ âûïîëíèòü 22 îïåðàöèè óìíîæå- íèÿ, 270 îïåðàöèé ñëîæåíèÿ è 122 îïåðàöèè ñäâèãà. Âû÷èñëèòåëüíàÿ ñëîæíîñòü ïðåäëîæåííîãî, èçâåñòíûõ [9, 10] è ïðèíÿòîãî â ñòàíäàðòå Í.265 [6, 7] 2D 32-òî÷å÷íûõ öåëî÷èñëåííûõ îáðàòíûõ ïðåîáðàçîâà- íèé ïðèâåäåíà â òàáë. 4. ÝÊÑÏÅÐÈÌÅÍÒÀËÜÍÛÅ ÐÅÇÓËÜÒÀÒÛ È ÈÕ ÀÍÀËÈÇ Íà ðèñ. 1 ïðåäñòàâëåíû èñõîäíûå èçîáðàæåíèÿ êëàññîâ À è Â äëÿ òåñòèðîâà- íèÿ. Â òàáë. 5 äàíû ýêñïåðèìåíòàëüíûå ðåçóëüòàòû ýôôåêòèâíîñòè êîäèðîâàíèÿ ïî õàðàêòåðèñòèêå ñòàíäàðòíîé êîëè÷åñòâåííîé îöåíêè èñêàæåíèé PSNR (äÁ) äëÿ ñæàòûõ òåñòîâûõ èçîáðàæåíèé êëàññà À (ðèñ. 1, à, á) ñ ðàçðåøàþùåé ñïî- ñîáíîñòüþ 2560�1600 ïèêñåëåé è êëàññà Â (ðèñ. 1, â, ã) — 1920�1056 ïèêñå- ëåé ïðè íîðìàëüíîì (22–37) äèàïàçîíå QP è çíà÷åíèÿõ (37, 42) âûñîêîãî äèà- ïàçîíà QP äëÿ ïðåäëîæåííîãî 2D ïðåîáðàçîâàíèÿ ñ áëîêàìè 32�32. Ýòè ðå- çóëüòàòû ïðåäñòàâëÿþò ðàçíîñòü íà îñíîâå ïðåäëîæåíîãî ïðåîáðàçîâàíèÿ è íà îñíîâå ïðåîáðàçîâàíèÿ Í.265. Äèàïàçîíû ïàðàìåòðà QP íèçêèé (1–13), íîð- ìàëüíûé (22–37) è âûñîêèé (36-51) îïðåäåëåíû â [18]. Ðåçóëüòàòû ýôôåêòèâíîñòè êîäèðîâàíèÿ ïî êðèòåðèþ (â óðîâíÿõ ÿðêîñòè) îöåíêè ñðåäíåêâàäðàòè÷åñêîãî îòêëîíåíèÿ (ÑÊÎ) ðàçíîñòè âõîäíîãî è âîññòà- íîâëåííîãî èçîáðàæåíèé äëÿ ïðåäëîæåííîãî 2D ïðåîáðàçîâàíèÿ ñ áëîêàìè 150 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2017, òîì 53, ¹ 4 Ò à á ë è ö à 4 Îïåðàöèè è õàðàêòåðèñòèêè Îöåíêà ñëîæíîñòè 2D îáðàòíûõ ïðåîáðàçîâàíèé 32 32� Ïðåäëî- æåííîãî Èçâåñòíûõ Ñðàâíèòåëüíûé àíàëèç õàðàêòåðèñòèê ïðåîáðàçîâàíèé Í.265 èç [6, 7] èç [9] èç [10] îòíîñèòåëüíî [9] (è [10]) îòíîñèòåëüíî Í.265 Óìíîæåíèå 1408 21888 5888 5568 Â 4,18 (è â 3,95) ðàçà ìåíüøå Â 15,55 ðàç ìåíüøå Ñëîæåíèå 17280 23808 11904 14144 — — Ñëîæåíèå � ñäâèã 25088 25856 11904 14656 Íà 107,5 % (è íà 71,2 %) áîëüøå ñëîæåíèé Íà 3,1 % ìåíüøå ñëîæåíèé ×èñëî èòåðàöèé äëÿ 1D 6 5 7 8 Íà 1 (è íà 2) èòåðàöèþ ìåíüøå Íà 1 èòåðà- öèþ áîëüøå Ïàìÿòü äëÿ êâàíòîâàíèÿ — — � — — — ×èñëî áèòîâ ýëåìåíòà ìàòðèöû 9 8 11 14 Íà 2 (è íà 5) áèòà ìåíüøå Íà 1 áèò áîëüøå Îáùåå óìåíüøåíèå — Â 3,11 (è 3,24) ðàçà ìåíüøå Â 15,6 ðàçà ìåíüøå 32�32, ïðåäñòàâëÿþùèå ðàçíîñòü íà îñíîâå ïðåîáðàçîâàíèÿ Í.265 è íà îñíîâå ïðåäëîæåíîãî ïðåîáðàçîâàíèÿ ïðèâåäåíû â òàáë. 6. Ýêñïåðèìåíòàëüíûå ðåçóëüòàòû êîäèðîâàíèÿ ïî õàðàêòåðèñòèêå êîýôôèöè- åíòà ñæàòèÿ K :1 äëÿ ïðåäëîæåíîãî 2D ïðåîáðàçîâàíèÿ ñ áëîêàìè 32�32 ïðèâåäå- íû â òàáë. 7. Ðåçóëüòàòû ýôôåêòèâíîñòè êîäèðîâàíèÿ ïî õàðàêòåðèñòèêå êîýôôè- öèåíòà ñæàòèÿ K (â %), ïðåäñòàâëÿþùèå ðàçíèöó íà îñíîâå ïðåäëîæåíîãî ïðåîá- ðàçîâàíèÿ è íà îñíîâå ïðåîáðàçîâàíèÿ Í.265, ïðèâåäåíû â òàáë. 8. Â òàáëèöàõ äàíû ñðåäíèå çíà÷åíèÿ ýêñïåðèìåíòàëüíûõ ðåçóëüòàòîâ ýôôåê- òèâíîñòè êîäèðîâàíèÿ ïî õàðàêòåðèñòèêàì PSNR, ÑÊÎ è êîýôôèöèåíòó ñæàòèÿ K ïî ÷åòûðåì òåñòîâûì èçîáðàæåíèÿì êëàññîâ À è Â. Ïðåäëîæåííîå öåëî÷èñëåííîå êîñèíóñíîå ïðåîáðàçîâàíèå ïîðÿäêà 32 ïî ñðàâíåíèþ ñ ïðåîáðàçîâàíèåì â ñòàíäàðòå Í.265 ïî õàðàêòåðèñòèêå èñêàæåíèÿ PSNR äëÿ ÷åòûðåõ òåñòîâûõ èçîáðàæåíèé êëàñîâ À è Â ïîíèæàåò ñðåäíåå çíà÷å- íèå íà 0,085–0,128 äÁ, à ïî õàðàêòåðèñòèêå ÑÊÎ ïîâûøàåò ñðåäíåå çíà÷åíèå íà 0,094–0,99 óðîâíåé ÿðêîñòè. Ïðè ýòîì ñðåäíåå çíà÷åíèå êîýôôèöèåíòà ñæàòèÿ K óìåíüøàåòñÿ íà 0,018�0,44 %. Ñîãëàñíî ïðèíÿòîãî Êîìèòåòîì MPEG èñïîëüçóå- ìîãî ñóáúåêòèâíîãî ïîðîãà PSNR � 0,5 äÁ ïðè ïðèíÿòèè êîäîâîé îïòèìèçàöèè ñ÷èòàåòñÿ, ÷òî óâåëè÷åíèå èëè óìåíüøåíèå íà ýòó âåëè÷èíó áóäåò çàìåòíî âèçó- àëüíî [19], à ïðè PSNR � 0,5 äÁ — çðèòåëüíî íå îùóùàåòñÿ. Òàêèì îáðàçîì, ïî- íèæåíèå íàèáîëüøåãî ñðåäíåãî çíà÷åíèÿ PSNR íà 0,128 äÁ áóäåò çðèòåëüíî íå- çàìåòíî, ò.å. ñîõðàíÿåòñÿ âèçóàëüíîå êà÷åñòâî èçîáðàæåíèÿ. Ñëåäóåò çàìåòèòü, ÷òî âûñîêîêîððåëèðîâàííîå (ÂÊ) èçîáðàæåíèå êëàññà À (ñì. ðèñ.1, à) èìååò â 2,77–5,47 ðàçà áîëüøèé êîýôôèöèåíò ñæàòèÿ äëÿ çàäàííîãî ïàðàìåòðà êâàíòîâàíèÿ QP, ÷åì íèçêîêîððåëèðîâàííîå (ÍÊ) èçîáðàæåíèå òîãî æå êëàññà (ðèñ. 1, á; òàáë. 7). Èçîáðàæåíèå ÂÊ êëàññà Â (ðèñ. 1, â) èìååò â 2,38–4,12 ðàçà áîëüøèé êîýôôèöèåíò ñæàòèÿ äëÿ çàäàííîãî QP, ÷åì ÍÊ èçîáðà- æåíèå òîãî æå êëàññà (ðèñ. 1, ã). Ïðè ýòîì ñðåäíåå çíà÷åíèå êîýôôèöèåíòà ñæà- òèÿ ÂÊ èçîáðàæåíèé êëàññîâ À è Â ñîñòàâëÿåò â 2,57–4,79 ðàçà áîëüøå, ÷åì äëÿ ñëó÷àÿ ÍÊ èçîáðàæåíèé ýòèõ êëàññîâ. ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2017, òîì 53, ¹ 4 151 Ðèñ. 1. Èñõîäíûå èçîáðàæåíèÿ êëàññà À: ôîòî 1, ðàçìåð 2560�1600 (à); õðàì, ðàçìåð 2560�1600 (á); è êëàññà Â: ôîòî 2, ðàçìåð 1920 �1056 (â); ïåéçàæ, ðàçìåð 1920 �1056 (ã) à á â ã ÇÀÊËÞ×ÅÍÈÅ Ïðåäëîæåí ìåòîä ïîñòðîåíèÿ îäíîíîðìîâîãî öåëî÷èñëåííîãî êîñèíóñíîãî ïðåîáðàçîâàíèÿ âûñîêîãî ïîðÿäêà. Ïîñòðîåíî îäíîíîðìîâîå öåëî÷èñëåííîå ïðåîáðàçîâàíèå ïîðÿäêà 32 è ðàçðàáîòàíû åãî áûñòðûå àëãîðèòìû íèçêîé âû- ÷èñëèòåëüíîé ñëîæíîñòè, â 3,24 ðàçà ìåíüøåé, ÷åì â èçâåñòíûõ àëãîðèòìàõ, è â 15,6 ðàçà ìåíüøåé, ÷åì â ñòàíäàðòå Í.265. Ýòî ïðåîáðàçîâàíèå íå òîëüêî 152 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2017, òîì 53, ¹ 4 Ò à á ë è ö à 6 Êëàññ Èçîáðàæåíèå ñ áëîêàìè 32 32� Ðåçóëüòàòû ýôôåêòèâíîñòè êîäèðîâàíèÿ ïî õàðàêòåðèñòèêå ÑÊÎ (â óðîâíÿõ ÿðêîñòè) äëÿ QP 22 27 32 37 42 À 2560 1600� Ôîòî 1 � 0,065 � 0,075 � 0,196 � 0,234 � 0,221 Õðàì � 0,164 � 0,281 � 0,543 � 1,120 � 2,057 B 1920 1056� Ôîòî 2 � 0,052 � 0,096 � 0,182 � 0,260 � 0,249 Ïåéçàæ � 0,094 � 0,145 � 0,344 � 0,819 � 1,433 Ñðåäíåå çíà÷åíèå � 0,094 � 0,149 � 0,316 � 0,608 � 0,990 Ò à á ë è ö à 7 Êëàññ Èçîáðàæåíèå ñ áëîêàìè 32 32� Ðåçóëüòàòû êîäèðîâàíèÿ ïî êîýôôèöèåíòó ñæàòèÿ K :1 äëÿ QP 22 27 32 37 42 À 2560 1600� Ôîòî 1 11,88 23,76 45,37 91,16 176,99 Õðàì 4,28 6,31 9,69 17,01 32,36 Â 1920 1056� Ôîòî 2 6,16 14,82 35,59 81,57 176,99 Ïåéçàæ 2,59 4,73 9,11 19,35 43,23 Ñðåäíåå çíà÷åíèå 6,228 12,405 24,940 52,273 107,393 Ò à á ë è ö à 8 Êëàññ Èçîáðàæåíèå ñ áëîêàìè 32 32� Ðåçóëüòàòû ýôôåêòèâíîñòè êîäèðîâàíèÿ ïî õàðàêòåðèñòèêå êîýôôèöèåíòà ñæàòèÿ K (%) äëÿ QP 22 27 32 37 42 À 2560 1600� Ôîòî 1 � 0,328 � 0,152 � 0,041 � 0,001 � 0,003 Õðàì � 0,739 � 0,554 � 0,338 � 0,159 � 0,050 Â 1920 1056� Ôîòî 2 � 0,257 � 0,147 � 0,046 0,0 � 0,001 Ïåéçàæ � 0,436 � 0,363 � 0,245 � 0,100 � 0,025 Ñðåäíåå çíà÷åíèå � 0,440 � 0,304 � 0,168 � 0,065 � 0,018 Ò à á ë è ö à 5 Êëàññ Èçîáðàæåíèå ñ áëîêàìè 32 32� Ðåçóëüòàòû ýôôåêòèâíîñòè êîäèðîâàíèÿ ïî õàðàêòåðèñòèêå PSNR (äÁ) äëÿ QP 22 27 32 37 42 À 2560 1600� Ôîòî 1 � 0,14 � 0,15 � 0,15 � 0,11 � 0,06 Õðàì � 0,22 � 0,18 � 0,16 � 0,16 � 0,14 B 1920 1056� Ôîòî 2 � 0,07 � 0,06 � 0,08 � 0,08 � 0,05 Ïåéçàæ � 0,08 � 0,05 � 0,07 � 0,09 � 0,09 Ñðåäíåå çíà÷åíèå � 0,128 � 0,110 � 0,115 � 0,110 � 0,085 íàèáîëåå áëèçêîå ê ÄÊÏ, íî òàêæå èìååò ïðåâîñõîäíûå õàðàêòåðèñòèêè êîäè- ðîâàíèÿ: ñðåäíåå çíà÷åíèå ïîíèæåíèÿ ïî õàðàêòåðèñòèêå èñêàæåíèé PSNR ñî- ñòàâëÿåò 0,085–0,128 äÁ, à ñðåäíåå çíà÷åíèå ïîâûøåíèÿ ïî õàðàêòåðèñòèêå ÑÊÎ ñîñòàâëÿåò 0,094–0,99 óðîâíåé ÿðêîñòè. Ïðè ýòîì ñðåäíåå çíà÷åíèå êîýô- ôèöèåíòà ñæàòèÿ óìåíüøàåòñÿ íà 0,018–0,44%. Äàííîå ïðåîáðàçîâàíèå îáåñïå- ÷èâàåò òàêîå æå âèçóàëüíîå êà÷åñòâî, à òàêæå è êà÷åñòâî ïî õàðàêòåðèñòèêàì PSNR, ÑÊÎ è êîýôôèöèåíòó ñæàòèÿ, êàê â ñòàíäàðòå Í.265. Â íàñòîÿùåé ñòàòüå ïðåäëîæåí ïîäõîä ðàçäåëåíèÿ èçîáðàæåíèé ïî õàðàêòå- ðèñòèêå êîýôôèöèåíòà ñæàòèÿ íà ÂÊ è ÍÊ èçîáðàæåíèÿ. Ïîýòîìó ïðè òåñòèðî- âàíèè êëàññû À è Â èçîáðàæåíèé ïðåäñòàâëÿþò ÂÊ è ÍÊ èçîáðàæåíèÿ. Àíàëèç ðåçóëüòàòîâ (ñì. òàáë. 7) ïîêàçàë, ÷òî ÂÊ èçîáðàæåíèÿ êëàññîâ À è Â (ñì. ðèñ. 1, à, â) èìåþò â ñðåäíåì â 2,57–4,79 ðàçà áîëüøèé êîýôôèöèåíò ñæàòèÿ äëÿ çàäàííîãî ïàðàìåòðà êâàíòîâàíèÿ QP, ÷åì ÍÊ èçîáðàæåíèÿ (ñì. ðèñ. 1, á, ã). Òàêèì îáðà- çîì, ðàçðàáîòàííîå öåëî÷èñëåííîå ïðåîáðàçîâàíèå ïîðÿäêà 32 ìîæåò áûòü èñ- ïîëüçîâàíî äëÿ óëó÷øåíèÿ ñòàíäàðòà Í.265 â öåëÿõ óâåëè÷åíèÿ áûñòðîäåéñòâèÿ è óìåíüøåíèå âû÷èñëèòåëüíûõ è ýíåðãåòè÷åñêèõ çàòðàò. ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ 1. Ãîíñàëåñ Ð., Âóäñ Ð. Öèôðîâàÿ îáðàáîòêà èçîáðàæåíèé. Ìîñêâà: Òåõíîñôåðà, 2005. 1072 ñ. 2. Ðè÷àðäñîí ß. Âèäåîêîäèðîâàíèå. Í.264 è MPEG-4 — ñòàíäàðòû íîâîãî ïîêîëåíèÿ. Ìîñêâà: Òåõíîñôåðà, 2005. 368 ñ. 3. ITU-T Rec. H.264 \| ISO/IEC 14496-10: 2009. Information technology — Coding of audio-visual objects. Part 10: Advanced Video Coding, 2009. 4. SMPTE standard 421 M-2006: VC-1 compressed video bitstream format and decoding process, 2006. 5. 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. 6. 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. 7. Fuldseth A., Bj �întegaard G., Budagavi M., Sze V. CE10: Core transform design for HEVC. Doc. JCTVC-G495. Geneva. CH, Nov. 2011. 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. 11. Ãíàò³â Ë.Î. Ìåòîä ïîáóäîâè øâèäêèõ ö³ëî÷èñåëüíèõ êîñèíóñíèõ ïåðåòâîðåíü âåëèêî¿ ðîçì³ðíîñò³ äëÿ âèñîêîåôåêòèâíîãî êîäóâàííÿ çîáðàæåíü ³ â³äåî. Ïð. Ì³æíàð. êîíô. «Ïèòàí- íÿ îïòèì³çàö³¿ îá÷èñëåíü (ÏÎÎ-2013)». Óêðà¿íà, Êðèì. ñìò. Êàöèâåë³, 30 âåðåñíÿ 2013. Ñ. 66–67. 12. Ãíàò³â Ë.Î., Ëóö Â.Ê. Ö³ëî÷èñåëüíå êîñèíóñíå ïåðåòâîðåííÿ ïîðÿäêó 32 íèçüêî¿ ñêëàäíîñò³ äëÿ âèñîêîåôåêòèâíîãî êîäóâàííÿ çîáðàæåíü ³ â³äåî. Ïð. Ì³æíàð. êîíô. «Ïèòàííÿ îïòèì³çàö³¿ îá÷èñëåíü (ÏÎÎ-2013)». Óêðà¿íà, Êðèì. ñìò. Êàöèâåë³, 30 âåðåñíÿ 2013. Ñ. 68–69. 13. Ãíàòèâ Ë.À. Öåëî÷èñëåííûå êîñèíóñíûå ïðåîáðàçîâàíèÿ äëÿ âûñîêîýôôåêòèâíîãî êîäèðîâà- íèÿ èçîáðàæåíèé è âèäåî. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. 2016. Ò. 52, ¹ 5. Ñ. 161–176. 14. Ãíàòèâ Ë.À. Ìåòîä ïîñòðîåíèÿ ïðîñòîãî öåëî÷èñëåííîãî êîñèíóñíîãî ïðåîáðàçîâàíèÿ áîëü- øîé ðàçìåðíîñòè äëÿ êîäèðîâàíèÿ èçîáðàæåíèé è âèäåî ñ âûñîêèì ðàçðåøåíèåì. Êèáåðíåòè- êà è ñèñòåìíûé àíàëèç. 2016. Ò. 52, ¹ 6. Ñ. 143–155. ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2017, òîì 53, ¹ 4 153 15. Ugur K., Andersson K., Fuldseth A. at el. High perfomance low complexity video coding and the emerging HEVC standard. IEEE Trans. Circuits Syst. Video Technol. 2012. Vol. 20, N 12. P. 1688–1697. 16. Øåâ÷óê Á.Ì., Çàä³ðàêà Â.Ê., Ãíàò³â Ë.Î., Ôðàºð Ñ.Â. Òåõíîëîã³ÿ áàãàòîôóíêö³îíàëüíî¿ îáðîá- êè ³ ïåðåäà÷³ ³íôîðìàö³¿ â ìîí³òîðèíãîâèõ ìåðåæàõ. Êè¿â: Íàóê. äóìêà. 2010. 378 ñ. 17. Ãíàòèâ Ë.À., Öåëî÷èñëåííûå êîñèíóñíûå ïðåîáðàçîâàíèÿ: ìåòîäû ïîñòðîåíèÿ íîâûõ áûñòðûõ ïðåîáðàçîâàíèé ïîðÿäêà 8,16 è èõ ïðèìåíåíèå. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. 2014. Ò. 50, ¹ 6. Ñ. 104–121. 18. 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. 19. Ñýëîìîí Ä. Ñæàòèå äàííûõ, èçîáðàæåíèé è çâóêà. Ìîñêâà: Òåõíîñôåðà, 2004. 368 ñ. Íàä³éøëà äî ðåäàêö³¿ 08.12.2016 Ë.Î. Ãíàò³â Ö²ËÎ×ÈÑÅËÜÍÅ ÊÎÑÈÍÓÑÍÅ ÏÅÐÅÒÂÎÐÅÍÍß ÂÈÑÎÊÎÃÎ ÏÎÐßÄÊÓ: ÌÅÒÎÄ ÏÎÁÓÄÎÂÈ ² ØÂÈÄÊ² ÀËÃÎÐÈÒÌÈ ÄËß ÊÎÄÓÂÀÍÍß ÇÎÁÐÀÆÅÍÍß ² Â²ÄÅÎ ÂÈÑÎÊÎ¯ ÐÎÇÄ²ËÜÍÎ¯ ÇÄÀÒÍÎÑÒ² Àíîòàö³ÿ. Çàïðîïîíîâàíî ìàòðè÷íèé ìåòîä ïîáóäîâè îäíîíîðìîâîãî ö³ëî- ÷èñåëüíîãî êîñèíóñíîãî ïåðåòâîðåííÿ âèñîêîãî ïîðÿäêó. Ïîáóäîâàíî îäíî- íîðìîâå ö³ëî÷èñåëüíå ïåðåòâîðåííÿ ïîðÿäêó 32 ³ ðîçðîáëåíî éîãî øâèäê³ àëãîðèòìè íèçüêî¿ îá÷èñëþâàëüíî¿ ñêëàäíîñò³ (ÿêà ìåíøà â 3,24 ðàçè, í³æ ó â³äîìèõ àëãîðèòìàõ, òà â 15,6 ðàç³â, í³æ ó ñòàíäàðò³ Í.265), ³ âîíè ïîòðå- áóþòü ò³ëüêè ö³ëî÷èñåëüíèõ îïåðàö³é. Öå ïåðåòâîðåííÿ íå ò³ëüêè íàéáëèæ÷å äî äèñêðåòíîãî êîñèíóñíîãî ïåðåòâîðåííÿ, àëå òàêîæ ìàº â³äì³íí³ õàðàêòåðèñòèêè êîäóâàííÿ. Êëþ÷îâ³ ñëîâà: äèñêðåòíå êîñèíóñíå ïåðåòâîðåííÿ, ö³ëî÷èñåëüíå êîñèíóñ- íå ïåðåòâîðåííÿ, ìàñøòàáîâàíå ïåðåòâîðåííÿ, ôàêòîðèçàö³ÿ, øâèäêå ïåðå- òâîðåííÿ, åôåêòèâí³ñòü êîäóâàííÿ, îá÷èñëþâàëüíà ñêëàäí³ñòü, êîåô³ö³ºíò ñòèñíåííÿ, â³äåîêîäóâàííÿ, Í.264, H.265, AVS. L.O. Hnativ HIGH-ORDER INTEGER COSINE TRANSFORM: CONSTRUCTION METHOD AND FAST ALGORITHMS FOR HIGH-RESOLUTION IMAGE AND VIDEO CODING Abstract. Matrix method of constructing one-norm high integer cosine transform is proposed. The one-norm order-32 integer transform is constructed and its fast algorithms of low computational complexity are developed, whose computational complexity is 3.24 times less than that in the well-known algorithms and is 15.6 times less than one in standard H.265 and requires integer operations only. This transform is not only very close to the discrete cosine transform, but also has excellent coding performance. Keywords: discrete cosine transform, integer cosine transform, scaled transform, factorization, fast transform, coding gain, computational complexity, compression ratio, video coding, Í.264, H.265,AVS. Ãíàòèâ Ëåâ Àëåêñååâè÷, êàíäèäàò òåõí. íàóê, ñòàðøèé íàó÷íûé ñîòðóäíèê Èíñòèòóòà êèáåðíåòèêè èì. Â.Ì. Ãëóøêîâà ÍÀÍ Óêðàèíû, Êèåâ, e-mail: levhnativ@gmail.com. 154 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2017, òîì 53, ¹ 4

Целочисленное косинусное преобразование высокого порядка: метод построения и быстрые алгоритмы для кодирования изображений и видео с высоким разрешением

Institution

Ähnliche Einträge