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


Фрактальный алгоритм - часть 4


Это существенно упрощает как компрессор, так и декомпрессор, т.к. задача масштабирования небольших областей является нетривиальной.

  • Все доменные блоки — квадраты и имеют фиксированный размер. Изображение равномерной сеткой разбивается на набор доменных блоков.

  • Доменные области берутся “через точку” и по Х, и по Y, что сразу уменьшает перебор в 4 раза.

  • При переводе доменной области в ранговую поворот куба возможен только на 00, 900, 1800 или 2700. Также допускается зеркальное отражение. Общее число возможных преобразований (считая пустое) — 8.

  • Масштабирование (сжатие) по вертикали (яркости) осуществляется в фиксированное число раз — в 0,75.

  • Эти ограничения позволяют:

    1. Построить алгоритм, для которого требуется сравнительно малое число операций даже на достаточно больших изображениях.

    2. Очень компактно представить данные для записи в файл. Нам требуется на каждое аффинное преобразование в IFS:

    • два числа для того, чтобы задать смещение доменного блока. Если мы ограничим входные изображения размером 512х512, то достаточно будет по 8 бит на каждое число.

    • три бита для того, чтобы задать преобразование симметрии при переводе доменного блока в ранговый.

    • 7-9 бит для того, чтобы задать сдвиг по яркости при переводе.

    Информацию о размере блоков можно хранить в заголовке файла. Таким образом, мы затратили менее 4 байт на одно аффинное преобразование. В зависимости от того, каков размер блока, можно высчитать, сколько блоков будет в изображении. Таким образом, мы можем получить оценку степени компрессии.

    Например, для файла в градациях серого 256 цветов 512х512 пикселов при размере блока 8 пикселов аффинных преобразований будет 4096 (512/8x512/8). На каждое потребуется 3.5 байта. Следовательно, если исходный файл занимал 262144 (512х512) байт (без учета заголовка), то файл с коэффициентами будет занимать 14336 байт. Коэффициент архивации — 18 раз. При этом мы не учитываем, что файл с коэффициентами тоже может обладать избыточностью и архивироваться методом архивации без потерь, например LZW.




    - Начало -  - Назад -  - Вперед -