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

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

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

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

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

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

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

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

Задание

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

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

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

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

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

1/9*

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

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

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

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

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

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

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

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

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

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

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

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

3) описание.

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

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

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

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

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

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

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

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

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

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

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

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

Сегментация

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Бинарные

Полутоновые

Палитровые

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

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

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

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

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

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

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

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

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

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

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

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

	0 0 0 0 1 1 1 0 0	120 122 125 128 115 117 118
	1 0 0 0 1 1 1 1 0	119 121 124 125 128 130 133
	1 1 0 0 1 1 0 0 1	122 122 124 123 127 126 128
		120 121 123 125 127 125 126
	1 1 1 0 1 1 0 0 0
		118 110 109 108 108 109 110
	0 0 1 0 0 1 0 0 1

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

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

31 15 03 09

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

If (i, j)	Im(i m , j n )h (m , n ), где:

m N11 n N21

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

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

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

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

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

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

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

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

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

Im(x , y )	Im(f x , f y )	If (f x , f y ) Im(f x , f y ) H (f x , f y )	If (fx , f y )		If (x, y).

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

1

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

обработка изображения

нечеткая логика

интеллектуальная система

распознавание объектов

1. Веснин Е.Н., Вето А.В., Царев В.А. К вопросу о разработке и применении адаптивных оптоэлектронных систем технического зрения// Автоматизация в промышленности, 2009.- № 11.- С. 48-52.

2. Гришин В.А. Системы технического зрения в решении задач управления беспилотными летательными аппаратами // Датчики и системы, №2, 2009.- C. 46-52.

3. Клевалин В.А., Поливанов А.Ю. Цифровые методы распознавания в системах технического зрения промышленных роботов// Мехатроника, автоматизация, управление, 2008, № 5.- С. 56-56.

4. Михайлов С.В., Романов В.В., Заикин Д.А. Система технического зрения для диагностики процесса резания материалов// Вестник компьютерных и информационных технологий, 2007, № 3.- С. 12-19.

5. Семин М.С. Обзор решения прикладных задач с помощью систем технического зрения// http://www.videoscan.ru/page/718#13.

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

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

Алгоритм предварительной обработки изображения с помощью нечеткой системы в СТЗ

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

Рис. 1. Алгоритм предварительной нечеткой обработки изображения

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

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

где - новое значение цвета, - интенсивность красной составляющей цвета, - интенсивность зеленой составляющей цвета, а - интенсивность синей составляющей цвета. Выход каждого алгоритма оттенки серого между 0 и 1. Для преобразования изображений в использующие только оттеки серого существует некоторые методов. В методе определения светлоты используется среднее значение между двумя наиболее и наименее значимыми цветами: . В методе среднего используется среднее значение всех трёх цветов: . В методе определения яркости используется взвешенное среднее значение всех трех цветов, учитывающее человеческое восприятие. Так, поскольку человеческий глаз наиболее восприимчив к зеленому цвету, его вес считается наиболее важным: . Метод определения яркости используется программное обеспечение для обработки изображений. Он реализован функцию « rgb2gray» в среде MATLAB и это часто используется для компьютерного зрения . В процессе предварительной нечеткой обработки имеет процесс преобразования изображений из цветного (RGB) в оттенки серого с помощью метода определения яркости. Далее изображение преобразуется из оттенки серого в черно-белый (рис. 2).

Рис. 2. процесс преобразования изображений из цветного в оттенки серого

Бинаризация изображения при предварительной обработке

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

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

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

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

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

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

Рис. 3. Преобразование пикселя изображения

Алгоритм нечеткой обработки для выделения границ и сегментации изображений

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

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

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

(1)

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

Выход системы для входной системы задается следующую формулу:

(2)

Рис. 4. Алгоритм нечеткой обработки изображений для выделения границ

Применение нейронных сетей для распознавания образов

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

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

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

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

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

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

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

Шаг 3. Настройка синоптических весов. Рассчитать изменение весов для выходного слоя нейронной сети по формулам:

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

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

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

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

Заключение

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

Рецензенты:

Гагарина Л.Г., д.т.н., профессор, заведующий кафедрой «Информатика и программное обеспечение вычислительных систем» Национального исследовательского университета «МИЭТ», г. Москва.

Портнов Е.М., д.т.н., профессор кафедры «Информатика и программное обеспечение вычислительных систем», начальник научно-исследовательской лаборатории «Управляющие информационные системы» Национального исследовательского университета «МИЭТ», г. Москва.

Библиографическая ссылка

Аунг Ч.Х., Тант З.П., Федоров А.Р., Федоров П.А. РАЗРАБОТКА АЛГОРИТМОВ ОБРАБОТКИ ИЗОБРАЖЕНИЙ ИНТЕЛЛЕКТУАЛЬНЫМИ МОБИЛЬНЫМИ РОБОТАМИ НА ОСНОВЕ НЕЧЕТКОЙ ЛОГИКИ И НЕЙРОННЫХ СЕТЕЙ // Современные проблемы науки и образования. – 2014. – № 6.;
URL: http://science-education.ru/ru/article/view?id=15579 (дата обращения: 01.02.2020). Предлагаем вашему вниманию журналы, издающиеся в издательстве «Академия Естествознания»

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

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

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

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

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

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

Введение.

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

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

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

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

ВВЕДЕНИЕ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Mij = (Aij, Cij).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Таблица 17.2.1.

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

Временное окно	Весовая функция	Фурье-образ
Естественное (П)	П(t) = 1, |t|£t; П(t) = 0, |t|>t	П(w) = 2t sinc
Бартлетта (D)		B(w) = t sinc2(wt/2).
Хеннинга, Ганна	p(t) = 0.5	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) = exp[-b2(t/t)2/2]	[(t/b) exp(-t2w2/(2b2))] ③ П(w)

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

f2(x, y) = f1(),

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

.

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

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

.

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

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

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

. .

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

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

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

. .

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

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

G(x, y) =.

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

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

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

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

Gxx, y = - ,

Gyx, y = - .

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

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

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

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

.

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

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

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

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

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

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

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

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

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

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

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

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

B(x, y) =

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

литература

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

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

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

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

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

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

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

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

Copyright ©2008 Davydov А. V .