ВВЕДЕНИЕ. Размах исследований в области цифровой обработки изображений стремительно нарастает

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

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

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

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

17.1. Основные понятия [1i]

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

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

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

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

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

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

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

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

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

M_ij = (A_ij, C_ij).

Рис. 17.1.1.

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

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

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

Рис. 17.1.2.

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

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

- черного цвета: f_black = 0, (R,G,B) = (0,0,0);

- фиолетового цвета f_violet = f_red + f_blue, (R,G,B) = (1,0,1);

- белого цвета f_white = f_red + f_green + f_blue, (R,G,B) = (1,1,1).

Рис. 17.1.3.

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

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

17.2. Геометрические преобразования растровых изображений [51, 1i]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

где Dx и Dy - горизонтальный и вертикальный интервалы дискретизации двумерного непрерывного сигнала s_a(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.1') и (17.2.2') являются одномерными ДПФ сечений функций s(n,m) и S(k,l) по линиям n и k соответственно, а первые - одномерными ДПФ вычисленных функций в сечениях по m и l. Другими словами, исходные матрицы значений s(n,m) и S(k,l) пересчитываются сначала в промежуточные матрицы с ДПФ по строкам (или по столбцам), а промежуточные - в окончательные с ДПФ по столбцам (или соответственно по строкам).

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

F_x ³ 2f_max.x, F_y ³ 2f_max.y, (17.2.3)

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

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

S_a(W_x,W_y) = 0 при |W_x| p/Dx, |W_y| p/Dx,

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

s_a(x,y) = S_n S_m 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.2.

На практике при этом обычно используются двумерные аналоги весовых функций, применяемых при обработке одномерных сигналов (Ганна, Хемминга, Гаусса и др.). Как правило, фильтры h(x', y') имеют либо радиальную, либо осевую симметрию. На рис. 17.2.2 приведен пример исходного изображения и изображения после выполнения префильтрации.

Рис. 17.2.3. Примеры весовых функций.

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

Таблица 17.2.1.

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

Временное окно	Весовая функция	Фурье-образ
Естественное (П)	П(t) = 1, |t|£t; П(t) = 0, |t|>t	П(w) = 2t sinc[wt]
Бартлетта (D)	b(t) = 1-|t|/t	B(w) = t sinc2(wt/2).
Хеннинга, Ганна	p(t) = 0.5[1+cos(pt/t)]	0.5П(w)+0.25П(w+p/t)+0.25П(w-p/t)
Хемминга	p(t) = 0.54+0.46 cos(pt/t)	0.54П(w)+0.23П(w+p/t)+0.23П(w-p/t)
Карре (2-е окно)	p(t) = b(t) sinc(pt/t)	t·B(w)*П(w), П(w) = 1 при |w|<p/t
Лапласа-Гаусса	p(t) = exp[-b2(t/t)2/2]	[(t/b) exp(-t2w2/(2b2))] ③ П(w)

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

f₂(x, y) = f₁(),

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

f₂(x, y) = f₁(x) × f₁(y).

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

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

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

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

Рис. 17.2.4.

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

Рис. 17.2.5.

Первый шаг – интерполяция нулями, увеличивающая длину сигнала в 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.

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

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

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

17.3. фильтрация изображений [49, 1i]

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

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

Линейные фильтры имеют очень простое математическое описание. Будем считать, что задано исходное полутоновое изображение 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)², а сумма значений равна единице. Это двумерный аналог низкочастотного одномерного П-образного фильтра скользящего среднего. При фильтрации с таким ядром значение пикселя заменяется усредненным значением пикселей в квадрате со стороной 2r+1 вокруг него. Пример маски фильтра 3× 3:

.

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

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

.

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

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

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

. .

Рис. 17.3.1.

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

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

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

. .

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

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

G(x, y) = .

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

G(x, y) @ .

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

G(x, y) = .

G(x, y) @ .

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

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

Gx_x,y= [A_x-1,y-1+2A_x-1,y+A_x-1,y+1] - [A_x+1,y-1+2A_x+1,y+A_x+1,y+1],

Gy_x,y = [A_x-1,y-1+2A_x,y-1+A_x+1,y-1] - [A_x-1,y+1+2A_x,y+1+A_x+1,y+1].

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

j(x, y) = argtg(Gy_x,y /Gx_x,y).

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

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

.

Рис. 17.3.2.

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

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

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

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

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

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

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

a = d_N /(d_N + k d_S), (17.3.3)

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

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

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

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

B(x, y) =

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

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

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

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

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

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

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

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

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

17.4. СЖАТИЕ ИЗОБРАЖЕНИЙ [1i]

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

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

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

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

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

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

Битовый уровень. Будем рассматривать исходные данные на уровне последовательности битов, например, представляющих черно-белое изображение. Подряд обычно идет несколько 0 или 1, и кодировать можно количество идущих подряд одинаковых цифр. Но количество повторений также надо кодировать битами. Можно считать, что каждое число повторений изменяется от 0 до 7 (3-х битовый код), чередуя последовательность кодов единиц и нулей. Например, последовательности 11111111111 можно сопоставить числа 7 0 4, т.е. 7 единиц, 0 нулей, 4 единицы, при этом имеем новый год – 111 000 100. Чем больше длина последовательностей одинаковых бит, тем больше эффект. Так, последовательность из 21 единицы, 21 нуля, 3 единиц и 7 нулей закодируется так: 111 000 111 000 111 111 000 111 000 111 011 111, т.е. из исходной последовательности длиной 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, T11... Причем для типичных фотореалистических изображений сначала будут идти ненулевые коэффициенты, соответствующие низкочастотным компонентам, а затем - множество нулей (высокочастотные составляющие).

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

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

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

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

литература

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

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

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

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

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

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

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

Поиск по сайту: