Преобразование Хафа (Hough Transform) -- это метод для поиска линий, кругов и других простых форм на изображении.

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

Существует и так называемое Обобщённое преобразование Хафа, с помощью которого можно искать фигуры произвольной формы.
Детектор границ Кенни

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

Причины возникновения краёв

· изменение освещенности;

· изменение цвета;

· изменение глубины сцены (ориентации поверхности).

Получается, что края отражают важные особенности изображения и поэтому, целями преобразования изображения в набор кривых являются:

· выделение существенных характеристик изображения;

· сокращение объема информации для последующего анализа.

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

Шаги детектора

· Убрать шум и лишние детали из изображения;

· Рассчитать градиент изображения;

· Сделать края тонкими (edge thinning);

· Связать края в контура (edge linking).

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

Сегментация изображений

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

К областям, получаемым в результате сегментации, предъявляются следующие требования:

1. Области должны быть однородны относительно определенных характеристик.

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

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

4. Границы каждого сегмента должны быть простыми, пространственно точными.

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

Выделяют следующие алгоритмы сегментации:

1. Алгоритмы пороговой обработки.

2. Алгоритмы классификации пикселей (включая релаксацию, подходы на основе случайного поля марковского типа и подходы на основе нейронных сетей).

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

4. Алгоритмы сегментации цветных изображений.

5. Алгоритмы выделения краев.

Алгоритм пороговой обработки

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

Пороговая обработка полутонового изображения заключается в разделении всех элементов изображения на два класса по признаку яркости, где f0 - некоторое "пороговое" значение яркости.

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

Алгоритм классификации пикселя

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

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

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

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

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

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

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

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

Алгоритмы сегментации цветных изображений

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

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

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

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

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

3) Кластеризация в пространстве цветов с использованием аппарата нечеткой логики (fuzzy logic). Для всех пикселей вычисляются нечеткие функции принадлежности и определяются нечеткие кластеры. Четкие кластеры получаются в результате анализа степени принадлежности. Далее изображение разбивается на связные области.

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

1) Методы наращения областей. Задается некоторое количество базовых однородных областей, после чего используются различные стратегии для объединения соседних областей.

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

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

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

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

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

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

В своей работе я уже описал самые распространенные алгоритмы - алгоритм Канни и преобразование Хафа. Однако существует еще целый ряд эффективных алгоритмов

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

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

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

Алгоритм Робертса

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

Листинг программы