«Алгоритмы дебайеризации»

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

им.

МЕХАНИКО-МАТЕМАТИЧЕСКИЙ ФАКУЛЬТЕТ

КАФЕДРА ТЕОРЕТИЧЕСКОЙ ИНФОРМАТИКИ

«АЛГОРИТМЫ ДЕБАЙЕРИЗАЦИИ»

Курсовая работа студентки 3его курса

Бешевой Инны Кахавны

Научный руководитель

Москва

2016 г.

Оглавление:

Введение …………………….………………………………………...………………3 Билинейная интерполяция ………………………………………..……………….4 Метод коэффициентов ……………………………………………...……………….4 Метод производных ……………………………………………………………....…..5 Алгоритм Кимелла ……………………………………………………………………5 Pixel Grouping алгоритм ……………………………………………...……………...7 Adaptive Homogeneity-Directed Demosaicing алгоритм ………...………………9

Введение

Основной элемент любой цифровой фото - или видеокамеры — матрица. От матрицы и объектива в наибольшей степени зависит качество получаемого изображения.

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

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

Существует несколько способов расположения светофильтров. Эти способы различаются чувствительностью и цветопередачей, при этом чем выше светочувствительность, тем хуже цветопередача. Исторически самый ранний мозаичный фильтр, использующийся в данный момент в большинстве цифровых фотокамер, это RGGB — фильтр Байера.

Первичные цвета  в фильтре Байера – красный, зеленый и синий (цветовая модель RGB). В классическом фильтре Байера применяются светофильтры трёх основных цветов в следующем порядке:

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

Вследствие использования фильтров каждый фотоприемник воспринимает лишь 1/3 цветовой информации участка изображения, а 2/3 отсекается фильтром. Для получения остальных цветовых компонент используются значения из соседних ячеек. Недостающие компоненты цвета рассчитываются процессором камеры на основании данных из соседних ячеек в результате интерполяции. Таким образом, в формировании конечного значения цветного пиксела участвует 9 или более фотодиодов матрицы.

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

Рассмотрим основные методы дебайеризации.

Билинейная интерполяция

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

Метод коэффициентов

Идея данного метода состоит в том, что соотношения цветов примерно одинаковы на одном объекте изображения. Сначала интерполируется зеленый цвет, так как он преобладает в байеровской матрице, затем вычисляются соотношения зеленого и красного (синего) в соответствующих пикселях. Коэффициенты в других пикселях находят с  помощью некоторого линейного алгоритма (например, как среднее арифметическое четырех соседних). Затем по получившемуся коэффициенту выражают красную (синюю) компоненту искомого пикселя. Такой метод  дает более высокий результат,  но проблема возникает в областях с малым количеством зеленого цвета.

Метод производных

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

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

Алгоритм Киммела

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

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

Сначала вычисляются вертикальная Dy, горизонтальная Dx и две диагональные производные Dxd и Dyd.

После этого по формуле находят весы Ei, где D(Pi) – производная в направлении P5 – Pi, то есть вертикальная, горизонтальная или одна из двух диагональных.

Затем с помощью вычисленных весов и коэффициентов определяются красные и синие компоненты.

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

Pixel grouping algorithm

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

Пусть дана  байеровская матрица, изображенная на рисунке:

Сначала интерполируем зеленую компоненту для пикселей, в которых известны красные и синие компоненты.

Например, найдем зеленую компоненту 13ого пикселя, у которого известна красная компонента R13, то есть найдем G13. Для этого вычислим north-, east-, west - и south-градиенты по формулам:

ДN = | R13 − R3 | Ч 2 + | G8 − G18 |

ДE = | R13 − R15 | Ч 2 + | G12 − G14 |

ДW = | R13 − R11 | Ч 2 + | G12 − G14 |

ДS = | R13 − R23 | Ч 2 + | G8 − G18 |

Далее находим минимальный из градиентов. Он характеризует направление, по которому значение компонент меняется меньше всего. То есть вероятно, что пиксели расположенные в данном направлении относительно пикселя G13  принадлежат одному и тому же объекту на изображении.

Если минимальный градиент - ДN, то G13 = (G8 Ч 3 + G18 + R13 − R3) / 4

Если минимальный градиент - ДE, то  G13 = (G14 Ч 3 + G12 + R13 − R15) / 4

Если минимальный градиент - ДW, то G13 = (G12 Ч 3 + G14 + R13 − R11) / 4

Если минимальный градиент - ДS, то G13 = (G18 Ч 3 + G8 + R13 − R23) / 4

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

Аналогично, находим зеленые компоненты пикселей, у которых известны синие компоненты.

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

Например, найдем B8 и R8 для 8ого пикселя, у которого изначально известна компонента G8. Для этого используется специальная функция hue_transit.

hue_transit (l1, l2, l3, v1, v3) :

если (l1 < l2 < l3) или (l1 > l2 > l3), то v1 + (v3 − v1) Ч (l2 − l1) / (l3 − l1)

иначе  (v1 + v3) / 2 + (l2 Ч 2 − l1 − l3) / 4

Теперь с помощью этой функции находим B8 и R8.

B8 = hue_transit(G7, G8, G9, B7, B9)

R8 = hue_transit(G3, G8, G13, R3, R13)

Идея состоит в том, что если зеленые компоненты монотонно возрастают (убывают) в данном направлении (для нахождения синей компоненты – горизонтальном, для красной - вертикальном), то B8(R8) придается значение, лежащее между B7 и B9 (R3 и R13). То есть предполагается, что красные (синие) компоненты в данном направлении тоже монотонно возрастают (убывают), причем множителем  (l2 − l1) / (l3 − l1) учитывается скорость возрастания (убывания). В противном случае (G8 меньше или больше обоих соседей) предполагается, что B8(R8) также будет меньше или больше соседей.

Осталось найти синие (красные) компоненты в тех пикселях, где были известны красные (синие) компоненты.

Например, найдем B13 для 13ого пикселя, у которого изначально была известна R13. Для этого вычислим north-east - и north-west-градиенты.

ДNE = | B9 − B17 | + | R5 − R13 | + | R13 − R21 | + | G9 − G13 | + | G13 − G17 |

ДNW = | B7 − B19 | + | R1 − R13 | + | R13 − R25 | + | G7 − G13 | + | G13 − G19 |

Найдем минимальный из двух градиент.

Если минимальный градиент - ДNE, то B13 = hue_transit(G9, G13, G17, B9, B17)

Если минимальный градиент - ДNW, то B13 = hue_transit(G7, G13, G19, B7, B19)

Аналогично, находим красные компоненты пикселей с известными синими компонентами.

Adaptive homogeneity-directed demosaicing algorithm

Идея данного алгоритма состоит в интерполировании компонент вдоль направления с наименьшим количеством цветовыми артефактами (aliasing, zippering и другие). Для определения таких направлений вводится метрическая модель, и интерполирование происходит в направлении, максимизирующем вводимую метрику.

Метрическая модель

Пусть X  двумерное множество координат расположения пикселей, и Y множество значений цветового пространства CIE RGB (то есть множество троек (R, G,B)). Тогда изображение от это отображение f из множества координат пикселей в множество наборов  (R, G,B).

f : X → Y

Теперь определим окрестность точки x∈X.

Пусть д ∈ ℜ, d ( ⋅,⋅ ) – некоторая функция расстояния на множестве X. Тогда д-окрестность точки x B(x, д) определим как:

B(x, д) = {p ∈ X | d (x, p) ≤ д }

Теперь рассмотрим цветовое пространство CIE LAB. Это трехмерное пространство, заданное тремя осями L, a,b. Вертикальная ось L характеризует яркость изображения.  Координата L принимает значения от 0 до 100 (от темного к светлому). Хроматическая составляющая цвета характеризуется декартовыми координатами a и b. a обозначает положение цвета от зеленого к красному, b – от синего к желтому.

Пусть dL ( ⋅,⋅ ) – евклидово расстояние по L координате, а dС ( ⋅,⋅ ) – евклидово расстояние на плоскости (a, b). Тогда определим окрестности Lf и Cf как:

Теперь определим окрестность Uf:

Если x0 ∈ Uf ( x, д,еL, еC ), то предполагается, что f(x0) будет близко к f(x).

Пусть | ⋅ | обозначает мощность множества. Тогда определим отображение Hf : X Ч ℜ3 → ℜ как:

Функция Hf используется для того, чтобы определить наилучшее направление интерполяции. Выбор направления очень важен, при неудачном выборе могут возникнуть цветовые артефакты. Например,  при интерполировании по направлению, ортогональном к границе объекта, может возникнуть эффект zippering, изображенный на рисунке.

Интерполяция

Первый этап интерполяции - восстановление зеленого цвета. Зеленый компонента строится отдельно по известным красным и синим. Получаем два изображения fh и fv (горизонтальное и вертикальное), построенные интерполяцией вдоль строк и вдоль столбцов соответственно.

Построим изображение fh по известным красным компонентам fv строится аналогично.

Рассмотрим красно-зеленую строку матрицы Байера.

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

Известны значения G(n) при четных n, и R(n) - при нечетных.  Разложим  G(n) на четную и нечетную составляющие:

Заметим, что G( n ) = G0( n ) + G1( n ). G0( n ) доступна из самой матрицы Байера, а G1( n ) требуется найти.

Пусть h  линейный фильтр (например, идеальный фильтр низких частот). Пропустим G(n) через фильтр: y( n ) = h( n ) ∗ G( n ), требуем, чтобы y( n ) = G( n ). Разложим фильтр h(n) на четную и нечетную составляющие, тогда:

Функцию можно переписать в виде:

Сигнал h0(n) выбираем таким, что сигнал разности G1( n ) − R1( n ) ослабляется:

Тогда, окончательная формула для вычисления зеленой компоненты по красной компоненте имеет вид:

Для нахождения h(n) решается следующая задача оптимизации:

где ^ обозначает преобразование Фурье

Решение данной задачи, вычисленное с помощью Matlab:

Затем восстанавливается красная компонента. Т. к. G(n)-R(n) медленно меняющаяся функция, интерполируем изображение разности R-G по уже вычисленному R1-G1, используя фильтр низких частот LP:

Аналогичная техника используется для нахождения синей компоненты.

Устранение цветовых артефактов

Для устранения цветовых артефактов используется медианный фильтр. median(.) обозначает оператор медианного фильтра. Для лучшего эффекта следующая процедура повторяется несколько раз:

R = median(R − G) + G

B = median(B − G) + G

G = 1/2 (median(G − R) + median(G − B) + R + B)

Окончательный алгоритм

Пользуясь всем вышеизложенным, составим полный алгоритм:

Строим  горизонтальное изображение fh по известной красной компоненте  и вертикальное изображение fv по известной синей.

Рассчитываем Hfh и Hfv с помощью метрической модели.

Находим функцию f следующим образом:

Пользуемся техникой устранения цветовых артефактов.

На шаге 2 для построения метрической модели требуются параметр д, еL, еC.  Параметр д принимает фиксированное значение, а параметры еL и еC подбираются подходящими под сцену данного изображения. Например, если пиксель n ∈ X расположен на горизонтальной границе некоторого объекта, то хотим, чтобы пиксели расположенные слева и справа по горизонтали попадали в окрестность Uf( n, д,⋅,⋅).

Пусть n1 и n2 координаты данного пикселя по горизонтали и вертикали, соответственно, тогда n = [ n1,n2 ] T. Положим еL:

Если же пиксель n расположен на вертикальной границе некоторого объекта, то еL имеет вид:

Аналогично, строится еC.

Список литературы:

An Improved Demosaicing Algorithm,
Alexey Lukin, Denis Kubasov
Moscow State University

Pixel Grouping Algorithm

Chuan-kai Lin

Adaptive Homogeneity-Directed Demosaicing Algorithm
Keigo Hirakawa, Thomas W. Parks
Electrical and Computer Engineering Cornell University