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

 

Министерство образования и науки Российской Федерации

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

высшего профессионального образования

Магистерская программа 230100.68.05 Интеллектуальные системы

Кафедра Информатики и вычислительной техники

Магистерская диссертация

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

Аннотация

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

Научный руководитель - д.т.н., профессор,

Направление подготовки: 230100.68 Информатика и вычислительная техника

Магистерская программа: Интеллектуальные системы

Институт информатики и телекоммуникаций

Кафедра информатики и вычислительной техники

Год защиты: 2012

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

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

Abstract

development of search algorithms and compensation effects ofon the video sequencesadviser - Doctor of technical sciences, professor of qualification: 230100.68 Informatics and computing techniques's Program: Intelligent Systemsof informatics and telecommunicationsof informatics and computing techniquesof defense: 2012the master's thesis deals with the development and implementation of the system to find and compensate for the effects of rain on the video sequences. Proved the novelty and relevance of the system development. Performs review and analysis there exist software systems. Methods and algorithms for finding the dynamical noise, the compensation of such noise. Selected methods based on motion estimation, morphological processing and adaptive filters. In this paper we propose a method for finding the motion of rain droplets, as well as developed and implemented a search system and compensate for the effects of rain, which is a Windows-based application. A technique for experimental studies and the results are presented.: noise, traffic, compensation, search, rain, algorithm evaluation, software product.

Введение

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

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

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

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

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

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

Для достижения поставленной цели решаются следующие задачи:

изучение существующих методов и алгоритмов предметной области;

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

тестирование и отладка программного продукта.

Апробация и публикации. Результаты работы не раз обсуждались на международной научной конференции «Решетневские чтения» и всероссийской научно-практической конференции «Актуальные проблемы авиации и космонавтики». Были опубликованы 4 статьи в сборниках в 2010 и 2011 годах. Темы тезисов: «Подавление шума на изображениях и видеопоследовательностях», «Слежение за точечными особенностями на сценах из видеопоследовательности», «Методы улучшения качества архивных видеопоследовательностей», «Методы улучшения качества изображений».

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

1. Анализ предметной области

Существуют различные виды шумов на изображениях и видеопоследовательностях. Эффект дождя можно интерпретировать как сложный динамический шум. Случайный шум проявляется в виде «снега», гранулярности или хаотически расположенных инородных точек на видео и возникает как вследствие нестабильности работы полупроводниковых приборов (при изменении температуры и с течением времени), так и в результате вносимых электронными компонентами искажений [7]. Наиболее заметен такой шум на тёмных областях изображений, поскольку при равном абсолютном уровне шума отношение «сигнал/шум» на них будет гораздо меньше, чем на светлых участках [7]. Для минимизации случайного шума, в процессе формирования видеопоследовательности, выполняется процедура калибровки, во время которой измеряются пороговые значения и смещение базового напряжения для каждого светочувствительного элемента. Случайный шум характеризуется колебаниями яркости и цветности выше и ниже настоящих [7]. Регулярный шум возникает вследствие перекрёстных помех (наводимых с соседних светочувствительных элементов), кратковременных изменений базового напряжения в ПЗС-матрице, воздействия высокочастотных электрических полей, изменение яркости источника света и т.п [6]. Регулярный шум, в отличие от случайного шума, очень хорошо заметен, поскольку проявляется в виде горизонтальных, вертикальных или диагональных полос. Шум особенно заметен в видеопоследовательностях, сделанных при высоких значениях чувствительности [7].

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

1.1 Анализ существующих методов и алгоритмов поиска эффектов дождя

1.1.1 Метод визуальной оценки

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

.1.2 Мультифрактальный метод распознавания

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

= ç(1) = 2 - > 0,(1.1)

где - фрактальная размерность графика , который является самоаффинным геометрический объектом в двумерном евклидовом пространстве. Это означает, что 1 - наибольшее возможное значение для Н1, которое достигается для почти всюду дифференцируемых функций. Если Н1=0, то имеем стационарный процесс, график которого заполняет пространство. Следовательно Н1 позволяет оценить нестационарность процесса . Мультипликативный шум (дождь) моделируется детерминированной функцией пространственных координат и по своей природе нестационарен, для его отличия от стационарного гауссовского и импульсного шума целесообразно применять мультифрактальный показатель Н1 [5]. Прологарифмируем выражение (1.1) и получим:

,(1.2)

где С - некоторая константа.

Для вычисления С1 в результате логарифмирования имеем

(1.3)

где - некоторая константа.

Идентификация помех на видеопоследовательности проводится путем вычисления мультифрактальных показателей с использованием вышеописанных формул. По значениям мультифрактальных показателей в автоматизированном режиме идентифицируется вид дождя [5].

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

.1.3 Метод гистограмм

Далее целесообразно рассмотреть метод гистограмм. Гистограммой цифрового изображения с уровнями яркости в диапазоне [0, L-1] называется дискретная функция h(rk)=nk, где rk - есть k-й уровень яркости, nk - число пикселов имеющих яркость rk [2].

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

,(1.4)

где n - общее число пикселов на изображении;

nj - общее число точек яркости rj;

L - число уровней яркости.

Уравнение (1.4) базируется на гистограмме входного изображения и является отображением его яркости в соответствующие промежуточные значения sk.

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

получить гистограмму исходного изображения;

с помощью уравнения вычислить значения отображения rk, sk;

вычислить функцию преобразования G;

итеративным путем вычислить zk для каждого sk;

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

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

Гистограммы являются основой для многочисленных методов пространственной обработки. Методы с использованием гистограмм очень эффективны, потому что они требуют только один проход по пикселам. Оптимальным с точки зрения зрительного восприятия человеком является изображение, элементы которого имеют равномерное распределение яркостей [2]. В этом методе гистограмма вычисляется по всем пикселам изображения и её минимумы и максимумы используются, чтобы найти кластеры. Цвет или яркость изображения могут быть использованы при сравнении. Метод гистограмм позволяет оценить динамический диапазон и особенности распределения пикселов по яркости [2]. Как уже говорилось случайный шум легче определить на темных участках изображения, которые можно получить, манипулируя гистограммой яркости. К достоинствам метода можно отнести:

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

управление с помощью фактов, а не мнений;

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

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

Этот метод очень актуален для нахождения дождя на видеопоследовательностях, потому что пикселы «пораженные» дождем отличаются от других пикселов кадра высокой интенсивностью. Это хорошо видно на гистограммах. Для примера приведем 6 графиков, показанных на рисунке 1.1. На тех, которые с левой стороны - видеопоследовательность с дождем, справа - без дождя.

Рисунок 1.1 - Графики интенсивности видеопоследовательностей: а), в), д) с дождем б), г), е) без дождя

