автореферат диссертации по электронике, 05.27.01, диссертация на тему:Разработка алгоритмов вычисления параметров глобального движения в видеопоследовательностях для реализации в системах на кристалле

На правах рукописи

МИРГОРОДСКИЙ АЛЕКСАНДР ЮРЬЕВИЧ

РАЗРАБОТКА АЛГОРИТМОВ ВЫЧИСЛЕНИЯ ПАРАМЕТРОВ ГЛОБАЛЬНОГО ДВИЖЕНИЯ В ВИДЕОПОСЛЕДОВАТЕЛЬНОСТЯХ ДЛЯ РЕАЛИЗАЦИИ В СИСТЕМАХ НА КРИСТАЛЛЕ

Специальность: 05.27.01 - твердотельная электроника, радиоэлектронные компоненты, микро- и наноэлектроника, приборы на квантовых эффектах

АВТОРЕФЕРАТ диссертации на соискание учёной степени кандидата физико-математических наук

Москва - 2006

Работа выполнена в Московском государственном институте электронной техники (Техническом университете)

Научные руководители: доктор технических наук,

профессор Казеннов Г.Г.,

Официальные оппоненты: доктор технических наук,

профессор Тишин Ю. И.

кандидат физико-

математических наук, Дворкович A.B.

Ведущая организация:

ФГУП «НИИ Космического приборостроения», г. Москва

2006г.

Защита диссертации состоится на заседании диссертационного совета" Д 217.011.01 при Государственном научно-исследовательском

институте физических проблем им. Ф.В.Лукина 124460, Москва, Зеленоград, проезд 4806, д.6.

С диссертацией можно ознакомиться в библиотеке Гос. НИИ физических проблем, телефон 531-46-73.

Автореферат разослан «¿5"» 2006 года.

Ученый секретарь диссертационного совета

д.ф.-м.н., проф. (у^Л—^——Попков А.Ф.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность проблемы

В конце 20-го - начале 21-го века средства телекоммуникации и портативные'"устройства цифровой фото-видео съемки развивались чрезвычайно быстрыми темпами. В нашу жизнь прочно вошли такие понятия, как мобильная связь, интернет, цифровая фото и видео камеры, и т.п. Реализация таких устройств требует не только увеличения степени интеграции используемых микросхем, но и повышения

эффективности алгоритмов обработки данных.

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

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

видеопоследовательности. При отсутствии видимых искажений типичный коэффициент покадрового сжатия равен 8-9.

Однако значительно более высокий уровень сжатия может быть достигнут за счет исключения временной избыточности в видеопотоке (т.е. в

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

Метод повышения степени компрессии путем кодирования только изменений в видеосцене, называемый условным замещением (УЗ), был использован в первом стандарте цифрового видео кодирования, ITU-T Rec. Н.120 [3]. Кодирование с УЗ состоит из передачи сигналов для индикации того, какая область изображения может быть повторена, и передачи закодированной информации об изменившихся областях. Также данный метод можно развить путем добавления метода компенсации движения (КД) . Суть метода заключается в том, что в некоторой окрестности исходной области одного кадра ищется наиболее похожая область из другого кадра. Разница в координатах между исходной и целевой областью называется вектором движения. В результате вместо кодирования целой области, кодируется только вектор движения и поправки к целевой области (разность между целевой и исходной областью). Размер области поиска движения выбирается исходя из предположения о максимальном смещении объектов внутри кадра. Зачастую используется квадрат размером 16x16 пикселей. Эффективность данных методов зависит от ряда предположений о виде движения в кадре, а именно:

• Объекты перемещаются в плоскости, параллельной плоскости камеры. Таким образом, не рассматриваются, например, эффекты масштабирования и вращения.

• Появление и исчезновение объектов не рассматриваются. Таким образом, не рассматриваются, например, эффекты вращения и сдвига.

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

описанные выше ограничения.

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

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

одновременно позволит повысить общую

производительность систем кодирования

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

Цель работы

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

Исследовать существующие методы вычисления параметров глобального движения сцены с целью выявления их достоинств и недостатков.

Разработать компактное представление

изображений для использования в алгоритмах вычисления параметров глобального движения.

Разработать алгоритмы вычисления параметров глобального движения сцены с использованием компактного представления изображений.

Создать экспериментальный программно-

аппаратный комплекс для проведения экспериментов по вычислению параметров глобального движения сцены.

Провести эксперименты по сравнению и показать преимущества разработанных алгоритмов по сравнению с широко распространенными методами.

Выработать требования к элементной базе, реализующей разработанные алгоритмы.

Научная новизна

1. Разработан новый способ вычисления параметров глобального движения в видеопоследовательностях, основанный на использовании интегральных характеристик бинаризованных изображений.

2. Разработан новый алгоритм вычисления параметров глобального движения, включающий:

• процедуру выделения и совмещения «крупномасштабных» пиков интегральных характеристик;

• итерационный алгоритм оценки комбинированных трансформаций.

3. Разработан новый способ вычисления параметров глобального движения сцены, основанный на использовании объектов бинаризованных изображений.

4. Разработан новый алгоритм вычисления параметров глобального движения, включающий:

• процедуру вычисления интегральных параметров объектов бинаризованных изображений;

• алгоритм установления соответствий между объектами бинаризованных изображений.

Практическая значимость работы

1. Разработанные алгоритмы вычисления параметров глобального движения повышают производительность систем кодирования видеопоследовательностей.

2. Предложенные алгоритмы вычисления параметров глобального движения применяются в разработанном в ООО «Юник Ай Сиз» устройстве видеосъемки -камкордер.

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

4. Проведенные теоретические оценки элементной базы могут быть применены при создании систем кодирования на кристалле.

Внедрение результатов работы

С использованием полученных в работе результатов разработано устройство видеосъемки -камкордер. Работа выполнена в рамках плана работ ООО «Юник Ай Сиз» на 2006г. Разработанные методы внедрены в учебный процесс кафедры ПКИМС МИЭТ(ТУ).

На защиту выносится:

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

изображений. Данный способ позволяет снизить вычислительные затраты по сравнению с аналогами.

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

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

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

5. Разработанное математическое и алгоритмическое обеспечение устройства вычисления параметров глобального движения, реализуемое в системах на кристалле.

Апробация работы

Результаты диссертационной работы

докладывались и обсуждались на международных и всероссийских научно-технических конференциях:

• 9-я всероссийская межвузовская научно-техническая конференция студентов и аспирантов «Микроэлектроника и информатика-2002», Москва, 2002;

• 7-я международная конференция «Распознавание образов и анализ изображений: новые информационные технологии», Санкт-Петербург, 2004;

• 12-я всероссийская межвузовская научно-техническая конференция студентов и аспирантов

«Микроэлектроника и информатика-2005», Москва, 2005;

- • Х1Л/111 научная конференция МФТИ, Москва, 2005;

• 13-я всероссийская межвузовская научно-

техническая конференция студентов и аспирантов «Микроэлектроника и информатика-2006», Москва, 2006.

Публикации

Основные результаты диссертационной работы опубликованы в 8 печатных работах.

Структура и объем диссертации

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

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ.

Во введении

обоснована актуальность темы, определены цели и задачи исследования, изложены научная новизна и практическая значимость работы.

В первой главе

рассмотрены различные виды движения в

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

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

• Дифференциальный метод [4];

• Прямое сопоставление [5];

• Линейная регрессия [6].

Рассмотрены вспомогательные методы,

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

видеопоследовательностях.

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

интегральных характеристик для определения параметров глобального движения. 2. Разработать алгоритм вычисления параметров глобального движения с _ использованием

интегральных характеристик.

3. Исследовать интегральные параметры объектов с целью использования в алгоритме вычисления параметров глобального движения.

4. Разработать алгоритм вычисления параметров глобального движения с использованием объектов изображения.

5. Разработать программное обеспечение, реализующее предложенные алгоритмы вычисления параметров глобального движения.

6. Провести сравнительный анализ точности разработанного алгоритмического и программного обеспечения.

Во второй главе

приводится описание методов предобработки изображений (выделение границ, бинаризация) Разработаны интегральные характеристики

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

Разработан алгоритм выделения объектов в изображении бинаризованном изображении. Предложен алгоритм вычисления параметров глобального движения сцены с использованием объектов изображений.

I. Алгоритмы оценки глобального движения с

помощью интегральных характеристик.

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

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

Таким образом, основная цель использования интегральных характеристик заключается в

дополнительном снижении количества обрабатываемой информации.

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

Использование интегральных характеристик позволяет избежать подобного рода проблем, заменяя задачу непосредственного совмещения точек двух множеств на задачу обеспечения совпадения их интегральных параметров, таких как количество точек, площадь, центр масс, момент инерции, и т.п.

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

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

Рассмотрим ряд характеристик, предложенных для индивидуальной оценки параметров глобального движения сцены.

1) Интегральная характеристика для оценки сдвига по одному направлению.

Для построения такой интегральной

характеристики, необходимо провести вычисления по формуле:

8}гХ(х) = ^1(х,у), (1)

