Лекции по "Технологии цифровой обработки сигналов"

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

 

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

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

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

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

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

Лекция 5. РАСПОЗНАВАНИЕ  ОБЪЕКТОВ ИЗОБРАЖЕНИЙ

Содержание

Введение.

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

2. Определение границ  объектов на изображении. Поиск  границ на основе градиента.  Поиск границ на основе лапласиана.

3. Выделение объектов  на изображении. Алгоритм "волшебная  палочка". Алгоритм "умные ножницы". Сегментация при помощи разрезов на графах.

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

5. Обнаружение и распознавание  объектов изображений. Обнаружение  объектов. Способ прямого сравнения  объекта с эталонным изображением. Корреляционный метод. Методы распознавания на основе системы признаков.

ВВЕДЕНИЕ

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

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

5.1. предварительная обработка ИЗОБРАЖЕНИй 

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

Коррекция яркости и контрастности изображений.

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

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

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

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

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

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

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

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