Главная
страница 1
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ

Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования

«Тверской государственный университет»

Факультет прикладной математики и кибернетики




КУРСОВАЯ РАБОТА

по дисциплине
«Цифровые методы обработки изображений»

Направление: 010300.68 – «Фундаментальная информатика и информационные технологии»


Магистерская программа: Информационные технологии

Тема: «Сравнение метода сопоставления блоков и объектного метода компенсации движения в видеоряде»







Выполнил:

магистрант 1 курса

Хохлов Дмитрий Владимирович
Проверил:

к.т.н., доцент, доцент кафедры ИТ Василенко С.И.











Тверь - 2013г.



Оглавление


Введение 2

Компенсация движения в видеоряде 4

Алгоритмы компенсации движения 6

Метод сопоставления блоков 7

Полный перебор 10

Перебор по шаблону 11

Трехмерный рекурсивный поиск 13

Объектный метод 16

Заключение 18

Литература 19












Введение

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

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

Само появление цифрового видео связано с разработкой эффективных алгоритмов сжатия изображения. Ведь для записи видеоряда на обычный DVD носитель необходимо сжать его более чем в 40 раз!

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

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

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

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

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

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



Компенсация движения в видеоряде



Компенсация движения — один из основных алгоритмов, применяемых при обработке и сжатии видеоданных. Алгоритм использует похожесть соседних кадров в видео последовательности и находит векторы движения отдельных частей изображения (обычно блоков 16x16 и 8x8). Использование компенсации позволяет при сжатии многократно увеличить степень сжатия за счет удаления избыточности в виде совпадающих частей кадров. Используется не только при сжатии, но и при фильтрации видео, изменении частоты кадров и т.д.

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



  • Размер кадра: 720x576 (Стандартный размер для Европейского телевидения (PAL), 414720 пикселей)

  • Частота кадров: 25 к/сек (Также стандартно для PAL)

  • Цветопредставление: YV12 (YUV 4:2:0) (16 бит на 4 пикселя + 8 бит на каждый = 12 бит на пиксель)

В итоге на запись или передачу одной секунды такого видео без применения сжатия потребуется 14,8 мегабайта без учета звука и служебной информации. Для хранения полуторачасового фильма уже будет нужно 78 (!) гигабайт.

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

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

1. Загружается текущий кадр.


2. Кадр делится на блоки (например 16x16).

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

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

Алгоритмы компенсации движения


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

  • анализируемый элемент – кадр, блоки, или объекты;

  • тип движения – операции параллельных сдвигов, поворотов, масштабирования;

  • мера принятия решения.

Как правило, в качестве меры выступает – сумма абсолютных разностей (САР) и сумма квадратов разностей (СКР):


http://e-memory.ru/memorycat/tvgu1.jpg
as a measure acts - the sum of absolute differences and the sum of squares of differences

где Obj – множество объектов компенсации, FOrig и FComp - яркость исходного и скомпенсированного кадра, соответственно.

Наиболее популярные методы компенсации движения в видеоряде:


  • Пиксельный метод

  • Объектный метод

  • Сопоставление блоков

    • Полный перебор

    • Перебор по шаблону

    • Трехмерный рекурсивный поиск

  • Метод параметрических моделей

Метод сопоставления блоков


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

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

Итак, принцип работы метода следующий (рис 2):


  1. Текущий кадр разбивается на непересекающиеся блоки одного размера B(x,y).

  2. Для каждого блока B(x,y) в небольшой окрестности http://cgm.computergraphics.ru/files/images/old_stories/76/image020.gif ищется наиболее ‘похожий’ на него блок BPrev(x+u,y+v) в предыдущем кадре. ‘Похожесть’ определяется выбранной метрикой, обычно SAD или SSD.

  3. Вектор d=(u,v)T, на котором достигается минимум выбранной функции ошибки, считается вектором смещения для данного блока.http://cgm.computergraphics.ru/files/images/old_stories/76/image023.gif

Рис 2. Схема работы алгоритма сопоставления блоков

В качестве функции ошибки компенсации чаще всего используется мера SAD для скомпенсированного блока:



http://cgm.computergraphics.ru/files/images/old_stories/76/image026.gif,

так как её вычисление проще реализуется на некоторых архитектурах процессоров.

Различные модификации этого подхода различаются тем, каким образом находится минимум функции ошибки компенсации во всей области http://cgm.computergraphics.ru/files/images/old_stories/76/image027.gif.

Полный перебор


Наилучшего качества приближения, то есть минимальной ошибки компенсации, может гарантировать полный перебор всех возможных значений векторов смещения из допустимой области с подсчётом ошибки компенсации для них и выбор того вектора, на котором достигается минимум ошибки. Этот подход считается эталонным, и сравнение с ним является неотъемлемой частью любой работы, посвященной разработке нового алгоритма компенсации движения. Однако практическое его применение в потребительских продуктах не представляется возможным ввиду слишком большой вычислительной сложности. Например, если требуется искать вектора движения в области +32 пиксела по каждому измерению для каждого блока размером 16x16, то SAD придется вычислить 64*64=4096 раз, в то время как каждое вычисление SAD требует 256 операций взятия модуля и 255 операций сложения.

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


Перебор по шаблону


Предположим, что функция http://cgm.computergraphics.ru/files/images/old_stories/76/image029.gif строго монотонно сходится к своему минимуму в области http://cgm.computergraphics.ru/files/images/old_stories/76/image030.gif. Тогда проверкой всего нескольких точек в этой области можно локализовать этот минимум. Алгоритм, по которому эти точки выбираются, называется шаблоном.

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



http://cgm.computergraphics.ru/files/images/old_stories/76/image032.jpg

http://cgm.computergraphics.ru/files/images/old_stories/76/image034.jpg

Рис 3. Ортогональный шаблон

Но, поскольку функция ошибки компенсации почти никогда не бывает монотонной, а обычно имеет множество локальных экстремумов, затрудняющих поиск глобального экстремума, часто является целесообразным использовать другие шаблоны, на каждом шаге проверяющие более чем две точки. Это уменьшает вероятность найти локальный минимум вместо глобального. Наиболее популярными являются прямоугольный и восьмиточечный шаблоны (рис 4), причем последний может иметь фиксированный размер на протяжении всех шагов либо уменьшаться вдвое на каждом шаге подобно рассмотренному ранее ортогональному шаблону. Последний вариант обычно называют трехшаговым поиском (Three Step Search, TSS), поскольку изначально этот шаблон применялся для области поиска +7 пикселов и находил минимум за три шага (с размером шаблона 4, 2 и 1 пиксел).



http://cgm.computergraphics.ru/files/images/old_stories/76/image035.gif

http://cgm.computergraphics.ru/files/images/old_stories/76/image037.gif

Рис 4. Виды шаблонов

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




Трехмерный рекурсивный поиск


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

Если записать формально, получим, что множество кандидатов на проверку (Candidate Set, CS) для блока с координатами p=(x,y)T кадра с номером n описывается следующим образом:



http://cgm.computergraphics.ru/files/images/old_stories/76/image040.gif,

где M, N - размеры блока по горизонтали и вертикали, соответственно, d(p,n) - вектор смещения для блока с координатами p=(x,y)T в кадре с номером n. Вектора v1(p) и v2(p) - это так называемые вектора обновления: случайные вектора из небольшой окрестности нулевого вектора. Основной смысл их использования - избежать насильственного сглаживания поля векторов, обеспечить возможность его вариации.

Графически формирование множества CS выглядит следующим образом (см. рис 5).

http://cgm.computergraphics.ru/files/images/old_stories/76/image042.jpg

рис 5. Формирование множества кандидатов

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

Изменение базовой версии заключается в том, что случайные вектора обновления v1(p) и v2(p) теперь не используются: вместо одного из них используется нулевой вектор, вместо второго - вектор http://cgm.computergraphics.ru/files/images/old_stories/76/image044.gif однопиксельного уточнения, найденный на второй стадии алгоритма для предыдущего блока в текущем кадре:



http://cgm.computergraphics.ru/files/images/old_stories/76/image046.gif,

взятый с коэффициентом http://cgm.computergraphics.ru/files/images/old_stories/76/image048.gif>0. Этот коэффициент определяет, насколько быстро алгоритм реагирует на градиентное изменение векторного поля в пространстве.



