Четвёртый шаг. Интерполяция

К началу четвёртого шага числовая таблица всё ещё остаётся таковой, хотя некоторые или все значения в ней могут претерпеть изменения. По окончании четвёртого шага «рождается» цифровое изображение. Основная процедура четвёртого шага – интерполяция (процесс «демозаики»). Рассмотрю процедуру подробнее. Начну с пояснения.

В чём отличие между числовой таблицей («входом» четвёртого шага) и цифровым изображением («выходом» четвёртого шага)?

По определению, каждый элементарный фрагмент цветного цифрового изображения – пиксел – определяется тремя числами. Если будет известно только одно или два числа, то пиксел не существует. Когда такая ситуация распространяется на все пикселы, то цветное цифровое изображение не может быть построено.

Далее каждое из чисел, необходимых для определения пиксела, буду называть цветовой компонентой. Все цветовые компоненты делятся на три группы: «красные» компоненты или R-компоненты (аббр. от англ. red – «красный»), «зелёные» компоненты или G-компоненты (аббр. от англ. green – «зелёный») и «синие» компоненты или B-компоненты (аббр. от англ. blue – «синий»).

По определению, числовую таблицу можно «разгруппировать» на три набора чисел. Три набора содержат числа, которые кодируют напряжения на электродах трёх групп сенселей соответственно: «красных», «зелёных» и «синих». Другими словами, напряжения на электродах «красных» сенселей образуют набор R-компонент, напряжения на электродах «зелёных» сенселей образуют набор G-компонент и напряжения на электродах «синих» сенселей образуют набор B-компонент.

Каждый набор чисел можно представить в виде мозаичного изображения – чёрно-белого цифрового изображения, в котором между любыми двумя соседними пикселами, окрашенными в один из оттенков серого цвета, находится по одному пикселу, окрашенному в белый (или чёрный цвет). Первый вид пикселей назову «значимыми» пикселами, вторые – «пропусками».

Пример мозаичного изображения, соответствующего «зелёным» сенселям представлен на рис. 18. Сравните расположение «значимых» пикселей с зелёной «мозаикой», продемонстрированной на рис. 9.

Рис. 18. Фрагмент (18 х 18 пикселей) мозаичного изображения, соответствующего «зелёным» сенселям.

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

Мозаичные изображения, соответствующие «синим» и «красным» сенселям, содержат «пропуски» не только между «значимыми» пикселами по вертикали и по горизонтали, но и между «значимыми» пикселами по диагонали:

Рис. 19. Фрагменты (18 х 18 пикселей) мозаичных изображений, соответствующих «синим» (слева) и «красным» (справа) сенселям.

Вот так выглядит псевдоизображение, полученное наложением друг на друга трёх мозаичных изображений, и соответствующее ему цифровое изображение:

Рис. 20. Фрагменты (18 х 18 пикселей) псевдоизображения, составленного из трёх мозаичных изображений, (слева) и соответствующего ему цифрового изображения (справа).

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

Слово «интерполяция» означает определение неизвестного значения на основании «соседних» известных значений. Один из алгоритмов интерполяции каждый из нас мог применять, когда говорил: «в среднем я трачу … столько-то денег на то-то» или «мне потребуется в среднем … дня, чтобы сделать то-то». Пример.

Я живу в пригороде и периодически езжу на встречи в центр города. Если позавчера поездка заняла 30 минут, а вчера – 40 минут (по пути произошло ДТП и образовалась «пробка»), то в среднем я трачу «на дорогу» 35 минут. Поэтому сегодня я выйду из дома за 35 минут до начала встречи, чтобы вероятность приехать вовремя была выше.

Можно учитывать не только два «случая», а значительно больше. Чем обширнее статистика, тем выше точность интерполяции.

Интерполяция по определению не даёт точный результат. То есть имеет место ошибка интерполяции. Проиллюстрирую последнее утверждение, продолжив пример выше.

Сегодня я добрался на встречу за 32 минуты до её начала (по дороге я случайно встретился со знакомым, и между нами завязалась короткая беседа). Таким образом, ошибка интерполяции составила 3 минуты.

Интерполяция применяется не только для построения цифрового изображения из псевдоизображения. При изменении размеров готовых цифровых изображений или при повороте, деформации последних также производится интерполяция. Кстати, прежде, чем отобразить текст, который Вы читаете, и иллюстрации к нему процессор Вашего компьютера интерполирует изображение текста и фотографий, «подгоняя» его под текущее разрешение экрана.

