Задание 2: Квантование (Quantization) 
                       Псевдотонирование (Dithering)

Цель задания - реализация и сравнение методов квантования (quantization) и псевдотонирования (dithering).

Реализуются и сравниваются следующие методы квантования:

1. Линейное квантование -- предварительное равномерное разбиение цветового пространства.
2. Алгоритм популярности. Строится гистограмма цветов в изображении и выбирается 2^m наиболее часто встречающихся цветов.
3. Алгоритм медианного сечения. Цветовой куб рекурсивно рабивается на параллелепипеды до тех пор пока не получится 2^m параллелепипедов, содержащих примерно равное количество точек. Центроид такого параллелепипеда определяет цвет для всех точек, оказавшихся в нем. Однако, результат может быть лучше, если цвет выбирается как центр масс для точек, оказавшихся в данном параллелепипеде.

Два последних алгоритма обеспечивают адаптивное нелинейное квантование.

Прочтите раздел из книги Дж.Фоли и А.ван Дама.

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

Реализуются и сравниваются следующие методы псевдотонирования:

1. случайное псевдотонирование,
2. упорядоченное псевдотонирование,
3. диффузия ошибки.

Для перевода цветного изображения в черно-белое используйте следующую формулу:

Исследуйте два варианта диффузии ошибки:

В дополнение к основному заданию можете реализоватьпрограмму оценки качества для методов псевдотонирования. Поскольку ошибка при псевдотонировании "размазывается", тот подход к ее вычислению, который использовался при квантовании, здесь не годится. Предлагается воспользоваться другой метрикой.
Прочтите раздел из книги Дж.Фоли и А.ван Дама.

Интерфейс

Интерфейс должен допускать ввод полноцветного изображения (в ВМР-формате), применение операции квантования или псевдотонирования, вывод полученного изображения (в BMP-формате) показ исходного и псевдотонированного изображений для визуальной оценки. Можно использовать директорию D:\tmp для записи результатов и промежуточной информации.

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

Pезультаты работы
Работа высылается по адресу assign2@graphicon.ru до 23:59 16 марта или в тот же день принимается на дискете в комн. 703 с 16:15 до 18:00. 

Набор изображений
Для работы можете использовать следующие изображения ( в формате BMP):
pic1.zip (265K)
pic2.zip (200K)
pic3.zip (343K) или pic3.rar (325K)
pic4.zip (593K) или pic4.rar (376K)

Учтите, что любое из этих изображений может быть использовано при проверке Вашей работы. 

Словарь

dithering: A means of providing additional gray shades or colors in an image by using neighboring pixels with different gray shades or colors. The method provides a larger color space at the expense of lower effective resolution. In the case where only two shades are provided (such as black and white laser printer), the method is sometimes called digital halftoning.

quantization: The process of converting a signal or function that varies continuously over a range into discrete levels, usually a range of successive binary numbers starting at zero. Linear quantization puts the binary numbers in correspondence with equal intervals over the continuous range. Nonlinear quantization puts the numbers in correspondence with nonuniform intervals covering the continuous range. In graphics, having too few quantization levels for intensity, i.e., too few shades of gray, produces artifacts in the image such as Mach banding. Potential cure include increasing the number of bits per pixel, using nonlinear quantization, or dithering -- or some combination of the three.