На рисунке 1.1 по оси OX указано количество кадров, а по оси OY - интенсивность пикселов. Хорошо видно, что пикселы пораженные дождем расположились в локальных минимумах и максимумах функции гистограммы. Сама форма гистограммы имеет резкие перепады. Поэтому метод приведения (нормализации, эквализации) гистограмм дает хорошие результаты в данном случае.

1.1.4 Метод Motion estimation

Можно выделить несколько основных групп методов оценки движения (ОД): методы оптического потока (optical flow) [8], методы фазовой корреляции (phase correlation) [8], методы сопоставления блоков (block matching algorithms) [8]. Далее будет рассмотрен метод оценки движения (motion estimation) на видеопоследовательности, основанный на сопоставлении блоков движения, который был выбран для реализации. Поскольку иногда можно шум на изображении ложно принять за дождь (шум также имеет колебания интенсивности), а выбранный алгоритм оценивает именно движение объектов (капель дождя) на видеопоследовательности и имеет наименьшую ошибку. В настоящее время ОД широко применяется в сжатии и обработке видео. У обеих областей применения есть своя специфика [27].

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

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

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

а) б)

Рисунок 1.2 - Метод сопоставления блоков: а) реперный блок на предыдущем кадре; б) реперный блок на следующем кадре и соответствующий вектор движения

В современных алгоритмах сопоставления блоков для ускорения поиска вектора движения блока используется сходство между векторами движения в пространстве и во времени. Ускорение достигается за счет перебора лишь небольшого числа векторов движения вместо проверки всех возможных [11].

Классические методы имеют определенные недостатки, ограничивающие их применение в алгоритмах обработки видео:

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

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

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

Методы сравнения пространственных областей различают по типу пространственной области (блок постоянного размера, блок переменного размера), по критерию сравнения (значение абсолютного отклонения, коэффициент корреляции) [16]. Эти методы характеризуются значительными вычислительными затратами, поэтому основные усилия по применению этих методов направлены на разработку алгоритмов, снижающих вычислительные затраты. Другими характерными недостатками методов сравнения пространственных областей являются проблема выбора размеров блока и зоны поиска, а также определение правила выбора вектора смещения из набора векторов-кандидатов и правила обработки областей открытия/закрытия фона [8]. В основу градиентных методов положен расчет оптического потока (ОП) или отношения пространственного и временного градиентов. Допустим, задан некоторый пространственный градиент, перепад яркости. Допустим также, что он не меняется с течением времени. Тогда при движении этого перепада, значение интенсивности в некоторой точке будет изменяться. Это изменение представляет собой временной градиент [8]. Расчет оптического потока требует введения определенных ограничений. Первое ограничение - это неизменность интенсивности точки на смежных кадрах вдоль траектории движения, ограничение постоянства яркости. Это означает, что любое изменение яркости вызвано исключительно смещением области изображения. Второе ограничение, пространственная связность или ограничение плавности, состоит в том, что точки, расположенные в малой, окрестности должны принадлежать одной и той же области изображения. Это означает, что оптический поток в произвольно малой области является постоянным, т.е. не существует участков изображения, на которых точки движутся в разных направлениях. Очевидно, что выполнение этих двух ограничений не всегда возможно.

Кроме вышеперечисленных методов в системах сжатия, оценки движения и кросс-корреляции, используются статистические, частотные и методы высшего порядка. Основная идея статистических методов заключается в расчете критерия максимума апостериорной вероятности поля движения [11]. Существует несколько способов реализации этого метода. Первый способ максимизации апостериорной вероятности заключается в стохастической релаксации, например, «имитированном отжиге», которая гарантирует сходимость на глобальном максимуме [13]. При стохастическом поиске следующая точка выбирается произвольным образом, поэтому процесс поиска требует значительных вычислительных затрат. Для его оптимизации разработан второй способ, детерминистский вариант «имитации отжига» - «детерминистский отжиг», при котором аналитически оцениваются наиболее подходящие математические ожидания значений системных параметров, т.е. переменных, используемых в процессе оптимизации [13].

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

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

(1.5)

Наиболее распространенным является метод фазовой корреляции. Однако используемые в процессе присвоения векторов движения блочные методы снижают его эффективность [15].

Приведенные выше методы относятся к так называемым простым методам, обрабатывающим только плоскопараллельное смещение. Эти методы не в состоянии обрабатывать более сложные движения, такие как вращение или комбинированное движение. Для обработки сложных смещений были разработаны так называемые методы высшего порядка. Наиболее распространенным из них является метод на основе аффинного преобразования [8]. В большинстве случаев аффинная модель задается шестью параметрами, отражающими смещение, поворот, масштабирование, отражение, сдвиг и перспективные преобразования. Задача заключается в определении параметров аффинного преобразования между кадрами t и t+1 [8].

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

1.1.5 Метод, использующий нейронные сети для распознавания образов

Последние десять лет идет активное развитие аналитических систем нового типа. В их основе лежат технологии искусственного интеллекта, имитирующие природные процессы, такие как деятельность нейронов мозга или процесс естественного отбора. Наиболее популярными и проверенными из этих технологий являются нейронные сети и генетические алгоритмы. Распознавание образов - это в общем случае отнесение объекта к какому-то множеству образов, т.е. в нашем случае классификация шумов (дождя) на изображении и видеопоследовательности [21]. Распознавание образов состоит из двух частей: обучения и распознавания. Обучение осуществляется путем показа отдельных объектов с указанием их принадлежности тому или другому образу [4]. В результате обучения распознающая система должна приобрести способность реагировать одинаковыми реакциями на все объекты одного образа и различными на все объекты различных образов [1]. В качестве объектов обучения выступают примитивные изображения различных шумов. За обучением следует процесс распознавания новых объектов, который характеризует действия уже обученной системы. Автоматизация этих процедур и составляет проблему обучения распознаванию образов. Сначала независимо от конкретного метода распознавания необходимо провести обработку полученного изображения, к примеру, преобразование цветного изображения к градациям серого, или к черно-белому изображению. Полученное преобразованное изображение подается на вход распознающей системы. На вход искусственного нейрона поступает некоторое множество сигналов, каждый из которых является выходом другого нейрона. Каждый вход умножается на соответствующий вес, аналогичный синаптической силе, и все произведения суммируются, определяя уровень активации нейрона. Как правило, передаточные функции всех нейронов в нейронной сети, фиксированные, а весы являются параметрами нейронной сети и могут изменяться [4].

