ЦИФРОВАЯ ОБРАБОТКА СИГНАЛОВ

Тема 17. ОБРАБОТКА ИЗОБРАЖЕНИЙ

Нет ничего, на что бы ни дерзнуло воображение человека.

Тит Лукреций. Римский философ и поэт. I в. до н. э.

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

Анатолий Пышминцев, Новосибирский геофизик Уральской школы. ХХ в.

Введение.

1. Основные понятия. Графическое представление изображений. Представление цвета в машинной графике. Цветовая модель RGB. Цветовая система CIE XYZ.

2. Геометрические преобразования растровых изображений. Области и этапы преобразований. Дискретизация. Интерполяционный ряд восстановления двумерного сигнала. Частотные искажения изображений и их устранение. Передискретизация изображений.

3. Фильтрация изображений. Линейные фильтры. Сглаживающие фильтры. Контрастоповышающие фильтры. Разностные фильтры. Двумерная циклическая свертка. Нелинейные фильтры. Пороговая фильтрация. Медианная фильтрация. Фильтры экстремумов.

4. Сжатие изображений. Алгоритмы кодирования длины повторения (RLE). Словарные алгоритмы. Алгоритмы статистического кодирования. Сжатие изображений с потерями. Оценка потерь в изображениях. Преобразование Фурье. Вейвлет-преобразование.

ВВЕДЕНИЕ

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

Изображение в математическом представлении - двумерный сигнал, несущий огромное количество информации. Цветное изображение размером 500 × 500 элементов - это массив в несколько сотен тысяч байтов. Обрабатывать такую информацию можно лишь рациональной организацией вычислений. Для конкретных задач обработки изображений можно применять эффективные способы обработки с учетом особенностей и ограничений этой конкретной задачи. Но если говорить об обработке изображений для решения широкого класса задач, то необходимо выделить набор стандартных операций, из которых можно строить алгоритмы для решения произвольных задач. К их числу относятся линейные преобразования, двумерная свертка и двумерное дискретное преобразование Фурье.

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

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

17.1. Основные понятия

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

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

Растровая графика оперирует с произвольными изображениями в виде растров. Растр (raster) - это описание изображения на плоскости путем разбиения (дискретизации) его на одинаковые элементы по регулярной сетке и присвоение каждому элементу своего цветового и любых других атрибутов. Самый простой растр – прямоугольный, самый экономичный по количеству отсчетов для передачи изображений - гексагональный. С математических позиций растр – это кусочно-постоянная аппроксимация на плоскости непрерывной функции изображения.

Элемент растра называют пикселем (pixel). Стандартная идентификация пикселей:

f(i, j) = (A(i, j),C(i, j)), (17.1.1)

где A(i, j) Ì R2 - область пикселя, C(i, j) Î C - атрибут пикселя (как правило, цвет). Чаще всего используются два вида атрибутов:

C(i, j) = I(i, j) - интенсивность (яркость) пикселя;

C(i, j) = {R(i, j), G(i, j), B(i, j)} - цветовые атрибуты в цветовой модели RGB.

В матричной форме:

Mij = (Aij, Cij).

При дискретизации непрерывных изображений значения Aij могут определяться двояко, либо как значения точек Aij = (i, j), для которых определены атрибуты Cij, либо как значения квадратов Aij = (i, i+1) × (j, j+1) или любой другой формы, с определением Cij по средним значениям в пределах этой формы (рис. 17.1.1).

На практике, как правило, X и Y - ограниченные наборы неотрицательных целых чисел квадратного или прямоугольного растра с аспектовым отношением (aspect ratio) ширины к высоте растра, которое записывается в виде, например "4:3".

Представление цвета в машинной графике. Понятие цвета базируется на восприятии глазами человека электромагнитных волн в определенном диапазоне частот. Воспринимаемый нами дневной свет имеет длины волн λ от 400 нм (фиолетовый) до 700 нм (красный). Описанием светового потока может служить его спектральная функция I(λ). Свет называется монохроматическим, если его спектр имеет только одну определенную длину волны.

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

Цветовая модель RGB (Red, Green, Blue - красный, зеленый, голубой) в машинной графике в настоящее время является самой распространенной. В этой модели спектральная функция представляется как сумма кривых чувствительности для каждого типа колбочек с неотрицательными весовыми коэффициентами (с нормировкой от 0 до 1), которые так и обозначаются - R, G и B. Модель характеризуется свойством аддитивности для получения новых цветов. К примеру, кодировка спектральных функций:

Черного цвета: fblack = 0, (R, G,B) = (0,0,0);

Фиолетового цвета fviolet = fred + fblue, (R, G,B) = (1,0,1);

Белого цвета fwhite = fred + fgreen + fblue, (R, G,B) = (1,1,1).

Трехмерное пространство цветов модели RGB приведено на рис. 17.1.3. В силу особенностей восприятия света рецепторами не все цвета, видимые человеком, представимы в этой модели. Однако доля воспроизводимых цветов значительно больше, чем доля не представимых в этой модели.