Я постарался показать идею и особенности интерполяции. Теперь опишу процесс «демозаики», происходящий по одному из современных алгоритмов ([4]). Вначале сделаю замечание.

Строго, процесс «демозаики» и интерполяция – не одно и то же. Процесс «демозаики» включает в себя множественное выполнение интерполяции. Для каждого «пропуска» с помощью интерполяции определяется неизвестные числа – две цветовые компоненты. Процесс «демозаики» описывает то, что будет интерполироваться, и в каком порядке.

Алгоритм процесса «демозаики» может включать четыре этапа:

1. Рассматривается мозаичное изображение, соответствующее «зелёным» сенселям. Неизвестные G-компоненты интерполируются.

2. Когда все G-компоненты известны, создаются два дополнительных мозаичных изображения. Тон каждого «значимого» пиксела одного мозаичного изображения равен разнице G- и R- компонент. Тон каждого «значимого» пиксела другого мозаичного изображения равен разнице G- и B- компонент.

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

4. Рассматриваются три псевдоизображения. Одно состоит из G-компонент, второе – из «G- «минус» R»- компонент, третье – из «G- «минус» B»- компонент. Вычисляются недостающие R- и B- компоненты.

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

Почему бы просто не вычислить «среднее» между двумя соседними известными компонентами? Потому что возрастают ошибки интерполяции. В итоге получаемое цифровое изображение искажено, и зритель невооружённым взглядом может видеть искажения, тоновые и цветовые.

Например, границы контрастных областей могут быть либо «размытыми» (недостаточно контрастными в сравнении с оригинальным оптическим изображением), либо содержать цвета, которых нет на самом деле. Так изображение чёрных полосок на шкуре зебры приобретает жёлтый, синий или другого цвета контур. Таким образом, уменьшается техническое качество цифрового изображения по первому критерию.

Ещё пример искажения.

Зеркальный блик на поверхности глазного яблока, ровно, как и тонкие ресницы, «размываются». В целом изображение выглядит «замыленным», недостаточно резким. Уменьшается техническое качество цифрового изображения по пятому критерию.

Опишу каждый этап подробнее, делая по ходу описания некоторые обобщения и сравнения.

В большинстве алгоритмов процесса «демозаики» первым интерполируется мозаичное изображение, соответствующее «зелёным» сенселям.

Во-первых, оно содержит меньше всего пропусков. Другими словами, оно изначально содержит в два раза больше достоверной, «не усреднённой», информации, чем мозаичные изображения, соответствующие «красным» или «синим» сенселям.

Во-вторых, G-компоненты отражают распределение тонов будущего цифрового изображения. По сути, изображение, составленное из G-компонент, похоже на «обесцвеченное», в оттенках серого, исходное оптическое изображение. Это значит, что можно вычислять недостающие G-компоненты более эффективно, точно: предварительно оценивать характер распределения тонов (плавная смена тонов – резкая смена тонов).

Процессы «демозаики», в которых учитывается характер распределения тонов, называют процессом «демозаики» с предварительным определением границ (от англ. edge-sensitive demosaicking – ESD). ESD-процессы (к ним относится рассматриваемый алгоритм) обладают существенно более низким уровнем ошибок интерполяции. Как следствие, будущее цифровое изображение выглядит для зрителя более привлекательным, так как более похоже на то, что он видит собственными глазами. Обычно, человек не видит цветовых контуров вокруг пятен зебры или тоновых и цветовых искажений на повторяющихся текстурах (заборе, кирпичной кладке и т.д.)

Опишу идею ESD-процесса.

Рассмотрю фрагмент мозаичного изображения, соответствующего «зелёным» сенселям (рис. 21). Светлоту оттенка серого (тона) буду указывать в абстрактных единицах в пределах от 0 до 255. Тону с номером 0 соответствует чёрный цвет. Тону с номером 255 – белый.

В реальности мозаичное изображение – это часть числовой таблицы. Процессор рассматривает и выполняет арифметические операции над последовательностями из нулей и единиц, кодирующими напряжения на электродах сенселей.

Рис. 21. Фрагмент мозаичного изображения, образованного «зелёными» сенселями. Для каждого сенселя указаны его месторасположение (например, 4-ый слева 3-ий сверху – G43 – относительно верхнего левого угла сенсора) и значение его светлоты (например, G33 = 156). Для наглядности на фрагменте рассматриваются четыре G-компоненты, серые тона «подкрашены» зелёным цветом.