http://cgm.computergraphics.ru/files/images/old_stories/76/image050.gif

Метод носит название Enhanced 3D-RS. Вследствие своей простоты и высокой эффективности он является привлекательным для аппаратной реализации, хотя качество компенсации не всегда бывает удовлетворительным, особенно в сложных случаях.












Объектный метод

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


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

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

Таким образом, предлагается в рамках предложенного метода следующее:

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

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

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

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

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

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

Также интерес представляет разработка подходов к накоплению информации по объектам движения (аналогично накоплению информации о

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

Заключение

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


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

Объектный метод является одним из наиболее перспетивных



Литература


  1. G. de Haan, Progress in motion estimation for video format conversion. IEEE Transactions on Consumer Electronics Vol 46 No 3 Aug 2000 pp 449-450

  2. C.-H. Lee and L.-H. Chen, A Fast Motion Estimation Algorithm Based on the Block Sum Pyramid. IEEE Trans. Image Processing, vol. 6, pp. 1587-1591, Nov. 1997.

  3. Yong-Sheng Chen, Yi-Ping Hung, Chiou-Shann Fuh, A Fast Block Matching Algorithm Based on the Winner-Update Rule. Proceedings of Fourth Asian Conference on Computer Vision(ACCV), Vol. 2, pp. 977-982, Taipei, January 2000.

  4. M. Gallant et al., An Efficient Computation-Constrained Block-Based Motion Estimation Algorithm for Low Bit Rate Video Coding. IEEE Transactions on Image Processing, vol. 8, no. 12, Dec. 1999.

  5. S. Olivieri, G. de Haan, and L. Albani, Noise-robust recursive motion estimation for H.263-based videoconferencing systems. Proc. Int. Workshop on Multimedia Signal Processing, Sep, 1999, Copenhagen, pp. 345-350.

  6. R. Braspenning and G. de Haan, Efficient Motion Estimation with Content-Adaptive Resolution. Proceedings of ISCE'02, Sep. 2002, pp. E29-E34.

  7. Wikipedia [Электронный ресурс]: Компенсация движения. URL: http://ru.wikipedia.org/wiki/Компенсация_движения


Смотрите также:
Курсовая работа по дисциплине «Цифровые методы обработки изображений» Направление: 010300. 68 «Фундаментальная информатика и информационные технологии»
153.45kb.
1 стр.
Место дисциплины в структуре ооп принципы построения курса: Курс входит в профессиональный цикл ооп 010300 «Фундаментальная информатика и информационные технологии»
33.6kb.
1 стр.
Место дисциплины в структуре ооп принципы построения курса: Курс входит в профессиональный цикл ооп 010300 «Фундаментальная информатика и информационные технологии»
31.14kb.
1 стр.
Аннотация рабочей программы дисциплины
14.15kb.
1 стр.
Отчет по учебной практике бакалавра направления 010300. 62 "Фундаментальная информатика и информационные технологии"
48.56kb.
1 стр.
Учебная программа Дисциплины б3 «Основы программирования» по направлению 010300 «Фундаментальная информатика и информационные технологии»
130.85kb.
1 стр.
Программа «Информатика и компьютерные науки»
50kb.
1 стр.
Учебная программа Дисциплины б7 «Операционные системы» по направлению 010300 «Фундаментальная информатика и информационные технологии»
136.79kb.
1 стр.
Направление подготовки: 230400. 68 Информационные системы и технологии
27.67kb.
1 стр.
«Фундаментальная информатика и информационные технологии» Магистерские программы «Технологии баз данных», «Технологии разработки компьютерных игр» Дисциплина «Объектно-ориентированные case-технологии» Задание на курсовой проект
9.15kb.
1 стр.
Рабочей программы дисциплины Функциональный анализ Место дисциплины в структуре ооп принципы построения курса: Курс входит в математический и естественнонаучный цикл ооп 010300 «Фундаментальная информатика и информационные технологии»
24.9kb.
1 стр.
Рабочей программы дисциплины программная инженерия Место дисциплины в структуре ооп принципы построения курса: Курс входит в профессиональный цикл ооп 010300 «Фундаментальная информатика и информационные технологии»
26.68kb.
1 стр.