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

Тип работы:
Реферат
Предмет:
ТЕХНИЧЕСКИЕ НАУКИ


Узнать стоимость новой

Детальная информация о работе

Выдержка из работы

Begin
Write XML
Getiefate XML
-[по]-

fr& quot-]
T
?per XML
1
1 1
Close XML
End
[Triplet slfeam]
[XWL RDF]
б
а
Рис. 3. Алгоритм RDF Parser (а) — алгоритм XML Writer (б)
Заключение
В работе рассмотрены основные принципы решения задачи преобразования исходного кода на объектно-ориентированном языке программирования в формат RDF и предложен прототип архитектуры программного продукта решающего эту задачу. Программный продукт, основанный на предложенном архитектурном прототипе, может найти достаточно широкое применение при решении задач анализа кода, в экспертных системах и САПР.
Литература
1. Eric Miller. RDF Primer: W3C Recommendation // W3C [Электронный ресурс]. — Режим доступа: http: //www. w3. org/TR/rdf-primer/ (дата обращения: 20. 01. 10).
2. Context-free grammar // Wikipedia [Электронный ресурс]. — Режим доступа: http: //en. wikipedia. org/wiki/Context-free_grammar (дата обращения: 04. 02. 10).
3. Extended Backus-Naur Form // Wikipedia [Электронный ресурс]. — Режим доступа: http: //en. wikipedia. org/wiki/EBNF (дата обращения: 04. 02. 10).
4. Parr T. The definitive ANTLR reference: Building domain-specific languages / Terence Parr. — San Francisco- The pragmatic programmers, LLC, 2007. — 384 p.
Зараковский Алексей Владимирович Клименков Сергей Викторович
Ткаченко Никита Иванович
Харитонова Анастасия Евгеньевна
Санкт-Петербургский государственный университет информационных технологий, механики и оптики, студент, dbiryukov@list. ru Санкт-Петербургский государственный университет информационных технологий, механики и оптики, ассистент, Serge. Klimenkov@Servicom. Ru
Санкт-Петербургский государственный университет информационных технологий, механики и оптики, студент, n.i. tkachenko@gmail. com
Санкт-Петербургский государственный университет информацион-
технологии,
механики
ассистент,
Anastassia. Kharitonova@Elcom. SPb. Ru
ных
и
оптики
УДК 004. 627
АНАЛИЗ МЕТОДОВ ПОСТРОЕНИЯ ТРАЕКТОРИИ ДВИЖУЩИХСЯ ОБЪЕКТОВ НА ОСНОВЕ СЕГМЕНТАЦИИ ВИДЕОДАННЫХ
И.С. Рубина
Проведено исследование алгоритмов, основанных на сегментном подходе к решению задачи прогнозирования и компенсации движения. Этот класс методов устраняет большую часть недостатков решений на основе попиксельно-го подхода с высокой трудоемкостью алгоритма и объектного подхода со сложностью в определении формы объекта прогнозирования. В связи с тем, что полный перебор возможных вариантов прогноза для блока имеет высокую вычислительную сложность, в рамках данной работы осуществлена выработка оптимальной схемы селекции блоков
для сравнения. Также предлагается ряд усовершенствований существующих схем с целью улучшения соотношения вычислительная сложность/качество.
Ключевые слова: сегментный подход, траектория, объект, компенсация движения, селекция блоков, сравнение подходов.
Введение
Задача построения траектории движущихся объектов является неотъемлемой частью эффективных схем сжатия видеопоследовательностей. Выбор ее решения всегда является компромиссом между точностью приближения и вычислительной сложностью алгоритма.
Сегментный подход к решению задачи построения траектории движущихся объектов устраняет большую часть недостатков решений на основе попиксельного подхода с высокой трудоемкостью алгоритма и объектного подхода со сложностью в определении формы объекта прогнозирования [1]. Сущностью компенсации в нем является прямоугольный блок. Сегментный подход использует предположение о том, что в рамках двух соседних кадров местоположение и форма объектов изменяются незначительно. Тогда это изменение можно скомпенсировать параллельным переносом сегмента на некоторый вектор так, как показано на рис. 1. Это допущение работает для подавляющего большинства кадров видеопоследовательности, за исключением участков полного изменения кадра при переключении сцены [2].
схожий блок