Персептрон (простейшая архитектура нейросети) - это некоторый инструмент, который способен «запоминать» какой образ относится к какому классу. После такого «обучения», в идеале, он должен уметь правильно «узнавать» и другие образы, не входившие в обучающее множество, но достаточно похожие на них, или сообщать, что образ не похож ни на один из множества обучающих образов [4]. После многократного предъявления примеров веса нейронной сети стабилизируются, причем нейронная сеть дает правильные ответы на все (или почти все) примеры из базы данных. Качество обучения нейронной сети напрямую зависит от количества примеров в обучающей выборке [4]. Можно выделить достоинства: решение задач при неизвестных закономерностях, устойчивость к шумам во входных данных, адаптирование к изменениям окружающей среды, потенциальное сверхвысокое быстродействие, отказоустойчивость при аппаратной реализации нейронной сети.

Для решения задач определения шума лучше всего подходит нейросеть Хопфилда. Она состоит из слоя нейронов, число которых является одновременно числом входов и выходов сети. Каждый нейрон связан синапсами со всеми остальными нейронами, а также имеет один входной синапс, через который осуществляется ввод сигнала. Выходные сигналы, образуются на аксонах. Для данной сети на вход требуется некоторый набор двоичных сигналов, которые считаются образцовыми. Сеть должна уметь из произвольного неидеального сигнала, поданного на ее вход, выделить («вспомнить» по частичной информации) соответствующий образец (если такой есть) или в противном случае выдать наиболее похожий образ [20]. Для сети Хопфилда число запоминаемых образов N не должно превышать величины, примерно равной 0,15n. Архитектура сети Хопфилда показана на рисунке 1.3.

Рисунок 1.3 - Архитектура сети Хопфилда

.2 Анализ существующих методов и алгоритмов компенсации эффектов дождя

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

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

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

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

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

Методы обработки изображения могут существенно различаться в зависимости от того, каким путем изображение было получено, синтезировано системой машинной графики, либо путем оцифровки черно-белой или цветной фотографии или видео [25].

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

Источники шума могут быть различными:

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

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

помехи при передаче по аналоговым каналам, наводки от источников электромагнитных полей, собственные шумы активных компонентов (усилителей) линии передачи (пример - телевизионный сигнал);

неточности (плохие фильтры) при выделении яркостного и цветоразностных сигналов из аналогового композитного сигнала и т. п. [14].

Соответственно, шумы тоже бывают разных видов. Самые распространенные:

белый шум - сигнал, отсчеты которого не коррелируют друг с другом, и его разновидность;

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

(1.6)

где d - амплитуда шума; у - параметр распределения.

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

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

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

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

Шум в видеопоследовательности можно условно разделить на пространственный и временной. Временным шумом называют неприятный визуальный эффект, возникающий в видео из-за случайного или коррелированного изменения пространственного шума от кадра к кадру [28]. В некоторых источниках под временным шумом понимают любое случайное изменение значений каждого пиксела во времени, в том числе смену яркости от кадра к кадру. Соответственно, фильтры шумоподавления также делятся на пространственные и временные: первые производят усреднение пикселов по каждому отдельному кадру (изображению), а вторые - между несколькими последовательно идущими кадрами. Во временных фильтрах часто используются алгоритмы детектирования и/или компенсации движения. На практике обычно используется сочетание пространственного и временного методов шумоподавления, так называемый, 3D-фильтр [29]. При этом в большинстве существующих алгоритмов первым применяется пространственный фильтр, поскольку после его работы процедура обнаружения движения во временном фильтре становится проще и точнее, и, как следствие, временное шумоподавление становится более эффективным. Хотя обратный порядок применения тоже имеет свои преимущества: временной фильтр, как правило, работает довольно бережно; проработав вначале, он понизит общий уровень шума и предотвратит излишнее размытие, характерное для любого пространственного фильтра [25].

Основная проблема при пространственном шумоподавлении заключается в том, чтобы не испортить четкость краев предметов на изображении, а также мелкие детали, соизмеримые по амплитуде с шумом. При шумоподавлении в видео подобные детали можно детектировать, отслеживая их на протяжении нескольких кадров [10].

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

Еще одной сложностью является оценка качества подавления шума. Как правило, оно оценивается следующим образом: на незашумленное изображение накладывается искусственный шум, затем полученное изображение фильтруется алгоритмом шумоподавления и сравнивается с исходным с помощью какой-нибудь метрики [10]. Чаще всего для этой цели используют метрику PSNR (peak signal-to-noise ratio - пиковое соотношение сигнал/шум), которая определяется формулой:

(1.7)

где xi, yi - i-е пикселы двух сравниваемых изображений; N - общее число пикселов на каждом изображении; d(xi, yi) - разность между цветами соответствующих пикселов (для оттенков серого это просто разность значений пикселов, а для цветных изображений - евклидово расстояние между пикселами в трехмерном цветовом пространстве). Соответственно, чем ближе отфильтрованное изображение к оригинальному, тем больше значение PSNR, и тем выше считается качество работы алгоритма.

Однако эта и другие аналогичные метрики позволяют оценивать лишь среднеквадратичную разницу между изображениями, поэтому лучшие результаты с точки зрения метрики не всегда соответствуют наилучшему визуальному восприятию. К примеру, более размытое изображение, в котором вместе с шумом были удалены мелкие детали, может иметь значение PSNR выше, чем изображение с более аккуратно подавленным шумом [8]. Визуальные оценки при этом покажут предпочтительность второго изображения.

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

Можно выделить следующие базовые подходы к пространственному шумоподавлению:

Линейное усреднение пикселов по соседям.

Медианная фильтрация.

- Математическая морфология.

Гауссовское размытие.

Методы на основе вейвлет-преобразования.

Метод главных компонент.

Анизотропная диффузия.

Фильтры Винера.

Некоторые из этих методов применимы с небольшими модификациями также и во временной области.

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

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

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

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

Математическая морфология. Шумоподавление можно также осуществлять с использованием двух основных морфологических операций (см. [3]): сужения (erosion) и расширения (dilation), а также их комбинаций - закрытия (closing) и раскрытия (opening). Раскрытие (сначала сужение, потом расширение) убирает выступы на границах объектов, а закрытие (сначала расширение, потом сужение) заполняет отверстия внутри и на границах.

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

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

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

Рисунок 1.4 - Схема одномерного вейвлет-преобразования

На рисунке 1.4 H1 (G1) - высокочастотный фильтр анализа (синтеза), а H2 (G2) - низкочастотный фильтр анализа (синтеза).

Метод главных компонент (МГК) позволяет выделить структуру в многомерном массиве данных и применяется в основном для распознавания или для сжатия изображений. В области шумоподавления этот подход является довольно новым и мало исследованным. Работает он лучше всего для изображений с белым гауссовским шумом.

