Что такое квантование изображений
Переход от непрерывных сигналов и преобразований к дискретным
В систему обработки информации сигналы поступают, как правило, в непрерывном виде. Для компьютерной обработки непрерывных сигналов необходимо, прежде всего, преобразовать их в цифровые. Для этого выполняются операции дискретизации и квантования.
Дискретизация изображений
Дискретизация – это преобразование непрерывного сигнала в последовательность чисел (отсчетов), то есть представление этого сигнала по какому-либо конечномерному базису. Это представление состоит в проектировании сигнала на данный базис.
Наиболее удобным с точки зрения организации обработки и естественным способом дискретизации является представление сигналов в виде выборки их значений (отсчетов) в отдельных, регулярно расположенных точках. Такой способ называют растрированием, а последовательность узлов, в которых берутся отсчеты – растром. Интервал, через который берутся значения непрерывного сигнала называется шагом дискретизации. Обратная шагу величина называется частотой дискретизации,
Существенный вопрос, возникающий в ходе дискретизации: с какой частотой брать отсчеты сигнала для того, чтобы была возможность его обратного восстановления по этим отсчетам? Очевидно, что если брать отсчеты слишком редко, то в них не будет содержаться информация о быстро меняющемся сигнале. Скорость изменения сигнала характеризуется верхней частотой его спектра. Таким образом, минимально допустимая ширина интервала дискретизации связана с наибольшей частотой спектра сигнала (обратно пропорциональна ей).
Для случая равномерной дискретизации справедлива теорема Котельникова, опубликованная в 1933 году в работе “О пропускной способности эфира и проволоки в электросвязи”. Она гласит: если непрерывный сигнал 
имеет спектр, ограниченный частотой 
, то он может быть полностью и однозначно восстановлен по его дискретным отсчетам, взятым с периодом 
, т.е. с частотой 
.
Восстановление сигнала осуществляется при помощи функции 
. Котельниковым было доказано, что непрерывный сигнал, удовлетворяющий приведенным выше критериям, может быть представлен в виде ряда:
.
Эта теорема так же еще называется теоремой отсчетов. Функция 
называется еще функцией отсчетов или Котельникова, хотя интерполяционный ряд такого вида изучал еще Уитакер в 1915 году. Функция отсчетов имеет бесконечную протяженность по времени и достигает наибольшего значения, равного единице, в точке 
, относительно которой она симметрична.
Каждую из этих функций можно рассматривать как отклик идеального фильтра низких частот (ФНЧ) на дельта-импульс, пришедший в момент времени 
. Таким образом, для восстановления непрерывного сигнала из его дискретных отсчетов, их необходимо пропустить через соответствующий ФНЧ. Следует заметить, что такой фильтр является некаузальным и физически нереализуемым.
Приведенное соотношение означает возможность точного восстановления сигналов с ограниченным спектром по последовательности их отсчетов. Сигналы с ограниченным спектром – это сигналы, спектр Фурье которых отличен от нуля только в пределах ограниченного участка области определения. Оптические сигналы можно отнести к ним, т.к. спектр Фурье изображений, получаемых в оптических системах, ограничен из-за ограниченности размеров их элементов. Частоту называют частотой Найквиста. Это предельная частота, выше которой во входном сигнале не должно быть спектральных компонентов.
Квантование изображений
Рис. 1. Функция, описывающая квантование
Основная задача при этом состоит в определении значений порогов 
и уровней 
квантования. Простейший способ решения этой задачи состоит в разбиении динамического диапазона на одинаковые интервалы. Однако такое решение не является наилучшим. Если значения интенсивности большинства отсчетов изображения сгруппированы, например, в «темной» области и число уровней 
ограничено, то целесообразно квантовать неравномерно. В «темной» области следует квантовать чаще, а в «светлой» реже. Это позволит уменьшить ошибку квантования.
В системах цифровой обработки изображений стремятся уменьшить число уровней и порогов квантования, так как от их количества зависит объем информации, необходимый для кодирования изображения. Однако при относительно небольшом числе уровней на квантованном изображении возможно появление ложных контуров. Они возникают вследствие скачкообразного изменения яркости проквантованного изображения и особенно заметны на пологих участках ее изменения. Ложные контуры значительно ухудшают визуальное качество изображения, так как зрение человека особенно чувствительно именно к контурам. При равномерном квантовании типичных изображений требуется не менее 64 уровней.
Квантизация изображений
Квантизация — уменьшение цветов изображения (wiki). Конечно, сейчас мало кому это необходимо, но задача сама по себе интересная.
Квантизированная Лена привлекает внимание
Например, старый добрый формат GIF использует палитру, максимум на 256 цветов. Если вы захотите сохранить серию своих селфи как gif-анимацию (кому бы это надо было), то первое, что вам, а точнее программе, которую вы будете для этого использовать, надо будет сделать – создать палитру. Можно использовать статическую палитру, например web-safe colors, алгоритм квантизации получиться очень простым и быстрым, но результат будет «не очень». Можно создать оптимальную палитру на основе цветов изображения, что даст результат наиболее визуально похожий на оригинал.
Алгоритмов создания оптимальной палитры несколько, каждый имеет свои плюсы и минусы. Я не стану утруждать читателя нудной теорией и формулами, во первых мне лень, во вторых большинству это не интересно – статью просто пролистают, рассматривая картинки.
Далее вас ждёт скучное и непонятное повествование о методе медианного сечения, алгоритму рассеивания ошибок (шума квантизации) по Флойду-Стейнбергу (и не только), особенностях цветового восприятия человеческого глаза, а так же немного говнокода.
Итак – метод медианного сечения. Он прост до безобразия. Первым делом надо из всех уникальных цветов изображения составить RGB куб. Далее рассечь его по самой длинной стороне. Например, диапазон красного у нас от 7 до 231 (длина 231-7=224), зелёного от 32 до 170 (длина 170-32=138), синего от 12 до 250 (длина 250-12=238), значит, будем «резать» куб по синей стороне. Получившиеся сегменты так же рассекаем по длинной стороне и т.д. пока не получим 256 сегментов. Для каждого сегмента высчитать средний цвет – так мы и получим палитру.
Что здесь можно улучшить? Первое, что приходит в голову – вычислять средний цвет не тупо сложив все цвета и разделив на их количество [ sum(color) / count(color) ], а с учётом, сколько раз каждый цвет встречается в изображении. То есть каждый цвет умножаем на количество его вхождений в изображении, полученные значения складываем, результат делим на количество вхождений в изображении всех цветов данного сегмента [ sum(color * total) / sum(total) ]. В результате, наиболее часто встречаемые цвета имеют приоритет при вычислении, но и редкие цвета вносят свои корректировки, поэтому палитра получается лучше, визуальное отклонение цветов меньше. Для лучших результатов желательно ещё учитывать гамму, но я оставил это на потом. Второе не так явно – медианное сечение совсем не учитывает особенности восприятия цвета человеческим глазом. Оттенки зелёного мы воспринимаем гораздо лучше оттенков синего. Я решил исправить это недоразумение и «сплющил» куб – длины сторон помножил на коэффициенты из этой статьи. В результате по зелёной и красной стороне сечений стало больше, по синей меньше. Такого решения я больше нигде не встречал (может плохо искал), но результат на лицо.
Теперь у нас есть оптимальная палитра, не идеальная конечно (я знаю, что её можно ещё улучшить), но достаточно хорошая. Следующий шаг – индексирование цветов изображения. Самый простой вариант – в каком сегменте находится цвет, такой и индекс. Быстро и просто. Но есть одно но, и даже не одно, поэтому к данному шагу мы ещё вернёмся.
Есть ещё один способ улучшить качество получаемого изображения – рассеивание ошибок. Тут тоже всё довольно просто – из индексируемого цвета вычитаем соответствующий цвет палитры, получаем ошибку, рассеиваем её по соседним пикселям в соответствии с определённой формулой (шаблоном), самая известная формула Флойда-Стейнберга, её я и использовал. При рассеивании ошибок размываются резкие переходы между цветами, и визуально кажется, что изображение содержит больше оттенков (цветов). Если интересно – про рассеивание ошибок подробно и интересно можно почитать тут. Этот алгоритм я так же решил допилить, помножив ошибку на всё те же коэффициенты, как оказалось, это была очень хорошая идея – так как сечений по синему диапазону стало меньше, в нём получалась значительная ошибка, и без корректировки ошибки коэффициентами рассеивание вносило много «шума».
Вот теперь можно снова вернуться к индексированию. Рассеиванием ошибок мы изменяем цвета пикселей и получаем такие, которых нет в нашем RGB-кубе (напомню, он составлен исключительно из цветов изображения). Теперь нельзя просто посмотреть в каком сегменте находится цвет, чтобы назначить индекс. Решение нашлось сразу – поиск ближайшего цвета в палитре. В данную формулу я подставил всё те же коэффициенты. Сравнивая результаты подбора цвета палитры по индексу сегмента в который входит исходный цвет и результаты поиска ближайшего цвета, наглядно увидел, что ближайший цвет часто оказывается в соседнем сегменте. Если исходный цвет находится ближе к центру сегмента – то индекс сегмента соответствует индексу цвета в палитре, но чем ближе исходный цвет к краям сегмента, тем больше вероятность, что ближайший цвет окажется в соседнем сегменте. В общем, единственный правильный путь индексирования – поиск ближайшего цвета в палитре. Но у поиска есть минус – он медленный, очень медленный. Писать числодробилку на python плохая идея.
Ну вот, хотел объяснить в двух словах, а получилась целая куча непонятной писанины. Надеюсь, код я пишу лучше, чем объясняю, поэтому вот ссылочка на github. Код несколько раз переписывался, сначала совершенствовался алгоритм, пока результат меня не устроил, потом оказалось, что он жрёт слишком много оперативы при обработке фотографий (сначала тестировал на небольших картинках), пришлось перенести RGB-куб, медианное сечение и карту пикселей в базу данных (sqlite). Скрипт работает очень медленно, но результат получается лучше, чем квантизация средствами PIL/Pillow и GIMP’ом (в нём эта операция называется индексирование).
Оригинал 
Результат квантизации в GIMP, оптимальная палитра на 256 цветов + размывание цвета по Флойду-Стенбергу (нормальное)
Результат квантизации PIL/Pillow
Результат квантизации моим кодом
На что обратить внимание: рассеивание ошибки у GIMP сильно «шумит», PIL/Pillow создает не очень оптимальную палитру и практически не рассеивает ошибки (резкие переходы между цветами).
Если не видите разницу — посмотрите другие примеры на github.
Уменьшение размеров изображения с помощью квантования цвета
Дата публикации: 2018-06-13
От автора: потребность в цветовом квантовании появилась еще в те времена, когда аппаратное обеспечение, необходимое для отображения цветных изображений, было довольно медленным и дорогостоящим. В то время невозможно было отображать цветные изображения в 24 битах, по 8 бит для каждого цветового канала (красный, зеленый и синий). Каждый пиксель имел, как правило, глубину цвета 8 бит, и необходимость как-то с этим справляться была неизбежной. Поэтому уменьшение размера изображения иногда вызывало трудности.
Цветовое квантование уменьшает количество отдельных цветов изображения, сохраняя при этом новое изображение визуально похожим на оригинал. Для этой цели обычно создается таблица цветов, где один 8-разрядный индекс может использоваться для указания до 256 различных 24-битных цветов.
Описанные ограничения больше не являются проблемой, так как технологии и аппаратное обеспечение значительно усовершенствовались, однако есть определенные случаи, когда мы можем использовать этот метод. Например:
Некоторые дисплеи встроенных систем ограничены низким разрешением
Ситуации, в которых цель заключается в уменьшении размера изображения при минимизации уменьшения воспринимаемого качестве выводимого изображения
JavaScript. Быстрый старт
Изучите основы JavaScript на практическом примере по созданию веб-приложения
Квантование цвета, примененное сегодня
Для повторения — цветовое квантование пытается уменьшить количество различных цветов до набора стандартных. Даже с наилучшим набором из 256 цветов, есть много изображений, которые все еще могут выглядеть плохо. Одной из наиболее распространенных проблем являются контуры вокруг плавно переходящих областей цвета. Вот пример, иллюстрирующий данную проблему.
Рисунок 1. Резкие контуры краев на квантованном изображении
Чтобы решить эту проблему, мы использовали популярный метод обработки изображений, называемый диффузионным сглаживанием ошибок (EDD). Диффузионное сглаживания ошибок работает через вычисление ошибки между значением пикселя и другого ближайшего к нему пикселя; затем эта ошибка распространяется на соседние пиксели, которым еще не были присвоены цвета на карте цветов. После применения диффузии ошибок средний цвет области заметно похож на средний цвет исходной области, однако отдельные цвета полученного изображения ограничены только теми, которые можно найти в таблице цветов.
Существует множество методов диффузионного сглаживания ошибок, таких как Atkinson, Burkes, Stucki, Sierra-2, Sierra-3, Sierra-Lite, но наиболее известным является метод Флойда-Стейнберга. Все эти алгоритмы имеют общую черту: они рассеивают ошибку в двух направлениях, но ошибку они всегда вводят вперед, а не назад. Причина этого очевидна: если вводить ошибку назад, нам нужно будет пересматривать все обработанные пиксели, что приводит к бесконечному циклу распространения ошибок.
Мы можем представить это с помощью следующей диаграммы:
Рис 2. Диффузионное сглаживание ошибок
где x представляет текущий обработанный пиксель. Дробь внизу — это делитель ошибки. Мы скоро вернемся к этому.
Методы квантования
Существует несколько методов решения проблемы поиска подходящих представлений цветов. Самый простой — это разделение фиксированного размера, которое охватывает все цветовое пространство, не требуя первого прохода изображения для генерации разбиения, но оно дает не очень хорошие результаты. Адаптивное разбиение на цвета работает намного лучше, потому что для создания таблицы цветов требуется два этапа: на первом собирается статистика изображения (при этом выборка каждого пикселя изображения может не потребоваться), а на втором этапе создаются стандартные цвета. Широко распространены три типа адаптивных методов квантования цвета: по популярности, по среднему срезу и октет. Мы сосредоточимся на алгоритме среднего среза.
В каждом из вышеупомянутых методов разделение цветового пространства может быть представлено деревом. Создание дерева начинается либо со всего цветового пространства с дальнейшим разбиением его, либо с выбора большого количества небольших партий с дальнейшим объединением их. Метод среднего среза использует алгоритм расщепления, чтобы получить примерно равное распределение пикселей в результирующих партиях. Он реализуется путем многократного разбиения цветового пространства (кластера) с наибольшим количеством пикселей до тех пор, пока не будет заполнено желаемое количество кластеров или пока мы не сможем разделить кластер далее.
Сглаживание цветов
Цель квантования цвета заключается в создании цветовой палитры наиболее стандартных цветов данного изображения или, другими словами, в получении наиболее доминирующих цветов изображения. Эта цель не учитывает визуальную привлекательность. В этом нам может помочь сглаживание цветов.
Как мы уже упоминалось ранее, сглаживание принципиально связано с диффузией ошибок. Давайте используем в качестве примера изображение в оттенках серого. Цель заключается в применении порога, то есть в преобразовании всех пикселей ниже определенного значения в черные, а всех пикселей выше этого значения — в белые. При преобразовании пикселей мы используем простую формулу: если значение пикселя ближе к 0 (чистый черный), преобразуем его в черный, в противном случае он становится белым. Возьмем в качестве примера значение 117: оно ближе к 0 (черный), поэтому мы переводим его в черный. Стандартным подходом было бы просто перейти к следующему пикселю и применить ту же формулу. Однако возникает проблема, когда у нас есть большое количество одинаковых пикселей. Они все становятся черными, и у нас остается огромный набор черных пикселей.
JavaScript. Быстрый старт
Изучите основы JavaScript на практическом примере по созданию веб-приложения
Рисунок 3. Простое пороговое сглаживание, применяемое к изображению
Диффузия ошибок использует более продвинутый подход: мы распространяем ошибку каждого вычисления на соседние пиксели. На каждом шаге не просто та же формула применяется к следующему пикселю, но принимается к сведению предыдущая ошибка и значение ошибки добавляется к текущему пикселю. Например, если текущий пиксель по-прежнему равен 117, он не просто преобразуется в черный, но вычисляется новое значение пикселя на основе предыдущего значения ошибки пикселя. Следующий код представляет собой простую реализацию вышеуказанного метода.
Глубина и квантование цвета
Глубина цвета
Цвет каждого пиксела цифрового изображения описывается несколькими числами (в зависимости от используемой цветовой системы). Количество бит, отводимое на представление информации о цвете каждого пиксела, называют глубиной цвета (color depth) или битовой глубиной цвета (bit depth). Иногда под цветовой глубиной понимают максимальное количество цветов, которые можно представить.
Глубина цвета определяет, как много цветов может быть использовано при отображении одного пиксела. Например, если цветовая глубина равна 1 бит, то пиксел может представлять только один из двух возможных цветов – белый или черный. Если цветовая глубина равна 8 бит, то количество возможных цветов равно 2 8 = 256. При глубине цвета 24 бит количество цветов превышает 16 миллионов, что фактически превосходит способность глаза человека разрешать цвета. Такой режим называется True Color (истинный цвет). В связи с тем, что 24-pазpядное представление неудобно с точки зpения обpаботки изобpажения, обычно в режиме TrueColor используется 32 бита. В случае 32-pазpядного пpедставление информации о цвете младшие тpи байта описывают цвет точки, а стаpший байт либо упpавляет дополнительными паpаметpами (напpимеp, альфа-каналом, инфоpмацией о взаимном пеpекpывании объектов или глубине в тpехмеpном изобpажении), либо не используется. Понятно, что при таком представлении увеличивается размер изображения, однако существенно возрастает скорость его обработки центральным и графическим процессорами компьютера.
Квантование цвета
Квантование цвета (color quantization) используется для получения малого числа характерных цветов в изображении. Задачу квантования в данном случае можно сформулировать как выбор заданного количества «наилучших» цветов, имеющихся в полноцветном изображении, и замены всех остальных цветов изображения подходящими заместителями из этого списка. Раньше процесс квантования цвета был необходим потому, что видеосистема компьютера могла работать лишь с ограниченной цветовой палитрой (как правило, 256 цветов). Теперь оно используется с целью уменьшения размера графического файла, создания спецэффектов, повышения резкости границ и т.п.
Самым простым подходом здесь является выбор комплекта цветов для палитры с равномерным распределением каждой из цветовых компонент. Он обеспечивает широкий выбор цветов, но при этом не учитывается тот факт, что в большинстве изображений нет равномерного цветового распределения.
На данный момент существует несколько методик квантования цвета. Одним из наиболее эффективных является метод квантования цветов медианным сечением. При этом цветовое пространство рассматривается как трехмерный куб. Каждая ось куба соответствует одному из трех основных цветов: красному, зеленому или синему. Каждая из трех сторон разбивается на 255 равных частей, деления на осях нумеруются от 0 до 255, причем большее значение соответствует большей интенсивности цвета. Метод медианного сечения делит куб на 256 параллелепипедов, каждый из которых содержит примерно одинаковое количество пикселов. При таком разбиении куба центральная точка каждого параллелепипеда представляет оптимальный выбор для цветовой палитры. В той области куба, которая густо заполнена точками, будет больше параллелепипедов и, соответственно, в палитру попадет больше цветов. А там, где точек меньше, будет взято меньшее количество цветов. При этом ни один цвет не будет отброшен полностью, а предпочтение будет отдано тем цветам, которые встречаются чаще.