у=О

где БНХ^х) - интегральная характеристика горизонтального сдвига; д:е(0,Ж), у^(0,Н~) -координаты; Н тл IV - высота и ширина изображения соответственно; 1{х,у) - функция яркости бинаризованного изображения.

Интегральная характеристика вертикального сдвига строится аналогично горизонтальному сдвигу:

МУОО = £/(*,.у), (2)

л=0

где - интегральная характеристика

горизонтального сдвига; X е , уе(0,Н)

координаты; Н и Ж - высота и ширина изображения соответственно; 1{х,у) - функция яркости бинаризованного изображения.

2) Интегральная характеристика для оценки вращения вокруг оси камеры.

Для построения данной интегральной

характеристики, необходимо провести вычисления по формуле:

-АЛ = 0 \

где - интегральная характеристика, зависящая

от угловой координаты СС ; Х,у - координаты точек в изображении; 1{х,у)~ функция яркости бинаризованного изображения.

Л. 1 1 ИмтФгрыьнм характеристика

|',ГЧ| — Ии1 юс -»гранъим I арате браяомия 2

II Ч

¡1

П и

II 11

|

1 1 5

,_и у - Лчк

номер строки

Рис. 1 Интегральные характеристики вертикального сдвига изображения 1 (до трансформации) и изображения 2 (после трансформации).

3) Интегральная характеристика для оценки коэффициентов масштабирования.

Для построения данной интегральной

характеристики, необходимо провести вычисления по формуле:

-, (4)

1тпга

где ~ интегральная характеристика

масштабирования, зависящая от радиуса; д:,_у координаты точек в изображении; г е (0,гаш(Я,}Г)) -радиус; Н и IV - высота и ширина изображения соответственно; - функция яркости

бинаризованного изображения; а - толщина кольца.

Суммирование проводится по кольцу Ur , точки которого удовлетворяют неравенству

а ^ г~2-2 а

