Задание №2. Фрактальный компрессор изображений

Начало: 9 ноября 2006 года.
Конец: 22 ноября 2006 года

Цель задания

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

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

Введение

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

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

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

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

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

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

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

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

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

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

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

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

ВНИМАНИЕ! Баллов, набираемых на экзамене (письменном) по курсу будет недостаточно для положительной оценки. Т.е. необходимо выполнить УСПЕШНО хотя бы одно задание.

Обязательная часть задания

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

Прочитать как выглядит заголовок BMP можно на: http://graphics.cs.msu.su/courses/cg01b/hw1/bmpfmt.htm Вообще чтение BMP из файла проще возложить на систему - посмотрите в MSDN "LoadImage": HBITMAP image = (HBITMAP) LoadImage(0,"image.bmp",IMAGE_BITMAP,0,0,LR_LOADFROMFILE);

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

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

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

     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, то на Pentium4-1700 она должна гарантированно отработать его за 5 минут.

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

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

Оформление работы

ZIP-архив с исходными текстами и исполняемыми файлами, названный по схеме GGG_Z_V_nnnnnnnn.zip (где G - трехзначный номер группы, Z - номер задания, V - номер версии задания, nnnnnnnn - номер студенческого билета) присылайте на

Например, студент 306 группы с номером студенческого билета 05015042, сдающий обновленную (вторую) версию программы по первому заданию, должен прислать архив с именем 306_1_2_05015042.zip.

Также смотрите здесь, какие файлы нам присылать и как их оформить

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

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