q-dex q-dex

Алгоритм сжатия изображений PGA

При создании графических приложений для микроконтроллеров семейств ARM, AVR, PIC часто возникает необходимость загрузки изображений из файла. Проблема как сравнительно невысокой вычислительной мощности чипа, так и низкой скорости обмена данными с ПЗУ заставляет задуматься об оптимальном формате графического файла. Форматы без сжатия, такие как BMP, имеют довольно простую структуру, но довольно большой размер. Форматы, использующие сжатие информации (например, JPEG), несмотря на компактный размер, требуют серьезных вычислений при загрузке изображений. Оба эти фактора сильно влияют на скорость загрузки графических файлов. В связи с этим возникла необходимость разработать формат графических файлов, позволяющий уменьшить занимаемое пространство на носителе и имеющий простой алгоритм восстановления исходного изображения.

Суть алгоритма заключается в разбиении изображения на квадратные блоки и аппроксимации значений каждой цветовой плоскости вдоль линий (два цвета по горизонтали и один по вертикали) внутри блока. Результатом такой аппроксимации будут полиномы вида y=A+BX или y = A+BX+CX^2 (в зависимости от выбранного режима). Алгоритм использует метод наименьших квадратов для построения подобных полиномов. Рассмотрим работу алгоритма на примере:

рис. 1 рис. 2

Имеем исходное изображение (рис. 1). Первым шагом алгоритма будет разбиение изображения на блоки фиксированного размера (рис. 2). В нашем случае размер блока равен 10 пикселям. Каждый блок анализируется независимо от остальных. Блок содержит три цветовые плоскости (рис. 3), каждая из которых, в свою очередь, будет аппроксимироваться отдельно по линиям (рис. 4). Следует отметить, что многие LCD дисплеи оптимизированы под вывод графики прямоугольными блоками. Данная особенность положительно скажется на быстродействии алгоритма.

рис. 3 рис. 4

Рассмотрим, как будет обрабатываться красный цвет, для других цветов процедура будет аналогичной. Красный блок состоит из n линий по n пикселей. В данном случае n = 10, а блок имеет размеры 10х10, диапазон цвета от 0 до 255 (24-х битный режим, по 8 бит на цветовую компоненту). Аппроксимируя данные значения для блока методом наименьших квадратов, мы получим уравнение параболы (или прямой), записывая в файл вместо десяти значений цветовых компонент только два-три коэффициента аппроксимирующих функций, можно сэкономить значительные объемы дискового пространства. Примеры линейной и квадратичной аппроксимации представлены на рисунках 5 и 6. Для записи коэффициентов полиномов разных степеней применяются различные подходы:

  1. Вычислить и сохранить значения аппроксимирующей функции в нескольких точках, а в процессе чтения восстанавливать коэффициенты этой функции. Данный способ будет работать, так как каждая парабола (или прямая) уникально задается тремя (или двумя) точками.
  2. Коэффициенты представляются в формате с фиксированной точкой: 1 бит на знак, 5 бит на целую часть, 2 бита на дробную часть.
рис. 5 рис. 6

Из-за того, что коэффициенты квадратичной функции в некоторых случаях могут доходить до 1500-2000, для сохранения этих коэффициентов потребуется не менее 12 бит, а значения самих функций всегда попадают в диапазон 0-255 и требуют только 8 бит для хранения, поэтому при сохранении квадратичной функции используется первый метод. Для сохранения линейных функций используется второй подход, так как он имеет меньшую вычислительную сложность. Таким образом, можно добиться того, что информационный объем любого параметра аппроксимирующей функции не превысит 8 бит. В описанном примере блок исходного изображения имел объем в 300 байт, при квадратичной аппроксимации размер блока составит 90 байт, а при линейной 60 байт.

Следует отметить, что описанный алгоритм приводит к потере качества изображения, и потери будут тем больше, чем больше выбран размер блока. В плане экономии дискового пространства алгоритм оказывается не самым эффективным и проигрывает популярному формату JPEG. Однако данный формат значительно превосходит по скорости загрузки как простой, но тяжеловесный BMP, так и компактный, но сложный по вычислениям JPEG.

Более подробно о структуре PGA файлов можно прочтать в спецификации к формату.

Скачать программу просмотра PGA изображений можно тут

Скачать программу для конвертирования изображений в формат PGA можно тут


184

Регистрационная форма

логин
фамилия
имя
отчество
e-mail
пароль
еще раз
пол

Сколько углов у фигуры?

Q-DEX, авторы: Кураев С.В. Саруханян С.К. © 2016г.-2019г.