Метод главных компонент заключается в нахождении таких базисных векторов исследуемого многомерного пространства, которые бы наилучшим образом отражали расположение некоторых исходных данных в этом пространстве (характеризовали эти данные) [8]. Кратко опишем алгоритм построения таких векторов.

Анизотропная диффузия. Основная идея данного подхода заключается в следующем. Яркость каждого пиксела интерпретируется как значение температуры в данной точке изображения, таким образом, все изображение представляется в виде карты температур. Шумоподавление производится путем выравнивания температур (фактически, интенсивностей пикселов) с помощью моделирования процесса теплопереноса [3].

Фильтры Винера основаны на преобразовании Фурье и применяются, в основном, для подавления шума в аудио, поэтому автором они подробно не исследовались [3].

.2.1 Фильтр erosion

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

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

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

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

Рисунок 1.5 - Эрозия области изображения

Математическое описание эрозии можно представить следующим образом. Эрозия множества A по примитиву S:

(1.8)

Использование структурного элемента S[3,3] = 1 дает следующие результаты, показанные на рисунке 1.6.

Рисунок 1.6 - Результат применения эрозии

Пример удаления лишнего шума представлен на рисунке 1.7.

а) б)

Рисунок 1.7 - Обработка эрозией: а) до обработки; б) после обработки

1.2.2 Фильтр Adaptive smoothing

Вторым исследуемым методом стал фильтр Adaptive smoothing. Данный фильтр применяется при наличии динамических шумов типа соль - перец. Фильтр предназначен для выполнения сглаживания изображения, но при этом сохраняет контуры объектов [24]. Это делает его применяемым к аддитивным шумам и сглаживанию контуров объектов [23]. Фильтр принимает изображения с восемью битами на пиксел в градациях серого и 24 бита на пиксел в цветных изображениях. Результаты работы фильтра представлены на рисунке 1.8.

а) б)

Рисунок 1.8 - Обработка фильтром Adaptive smoothing: а) исходное изображение; б) обработанное изображение

.3 Обзор существующих программных продуктов

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

Пакет «AviSynth» - средство для обработки, в частности линейного и нелинейного монтажа видеоматериалов [10]. Позволяет осуществить нелинейное редактирвоание любого уровня сложности. «AviSynth» - свободно распространяемая программа с открытым кодом. Большое количество различных плагинов позволяет расширить возможности программы. В частности существует несколько авторских плагинов по детектированию и удалению шумов с видеопоследовательностей. Например, при помощи плагина «Quicktime Import Filter» для «AviSynth» можно импортировать нужный нам файл «Apple Quick Time» в любую программу, которая поддерживает импорт файлов «AviSynth». При этом абсолютно не важно, поддерживает нужная нам программа формат «Apple Quick Time» или не поддерживает.

Программа «AviSynth» имеет достаточно простой интуитивно понятный интерфейс (Рисунок 1.9).

Рисунок 1.9 - Интерфейс программы «AviSynth»

Программа «VirtualDub» - свободно распространяемая программа для захвата, монтажа и редактирования видеопотока для платформы Windows [10]. Может использоваться для простых линейных операций над видео. Также «VirtualDub» может использовать встроенные фильтры или подключаемые модули сторонних разработчиков. Основные функции программы делятся:

вырезание и склеивание;

конвертация;

видеозахват;

замена звуковых дорожек;

наложение фильтров (в том числе позволяющих определить шум);

распределенная работа по сети.

Уникальность «VirtualDub» состоит в том, что для работы с различными видеоданными ему не нужна рекомпрессия. Скорость работы программы значительно отличается от подобных программ за счет того, что программа дает малую нагрузку на центральный процессор. Достигается это за счет того, что «VirtualDub» написан на низкоуровневом языке. Интерфейс программы представлен на рисунке 1.10

Рисунок 1.10 - Интерфейс программы «VirtualDub»

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

Рисунок 1.11 - Интерфейс программы «EnhanceMovie»

Программный продукт «NeatImage» - средство, которое обрабатывает графические данные с шумами, при попадании их в компьютер. Программа учитывает особенности камеры, с помощью которой производилась съёмка, что приводит к созданию итоговых видеоданных хорошего качества. Побочным положительным эффектом работы программы является существенное сокращение размера файла. Процесс удаления шумов в программе «NeatImage» состоит из четырёх частей: 1) открытие файла с изображением; 2) настройка профиля; 3) установка параметров удаления шума; 4) просмотр и сохранения результата. Вид программы представлен на рисунке 1.12.

Рисунок 1.12 - Внешний вид программы «NeatImage»

Программный фильтр «Video DeNoise». Основная задача данной программы - это уменьшение шумов, таких как: маленькие яркие линии, красные или голубые цвета и т.д. Фильтр анализирует каждый кадр по отдельности к другим, так что по сравнению с динамичными фильтрами может найти больше искажений. Уровень устранения шумов регулируется любыми цветовыми компонентами. Фильтр оптимизирован для процессоров, которые поддерживают технологию MMX (дополнительный набор инструкций, выполняющих характерные для процессов кодирования/декодирования потоковых аудио/видео данных действия за одну машинную инструкцию). Вид программы приведен на рисунке 1.13.

Рисунок 1.13 - Вид программы «Video DeNoise»

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

Рисунок 1.14 - Интерфейс программы «VideoChimeraHome»

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

.4 Выводы по главе

Таким образом, в первой главе были рассмотрены методы поиска и компенсации дождя на видеопоследовательностях. Для реализации и достижения поставленных целей выбран метод Motion estimation с использованием метода гистограмм для визуальной информации и фильтры erosion, adaptive smoothing. Рассмотрены наиболее популярные из существующих программных продуктов предметной области. Их анализ выявил, что применяются различные алгоритмы детектирования движения и компенсации различных шумовых эффектов. Эффективность метода зависит от времени обработки, следовательно, необходимо улучшать и оптимизировать существующие методы для лучшей производительности системы. Работа не с простыми, а с динамическими шумами на видеопоследовательности так же будет требовательна к ресурсам и возможностям выбранных методов, поэтому их дополнительно необходимо оптимизировать под конкретную задачу.

Таблица 1.1 - Сравнение программ

