Содержание к диссертации
Введение
1. Анализ методов сокращения информационной избыточности цифровых изображений 9
1.1. Представление цифровых изображений 11
1.2. Классификация методов сжатия. Основные характеристики 12
1.3. Алгоритмы сжатия изображений без потерь 20
1.3.1. Сжатие способом кодирования серий (RLE) 20
1.3.2. Сжатие по методу Хаффмана 21
1.3.3. Алгоритм Лемпеля-Зива (LZ-compression) 22
1.3.4. Алгоритм Лемпеля-Зива-Велча (Lempel-Ziv-Welch -LZW) 23
1.3.5. Алгоритм JBIG 24
1.3.6. Алгоритм Lossless JPEG 24
1.4. Алгоритмы сжатия с потерями 26
1.4.1. Метод усеченного блочного кодирования (УБК) 26
1.4.2. Сжатие по стандарту JPEG 27
1.4.3. Сжатие по стандарту MPEG 35
1.4.4. Сжатие по методу WIC (Wavelet Image Compression) 38
1.4.5. Фрактальное сжатие изображений 43
Выводы по главе 1 51
2. Модификация алгоритмов сжатия /восстановления изображений по методу JPEG 52
2.1. Применение преобразования Хартли для пространственно-частотной декомпозиции фрагментов 52
2.2. Применение дискретных ортогональных двузначных преобразований 56
2.2.1. Дискретное преобразование Уолша-Адамара 56
2.2.2. Преобразование Хаара 60
2.3. Алгоритмы быстрых ортогональных преобразований в базисах знакопеременных диадных функций 61
2.4. Модификация процедур сканирования и квантования отсчетов фрагмента 66
2.5. Исследование эффективности сжатия/восстановления изображений на основе модифицированного метода JPEG 76
Выводы по главе 2 86
Глава 3. Сжатие изображений с адаптивным выбором фрагментов 88
3.1. Адаптивный метод сегментации областей 88
3.2. Параллельный алгоритм отслеживания границы связного дискретного изображения 98
3.3. Алгоритм сжатия отдельных фрагментов 106
3.4. Исследование эффективности сжатия/восстановления изображений с адаптивным выбором областей 108
Выводы по главе 3 117
Глава 4. Модифицированный фрактальный метод сжатия 118
4.1. Аппроксимация локальных областей изображения 119
4.2. Определение параметров аппроксимирующей функции 124
4.3. Поиск области максимального размера 127
4.4. Восстановление изображения 129
4.5. Анализ полученных результатов 131
Выводы по главе 4 141
Заключение 142
Список литературы 145
- Представление цифровых изображений
- Применение преобразования Хартли для пространственно-частотной декомпозиции фрагментов
- Адаптивный метод сегментации областей
- Аппроксимация локальных областей изображения
Введение к работе
Актуальность проблемы. В последнее время наблюдается бурное развитие телекоммуникационных систем, причем одной из важнейших задач для них является прием и передача видеоданных.
Решение подобной задачи стало возможным благодаря существенному увеличению емкости памяти и вычислительной мощности технических средств, входящих в состав телекоммуникационных систем.
Однако рост потребительских требований к объемам передаваемых видеоданных и к их качеству опережает возможности технических средств хранения изображений и пропускную способность средств приема-передачи видеоданных, что вызывает значительные трудности при хранении и передаче изображений. Тем самым возникает необходимость использования различных технологий сжатия видеоинформации, представляющих собой методы составления искусственного описания исходного изображения меньшим количеством бит при сохранении или незначительном уменьшении количества информации.
В настоящее время используются многочисленные методы сжатия/восстановления изображений различной физической природы. Среди них можно выделить два больших класса - методы сжатия без потерь и методы сжатия с потерями. Первые из них не обеспечивают больших значений коэффициента сжатия, что во многих практических приложениях требует использования второй группы методов. К числу подобных методов можно отнести аппроксимационные методы, методы спектрального разложения (к таким методам относятся, в частности, широко распространенные методы сжатия JPEG, MPEG и WIC) и фрактальные методы. Однако им присущи существенные недостатки - высокая трудоемкость и достаточно существенные искажения при больших значениях коэффициента сжатия.
Тем самым является актуальной задача разработки новых методов сжатия и совершенствования существующих широко распространенных методов JPEG и MPEG с целью уменьшения вычислительной сложности и повышения качества восстанавливаемых по сжатым образам изображений, что имеет важное значение при передаче изображений по каналам связи и в иных задачах, требующих обеспечения реального масштаба времени.
Целью настоящей работы является совершенствование существующих и создание новых методов сокращения информационной избыточности цифровых изображений, выработка рекомендаций по возможностям применения реализации этих методов для решения различных практических задач.
Задачами исследования являются: совершенствование алгоритмов сжатия изображений по стандарту JPEG за счет: применения преобразований Хартли, Уолша - Адамара и Хаара; применения новых способов сканирования матрицы спектральных компонент фрагментов; дополнительной весовой обработки вектора спектральных компонент перед квантованием; применения оптимального кодирования с укрупнения для представления квантованных значений спектральных компонент; разработка метода сжатия изображений на основе выделения локальных областей, подлежащих сжатию:
О разработка метода сегментации изображений с адаптивным выбором порога; О разработка методов сглаживания границ объектов, локализованных в выделенных областях; О исследование влияния размеров сжимаемых фрагментов выбранной области на коэффициент сжатия и качество восстановленного изображения; разработка метода сжатия на основе аппроксимации изображения фрагментами гармонических функций:
О построение алгоритмов сжатия и восстановления;
О разработка методики определения параметров аппроксимирующей функции.
Методы исследований основаны на теории спектральной обработки сигналов, теории информации, распознавания образов, принципах распараллеливания и конвейеризации вычислений.
Научная новизна работы состоит в следующем: разработана модификация алгоритма JPEG, основанная на применении ортогонального преобразования Хаара при выполнении спектрального разложения фрагментов изображения; предложено применение кодирования по Хаффману с укрупнением при кодировании квантованных спектральных компонент; выполнено исследование эффективности преобразований Хаара и Уолша -Адамара для сжатия изображений по стандарту JPEG; разработаны новые алгоритмы сканирования матрицы спектральных компонент фрагментов для указанных базисов с использованием вероятности появления ненулевых компонент в каждой позиции и спирального сканирования; выбраны весовые функции при квантовании отсчетов вектора спектральных компонент фрагментов изображения, позволяющие при приемлемом качестве восстановленного изображения сократить число ненулевых компонент; разработан метод сегментации областей изображения; разработан метод сжатия изображений на основе выделения локальных областей, подлежащих сжатию и содержащих информативные объекты изображения; разработан метод сжатия на основе сегментации областей изображения и их аппроксимации фрагментами гармонических функций.
Практическая ценность результатов заключается в следующем: разработаны программно-алгоритмические средства сжатия и восстановления изображений по JPEG-подобному методу, реализующие предложенные автором подходы; разработаны программно-алгоритмические средства сжатия изображений на основе выделения локальных областей с информативными объектами изображения, подлежащих сжатию; выполнены эксперименты по сжатию восстановлению изображений различного смыслового характера, в ходе которых подтверждена эффективность предложенных методов, а именно, снижение вычислительных затрат, обеспечение большего коэффициента сжатия или меньшие искажения при восстановлении; разработаны рекомендации по применению разработанных методов сжатия для решения различных практических задач сжатия многоуровневых изображений.
Основные результаты работы внедрены в СПбГИТМО(ТУ), ЗАО "Петербург Транзит Телеком". Работа поддерживалась грантами Конкурсного центра фундаментального естествознания Министерства образования Российской федерации в 2001 и 2002 годах.
Основные положения, выносимые на защиту:
Модифицированный алгоритм JPEG, отличающийся иными ортогональными преобразованиями и способом сканирования матрицы спектральных компонент.
Результаты исследования эффективности применения ортогональных преобразований Хартли, Уолша - Адамара и Хаара для сжатия изображений по стандарту JPEG.
Метод сегментации областей изображения и отслеживания границ областей.
Метод сжатия изображений на основе выделения локальных подлежащих сжатию областей, содержащих информативные объекты.
Метод сжатия на основе сегментации областей изображения и их аппроксимации фрагментами гармонических функций.
Апробация работы. Результаты выполненных исследований докладывались на IV Int. Conf. «Pattern recognition and information processing», 20-22 may 1997, Minsk - Szczecin, Belarus - Poland, XXX научно-технической конференции студентов, аспирантов и молодых ученых Санкт-Петербургской академии гражданской авиации , -СПб, 1998, XIII International conference "Systems for automation of engineering and research" (SAER-99) September 18-19, St.Konstantin, Bulgaria, 1999, XXXII научно-технической конференции студентов, аспирантов и молодых ученых Санкт-Петербургской академии гражданской авиации, -СПб, 2000, VI Санкт-Петербургской ассамблеи молодых ученых и специалистов, СПб, СпбГУ, 2001, III Int.Conf."Advanced Computer Systems ASC-2002", Szczecin, Poland, 23-25 Oct., 2002, Всероссийской научно-технической конференции "Прогрессивные технологии в машино и приборостроении", Нижний Новгород-Арзамас, 2002, XXXIV научно-технической конференции студентов, аспирантов и молодых ученых Санкт-Петербургской академии гражданской авиации, -СПб, 2002, Политехническом Симпозиуме «Молодые ученые - промышленности Северо-Западного Региона, СПб, СПбГПУ, 2002, XXXII (2002) и ХХХШ (2003) Научно-технических конференциях профессорско-преподавательского состава СПбГИТМО(ТУ).
По теме диссертации опубликовано 12 работ. Структура и объем диссертации. Диссертация состоит из введения, четырех глав, заключения и списка литературы. Рукопись содержит 151 страницу текста, 45 рисунков и 10 таблиц.
Список литературы включает 69 наименований.
1. АНАЛИЗ МЕТОДОВ СОКРАЩЕНИЯ ИНФОРМАЦИОННОЙ
ИЗБЫТОЧНОСТИ ЦИФРОВЫХ ИЗОБРАЖЕНИЙ
В последнее время наблюдается бурное развитие телекоммуникационных систем, предназначенных для приема и передачи видеоданных.
Решение подобной задачи стало возможным благодаря существенному увеличению емкости памяти и вычислительной мощности технических средств, входящих в состав телекоммуникационных систем. В состав таких средств входят универсальная или специализированная ЭВМ, специализированные устройства ввода-вывода изображений, средства для хранения или архивации видеоинформации и соответствующее программное обеспечение. В общем случае комплекс подобных средств должен также обеспечивать ввод, вывод и передачу изображений различной физической природы [5].
Под вводом изображения понимаются процедуры преобразования исходного изображения к виду, удобному для вычислительной системы. Ввод может производится как со стандартных периферийных устройств ЭВМ (ВЗУ, сканеров), так и с нестандартных по отношению к ЭВМ устройств. К последним относятся, например, телевизионные камеры и ПЗС-линейки.
Под выводом изображения понимается оперативная визуализация на видеомониторе, архивация с целью долговременного хранения и документирование необходимой информации.
Передача изображений включает в себя обмен изображениями между различными блоками системы обработки и обмен изображениями по каналам передачи данных между системой и устройствами, не входящими в ее состав.
Следует отметить, что выполнение различных функций может быть возложено на функционально-ориентированные рабочие станции на базе персональных ЭВМ, подключенных к локальной сети с выходом в глобальную сеть (рис Л Л).
Сканер t
Исходный фотодокумент
Обработка
Улучшение качества
Адаптивная импульсная фильтрация
Повышение контраста
Интерактивная обработка
Сжатие из о сражений Microsoft Access
Ввод текста ~\ Конвертер Г t j
Архив(ы) изображений
Логическая связь
Б аз а данных
АрХИВаЦИЯ J '"^Жирование w, Прочие -----і--- "" еерсии БД I
Узел WWW
О 1 Комплект CD-ROM Microsoft Access
Поиск Фильтрация Сортировка
Процедура наУВА DLL для конверсии
Текст
Экспортв файл
Показ формы
Рабочее место на PC
Временный BMP
Печать отчета j Другие платформы
Рис. 1.1. Технические средства телекоммуникационной системы для передачи видеоданных и их функциональное назначение
Представление цифровых изображений
Компьютерное изображение в его цифровом представлении является набором значений интенсивностей светового потока, распределенных по конечной площади.
Для простоты рассмотрим сначала монохромные изображения. Интенсивность излучаемой световой энергии с единицы поверхности в точке с координатами {E,,rj) изображения можно представить некоторым числом B(,rj). Единичный элемент изображения, характеризуемый определенным значением {%,rj), называется пикселем, а величина z = /(,77) - яркостью [5,17].
Прежде чем рассмотреть алгоритмы сжатия изображений, необходимо определить что в дальнейшем будет пониматься под изображением. В дальнейшем будут рассматриваться статические растровые изображения, представляющие собой двумерный массив отсчетов - пикселов. Все изображения можно разделить на две группы: с палитрой и без нее. У изображений с палитрой в пикселе хранится число - индекс в некотором одномерном векторе цветов, называемом палитрой. Изображения без палитры бывают в какой-либо системе цветопредставления и в градациях серого. Для последних значение каждого пиксела интерпретируется как яркость соответствующей точки. При использовании некой системы цветопредставления каждый пиксел представляет собой запись (структуру), полями которой являются компоненты цвета. Самой распространенной является система RGB, в которой цвет представлен значениями интенсивности красного (R), зеленого (G) и синего (В) компонента.
Большинство цветных растровых изображений для сохранения деталей цвета пикселя применяют систему цветов RGB, прежде всего потому, что эта система используется для изображения цветов монитором компьютера. Для точного сжатия изображения с цветами RGB необходимо все три компоненты сжимать с одинаковым уровнем точности. Комбинация этих трех компонент определяет относительную яркость пикселя, а также его цвет.
Так как глаз человека более чувствителен к изменению яркости, чем к изменению цвета, часто требуется преобразовать систему цветов RGB в систему, где информация о яркости пикселях запоминалась бы отдельно от информации о цвете. К подобным системам цветов, относятся системы HSB (тон, насыщенность, яркость) и YUV (У - компонента яркости; U и V хранят характеристики цвета).
Все методы сжатия информации основаны на том простом предположении, что набор данных всегда содержит избыточные элементы. Сжатие достигается за счет поиска и кодирования избыточных элементов [2,8,34].
Поток данных об изображении имеет существенное количество излишней информации, которая может быть устранена практически без заметных для глаза искажений. При этом различают два типа избыточности.
Статистическая избыточность связана с корреляцией и предсказуемостью данных. Эта избыточность может быть устранена без потери информации, исходные данные при этом могут быть полностью восстановлены [8,34]. Наиболее известные методы эффективного кодирования символов основаны на знании частоты каждого символа присутствующего в сообщении. Зная эти частоты, строят таблицу кодов, обладающую следующими свойствами: различные коды могут иметь различное количество бит; коды символов с большей частотой встречаемости, имеют меньше бит, чем коды символов с меньшей частотой; хотя коды имеют различную битовую длину, они могут быть восстановлены единственным образом, т.е. коды строятся как префиксные. Этими свойствами обладает известный алгоритм Хаффмана [34].
Визуальная (субъективная) избыточность, которую можно устранить с частичной потерей данных, мало влияющих на качество воспроизводимых изображений; это - информация, которую можно изъять из изображения, не нарушая визуально воспринимаемое качество изображений.
Устранение визуальной избыточности изображений является основным резервом сокращения передаваемой информации [8,11]. Для оптимизации процесса кодирования в целях обеспечения передачи наименьшего объема информации необходимо, с одной стороны, не передавать избыточную информацию, а, с другой, - не допустить чрезмерной потери качества изображения.
До сих пор не существует простой и адекватной модели визуального восприятия изображений, пригодной для оптимизации их кодирования [5,17]. Рассмотрим этапы процедуры сжатия данных в общем виде. Любой метод сжатия реализует три основных этапа (рис. 1.2):
1. Этап предварительной обработки 2. Основное преобразование 3. Кодирование и упаковка компонент преобразования. Исходное изображение I этап предварительная обработка SL II этап основное преобразование III этап кодирование и упаковка Сжатое изображение
На этапе предварительной обработки производится, в общем случае, подготовка исходного изображения к выполнению процедуры основного преобразования. В частности, можно выделить два вида такой подготовки: фильтрация шумов и перестановка пикселов исходного изображения. В общем случае изображение / может быть представлено в виде: где /„-исходное изображение; G- случайный аддитивный шум, распределенный по какому-либо случайному закону. Ни одно известное преобразование, используемое в процедурах сжатия, не дает эффекта для случайного шума. Поэтому на этапе предварительной обработки случайный шум пытаются устранить различными методами фильтрации [15,23,26,46]. Для обеспечения работы процедур быстрых преобразований необходима, в ряде случаев, перекомпоновка и пересчет значений исходного изображения. В общем случае процедура фильтрации вносит искажения в исходное изображение [15,17]. Но при этом визуально качество исходного и восстановленного изображения улучшается [46].
Применение преобразования Хартли для пространственно-частотной декомпозиции фрагментов
Как следует из главы 1, одним из наиболее эффективных методов сжатия изображений является процедура сжатия согласно стандарту JPEG, которая предусматривает разбиение исходного изображения на фрагменты размером 8 х 8 элементов, пофрагментное ортогональное преобразование в базисе косинусных функций, квантование полученных результатов на определенное число уровней и последующее кодирование отсчетов по Хаффману.
Однако применение модифицированного преобразования Хартли для вычисления двумерных функций свертки и корреляции приводит к ряду особенностей, которые, в частности рассматриваются в работах [27, 35].
Применение преобразования Хартли вместо преобразования Фурье как при спектральном разложении фрагментов исходного изображения, так и при пространственно-частотной фильтрации исходного изображения в целях удаления шумов позволяет существенно сократить затраты памяти и время решения задач (более чем в два раза по сравнению с ДПФ), в чем и заключается его преимущество. В заключении отметим, что двумерное ДПХ может быть реализовано в свою очередь на основе высоко эффективных быстрых алгоритмов [3, 27, 43].
Помимо преобразований Хартли и косинусного преобразования в цифровой обработке сигналов достаточно широко применяется разложение по набору ортогональных знакопеременных двузначных функций, что позволяет устранить операции умножения при выполнении преобразований и сократить тем самым время обработки. Однако в литературе не встречалось данных о применении таких базисов для сжатия данных. Поэтому представляет интерес проанализировать возможности использования подобных базисов функций и для задач сжатия/восстановления изображений.
При этом матрица ядра обратного преобразования обладает свойством E l = E N, где E N - эрмитово-сопряжённая матрица. Как известно, для эрмитово-сопряжённой матрицы матрица обратного преобразования является транспонированной по отношению к EN и элементы её являются комплексно сопряжёнными к элементам исходной матрицы.
Ортогональные преобразования в двузначных знакопеременных базисах определены только для данных, представленных векторами с длиной N= 2м. К таким преобразованиям относятся преобразования Адамара, Пэли, Уолша, Трахтмана, Качмарджа и ряд других. Матрица ядра любого из подобных преобразований содержит целочисленные коэффициенты из множества {-1; +1}. Очевидно, что при выполнении подобных преобразований существенно сокращается объем вычислений, поскольку при умножении исходных данных на матрицу ядра сами операции умножения исключаются из-за тривиальности элементов матрицы ядра и остаются лишь операции сложения - вычитания [13,18].
Очевидно, что свойства матриц PN и WN аналогичны свойствам матрицы AN. Матрицы ядер преобразования Трахтмана и Качмарджа также могут быть получены на основе матрицы ядра Адамара, но при использовании обратной перестановки по коду Грея.
Заметим, что матрицы преобразований в указанных базисах отличаются порядком строк. Очевидно, что при обработке одного и того же вектора исходных данных X в различных базисах вектор результата будет содержать одинаковые по своей величине элементы, отличаясь для каждого преобразования лишь порядком их следования. Поэтому для всех подобных преобразований можно использовать одну и ту же матрицу ядра, например, AN, а для получения вектора F с нужным для каждого преобразования порядком следования элементов, переупорядочить элементы исходного вектора X. Так, для преобразования Пэли необходима двоично-инверсная перестановка, а для преобразования Уолша - двоично-инверсная перестановка и затем перестановка по коду Грея.
Адаптивный метод сегментации областей
Как было отмечено, объект (фрагмент или локальную область) изображения можно рассматривать как совокупность областей интенсивности. Для выделения области интенсивности на изображении используются методы локализации объектов на изображении или методы сегментации областей.
Классические методы сегментации основаны на использовании порога интенсивности [28,44, 45]. Если точки изображения имеют значения выше (ниже) некоторого порога, то они принадлежат области, иначе - не принадлежат. Эти методы имеют ряд недостатков: методы сегментации по уровню интенсивности дают плохие результаты, если имеется изменение интенсивности освещенности в пространстве изображения; если внутри области наблюдается изменение интенсивности, то будет выделено несколько концентрических областей. Главная трудность заключается в выборе порога интенсивности. В связи с этими недостатками предлагается использовать новый метод сегментации областей, который заключается в следующем х12б 39ъ. Пикселы изображения составляют область, если каждый пиксел области обладает необходимыми свойствами. Наличие или отсутствие этих свойств определяет принадлежность конкретного пиксела области изображения.
Свойство монотонности (рис.3.1) определяет границы объекта, которыми являются точки экстремумов двумерной функции /, описывающей изображение. Т.е., если существует какое - либо множество точек объекта и необходимо определить связана ли некоторая соседняя точка с множеством точек этого объекта, то достаточно проверить, чтобы значение ее интенсивности было меньше, чем у соседней с ней точки объекта. В противном случае эта точка не связана с объектом.
Основные отличия предлагаемого метода от классических методов сегментации, заключается в следующем: в отличии от методов порогового ограничения, не используется порог, общий для всего изображения. Пороговые уровни Itop и hottom определяются для каждой области индивидуально и составляют некоторую долю от уровня 1тах. в отличии от методов наращивания областей, выбирается только одна стартовая точка. вводятся дополнительные ограничения на форму области.
Определение порогов обычно связано с анализом гистограммы отображения из множества значений яркости в множество натуральных чисел. Глобальный максимум гистограммы соответствует наиболее часто встречающемуся значению яркости bmax- В большинстве задач доминирует фон, так что значение bmax отвечает фону. Следует ожидать, что и близкие к bmax значения яркости также соответствуют фону. Для определения порога, отделяющего яркость объектов от яркости фона, достаточно располагать дополнительной информацией.
Поиск максимального по модулю элемента двумерного целочисленного массива, каким является цифровое изображение, есть стандартная процедура. Однако, ввиду того, что изображения представляют собой массивы больших объемов, а также то, что эта процедура повторяется многократно в процессе работы алгоритма, то непосредственное ее выполнение приводит к значительным вычислительным затратам.
На самом деле после определения очередной компоненты и исключения ее из исходного изображения модифицируется только определенная часть изображения.
Для оптимизации процедуры поиска точки максимальной по модулю яркости предлагается прием, используемый в системах параллельной обработки и нейроподобных структурах.
Исходное изображение разбивается на фрагменты с таким расчетом, что число фрагментов равно количеству пикселов внутри каждого фрагмента. Например, если изображение имеет размеры 256x256 точек, то организуется матрица 16x16=256 фрагментов, причем каждый содержит 16x16=256 пикселов. Затем организуется массив, каждый элемент которого соответствует фрагменту МАХ 16x16. В нем будут храниться координаты ТМЯ для каждого фрагмента. Вначале, до работы основного алгоритма заполняется массив МАХ. Затем, зная ТМЯ для каждого фрагмента, выбирается ТМЯ для всего изображения. При этом поиск происходит только внутри массива МАХ.
После этого производится распознавание и исключение из исходного изображения очередного объекта. Зная координаты центра области (х0, уо) и его размеры 1Х, 1У, определяем, какие фрагменты затронула обработка. В этих фрагментах производится обновление координат ТМЯ. Затем снова производится выбор ТМЯ для всего изображения.
Преимущества такого подхода заключаются в следующем: 1. При поиске ТМЯ происходит перебор значений пикселов не всего изображения, а только тех фрагментов, которые подверглись обработке. Это приводит к существенной экономии времени. 2. Такая схема удобна для аппаратной реализации, либо для реализации в системах параллельной обработки, поскольку поиск внутри каждого фрагмента может производиться независимо. Для выполнения подобного алгоритма организуется два массива:
1. Массив отметок REG. Если пиксел принадлежит локальной области, то соответствующий элемент массива REG принимает ненулевое значение. Массив REG - двумерный. Система координат выбирается такая, что центральный элемент массива имеет координаты (0,0) и соответствует первой обнаруженной точке объекта - точке максимальной яркости. Размеры массива выбираются, исходя из максимального размера объекта, предполагаемого обнаружить на исходном изображении. По окончании работы алгоритма массив содержит отметки, соответствующие всем пикселам обнаруженного объекта.
2. Вспомогательный массив STACK. Этот массив содержит координаты пикселов, принадлежащих локальной области, рядом с которыми есть непроверенные пикселы - кандидаты на принадлежность данной области.
Аппроксимация локальных областей изображения
Алгоритм сегментации выделяет на изображении некоторую локальную область или объект на изображении, описываемой функцией .
Основной принцип классических методов распознавания заключается в том, что исходный объект на изображении сравнивается с эталонным примитивом. По результатам сравнения принимается решение о соответствии объекта и эталона[44]. Предлагаемый подход имеет важное преимущество перед классическими методами, которое состоит в том, что простой объект существенно легче выделить на реальном изображении. Для этого необходимо, чтобы интенсивность точек этого объекта изменялась по закону, определяемому функцией . Таким образом, необходимо распознавать области только одного заданного типа. Это очень важно для машинной реализации, поскольку с относительно небольшими вычислительными затратами, позволяет выполнять распознавание простых образов на любых изображениях.
Для выбора примитива необходимо заменить пикселы выделенного объекта значениями функции , т.е. аппроксимировать область изображения функцией fs.
Функция , которая задает пятно, должна быть гладкой, чтобы избежать разрывов при аппроксимации больших пятен. Применение аппроксимирущей функции позволяет сохранить информацию о пятне в виде координат центра, амплитуды и размерах фрагмента используемой гармонической функции. К аппроксимирующим функциям предъявляются следующие требования [39, 41]: простота аналитического описания аппроксимирующей функции; наличие выраженного максимума в центре и монотонность убывания к периферии; осесимметричность; плавное сопряжение с фоновым изображением («подстилающей поверхностью»); простота масштабного преобразования.
К числу аппроксимирующих функций, наиболее полно удовлетворяющих указанным требованиям, могут быть отнесены, в частности, двумерные гармонические функции вида [39] /(х ) = sbos[ios(x-x0s)]+ll Ms[a),{y-y0s)]+l}x,yeDs [0;x,yDs В выражении (4.2) x,ysDs означает, что отсчеты аппроксимирующей функции относятся к области Ds, a s - частота гармонической функции, причем размер локальной области определяет пространственный период гармонической функции.
В этом случае весь набор или множество эталонов состоит всего из одного примитива. Очевидно, что с помощью такого простого эталона невозможно точно представить объекты реального изображения. Это приведет к тому, что изображение будет представляться с определенной точностью. К тому же функции fs будут перекрываться в пространственной области. Но, с другой стороны, тем самым существенно упрощается задача аппроксимации.
Заметим, что функция sine (х,у) также обладает явно выраженной осевой симметрией и плавным сопряжением с фоновой поверхностью, однако при более высоком разрешении при восстановлении изображения обеспечивает меньшие значения коэффициентов сжатия.
На рис 4.1 а) и б) представлены в качестве примера локальные области, описываемые указанными аппросимирующими функциями.
Рассмотрим аппроксимацию выделенных локальных областей фрагментами двумерных гармонических функций вида (4.2). Такая аппроксимация приводит к погрешности (потерям) при построении изображения из функций, аппроксимирующих пятна, но при этом существенно упрощается задача описания пятен. Для этого нужно определить параметры: С - максимальную амплитуду области; х& уо - координаты центра области; 1Х, 1У -размеры области, однозначно определяющие частоты .
Если область имеет эллиптическую форму, то необходимо также определить его ориентацию на изображении. В этом случае при аппроксимации объекта необходимо выполнять дополнительное аффинное преобразование аргументов функции fs, соответствующее ее развороту на угол р в пространстве изображения, (см. рис.4.2.).