41 У ^
1 IJm
s ш
Шлт
Г г 1
1 V 1 i s
у л ГГЦ
m й л ?
* ч * fIr & gt- I
iJM / f i
il* kKi / / -
компенсируемый блок
предыдущий кадр вектор движения текущии кадр
Рис. 1. Схема работы алгоритма
В связи с тем, что полный перебор возможных вариантов прогноза для блока (метод FS) имеет высокую вычислительную сложность [3], в рамках исследования необходима выработка схемы селекции блоков для сравнения.
Целью данной работы является анализ существующих методов построения траектории движущихся объектов на основе сегментации видеоданных и выработка способов их модификации.
Базовые положения исследования
Человеческое зрение обладает особенностью не отличать умеренно пониженное разрешение и менее точно представленное динамичное движение.
При поиске совпадений необходимо учитывать совпадения, найденные на более ранних стадиях решения задачи.
Необходимо осуществлять поиск глобального минимума критерия различия сущностей, препятствуя выявлению локального минимума вместо глобального.
Схемы алгоритмов в рамках исследования
Произведен анализ существующих схем построения траектории движущихся объектов на основе сегментации видеоданных. Были исследованы следующие схемы: полный перебор (FS), алгоритм «один за раз» (OTA), алгоритм ортогонального поиска (OSA), трехшаговый поиск (TSS), двухмерный логарифмический поиск (TDL), четырехшаговый поиск (FSS), иерархический поиск — метод усредненной пирамиды (MP).
Алгоритм FS (алгоритм полного перебора). Алгоритм предполагает перебор всех возможных вариантов прогноза для блока. Данная схема имеет высокую вычислительную сложность при максимальном качестве прогнозирования и может использоваться в качестве эталона для сравнения.
Алгоритм OTA (алгоритм «один за раз»). Алгоритм прост в реализации, но эффективен в поиске положения оптимального блока. На протяжении начального этапа алгоритма по горизонтали находится блок с минимальным отклонением, затем, начиная с него, минимальное отклонение ищется в направлении вертикали. Обязательным условием расширения области поиска является уменьшение величины
отклонения, иначе один из этапов алгоритма заканчивается. Схема работы алгоритма представлена на рис. 2, где блок А- минимум на горизонтальной стадии, а В — искомый блок компенсации.

и
В / А
С с г s & lt-



д


ы si il
a & amp- л

а, а а

j J J




si




il J il
ы si У
il J J il J J
и J
il il

J J J



J J J


ОТА




SI j
SI a
г il ш
?3 ?a a
il il j il j j

si

si j



OSA
TSS
a a 9
si j? j Я u
a a a
SI si SI

j J j il

j J j il

j J j





TDL FSS Порядок обработки
Рис. 2. Схемы работы рассматриваемых алгоритмов
Недостатком алгоритма является то, что в нем невозможно предсказать количество обрабатываемых блоков. Также необходимо учитывать тот факт, что функция ошибки компенсации почти никогда не бывает монотонной, часто имеет место множество ее локальных экстремумов, затрудняющих поиск глобального экстремума. Поэтому представляется целесообразным использовать алгоритмы с другими шаблонами.
Алгоритм OSA (алгоритм ортогонального поиска). Для уменьшения вероятности нахождения локального минимума вместо глобального используют алгоритм ортогонального поиска. Он решает задачу нахождения блока за конечное число шагов. Использует поочередно два шаблона, в процессе перемещая центр области в позицию блока с меньшим отклонением, с циклическим уменьшением плеча (рис. 2).
Ряд экспериментов показал, что использование этого шаблона также не устраняет вероятность случайных совпадений. Это приводит к необходимости использования алгоритмов многоточечных шаблонов.
Алгоритмы многоточечных шаблонов TSS, TDL, FSS.
— Алгоритм TSS (трехшаговый поиск) был разработан в 1981 году и до сих пор является популярным благодаря своей простоте, надежности и высокой производительности (рис. 2). Основная проблема алгоритма заключается в удаленности равномерно распределенных точек шаблона, что делает его неэффективным для областей малого движения.
— Алгоритм TDL (двухмерный логарифмический поиск) требует несколько большего количества шагов, но может быть более точным, особенно в случаях большого размера окна. В отличие от TSS, текущий центр области поиска включается в множество кандидатов. Условием уменьшения шага алгоритма является определение центра области блоком наименьшего отличия. На последней стадии алгоритма шаблон изменяется (рис. 2). Существует множество вариантов этого алгоритма, отличающихся условием смены шага шаблона, причем уменьшение шага вдвое не всегда является оптимальным решением.
— Алгоритм FSS (четырехшаговый поиск) основан на таком свойстве большинства видеопоследовательностей, как ориентированность к центру кадра. На первой и на последней стадии алгоритма используется девятиточечный шаблон, на двух остальных в зависимости от локации блока с минимальной функцией критерия выбирается один из шести шаблонов (рис. 2). Как правило, данный алгоритм показывает большую надежность с сохранением эффективности для сложных
вариантов движения и операций масштабирования. Это делает привлекательной стратегией для выборки блоков в схемах компенсации движения.
Алгоритм М Р (иерархический поиск — метод усредненной пирамиды). Для уменьшения сложности схемы полного перебора также были предложены схемы грубого иерархического поиска. Это сокращение достигается за счет компенсации на кадре меньшего разрешения. Примером таких алгоритмов является МР [4].
Вначале для устранения шумового эффекта изображение меньшего разрешения получают с помощью фильтра низких частот. В дальнейшем для получения многоуровневой иерархии изображений меньшего разрешения используется простое усреднение пикселей изображения предыдущего уровня по принципу
gL (p q) =
(i i
p + м, 2 p + w) Vu=0w=0 у
где gL (p, q) _ значение пикселя уровня L в позиции (p, q). Таким образом, если использовать три уровня иерархии, один пиксель уровня 2 соответствует блоку 4×4 уровня 0 и блоку 2×2 уровня 1 соответственно. В то же время, блок размером 16×16 уровня 0 будет соответствовать блоку (16/2L)x (16/2L) уровня L.
После построения усредненной пирамиды осуществляется подсчет среднего абсолютного отклонения (MAD) и выбор вектора, имеющего наименьшее MAD, в качестве грубого вектора движения 2 уровня. Найденный вектор перемещается на уровень 1, и производится его уточнение. Тот же процесс повторяется для уровня 0, на котором получается искомый вектор. Для увеличения точности работы алгоритма данная процедура может выполняться для нескольких векторов уровня 2, имеющих близкие значения MAD, c использованием окон (областей поиска) уменьшенного размера (рис. 3).
Таким образом, были выявлены существенные достоинства и недостатки методов отбора блоков компенсации.
Уровень 2 Уровень 1
Три точки
лучшего
совпадения
выбираются
центрами
окон на
уровне 1
Окна поиска
лучшего
совпадения
Уровень 0
Окно поиска лучшего совпадения, на основе которого строится целевой вектор движения
Рис. 3. Схема работы алгоритма иерархического поиска Экспериментальные результаты
В рамках проведенного исследования для алгоритмов, за исключением MP, использовались размеры блока 16xi6. В ходе экспериментов были получены следующие зависимости.
1. Количество базовых операций на блок для перечня кадров (0−20) для последовательности «Береговая охрана». В данном случае под базовой операцией понимается количество операций сложения/вычитания.
2. Усредненное среднее абсолютное отклонение (AMAD) — среднее по изображению MAD для перечня рассматриваемых алгоритмов:
MAD = -? |(FOrig (p) — Fcomp (q))|,
где тхп -размеры блока, а Forig (р) и FComp- значения интенсивности пикселя блока ссылочного
кадра р и интенсивности соответствующего ему пикселя блока-прогноза q компенсируемого кадра. 3. Среднее время процессора для перечня рассматриваемых алгоритмов.
35п 30 25 20 '- 15 10 50
1
11
номер кадра
16
230 220 210 200 2 190 180 170 160 150
11
номер кадра б
16
Рис. 4. Значения количества базовых операций (N) для ряда кадров последовательности «Береговая охрана» для перечня рассматриваемых алгоритмов: (а)---TSS--------TDL--FSS-----OTA-
--OSA- (б)--FS--MP
6
а
90 80 70 60 50 40 30 20 10 0
JSS
TDL FSS OTA OSA
MP
а б
Рис. 5. Значения среднего по кадру усредненного абсолютного отклонения (а) — значения времени процессора (б) для последовательностей: -¦- «Дети" — -¦- «Погода" — «Береговая охрана" —
-Х-«Акийо" — -^-«Телефон в машине»
Исследование подтвердило предположение о том, что увеличение трудоемкости алгоритма сопровождается улучшением качества его работы. Таким образом, большинство алгоритмов с высокой производительностью страдает недостаточным качеством работы схем компенсации, и наоборот. По количеству базовых операций наиболее интересен в анализе алгоритм OTA, показавший хорошие значения критерия на областях плавного движения (кадры 1−5 и 12−20) и чуть худший в динамичных сценах (рис. 4, а).
Самые лучшие показатели процессорного времени показал алгоритм OTA (рис. 5, б) при одном из худших уровней качества работы схемы компенсации движения (рис. 5, а). TDL не дал оптимальной схемы выборки, уступив OTA как с точки зрения качества, так и по части трудоемкости. Популярный среди разработчиков алгоритмов компенсации движения TSS значительно уступил OTA в плане вычислительных затрат. В свою очередь, алгоритм FSS превзошел TSS по вычислительной сложности при схожем качестве получаемого прогноза.
В ходе исследования было выявлено, что единственный подход, сравнимый по качеству с FS, но снижающий его вычислительную сложность — MP-алгоритм иерархического поиска (рис. 4, б). MP избегает подмены глобального минимума локальным путем сглаживания поля векторов за счет анализа нескольких векторов-кандидатов (основной причины снижения производительности алгоритмов поиска по шаблону). Однако как преимущество алгоритмов поиска по шаблону можно отметить то, что поиск вектора движения для каждого блока не зависит от результатов поиска на более ранних стадиях алгоритма, что делает метод наиболее эффективным при сложных вариантах движения.
Заключение
В ходе исследования было выявлено, что для видеопоследовательностей различной динамичности алгоритмы построения траектории движущихся объектов на основе сегментации видеоданных показывают различные результаты. Например, перебор по шаблону дает высокую точность на прогнозируемом количестве шагов в сценах высокой динамичности, в то время как иерархический поиск дает лучшее качество прогнозирования на последовательностях низкой динамичности.
В целях дальнейшей оптимизации схемы поиска необходимо объединение сегментов по направлению движения в рамках объекта — приближение к объектному подходу, а также сочетание с параметрическими алгоритмами.
ПРОБЛЕМЫ ПОПОЛНЕНИЯ СЕМАНТИЧЕСКОГО СЛОВАРЯ
Литература
1. Ватолин Д., Ратушняк А., Смирнов М., Юкин В. Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео. — М.: Диалог-МИФИ, 2002. _ 384 с.
2. Гонсалес Р., Вудс Р. Цифровая обработка изображений. — М.: Техносфера, 2006. _ 1072 с.
3. Toivonen T. A New Algorithm for Fast Full Search Block Motion Estimation Based on Number Theoretic Transforms / J. Heikkila, O. Silven // Proc. 9th International Workshop on Systems: Signals and Image Processing: November 78: Manchester: United Kingdom, 2002. _ Р. 9094.
4. Kwon Moon Nam. A Fast Hierarchical Motion Vector Estimation Algorithm Using Mean Pyramid / Joon-Seek Kim, Rae-Hong Park // IEEE Transactions on Circuits and Systems for Video technology. _ 1995. _ V. 5. _ № 4. _ Р. 344351.
Рубина Ирина Семеновна — Санкт-Петербургский государственный университет информационных технологий, механики и оптики, аспирант, rubren@mail. ru
УДК 004. 912: 303. 7
ПРОБЛЕМЫ ПОПОЛНЕНИЯ СЕМАНТИЧЕСКОГО СЛОВАРЯ
К. К. Боярский, Е.А. Каневский
Рассмотрены проблемы пополнения компьютерного семантического словаря новыми словами, встреченными в тексте при его анализе. Предлагаемая для этого система работает в полуавтоматическом диалоговом режиме. На первом этапе определяются морфологические характеристики нового слова, на втором — его синтактико-семантические параметры по аналогам, имеющимся в существующем словаре. Предлагаемые подходы обеспечивают высокий уровень точности. Впервые появилась возможность указания точной семантики новых слов с учетом не только семантических классов, но и аргументов, обеспечивающих связь с подсоединяемыми словами. Ключевые слова: анализ текста, лексема, морфология, семантика, синтаксис, словарь, слово.
Введение
Задаче компьютерного анализа текста на естественном языке посвящено множество теоретических и практических работ. Эти задачи, а именно — поиск документов, рубрицирование и аннотирование документов, диалог с компьютером, машинный перевод и построение баз знаний, — решали и решают различными методами, используя или не используя ту или иную дополнительную информацию. Решение любых прикладных задач, связанных с анализом естественного текста, начинается с морфологического анализа. Такой анализ еще можно проводить без использования словаря [1]. Далее может проводиться синтаксический и семантический анализы, для которых словарь крайне необходим.
Используемый авторами семантический словарь В. А. Тузова [2] основан на расширенном морфологическом словаре А. А. Зализняка [3] и представляет собой список статей (лексем), каждая из которых соответствует одному слову русского языка. При этом одному слову может соответствовать несколько лексем, выражающих различный семантический смысл. Так, например, слову коса соответствуют три лексемы: девичья коса, береговая коса и острая коса. В настоящее время словарь насчитывает 165 тысяч лексем, соответствующих 145 тысячам слов общей нормативной лексики русского языка. Лексемы сгруппированы в 1650 классов, которые образуют иерархическую структуру, отражающую родовидовые отношения между лексемами [2]. Каждая из статей словаря содержит морфологическое, синтаксическое и семантическое описания лексемы. Так для лексемы «ЗОРИН» словарная статья имеет следующий вид: ЗОРИН $ 12 413/03000(S1& gt-Hab (S1:ЧЕЛОВЕК$ 1241,S0:ФАМИЛИЯ$ 1241/11)) {м11о 298} Морфологическое описание лексемы содержится в фигурных скобках, где «м11о» (морфологический описатель, аналогичный описателю в [3] обозначает существительное мужского рода, 11-го класса, одушевленное, а число «298» — адрес соответствующих падежных окончаний в файле окончаний лексем. Идентификатор $ 12 413/03000 обозначает принадлежность к классу
(ФО/Живой/Человек/Личность/ФИО/Фамилия). В круглых скобках расположено собственно синтаксическое и семантическое описание лексемы, которое в данном случае означает «человек имеет фамилию».
Проблема заключается в том, что какого бы объема ни был словарь, при анализе очередного текста всегда обнаруживаются новые слова (НС), в данном словаре отсутствующие. Это могут быть имена и фамилии, географические названия и образованные от них прилагательные, специальные термины и слова, употребленные автором в необычном значении, словоформы, противоречащие современным правилам грамматики (например, при передаче особенностей речи персонажей) и т. д. Так, по наблюдению Т. Ю. Кобзаревой, при анализе текстов Набокова, Мандельштама, Л. Н. Толстого, Гоголя часто встречались лексически продуктивные формы, неологизмы, «аномалии», не учтенные, например, в [3] и в компьютерном словаре пакета Word-2000 [4]. Рассмотрим подробнее структуру НС в романах Гончарова.

Показать Свернуть
Заполнить форму текущей работой