Название ПОТип лицензииOSRUSПроизводительФункциональностьAviSynthGNU GPLWindows+СШАРаботает как фрэймсервер, имеющий систему сценариев, редактирование которых позволяет осуществлять редактирование любого уровня сложности с высоким уровнем воспроизводимости результатов.VirtualDubGPLWindows+АнглияВыполняет простые линейные операций над видео. Имеет встроенные фильтры или подключаемые модули сторонних разработчиков.EnhanceMovieGNUWindows(XP, Vista)+АнглияУлучшает качество. Регулируются контрастность, насыщенность и «температура» цветов, яркость и четкость картинки. Есть функция Deinterlace. Наглядно показывается результат: можно выбрать просмотр оригинальной записи, ролика с примененными фильтрами. Изображение разделяется на две части: слева - неотфильтрованное видео, справа - конечный роликNeatImageGNUWindows(32, 64 бит)+СШАРаботает как самостоятельно, так и плагин для множества редакторов. Имеет встроенный бенчмарк для измерения скорости обработки изображений на специальном оборудовании. использует самые современные индустриальные алгоритмы шумоподавления Video DeNoiseУсловно-бесплатнаяWindows -СШАУменьшает шумы, такие как: маленькие яркие линии, красные или голубые цвета и т.д. Фильтр анализирует каждый кадр по отдельности к другим. VideoChimeraHomeУсловно-бесплатнаяWindows-Англия/ФранцияОбработка видео с 48-ю битной точностью, мощная система удаления шума, динамически изменяемая резкость и контрастность, наложение эффектов, интеллектуальный графический детектор движения в реальном времени.

2. Алгоритмическая реализация

.1 Алгоритм поиска дождя на видеопоследовательностях на основе метода Motion estimation

Для реализации был выбран алгоритм Motion estimation (оценка движения), т.к. иногда можно шум на изображении ложно принять за дождь (шум также имеет колебания интенсивности), а выбранный алгоритм оценивает именно движение объектов (капель дождя) на видеопоследовательности. Метод имеет наименьшую ошибку.

Как уже было сказано в первой главе, можно выделить несколько основных групп методов оценки движения: методы оптического потока (optical flow) [8], методы фазовой корреляции (phase correlation) [8], методы сопоставления блоков (block matching algorithms) [8].

Широко на практике применяются методы сопоставления блоков. Общая схема работы этих методов представлена на блок-схеме (Рисунок 2.1). Приведем описание алгоритма:

текущий кадр разбивается на множество непересекающихся блоков;

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

Для поиска областей со сложным движением вычисляется дисперсия координат векторов, входящих во множество векторов-кандидатов для блока. Области со сложным движением определяются путем сравнения дисперсии с порогом: если она превышает порог, то в окрестности блока имеет место сложное движение [3].

Рисунок 2.1 - Блок-схема алгоритма поиска реперного блока

Приемлемый уровень ошибок для вектора движения блока определяется следующим образом. Имеет место зависимость между величиной VAR(t,B) и средним значением ошибки вектора:

(2.1)

где B - блок; I(t, x, y) - яркость точки (x, y) кадра с номером t.

Таким образом, вычислив величину VAR для блока, становится возможным адаптивно определить порог для ошибки вектора, в случае превышения которого блок необходимо разбить на блоки меньшего размера. Адаптивный выбор размера блока позволяет значительно повысить точность векторного поля (например, на границах объектов), не повышая при этом чувствительность к шуму [2]. Иными словами, блоки малого размера используются только в тех областях кадра, где это необходимо.

В современных алгоритмах сопоставления блоков для ускорения поиска вектора движения блока используется сходство между векторами движения в пространстве и во времени. Ускорение достигается за счет перебора лишь небольшого числа векторов движения вместо проверки всех возможных. Поиск вектора движения для каждого блока в таких алгоритмах производится следующим образом (Рисунок 2.2). Приведем описание алгоритма:

формируется множество векторов-кандидатов;

в нем осуществляется поиск лучшего вектора-кандидата;

производится его уточнение.

Рисунок 2.2 - Блок-схема алгоритма поиска вектора движения

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

Рисунок 2.3 - Блок-схема усовершенствованного алгоритма поиска вектора движения

.1.1 Усовершенствованные алгоритмы

Использование простейшего алгоритма motion estimation не дает хорошего результата, когда объект движется слишком медленно, т.к. он попросту не успевает его «захватить». Отличие следующего детектора от предыдущего в том, что он ищет вектор движения, сравнивая кадр не с предыдущим кадром, а с первым в видеопоследовательности [8]. Блок-схема такого алгоритма представлена на рисунке 2.3.

Единственный случай, когда этот алгоритм не срабатывает - это когда на первом кадре присутствует объект, а на последующих кадрах его нет.

.1.2 Оптимизированный алгоритм

Наиболее эффективные алгоритмы поиска векторов движения сравнивают текущий кадр не с другими кадрами, а с фоном видеопоследовательности [10]. Сначала получается фон первого кадра видеопоследовательности в качестве объекта сравнения. В последующем текущий кадр всегда сравнивается с фоном. Данный алгоритм был усовершенствован в плане возможности двигать фон на необходимый уровень. Фон двигается в кадре в сторону, т.е. меняются цвета пикселов в фоновом кадре на необходимый уровень в каждом кадре. Схематично такой алгоритм представлен на блок-схеме (Рисунок 2.4).

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

Рисунок 2.5 - Результат работы усовершенствованного алгоритма поиска векторов движения

Еще один подход к определению векторов движения отличается от предыдущих применением фильтра Pixellate (разбиение изображения на пикселы). Для обработки представляются пикслеллированные кадры - текущий и фоновый [10]. Остальная часть алгоритма, как и в описанных выше алгоритмах. Результат работы оптимизированного алгоритма представлен на рисунке 2.6.

Рисунок 2.4 - Блок-схема усовершенствованного алгоритма поиска векторов движения

Рисунок 2.6 - Результат применения оптимизированного алгоритма

Применение для поиска дождя видно на рисунке 2.7.

Рисунок 2.7 - Детектирование капель дождя на бинаризированной видеопоследовательности

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

Алгоритм компенсации состоит из двух этапов. Первый этап: фильтр erosion применяется уже при поиске дождя. Вторым этапом применяется фильтр Adaptive Smoothing. Блок-схему работы фильтра можно посмотреть на рисунке 2.8. Приведем подробное описание. Параметр Radius метода влияет на формирование фактора сглаживания. Метод использует приём, который называется «метод двойной апертуры». Квадратная апертура 3×3 пробегает в цикле по всем пикселам изображения. На каждом шаге цикла в другом цикле проходит по всем 9 пикселам апертуры и рассматривается каждый такой пиксел как центр крестообразной апертуры 3×3. Вычисляется горизонтальная и вертикальная разница цветов лучей крестообразной апертуры, возводится сумма квадратов разниц в экспоненту, получая вес каждого пиксела апертуры. Умножается вес на цвет центрального пиксела апертуры, в результате получаются отклонения.

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

Рисунок 2.8 - Расчет значения пиксела при применении фильтра Adaptive smoothing

Также для общего понимания приведу математическое описание метода. Метод адаптивного сглаживания основан на идеях Ли (Lee) [14], но расширен до мульти-разрешения. Метод Ли рассчитывает окрестное среднее арифметическое zi,j и дисперсию с поправкой на шум qi,j в точке i,j, а затем получает вычисленное значение, как взвешенную сумму среднего и исходного зашумленного значения:

