Содержание к диссертации
Введение
Глава 1. Исследование и разработка функциональных моделей описания объектов видеонаблюдения 8
1 Выделение основных категорий, последовательности стадий и особенностей
обработки видеоинформации 8
1.1.. Выделение особенностей обработки видеоинформации 9
1.2. Определение технологического цикла обработки видеоинформации и формирование условий выделения объектов 14
2.Исследование и разработка алгоритмов регистрации активности задачах видеонаблюдепия 19
2.1. Анализ принципов функционирования традиционного алгоритма детектора движения 20
2.2. Исследование параметров и возможностей настройки алгоритма регистрации активности 23
2.3. Разработка методов улучшения характеристик алгоритма регистрации активности 26
3. Исследован не и разработка алгоритмов выделение силуэтов 34
3.1. Исследование возможностей выделенная силуэта методом вычитания фона 35
3.2. Разработка алгоритма выделения силуэта с использованием волнового метода 38
4. Анализ возможностей математических моделен описания силуэта для представлення объекта видео наблюдения 43
4.1. Определение и назначение векторизованого представления растрового изображения 43
4.2. Исследование возможностей интерполяционных моделей для описания формы объекта 47
4.3. Оценка погрешности липеаризационного приближения контура 53
4.4. Исследование возможностей моделей аппроксимации контура методом наименьших квадратов и преобразования Хафа 57
4.5- Обсуждение возможностей математических моделей приближенного описания силуэта для представления объекта объекта 59
Глава 2. Формирование модели выделения структуры области силуэта и исследование информационных свойств точек 63
1. Определение топографии силуэта и разработка алгоритма ее формирования 63
1.1. Обоснование формулы расчета топографии силуэта 65
1.2, Волновой алгоритм нахождения топографии 69
1.3. Определение возможностей топографии при анализе информационных свойств точек области 75
2. Определение места и роли базовых точек в структуре произвольной области силуэта 79
2.1. Исследование методов отыскания позиций размещения базовых точек 79
2.2. Уточнение диаграммного описания в случае произвольной области силуэта 84
2.3. Исследование алгоритмов построения структуры области силуэта в виде правильного остовного дерева 87
2.4. Разработка процедуры восстановления контура по структуре области 92
3. Особенности выделения структуры области на растре 95
Глава 3. Разработка и исследование структуры изображения па основе скелстизации 102
1. Разработка алгоритма скелетизации методом постепенной детализации срезов 104
1.1. Описание основных принципов построения скелета изображения 105
1.2. Реализация алгоритма на псевдоязыке 110
1,3 Преимущества и недостатки алгоритма скелетизации 115
2. Определение взаимосвязи скелетной структуры с диаграммным описанием области 118
3. Разработка методов выделения характеристических точек на скелете 126
4, Разработка автоматно-лингвистнческих, параметрических, спектральных моделей и теоретических основ алгебраического описания скелетных линий 135
4.1. Разработка автоматно-лннгвистических, параметрических и спектральных моделей скелетных линий 135
4.2. Разработка теоретических основ алгебраического описания и показателен сравнения скелетных линий 145
Глава 4. Разработка методов формирования и распознавания информационного образа схемы объекта и сцены на основе скелетного представления изображения 152
1. Разработкам исследование операций регуляризации скелетных линий 152
2.Разработка методов оценки и снижения рассогласования исходных и регуляризованиых скелетных линий 164
3. Разработка методов формирования информационного образа-схемы объекта на основе регуляризованиых линий скелета 169
3.1 Разработка теоретических основ алгебраического описания соединения регуляризованиых линий скелета в информационный образ-схему 169
3.2. Разработка алгоритма формирования описания информационного образа-схемы. 175
4. Разработка методов оценки похожести и средств распознавания информационных образов-схем 181
4.1. Определение показателей сравнения двух информационных образов-схем 181
4.2. Разработка алгоритмического аппарата и информационной компоненты сопоставления образов-схем 192
4.3. Экспериментальное исследование возможностей алгоритмического аппарата сопоставления образов-схем 195
Заключение 207
Литература 209
Приложения 217
- Определение технологического цикла обработки видеоинформации и формирование условий выделения объектов
- Исследование возможностей интерполяционных моделей для описания формы объекта
- Волновой алгоритм нахождения топографии
- Описание основных принципов построения скелета изображения
Введение к работе
Ускорение развития мирового научно технического прогресса в сочетании с присушим человечеству стремлением сохранить свой научный и культурный опыт дія будущих поколений па сегодняшний день уже нельзя считать единственными факторами» порождающими глобальный рост информационных ресурсов. Появление новых технических средств записи и сохранения данных, из условия реализации информационного процесса превращаются в катализатор, стимулирующий ускорение лавинообразного роста информации.
Новые информационные средства расширяют формы представления информации; обеспечивают подготовку информации со скоростью ее образования; минимизируют физические размеры информационных носителей практически до молекулярного уровня; способствуют самим своим появлением распространению и повсеместному внедрению информационных технологий в современную жизнь.
Вместе с тем, всесторонняя информатизация современного общества, становится во многом вынужденной мерой, направленной иа защиту и повышение стабильности современного, чрезвычайно уязвимого мира. Реальность таких угроз как вероятные последствия глобальных катастроф природного или техногенного происхождения, терроризм или международная напряженность,- однозначно указывает па необходимость информационного мониторинга всех узловых точек, процессов или явлений современного мира.
В тоже время, очевидно, что любая информация лишь тогда становится ценной, когда в дштьнейшем она оказывается востребованной. Получаемая информация должна быть применена Например, должна аккумулироваться в новых знаниях об окружающем мире или стать исходными данными, на основании которых производится формирование решений. Однако в этом плане достижения научно-технического прогресса видятся значительно менее впечатляющими.
Парадигмой современной информационной обработки является обязательное наличие в этом процессе человека, в функции которого как раз и входит решение основной задачи - воплощения информации в управляющих решениях или знаниях па основании анализа исходных, практически первичных (не агрегированных) данных. Но ввиду того, что производительность человека оказывается несопоставимо более низкой по сравнению с техническими возможностями средств подготовки и накопления данных, опасность углубляющегося разрыва в развитии технических средств и современных технологий интеллектуализации информационной обработки - трудно переоценить.
Все сказанное в полной мерс относится и к видсинформации, которая наряду с лексическими данными (текстами, гипертекстами, таблицами) и аудиоданными составляет основную часть наполнение информационной сферы [41].
Среди коммуникационных форм видеоинформация отличаются едва ли не самыми большими диспропорциями в развитии, а работа с видеоданными относится к разряду наиболее сложных областей интеллектуализации машинной деятельности. В современном мире видеоинформацию одновременно характеризует исключительно широкая распространенность в сочетании с достаточно скудными на текущий момент возможностями в плане автоматизации процессов машинного понимания: распознавания, классификации, трансляции и перевода в другие коммуникационные системы.
Видеоинформация является наиболее информативной формой описания. Вместе с тем, эту форму отлипает также смысловая избыточность [7, 42, 100] и большие объемы представляющих информацию данных (к тому же, сложно поддающихся сжатию [103, 33]).
Формирование видеоданных, происходит в реальном времени протекания процесса (или во времени, масштаб которого всегда кратен реальному времени), т.е. эта форма является наиболее удобной для мониторинга любих реальных процессов (формирования видеонаблюдепий).
Перечисленные особенности н текущие возможности применения видеоинформации, определяют актуальность исследований, посвященных вопросам интеллектуализации обработки этой исключительно перспективной коммуникационной формы взаимодействия человека и машины.
Для человека видеоданные, по сути, являются, главным источником получения информации об окружающем мире. Известно, что около 80-85% от всей информации поступает к человеку через органы зрения.
В культурном наследии человечества к разряду видеоинформации помимо всевозможных рисунков, схем и картин (от наскальных до компьютерных) относится вся фото кино и видео продукция. На сегодняшний день даже только оцифрованные видеоданные (т.е. картины, рисунки, схемы, фотографии, фильмы и голограммы в электронном представлении) составляют практически большую часть машинных мировых информационных ресурсов, по крайней мере в побайтном выражении. В настоящее время только форм электронного представления видеоинформации насчитывается несколько десятков (tif, jpg, bmp, gif, mpeg и т.д.). Причем за счет постоянного совершенствования процессов записи и хранения видеоинформации количество форм представления постоянно увеличивается.
Представление информации в виде изображения является для человека наиболее быстро и эффективно воспринимаемой формой. В подтверждении этого факта достаточно обратить внимание на то, что повсеместно указатели, требующие быстрой и однозначной реакции человека, обозначают упрощенным (символическим) рисунком. Примером могут послужить изображения пиктограмм - «иконок» рабочего стола Windows. Другим частным, но важным примером компьютерного применения быстрой воспринимаемости ви-дезинформации можно назвать исключительно эффективные по скорости разработки информационные технологии визуального программирования, общим подходом в которых является то, что будущий результат программирования зрительно представляется пользователю в виде некоторого настраиваемого прототипа.
Но, несмотря на все выше сказанное, видеоданные не становятся основной формой коммуникационного общения ни среди людей, ни в межмашинном обмене, ни во взаимодействии человека с машиной. При этом все перечисленные типы информационного взаимодействия с применением видеоданных, как правило, носят ассиметричный характер, выражающийся в том, что представление информации видеосредствами осуществляется, как правило, одной из сторон диалога - докладчиком или рассказчиком, стремящимся донести до других участников большой массив данных. При этом вторая сторона диалога, выражая свое отношение к полученным данным, может пользоваться в общении другими средствами передачи информации: звуковыми, лингвистическими, мнемоническими и т.д. Заметим, что если в диалогах между людьми односторонняя направленность потока видеоданных объяснима неодинаковой способностью людей к быстрому воспроизведению графической информации (при наличии общей для всех людей способности к быстрому восприятию зрительных образов), то в межмашинном или человеко-машинном диалоге основным препятствием двухстороннего видеообмспа, наоборот, выступает как раз отсутствие у машины достаточно общих способов реализации восприятия смысла видеоданных (при наличии способности к машинно-ориентированному храпению и воспроизведению видеоданных) [117].
Семантика видеоданных - контекстна [10, 74], т.е. определяется фреймом, кадром или сценой, в рамках которой происходит подлежащее распознаванию смысловое действие. И если на сегодняшний день говорить о распознавании смысла произвольных (пускай даже реальных сцен), по-видимому, преждевременно, то практическая ценность алгоритмов распознавания поведения людей в конкретной обстановке - не вызывает сомнения- В дальнейшем видеоданные поведения людей в конкретной обстановке с неизменным местом действия, фоном и освещенностью будем называть сценами с предопределенной ситуацией, указывая на ограниченный характер разворачивающихся в этих сценах реаль ных действий. Например, к таким сценам можно отнести видеонаблюдсния охранных систем; в местах общественного пользования (в подъездах и вестибюлях, в холлах и переходах, на лестничных маршах, и т.д,) и на транспорте (в кабинах лифтов, в вагонах, на эскалаторе и т.д.) а также большую часть информации, с которой работают системы «интеллектуального дома».
Особенностью, облегчающей обработку видеоданных в предопределенных ситуациях, является возможность выделения находящихся на переднем плане объектов действия путем «вычитания из сцены» неизменных деталей.
Целью диссертационной работы является разработка и исследование алгоритмического аппарата обработки видеоинформации, распознавания объектов и сцен в предопределенной ситуации.
Предметом исследования работы стала разработка и оценка возможностей программных и математических моделей, описывающих процессы обработки видеоданных, возникающие и системы видеонаблюдения в связи с решением задач распознавания образов и сцен с участием живых объектов (людей) в предопределенных ситуациях. Достижение указанных целей предполагает решение следующих задач
В соответствии с указанной целью, в диссертационной работе решаются следующие задачи:
• анализ существующих методов и проблем обработки видеоданных с целью выделения информации и разработки функциональной схемы работы автоматизированной системы видеонаблюдения;
? построение аффективных алгоритмов и методов выделения объектов па стадии первичной обработки видеоданных;
? разработка последовательности алгоритмов выделения информации о внутренней структуре объектов наблюдения (людей) и исследование особенностей применения алгоритмов формирования информации о структуре объекта на основе построения «топографии» силуэта объекта;
• разработка алгоритмов и исследование свойств «скелетного» представления объектов, разработка математических моделей формы записи скелета объекта в виде информационного образа-схемы (ИОС);
• разработка методики, алгоритмического аппарата и информационной компоненты сравнения ИОС объекта с набором эталонных - образов личин, выражающих элементы невербальной информации об объектах живой природы;
проведение программных экспериментов и обработка результатов с целью выявле ния возможностей разработанного алгоритмического аппарата и выделения показателей оценки сравнения ИОС. Основные положения, выносимые на защиту разработанный метод описания структуры силуэтного изображения объекта, формируемого на основе поверхности топографии;
алгоритм формирования скелетного описання структуры объекта; методы регуляризации скелетных линий и построения информационного образа -схемы объекта;
метод сопоставления двух ИОС с целью выделения информации об объектах и сцене.
Определение технологического цикла обработки видеоинформации и формирование условий выделения объектов
Выделению смысла из видеоданных достаточно сложный н многоэтапный процесс обработки результатов видеонаблюдения. Ниже последовательность обработки видеоинформации приводится для типового технологического цикла преобразования, видеоданных связанного с выработкой решений в автоматизированной системе видеопаблюдепий.
Любую автоматизированную систему видео наблюдения можно условно представить в виде ряда программно-аппаратных модулей, взаимодействующих друг с другом. Основным элементом системы, безусловно, являются аппаратные устройства наблюдения — видеокамеры. Помимо камер, осуществляющих наблюдение в оптическом диапазоне, в современных охранных системах могут также применяться вспомогательные устройства, такие как инфракрасные дальномеры, датчики изменения объема, микрофоны, детекторы движения. Кроме того, наибольшей эффективности можно достичь, интегрируя подобные системи в комплекс, объединяя их с системами пожаротушения и контроля/ограничения доступа. Поэтому, к перечисленным выше устройствам съема информации также добавляются датчики, реагирующие на задымленность помещения и всевозможные консоли, кодовые замки, шлюзовые камеры, передающие данные о личности объекта наблюдения, времени и месте его перемещения.
Другим обязательным элементом системы наблюдения являются устройства представления информации или устройства оповещения. Для информации, поступающей от камер видео наблюдения — это совокупность всех мониторов, пользовательских интерфейсов и консолей наблюдения, транслирующих полученные видеоданные и дающих воз-можность оператору регистрировать события, происходящие (или происходившие) на охраняемом объекте.
Охранная система может быть оснащена механизмами реагирования (например, в системах ограничения доступа - ато запорные механизмы, в системе пожарной безопасно-сти — устройства пожаротушения). Для комплекса наблюдения элементами реагирования могут также являться устройства оповещения и механизмы управления устройствами ввода/вывода информации.
До недавнего времени все охранные системы наблюдения реализовывались на основе совокупности описанных модулей. Однако все большую популярность в технологиях безопасности находят автоматизированные системы, основным отличием которых от традиционных систем является наличие нового элемента - интеллектуального программного комплекса обработки информации.
Автоматизированный комплекс обработки видеоинформации позволяет переложить часть функций человека-оператора на вычислительные ресурсы системы. Программно реализованные алгоритмы распознавания образов осуществляют семантическую обработку наблюдаемых видеоданных, выделяют из изображения объекты наблюдения, классифицируют их и обеспечивают принятие решения на основе полученных данных. В зависимости от результата обработки и его важности для системы в целом, решением автоматизированного комплекса может быть либо сигнал, привлекающий внимание оператора, либо непосредственно команда механизмам реагирования. Простейшим примером интеллектуального программного комплекса обработки видеоинформации, получившим, тем не менее, широкое распространение в современных системах охранного телевидения, является детектор движения [120, 121].
Полный цикл комплекса обработки видеоинформации можно разбить па ряд последовательно выполняемых стадий (рис. 1.1), целью которых становится максимальное упрощение видеоинформации, не приводящее к потере заложенного в ней смысла. Так, при поступлении данных с видеокамер необходимо произвести графическую обработку информации. Цель такой обработки - максимальное улучшение качества поступающего изображения. На данном этапе применяются алгоритмы очищения видеоданных от различных помех и «шума» [50, 70], вызванных как некачественными условиями видеопаблюде-ния, так и в ходе активного противодействия [115, 111]. На этой стадии используются как алгоритмы сглаживания, автофокусировки, фильтры цветокалибровки и т.д. [17, 59, 114], так и более сложные интеллектуальные методы обнаружения шумовых сигналов [47, 90, 98]. Результатом работы первого блока алгоритмов является поток видеоданных, наилучшим образом подготовленный для последующего анализа изображений, выделения на них объектов и распознавания образов.
В таком виде изображение поступает на вход блока алгоритмов первичного выделения информации. Основной целью функционирования данного блока является уменьшение объема обрабатываемой информации и выделение из общего потока данных только той информации, которая в последствии будет востребована алгоритмами распознавания образов. На этапе первичного выделения информации происходит
Исследование возможностей интерполяционных моделей для описания формы объекта
Построение машинно-ориентированных способов выделение смысла из видеоданных связано с проведением структуризации видеоинформации, упрощением представления о выделяемых объектах и построением формальных механизмов их типизации. В частности далее сформулируем ряд упрощающих предположений, действие которых будет распространяться на распознаваемые сиены. I. Первым в ряду упрощающих предположений назовем положение о том, что любой выделяемый объект представляется единственной односвязной областью. Сделанное предположение является верным для широкого класса объектов, расположенных на перед нем плане монохромных контрастных сцеп, где информация фона не важна (или заранее известна). В условиях предположения I понятия области, представляющей объект, смыка ется с понятием силуэта, а сам силуэт однозначно определяется контуром, II. Вторым предположением, на котором будут основываться дальнейшие построе ния, является принцип с относительного позиционирования па объект». Субъективность формулировки данного предположения требует определенных разъяснений. Силуэт объекта, занимающий некоторую область кадра, помимо яркости (и цвета) образующих пикселей, отличает форма и положение в кадре. Исходя из ограниченности экспозиции формирующих видеоинформацию камеры или человеческого глаза, для областей, выходящих за пределы обзора, можно полагать дополнительной замыкающей частью контура-границы кадра. Таким образом, не ограничивая общности, можно считать любой контур объекта всегда замкнутым.
Силуэт задает информацию о присутствии объекта в зоне обработки, его геометрических размерах, а при наличии нескольких последовательно взятых кадров видснаблюдения - скорости перемещения.
Положение силуэта в кадре, обычно определяется позиционированием некоторой (любой) точки силуэта, относительно которой имеется возможность однозначно установить расположение всей области объекта внутри кадра. В дальнейшем точку позиционирования силуэта, позволяющую установить положение внутри кадра соответствующего итой области объекта, будем называть базовой. Например, в качестве базовой точки может быть использована любая точка границы области, относительно которой выстраивается весь контур. В человеческом восприятии такой характеристике, как расположение базовой точки области, наиболее полно отвечает понятие «брошенного (па объект) взгляда». Уточняя это понятие, заметим, что нередко взгляд не охватывает рассматриваемый объект целиком. Например, подобная ситуация возникает при рассмотрении близко расположенного крупного объекта. В составе человеческого восприятия объекта наряду с реально видимыми деталями присутствуют «додуманные» элементы. Произвольно (или систематично) сканирующий поле зрения взгляд останавливается па наиболее характерных или информативных фрагментах объекта, дополняя невидимые детали присущими данному «узнанному» объекту элементами.
Известной психологической особенностью человеческого восприятия является его адаптируемость, проявляющаяся в том, что взгляд позиционируется на некоторых, наиболее характерных, выдающихся (потенциально опасных или привлекательных) деталях известных объектов, а при отсутствии таковых «останавливаясь в центре области» в позиции наиболее удаленной от границ области. При этом у большинства людей, по мере удаления от точки позиционирования к границам области, отображающей объект, уровень детализации восприятия понижается. Можно сказать, что при отсутствии специально привлекаю щих точек, позиционирование взгляда шцентре _о.бъекта диктуется соображениями о получении более полной целостной и всесторонней картины объекта. Априорно предполагая выпуклость наблюдаемых объектов, человек (а отсутствии целсуказущих соображений) обращается внимание на пик выпуклости объекта, предполагая его расположение в середине представляющей объект области. Описанная избирательность человеческого восприятия часто используются в профессиональных целях иллюзионистами, дизайнерами, модельерами и т.д., для привлечения внимание зрителей к определенным демонстрируемым частям объекта или, наоборот, для отвлечения внимание от скрываемых частей. Указанная особенность человеческого восприятия в последнее время находит широкое применение при архивации («сжатии») файлов видеоданных, например, с использованием фракталов [21, 103] или в форматах JPEG/MPEG [96, 97, 9S], где периферийные элементы картинки сохраняются в видеоданных в упрощенной форме, занимающей меньше места.
При машинно-ориентированном выделении информации внутри кадра названный принцип «относительного позиционирования на объект» содержательно могут определить следующие два правила положение объекта, описываемого одной замкнутой областью, внутри кадра устанавливается некоторой «свободно» выбираемой базовой точкой, расположенной внутри области, в позиции наиболее удаленной от всех границ; H.2. описание формы области задается расстоянием до границ области относительно выбранной базовой точки.
Выбор базовой точки, имеет относительный характер, т.к. позиционирование хотя и не зависит от ракурса объекта по отношению к наблюдателю, ио, очевидно, выражает положение объекта в составе экспозиции, а для известных объектов - возможно также может зависеть и от особенностей самого объекта. Указанную в правиле (II 1) свободу выбора базовой точки следует понимать аналогично позиционированию человеческого взгляда, в том смысле, что выбор базовой точки сходен с тем, как человек обращает свой взгляд, например, в сторону источника заинтересовавшего его звука, приближенно предполагая его координаты и не интересуясь (по крайней мере в первый момент) как расположен соответствующий объект. При этом, если предполагаемый объект наблюдения известен (например, это другой человек, желающий вступить Б разговор), то точкой позиционирования скорее всего станут глаза собеседника. В противном случая, точкой позиционирования может стать любой другой фрагмент объекта предположительно характерный для него или точка в середине области объекта.
Необходимо заметить, что при машинно-ориентированном выделении информации из видеоданных, относительная произвольность выбора точки позиционирования связана не с субъективностью восприятия, а с техническими возможностями средств видеонаблкь деиия, а также с функциональным назначением системы видеонаблюдения.
В самом простейшем случае, при проведении видеонабл юлений с помощью пеориен-тируемой камеры, базовая точка может выбираться (например, па основании регистрации движения) лишь предположительно внутри области, описывающей объект. При наличии технической возможности ориентации камеры и связанных с пси устройств (центрировании точки фокуса) выбор базовой позиции может быть произведен более рационально. Так для получения наиболее целостной картины об объекте наблюдения точку позиционирования целесообразно выбирать внутри соответствующей объекту области наиболее удаленной от всех границ.
Волновой алгоритм нахождения топографии
Про точки растра монохромной области, представляющие объект в виде силуэта, можно сказать, что информация об объекте содержится в граничных точках контура, по сравнению с которыми внутренние точки области «в плане информативности кажутся менее ценными». Исследуем далее этот вопрос с учетом такой характеристики как функция топографии.
Приведенные в главе 1 описание технологической последовательности обработки видеоданных, а также анализ эффективности математических методов определения формы объекта, показывают, что на практике информационную ценность точек контура снижают присущие атому способу описания области недостатки неточности и многозначности, которые, по-видимому, имеют неустранимый характер.
Качество выделения границ области силуэта, которое само по себе является сложной инженерной задачей, существенно зависит от целого ряда нерегулярных факторов, таких как освещенность объекта, резкость изображения и т.д. В общем случае выделение точек контура силуэта па любом изображении a priori нельзя считать тонным- Поэтому в отсутствии достоверной теории, сопоставляющей уровень неточности выделения с возникающими из-за этого смысловыми потерями, точки контура нельзя считать информационно соответствующими целям и задачам распознавания.
Опыт построения математического описания контура указывает на то, что информацию об объекте несут не сами точки контура, а их взаимное расположение (точнее отношение, в котором находятся соседние точки контура). Таким образом, даже при ограниченном количестве способов расположения соседних точек, количество вариантов его построения контура будет описываться показательной функцией от числа используемых точек. Описание области силуэта с помощью контура оказывается слишком многозначным и сложным для целей построения машинно-ориентированных процедур выделения смысла (даже, если ие принимать в расчет возможные неточности, связанные с процессом выделения контура).
Заметим также, что, по-видимому, причина сложности и многозначности описание силуэта с помощью граничных точек области кроется ие столько в слабости используемых для этих целей математических моделей, а скорее в самой природе контурного описання объекта. Например, представленные в работах [75, 104] лингвистические (формально языковые) модели описання формы контура па основе аппарата формальных грамматик также чрезвычайно усложняются в случае фигуры сколько-нибудь общего вида,
В составе растра изображения точки контура определяются одна относительно другой, выражая логику «последовательного», относительного описания по цепочке, при котором положение любого фрагмента фигуры определяется относительно одного или нескольких ближайших соседних элементов той же фигуры (а положение тех относительно ближайших к ним элементов и т,д.),
В человеческой логике для описания зрительного восприятия фигур и линий наряду с «относительным подходом», существует также подход, использующий протяженность, при котором положение любого элемента фигуры описывается в терминах удаленности и направления от некоторой заданной для всех элементов базовой точки (или нескольких заданных точек, образующих репер) [9, 31],
Например, расположение точек Л и В на рис 2.1 .в относительных терминах может звучать следующим образом: «тонка В находится левее точки С, которая находится левее и выше точки А» или «точка В находится левее и выше точки С которая находится левее точки А», А в терминах протяженности, тоже описание может звучать так: кточка В от точки Л находится левее на 2 ячейки и выше па /ячейку».
Очевидно, что в языковой практике оба способа трансляции зрительных образов равноправны. Однако описание в терминах протяженности более короткие. Например, достаточно сравнить описание расположения точек Л и D па рис 2, К в относительных терминах и в терминах протяженности. Вместе с тем, описание в терминах протяженности неявно подразумевает расположение объектов видеонаблюдсния в метрическом пространстве, как для описания в относительных терминах достаточна лишь частичная попарная измеримость математические подходы к описанию формы области с помощью методой штерл&адия (линеаризации), аппроксимации и векторизации точек хошури, хотя її представляет собой описание Б терминах протяженности, тем не менее, из-за аепрерьшшсти моделей пеелш в себе недостатки сложности (мнотозна шо-іти) и приближенности,
С тих ііозиі 1ий рассмотрим далее взшчадьпо дискретный объект топоф&фию области. Так как люйая линии уродил в тшнмрафин соеттп ИЗ точек, с одинаковым минимальным расстоянием до ірщщц облаєш, ю Ї плаце задач описания объекта тошл рафия становится инструментом перевода ошоеителышш оішешшн контура в термины протяженности. Расположенные ни лилии уровня юпографии внутренние ТОНКІЇ области (отди-чшопшеся одинаковым минимальным расстоянием до границ области) «повторяют неведение б;шжайпшх к ним граничных точек.
Тогда среди внутренних тчек области особый nmgpcv должны представлять тонкій минимальное расстояние я которых ;ю днух несмежных участков Гранины одинаковое. Таким топкям соответствуют «гребни или хребты» тшюірафнн. А также внутренние тачіси, расстояние в которых одинаковое до, более чем. ішук несмежных участков іршшцьі, В то-поірафии таких точкам соответствуют пики вершин, обладающие в некоторой одноевяз-ноіі области наибольшей высотой (локальные максимумы). заметим, что рошешіє чадячи отыскания локальных максимумов топографии оказывается связанным с возникающим в процессе век-торюаіщи определением простых ісомаршческш фигур, «гюкрываюпщк СОбОН исход-тдй еложнокоигурный еилу,п. Например, силуэт на рис.2 J а, в классе круговых фигур можег быть представлен конструкцией, отображенной щ ржЛ 7л. Для иого достаточно расположить фигуры- круга так, тш бы их центры совпадали с локальными максимумами области иилуэш. О лнаш. очевидно, что и общем слуїж, когда не оговорены ни форма представляемой области, ли представляющие ее фрагменты, такая задачи может оказаться шачлг&лыю бод е сложной.
Описание основных принципов построения скелета изображения
Особенностью скелета является то, что в отличие от точек контура, в информационном плане роль этих точек - неодинакова- Для точек, образующих скелет, принципиально важным .моментом являются не столько координаты их расположения, сколько их место на топографии области, т.е. роль, которая соответствует этим точкам в структуре области.
Исходя из того, что в описании информации о структуре области не всё точки скелета одинаковы, проведем их классификацию и выделим среди них подмножество терминальных точек
Достаточным условием, отличающим Терминальную точку, является наличие среди смежных к леи точек только одной точки скелета. Точка является терминальной и в том случае, если смежных к анализируемой точке две и они смежны между собой.
Ясно, что в произвольной невыпуклой области терминальных точек будет больше одной. Все остальные точки скелета, не принадлежащие к подмножеству терминальных точек, назовем точками скелетных линий. Таким образом, линией скелета будем называть упорядоченную конечную совокупность последовательно смежных между собой точек Xt =( ,у) скелета, первая из которых смежна одной из терминальных точек, а последняя - смежна другой терминальной точке, В связи с начальными и конечными точками скелетных линий будем также говорить, что данная линия ими ограничивается. Т.к. набор точек скелета с соответствующими переходами между смежными точками представляет собой дерево, то в составе точек любой из скелетных линий не бывает повторов точек. Исходя из неоднородности роли точек скелета при формировании структуры области, выделим в их совокупности подмножество точек, по которым область может Сыть описана в виде комбинации выпуклых подобластей, и построим по этим точкам структуру организации области. С этой целью определим на множестве точек скелета подмножество базовых точек, позиции которых при формировании представления исходной области в виде комбинации выпуклых подобластей, станут местом размещения диаграмм. В подмножество базовых точек войдут терминальных точек скелета, а также экстремумы топографии, среди точек линий скелета. По построению вес терминальные точки скелета - периферийные, т.е. являются позициями размещения диаграмм.
Сложнее обстоит дело с экстремумами скелетных линий, выделение которых будет рассмотрено ниже. Скелет; хотя и включает в себя все позиции потенциально возможного размещения базовых точек, сам по себе не является информационно достаточным для описания области в виде комбинации нескольких выпуклых подобластей, т.к. для его точек (кроме терминальных) нет указаний на то, является ли данная точка базовой для некоторой из подобластей данной области.
Иначе говоря, для каждой из точек скелетных линий необходимо выяснить, является ли соответствующая этой точке позиция местом размещения диаграммы, а также каков вид этой диаграммы. Необходимая (для представления области в виде комбинации подобластей) информация образуется при рассмотрении скелета совместно с топографией области. Задавшись для каждой скелетных линий некоторым способом последовательного просмотра соответствующих ей точек Xt - {ХІІУІ), назовем профилем ЛИНИИ функцию изменения топографии вдоль ее точек. Учитывая, что скелет является геометрическим местом точек, равноудаленных (в смысле кратчайшего пути до границ области) по двум и более направлениям, профиль несет н себе данные «о минимальной ширине области на траверзе соответствующей точки». Здесь, под траверзом скелетных линий подразумевается направление кратчайшего пути из точки линии к границам области.
Можно сказать, что большим значениям профиля соответствует большая окрестность области; перепад значений функции профиля вдоль некоторой пинии скелета означает локальное «утолщение» или «истоньшепие» контура на траверзе соответствующей точки и т.д.
Опираясь на приведенные соображения, определим (па основе данных об изменении топографии на точках скелета) порядок конкретизации базовых точек, по которым должно проводиться формирование описание произвольной области в виде комбинации выпуклых подобластей, а также установим способ построения диаграмм, соответствующих выбранным базовым точкам.
Конкретизацию состава базовых точек можно рассматривать как задачу отыскание локальных экстремумов профилей вдоль всех скелетных линий. Локальным максимумом (минимумом) линии скелета будем называть такую точку х в не нулевой окрестности, которой все имеющиеся точки х линии скелета меньше (больше) заданной, т.е. Э 0 Vx\x-x \ S f(x) f(x ).
Тле по построению точки скелета должны содержать локальные максимумы топо-і-рафии, точке локального максимума па профиле соответствует базовая точка локального максимума топографии, а точке локального минимума на профиле - седловая тонка на «перевале» топографии. Локальные минимумы профилей можно рассматривать как позиции пересечение линии скелета и линии перевала, образующей рубежные точки, отделяющие одну подобласть от другой (см. рис. 2.10).
Заметим, что приведенная интерпретация экстремальных точек профиля объясняет оправданность терминологического заимствование понятия траверза — как «направления перпендикулярного курсу». Для поверхности топографии, повторяющей в своих линиях уровня исходный контур области, линия скелета, ведущая к одной из точек локального максимума топографии (по направлению, перпендикулярному выпуклым линиям уровня) и линия траверза, определяющая кратчайшее расстояние к седло вой точкой топографии (по направлению, перпендикулярному вогнутым линиям уровня) —должны быть ортогональны.
Очевидно, что способ аналитического отыскания экстремальной точки функции через определение корней ее производной является не приемлемым в случае с функцией профиля. П связи с этим рассмотрим ниже возможные подходы к численному решению этой задачи. Определим важный с практической стороны класс унимодальных функций [34, 78]. Ограниченная снизу функция, у которой JC = argmin j f{x)» обладает свойством унимодальности на множестве [a,b], если для любых х! х2 выполняется одно из двух: пи6ох1 х2 хт = f(xl) f(x2); либо X х! х2 = f(xJ) f(x2) Т.е. унимодальная функция строго монотонно убывает слева от точки минимума х и строго монотонно возрастает справа (см. рис. 3,9а)- (При нестрогой монотонности можно говорить о нестрогой унимодальности). Аналогичное определение унимодальности может быть сформулировано и в случае максимума функции Заметим что, с учетом дискретного характера области определения, представленной линией скелета, под [а3Ъ] следует понимать упорядоченное односвязпое множество точек про любые две из которых (не занимающие одну и ту же позицию) молено сказать одно из Двух
