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

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

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

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

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

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

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

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

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

Аннотация

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

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

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

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

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

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

Год защиты: 2012

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

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

Abstract

The development of search algorithms and compensation effects of

rain on the video sequences

Scientific adviser - Doctor of technical sciences, professor

Course of qualification: 230100.68 Informatics and computing techniques

Master's Program: Intelligent Systems

Institute of informatics and telecommunications

Department of informatics and computing techniques

Year of defense: 2012

In the 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.

Keywords: 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.1.2 Мультифрактальный метод распознавания

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

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

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

, (1.2)

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

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

(1.3)

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

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

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

1.1.3 Метод гистограмм

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

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

, (1.4)

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

n_j - общее число точек яркости r_j;

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

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

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

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

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

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

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

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

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

Гистограммы являются основой для многочисленных методов пространственной обработки. Методы с использованием гистограмм очень эффективны, потому что они требуют только один проход по пикселам. Оптимальным с точки зрения зрительного восприятия человеком является изображение, элементы которого имеют равномерное распределение яркостей [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 - Архитектура сети Хопфилда

1.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)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

На рисунке 1.4 H₁ (G₁) - высокочастотный фильтр анализа (синтеза), а H₂ (G₂) - низкочастотный фильтр анализа (синтеза).

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

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

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

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

1.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: а) исходное изображение; б) обработанное изображение

1.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 приведена сравнительная характеристика программных продуктов по параметрам.

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

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

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

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

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

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