Содержание к диссертации
Введение
Глава 1. Аналитический обзор методов обработки видеоданных 13
1.1. Интегральные методы анализа изображений 18
1.1.1. Преобразование Фурье. Алгоритм JPEG 21
1.1.2. Вейвлет-анализ 27
1.1.3. Кратноразрешающий анализ. JPEG 2000 31
1.2. Метод и алгоритмы цифровой обработки видеоданных 38
1.2.1. Алгоритмы и форматы цифрового представления изображений :.38
1.2.2. Форматы сжатия и хранения видеоданных 48
Выводы по главе 1 57
Глава 2. Метод и алгоритмы адаптивно-динамической сегментации изображений 58
2.1. Дискретные методы обработки изображений 58
2.1.1. Динамическая модель дискретного пространства 58
2.1.2. Метод коллажа. Итерационно-функциональный подход 63
2.1.3. Адаптивно-динамическая сегментация (АДС) изображений..
2.2. Концептуальная схема АДС 72
2.3. Критерий оценки качества изображения 79
2.4. Алгоритмы адаптивно-динамической сегментации
2.4.1. Дизъюнктивная сегментация 85
2.4.2. Конъюнктивная сегментация 86
Выводы по главе 2 88
Глава 3. Разработка программной среды интерфейсной поддержки селекции семантических фрагментов 89
3.1. Описание метода интерфейсной поддержки 89
3.2. Автоматический режим 91
3.3. Операторный режим 92
Выводы по главе 3 94
Глава 4. Экспериментальная апробация 95
4.1. Селекция семантических фрагментов 95
4.2. Оценка качества передачи видеоданных 98
4.3. Оценка качества восприятия изображений 102
Выводы по главе 4 111
Заключение 112
Список использованной литературы
- Вейвлет-анализ
- Динамическая модель дискретного пространства
- Автоматический режим
- Оценка качества передачи видеоданных
Введение к работе
Актуальность темы диссертации. Актуальность темы диссертационной работы в первую очередь определяется её ориентацией на важную практическую проблему эффективного анализа семантических составляющих на видеоданных и изображениях. Традиционные подходы к решению задач сегментации видеоданных с целью селекции и распознавания образов не покрывают такие проблемы как видеонаблюдение, например face-control, а также передача в реальном времени больших объемов видеоданных с одновременной локализацией и семантическим описанием объекта. До сих пор обработка изображений в большей степени использовала математические модели, основанные на спектральном -интегральном анализе, которые сводятся к числовой обработке и выявлению специфических признаков. Однако развитие компьютерных технологий привело к расширению класса прикладных задач анализа видеоданных, появлению таких задач как: визуализация пространственных объектов в реальном времени, создание растрового покрытия территорий в неогеографии, управление беспилотными летательными аппаратами, требующее постоянного развития алгоритмов поиска цели, для которых необходимо решение задач селекции, идентификации объектов по семантическому содержанию, в том числе и современных проблем кодировки и сокрытия данных, а также выявления различных уровней семантического содержания.
Различные аспекты обработки и анализа изображений и видеоданных рассмотрены в работах Ю.И Журавлева, В.В. Александрова, Н.Д. Горского, В.В. Поповича, Д.Сэломона, Д. Ватолина, А. Ратушняка, М. Смирнова, В. Юкина, и многих других.
Возможности программируемой технологии и семантического анализа позволяют эффективно решать задачи, поставленные динамично развивающимися современными Hi-tech (высокими) технологиями. В данной работе предлагаются решения в области сегментации видеоданных для комплексного решения проблемы семантического анализа.
Цель работы и задачи исследования. Исследование и разработка иерархической структуры представления видеоданных, методов сегментации с целью выявления семантических фрагментов и интерфейса поиска ассоциативных семантических связей.
Для достижения поставленной цели в диссертационной работе решаются следующие задачи:
Исследование и разработка метода адаптивно-динамической сегментации.
Разработка алгоритма и программы многоуровневой древовидной сегментации изображения для выявления семантического порога є-идентифицируемости.
Разработка программы адаптивного поиска и локализации семантических фрагментов.
Экспериментальная апробация программно-инструментальной среды для выявления понятийных семантических составляющих.
Методы исследования. Для решения поставленных задач в работе используются цифровые технологии, математические модели итерационно-функциональных систем (рекурсивно-фрактальный подход) и инфологические методы. Компьютерная реализация разработанных алгоритмов производилась с использованием объектно-ориентированного программирования.
Положения, выносимые на защиту:
Метод «коллажа» как индексация древовидной структуры видеоданных, сохраняющая локально-пространственную (пиксельную) и семантическую идентификацию.
Алгоритм и программы адаптивно-динамической сегментации изображения. Селекция и идентификация семантических фрагментов.
Программа адаптивной интерфейсной поддержки индексации семантических фрагментов.
Оценка критерия качества изображения с позиции семантической є-идентифицируемости.
Научная новизна работы состоит в следующем:
Предложен метод «коллажа» для представления изображений и их фрагментов в виде индексной древовидной структуры данных, сохраняющей локально-пространственную и семантическую идентификацию, в отличие от известных интегральных методов (Фурье- и вейвлет-анализ и др.).
Разработаны алгоритм и программы многоуровневой древовидной индексации видеоданных, использующие адаптивно-динамическую сегментацию, обеспечивающую семантическую селекцию и индексную идентификацию фрагментов.
Разработана программа интерфейсной адаптивной поддержки выявления семантических фрагментов изображения, позволяющая представить исходное изображение как совокупность семантических фрагментов (метод коллажа).
Предложено использовать понятие є-идентифицируемости (эквивалентности) для оценки качества семантического восприятия в отличие от энергетических характеристик оценки качества изображения, таких как среднеквадратическое отклонение (СКО), пиковое отношение сигнала к шуму (PSNR) и др.
Обоснованность и достоверность научных положений, основных выводов и результатов диссертации обеспечивается опорой на математические модели интегральной геометрии, анализом исследований в
данной области, корректность предложенных алгоритмов подтверждается экспериментальной апробацией разработанных методов, а также апробацией основных теоретических положений диссертации в печатных трудах и докладах на научных конференциях.
Практическая ценность работы. Разработанные модели и алгоритмы позволяют расширить круг решаемых проблем обработки видеоданных:
выявления различных семантических уровней, что позволяет решать задачу компрессии с точки зрения семантико-смыслового восприятия;
локализации и семантического описания объектов при видео наблюдении, передаче видеоданных в реальном времени.
Для решения перечисленных проблем разработана инструментальная среда адаптивно-динамической сегментации для семантического анализа видеоданных. Программа адаптивной интерфейсной поддержки позволяет реализовать функции визуализации семантических фрагментов.
Реализация результатов работы. Полученные результаты реализованы в виде прикладных программных продуктов. Ряд программных продуктов был внедрен в виде составных фрагментов НИР в 2004-2008 при выполнении контрактов с ГОС НИИПП. Исследования, отраженные в диссертации были поддержаны грантами ОИТВС РАН (№4.8, 2003-2006), часть результатов была использована в проектах СПбНЦ РАН, 2003-2005.
Апробация результатов работы. Основные положения и результаты диссертационной работы представлялись на конференциях «Региональная информатика» (2000, 2004, 2008 гг.), «Информационные технологии и системы (ИТиС'08)», «Distributed Intelligent Systems and Technologies Workshop» (2009).
Публикации. Основные результаты по материалам диссертационной работы опубликованы в 10 печатных работах, среди них 3 работы в журналах из перечня ВАК.
Структура и объем работы. Диссертация объемом 125 машинописных страниц, содержит введение, четыре главы и заключение, список литературы (97 наименований), 2 таблицы, 47 рисунков.
Вейвлет-анализ
Интегральное преобразование Фурье и ряды Фурье являются основой гармонического анализа стационарных непрерывных сигналов. Получаемые в результате преобразования коэффициенты Фурье поддаются достаточно простой физической интерпретации, причем простота ни в коем случае не умаляет важности последующих выводов о характере исследуемого сигнала. Применение интегрального преобразования и рядов Фурье в вычислениях и аналитических преобразованиях легко интерпретируется посредством действительных функций smf scosf (или одной комплексной - синусоидальной волны е =cosf + smM = V-1) и достаточно легко доказываются. Другой, не менее важной причиной популярности Фурье-анализа явилось наличие адекватной аналоговой элементной базы (RLC—цепочек), позволившее в свое время совершить существенный прорыв в теории и технологии связи. Язык Фурье-анализа является все еще языком «общей теории связи» и технологии построения систем связи.
И, несмотря на существенное превосходство цифровой технологии систем связи и явное несоответствие ключевых свойств целого ряда сигналов классической спектральной модели, ее популярность до сих пор остается преобладающей.
Тем не менее, возможности компьютерного моделирования требуют расширения математических моделей на нестационарные и степенные процессы.
Хотя все определения, свойства и их следствия приводятся для одномерных функций и рядов данных, при необходимости все сказанное может быть обобщено на многомерные случаи. Для определенности ниже будет говориться о функциях, зависящих от времени, о временных рядах и соответственно о частотах. Однако без нарушения общности независимая координата может быть пространственной (с соответствующими волновыми числами) и любой другой природы.
В классическом спектральном анализе сигнал во временной области удобно представлять в виде преобразования Шеннона, или разложения по S -функциям Дирака f{t)=\f{u)b{t-u)du (1-І) и соответственно его частотное представление или преобразование Фурье — не что иное, как разложение по комплексным экспонентам f(t)=\F(G )emtdG (1-2) Первая формула дает информацию о максимально возможном разрешении по времени: величина представляет интенсивность сигнала в момент времени . Никакая частотная информация при этом недоступна, простое поточечное представление не дает никакой информации о частотном содержании сигнала. Напротив, Фурье-представление дает точное частотное представление, не обеспечивая никакой информацией о временной локализации событий. На практике далеко не все сигналы стационарны. Пик в сигнале во временной области распространится во всей частотной области его преобразования Фурье. Можно провести аналогию с аудиозаписью. Ее временное представление позволяет нам знать ноты или паузы и слышать звенящий колокольчик. Напротив, частотное представление говорит, какие тоны присутствуют в музыке, не говоря ничего, в какой момент они могут быть услышаны.
Каждое из представлений содержит различного рода информацию о сигнале. Преобразование Фурье лишь на бесконечности является взаимнооднозначным отображением временного представления сигнала в частотное и наоборот. Однако в каждом из этих двух видов (временном и спектральном) представления сигнала доступна различная семантическая информация. Иными словами, распределение по импульсам Дирака имеет сколь угодно малое разрешение по времени, в то время как Фурье-спектр дает распределение по частоте. Отсюда возникает очевидная потребность представления сигнала одновременно по двум параметрам, при которых сохраняется вся информация, и лишь возможности компьютерного моделирования позволяют практически решать эти задачи.
Первые попытки частичного устранения неспособности анализа Фурье осуществлять временную локализацию сингулярностей сигналов заключались в применении оконного преобразования Фурье. В стандартное преобразование вводится умножение на так называемое окно w - движущуюся по временной оси функцию, имеющую компактный носитель. Использование оконной функции позволяет представить результат анализа - образ Фурье - в виде функции двух переменных, а именно частоты ю и времени т положения окна: F(CO,T) = )w(t - i)f{t)e-ja dt (1.3) или с учетом обозначения g(G),t) = w(t-l)e-M (14) следующим образом: F((0, t) = (s(co, t\f(t)) = Tg(co, t)f{t)dt (1.5) Однако введение оконных функций имеет существенный недостаток, который состоит в том, что ширина окна при данном виде анализа фиксирована и поэтому не может быть адаптирована к локальным свойствам сигнала. Возникают и другие дополнительные проблемы, уже не поддающиеся решению в рамках традиционного Фурье-анализа.
Динамическая модель дискретного пространства
Информация о типе текущего кадра включается в цифровой поток данных. Стандартом предусмотрено использование блочного кодирования. Кадры Р-типа могут содержать макроблоки Р и I типов, а кадры типа В — макроблоки всех трех типов В, Р и I. Кадры типа I содержат только I-макроблоки.
С целью пространственной декорреляции исходного цифрового потока его отсчеты представляют не во временной или пространственной областях, а в частотной. Таким образом, основная последовательность преобразования Y, CR,CBсигналов включает: ДКП, т. е. перевод отдельных блоков изображения (размером 8x8 элементов) из пространственной области в область пространственных частот; квантование (с коэффициентами квантования, устанавливаемыми отдельно для каждой из пространственных частот) и сжатие (используется модифицированный метод Хаффмана). Наряду с пространственной используется временная декорреляция смежных кадров или полей, чем достигается повышение степени сжатия при сохранении высокого результирующего качества изображения. Она реализуется с помощью ДИКМ (дифференциальной импульсно-кодовой модуляции).
В схему кодера обычно вводится полный декодер, формирующий реальный предсказанный сигнал. Этот сигнал, задержанный на время кадра, вычитается из входного сигнала. Используя формируемый разностный сигнал, удается устранить накопление ошибки квантования в восстанавливающем фильтре декодера. В кодерах, реализованных по стандарту MPEG-2, применяют предсказание с использованием векторов движения. Для этого изображение делят на макроблоки (16x16 элементов) и каждому отдельному макроблоку ставят в соответствие макроблок предыдущего (опорного) кадра, смещенный так, чтобы достигалась максимальная корреляция между ними. Эта пара подвергается ДИКМ. Величину смещения с учетом его направления называют вектором движения для рассматриваемого макроблока. Для достижения наибольшего сжатия учитывают корреляцию не только с предыдущим, но и с последующими кадрами. Для этого перед ДКП производят пересортировку кадров (изменяют порядок передачи кадров).
Изображение в стандарте MPEG-2 включает такие иерархические единицы, как блоки (8x8 элементов), макроблоки (16x16 элементов) и слайсы (строка макроблоков). В заголовках слайсов, макроблоков и блоков передается информация, необходимая для декодирования сигналов (коэффициенты квантования, сигналы синхронизации и др.). Стандарт MPEG-2 не только дает возможность передавать цифровые данные ТВЧ, но и обеспечивает возможность перехода к стандарту с числом строк 625. Для этого поток видеоданных разделяют на три: первый (основной), соответствующий 625-строчному разложению, второй, который несет недостающую информацию об изображении с числом строк 1250 и третий (дополнительный), обеспечивающий повышение результирующего отношения сигнал/шум в 1250-строчном изображении.
Цифровой поток стандарта MPEG-2 подвергается помехоустойчивому кодированию, вид которого зависит от используемого канала связи. При компрессии видеоданных реализуют ряд ступеней качества. Для передачи сигналов стандартного качества предусматривают цифровой поток до 15 Мбит/с. При 9 Мбит/с обеспечивается качество, сравнимое со студийным. Качество, сравнимое с получаемым в системе PAL, достигается при 6 Мбит/с.
Стандарт Н.261 специфицирует кодирование и декодирование видеопотока для передачи по каналу рх64 Кбит, где р=1...30. В качестве канала могут выступать, например, несколько телефонных линий [33].
Входной формат изображения - разрешения CIF или QCIF в формате YUV (CCIR 601), частота кадров от 30 fps и ниже. Используется уменьшение разрешения в 2 раза для компонент цветности.
В выходной поток записываются два типа кадров: INTRA — сжатые независимо (соответствуют I-кадрам) и INTER - сжатые со ссылкой на предыдущий кадр (соответствуют Р-кадрам). В передаваемом кадре не обязательно присутствуют все макроблоки изображения; если блок изменился незначительно передавать его обычно нет смысла. Сжатие в INTRA—кадрах осуществляется по схеме сжатия отдельного изображения. В INTER-кадрах производится аналогичное сжатие разности каждого передаваемого макроблока с "наиболее похожим" макроблоком из предыдущего кадра (компенсация движения). Для сглаживания артефактов ДКП предусмотрена возможность применения размытия внутри каждого блока 8x8 пикселов. Стандарт требует, чтобы INTRA-кадры встречались в потоке не реже чем через каждые 132 lNTER-кадра (чтобы не накапливалась погрешность кодирования и была возможность восстановиться в случае ошибки в потоке).
Степень сжатия зависит в основном от метода нахождения "похожих" макроблоков в предыдущем кадре, алгоритма решения, передавать ли конкретный макроблок, выбора способа кодирования каждого макроблока (INTER/INTRA) и выбора коэффициентов квантования результатов ДКП.
Автоматический режим
Необходимо отметить, что редукция изображения по количеству сегментов, согласно базовому алгоритму, допускает оптимизацию вычислений с комбинированной структурой данных [82], но выигрыш по времени достигается за счет неадекватного возрастания числа вычислительных операций.
Совокупность различных сегментов, получаемых на всех уровнях аппроксимации исходных данных в базовом алгоритме выделения объектов, является вариантом экспериментально обоснованного объектно-ориентированного представления и служит реальной основой комплексного решения проблемы анализа аудиовизуальных данных.
Многоуровневая модель - это своего рода алгебраический «конструктор», обеспечивающий аппроксимацию сигнала «деталями» различной формы и размеров. Детали способны сливаться друг с другом, что позволяет представить сигнал минимальным количеством частей. Детали конструктора в виде связных сегментов задаются как элементы последовательности разбиений сигнала (уровней), порождаемой базовым алгоритмом итеративной сегментации. В качестве начального уровня берется исходный сигнал, представленный наиболее мелким разбиением на отдельные отсчеты, либо используется любое другое разбиение сигнала на связные сегменты. Ограничений на форму и размеры рассматриваемых сегментов не накладывается. Каждый сегмент характеризуется средней амплитудой, которая выражается через характеристики, аддитивные относительно слияния сегментов, — интеграл амплитуды по числу отсчетов и число отсчетов. Пары сегментов характеризуются отношением смежности.
Уровни строятся последовательно. При фиксированном текущем разбиении находятся все смежные сегменты близкой амплитуды, затем путем слияния найденных сегментов из рассматриваемого разбиения получают следующее - с меньшим количеством элементов. Каждое новое разбиение от порядка слияния пар смежных сегментов не зависит. Уровни представляются наглядно, посредством усреднения амплитудных отсчетов в пределах укрупненных сегментов.
В порядке построения уровни индексируются неубывающими значениями параметра є. В [67] значение индекса є отождествляется с верхней границей минимальной разности средней амплитуды, встречающейся между соседними сегментами, и приписывается результату нескольких последовательных итераций переходного процесса достижения верхней границы при слиянии сегментов. Для простоты индекс є допустимо отождествлять с порядковым номером итерации. Тогда минимальная амплитудная разность с ростом є, вообще говоря, изменяется немонотонно.
Таким образом эмпирически найденный критерий є-идентифицируемости, позволяет реализовать процесс автоматизированного выбора є-слоя, достаточного для семантического распознавания. Что в свою очередь делает возможным создания методов сжатия данных, кодеков, методов распознавания основанных на концепции программируемой технологии и семантического анализа данных.
В разделе 2.1—2.3 было показано, что для эффективной обработки видеоданных, в том числе, для семантического анализа и компрессии наиболее подходит метод адаптивно-динамической сегментации, позволяющий организовать послойное представление изображения и селектировать семантические фрагменты на изображении. Возможны несколько вариантов реализации идеи АДС:
Дерево выстраивается, начиная от корневого узла, в котором s принимает максимальное значение, а все изображение состоит из 1 сегмента, последовательным итеративным уменьшением значения s [2]. Принцип формирования дерева АДС приведен на рисунке 2.15.
Процедура дизъюнктивной сегментации производится в следующей последовательности: для заданного начального значения s производится объединение в сегмент пикселов, удовлетворяющих критерию идентифицируемости. Каждый сегмент помечается уникальным идентификатором и для него создается новый узел дерева. Затем процедура рекурсивно повторяется для каждого сформированного сегмента, при этом все узлы сегмента становятся потомками узла, соответствующего сегменту предыдущего уровня (є + Ає) и объединяющего сегменты-потомки. Достоинства алгоритма: простота построения дерева, возможность реализации в виде простой рекурсивной процедуры. Недостатки: возможны искажения полученного результата за счет упрощения построения дерева.
Оценка качества передачи видеоданных
Общепринятая традиционная оценка качества восприятия телевизионной картинки основана на использовании СКО, PSNR и других интегральных критериев, в основе которых лежат энергетические характеристики интенсивности излучения пикселов.
Распознавание и идентификация объектов последовательно опирается на селекцию и идентификацию на изображении семантических объектов. Под идентификацией в данном случае понимается присвоение выявленному фрагменту на изображении семантики-имени объекта. Оператор в процессе селекции и семантической идентификации присваивает ассоциативные метки-имена — результат процесса наблюдения, восприятия и распознавания. Автоматические системы, решающие проблемы распознавания, прежде всего, должны быть ориентированы на процесс семантической селекции и идентификации распознаваемых объектов.
Для объективной оценки эффективности разработанных методов в работе используется величины СКО и PSNR (peak signalo-noise ratio) - пиковое отношение сигнала к шуму, которое обозначает соотношение между максимумом возможного значения сигнала и мощностью шума, искажающего значения сигнала. Поскольку многие сигналы имеют широкий динамический диапазон, PSNR обычно измеряется в логарифмической шкале в децибелах. PSNR наиболее часто используется для измерения уровня искажений при сжатии изображений. Проще всего его определить через среднеквадратичное отклонение (СКО), которое для двух монохромных изображений I и К размера щхп, одно из которых считается зашумленным приближением другого, вычисляется так: где MAX/ - нормировочный коэффициент - максимальный размах амплитуды, заданный разрядностью изображения. При разрядности пиксела 8 бит, МАХ/ = 255. Типичные значения PSNR для сжатия изображений лежат в пределах от 30 до 40 dB. Большему значению PSNR соответствует лучшее качество изображения на фоне шума.
Для цветных изображений с тремя компонентами RGB на пиксел применяется такое же определение PSNR, но СКО считается по всем трем компонентам (и делится на утроенный размер изображения).
Тестовая оценка восприятия использует разрешающую способность восприятия контуров (интенсивности, яркости, цветности) глазом (рис. 4.6).
В качестве операторного критерия семантической идентификации позволяющего осуществлять оценку качества передачи видеоданных, используется фрактальный подход. В этом случае, критерий качества есть функция от числа итераций, используемых для построения сложной цветовой фигуры. Операция идентификации осуществляется на основе сопоставления по критерию є-идентифицируемости, так при є=0 имеем уникальную идентификацию (например по штрихкоду). Примером использования операции идентификации неразличимости является, разработанная для оценки качества телевизионных каналов, фрактальная таблица (рис. 4.6).
Эта таблица позволяет определить информационную избыточность формата передачи изображений, эффективность и корректность работы алгоритмов компрессии видеопотока. Таблица представляет собой изображение итеративной функции, заданной начальными параметрами и состоит из 4 квадрантов, на каждом из которых функция построена с разным количеством итераций (50, 100,150, 200).
В качестве альтернативы для оценивания качества восприятия разработан фрактальный подход сопоставления семантического критерия узнавания с разрешающей способностью пиксельного восприятия. В качестве теста предлагается таблица, состоящая из четырех квадрантов. Исходное изображение является множеством Жюлиа, построенным итеративно при различном числе итераций для четырех квадрантов [87].
Каждый квадрант является эквивалентом исходного фрактала при загрублении его с СКО=5 и при этом он имеет /итераций, тогда S 60 40 20 0 I 50 100 150 200 Информационная избыточность формата оценивается как отношение размера кадра, представленного в формате, к известному размеру параметров, требуемых для построения этой функции. Качество передачи изображения каждого из квадрантов позволяет оценить уровень потерь при использовании форматов компрессии с потерями. Это табличная форма оценки (идентификации) адекватности семантического восприятия квадрантов, при которой производится не по-пиксельное сравнение на базе критерия СКО, а комплексная оценка целостного восприятия объекта.
Для изображений, содержащих семантику, всегда существует возможность значительной их компрессии. Подход АДС обеспечивает резкое уменьшение количества семантических фрагментов с увеличением значения є-идентифицируемости. Критерий качества представления изображения относится к каждому є-слою, который отображает исходное изображение с определенной є-разрешающей способностью.
Использование критерия адекватности семантического восприятия позволяет непосредственно оценивать изображение, в то же время использование семантического критерия дает возможность получения объективной (безоператорной) оценки и привязки его к значениям величины СКО.