,(2.2)

где у12 - это дисперсия шума; xi,j - истинное значение в точке i,j; zi,j - это значение, поврежденное шумом.

Суть в том, что там, где дисперсия зашумленного сигнала значительно больше, чем шум, зашумленное значение используется в качестве предполагаемой истинной величины, так как шум не оказывает большого влияния; там, где дисперсия мала по сравнению с шумом, используется окрестное среднее арифметическое, значительно устраняющее шум. Использование различных размеров области расчета значительно влияет на качество обработки изображений. Если область слишком мала, алгоритм фильтрации шума не эффективен. Если область слишком велика, мелкие детали изображения будут потеряны в процессе фильтрации [14]. Решение по выбору размера области расчета в данном методе адаптивного сглаживания заключается в том, что нужно сглаживать с помощью областей различных размеров, позволяя дисперсии в области каждого размера контролировать, на сколько среднее арифметическое в данной области влияет на вычисленное значение. Алгоритм учитывает различную дисперсию шума в пространстве и рассчитывает средние арифметические значения и дисперсии во вложенных областях так, что все расчеты после этапа с начальным разрешением производятся по сеткам с постепенно увеличиваемым размером ячейки, что ведет к весьма эффективной обработке. Для применения данного алгоритма адаптивного сглаживания к данным, необходима оценка дисперсии для каждой точки. Описанный здесь способ оценки шума был разработан для использования с односекундными данными, требовал некоторой дополнительной подстройки к особенностям данных, в частности к пространственно - обусловленной природе шума. Для других источников данных может потребоваться другой способ; в некоторых случаях оценка шума может быть выполнена в процессе создания. Для каждой ячейки среднее значение рассчитывается по кольцевой области радиусом от 3 до 5 ячеек; кольцо означает, что значения, окружающие целевую ячейку не учитываются при расчете среднего значения. Рассчитывается разность между целевой ячейкой и средним значением, а затем получают стандартное отклонение этой разности по области из 5 ячеек. Это даёт информацию о величине дисперсии высот относительно средних высот на небольшом расстоянии, идея в том, что эта дисперсия должна быть наиболее зашумленной, так как небольшая дисперсия произведет пространственно - связанные отличия от среднего значения, которое не сильно повлияет на стандартные отклонения разностей. Эта первоначальная оценка величины шума всё еще весьма приблизительна, поэтому она сглаживается двумя этапами медианной фильтрации, сначала группировкой по прямоугольнику размерами 5×5, а затем по круговой области радиусом в 5 ячеек по полученной более грубой сетке. Результирующая сетка затем улучшается до начального разрешения с помощью билинейного пересчета.

2.3 Выводы по главе

Таким образом, во второй главе были подробно рассмотрены реализованные алгоритмы поиска и компенсации дождя на видеопоследовательностях на основе метода Motion estimation и алгоритмы в него включающиеся: автоматический фильтр erosion и фильтр Pixellate, а также Adaptive smoothing. Метод motion estimation включает в себя несколько детекторов движения основывающихся на усовершенствованных и оптимизированном алгоритмах. Оптимизированный алгоритм был усовершенствован в плане движения фона кадра на необходимый уровень. Оптимизированный алгоритм использует фильтр Pixellate для разложения изображения на пикселы. Представлены результаты обработки в виде изображений и видеофайлов. Алгоритмическая реализация включает в себя математические модели и описание алгоритмов выбранных для использования и оптимизированных методов и алгоритмов. Метод Adaptive smoothing является адаптивным. Данный метод самостоятельно подстраивает веса функции для определения применения в той или иной степени, что адекватно сказывается на обработке сложных динамических шумов, коими и является эффекты дождя. Этот относительно простой алгоритм адаптивного сглаживания эффективно устраняет пространственно-распределенный шум, полученный с помощью различных видеоисточников. Алгоритм сглаживания успешно заполняет участки с отсутствующими данными сглаженными соседними значениями, благодаря применению нулевых весов, которые могут быть использованы как простой метод для заполнения пустот.

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

3. Программная реализация, описание программного продукта

3.1 Структура программного продукта

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

Рисунок 3.1 - Структура меню программы

Рисунок 3.2 - Структура взаимодействия модулей

Структура взаимодействия модулей представлена на рисунке 3.2.

Система имеет интуитивно понятный интерфейс. На главной форме расположены пункты меню «Файл», «Движение», «Справка». Загруженная видеозапись отображается в середине окна. В меню «Файл» находится кнопка открытия видеопотока, в меню «Движение» находятся детекторы движения, в меню «Справка» информация о системе. В таблице 3.1 представлена файловая структура программного продукта.

Таблица 3.1 - Файловая структура программного продукта

Файлы *.csНазначениеMainform.csГлавная форма программыAVIReader.csЧтение видео с помощью vfwAVIWriter.csЗапись в видео с помощью vfwmotion.exeИсполняемое приложениеMotionDetector1Простой детекторMotionDetector2Детектор по 1 кадруMotionDetector3Детектор фонаMotionDetector4Детектор оптимизированныйвидеофайлывидеофайлы для приложения

Внешний вид главного окна программы представлен на рисунке 3.3.

Рисунок 3.3 - Главное окно программы «Motion Detector»

3.1.1 Простой детектор

Детектор предназначен для поиска векторов движения и оценки движения в видео основанный на сравнении с предыдущим кадром. Данный детектор представляет собой класс в программном продукте. Его UML-диаграмму можно посмотреть на рисунке 3.4.

Рисунок 3.4 - UML-диаграмма класса простого детектора

Листинг кода детектора представлен ниже.

Листинг 1 - Код метода простого детектора

// создать фильтры

Difference differenceFilter = new Difference();thresholdFilter = new Threshold(15);

// установка backgroudFrame в качестве наложения для разностного фильтра

differenceFilter.OverlayImage = backgroundFrame;

// применение фильтровtmp1 = differenceFilter.Apply(currentFrame);tmp2 = thresholdFilter.Apply(tmp1);

// создать фильтрerosionFilter = new Erosion();

// применить фильтрtmp3 = erosionFilter.Apply(tmp2);

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

Рисунок 3.5 - Результат работы простого детектора

3.1.2 Детектор по первому кадру

Детектор основан на сравнении с первым кадром. Данный детектор так же представляет собой класс в программном продукте. Его UML-диаграмму можно посмотреть на рисунке 3.6.

Рисунок 3.6 - UML-диаграмма класса детектора по первому кадру

В листинге 2 показан код метода детектора.