Цветовая система CIE XYZ. Международный стандарт представления цвета CIE (CIE - Commission Internationale de l"Eclairage) был принят в 1931 году Международной комиссией по освещению, В нем определяются три базисные функции ρX(λ), ρY(λ), ρZ(λ), зависящие от длины волны, линейные комбинации которых с неотрицательными коэффициентами (X, Y и Z) позволяют получить все видимые человеком цвета. Этими функциями учитывается относительное восприятие интенсивности света рецепторами глаза. В трехмерном пространстве цветовая система CIE образует конус в первом квадранте и применяется для высококачественного отображения цветных изображений.

17.2. Геометрические преобразования растровых изображений

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

Существуют три основные группы алгоритмов обработки изображений на компьютерах:

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

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

3. Эффективное кодирование для уменьшения объема при передаче и хранении.

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

КИХ фильтры реализуются методом свёртки. Преимуществом двумерных КИХ фильтров является наглядность, простота и абсолютная устойчивость. БИХ фильтры реализуются с помощью разностных уравнений и z-преобразований. Они более скоростные по сравнению с КИХ фильтрами, но могут оказаться неустойчивыми. Синтез двумерных БИХ фильтров отличается от синтеза одномерных, так как для двумерной функции в явном виде не удаётся выделить полюса.

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

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

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

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

В простейшем случае черно-белых изображений мы имеем двумерный массив sa(x, y). Для цветных изображений в модели RGB, учитывая свойство аддитивности при сложении цветов, каждый слой R, G и B также может рассматриваться и обрабатываться, как двумерный массив, с последующим суммированием результатов.

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

s(n, m) = sa(nDx, mDy),

где Dx и Dy - горизонтальный и вертикальный интервалы дискретизации двумерного непрерывного сигнала sa(x, y) с непрерывными координатами x и y. Ниже значения Dx и Dy, как и в одномерном случае, принимаются равными 1.

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

S(k, l) =s(n, m) exp(-jn2pk/N-jm2pl/M), (17.2.1)

S(k, l) =exp(-jn2pk/N) s(n, m) exp(-jm2pl/M), (17.2.1")

s(n, m) =S(k, l) exp(-jn2pk/N-jm2pl/M). (17.2.2)

s(n, m) =exp(-jn2pk/N) S(k, l) exp(-jm2pl/M). (17.2.2")

Эти выражения показывают, что двумерное ДПФ по прямоугольному растру дискретизации данных может вычисляться с помощью одномерных последовательных ДПФ. Вторые суммы выражений (17.2.1") и (17.2.2") являются одномерными ДПФ сечений функций s(n, m) и S(k, l) по линиям n и k соответственно, а первые - одномерными ДПФ вычисленных функций в сечениях по m и l. Другими словами, исходные матрицы значений s(n, m) и S(k, l) пересчитываются сначала в промежуточные матрицы с ДПФ по строкам (или по столбцам), а промежуточные - в окончательные с ДПФ по столбцам (или соответственно по строкам).

Для того чтобы периодическое повторение спектра (рис. 17.2.1), вызванное дискретизацией аналогового сигнала с частотой Fx=1/Dx и Fy=1/Dy, не изменяло спектр в главном частотном диапазоне (по отношению к спектру исходного аналогового сигнала), необходимо и достаточно, чтобы максимальные частотные составляющие fmax в спектре аналогового сигнала как по строкам, так и по столбцам, не превышали частоты Найквиста (fmax. x £ fN = Fx/2, fmax. y £ fM = Fy/2). Это означает, что частота дискретизации сигнала должна быть минимум в два раза выше максимальной частотной составляющей в спектре сигнала:

Fx ³ 2fmax. x, Fy ³ 2fmax. y, (17.2.3)

что обеспечивает выход спектральных функций на нулевые значения на концах главного диапазона спектра.

Интерполяционный ряд восстановления двумерного сигнала. Если непрерывный сигнал sa(x, y) является сигналом с ограниченным спектром, а периоды дискретизации выбраны достаточно малыми и спектры соседних периодов не перекрываются:

Sa(Wx, Wy) = 0 при |Wx|p/Dx, |Wy|p/Dx,

то, как и в одномерном случае, сигнал sa(x, y) может быть восстановлен по дискретному сигналу с использованием двумерного аналога ряда Котельникова-Шеннона:

sa(x, y) = Sn Sm s(n, m). (17.2.4)

Частотные искажения изображений и их устранение. Сигнал с неограниченным спектром также может быть дискретизирован, однако в этом случае имеет место наложение спектров в смежных периодах, при этом высокие частоты, большие частот Найквиста, будут "маскироваться", как и в одномерном случае, под низкие частоты главного периода. Эффект "отражения" от границ периода дает еще более сложную картину вследствие интерференции частот, отраженных по разным координатам. Аналогичный эффект, известный как алиасинг (aliasing) будет наблюдаться и при недостаточной частоте дискретизации изображений. Особенно наглядно этот эффект можно наблюдать на резких контрастных изменениях яркости.

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

z(x, y) = h(x", y") ③③ s(x-x", y-y"). (17.2.5)

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

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

Таблица 17.2.1.

Основные весовые функции

Двумерные аналоги одномерных фильтров f1(x) строятся в двух вариантах симметрии: или как функция от радиуса:

f2(x, y) = f1(),

или как произведение:

f2(x, y) = f1(x) × f1(y).

Первый вариант - более корректный, но второй обладает свойством сепарабельности, т. е. двумерную свертку можно выполнять двумя одномерными свертками последовательно по строкам с f1(x) и по столбцам с f1(y).

Передискретизация изображения или ресамплинг (resampling) – это изменение частоты дискретизации цифрового сигнала. Применительно к цифровым изображениям это означает изменение размеров изображения.

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

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

Допустим, мы имеем одномерный сигнал (рис. 17.2.4), заданный на интервале 0-Т и дискретизированный с шагом Dt=1 (N интервалов). Нужно «растянуть» сигнал в m раз. Спектр сигнала, показанный на рисунке, вычисляется быстрым преобразованием Фурье (БПФ, количество отсчетов спектра равно количеству отсчетов сигнала) и приводится в главном диапазоне БПФ (0-2p, частота Найквиста wN = p/Dt = p, или 0.5N по нумерации отсчетов спектра при шаге по спектру Df = 1/T или Dw = 2p/T). Для выполнения растяжения необходимо выполнить 2 шага.

Первый шаг – интерполяция нулями, увеличивающая длину сигнала в m раз. (рис. 17.2.5). Нужно умножить все отсчеты исходного сигнала на m, а потом после каждого отсчета сигнала вставить m-1 нулевое значение. На интервале 0-Т, значение которого остается без изменения, теперь располагается в m-раз больше интервалов дискретизации (mN), и новый шаг дискретизации будет равен Dx=Dt/m. Соответственно, новая частота Найквиста для этого сигнала равна mp/Dt = mp. Но физическая величина шага по спектру в единицах частоты обратна физической величине интервала задания сигнала (Df=1/T), и, следовательно, БПФ по mN точкам сигнала вычислит mN точек спектра в главном диапазоне БПФ 0-2pm с шагом спектра исходного сигнала, в котором будут присутствовать m-периодов спектра исходного сигнала (один главный и m-1 боковых).

Второй шаг – отфильтровывание боковых диапазонов спектра с помощью НЧ-фильтра или во временной, или в спектральной области. На рис. 17.2.6 выполнены очистка спектра и обратное преобразование Фурье, в результате чего получен сигнал в m раз длиннее исходного с полным сохранением всей частотной информации.

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

При выполнении ресамплинга только во временной области алгоритмы растяжения и сжатия объединяют, как правило, в единый последовательный процесс с заданием изменения шага дискретизации в виде отношения m/n, что позволяет задавать целые значения m и n при дробных значениях изменения шага дискретизации. Это существенно упрощает алгоритмы и повышает эффективность и качество их работы. Так например, при растяжении сигнала в 1.5 раза при m/n = 3/2 сигнал сначала растягивается в 3 раза (простое и равномерное дополнение нулями всех отсчетов, затем выполняется НЧ-фильтрация, после чего сигнал прореживается в два раза. Антиалиасингового фильтра не требуется, т. к. частота его среза перекрывается частотой первого НЧ-фильтра. При обратной операции сжатия (например, m/n = 2/3), аналогично используется только антиалиасинговый фильтр.

17.3. фильтрация изображений

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

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

Линейные фильтры имеют очень простое математическое описание. Будем считать, что задано исходное полутоновое изображение A, и обозначим интенсивности его пикселей A(x, y). Линейный фильтр определяется вещественнозначной функцией h (ядром фильтра), заданной на растре. Сама фильтрация производится при помощи операции дискретной свертки (взвешенного суммирования):

B(x, y) = h(i, j) ③③A(x, y) = h(i, j) A(x-i, y-j). (17.3.1)

Результатом служит изображение B. Обычно ядро фильтра отлично от нуля только в некоторой окрестности N точки (0, 0). За пределами этой окрестности h(i, j) равно нулю, или очень близко к нему и им можно пренебречь. Суммирование производится по (i, j) Î N, и значение каждого пикселя B(x, y) определяется пикселями изображения A, которые лежат в окне N, центрированном в точке (x, y) (обозначение - множество N(x, y)). Ядро фильтра, заданное на прямоугольной окрестности N, может рассматриваться как матрица m на n, где длины сторон являются нечетными числами. При задании ядра матрицей ее следует центрировать. Если пиксель (x, y) находится в окрестности краев изображения, то координаты A(x-i, y-j) для определенных (i, j) могут соответствовать несуществующим пикселям A за пределами изображения. Данную проблему можно разрешить несколькими способами.

Не проводить фильтрацию для таких пикселей, обрезав изображение B по краям, или применив для их значений исходные значения изображения А.

Не включать отсутствующий пиксель в суммирование, распределив его вес h(i, j) равномерно среди других пикселей окрестности N(x, y).

Доопределить значения пикселей за границами изображения при помощи экстраполяции.

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

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

Сглаживающие фильтры. Простейший прямоугольный сглаживающий фильтр радиуса r задается при помощи матрицы размера (2r+1) × (2r+1), все значения которой равны 1/(2r+1)2, а сумма значений равна единице. Это двумерный аналог низкочастотного одномерного П-образного фильтра скользящего среднего. При фильтрации с таким ядром значение пикселя заменяется усредненным значением пикселей в квадрате со стороной 2r+1 вокруг него. Пример маски фильтра 3× 3:

.

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

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

.

Более эффективное шумоподавление можно осуществить, если влияние пикселей на результат будет уменьшаться с увеличением расстояния от обрабатываемого. Этим свойством обладает гауссовский фильтр с ядром: h(i, j) = (1/2ps2) exp(-(i2+j2)/2s2). Гауссовский фильтр имеет ненулевое ядро бесконечного размера. Однако значения ядра фильтра очень быстро убывает к н), и потому на практике можно ограничиться сверткой с окном небольшого размера вокруг (0, 0), например, взяв радиус окна равным 3σ.

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

Контрастоповышающие фильтры . Если сглаживающие фильтры снижают локальную контрастность изображения, размывая его, то контрастоповышающие фильтры производят обратный эффект и, по существу, являются фильтрами высоких пространственных частот. Ядро контрастоповышающего фильтра в точке (0, 0) имеет значение, большее 1, при общей сумме значений, равной 1. Например, контрастоповышающими фильтрами являются фильтры с ядром, задаваемым матрицами:

. .

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

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

Простейшим дифференциальным оператором является взятие производной по x-координате d/dx, который определен для непрерывных функций. Распространенными вариантами аналогичных операторов для дискретных изображений являются фильтры Прюита (Prewitt) и Собеля (Sobel):

. .

Фильтры, приближающие оператор производной по y-координате d/dy, получаются путем транспонирования матриц.

Простейший алгоритм вычисления нормы градиента по трем смежным точкам:

G(x, y) =.

Применяется также упрощенная формула вычислений:

Вычисление нормы градиента по четырем смежным точкам (оператор Робертса):

В алгоритме Собеля используется восемь отсчетов яркости в окрестностях центральной точки:

G(x, y) =, G(x, y) @ ,

Gxx, y = - ,

Gyx, y = - .

Наряду с более точным определением нормы градиента алгоритм Собеля позволяет определять и направление вектора градиента в плоскости анализа изображения в виде угла j между вектором градиента и направлением строк матрицы:

j(x, y) = argtg(Gyx, y /Gxx, y).

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

Аналогично вышеприведенным фильтрам, по методу конечных разностей можно составить фильтры для других дифференциальных операторов. В частности, важный для многих приложений дифференциальный оператор Лапласа (лапласиан) D= 𝝏2/𝝏x2 + 𝝏2/𝝏y2 можно приблизить для дискретных изображений фильтром с матрицей (один из вариантов):

.

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

Однако такой алгоритм имеет существенные недостатки. Главный из них - неопределенность в выборе величины порога. Для разных частей изображения приемлемый результат обычно получается при существенно разных пороговых значениях. Кроме того, разностные фильтры очень чувствительны к шумам изображения.

Двумерная циклическая свертка. Как и для одномерных сигналов, двумерная свертка может выполняться в области пространственных частот с использованием алгоритмов быстрого преобразования Фурье и перемножением двумерных спектров изображения и ядра фильтра. Она также является циклической, и выполняется обычно в скользящем варианте. С учетом цикличности, для вычисления постоянного шаблона спектра ядра размеры маски фильтра ядра удваиваются по осям и дополняются нулями, и эти же размеры маски используются для выделения скользящего по изображению окна, в пределах которого и выполняется БПФ. Реализация КИХ фильтра с помощью БПФ особенно эффективна, если фильтр имеет большую опорную область.

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

Введем понятие M-окрестности элемента изображения A(x, y), который является для этой окрестности центральным. В простейшем случае M-окрестность содержит N-пикселей – точки, попадающие в маску фильтра, включая (или не включая) центральный. Значения этих N-элементов можно расположит в вариационном ряду V(r), ранжированном по возрастанию (или убыванию), и вычислить определенные моменты этого ряда, например, среднее значение яркости mN и дисперсии dN. Вычисление выходного значения фильтра, которым заменяется центральный отсчет, выполняется по формуле:

B(x, y) = aА(x, y) + (1-a)mN. (17.3.2)

Значение коэффициента a = связывается определенной зависимостью со статистикой отсчетов в окне фильтра, например:

a = dN /(dN + k dS), (17.3.3)

где dS – дисперсия шумов по изображению в целом или по S-окрестности при S > M и MÎS, k - константа доверия дисперсии S-окрестностей. Как следует из этой формулы, при k=1 и dN » dS имеет место a » 0.5, а значение B(x, y) = (А(x, y) + mN)/2, т. е. складываются в равной степени от значений центрального отсчета и среднего значения пикселей его M-окрестности. При увеличении значений dN происходит увеличение вклада в результат значения центрального отсчета, при уменьшении – значения mN. Весомость вклада средних значений по M-окрестности можно изменять значением коэффициента k.

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

Наиболее простыми и распространенными типами нелинейных фильтров для обработки изображений являются пороговые и медианные фильтры.

Пороговая фильтрация задается, например, следующим образом:

B(x, y) =

Величина p является порогом фильтрации. Если величина центральной точки фильтра превышает среднее значение отсчетов mN в ее М-окрестности на величину порога, то она заменяется средним значением. Значение порога может быть как константой, так и функционально зависимым от величины центральной точки.

Медианная фильтрация определяется следующим образом:

B(x, y) = med {M(x, y)},

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

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

Фильтры экстремумов определяются по правилам:

Bmin(x, y) = min {M(x, y)},

Bmax(x, y) = max {M(x, y)},

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

17.4. СЖАТИЕ ИЗОБРАЖЕНИЙ

Типичное изображение с разрешением порядка 3000×2000 при 24 бит на пиксель для передачи цвета имеет объем 17 мегабайт. Для профессиональных устройств размер получаемого растра изображений может быть значительно больше, глубина цвета до 48 бит на пиксель, а размер одного изображения может быть больше 200 мегабайт. Поэтому весьма актуальными являются алгоритмы сжатия изображений для уменьшения объема данных, представляющих изображение.

Существуют два основных класса алгоритмов:

1. Сжатие без потерь А (lossless compression), если существует такой обратный алгоритм A-1, что для любого h - изображения A[h] = h1 имеем A-1 = h. Сжатие без потерь применяется в таких графических форматах представления изображений, как: GIF, PCX, PNG, TGA, TIFF, и применяется при обработке особо ценной первичной информации (медицинские изображения, аэро- и космоснимки и т. п.), когда даже малейшие искажения нежелательны

2. Сжатие c потерями (lossy compression), если оно не обеспечивает возможность точного восстановления исходного изображения. Парный к A алгоритм примерного восстановления изображения будем обозначать как A*. Пара (A, A*) подбирается так, чтобы обеспечить большие коэффициенты сжатия при сохранении визуального качества. Сжатие с потерями применяется в графических форматах: JPEG, JPEG2000 и т. д.

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

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

Битовый уровень. Будем рассматривать исходные данные на уровне последовательности битов, например, представляющих черно-белое изображение. Подряд обычно идет несколько 0 или 1, и кодировать можно количество идущих подряд одинаковых цифр. Но количество повторений также надо кодировать битами. Можно считать, что каждое число повторений изменяется от 0 до 7 (3-х битовый код), чередуя последовательность кодов единиц и нулей. Например, последовательности можно сопоставить числа 7 0 4, т. е. 7 единиц, 0 нулей, 4 единицы, при этом имеем новый год – Чем больше длина последовательностей одинаковых бит, тем больше эффект. Так, последовательность из 21 единицы, 21 нуля, 3 единиц и 7 нулей закодируется так: , т. е. из исходной последовательности длиной 51 бит, имеем последовательность длиной 36 бит.

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

Будем разбивать входной поток на байты (код от 0 до 255) и кодировать повторяющиеся байты парой (количество, буква). Одиночный байт можно не изменять. Так, байты AABBBCDAA кодируем (2A) (3B) (C) (D) (2A).

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

Словарные алгоритмы вместо кодирования только по одному элементу входящей последовательности производят кодирование цепочки элементов. При этом используется словарь цепочек (созданный по входной последовательности) для кодирования новых.

Алгоритм LZ77 был одним из первых, использующих словарь. В качестве словаря используются N последних уже закодированных элементов последовательности. В процессе сжатия словарь-подпоследовательность "скользит" по входящей последовательности. Цепочка элементов на выходе кодируется следующим образом: положение совпадающей части обрабатываемой цепочки элементов в словаре - смещение (относительно текущей позиции), длина, первый элемент, следующий за совпавшей частью цепочки. Длина цепочки совпадения ограничивается сверху числом n. Соответственно, задача состоит в нахождении наибольшей цепочки из словаря, совпадающей с обрабатываемой последовательностью. Если же совпадений нет, то записывается нулевое смещение, единичная длина и первый элемент незакодированной последовательности.

Описанная выше схема кодирования приводит к понятию скользящего окна (sliding window), состоящего из двух частей:

Подпоследовательность уже закодированных элементов длины N-словарь - буфер поиска (search buffer);

Подпоследовательность длины n из цепочки элементов, для которой будет произведена попытка поиска совпадения - буфер предварительного просмотра (look-ahead buffer).

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

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

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

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

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

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

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

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

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

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

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

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

Некоррелированность и независимость коэффициентов спектра, т. е. точность представления одного коэффициента не зависит от любого другого.

- "Уплотнение" энергии (energy compaction). Преобразование сохраняет основную информацию в малом количестве коэффициентов. Данное свойство сильнее всего проявляется на фотореалистичных изображениях.

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

Алгоритм сжатия, используемый в формате JPEG, построен на использовании дискретного косинусного преобразования Фурье. Схема сжатия в алгоритме представляет собой конвейер, где это преобразование - лишь одна из стадий, но одна из основных. Алгоритм содержит следующие основные операции:

1. Перевод в цветовое пространство YCbCr. Здесь Y - компонента яркости, Cb и Cr - компоненты цветности. Человеческий глаз более чувствителен к яркости, чем к цвету. Поэтому важнее сохранить большую точность при передаче Y, чем при передаче Cb и Cr.

2. Дискретное косинус-преобразование (ДКП). Изображение разбивается на блоки 8 × 8. К каждому блоку применяется дискретное косинус-преобразование (отдельно для компонент Y, Cb и Сr).

3. Сокращение высокочастотных составляющих в матрицах ДКП. Человеческий глаз практически не замечает изменения в высокочастотных составляющих, следовательно, коэффициенты, отвечающие за высокие частоты, можно хранить с меньшей точностью.

4. Зигзаг-упорядочивание матриц. Это особый проход матрицы для получения одномерной последовательности. Сначала идет элемент T00, затем T01, T10, T1Причем для типичных фотореалистических изображений сначала будут идти ненулевые коэффициенты, соответствующие низкочастотным компонентам, а затем - множество нулей (высокочастотные составляющие).

5. Сжатие сначала методом RLE, а затем методом Хаффмена.

Алгоритм восстановления изображения действует в обратном порядке. Степень сжатия от 5 до 100 и более раз. При этом визуальное качество для большинства фотореалистичных изображений остается на хорошем уровне при сжатии до 15 раз. Алгоритм и формат являются самыми распространенными для передачи и хранения полноцветных изображений.

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

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

литература

46. и др. Быстрые алгоритмы в цифровой обработке изображений. – М.: Радио и связь, 1984. – 224 с.

47. Сойфер обработка изображений. Часть 2. Методы и алгоритмы. – Соросовский образовательный журнал №3, 1996.

48. , Хрящев шума из изображений на основе нелинейных алгоритмов с использованием ранговой статистики. - Ярославский государственный университет, 2007.

49. Андреев телевизионные системы наблюдения. Часть II. Арифметико - логические основы и алгоритмы. Учебное пособие. - СПб: СПб, ГУИТМО, 2005. – 88с.

51. Введение в цифровую обработку сигналов (Математические основы).- М.: МГУ, Лаборатория компьютерной графики и мультимедиа, 2002. – http://pv. *****/dsp/dspcourse. pdf, http://dsp-book. *****/dspcourse. djvu, http://geogin. *****/arhiv/dsp/dsp4.pdf.

1i. и др. Алгоритмические основы растровой графики. – Интернет университет информационных технологий . – http://www. *****/goto/course/rastrgraph/

2i. Лукин -электронные системы: Конспект лекций. ИТМО, 2004. – СПб, ИТМО ИФФ, 2004. - http://iff. *****/kons/oes/KL. htm

О замеченных ошибках и предложениях по дополнению: *****@***ru.

Copyright ©2008 Davydov А. V .

Лабораторная работа № 1

Алгоритмы обработки изображений

Операция свертки

Свертка - это алгоритм очень широкого применения, который можно использовать как для предварительной обработки изображения, так и для распознавания и идентификации объектов. Пусть изображение задается двумерной матрицей яркостей F " , а импульсная характеристика матрицей H . Математически свертку матрицы F с ядром H можно определить следующей формулой:

где M2xN2 - размер матрицы ядра свертки. Размер матрицы F равен (M1+M2-1)x(N1+N2-1), где M1xN1 - размер исходной матрицы F " . Матрица F получается из исходной путем добавления элементов на краях матрицы по некоторому правилу с тем, чтобы привести ее к необходимому размеру. Обычно исходная матрица на краях дополняется нулями на половину ширины матрицы H влево и вправо и соответственно на половину высоты вверх и настолько же вниз. Тогда размер полученной матрицы R будет таким же, как и у матрицы F " .

Свертку можно вычислять непосредственно "пробеганием" одной матрицы по другой, как уже было показано выше. На рис. 1 показана схема вычисления свертки (размер матрицы маски взят равным 3х3). Оператор свертки можно рассматривать как матрицу коэффициентов (масок), которые поэлементно умножаются с выделенным фрагментом изображения с последующим суммированием для получения нового значения элемента отфильтрованного изображения. Эта матрица может быть произвольного размера, необязательно квадратная.

Рис. 1. Реализация операции свертки.

Задание

Реализовать алгоритм, выполняющий операцию свертки исходного изображения с матрицей-маской.

Размер и вид матрицы-маски задаются пользователем.

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

• для сглаживания и подавления шумов в изображении используют матрицу-маску размером 3х3 следующего вида:

для подчеркивания контуров используются матрицы-маски следующего вида:

1/9*

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

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

5. Реализовать алгоритм тиснения. Тиснение делается аналогично алгоритмам усреднения или подчеркивания контуров. Каждый пиксел в изображении обрабатывается ядром (матрицей-маской) тиснения размером 3х3. Например, в качестве ядра тиснения можно взять следующую матрицу-маску:

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

В тисненом варианте изображения контуры кажутся выдавленными над поверхностью. Направление подсветки изображения можно изменять, меняя позиции 1 и -1 в ядре. Если, например, поменять местами значения 1 и -1, то реверсируется направление подсветки.

6. Акварелизация изображения. Акварельный фильтр преобразует изображение, и после обработки оно выглядит так, как будто написано акварелью:

первый шаг в применении акварельного фильтра - сглаживание цветов в изображении. Одним из способов сглаживания является применение медианнного усреднения цвета в каждой точке. Значение цвета каждого пиксела и его 24 соседей (размер матрицы-маски равен 5х5) выстраиваются в вариационный ряд по убыванию или возрастанию. Медианное (тринадцатое) значение цвета в вариационном ряде присваивается центральному пикселу.

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

Представление изображений

Существуют два основных вида представлений изображений – векторное и растровое.

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

Растровое изображение представляет собой одну или несколько матриц, описывающих пространственное распределение характеристик изображения на некоторой декартовой координатной сетке. В этом случае изображение строится из множества точек и имеет структуру растра. Основным элементом растрового представления изображения является пиксел (сокращение от словосочетания «picture elements» - элементы изображения), имеющий координаты в растровой системе координат и некоторые атрибуты (цвет, яркость, прозрачность и т.п.). Число пикселей по координатам X и Y (по горизонтали и вертикали) задает разрешение (размерность) представления изображения. Цвет пиксела задается глубиной – количеством битов, необходимым для задания любого цвета.

Растровые изображения, в зависимости от методов задания цвета пиксела и свойств исходного изображения подразделяются на:

Бинарные

Полутоновые

Палитровые

Полноцветные

В бинарном представлении цвет пиксела может быть либо белым, либо черным и кодируется одним битом. Изображение представляет собой матрицу. Каждый элемент I (i , j ) этой матрицы имеет значение либо 0 либо 1, где i - номер строки, а - номерj столбца элемента, соответствующего заданному пикселю (рис. 1).

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

– задает его яркостьI (i , j ) (рис. 2).

Палитровые изображения описываются двумя матрицами (рис. 3). Одна хранит значения индексов, которые задают обращение к строке матрицы палитр. Матрица палитр это цветовая карта. Она содержит 3 группы столбцов – соответствующих красному «R», зеленому «G» и синему «B» цветам. Они и задают цвет соответствующего пиксела.

Палитра это матрица размерностью Nc 3 , где Nc - количество цветов.

Алгоритмы предварительной обработки изображений

Полноцветные изображения – строятся в формате RGB и представляют собой три матрицы R (i , j ), G (i , j ), B (i , j ) . Соответствующие элементы каждой матрицы содержат значения интенсивностей красного, зеленого и синего цветов для пиксела задаваемого индексами матриц. Таким образом полноцветное изображение не имеет цветовой карты и цвет каждого пиксела представляется тремя числами, взятыми из соответствующих матриц (рис. 4).

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

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

Для полноцветных изображений одним из параметров является максимальное количество цветов, которое может быть представлено в этом формате. Наиболее часто используются изображения, имеющие 16, 256, 65536 (High Color) и 10.7 миллиона (True Color) цветов.

Алгоритмы предварительной обработки изображений

Алгоритмы предварительной обработки изображений

Матрица индексов

31 15 03 09

Матрица палитры

Алгоритмы предварительной обработки изображений

Полноцветное изображение может быть представлено не только в формате RGB, но и с помощью других цветовых систем.

В системе HSB цвет представляется следующими цветовыми характеристиками: Hue – цветовой тон;

Saturation – насыщенность; Brightness – яркость.

Считается, что эта цветовая система соответствует особенностям человеческого восприятия цвета.

В системе LAB цвет рассматривается как совокупность яркости (lightness) и двух независимых значений цветности, которые и определяют истинный цвет пиксела. Цветность A – цветовая составляющая выбирается в диапазоне от пурпурного до зеленого. Цветность B - вторая цветовая составляющая выбирается из диапазона от желтого до голубого.

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

Алгоритмы предварительной обработки изображений

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

Классификация алгоритмов предварительной обработки

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

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

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

Алгоритмы выполняющие геометрические операции с изображение называются алгоритмами геометрической обработки . К ним относятся:

Алгоритмы предварительной обработки изображений

– Кадрирование изображение – выделение из исходного изображения некоторой части прямоугольной формы;

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

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

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

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

Алгоритмы предварительной обработки изображений

Алгоритмы пространственной фильтрации

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

m N11 n N21

Im, If матрицы исходного и отфильтрованного изображений, h матрица импульсной характеристики фильтра,

N 11 , N 21 нижняя и верхняя границы столбцов импульсной характеристики, N 12 , N 22 левая и правая границы рядов импульсной характеристики.

Матрица импульсной характеристики может быть получена при расчете пространственного фильтра исходя из заданных параметров. Методам расчета пространственных фильтров посвящено большое количество литературы посвященной цифровой фильтрации, например . Для практических расчетов можно использовать стандартные математические пакеты, например в состав системы “MATLAB” входит система расчета фильтров “Image Filter Design”.

Отметим, что фильтрацию можно проводить и в частотной области. В этом

Алгоритмы предварительной обработки изображений

случае порядок фильтрации следующий:

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

Осуществить поэлементное умножение частотной матрицы изображения на частотную матрицу фильтра

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

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

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

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

1) предварительная обработка изображения;

2) сегментация;

3) описание.