Как действует процессор? Например, необходимо интерполировать тон «пропуска» G43. Оценивает абсолютную (по модулю) разницу тонов двух соседних сенселей по горизонтали (|G33 – G35| = |156 – 225| = 69) и абсолютную разницу тонов двух «соседних» сенселей по вертикали (|G24 – G44| = |156 – 225| = 24).

Если оба результата вычитания меньше некоторого заранее определённого значения – «порога» – то сенсель характеризует однородную по тону область оригинального оптического изображения. Значение тона вычисляется как среднее от тонов четырёх «соседних» сенселей, результат «усреднения» округляется:

Если какой-то из результатов превышает «порог», то в одном направлении область однородна, а в другом существует граница. Приведу пример.

Пусть «порог» равен 25. По вертикали (25 > 24) область оптического изображения равномерна, однородна. А по горизонтали (25 < 69) – неравномерна. То есть искомый сенсель «запечатлел» вертикальную (или стремящуюся к вертикальной) границу двух областей, контрастных по отношению друг к другу.

Обращусь снова к примеру с зеброй. Искомый сенсель характеризует контур (границу) между чёрной и белой полосками на шкуре животного. В этом случае тон искомого сенселя вычисляется как среднее между тонами «соседних» сенселей по вертикали, потому что «соседи» по вертикали вероятнее всего принадлежат той же границе:

Если оба результата больше «порога», то искомый сенсель характеризует сложную область оптического изображения, например, текстуру (кирпичная кладка, ткань и т.д.) В этом случае вычисляется тенденция и учитываются тона всех, четырёх, «соседних» сенселей. К тонам каких «соседей» может быть ближе неизвестный тон: к «соседям» по вертикали или по горизонтали?

Таким же образом процессор фотоаппарата «рассуждает» относительно каждого пропуска в мозаичном изображении, составленном из значений напряжений на электродах «зелёных» сенселей. В итоге вычисляются все G-компоненты. Мозаичное изображение превращается в изображение, состоящее из G-компонент. Назову его «зелёным» каналом или G-каналом.

G-канал является чёрно-белым (в оттенках серого) аналогом цветного оптического изображения. Другими словами, G-канал характеризует распределение тонов (яркостей) на исходном изображении.

На этом первый этап процесса «демозаики» завершается. Прежде чем перейти к описанию второго этапа, сделаю замечание относительно современных алгоритмов ESD-процессов и эффективности применяемых в них методов интерполяции.

Я постарался показать идею процесса «демозаики» с предварительным определением границ (ESD-процесс). Многие современные алгоритмы ESD-процесса сложнее. Их основная особенность заключается в том, что они учитывают тона не только близлежащих «соседей», но и тона «дальних» соседей, а также тона сенселей других цветов: «красного» и «синего». По сути, рассматриваются сразу все три мозаичных изображения.

Таким образом, современные алгоритмы для интерполирования одной G-компоненты могут анализировать известные тона 25 «соседних» сенселей, как «зелёных», так и «синих» и «красных». Сравните, с примером, который я использовал для раскрытия идеи ESD-процесса. Здесь задействуются всего 4 известных тона сенселей одного «цвета», а используемые методы интерполяции называются билинейным (для первого случая) и линейным (для второго случая). С билинейной интерполяцией Вы можете встречаться в Adobe Photoshop, когда используете команду «Сохранить для Web…» («Save for Web…»).

Методы интерполяции, оценивающие тона сенселей всех цветов и разницу между названными тонами, получили название эффективной интерполяции по разницам цветов (от англ. colour difference-based efficient interpolation – CDEI). Ошибки интерполяции таких методов малы в сравнении ошибками методов, где оцениваются тона сенселей только одного «цвета». В большинстве случаев итоговое цифровое изображение получается приятным «для глаза» зрителя. Оно также не уступает по качеству изображениям, которые получены с помощью светочувствительных сенсоров, изготовленных по технологии наподобие Foveon X3 (посмотрите, краткий обзор современных технологий во втором разделе).

В рассматриваемом ESD-процессе как раз используется один из методов эффективной интерполяции по разницам цветов.

На втором этапе процесса «демозаики» строятся два дополнительных мозаичных изображения. По сути, две дополнительные числовые таблицы.