Листинг 2 - Код метода детектора по первому кадру

// создание фильтра

MoveTowards moveTowardsFilter = new MoveTowards();

// установка currentFrame в качестве наложения для фильтра

moveTowardsFilter.OverlayImage = currentFrame;

// применяем фильтрtmp = moveTowardsFilter.Apply(backgroundFrame);

// удаляем старую фоновую сцену.Dispose(); = tmp;

На рисунке 3.7 показан результат работы метода детектора.

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

.1.3 Детектор фона

Детектор основан на сравнении с фоном. UML-диаграмма класса детектора фона представлена на рисунке 3.8.

Рисунок 3.8 - UML-диаграмма класса детектора фона

Ниже представлен листинг детектора фона (Листинг 3).

Листинг 3 - Метод детектора фона

// создание фильтра

IFilter pixellateFilter = new Pixellate();

// применение фильтра newImage = pixellateFilter(image);

// создаем набор фильтров для последовательного применения

FiltersSequence processingFilter = new FiltersSequence();.Add(new Difference(backgroundFrame));.Add(new Threshold(15));.Add(new Dilatation());.Add(new Edges());

// применение фильтраtmp1 = processingFilter.Apply(currentFrame);

На рисунке 3.9 показан результат работы детектора фона.

Рисунок 3.9 - Результат работы метода детектора фона

3.1.4 Оптимизированный детектор

Оптимизированный детектор представляет собой усовершенствованный детектор по фону. Является классом в программном продукте. UML-диаграмма класса представлена на рисунке 3.10.

Рисунок 3.10 - UML-диаграмма класса оптимизированного детектора

Результат работы детектора представлен на рисунке 3.11. Данный детектор отличается улучшенным быстродействием.

Рисунок 3.11 - Результат работы оптимизированного детектора

3.2 Описание программного продукта

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

загрузка и отображение видео файла с жесткого диска;

анализ видеопотока, оценка движения, поиск движущихся объектов;

сохранение результатов анализа.

Для нормальной работы программы необходимо выполнение следующих программных и аппаратных требований:

Операционная система «Microsoft Windows XP/Vista/7».

Процессор Intel Pentium 1,5 MHz и выше 512 Mb оперативной памяти.

100 Mb свободного места на жестком диске для файлов приложения.

Ускоритель «Radeon», «GeForce».

NET.Framework версии не ниже 3.0.

Установленную Visual studio не ниже 2008 версии.

Библиотеки AForge для работы с видеопотоком.

Средой разработки была выбрана Microsoft Visual Studio 2010, включающая в себя интегрированную среду разработки программного обеспечения и ряд других инструментальных средств. Данные продукты позволяют разрабатывать как консольные приложения, так и приложения с графическим интерфейсом, в том числе с поддержкой технологии Windows Forms, а также веб-сайты, веб-приложения, веб-службы как в родном, так и в управляемом кодах для всех платформ, поддерживаемых Microsoft Windows, Windows Mobile, Windows CE,.NET Framework,.NET Compact Framework и Microsoft Silverlight. Языком программирования выбран Visual C# - объектно-ориентированный язык программирования. Разработанный в 1998 - 2001 годах группой инженеров под руководством Андерса Хейлсберга в компании Microsoft как язык разработки приложений для платформы Microsoft.NET Framework и впоследствии был стандартизирован как ECMA-334 и ISO/IEC 23270.

В программном продукте поддерживается работа с интерфейсом Video for Windows.

Video for Windows предоставляет в распоряжение пользователей новую технологию работы со звуковой информацией, видеоинформацией и другими типами данных. С помощью Video for Windows пользователь может создавать файлы с расширением имени *avi, содержащие одновременно несколько потоков данных. Например, в файле может храниться видеофильм со звуковым сопровождением на нескольких национальных языках. Во время воспроизведения пользователь может выбрать нужный ему язык, указав соответствующий поток звуковых данных.

В качестве источника видео можно использовать видеокамеру, подключенную к компьютеру через видеоадаптер.

UML-диаграмма классов программы представлена на рисунке 3.12.

Программный продукт «Motion detector» не требует сложной установки. Достаточно скопировать все файлы проекта в выбранную папку на жестком диске. После установки и запуска исполняемого файла ««motion.exe» активируется главное окно. Чтобы начать анализ видео с файла на жестком диске достаточно выбрать пункт меню «Файл ? Открыть» и выбрать интересующий нас видео файл. Затем в меню движение необходимо выбрать соответствующий детектор из четырех предложенных и результат отобразится на видеопоследовательности. Существует возможность сохранить полученный результат. В меню справка можно познакомиться со справкой о программном продукте.

Рисунок 3.12 - UML-диаграмма классов программ

3.3 Тестирование и анализ характеристик

Объектом тестирования являются выбранные алгоритмы и программный продукт. Методика тестирования включает в себя сравнение алгоритмов с помощью метрик, результаты показаны в виде графиков. Было проведено сравнение усовершенствованного метода с алгоритмами FAME [3] и E3DRS [3], как с одними из наиболее популярных алгоритмов ОД того же класса. Рассматриваются два сценария применения ОД:

использование блоков размера 16×16. Данный сценарий подразумевает разбиение области кадра только на блоки размера 16×16;

использование блоков размера 4×4. В данном случае сравнение с алгоритмом FAME не проводилось, поскольку он предназначен только для работы с блоками размера 16×16.

Алгоритм E3DRS работает с блоками произвольного фиксированного размера, поэтому для него использовалось разбиение области кадра на блоки размера 4×4. Алгоритм способен адаптивно определять размер блока, для него использовалось начальное разбиение области кадра на блоки размера 16×16, а во время работы алгоритма происходило адаптивное разбиение блоков на подблоки по схеме 16×16 -? 8×8 -? 4×4.

В сравнении применялась метрика Y-PSNR, вычисляемая для каждой пары скомпенсированный и сходный кадр по их яркостным компонентам. Большие значения метрики соответствуют меньшей скомпенсированной разнице. Иными словами, чем выше показатель Y-PSNR. тем выше точность найденных векторов движения. Для удобства сравнения была также вычислена метрика ДУ-PSNR. которая представляет собой разность значений метрики Y-PSXR сравниваемого алгоритма и алгоритма E3DRS.

При использовании первого сценария усовершенствованный алгоритм демонстрирует лучшие значения Y-PSNR - соответствующая ветвь на графике (Рисунок 3.8) лежит выше остальных.

Рисунок 3.8 - Сравнение PSNR для алгоритмов (блоки 16 ×16)

Не смотря на некоторое отставание этого алгоритма по скорости обработки (Рисунок 3.9), он, тем не менее, осуществляет обработку кадров видеопотока с большой скоростью.

