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

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

Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования
«Московский государственный машиностроительный университет (МАМИ)»

Отчет

по курсу «Проектная деятельность»

на тему

«Техническое зрение»

Группа 141-161

Выполнил: Бушуев Иван

Руководитель: Марков Н.И.

Москва 2015

Основные алгоритмы обработки

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

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

· обнаружение объектов и изменений в сцене наблюдения;

· высокоточные измерения элементов сцены;

· слежение за объектами;

· самоориентация и самопозиционирование;

· реконструкция поверхностей и обнаружение трехмерных структур;

· описание сцены и идентификация объектов;

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

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

Метод Собеля

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

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

Алгоритмы выделения краев объекта - student2.ru

Данный оператор используется для приближенного вычисления градиента функции интенсивности пикселей. Применение оператора G{x} позволяет определить приближенное значение первой частной производной изменения интенсивности в горизонтальном направлении, G{y} – в вертикальном. На основании данной информации можно вычислить магнитуду градиента для пикселя с координатами (i,j) согласно формуле Алгоритмы выделения краев объекта - student2.ru . Также используя полученные данные, можно определить направление градиента как Алгоритмы выделения краев объекта - student2.ru

Алгоритмы выделения краев объекта - student2.ru Алгоритмы выделения краев объекта - student2.ru

Результаты алгоритма Собеля

Очевидно, что применение горизонтального оператора Собеля позволяет отчетливо выделить вертикальные ребра, а вертикального – горизонтальные ребра.

Метод Перевитта Робертса

Оператор Робертса

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

Алгоритмы выделения краев объекта - student2.ru

Рисунок 2. Окрестность 3х3 внутри изображения

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

Алгоритмы выделения краев объекта - student2.ru и Алгоритмы выделения краев объекта - student2.ru

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

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

Алгоритмы выделения краев объекта - student2.ru Алгоритмы выделения краев объекта - student2.ru

Результаты алгоритма Перевитта и Робертса

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

Оператор Лапласа

Математически оператор Лапласа представляет сумму квадратов вторых частных производных Алгоритмы выделения краев объекта - student2.ru . Дискретный аналог оператора Лапласа используется при обработке изображений, в частности, для определения ребер объектов на изображении. Ребра формируются из множества пикселей, в которых оператор Лапласа принимает нулевые значения, т.к. нули вторых производных функции соответствуют экстремальным перепадам интенсивности.

Простейшим оператором является оператор Лапласа. Оператор Лапласа (Лапласиан) 3×3 имеет маску следующего вида:

Алгоритмы выделения краев объекта - student2.ru

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

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

Алгоритмы выделения краев объекта - student2.ru

Сегментация

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

Автоматические методы

Сегментация как разбиение изображения на однородные области

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

Ясно, что задача разбиения изображения на однородные области поставлена некорректно. Нет единства в выборе разбиения изображения. Далеко не всегда для изображения есть единственно «правильная» сегментация, и далеко не всегда задача сегментации имеет единственное решение. По той же причине нет и объективного критерия оценки качества разбиения изображения.

Алгоритмы выделения краев объекта - student2.ru

Варианты сегментации изображения

Кластеризация цветового пространства

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

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

Методы теории графов

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

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

Алгоритмы выделения краев объекта - student2.ru Алгоритмы выделения краев объекта - student2.ru

Пример моделирования изображения взвешенным графом.

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

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

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

Наши рекомендации