[Из песочницы] Кто жмёт лучше, или Уолш против Фурье
Несмотря на развитие науки и техники, сжатие информации по прежнему остаётся одной из актуальных задач, где особое место занимают алгоритмы сжатия видеоинформации. В этой публикации речь пойдёт о сжатии статических цветных изображений JPEG-подобными алгоритмами.
Для начала хочу поблагодарить автора статей «Декодирование JPEG для чайников» и «Изобретаем JPEG», которые очень помогли мне в работе по написанию данной публикации. Когда я занялся вопросами изучения алгоритмов сжатия изображений с потерями, то в части алгоритма JPEG меня всё время мучил вопрос: «Почему роль базисного преобразования в алгоритме JPEG отведена именно частному случаю преобразования Фурье?». Здесь автор даёт ответ на этот вопрос, но я решил подойти к нему не с точки зрения теории, математических моделей или программной реализации, а с точки зрения схемотехники.
Алгоритм сжатия изображений JPEG является алгоритмом цифровой обработки сигналов, которые, аппаратно, как правило, реализуются либо на цифровых сигнальных процессорах, либо на программируемых логических интегральных схемах. В моём случае, выбор для работы цифрового сигнального процессора означал бы приход к тому, от чего я пытался уйти — к программной реализации, поэтому решено было остановиться на программируемой логике.
В одном из интернет-магазинов я приобрёл довольно простую отладочную плату, которая содержит в своём составе ПЛИС Altera FPGA Cyclone 4 -EP4CE6E22 и память SRAM 512Kx8. Так как ПЛИС была фирмы Altera, то и для разработки решено было использовать среду Quartus II Web Edition. Разработка отдельных функциональных блоков аппаратного кодека осуществлялась на языке Verilog, а сборка в единую схему производилась в графическом редакторе среды Quartus II Web Edition.
Для связи с персональным компьютером (приём команд, приём/передача обрабатываемых данных), на языке Verilog мной был написан простенький асинхронный приёмопередатчик UART. Для подключения к COM-порту (RS-232) компьютера, на базе микросхемы MAX3232WE и из того, что было под рукой, наспех, был спаян преобразователь уровней. В итоге вот, что получилось: 
Для отправки команд с персонального компьютера, а также приёма-передачи данных использовалась триальная версия программы ADVANCED SERIAL PORT MONITOR, которая позволяет формировать не только отдельные посылки байт данных, но и формировать потоки данных из содержимого файлов, а также записывать принимаемые потоки данных в файл, что позволило передавать и принимать файлы. Никакие протоколы и контрольные суммы, для для приёма/передачи данных по UART я тут не использую и не контролирую (попросту лень было всё это предусматривать и реализовывать), во время связи для приёма/передачи я использовал, что называется, «сырые данные».
Все арифметические операции связанные с дробными числами в кодеке осуществляются в формате с фиксированной точкой, операции сложения и вычитания осуществляются в дополнительном коде, в принципе это и так понятно. Как определялась разрядность обрабатываемых данных будет описано ниже.
Операция сжатия осуществляется над исходными изображениями, представленными в формате .bmp с глубиной цвета — 24 бита на пиксель (по 8 бит на каждую из цветовых компонент).
Имеющаяся на отладочной плате память была организована следующим образом: адреса с 00000h по 3FFFFh (в шестнадцатиричной системе счисления) выделены под хранение исходных данных (рисунок в формате .bmp для сжатия, либо закодированные данные для распаковки), итого 256 КБ, остальные 256 КБ — пространство для записи получаемых, в результате сжатия или распаковки данных, это адреса с 40000h по 7FFFFh. Я думаю, очевидно, что максимальный размер сжимаемых изображений ограничен объёмом, выделяемой для хранения данных, памяти.
Алгоритм работы устройства такой: сразу после подачи питания кодек ожидает поток данных по UART, любые принятые, при этом, данные здесь интерпретируются как исходный файл для обработки, если пауза между байтами составляет 10 мс, то это интерпретируется как конец файла, и следующий за паузой байт, принимаемый по UART, воспринимаются устройством как команда. Команды представляют собой конкретные значения байт. Например, после приёма файла через 10 мс, поступившее в кодек по UART, значение байта AAh интерпретируется устройством как команда, по которой происходит выдача по UART на компьютер данных с микросхемы памяти, начиная с адреса 40000h и до значения адреса на котором завершилась запись обработанных данных, т.е. на компьютер передаются результаты сжатия/распаковки. Значение EEh интерпретируется как команда на сжатие/распаковку изображения, также для отладки мной был предусмотрен ряд других команд.
Что касается структуры файла с жатым изображением, то тут я решил не заморачиваться, и, в отличии от алгоритма JPEG, реализуемый мной алгоритм, носит довольно-таки узконаправленный характер и не рассчитан на все случаи жизни, поэтому получаемые, в результате сжатия, данные единым потоком записываются в выделенную область памяти. Единственное, что тут нужно отметить, для того чтобы не реализовывать генератор заголовка .bmp файла (тоже было лень), при сжатии он просто целиком переписывается в начальную (с адреса 40000h) область памяти, отведённую для конечных данных, а затем уже, начиная со смещения, с которого в исходном .bmp файле хранятся пиксельные данные, записываются сжатые данные. Это смещение храниться в заголовке .bmp файла по адресу 0Ah относительно его начала, и, как правило составляет 36h. При распаковке, соответственно осуществляется такая же операция.
Итак, сжатие изображений JPEG-подобными алгоритмами осуществляется в следующей последовательности:
- преобразование цветового пространства из RGB в YCbCr или YUV;
- цветовая субдискретизация;
- базисное преобразование;
- квантование коэффициентов получаемых после базисного преобразования;
- зигзаг-сканирование;
- кодирование длин серий;
- сжатие по алгоритму Хаффмана.
Распаковка идёт в обратном порядке.
Из всех, вышеперечисленных этапов, в кодеке я не реализовывал субдискретизацию, так как посчитал её лишней (может быть я не прав).
Исходя из представленной выше последовательности действий, мной была разработана следующая функциональная схема кодека:
Процесс работы кодека контролирует устройство управления, которое представляет собой конечный автомат, здесь же осуществляется кодирование/декодирование длин серий, а также формирование конечных данных из кодов Хаффмана при сжатии и формирование самих кодов Хаффмана из поступающих с памяти SRAM данных при распаковке. Также устройство управления генерирует управляющие сигналы для других операционных блоков.
Под основной схемой, представлены схемы операционных блоков, меняя которые в основной схеме, я менял режимы работы устройства. Была попытка собрать всё в единое устройство и задавать режимы работы кодека, а также способы базисного преобразования при помощи команд по UART, но не хватило логической ёмкости ПЛИС. Поэтому режимы работы устройства меняются сменой соответствующих операционных блоков и задачей определённых параметров в устройстве управления (в т.ч. и размеры сжимаемого/распаковываемого изображения), после чего изменённый проект компилируется и прошивается в ПЛИС.
Преобразование цветового пространства
В интернете можно найти много различной информации, посвящённой преобразованию цветовых пространств, поэтому сразу начну с описания аппаратной реализации.
Блок преобразования цветовых пространств представляет собой комбинационную логику, благодаря чему преобразование цветовых компонент осуществляется за один такт генератора. Преобразование цветового пространства RGB в YCbCr осуществляется по следующим формулам:
Вычисление начинается с того, что устройство управления выставляет в адресный порт микросхемы памяти SRAM начальный адрес, с которого в .bmp файле хранятся пиксельные данные, как было сказано выше, значение начального адреса — 36h. В файлах .bmp по этому адресу хранится значение синей цветовой компоненты самого нижнего правого пикселя изображения. По адресу 37h — значение зелёной цветовой компоненты, далее красной, потом снова идёт синяя компонента следующего пикселя в самой нижней строке изображения и т. д. Как видно из функциональной схемы, под каждую цветовую компоненту в схеме предусмотрен свой регистр. После загрузки с памяти всех трёх цветовых компонент в свои регистры, со следующего такта генератора осуществляется запись в память результатов вычислений. Так, по адресу синей компоненты «B» записывается монохроматическая красная компонента «Cr», по адресу зелёной компоненты «G» записывается монохроматическая синяя компонента «Cb», и по адресу компоненты «R» записывается компонента яркости «Y». В результате выполнения данного этапа на месте исходного изображения в памяти SRAM, представленного в формате RGB, появится то же изображение в формате YCbCr.
Для аппаратной реализации вычислений яркостной и монохроматических компонент, все дробные коэффициенты из формул были представлены в виде шестнадцатиразрядных слов в формате с фиксированной точкой, где в старших восьми битах содержится целая часть, соответственно в младших восьми — дробная. Например, коэффициент 0.257 в двоичном представлении с фиксированной точкой выглядит так: 0000000001000001 или в шестнадцатиричной форме 0041h. Ограниченность количества разрядов уменьшает точность, так, если дробное двоичное число 0000000001000001 перевести в десятичную форму, то получим: 2^(-2) + 2^(-8) = 0.25 + 0.00390625 = 0.25390625. Как видно, результат отличается от значения 0.257 и для повышения точности представления нужно увеличивать количество разрядов, отводимых под дробную часть. Но я решил ограничиться, как было сказано выше, восемью разрядами.
Итак, на первом этапе преобразования, восьмиразрядные значения цветовых компонент RGB преобразуются в шестнадцатиразрядные в формате с фиксированной точкой путём добавления восьми младших разрядов, заполненных нулевыми битами:
На втором этапе осуществляются операции умножения, сложения и/или вычитания. В результате которых получаются тридцатидвухразрядные данные, где в шестнадцати старших разрядах содержится целая часть, в шестнадцати младших — дробная.
На третьем этапе из полученных тридцатидвухразрядных слов формируются восьмиразрядные данные путём выделения восьми разрядов, стоящих непосредственно перед запятой (если порядковый номер самого младшего бита — 0, а самого старшего — 31, то это биты с 23 по 16):
На четвёртом этапе, к полученным восьмиразрядным словам, в соответствии с вышепредставленными формулами, прибавляются смещения (для компоненты Y — 16, для компонент Cb, Cr — 128).
Преобразование из YCbCr в RGB осуществляется по таким формулам:
Здесь есть такая особенность, что результаты вычислений, в некоторых случаях, могут приобретать значения большие 255, что выходит за пределы одного байта, либо отрицательные значения, соответственно такие ситуации нужно отслеживать.
Так, если возникает переполнение, то значение итоговой цветовой компоненты должно быть равным 255, для этого просто проводим побитовую логическую операцию «ИЛИ» результата с битом переполнения. А если знаковый разряд результата равен единице (т.е. значение меньше нуля), то значение итоговой цветовой компоненты должно быть равным 0, для этого проводим побитовую логическую операцию «И» результата с инвертированным значением знакового бита.
Итак, на первом этапе операции преобразования цветового пространства YCbCr в RGB, считанные с микросхемы памяти SRAM, восьмиразрядные значения яркостной и монохроматических компонент переводим в дополнительный десятиразрядный код, путём добавления двух старших нулевых бит (знаковый бит и признак переполнения). В итоге получаем десятиразрядные слова. Далее в соответствии с формулами отнимаем от данных значений смещения (или прибавляем отрицательные значения смещений, представленные в десятиразрядном дополнительном коде). Затем, полученный результат переводим из дополнительного кода в прямой, сохраняя значения самого старшего (знакового) бита. Оставшиеся девятиразрядные слова преобразуем в восемнадцатиразрядные с фиксированной точкой путём, приписывания младших девяти разрядов с нулевыми битами:
Дробные коэффициенты, фигурирующие в формулах, также представляем в виде восемнадцатиразрядного кода с фиксированной точкой, где под целую и дробную части отводятся по 9 бит. В результате операций умножения получаем тридцатишестиразрядные значения произведений, в которых 18 старших разрядов — целая часть, 18 младших — дробная. Затем вычисляем знак произведения путём проведения логической операции «сложение по модулю 2», ранее сохранённого знакового разряда со знаком, стоящим перед коэффициентом в формуле (если »-», то »1», если »+», то »0»).
Также нужно определить, не является ли результат произведения нулевым, если результат умножения равен нулю, то и в знаковом разряде должен быть записан 0 вне зависимости от знаков, стоящих перед коэффициентами и знаков, стоящих перед результатами, полученных в результате смещения считанных с памяти компонент. Для этого, к произведению применяем оператор редукции (|product[35:0]), который определяет, все ли биты в результате умножения равны нулю (если да, то результат работы данного оператора будет нулевым), после чего проводим операцию логического «И» полученного результата с результатом операции «сложение по модулю 2» знаковых разрядов.
После всего этого переводим результаты умножения в дополнительный тридцатисемиразрядный код, где в самом старшем разряде хранится знак, и проводим операции сложения. После операций сложения, полученные, в дополнительном коде, результаты переводим в прямой код, и выделяем восемь бит, стоящих непосредственно перед запятой (если номер самого младшего бита 0, а самого старшего — 36, то это биты с 25 по 18). Далее проверяем, не было ли переполнения, для этого, как было сказано выше, проводим операцию побитового логического «ИЛИ» выделенных восьми бит с признаком переполнения, который хранится в 26-ом разряде. И ещё, проверяем не получился ли отрицательный результат, для чего проводим побитовую операцию логического «И» инвертированного знакового разряда с этими же восемью битами:
Полученные, в результате вычисления по трём формулам, и преобразованные восьмиразрядные значения и есть значения цветовых компонент RGB.
Тестировать работу устройства я решил при помощи фотографии Лены Содерберг размером 256 на 256 пикселей:
С этой фотографией работают все, кто занимается обработкой изображений, и я решил не быть исключением.
Итак, в результате преобразования исходной фотографии, загруженной по UART в память SRAM отладочной платы, из цветового пространства RGB в пространство YCbCr, было получено следующее изображение:
Ниже на рисунке справа представлена исходная фотография, слева фотография — результат обратного преобразования из пространства YCbCr в цветовое пространство RGB так, как это описывалось выше:
При сравнении исходной и преобразованной фотографии можно увидеть, что исходная фотография ярче обработанной, это объясняется потерей данных, которые возникали при округлении («отбросе» дробной части), а также потерей точности, при представлении дробных коэффициентов в двоичной форме.
Базовые преобразования и квантование коэффициентов
Дискретное косинусное преобразование
Информации о том, что такое дискретное косинусное преобразование (далее по тексту ДКП), на просторах интернета присутствует в предостаточном количестве, поэтому на теории остановлюсь кратко.
Как было сказано в этой публикации, суть любого базового преобразования сводится к умножению матрицы преобразования на матрицу исходных данных, после чего полученный результат снова умножается уже на транспонированную матрицу того же преобразования. В случае с дискретным косинусным преобразованием, коэффициенты матрицы преобразования вычисляются по следующему правилу:
Где:
N — размерность матрицы;
i, j — индексы элементов матрицы.
В нашем случае N = 8, т.е. исходное изображение разбивается на блоки 8 на 8 пикселей, при этом значения индексов i и j изменяются в диапазоне от 0 до 7.
В результате применения этого правила при N = 8 получаем такую матрицу преобразования:
Для того, чтобы не проводить вычисления с дробными числами помножим каждый элемент матрицы на 8√8, и округлим полученные значения элементов матрицы до целых чисел, в результате чего получим матрицу Т:
При этом, необходимо будет результат умножения матриц, как в случае прямого дискретного косинусного преобразования при кодировании, так и в случае обратного при декодировании, разделить на 512. Учитывая, что 512 = 2^(9), то деление осуществляется методом сдвига делимого вправо на 9 позиций.
В результате прямого дискретного косинусного преобразования получается матрица, так называемых, коэффициентов ДКП, в которой элемент, расположенный в нулевой строке и нулевом столбце, называется низкочастотным коэффициентом и его значение всегда положительное. Остальные элементы матрицы ДКП — высокочастотные коэффициенты, значения которых могут быть как положительными, так и отрицательными. Учитывая это, и то, что элементы результирующей матрицы должны быть восьмиразрядными, для низкочастотного коэффициента диапазон значений составит [0…255], а для высокочастотных — [-127…127]. Для того, чтобы уложиться в эти диапазоны необходимо результаты прямого дискретного косинусного преобразования разделить на 8, соответственно результаты обратного — помножить на 8. В результате для прямого ДКП получаем такую формулу:
Где:
С — матрица коэффициентов дискретного косинусного преобразования;
Т — матрица преобразования;
Х — матрица 8 на 8 яркостной или монохроматических компонент (в зависимости от того какая, назовём так, компонентная плоскость Y, Cb или Cr кодируется).
Для обратного ДКП получаем следующую формулу:
Коэффициенты матрицы T в восьмиразрядном формате хранятся в памяти ROM, расположенной на кристалле ПЛИС в прямом коде, при этом старший бит содержит знак.
И так, на первом этапе дискретного косинусного преобразования, с памяти SRAM в операционный блок, осуществляющий прямое ДКП, последовательно считываются 64 байта одной из компонент (сначала кодируется вся компонентная плоскость Y, затем Cb и Cr), образующие часть изображения, как было написано ранее, размером 8 на 8 пикселей (при этом адреса для памяти SRAM генерируются особым образом):
Операции вычисления в данном блоке осуществляются с двадцатиодноразрядными данными: 12 младших разрядов — значения, которые будут потерянны при делении на 4096 (2^(12)), 8 разрядов — значащая часть и старший разряд — знак, итого: 12+8+1 = 21:
Исходя из этого, во время загрузки, восьмиразрядные данные в операционном блоке преобразуются в двадцатиодноразрядные слова, представленные в дополнительном коде, путём приписывания старших тринадцати разрядов, заполненных нулевыми битами (старший бит — знак), после чего полученное слово запоминается в буферную память RAM, расположенную, также, на кристалле ПЛИС, в адресное пространство c 00h по 3Fh (среда Quartus II не позволила создать память RAM с организацией 128×21, поэтому пришлось использовать память с организацией 128×32).
На втором этапе, после того как в буферную память RAM записано 64 двадцатиодноразрядных слова (блок 8 на 8), запускается процесс умножения матриц. При этом, с памяти ROM считывается восьмиразрядный строковый элемент матрицы преобразования, который «разворачивается» в двадцатиодноразрядное слово, путём записывания седьмого (знакового) бита значения, считанного с памяти ROM, в двадцатый (знаковый) бит распакованного слова. Остальные семь бит, считанного восьмиразрядного значения элемента матрицы преобразования, переписываются в семь младших бит распакованного слова, биты с порядковыми номерами 7 — 19 заполняются нулями:
Далее, с буферной памяти RAM считывается, ранее записанный туда, двадцатиодноразрядный столбцовый элемент, после чего, его двадцать младших разрядов перемножаются с двадцатью разрядами развёрнутого элемента матрицы преобразования. Знак произведения вычисляется также, как и при преобразовании цветовых пространств:
Произведение переводится в дополнительный код и запоминается в стек, глубиной 8 двадцатиодноразрядных слов. Как только стек заполнен (это означает, что элементы строки матрицы преобразования перемножены на элементы очередного столбца исходной матрицы), все значения стека суммируются и результат в дополнительном коде, записывается в буферную память RAM, в адресное пространство с 40h по 7Fh.На третьем этапе, с буферной памяти RAM, с адресного пространства 40h — 7Fh, построчно считываются элементы матрицы, которая является результатом произведения матриц преобразования и исходной матрицы, и преобразуются в прямой код. А с памяти ROM, также как и ранее, считываются, также построчно, и разворачиваются элементы матрицы преобразования (вопреки правилу умножения матриц, здесь мы перемножаем строку на строку, что означает операцию транспонирования матрицы множителя). Затем, также как и раньше, в прямом коде перемножаются двадцатиразрядные элементы матриц, вычисляется знаковый разряд, произведение переводится в дополнительный код и запоминается в стек. Как только стек заполняется восемью элементами, осуществляется их суммирование, и результат из дополнительного кода переводится в прямой.
Далее осуществляется операция квантования. Каждый элемент полученной матрицы делится на, так называемый, соответствующий коэффициент квантования, таблица которых хранится в отдельной памяти ROM на кристалле ПЛИС. Значения коэффициентов квантования рассчитывались по следующей формуле:
Где:
R — коэффициент сжатия, или коэффициент характеризующей потери качества восстановленным изображением по отношению к исходному;
i, j — индексы вычисляемого элемента матрицы квантования, изменяются в пределах от 0 до 7.
Тут же нужно сказать, что для всех компонентных плоскостей Y, Cb, Cr в кодеке используется одна матрица квантования, вычисленная для R = 2 (не стал я заморачиваться, делая для каждой плоскости свою таблицу коэффициентов квантования).
Для того, чтобы аппаратно не реализовывать делитель, операцию деления при квантовании я заменил операцией умножения следующим образом:
Где:
a — квантуемый коэффициент, элемент результативной матрицы базового преобразования;
b — соответствующий коэффициент матрицы квантования, вычисленный по ранее приведённой формуле;
c — результат квантования.
Соответственно, в память ROM записаны результаты возведения в степень -1 (или 1/b), представленные в формате с фиксированной точкой, при этом в памяти хранятся только 8 разрядов дробной части, так как целая часть всегда равна 0.
Процесс квантования в кодеке реализован следующим образом: как только вычислен и переведён из дополнительного кода в прямой, очередной двадцатиодноразрядный элемент результирующей матрицы линейного преобразования, определяется, является ли этот элемент низкочастотным коэффициентом и если да, разряды с 19 по 12 записываются в восемь старших разрядов промежуточного шестнадцатиразрядного регистра, 8 младших разрядов данного регистра, при этом, заполняются нулями (разряды с 11 по 0 исходного двадцатиодноразрядного слова отбрасываются, так осуществляется операция деления на 4096).
Если элемент является высокочастотным коэффициентом, то в самый старший разряд промежуточного регистра записывается 0, в семь следующих разрядов переписываются разряды с 18 по 12 двадцатиодноразрядного слова, а 8 младших разрядов промежуточного регистра, также, заполняются нулями. Выходы с данного промежуточного регистра подключены к одному из входных портов умножителя 16×16, на другой порт данного умножителя подаются значения из памяти ROM, где хранятся дробные части коэффициентов квантования, возведённых в степень -1. Причём, на 8 старших выводов порта подаются нулевые значения, а на 8 младших — значения считанные с памяти ROM.
Далее, с тридцатидвухразрядного выходного порта умножителя считывается результат квантования, в котом 16 младших разрядов — дробная часть, которая отбрасывается, а 8 разрядов, стоящих непосредственно перед фиксированной запятой, это значащая часть (я думаю и так понятно, что результат квантования — это дробное число, представленное в формате с фиксированной точкой). Причём, в случае с низкочастотными коэффициентами, значащей частью являются не 8, а 7 разрядов, стоящих непосредственно перед запятой, в восьмой разряд здесь переписывается знак, полученный ещё на этапе базового преобразования, находящийся в самом старшем разряде:
Ну и далее, сформированные восьмиразрядные значения записываются в буферную память RAM в адресное пространство 00h — 3Fh:
Готовые данные с буферной памяти считываются в соответствии с алгоритмом зигзаг-сканирования (что такое зигзаг-сканирование можно прочитать здесь) и идут на этап кодирования длин серий.
Декодирование идёт в обратном порядке. И здесь мы оперируем уже пятнадцатиразрядными данными: 6 младших разрядов — разряды, которые теряются при делении на 64, 8 разрядов — значащая часть, 1 разряд — знак. Итого: 6+8+1 = 15:
На первом этапе, поступившее в операционный блок, осуществляющий обратное дискретное косинусное преобразование, восьмиразрядное слово разворачивается до пятнадцатиразрядного. Для это, сначала осуществляется проверка, не является ли поступивший байт низкочастотным коэффициентом, и если да, то все 8 разрядов переписываются в 8 младших разрядов пятнадцатиразрядного слова. А если поступил высокочастотный коэффициент, то 7 младших разрядов поступившего байта переписываются в 7 младших разрядов пятнадцатиразрядного слова, а старший разряд, содержащий знак, записывается в самый старший разряд пятнадцатиразрядного слова.
Затем развёрнутые до 15-ти разрядов данные записываются в буферную память RAM в адресное пространство 00h — 3Fh в соответствии с алгоритмом зигзаг-сканирования. После того как в памяти RAM будет сформирована матрица квантованных коэффициентов ДКП размером 8 на 8, начинается процесс обратного дискретного косинусного преобразования, также как было описано выше. При этом каждое считанное пятнадцатиразрядное слово с RAM, сначала проходит процедуру восстановления (процедура обратная квантованию) путём умножения на соответствующий коэффициент квантования, хранящийся в памяти ROM.
Здесь осуществляется умножение четырнадцатиразрядного слова на восьмиразрядный коэффициент квантования, который является целым числом (это те значения, которые при сжатии возводились в степень -1). Далее осуществляется перемножение матриц также, как было описано выше. После чего из получившихся пятнадцатиразрядных значений отбрасываются 6 младших разрядов (деление на 64) и проверяется знаковый разряд, и если его значение равно 0, то 8 последующих разрядов содержат результирующее значение декодируемой компоненты Y, Cb или Cr (в зависимости от того, какая компонентная плоскость декодируется). А если знаковый разряд равен 1, то следующие 8 разрядов просто обнуляются (т.е. округляются до 0, т.к. результат обратного ДКП не может быть отрицательным).
Получаемые восьмиразрядные результаты обратного ДКП записываются в буферную память RAM, формируя, таким образом, блок изображения 8 на 8. После того как блок сформирован, каждый его элемент переписывается во внешнюю память SRAM по соответствующему адресу, формируя там, в свою очередь, конечное изображение в пространстве YCbCr.
Преобразование Уолша
И вот, наконец-то мы дошли до того, ради чего всё затевалось. Преобразование Уолша — разновидность базового преобразования, матрица преобразования которого выглядит следующим образом:
Информацию о том, откуда эта матрица берётся, как выводится и как формируется, можно, также, найти в интернете или в учебниках по теории цепей и сигналов. Останавливаться здесь на этом не будем.
Итак, как было сказано выше, базовое преобразование сводится к умножению матрицы преобразования на матрицу исходных данных, после чего полученный результат снова умножается уже на транспонированную матрицу того же преобразования. Значения всех элементов матрицы преобразования Уолша равны либо 1, либо -1, соответственно аппаратно потребуется выполнять только операции сложения данных, представленных в дополнительном коде. Если расписать процесс умножения матрицы Уолша на исходную матрицу блока изображения 8 на 8, то получим следующие выражения для каждого строкового элемента промежуточной матрицы:
Где:
p[0…7] — очередная строка промежуточной матрицы;
x[0…7] — очередная строка исходной матрицы, являющейся блоком изображения 8 на 8.
И далее, если расписать процесс умножения промежуточной матрицы на транспонированную матрицу Уолша, то получим такие выражения для каждого уже столбцового элемента результирующей матрицы:
Где:
y[0…7] — очередной столбец результирующей матрицы;
p[0…7] — очередной столбец промежуточной матрицы.
Также как и в случае с ДКП, верхний левый элемент результирующей матрицы, будет являться низкочастотным коэффициентом, значение которого всегда больше 0, а остальные 63 элемента — высокочастотные коэффициенты, значения которых могут быть как меньше так и больше 0 (также как и при ДКП).
Аппаратно, блок преобразования Уолша, представляет собой группу сумматоров подключённых определённым образом, на входы которых сначала поочерёдно подаются строки исходной матрицы, результаты при этом запоминаются в буфер, а затем из буфера на входы этой же группы сумматоров поочерёдно подаются столбцы, ранее полученной матрицы. Также нужно учесть, что при прямом преобразовании Уолша, значения элементов результирующей матрицы могут выходить за пределы 255, поэтому их нужно будет разделить на 64 или сдвинуть на 6 разрядов вправо.
Обратное преобразование Уолша осуществляется точно также с тем лишь исключением, что элементы результирующей матрицы, которая будет являться блоком изображения 8 на 8 не нужно не на что делить, значения уже получаются нормированными.
Итак, в блоке прямого преобразования Уолша поступающие восьмиразрядные значения компонент, по аналогии с блоком ДКП, разворачиваются в пятнадцатиразрядные (6 разрядов — разряды которые будут потеряны при делении на 64, 8 разрядов — значащие разряды, 1 разряд — знак) и записываются в буферную память RAM. Как только в буфере сформирована матрица 8 на 8, из буфера построчно считываются элементы исходной матрицы, преобразуются, и записываются в адреса той же строки, откуда были считаны. Это позволяет использовать память RAM c организацией 64×15 (в случае с ДКП потребовался буфер с организацией 128×21), но Quartus II позволил создать блок памяти RAM только с организацией 64×16, один разряд остался не использованным (хотя в случае с ДКП не использовалось 11 разрядов).
Затем из буфера считываются уже столбцы матрицы, полученной на предыдущем этапе, преобразуются, и результат этого преобразования переводится из дополнительного кода в прямой, после чего абсолютно также, как и в случае прямого ДКП осуществляется операция квантования, результат которой записывается в буферную память RAM откуда, затем считывается в соответствии с алгоритмом зигзаг-сканирования. Обратное преобразование Уолша осуществляется аналогично прямому, поступающие данные при этом записываются в буферную память RAM в по алгоритму зигзаг-сканирования, а при считывании для непосредственного преобразования Уолша, домножаются на соответствующие коэффициенты квантования.
Ниже, в сравнительной форме, представлены результаты работы блоков прямого преобразования Уолша и прямого дискретного косинусного преобразования:
Сверху слева представлена фотография, на которой мы тренируемся, которая сначала была переведена, скажем так, внутри нашей отладочной платы, из цветового пространства RGB в про