Предварительная обработка, в свою очередь, имеет две базовые стадии: формирование изображения и его кодирование (сжатие). Последователь­ность этапов не является жесткой и зависит от конкретной задачи.

Предварительная обработка изображения

Все методы предварительной обработки изображения в СТЗ подразде­ляют на пространственные и частотные. Пространственные методы являют­ся процедурами, оперирующими непосредственно с пикселями изображе­ния. В качестве характеристики изображения используется яркость У(х, у). Частотные методы связаны с переводом изображения в комплексную плос­кость с помощью преобразования Фурье.

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

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

В СТЗ на этапе формирования изображения выбирают порог яркости пу­тем регулирования освещения и проводят фильтрацию изображения.

Фильтрация изображения является наиболее длительной и сложной ста­дией предварительной обработки. В общем случае фильтрация решает следующие основные задачи:

· сглаживание (подавление высокочастотной помехи типа «снег»);

· повышение контрастности;

· выделение контура.

Процедура сглаживания реализуется сразу после выбора порога яркости. Ее смысл заключается в усреднении по определенному правилу значений функции яркости Y(X, у) внутри анализируемого фрагмента изображения.

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

Сегментация

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

Если априорно известно, что изображение содержит не­сколько объектов, процедура сегментации проводится после выделения контуров перед этапом кодирования изображения.

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

