Обработка двумерных цифровых сигналов

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 23:40, 17 ноября 2016.


Содержание

Введение

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

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

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

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

Графическое представление изображений

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

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

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

где - область пикселя,
- атрибут пикселя (как правило, цвет).

Чаще всего используются два вида атрибутов:

- интенсивность (яркость) пикселя;
- цветовые атрибуты в цветовой модели RGB.

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

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

Рис. 1.1.

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

Представление цвета в машинной графике

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

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

Рис. 1.2.

Цветовая модель RGB

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

  • черного цвета: ;
  • фиолетового цвета ;
  • белого цвета .

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

Рис. 1.3.

Цветовая система CIE XYZ

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

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

Области и этапы преобразований

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

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

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

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

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

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

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

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

Дискретизация

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

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

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

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

где и - горизонтальный и вертикальный интервалы дискретизации двумерного непрерывного сигнала с непрерывными координатами и .

Ниже значения и , как и в одномерном случае, принимаются равными 1.

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

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

Рис. 2.1. Периодизация спектра

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

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

Интерполяционный ряд восстановления двумерного сигнала

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

при

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

Частотные искажения изображений и их устранение

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

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

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

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

Рис. 2.2.

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

Рис. 2.3. Примеры весовых функций.
Таблица 2.1.

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

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

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

Передискретизация изображения

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

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

Допустим, мы имеем одномерный сигнал (рис. 2.4), заданный на интервале и дискретизированный с шагом ( интервалов). Нужно «растянуть» сигнал в раз. Спектр сигнала, показанный на рисунке, вычисляется быстрым преобразованием Фурье (БПФ, количество отсчетов спектра равно количеству отсчетов сигнала) и приводится в главном диапазоне БПФ (, частота Найквиста , или по нумерации отсчетов спектра при шаге по спектру или ). Для выполнения растяжения необходимо выполнить 2 шага.

Рис. 2.4.

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

Рис. 2.5.

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

Рис. 2.6.

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

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

Фильтрация изображений

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

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

Линейные фильтры

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

Результатом служит изображение B. Обычно ядро фильтра отлично от нуля только в некоторой окрестности точки . За пределами этой окрестности равно нулю, или очень близко к нему и можно им пренебречь. Суммирование производится по , и значение каждого пикселя определяется пикселями изображения , которые лежат в окне , центрированном в точке (обозначение - множество ). Ядро фильтра, заданное на прямоугольной окрестности , может рассматриваться как матрица на , где длины сторон являются нечетными числами. При задании ядра матрицей ее следует центрировать. Если пиксель находится в окрестности краев изображения, то координаты для определенных могут соответствовать несуществующим пикселям за пределами изображения. Данную проблему можно разрешить несколькими способами: Не проводить фильтрацию для таких пикселей, обрезав изображение B по краям, или применив для их значений исходные значения изображения А.

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

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

Сглаживающие фильтры

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

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

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

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

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

Контрастоповышающие фильтры

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

Рис. 3.1.

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

Разностные фильтры

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

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

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

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

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

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

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

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

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

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

Рис. 3.2.

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

Двумерная циклическая свертка

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

Нелинейные фильтры

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

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

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

где – дисперсия шумов по изображению в целом или по -окрестности при и ,
- константа доверия дисперсии S-окрестностей.

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

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

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

Пороговая фильтрация

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

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

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

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

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

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

Фильтры экстремумов

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

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

Сжатие изображений

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

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

  1. Сжатие без потерь А (lossless compression), если существует такой обратный алгоритм , что для любого - изображения имеем . Сжатие без потерь применяется в таких графических форматах представления изображений, как: GIF, PCX, PNG, TGA, TIFF, и при-меняется при обработке особо ценной первичной информации (медицинские изображения, аэро- и космоснимки и т.п.), когда даже малейшие искажения нежелательны
  2. Сжатие c потерями (lossy compression), если он не обеспечивает возможность точного восстановления исходного изображения. Парный к алгоритм примерного восстановления изображения будем обозначать как . Пара подбирается так, чтобы обеспечить большие коэффициенты сжатия при сохранении визуального качества. Сжатие с потерями применяется в графических форматах: JPEG, JPEG2000 и т.д.

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

Алгоритмы кодирования длины повторения (RLE)

Алгоритмы кодирования длины повторения (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

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

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

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

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

Алгоритм LZW

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

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

Алгоритмы статистического кодирования

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

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

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

Сжатие изображений с потерями

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

Оценка потерь в изображениях

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

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

Преобразование Фурье

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

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

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

Рис. 4.1.
  1. Перевод в цветовое пространство YCbCr. Здесь Y - компонента яркости, Cb и Cr - компоненты цветности. Человеческий глаз более чувствителен к яркости, чем к цвету. Поэтому важнее сохранить большую точность при передаче Y, чем при передаче Cb и Cr.
  2. Дискретное косинус-преобразование (ДКП). Изображение разбивается на блоки 8x8. К каждому блоку применяется дискретное косинус-преобразование (отдельно для компонент Y, Cb и Сr).
  3. Сокращение высокочастотных составляющих в матрицах ДКП. Человеческий глаз практически не замечает изменения в высокочастотных составляющих, следовательно, коэффициенты, отвечающие за высокие частоты, можно хранить с меньшей точностью.
  4. Зигзаг-упорядочивание матриц. Это особый проход матрицы для получения одномерной последовательности. Сначала идет элемент T00, затем T01, T10, T11 . . . Причем для типичных фотореалистических изображений сначала будут идти ненулевые коэффициенты, соответствующие низкочастотным компонентам, а затем - множество нулей (высокочастотные составляющие).
  5. Сжатие сначала методом RLE, а затем методом Хаффмена.

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

Вейвлет-преобразование

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

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

Литература

  1. Хуанг Т.С. и др. Быстрые алгоритмы в цифровой обработке изображений. – Москва: Радио и связь, 1984. – 224 с.
  2. Сойфер В.А. Компьютерная обработка изображений. Часть 2. Методы и алгоритмы. – Соросовский образовательный журнал №3, 1996.
  3. Апальков И.В., Хрящев В.В. Удаление шума из изображений на основе нелинейных алгоритмов с использованием ранговой статистики. - Ярославский государственный университет, 2007.
  4. Андреев А.Л. Автоматизированные телевизионные системы наблюдения. Часть II. Арифметико-логические основы и алгоритмы. Учебное пособие. - СПб: СПб, ГУИТМО, 2005. – 88с.

Ссылки

  1. «Лукин А. Введение в цифровую обработку сигналов (Математические основы).- Москва: МГУ, Лаборатория компьютерной графики и мультимедиа, 2002.»;
  2. Зеркало: «Лукин А. Введение в цифровую обработку сигналов (Математические основы).- Москва: МГУ, Лаборатория компьютерной графики и мультимедиа, 2002.»;
  3. Зеркало: «Лукин А. Введение в цифровую обработку сигналов (Математические основы).- Москва: МГУ, Лаборатория компьютерной графики и мультимедиа, 2002.»;
  4. «Иванов Д.В. и др. Алгоритмические основы растровой графики. – Интернет университет информационных технологий.»;
  5. «Лукин С.Б. Оптико-электронные системы: Конспект лекций. ИТМО, 2004. – СПб, ИТМО ИФФ, 2004.»;

См. также