Задание 2. Фрактальное сжатие

Цель задания

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

Описание задания

Введение

Задача - достичь как можно большего сжатия при использовании сетки фиксированного размера (4х4, 8х8 и 16х16 по параметру) и как можно лучшего соотношения степени сжатия к качеству для варианта с квадродеревом.

Мерой потерь будет служить PSNR - метрика обратно логарифмически пропорциональная среднеквадратичному отклонению пикселов.

Замер будет проводиться в двух номинациях:

  • Сжатие с использованием сетки 4х4, 8х8 и 16х16 (допустим ТОЛЬКО классический алгоритм, который был рассмотрен на лекции).
  • Сжатие с использованием квадродерева и указанием качества.

Все результаты (с фамилиями авторов, естественно) будут сведены на двумерные графики - сжатие/качество. Ваши результаты будут там иметь вид примерно параллельно идущих кривых. Лучше тот, чтя кривая лучше по качеству при той же
степени сжатия.

Отдельно будет учитываться оптимизация алгоритма по скорости. Т.е. если алгоритм не только качественный, но еще и быстрее коллег - будут даваться дополнительные баллы (но основные баллы - за хорошее качество при высокой степени сжатия, очень быстро, но очень плохо - не вариант).

За первое место в любой номинации (после собеседования по алгоритму) - большие дополнительные баллы.

За второе и третье место - дополнительные баллы.

Если файл распаковывается с артефактами (картинку невозможно узнать), компрессор падает или работает более 3 минут - результат дисквалифицируется.

Для повышения соотношения степени сжатия и качества рекомендуется использовать следующие методы:

  1. Использование перевода в YUV и дискретизацию в 4 раза цветовых компонент U & V.
  2. Использование квадродерева - 16х16 - 8х8 - 4х4 с дроблением очередного блока, если его приближение (например), хуже среднего значения для всех остальных блоков. Другой вариант - просто по порогу, пропорционально пересчитываемому для каждого уровня квадродерева.
  3. Использование арифметического сжатия для дожатия афинных коэффициентов (в первую очередь сдвига и контрастности).

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

ВНИМАНИЕ! Из-за ваших ошибок возможно программа не заработает (такое бывает постоянно), поэтому настоятельно рекомендуется подавать ВСЕ задания. Ибо иначе вы рискуете не сдать курс.

Первая часть задания

Программа должна уметь получать на вход BMP файл и по опции -с - сжимать его, по опции -d распаковывать его.

Прочитать как выглядит заголовок BMP можно на:
http://c-site.h1.ru/infa/bmp_struct.htm

Вообще чтение BMP из файла проще возложить на систему - посмотрите в MSDN "LoadImage":
HBITMAP image =
(HBITMAP) LoadImage(0,"image.bmp",IMAGE_BITMAP,0,0,LR_LOADFROMFILE);

Пример простой программы, которая работает с BMP также входит в комплект VS.

По умолчанию должен использовать фрактальный алгоритм разбиением изображения на сетки 4х4, 8х8 и 16х16.

Программа должна быть консольным приложением и запускаться так:

     compress -c image.bmp out_file.fr -s 8
     compress -d out_file.fr out_image.bmp
  

Т.е. тестовый файл test.bat вида:

     compress -c image1.bmp out_file1.fr -s 8
     compress -d out_file1.fr out_image1.bmp
     compress -c image2.bmp out_file2.fr -s 8
     compress -d out_file2.fr out_image2.bmp
     compress -c image3.bmp out_file3.fr -s 8
     compress -d out_file3.fr out_image3.bmp
     compress -c image4.bmp out_file4.fr -s 8
     compress -d out_file4.fr out_image4.bmp
     compress -c image5.bmp out_file5.fr -s 8
     compress -d out_file5.fr out_image5.bmp
  

(обратите внимание - минус перед параметром означает, что это опция)

должен сжимать 5 тестовых изображений (image1.bmp, ... image5.bmp). Для оценки степени сжатия используются размеры каждого сжатого изображения, а для оценки качества - разница между исходным и распакованным изображениями.

Вторая часть задания

Для повышения соотношения качества к размеру (и набора дополнительных баллов) нужно реализовать работу с квадродеревом и управление качеством.

С ним ваша программа должна уметь выполнять тестовый файл test_qual.bat вида:

     compress -c image1.bmp out_file1.fr -q 10
     compress -d out_file1.fr out_image1.bmp
     compress -c image2.bmp out_file2.fr -q 10
     compress -d out_file2.fr out_image2.bmp
     compress -c image3.bmp out_file3.fr -q 10
     compress -d out_file3.fr out_image3.bmp
     compress -c image4.bmp out_file4.fr -q 10
     compress -d out_file4.fr out_image4.bmp
     compress -c image5.bmp out_file5.fr -q 10
     compress -d out_file5.fr out_image5.bmp
  

При этом q - параметр качества должен изменяться от 1 до 100 (включительно).

Для тестов будут использованы 4-6 значений, условно 10, 30, 50, 70, 85, 100.

Литература

  1. Настоятельно рекомендуется найти книгу "Методы сжатия данных." Диалог-МИФИ (Ватолин, Ратушняк, Смирнов, Юкин) Ссылки на интернет-магазины, в которых она есть:
    http://www.findbook.ru/search/d0?s=1&pvalue=%CC%E5%F2%EE%E4%FB+%F1%E6%E0%F2%E8%FF&r=1&ptype=1
  2. Также описание алгоритма есть в части книги на сайте:
    http://compression.ru/book/pdf/compression_methods_part2_a4.pdf

Требования к программе

Главное требование - выполнить обязательную часть задания.

Язык реализации – С или С++

Программа обязательно должна быть консольной (НИКАКОГО ИНТЕРФЕЙСА - обычный компрессор). Писать интерфейс вам потребуется позднее при обработке видео, всему свое время.

За использование чужих исходных текстов или совместное написание - программы всех участников будут сниматься с замеров, и будет выставляться 0 баллов. Программа должна устойчиво работать с изображениями ТОЛЬКО ДВУХ РАЗМЕРОВ - 256х256 и 512х512 в формате BMP и режиме RGB 24 бита на точку.

Если программа откажется работать с другими разрешениями (культурно сказав об этом) - это будет только в плюс.

Программа должна быть оптимизирована по скорости, т.е. если на вход ей дать изображение 512х512, то на средней машине она должна гарантированно отработать его за 5 минут.

Не укладываетесь - уменьшайте перебор. Если 6 прогонов с разным качеством на 5 изображениях будут работать больше 2.5 часов - то ваши работы будет достаточно сложно проверять.

Болванка и программа измерения находятся наверху задания.

НЕ ЗАБУДЬТЕ ПОЛОЖИТЬ В АРХИВ файл readme.txt.

© Лаборатория компьютерной графики при ВМиК МГУ