Кодирование изображения

Для систем, обрабатывающих полутоновые изо­бражения пространственными методами, различают два основных метода кодирования:

· кодирование собственно изображения методом кодов длин серий;

· кодирование контура изображения цепным кодом Фримана.

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

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

Для кодирования непосредственно контура изображения чаще всего применяют цепной код Фримана (рис. 6.22, б). В этом случае контур объек­та начиная с некоторой точки задается последовательностью векторов, принимающих дискретные значения, с углом наклона модуля, кратным 45. Значение модуля равно 2, если угол наклона вектора составляет 45 , и 1 при вертикальном или горизонтальном его положении. Изменение направления вектора при переходе от одной точки кривой к другой отражает ха­рактер изменения моделируемой кривой.

Описание изображения

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

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

Локальные признаки используют реже; они характеризуют не все изображение, а только часть его. К ним относятся угол между двумя контурными линиями, число и параметры отверстий на изображении объекта и т. п.

Распознавание изображения

Распознаванием называется процесс, при котором на основании набора признаков некоторого изображения объекта определяется его принадлеж­ность к определенному классу.

Распознавание реализует функцию анализа визуального образа .

Условно все методы распознавания можно разделить на две группы: теоретические и структурные. Наиболее распространенные теоретические методы распознавания используют принципы теории принятия решений.

Определить реальное значение признаков объекта невоз­можно, так как значения различаются при каждом измерении. Поэтому за­дача распознавания ставится так: определить вероятность того, что объект принадлежит к заданному классу.

Одно из наиболее интересных направлений распознавания образов в СТЗ связано с разработкой алгоритмов распознавания лиц. Алгоритм распознавания (верификации) близок к алгоритму регистра­ции. Выделенные из текущего изображения признаки объединяются в век­тор признаков, компоненты которого сравниваются с соответствующими компонентами всех векторов, содержащихся в базе данных.

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

Шум на видео может возникать по нескольким причинам :

1. Неидеальное оборудование для захвата видео.

2. Плохие условия съемки - например, ночная фото/видеосъемка, съемка в ненастную погоду.

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

4. Неточности фильтрации при выделении яркостного и цветоразностных сигналов из аналогового композитного сигнала и т. п.

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

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

Белый Гауссовский шум

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

Цифровой шум

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

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

Комбинированный шум

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

Дефекты сканирования изображений

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

Алгоритмы удаления шума

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

Рассмотрим несколько наиболее известных алгоритмов подавления шума на изображениях.

Линейное усреднение пикселей

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

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

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

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

Фильтр Гаусса

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

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

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

Отсюда следует, что свертку можно производить последовательно по строкам и по столбцам, что приводит к значительному ускорению работы метода при больших размерах фильтра.

Алгоритм 2Dcleaner

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

Медианная фильтрация

Линейные алгоритмы оказываются очень эффективными при подавлении помех гауссовского характера, когда соседние пиксели хоть и имеют некоторый случайный разброс значений, но все же остаются в пределах некоторого среднего значения, характерного для области, к которой они принадлежат. Однако порой приходится иметь дело с изображениями, искаженными другими видами помех. Примером такой помехи является импульсный шум, проявляющийся в наличии на изображении хаотично разбросанных точек случайной яркости. Усреднение в этом случае “размазывает” каждую такую точку на соседние пиксели, приводя к ухудшению качества изображения.

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

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

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

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

Повышение резкости изображения

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

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

Рисунок 5.1 - Иллюстрация понятия «резкость контура»

Резкость изображения зависит от величины перепада яркости между областями (W), образующими его контуры, и от резкости изменения этого перепада (H).

Прием нерезкого маскирования был впервые применен еще для обработки пленочных фотографий . Приспособленный к цифровой обработке изображений метод мало отличается от оригинального: из изображения вычитается так называемая “нерезкая маска” - его размытая и инвертированная копия. Итогом становится новое изображение, содержащее только светлые контуры оригинала. Темные контуры можно получить простым инвертированием результата.

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

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

Рисунок 5.2 - Результат применение нерезкого маскирования

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

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