Рисунок 3.9 - Сравнение скорости обработки

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

Таблица 3.2 - Время срабатывания алгоритмов

РазрешениеПростой детекторДетектор по первому кадруДетектор фонаОптимизированный детектор640×4800,110,140,1130,01800×6000,720,6850,540,0751024×7681,11,1341,090,431280×10241,731,882,01,184640×4800,10,120,140,015800×6000,20,120,10,091024×7681,31,231,120,581280×10241,91,91,871,9640×4800,120,090,170,02800×6000,30,140,110,11024×7681,41,411,20,451280×1024221,491,95640×4800,090,0980,20,017800×6000,30,140,120,131280×10242,12,31,831,891024×7681,61,471,230,531280×10241,951,941,951,1640×4800,080,0880,150,019800×6000,410,180,730,41024×7681,91,81,370,41280×10242,0822,171,28640×4800,070,920,20,2800×6000,50,20,80,351024×7681,792,22,131,731280×102422,32,31,97640×4800,140,930,20,2800×6000,50,230,90,371024×7681,832,252,141,9

Данные таблицы представлены на графике (Рисунок 3.10).

Рисунок 3.10 - График результатов тестирования

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

.4 Принятие решения об использовании результатов

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

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

Применение метода Adaptive smoothing несущественно замедлило работу программы, но дало хорошие визуальные результаты. В общем, цель программы достигнута. Результаты адекватны поставленным задачам перед программным продуктом.

.5 Выводы по главе

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

Заключение

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

изучены существующие методы определения дождя на видеопоследовательностях. Для реализации выбран метод Motion estimation;

изучены методы компенсации шумов, выбран метод Adaptive smoothing;

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

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

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

написана пояснительная записка.

Реализация показала, что метод Motion estimation дает неплохие результаты по сравнению с другими рассмотренными методами. Совместно с предварительной и постобработкой видеопоследовательности можно добиться стабильных хороших результатов поиска дождя на видеопоследовательности. А метод Adaptive smoothing с адаптивным подбором весов значительно очищает видеопоследовательность от эффектов дождя. Данные методы также широко используются в играх и имитаторах. К примеру, Adaptive smoothing - настройка графики есть практически в каждой современной игре. Она помогает улучшить визуальное качество картинки, сгладить контуры объектов, убрать лишнее. Оценка движения используется в основном в «стрелялках», например, для определения движения врага и т.п.

Список использованных источников

1. Боровиков В.П. Нейронные сети [Текст]/ В.П. Боровиков. - М.: Горячая линия телеком, 2008. - 392 с.

. Гонсалес Р. Цифровая обработка изображений [Текст]/ Р. Гонсалес, Р. Вудс. - М.: Техносфера, 2006. - 1072 с.

. Журавель И.М. Краткий курс теории обработки изображений [Текст]/ И.М. Журавель.// IV Всероссийская научная конференция «Проектирование научных и инженерных приложений». - М.: Техносфера 2009. - 120 с.

. Исаенко А.П. Использование нейронных сетей для решения задач распознавания образов [Текст]/ А.П. Исаенко. - Донецкий национальный технический университет, автореферат по магистерской диссертации, 2007. -

. Калинкина Д. Проблема подавления шума на изображениях и видео и различные подходы к ее решению [Текст]/ Д. Калинкина, Д. Ватолин. - М.: Компьютерная графика и мультимедиа, сетевой журнал, 2010. - 9 с.

. Кубасов Д. Обзор методов компенсации движения [Текст]/ Д. Кубасов, Д. Ватолин. - М.: Компьютерная графика и мультимедиа, сетевой журнал, 2010.

. Полякова М.В. Мультифрактальный метод автоматизированного распознавания помех на изображении [Текст]/ М.В. Полякова, В.Н. Крылов. - М.: Информационно-измерительные системы, 2006. - 12 с.

. Руднева, В. Методы повышения цветового качества изображений и восстановления цветов в старом видео [Текст]/ В. Руднева. - М.: Компьютерная графика и мультимедиа, сетевой журнал, 2010. - 11 с.

. Симонян К.В. Адаптивный метод оценки движения в видео [Текст]/ К.В. Симонян. - М.: ВМик МГУ, 2008. - 8 с.

. Слынько Ю.В. Комплекс алгоритмов улучшения изображений и компенсации их геометрических искажений [Текст]/ Ю.В. Слынько. - М.: Московский физико-технический институт, 2005. - 100 с.

11. Ahmad W. A fast adaptive motion estimation algoritm [Text] / W. Ahmad// IEEE Transactions on CSVT, March 2006. - Pp. 420-438.

. Biswas M. DCT-based phase correlation motion estimation [Text]/ M/ Biswas// In Proceedings of ICIP 2004, Vol. 1. - Pp. 445-448.

. Braspenning R. Efficient Motion Estimation with Content-Adaptive Resolution [Text] / R. Braspenning// In Proceedings of ISCE"02, September 2002. - Pp. E29-E34.

. Olivieri S. A low-complexity motion estimation algorithm for H.263 video coding [Text]/ S. Oliveri// In Proceedings of Philips Conference on DSP. Veldhoven, November 1999. - P 17.

. Pizurica A, Noise Reduction in Video Sequences Using Wavelet-Domain and Temporal Filtering [Text] / A. Pizurica// SPIE Conference on Wavelet Applications in Industrial, October 2003. - Pp. 27 - 31.

. Richard A. A New Algorithm for Image Noise Reduction using Mathematical Morphology [Text] / A. Richard// IEEE Transactions on Image Processing, Volume 4, Number 3, May 1995. - Pp. 554-568.

17. Адаптивное сглаживание для шумных ЦМР. [Электронный ресурс]. - Режим доступа: www.url: #"justify">Список публикаций автора по теме работы

31. Иванов Д.А. Подавление шума на изображениях и видеопоследовательностях [Текст]/ Д.А. Иванов// Международная научная конференция «Решетневские чтения», Москва, 2010. - Cс. 530-532.

. Иванов Д.А. Слежение за точечными особенностями на сценах из видеопоследовательности [Текст]/ Д.А. Иванов // Международная научная конференция « Невские чтения», Москва, 2011. - Cс. 485-487.

. Иванов Д.А. Методы улучшения качества архивных видеопоследовательностей [Текст]/ Д.А. Иванов // VII всероссийская научно-практическая конференция «Актуальные проблемы авиации и космонавтики», Москва, 2011. - Cс. 369-371.

. Иванов Д.А. Методы улучшения качества изображений [Текст]/ Д. А. Иванов // VI всероссийская конференция творческой молодежи «Актуальные проблемы авиации и космонавтики», Москва, 2010. - Cс. 224 -225.

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

Больше работ по теме: