Методы сравнения изображений, используемые для управления синтезом, или сжатием изображений требуют более точного подхода. Существуют итерационные алгоритмы синтеза изображений по геометрической модели, основанные на методе излучательности. В этом методе рассчитывается распространение энергии от источников света к граням модели, отражение, преломление света. В этих алгоритмах на каждом этапе уточняется изображение, полученное на предыдущем шаге, при этом основной результат достигается уже после нескольких первых итераций, а далее полученное изображение уточняется лишь в отдельных областях. Лучшие современные реализации позволяют получать удовлетворительные результаты для реальных сцен за 15-20 минут, однако для получения точного результата им требуется до нескольких дней [5]. Для оптимизации подобных алгоритмов было бы полезно определять области, в которых изменения за последние 1-2 итерации были не заметны для человека, и исключать их из дальнейшего рассмотрения. Несмотря на простоту идеи, этот метод оказывается очень эффективным и позволяет сосредоточить усилия именно на тех участках, где это требуется. Единственным недостатком является то, что изменения могут складываться и после нескольких итераций, действие каждой из которых было практически незаметно, суммарный вклад может быть достаточно велик. Единственный способ борьбы с этим явлением - уменьшение порога, после которого участок больше не рассматривается.

Такой подход описывается в статье M.Ramasubramanian и др.[5], где строится модель восприятия изображения человеком, которая учитывает разную чувствительность глаза к перепадам яркости в зависимости от яркости фона и от однородности. Для этого авторы используют функцию чувствительности контраста. На основе некоторой модели для каждой точки изображения рассчитывается величина, на которую яркость данного пиксела может отличаться от правильной, чтобы человек не заметил отличия. Существенным недостатком этой системы является то, что в данный момент она учитывает все эти параметры только для одной из компонент цвета - яркости.

Другая подобная система описана в работе Gaddipatti и др. [6]. В ней для сравнения изображений сначала строится маска, выделяющая области перепада яркости, параллельно с вычислением маски производится вейвлет-преобразование изображения, и обнуляются те коэффициенты, которые соответствуют областям без перепадов. Затем с помощью функции чувствительности контраста определяется «важность» каждого из оставшихся коэффициентов и получившиеся наборы чисел сравниваются по метрике MSE. Кроме того в этой работе рассматривается вопрос, почему изображения некорректно считать просто сигналами и сравнивать их с помощью стандартных в области обработки сигналов метрик MSE и SNR.

Управление сжатием

где- разность соответствующих компонент цвета.

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

Для перехода из пространства RGB в пространство Luv необходимо сначала посчитать координаты цвета в пространстве XYZ, а потом с их помощью получить координаты в пространстве Luv. Для этого надо один раз посчитать так называемую тройственную матрицу В английской литературе - tristimulus matrix., а затем умножать на нее вектор (R,G,B).

Методика вычисления тройственной матрицы, а также переход из пространства RGB в пространство Luv описан в приложениях 1 и 2.

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

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

Функция чувствительности контраста

В качестве определения контрастности будем использовать определение по Майкельсону (Michaelson), согласно которому контрастность периодического сигнала L (в простейшем случае - яркости изображения) равна .

Функция чувствительности контраста (ФЧК) позволяет определить воспринимаемую глазом контрастность изображения в зависимости от частоты рассматриваемого сигнала. Она показывает отношение воспринимаемой контрастности к реально присутствующей. Мы воспользуемся ФЧК, описанной Mannos и Sacrison в статье [1], как одной из наиболее часто используемых в современных работах. Она вычисляется по формуле:

, (2)

где f - пространственная частота изображения.

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

График ФЧК приведен на рисунке 1.

Наилучшее восприятие контраста человеческим глазом соответствует частоте около 7,9 периодов/градус и соответствует чувствительности 0.98. Поскольку максимальное значение ФЧК не равно 1, то при использовании ее в качестве весовой функции, ее приходится нормировать. Нормированная ФЧК изображена на рисунке 1 пунктирной линией.

Рисунок 1. Функция чувствительности контраста.

Вычисление пространственной частоты

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

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

Исходя из определения функции чувствительности контраста, на вход преобразования Фурье (ПФ) должен подаваться массив яркостей изображения. Но чтобы можно было применить ФЧК для вычисления порогов различимости цветов, нужно чтобы пространственная частота отражала также неоднородности вызванные флуктуациями компонент u и v в пространстве Luv. Поэтому предлагается применить ПФ не к массиву яркостей точек, а к массиву величин .

Для того чтобы посчитать пространственную частоту, надо оценить вклад каждой из частот в неоднородность изображения. Вклад каждой частоты определяется ее амплитудой, а также чувствительностью глаза к этой частоте. Таким образом можно записать формулу для пространственной частоты F_sp изображения в точке:

, где (3)

f_rij - радиальная частота, соответствующая коэффициенту X_ij двумерного преобразования Фурье;

A_ij - действительная часть (т.е. амплитуда соответствующего сигнала) коэффициента X_ij двумерного ДПФ;

W_ij - весовой коэффициент, учитывающий вклад каждой частоты в воспринимаемую неоднородность изображения;

l - длина стороны квадрата, в котором рассматривается ДПФ;

cpd [пиксел/градус] - коэффициент для перевода частот к размерности [период/градус];

коэффициент N получается из условия

Радиальная частота, соответствующая коэффициенту двумерного преобразования Фурье, вычисляется по формуле:

, где

f_v и f_h - вертикальная и горизонтальная частоты, соответствующие этому же коэффициенту.

Весовой коэффициент W_ij описывает чувствительность глаза к возмущению, создаваемому определенной частотой ДПФ, и имеет вид:

, (4)

где NormCSF - нормированная функция чувствительности контраста.

Вычисление порогов различимости цветов

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

Поскольку ФЧК показывает отношение воспринимаемой контрастности к реальной, то для того, чтобы определить, отличит ли человек два цвета, нужно найти расстояние между этими цветами, умножить его на значение ФЧК и полученное число сравнить с порогами 1 и 3. Отсюда следует, что в точке (i,j) в качестве первого порога нужно использовать величину T_ij, а в качестве второго порога - 3 T_ij

, (5)

где F_{sp ij} - значение пространственной частоты;

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

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

Статистическая обработка и визуализация карты видимых ошибок

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

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

, где

H, W - высота и ширина изображения соответственно;

- расстояние между цветами в точке (i,j); см. формулу 1

I_i,j вычисляется по формуле:

T_ij - значение порога в точке (i,j), вычисляемое по формуле 5.

Эксперименты показали, что разница между изображениями становится хорошо заметна, когда характеристика LuvDiff превышает значение 0.8-0.9 для черно-белых изображений, и 1.2-1.4 для цветных.

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

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

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

Особенности программной реализации

Общие сведения

На основе предложенного алгоритма были написаны программа сравнения изображений, и программа тестирования алгоритмов сжатия изображений с потерями качества. Обе программы компилировались в среде Borland C++ Builder 4.0 Professional Edition. В обеих программах для вычисления дискретного преобразования Фурье, а также весовых коэффициентов в формулах 3, 4 использовались функции библиотеки Intel Signal Processing Library версии 4.1.

Кроме того, в целях оптимизации программы сравнения изображений алгоритм был модифицирован. За счет этого время работы программы было сокращено на 20%, а объем используемой памяти уменьшен на 10%. После этого, при тестировании на платформе Intel Pentium-III 500 128M Ram под управлением Windows NT 4.0, изображения размером 512x512 пикселов сравнивались за 19-20 секунд, при этом использовалось около 16Мб памяти.

Схема алгоритма

В результате написания дипломной работы был создан новый метод сравнения изображений, который моделирует человеческое восприятие, используя для этого специальные цветовые пространства, а также функцию чувствительности контраста. На основе предложенного метода написаны программы сравнения изображений, а также программа для полуавтоматического тестирования алгоритмов сжатия изображений с потерями качества, которая получала на вход исходные и восстановленные после сжатия изображения, сравнивала их, и записывала протокол сравнения в виде HTML-файла (образец смотри в приложении 4). Обе программы использовались в проекте Лаборатории Компьютерной графики ВМиК МГУ по созданию нового алгоритма сжатия изображений с потерями. Проект выполнялся по заказу корпорации Интел.

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

Abstract

In this work a new perceptual-based method of image comparison is introduced. It is based on the color comparison in perceptually uniform color space CIE Luv, and using Contrast Sensitivity Function to modify color similarity thresholds. This method can be used to measure image distortion in case of lossy image compression.

Литература

Для перехода в пространство Luv достаточно знать не сами координаты x, y, z, а промежуточные значения X, Y и Z. В любом случае их можно восстановить по формулам:

Далее переход в пространство Luv осуществляется по формулам:

,

где - соответствующие значения белого цвета для данного монитора.

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

Подробнее о цветовых пространствах, их свойствах и переходах в различные пространства смотри книгу Девида Тревиса [10].

Приложение 3. Вычисление индивидуальных порогов различимости цветов

Out - карта индивидуальных порогов

Extra=2^order - длина стороны квадрата, в котором проводится БПФ

void LUV::FFT(float ** Out, int Extra)

{

// Выделение памяти для коэффициентов БПФ

SCplx **Spectr;

bool res=false;

Spectr=new SCplx*[Extra];

if (Spectr==NULL)

throw Exception("Can't allocate RAM
for FFT spectrum");

Spectr[0]=new SCplx[Extra*Extra];

if (Spectr==NULL)

{

delete[] Spectr;

throw Exception("Can't allocate RAM
for FFT spectrum");

}

res=true;

int i;

for (i=1; i<Extra; i++)

Spectr[i]=Spectr[0]+i*Extra;

int order=int(log(Extra)/log(2)+0.5);

int j, c; // just counters

float tmp, mean;

// Инициализация матрицы для вычисления БПФ

nspsRealFftNip(NULL, NULL, order, NSP_Init);

for (i=0; i< Height; i+=2)

for (j=0; j< Width; j+=2)

{

// Преобразование Фурье строк области

// Field - массив значений

for (c=0; c<Extra; c++)

{

nspsRealFftNip(Field[i+c]+j, Spectr[c], order,

NSP_Forw);

nspcbConjExtend1(Spectr[c], (Extra>>1)+1);

}

// Транспонирование матрицы коэффициентов

Transpose(&Spectr, Extra);

// Преобразование Фурье столбцов области

for (c=0; c<Extra; c++)

nspcFft(Spectr[c], order, NSP_Forw);

// Вычисление амплитуд

nspcbReal(Spectr[0], Amps[0], Extra*Extra);

nspsbAbs1(Amps[0], Extra*Extra);

// Вычисление весовых коэффициентов

// Matrix - массив коэффициентов W_ij (см. формулы 4, 5)

// Freqs - массив значений (см. там же)

nspsbMpy2(Matrix[0], Amps[0], Extra*Extra);

mean=nspsMean(Amps[0], Extra*Extra);

// Вычисление пространственной частоты

tmp=nspsDotProd(Amps[0],Freqs[0], Extra*Extra);

/* Нормировка (В целях повышения быстродействия весовые коэффициенты нормируются после вычисления пространственной частоты)*/

if (mean!=0)

tmp/=Extra*Extra*mean;

else

tmp=0;

Out[i][j]=Out[i+1][j]=

Out[i][j+1]=Out[i+1][j+1]=CSF(tmp);

}

// Освобождение памяти

if (res)

{

delete[] Spectr[0];

delete[] Spectr;

}

}

Приложение 4. Протокол тестирования алгоритма сжатия