Главным элементом свертки является маска свертки - это матрица (произвольного размера и отношения сторон). Часто такую маску называют фильтром, ядром, шаблоном или окном. Значения элементов матрицы принято называть коэффициентами.

Чаще всего в качестве ядра свертки используется квадратная матрица.

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

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

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

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

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

Компенсация разности освещения

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

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

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

Алгоритм Single Scale Retinex

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

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

Этим требованиям удовлетворяет алгоритм Single Scale Retinex, основанный на принципах устройства рецепторов сетчатки глаза. Основная цель алгоритма - разделить изображение на компоненты, отвечающие отдельно за освещенность и детали. Так как проблемы в изображении связаны с освещением сцены, то, получив компоненту, отвечающую за освещение, становится возможным преобразовать её отдельно от изображения, тем самым значительно повысив его качество.

Любое изображение можно представить, как произведение высокочастотного сигнала (отражение - R) и низкочастотного сигнала (освещенность - I) .

S(x,y) = I(x,y) * R(x,y)(5.6)

Рисунок 5.3 - Представление изображения в алгоритме Retinex.

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

где G -- Гауссовский фильтр

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

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

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

Гамма-коррекция

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

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

где I -- яркость пиксела на экране дисплея (или яркости составляющих цвета, красной, зелёной и синей по отдельности),

V -- численное значение цвета от 0 до 1, а

г -- показатель гамма-коррекции .

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

По умолчанию параметр г равен 1, что соответствует линейной характеристике передачи уровней и отсутствию гамма - коррекции.

Выделение контуров изображения

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

Рисунок 5.4 - Изменение вида степенной функции в зависимости от параметра г

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

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

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

Фильтр Собеля применяется последовательно к каждому пикселю, вычисляя приближенное значение градиента его яркости. Градиент для каждой точки изображения (функция яркости) -- это двумерный вектор, компонентами которого являются производные яркости изображения по горизонтали и вертикали .

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

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

Для вычисления приближенных значений производных в каждой точке изображения фильтр Собеля использует свертку с матрицей размером 3Ч3.

Коэффициенты матрицы Собеля :

Итоговая величина градиента вычисляется путем аппроксимируции по формуле:

|G| = |Gx| + |Gy|

Детектор границ Кенни

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

1. Очистка изображения от шума и лишних деталей.

2. Очистка изображения от шума и лишних деталей.

3. Поиск градиентов изображения, к примеру, оператором Собеля.

4. Подавление не-максимумов. Только локальные максимумы отмечаются как границы.

5. Двойная пороговая фильтрация. Потенциальные границы определяются порогами.

6. Трассировка контуров (Связать края в контуры)

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

Угол направления границы округляется до одной из четырех углов, представляющих вертикаль, горизонталь и две диагонали (например, 0, 45, 90 и 135 градусов). Границами объявляются только те пиксели, в которых достигается локальный максимум градиента в направлении вектора градиента. Значение направления должно быть кратно 45°. После подавления не-максимумов, края становятся более точными и тонкими.

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

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

Сегментация