/---<s!X + V </*Н—, Минимальное значение г

2 2 целесообразно выбирать отличным от 0, ввиду большого влияния шума, экспериментально

определенное значение г^ = ОД • Ш1п(//, W) .

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

• характеристика для оценки горизонтального сдвига инвариантна по отношению к вертикальному сдвигу, но неинвариантна по отношению к повороту и растяжению;

• аналогичным свойством обладает и характеристика для оценки вертикального сдвига;

• характеристика для оценки масштабирования инвариантна к повороту, но не инвариантна к сдвигу;

• аналогично, характеристика для оценки поворота инвариантна к масштабированию, но также не инвариантна к сдвигу.

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

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

4) Интегральная характеристика для

одновременной оценки коэффициентов сдвига и масштабирования.

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

« = Дах^ (/?) + ^(/? + 180)), (5)

где (X - направление максимального количества точек, - количество точек в секторе с угловой

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

е (10°,20°,30°,40°) было установлено, что наилучшие

результаты достигаются при у = 30° .

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

28}1(х) = ^1{х,у), (б)

где ZiSЙ(л:) - интегральная характеристика

горизонтального сдвига и масштабирования, 1{х,у) -

функция яркости изображения, Хб(0 _уе(0,//),

Н и ^ - высота и ширина изображения после поворота.

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

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

" \ShX\ii + БМАХ) - ,ШГ2(0|

егг ~ -Гт-' (7)

где БЮПфи 5,АЛГ2(г) - интегральные характеристики исходного и трансформированного изображений соответственно; БЫАХ - сдвиг по горизонтали; [а..^] - отрезок, общий для интегральных характеристик при каждом значении

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

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

Идея алгоритма основана на выделении и последующем совмещении «крупномасштабных» пиков

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

i i i i

— Имгагралымм карактаристим — ■ Усредненная иитагрвльнт х ■ракпристи л НА \ л

V И V - 1 А

1 ■ / ! У-

Т, •л

V

80 100 130 140 160 180 300 330 340 360 380

Рис. 2 Интегральная характеристика, ее сглаживающая функция и усредненная интегральная характеристика.

В основе предложенного метода лежит сглаживающая функция:

\{y-x)'f{y)dy ¡f(y)dy

(8)

где /(х) ~ характеристика; а - параметр, определяющий некоторую окрестность интегрирования.

Раскладывая характеристику /"(у) в ряд Тейлора на отрезке интегрирования, который определяется параметром О (предполагается, что а - малый параметр), можно убедиться, что сглаживающая

функция в первом приближении определяется

первой производной от /(У) • Эта функция мало чувствительна к многочисленным мелким пикам интегральной характеристики, но обращается в нуль в окрестности «крупномасштабных» экстремумов. На рисунке 2 изображены интегральная характеристика, ее сглаживающая функция и усредненная интегральная характеристика.

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

1. Итерационный алгоритм с последовательным вычислением отдельных трансформаций.

В данном алгоритме каждая итерация состоит в последовательном рассмотрении одиночных

трансформаций

• поворот;

• масштабирование;

• сдвиг по горизонтали;

• сдвиг по вертикали.

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

Значения параметров, вычисленные на текущей итерации, сравниваются со значениями, определенными на предыдущей итерации. Если все параметры удовлетворяют условию (9), то необходимая точность

считается достигнутой, параметры считаются вычисленными окончательно и процесс прекращается.

\Р2-Р1\<е, (9)

где Р1 , Р2 - предыдущее и текущее значение

|Р2 + Р1|

параметра соответственно, £' = 0,05--—-

2. Итерационный алгоритм с использованием «парных» трансформаций.

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

(масштабирование и сдвиг) находятся не

последовательно, а одновременно.

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

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

Затем на третьем этапе итерации

рассматривается сдвиг в ортогональном направлении.

Сдвиг в ортогональном направлении определяется из соответствующей интегральной характеристики как одиночное преобразование.

Существенное улучшение сходимости алгоритма определяется тем фактом, что интегральная характеристика для одновременной оценки

масштабирования и сдвига инвариантна к повороту и слабо зависит от сдвига в ортогональном направлении.

II. Алгоритмы оценки глобального движения с помощью объектов сцены.

Выделение объектов проводилось в изображениях, предварительно обработанных алгоритмами выделения границ и бинаризации.

Будем называть объектом группу точек, в которой для каждой точки найдется по крайней мере одна точка, принадлежащая этой же группе, расстояние до которой менее £) рисунок 3.

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

точек в окрестности . В ходе экспериментов с

использованием визуального контроля было

определено, что наилучшие результаты достигаются

Для каждого объекта вычислялись интегральные параметры:

• PointsCoutlt - количество точек объекта;

• Wa, Н0 - ширина и высота описанного вокруг объекта прямоугольника;

PointsCount

• Р„ —- - плотность - количество

W.-H.

точек объекта, деленное на площадь описанного прямоугольника;

PintsCount

ZA

• Dmid =-—- - среднее расстояние до

PointsCount

точек от центра масса (ЦМ) объекта, Di - расстояние до' 1-й точки объекта от ЦМ;

шах (Д.)

-J.T !е(0, PointsCount)

• DmaxNorm =- - расстояние до

Dmid

максимально удаленной от ЦМ объекта точки, нормированное на среднее расстояние до точек от ЦМ объекта;

• Dmaxi, /б [0,7] - максимальные расстояния до

точек, находящихся в каждом из 8-ми секторов описанной вокруг объекта окружности с центром, совпадающим с ЦМ объекта;

• DmaxNorntf , i е [0,7] - расстояние до точек,

находящихся в каждом из 8-ми секторов описанной

вокруг объекта окружности с центром, совпадающим с

ЦМ объекта, нормированное на среднее расстояние до точек от ЦМ объекта;

• а = arg шах (М1(ВЧ) - направление объекта,

£е(0,360) г

я

M"(ß) = (x2+y2)2 - момент И-го порядка точек в

секторе с угловой шириной у, определяемом окружностью, описанной вокруг объекта с центром в ЦМ объекта, и направлением Р .

Установление соответствия между объектами проводилось в пять этапов:

1-й. от ал

Грубый отсев объектов, которые находятся слишком близко к границам - расстояние центра масс

(ЦМ) объекта до границы не превышает Кграиица

К„а= 0,03-^1^, (10)

где Н - высота изображения, IV- ширина изображения.

Также из рассмотрения отбрасываются объекты, количество точек в которых менее экспериментально

определенного Сточек = 200 .

2-й этап

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

превышать Ярасстояние :

Кросс— = 0,3 • шах(Я, Ш), (11)

где Н - высота изображения, - ширина изображения.

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

между интегральными параметрами /)отклонение - Значение

порога для отбора по этому критерию определено как

£> =0,15.

отклонение >

3-я зтап

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

4-х отал

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

Из списка составленных групп требуется выбрать наиболее многочисленную, объекты которой

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

5-й атап

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

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

Третья глава

посвящена вопросам внедрения разработанных алгоритмов вычисления параметров глобального движения в системы кодирования

видеопоследовательностей по стандарту МРЕС-4 [7] . Проведен анализ технологии кодирования по стандарту МРЕ6-4 с использованием компенсации движения, в результате которого выявлена необходимость разработки алгоритма преобразования выходных данных предложенных алгоритмов для использования их в системах кодирования видеопоследовательностей. Разработан алгоритм преобразования выходных данных алгоритмов в соответствии с требованиями стандарта МРЕС-4. Применение предложенных автором

диссертационной работы алгоритмов вычисления параметров глобального движения в системах кодирования видеопоследовательностей с

использование технологии компенсации глобального движения позволит повысить производительность систем.

В четвертой главе

проводится сравнение разработанных автором диссертационной работы методов оценки глобального движения с ранее разработанными методами. Сравнения проводятся по критерию качества на различных видео последовательностях. Так же приводятся

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

В результате сравнения разработанных автором диссертационной работы алгоритмов оценки

глобального движения с существующими алгоритмами по производительности, выявлено преимущество

разработанных алгоритмов, в особенности для изображений с разрешением, превышающим VGA. Также установлено, что последовательное применение

алгоритмов вычисления параметров глобального движения и блочных алгоритмов поиска движения позволяет достигать более высоких степеней сжатия.

I

6

г » м'

«10* 1 10* «Ю-5 Ют 4-10* ' Л О1 110* но*

Рис. 4 Зависимость количества единых операций от линейного размера кадра.

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

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

} / / 1 1 — Интафальньм харакпристмт — Объекты юовоазмни я

! / Прж» Дифф и сопост*м« •р*нцмльныА ИМ истод

1 1 /

/ / 1 ! /

1 ¡' ! /

/ .' / * /

' / /

/ / <*

/ / /

' У

0 0 )01 ХО ЭТО «О МО 600 ПО 800 900 (ООО

Высота мера (тмкалм)

ЗАКЛЮЧЕНИЕ

По результатам полученным, в диссертационной

работе, можно сделать следующие выводы:

1. предложены интегральные характеристики бинаризованных изображений, которые позволяют вычислять параметры глобального движения в видеопоследовательностях;

2. определены интегральные параметры объектов бинаризованных изображений, позволяющие вычислять параметры глобального движения в видеопоследовательностях;

3. разработан алгоритм вычисления параметров глобального движения с использованием интегральных характеристик, требующий меньших вычислительных затрат по сравнению с известными алгоритмами при схожем качестве;

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

5. разработан алгоритм вычисления параметров глобального движения с использованием объектов бинаризованных изображений, требующий меньших вычислительных затрат по сравнению с известными алгоритмами при схожем качестве;

6. разработан метод преобразования выходных данных алгоритмов вычисления параметров глобального движения в соответствии с требованиями стандарта МРЕв-4, позволяющий применять разработанные алгоритмы в системах кодирования по стандарту МРЕС-4 (данные алгоритмы использованы в проекте «Камкордер» ООО «Юник Ай Сиз»);

7. проведено исследование и сравнение результатов работы предложенных алгоритмов вычисления параметров глобального движения с известными алгоритмами и показано что:4

• итерационный алгоритм вычисления параметров глобального движения сцены, включающий процедуру выделения и совмещения «крупномасштабных» пиков интегральных характеристик, превосходит по производительности известные алгоритмы вплоть до порядка, для изображений превышающих VGA при схожем качестве восстановленных изображений, для определенного типа видеопоследовательностей.

• алгоритм вычисления параметров глобального движения сцены с использованием объектов сцены, заключающийся в определении значений параметров глобального движения по перемещениям объектов, превосходит по производительности известные алгоритмы вплоть до порядка, для изображений превышающих VGA при схожем качестве восстановленных изображений, для определенного типа видеопоследовательностей.

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

В приложениях

приведены акты внедрения результатов

диссертационной работы в различных организациях.

СПИСОК ЦИТИРУЕМОЙ ЛИТЕРАТУРЫ

1. ISO/IEC 14495-1:2000 Information technology -lossless and near-lossless compression of continuous-tone still images: Baseline, JPEG.

2. ISO/IEC 15444-1 Information technology — JPEG 2000 image coding system. Part 1: Core coding system. Введ. 15.12.00. - Switzerland: ISO, 2000. -218 c.

3. ITU-T, "Codec for videoconferencing using primary digital group transmission" ITU-T Ree. H.120; version 1 1984, version 2 1988, version 3 1993.

4. S. F. Wu and J. Kittler, "A differential method for simultaneous estimation of rotation.

change of scale and translation," Signal processing: Image communication , vol.. 2, 1990, pp. 69-80. . ' '

5. . F. Moscheni, F. Dufaux, and. M. Kunt, "A new two-stage global/local motion estimation based on a background/foreground segmentation," in IEEE Proc. ICASSP'95, Detroit, MI, May 1995, pp. 2261-2264.

6. Y. T. Tse and R. L. Baker, "Global zoom/pan estimation and compensation for video compression," Proc. Int. Conf on Acoustics, Speech and Signal' Processing, Toronto, Canada, Apr. 1991, pp. 27252728.

7. Coding and Audio-Visual Objects. Part 2: Visual, ISO/IEC 14496-2 (MPEG-4), 2001.

ОСНОВНОЕ СОДЕРЖАНИЕ ДИССЕРТАЦИИ ОПУБЛИКОВАНО . В СЛЕДУЮЩИХ РАБОТАХ

1. Миргородский А.Ю. Метод оценки величин масштабирования, поворота и сдвига сцены с использованием объектов бинаризованных изображений// Электросвязь. 2006. - №4. - С. 46-47

2. Казеннов Г.Г., Миргородский А.Ю. Метод оценки коэффициента масштабирования с применением интегральных характеристик бинаризованного изображения// Известия высших учебных заведений Электроника. 2005. - №3. - С. 60-75

3. Казеннов Г.Г., Миргородский А.Ю. Численная оценка параметров поворота и сдвига изображений// Электросвязь. 2006. - №4. - С. 48-49

4. Миргородский А.Ю. Рекурсивное деление интервала// «Микроэлектроника и информатика 2002». 9-я Всероссийская межвузовская научно-техническая конференция студентов и аспирантов. Тезисы докладов, Москва, 2002.

5. Миргородский А.Ю. Метод оценки величины зума с применением интегральных характеристик бинаризованного изображения// «Распознавание образов и анализ изображений: новые информационные

технологии». 7-я международная конференция. Тезисы докладов, Санкт-Петербург, 2004.

6. Миргородский А.Ю. Модель оценки величины коэффициента масштабирования в видеопоследовательностях// «Микроэлектроника . и информатика - 2005». 12-я Всероссийская межвузовская научно-техническая конференция студентов и аспирантов 19-21 апреля 2005 г. Тезисы докладов, Москва, 2005.

7. Миргородский А.Ю. Метод оценки величин масштабирования, поворота и сдвига сцены с использованием объектов бинаризованного изображения// «Современные проблемы фундаментальных и прикладных наук». Труды ХЦУШ научной конференции Часть V, 25-26 ноября 2005 г. Тезисы докладов, Москва, 2005.

8. Миргородский А.Ю. Численная оценка параметров движения камеры// «Микроэлектроника и информатика -2006». 12-я Всероссийская межвузовская научно-техническая конференция студентов и аспирантов. Тезисы докладов, 19-21 апреля 2006 г, Москва, 2006.

Подписано в печать

Заказ • Тираж /00экз. Уч.-изд. л. Формат 60x84 1/16.

Отпечатано в типографии МИЭТ (ТУ). 124498, Москва, МИЭТ.

Введение.

Глава 1. Обзор алгоритмов вычисления параметров глобального движения сцены.

1.1. Оценка движения в системах видеокодирования.

1.2. Модели движения видеокамеры.

1.3. Алгоритмы вычисления параметров глобального движения.

1.3.1. Алгоритм Wu и Kittler.

1.3.2. Алгоритм Moscheni, Dufaux и Kunt.

1.3.3. Алгоритм Tse и Baker.

1.4. Вспомогательные технологии для оценки движения.

1.5. Выводы и постановка задачи.

Глава 2. Разработка алгоритмов оценки глобального движения сцены.

2.1. Методы предобработки изображений.

2.1.1. Алгоритм выделения границ в монохромном изображении.

2.1.2. Алгоритм бинаризации монохромного изображения.

2.1.3. Совмещение бинаризованных изображений.

2.2. Интегральные характеристики бинаризованного изображения.

2.2.1. Интегральная характеристика для оценки сдвига по одному направлению.

2.2.2. Интегральная характеристика для оценки вращения вокруг оси камеры.

2.2.3. Интегральная характеристика для оценки коэффициентов ма сшта бир ов а ния.

2.2.4. Интегральная характеристика для одновременной оценки коэффициентов сдвига и масштабирования.

2.3. Методики определения независимых параметров глобального движения сцены с использованием интегральных характеристик.

2.4. Алгоритм оценки параметров глобального движения сцены с использованием интегральных характеристик.

2.4.1. Описание алгоритма.

2.4.2. Алгоритмы оценки параметров при комбинированной трансформации.

2.5. Алгоритм выделения объектов в бинаризованном изображении

2.6. Алгоритм оценки параметров глобального движения сцены с использованием объектов изображений.

2.6.1. Алгоритм установления соответствий между объектами изображений.

2.7. Выводы.

Глава 3. Интеграция алгоритмов оценки глобального движения и системы кодирования по стандарту MPEG-4.

3.1. Архитектура системы кодирования по стандарту MPEG-4.

3.2. Формат данных глобальной компенсации движения в стандарте MPEG

3.3. Преобразование параметров алгоритмов глобальной оценки движения.

3.4. Выводы.

Глава 4. Исследование эффективности разработанных алгоритмов вычисления параметров глобального движения.

4.1. Сравнение разработанных алгоритмов оценки глобального движения с существующими алгоритмами по производительности.

4.1.1 Выделение границ и бинаризация изображения.

4.1.2 Алгоритм, основанный на использовании интегральных характеристик.

4.1.3 Алгоритм, основанный на выделении объектов.

4.1.4 Алгоритм Tse и Baker.

4.1.5 Алгоритм Wu и Kittler.

4.1.6 Алгоритм Moscheni, Dufaux и Kunt.

4.2. Оценка точности алгоритмов путем сравнения параметров глобального движения.

4.3. Сравнение разработанных алгоритмов вычисления параметров глобального движения с существующими алгоритмами по критерию качества.

4.4. Требования к элементной базе.

4.5. Выводы.

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

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

Существуют различные подходы к компрессии видеопоследовательностей. Один из вариантов обработки видеоинформации - это последовательное сжатие каждого кадра, используя такие алгоритмы, как JPEG, JPEG2000, MJPEG2000 [55,74,36-38,75]. Фактически такое внутрикадровое сжатие сейчас широко используется как метод кодирования видеоинформации в системах качественного видеомонтажа, которые требуют быстрого доступа к любому кадру видеопоследовательности. При отсутствии видимых искажений типичный коэффициент покадрового сжатия равен 8-9.

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

Метод повышения степени компрессии путем кодирования только изменений в видеосцене, называемый условным замещением (УЗ), был использован в первом стандарте цифрового видео кодирования, ITU-T Rec. Н.120 [39]. Кодирование с УЗ состоит из передачи сигналов для индикации того, какая область изображения может быть повторена, и передачи закодированной информации об изменившихся областях. Также данный метод можно развить путем добавления метода компенсации движения (КД) . Суть метода заключается в том, что в некоторой окрестности исходной области одного кадра ищется наиболее похожая область из другого кадра. Разница в координатах между исходной и целевой областью называется вектором движения. В результате вместо кодирования целой области, кодируется только вектор движения и поправки к целевой области (разность между целевой и исходной областью). Размер области поиска движения выбирается исходя из предположения о максимальном смещении объектов внутри кадра. Зачастую используется квадрат размером 16x16 пикселей. На эффективность данных методов оказывает влияние ряд предположений о виде движения в кадре, а именно:

• Объекты перемещаются в плоскости, параллельной плоскости камеры. Таким образом, не рассматриваются, например, эффекты масштабирования и вращения.

• Появление и исчезновение объектов не рассматриваются. Таким образом, не рассматриваются, например, эффекты вращения и сдвига.

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

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

Цель работы

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

Исследовать существующие методы вычисления параметров глобального движения сцены с целью выявления их достоинств и недостатков.

Разработать компактное представление изображений для использования в алгоритмах вычисления параметров глобального движения.

Разработать алгоритмы вычисления параметров глобального движения сцены с использованием компактного представления изображений.

Создать экспериментальный программно-аппаратный комплекс для проведения экспериментов по вычислению параметров глобального движения сцены.

Провести эксперименты по сравнению и показать преимущества разработанных алгоритмов по сравнению с широко распространенными методами.

Выработать требования к элементной базе, реализующей разработанные алгоритмы.

Научная новизна

1. Разработан новый способ вычисления параметров глобального движения в видеопоследовательностях, основанный на использовании интегральных характеристик бинаризованных изображений.

2. Разработан новый алгоритм вычисления параметров глобального движения, включающий:

• процедуру выделения и совмещения «крупномасштабных» пиков интегральных характеристик;

• итерационный алгоритм оценки комбинированных трансформаций.

3. Разработан новый способ вычисления параметров глобального движения сцены, основанный на использовании объектов бинаризованных изображений.

4. Разработан новый алгоритм вычисления параметров глобального движения, включающий:

• процедуру вычисления интегральных параметров объектов бинаризованных изображений;

• алгоритм установления соответствий между объектами бинаризованных изображений.

Практическая значимость

1. Разработанные алгоритмы вычисления параметров глобального движения повышают производительность систем кодирования видеопоследовательностей.

2. Предложенные алгоритмы вычисления параметров глобального движения применяются в разработанном в ООО «Юник Ай Сиз» устройстве видеосъемки - камкордер.

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

4. Проведенные теоретические оценки элементной базы могут быть применены при создании систем кодирования на кристалле.

Внедрение результатов работы

С использованием полученных в работе результатов разработано устройство видеосъемки - камкордер. Работа выполнена в рамках плана работ ООО «Юник Ай Сиз» на 2006г. Разработанные методы внедрены в учебный процесс кафедры ПКИМС МИЭТ(ТУ).

На защиту выносится следующее

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

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

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

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

5. Разработанное математическое и алгоритмическое обеспечение устройства вычисления параметров глобального движения, реализуемое в системах на кристалле.

Апробация работы

Результаты диссертационной работы докладывались и обсуждались на международных и всероссийских научно-технических конференциях:

• 9-я всероссийская межвузовская научно-техническая конференция студентов и аспирантов «Микроэлектроника и информатика-2002», Москва, 2002;

• 1-я международная конференция «Распознавание образов и анализ изображений: новые информационные технологии», Санкт-Петербург, 2004;

• 12-я всероссийская межвузовская научно-техническая конференция студентов и аспирантов «Микроэлектроника и информатика-2005», Москва, 2005;

• XLVIII научная конференция МФТИ, Москва, 2005;

• 13-я всероссийская межвузовская научно-техническая конференция студентов и аспирантов «Микроэлектроника и информатика-2006», Москва, 2006.

Публикации

Основные результаты диссертационной работы опубликованы в 8 печатных работах [56-63].

Структура и объем диссертации

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

4.5.Выводы

1. Проведено сравнение разработанных алгоритмов вычисления параметров глобального движения с существующими алгоритмами по производительности, в результате которого выявлено преимущество разработанных алгоритмов, в особенности для кадров с разрешением более VGA.

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

Заключение

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

1. предложены интегральные характеристики бинаризованных изображений, которые позволяют вычислять параметры глобального движения в видеопоследовательностях;

2. определены интегральные параметры объектов бинаризованных изображений, позволяющие вычислять параметры глобального движения в видеопоследовательностях;

3. разработан алгоритм вычисления параметров глобального движения с использованием интегральных характеристик, требующий меньших вычислительных затрат по сравнению с известными алгоритмами при схожем качестве;

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

5. разработан алгоритм вычисления параметров глобального движения с использованием объектов бинаризованных изображений, требующий меньших вычислительных затрат по сравнению с известными алгоритмами при схожем качестве;

6. разработан метод преобразования выходных данных алгоритмов вычисления параметров глобального движения в соответствии с требованиями стандарта MPEG-4, позволяющий применять разработанные алгоритмы в системах кодирования по стандарту MPEG-4 (данные алгоритмы использованы в проекте «Камкордер» ООО «Юник Ай Сиз»);

7. проведено исследование и сравнение результатов работы предложенных алгоритмов вычисления параметров глобального движения с известными алгоритмами и показано, что:

• итерационный алгоритм вычисления параметров глобального движения сцены, включающий процедуру выделения и совмещения «крупномасштабных» пиков интегральных характеристик, превосходит по производительности известные алгоритмы вплоть до порядка, для изображений превышающих VGA при схожем качестве восстановленных изображений, для определенного типа видеопоследовательностей;

• алгоритм вычисления параметров глобального движения сцены с использованием объектов сцены, заключающийся в определении значений параметров глобального движения по перемещениям объектов, превосходит по производительности известные алгоритмы вплоть до порядка, для изображений превышающих VGA при схожем качестве восстановленных изображений, для определенного типа видеопоследовательностей.

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

1. U-T Recommendation H.2 61, Video CODEC for audiovisual services at px64 kbit/s, 1993 ITU-T Recommendation H.263, Video coding for low bit rate communication, Version 2, 1998

2. O/IEC 14496-10 and ITU-T Recommendation H.264. Advanced Video Coding, 20031.in Richardson "H.264 and MPEG-4 video compression. Video coding for next-generation multimedia", John Wiley & Sons Ltd, 2003.

3. D. Adolph and R. Buschmann, "1.15 Mbit/s coding of video signals including global motion compensation," Signal processing: Image communication, vol. 3, 1991, pp. 259-274.

4. Y. Т. Tse and R. L. Baker, "Global zoom/pan estimation and compensation for video compression," Proc. Int. Conf on Acoustics, Speech and Signal Processing, Toronto, Canada, Apr. 1991, pp. 2725-2728.

5. G. Keesman, "Motion estimation based on a motion model incorporating translation, rotation and zoom," Signal processing, vol. 4, 1988, pp. 31-34.

6. M. Hoetter, "Differential estimation of the global motion parameters zoom and pan," Signal processing, vol. 16, Mar.1989, pp. 249-265.

7. S. F. Wu and J. Kittler, "A differential method for simultaneous estimation of rotation, change of scale and translation," Signal processing: Image communication , vol. 2, 1990, pp. 69-80.

8. A. Zakhor and F. Lari, Edge-Based 3-D Camera Motion Estimation with Application to Video Coding," IEEE Trans on Image Processing, vol. 2, pp. 481-499, Oct. 1993.

9. F. Moscheni, F. Dufaux, and M. Kunt, "A new two-stage global/local motion estimation based on a background/foreground segmentation," in IEEE Proc. ICASSP'95, Detroit, MI, May 1995, pp. 2261-2264.

10. H. Jozawa, K. Kamikura, A. Sagata, H. Kotera, and H. Watanabe, "Two stage motion compensation using adaptive global MC and local affine MC," IEEE Trans. Circuits Syst. Video Technol., vol. 7, pp. 75-85, Feb. 1997.

11. M. Etoh and T. Ankei, "Parametrized block correlation— 2D parametric motion estimation for global motion compensation and video mosaicing," in IEICE TR PRMU97, July 1997.

12. В.P. Horn and B.G. Schunck, "Determining optical flow," Artif. Intell. 17 (1981), pp. 185-204.

13. L. Kaufman and P.J. Rousseeuw. "Finding groups in data", John Wiley&Sons, Inc., New York, 1990.

14. P. J. Burt and E. H. Adelson. "The laplacian pyramid as a compact image code", IEEE Trans. Commun., vol. COM-31, no. 4, pp. 482-540, April 1983.

15. J.F. Canny "Finding Edges and Lines in Images", Technical report no. 720, Massachusetts Institute of Technology, 1983

16. J.F. Canny "A Computational Approach to Edge Detection", IEEE Transaction on Pattern Analysis and Machine Intelligence, 8(6):679-698, Nov 1986

17. D. Ziou, S. Tabbone, "Edge Detection Techniques An Overview", International Journal of Pattern Recognition and Image Analysis, 1998

18. D. Marr and E. C. Hildreth, "Theory of edge detection," Proc. Royal Society London В., vol. 207, pp. 187-217, 1980.

19. E. C. Hildreth, "Computations underlying the measurement of visual motion," Artificial Intelligence, vol. 23, pp. 309-354, 1984.

20. David W. Murray and Bernard F. Buxton, "Experiments in the machine interpretation of visual motion", Cambridge, MA MIT Press, 1990.

21. A. Averbuch, Y. Keller, "Fast gradient methods based global motion estimation for video compression", School of Computer Science, Tel Aviv University, Tel Aviv 69978 Israel

22. F. Dellaert and R. Collins, "Fast Image-Based Tracking by Selective Pixel Integration", ICCV 99 Workshop on Frame-RateVision, September, 1999.

23. Q. Wei, H.J. Zhang and Y. Zhong, "A Pre-Analysis Method for Robust Global Motion Estimation", IEEE International Conference on Image Processing, ICIP-99, vol. 2, pp. 26-30, Kobe, Japan, October 1999.

24. F. Dufaux and J. Konrad, "Efficient, Robust, and Fast Global Motion Estimation for Video Coding", IEEE Transactions on Image Processing, vol. 9, no. 3, pp. 497-501, March 2000.

25. J. Heuer, А. Каир "Global Motion Estimation in Image Sequences Using Robust Motion Vector Field Segmentation" proceedings ACM Multimedia 99, Orlando, Florida, 30 October 5 November 1999, pp. 261-264.

26. A. Smolic, J-R Ohm "Robust global motion estimation using a simplified m-estimator approach", Heinrich-Hertz-Institute, Image Processing Dept.

27. Q. Wei, H-J Zhang, Z. Yuzhuo "New Robust Global Motion Estimation Approach Used in MPEG-4" Tsinghua University, Department of Computer Science and Technology, Beijing 100084

28. S. Jehan-Besson, M. Barlaud, and G. Aubert, "Region-Based Active Contours for Video Object Segmentation with Camera Compensation", in IEEE International conference on Image processing, 2001, vol.2, 61-64 Thessaloniki, Greece.

29. J. Odobez and P. Bouthemy, "Detection of multiple moving objects using multiscale MRI: with camera motion compensation," in ICZP, Texas, 1994.

30. ISO/IEC 15444-1 Information technology JPEG 2000 image coding system. Part 1: Core coding system. Введ. 15.12.00. - Switzerland: ISO, 2000. - 218 c.

31. Marcellin M. et all. An Overview of JPEG-2000 // Proc. Data Compression Conference, J.A. Storer and M. Cohn, eds. Snowbird, Utah, Mar. 28-30, 2000. Snowbird, 2000. - pp. 523-541.

32. Taubman D.S., Marcellin M.W. JPEG2000: Image compression fundamentals, standards and practice Boston/Dordrecht/London: Kluwer Academic Publishers, 2002. 773 p.

33. ITU-T, "Codec for videoconferencing using primary digital group transmission" ITU-T Rec. H.120; version 1 1984, version 2 1988, version 3 1993.

34. P. Anandan, J.R. Bergen, K.J. Hanna, and R. Hingorani. Hierarchical model-based motion estimation. In M.I. Sezan and R.L. Lagendijk, editors, Motion Analysis and Image Sequence Processing, pages 1-22. Kluwer Academic Publishers, 1993.

35. Tompa D., Morgan J, Jernigan E. Computational imafe quality metrics: A review // Society for Information Display International Symposium Digest of Technical Papers, 1993, Vol.24. pp. 305-308.

36. Ramanath A.R., Snyder B.W., Hinks C.D. Image Comparison Measure for Digital Still Color Cameras // Proceedings IEEE International Conference on Image Processing, Sep. 2002, vol. 1. pp. 629-632.

37. I.E. Abdou, Quantitative Methods of Edge Detection. Technical report no. 830, Image Processing Institute, University of Southern California, 1978

38. F. Bergholm. Edge Focusing. IEEE Transaction on Pattern Analysis and Machine Intelligence, 9 (6):72 6741, Nov 1987.

39. V. Berzins. Accuracy of Laplacian Edge Detectors. Computer Vision, Graphics and Image Processing, 27:195-210, 1984.

40. S. Castan, J. Zhao and J. Shen Optimal Filter for Edge Detection Methods and Results. In Proceeding of First European Conference on Computer Vision (ECCV), pages 13-17, 1990.

41. J.S. Chen and G. Medioni. Detection, Localization and Estimation of Edges. IEEE Transactions on Pattern Analysis and Machine Intelligence, 11(2):191-198, 1989.

42. R. Deriche. Optimal Edge Detection Using Recursive Filtering. In Proceedings of the First International Conference on Computer Vision, pages 501-505, Londres, 1987

43. R. Deriche. Using Canny's Criteria to Derive a Recursive Implemented Optimal Edge Detector. The International Journal of Computer Vision, 1(2):167— 187, 1987

44. M. Heath, S. Sarkar, T. Sanocki and K. Bowyer, Comparison of Edge Detectors: A Methodology and Initial Study. In Proceedings of IEEE, International Conference on Computer Vision and Pattern Recognition, pages 143-148, San Francisco, 1996.

45. W.H.H.J. Lunscher and M.P. Beddoes, Optimal Edge Detector Design I: Parameter Selection and Noise Effects. IEEE Transaction on Pattern Analysis and Machine Intelligence, 8(2):164-177, Mar 1986.126

46. D.Marr and E.C. Hildreth, Theory of Edge Detection. Proceedings of the Royal Society of London B207, pages 187-217, 1980.

47. R. Li, B. Zeng and M. L. Liou, "A new three-step search algorithm for block motion estimation", IEEE Transactions Circuits Systems Video Technology, vol. 4, no. 4, pp. 438-442, August 1994.

48. G. Kummerfeld, F. May and W. Wolf, "Coding television signals at 320 and 64kbits/s", 2nd International Technical Symposium on Optical and Electro-Optical Applied Science and Engineering, SPIE Conf., Image Coding, Cannes, France, December 1985.

49. ISO/IEC 14495-1:2000 Information technology lossless and near-lossless compression of continuous-tone still images: Baseline, JPEG.

50. Миргородский А.Ю. Рекурсивное деление интервала// «Микроэлектроника и информатика 2002». 9-я Всероссийская межвузовская научно-техническая конференция студентов и аспирантов. Тезисы докладов, Москва, 2002.

51. Казеннов Г.Г., Миргородский А.Ю. Метод оценки коэффициента масштабирования с применением интегральных характеристик бинаризованного изображения// Известия высших учебных заведений Электроника. 2005. №3. - С. 60-75

52. Миргородский А.Ю. Метод оценки величин масштабирования, поворота и сдвига сцены с использованием объектов бинаризованных изображений// Электросвязь. 2006. №4. - С. 46-47

53. Казеннов Г.Г., Миргородский А.Ю. Численная оценка параметров поворота и сдвига изображений// Электросвязь. 2006. №4. - С. 48-49

54. Миргородский А.Ю. Численная оценка параметров движения камеры// «Микроэлектроника и информатика 2006». 13-я Всероссийская межвузовская научно-техническая конференция студентов и аспирантов. Тезисы докладов, 19-21 апреля 2006 г, Москва, 2006.

55. Претт У. "Цифровая обработка изображений" В 2-х кн.: Пер. с англ. М.:Мир, 1982.

56. Weszka J.S. A survey of threshold selection techniques, Computer Vision, Graphics and Image Processing, Vol.7, №2, 259-265, 1978.

57. Samet H., Soffer A. A map acquisition, storage, indexing, and retrieval system, Proc. 3rd Int. Conf. On Document Analysis and Recognition ICDAR'95, Vol.2, 992-996, 1995.67. 0'Gorman L., Kasturi R., eds. Document Image Analysis, IEEE CS Press, 1995.

58. Wang S., Haralick R.M. Automatic multithreshold selection, Comput. Vision, Graphics and Image Process., Vol. 25, 46-47, 1984.

59. Otsu N., A Threshold Selection Method from Gray-Level Histograms. IEEE Trans. on Systems Man and Cybernetics, 1979. Vol 9, n 1, pp 62-67.

60. Pal S.K.,Rosenfeld A. Image enhancement and thresholding by optimisation of fuzzy compactness. Pattern Recognition Letters, 1988. Vol 1, pp. 77-86

61. Y. Nakagawa, A. Rosenfeld, Some experiments on variable thresholding, Pattern Recognition 11 (1979) 191-204.

62. S.U. Lee, S.Y. Chung, R.-H. Park, A comparative performance study of several global thresholding techniques for segmentation, Comput. Vision Graphics Image Process. 52(2) (1990) 171-190.

63. P.K. Sahoo, S. Soltani, A.K.C. Wong, Y.C. Chen, A survey of thresholding techniques, Comput. Vision Graphics Image Process. 41 (2) (1988) 233-260.

64. ISO/IEC 10918-1:1994 Information technology ~ Digital compression and coding of continuous-tone still images: Requirements and guidelines.

65. ISO/IEC 15444-3:2002 Information technology — JPEG 2000 image coding system — Part 3: Motion JPEG 2000.

66. АКТ О ВНЕДРЕНИИ РЕЗУЛЬТАТОВ ДИССЕРТАЦИОННОЙ РАБОТЫ В1. УЧЕБНЫЙ ПРОЦЕСС

67. В учебном процессе кафедры ПКИМС разработанные алгоритмы использовалась в лабораторных работах, курсовом и дипломном проектировании по дисциплине «Теоретические основы САПР».

68. Зав. кафедрой ПКИМС, к.т.н.I1. Сухопаров А.И.зам. зав. кафедрой ПКИМС Миидесва А.Апроф. каф. ПКИМС\J/a v Казеннов Г.Г.аспирант/афедры ПКИМС1. Миргородский АЛО.1. УТВЕРЖДАЮ»

69. Генеральный директор ООО <ЦПНЙ£АЙ Сиз», К.Т.Н. лу/\ /Перминов В.Н. /дГ») /О ? 2006г.1. АКТ О ВНЕДРЕНИИ

70. С использованием полученных в работе результатов разработано устройство видеосъемки камкордер.аспирант кафедры ПКИМС