Дополнительные числовые таблицы нужны, чтобы уменьшить ошибки интерполяции и, как следствие, улучшить приближение оптического изображения будущим цифровым изображением. Уменьшение ошибок интерполяции возможно за счёт того, что дополнительные числовые таблицы содержат маленькие числа, а разброс тонов, значений таких чисел, «лежит» в довольно узких границах, например, от 34 до 85, от 48 до 125.

Сравните. Разброс исходных значений в соответствии с принятыми ранее обозначениями тонов составляет от 0 до 255. «Изменчивость» тонов на исходных мозаичных изображениях в 4-5 раз выше «изменчивости» тонов на дополнительных мозаичных изображениях.

Какие числа содержат дополнительные числовые таблицы? Результаты вычитания цветовых компонент друг с другом. Посмотрите на рис. 22:

Рис. 22. Фрагмент совмещённых трёх исходных мозаичных изображений. Для наглядности на фрагменте рассматриваются две R-компоненты и одна G-компонента, серые тона «подкрашены» соответствующими цветами.

Известные «красные» компоненты R41 и R43, а также известная «зелёная» компонента G42 участвуют в образовании одной компоненты. Например, таким способом:

где KR42 – компонента дополнительной числовой таблицы, содержащей разницы G- и R- компонент.

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

Различные методы интерполяции, относящиеся к классу интерполяций по разницам цветов, могут по-другому определять компоненты дополнительных числовых таблиц. Например, содержать не только разницы исходных цветовых компонент, но и их отношения. Однако, идея остаётся прежней: оперировать не исходными цветовыми компонентами, а искусственно созданными числами на основе исходных компонент. С целью уменьшить ошибки интерполяции.

Первое дополнительное мозаичное изображение будет содержать «значимые» пикселы в тех же местах, что и мозаичное изображение, соответствующее «красным» сенселям. Аналогично, расположение «значимых» пикселей на втором дополнительном мозаичном изображении будет повторять мозаичное изображение, соответствующее «синим» сенселям. Рис. 19 иллюстрирует расположение «значимых» сенселей на дополнительных мозаичных изображениях.

Когда второй этап завершён: построены две дополнительные числовые таблицы (мозаичные изображения), – наступает пора для интерполяции недостающих чисел.

На третьем этапе ESD-процесса ошибки интерполяции минимальны. Как я отмечал ранее, дополнительные числовые таблицы «равномерны» (числа мало отличаются друг от друга) и сами числа малы в сравнении с величинами, содержащимися в исходной числовой таблице.

Методы интерполяции на третьем этапе также достаточно сложны. Аналогично своим «собратьям» по классу они оперируют не только значениями новых числовых таблиц, но исходными цветовыми компонентами (значениями исходной числовой таблицы). С целями, указанными мной ранее. Здесь, как и на первом этапе, «разыскиваются» границы контрастных областей исходного оптического изображения.

Когда две дополнительные числовые таблицы заполнены недостающими числами, третий этап завершается.

На четвёртом этапе на основании G-канала и двух дополнительных числовых таблиц определяются R- и B- каналы. Например, для 3-его слева 2-ого сверху пиксела, для которого изначальна была известна лишь B-компонента, неизвестная R-компонента определяется простой операцией сложения:

где R32 – R-компонента рассматриваемого пиксела, KR32 – компонента дополнительной таблицы, соответствующая позиции рассматриваемого пиксела.

Для 4-ого слева 2-его сверху пиксела, для которого изначальна была известна лишь R-компонента, неизвестная B-компонента определяется аналогично:

где B42 – B-компонента рассматриваемого пиксела, KB42 –компонента дополнительной таблицы, соответствующая позиции рассматриваемого пиксела.

Процесс «демозаики» считается завершённым, когда получены три цветовых канала. Другими словами, для каждого пиксела цифрового изображения известны три цветовых компоненты.

Исходная числовая таблица при этом расширилась, в ней появились новые интерполированные значения. Такая, «расширенная» числовая таблица и есть цифровое изображение.

На этом третий шаг конвейера может быть завершён. Полученное цифровое изображение «отправляется» на четвёртый шаг – на последующую обработку и приведение к стандартному формату. Пока что, полученное цифровое изображение может быть «понято» и воспроизведено лишь самим «создателем» – цифровым фотоаппаратом.

Прежде чем перейти к рассмотрению последнего, пятого, шага конвейера обращу Ваше внимание на возможные дополнительные процедуры четвёртого шага. Обычно, они выполняются после того, как построено цифровое изображение.