Большая часть изображений, получаемых с фото- и видеоаппаратуры являются растровыми, то есть состоящими из цветных точек, расположенных в виде прямоугольной сетки. Однако люди воспринимают окружающий мир как совокупность цельных объектов, а не матрицу из точек. Человеческий мозг способен объеденить разрозненные детали изображения в однородные области, на подсознательном уровне четко разделив его на объекты. Этот процесс называется сегментацией, и может быть реализован программно при решении задачи компьютерного анализа изображения и распознавания образов. Сегментация выполняется на первых этапах анализа, и качество её выполнения может оказать сильное влияние на его скорость и точность.

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

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

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

§ однородность регионов (однородность цвета или текстуры);

§ непохожесть соседних регионов;

§ гладкость границы региона;

§ маленькое количество мелких «дырок» внутри регионов ;

Пороговая сегментация

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

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

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

где x0 - единственный параметр обработки, называемый порогом. Уровни выходной яркости y0 и y1, могут быть произвольными, они лишь выполняют функции меток, при помощи которых осуществляется разметка получаемой карты - отнесение ее точек к классам К1 или К2 соответственно. Если образуемый препарат подготавливается для визуального восприятия, то часто их значения соответствуют уровням черного и белого. Если существует более двух классов, то при пороговой обработке должно быть задано семейство порогов, отделяющих яркости различных классов друг от друга.

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

Сегментация основанная на разбиении графа

Методы теории графов - одно из наиболее активно развивающихся направлений в сегментации изображений.

Общая идея методов этой группы следующая. Изображение представляется в виде взвешенного графа, с вершинами в точках изображения. Вес ребра графа отражает сходство точек в некотором смысле (расстояние между точками по некоторой метрике). Разбиение изображения моделируется разрезами графа .

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

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

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

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

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

Интерполяция методом ближайшего соседа

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

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

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

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

Бикубическая интерполяция идёт на один шаг дальше билинейной, рассматривая массив из 4x4 окружающих пикселей -- всего 16. Поскольку они находятся на разных расстояниях от неизвестного пикселя, ближайшие пиксели получают при расчёте больший вес. Бикубическая интерполяция производит значительно более резкие изображения, чем предыдущие два метода, и возможно, является оптимальной по соотношению времени обработки и качества на выходе. По этой причине она стала стандартной для многих программ редактирования изображений (включая Adobe Photoshop), драйверов принтеров и встроенной интерполяции камер .

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

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

5.2 Обоснование выбора алгоритмов, используемых в подсистеме

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

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

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

1. Для удаление “аддитивного белого” шума был выбран алгоритм Гаусса. Как наиболее расространенный метод шумоподавления он очень хорошо оптимизирован и соответственно обладает высокой скорость работы

2. Для удаление “аддитивного белого” шума был выбран алгоритм Гаусса. Как наиболее распространенный метод шумоподавления он очень хорошо оптимизирован и соответственно обладает высокой скорость работы

3. Для удаления “импульсного” шума была выбрана медианная фильтрация. Данный метод так же хорошо оптимизирован, кроме того он был разработан специально для устранения импульсного шума и шума вида «соль и перец»

4. Для повышения резкости изображения была выбрана свертка, так как она работает гораздо быстрее нерезкого маскирования, вместе с тем давая приемлемые результаты.

5. Библиотека OpenCV не содержит алгоритмов цветокоррекции - поэтому решено было реализовать наиболее распространенный и хорошо документированный алгоритм Single Scale Retinex. Данный метод обладает очень высокой эффективностью, но требует оптимизации для ускорения скорости работы.

6. В качестве метода выделение контуров был выбран алгоритм Кенни, так как он дает более качественные результаты, чем фильтр Собеля.

7. Алгоритм пирамидальной сегментации, представленный в библиотеке OpenCV работает крайне медленно, поэтому решено было использовать рассмотренный ранее алгоритм сегментации на графах.

8. интерполяция - выбран метод бикубической интерполяции как самый разумный компромисс между скоростью работы и качеством результата.

Установка и конфигурирование используемых программных средств.

На используемом вычислительном кластере была установлена система GNU Linux (Ubuntu)

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

Установка CMake

Сборка проекта осуществляется с помощью CMake (требуется версия 2.6 или выше). Установить ее можно командой:

apt-get install cmake

Так же могут понадобиться следующие библиотеки:

build-essential libjpeg62-dev libtiff4-dev libjasper-dev libopenexr-dev libtbb-dev libeigen2-dev libfaac-dev libopencore-amrnb-dev libopencore-amrwb-dev libtheora-dev libvorbis-dev libxvidcore-dev

Установка ffmpeg

Чтобы opencv мог корректно обрабатывать видео-файлы, необходимо установить библиотеку ffmpeg. Это делается следующими командами:

1) Скачивание исходных кодов библиотеки

wget http://ffmpeg.org/releases/ffmpeg-0.7-rc1.tar.gz

2) Распаковка архива с исходными кодами

tar -xvzf ffmpeg-0.7-rc1.tar.gz

3) Конфигурация библиотеки

configure --enable-gpl --enable-version3 --enable-nonfree --enable-postproc

Enable-libfaac --enable-libopencore-amrnb --enable-libopencore-amrwb

Enable-libtheora --enable-libvorbis --enable-libxvid --enable-x11grab

Enable-swscale --enable-shared

4) Сборка и установка библиотеки

установка GTK

Для отображения окон OpenCV требуется установленная библиотека GTK+ 2.x или выше, в том числе заголовочные файлы (libgtk2.0-dev)

apt-get install libgtk2.0-dev

Установка Opencv

После установки всех сопутствующих библиотек установка opencv2.2 выполняется следующими командами:

1) Скачивание исходных кодов библиотеки OpenCV

http://downloads.sourceforge.net/project/opencvlibrary/opencv-unix/2.2/OpenCV-2.2.0.tar.bz2

2) Распаковывание архива с исходными кодами

tar -xvf OpenCV-2.2.0.tar.bz2

3) генерация Makefile с помощью CMake.

4) сборка и установка библиотеки OpenCV

5) Так же может понадобиться прописать путь к библиотекам

export LD_LIBRARY_PATH=/usr/local/lib:$LD_LIBRARY_PATH

Установка и компиляция разработанного пакета программ

Необходимо скопировать исходные коды программ с диска, прилагаемого к данной пояснительной записке. В ту же папку необходимо скопировать и пакетный файл build_all.sh, а затем запустить его. Если в системе установлен компилятор gcc, сборка произойдет автоматически.