Умные ножницы (Алгоритм)

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 16:00, 19 апреля 2016.
Статья по учебной дисциплине
Название дисциплины:

Обнаружение и распознавание сигналов

Раздел:

8. Распознавание и идентификация сигналов на физическом уровне

Глава:

8.1 Предварительная обработка изображений

Преподаватель:

Чичварин Н. В.

Алгоритм "умные ножницы" используется с 1996 году, завоевал популярность и был встроен в распространенный редактор фотоизображений Adobe Photoshop. При использовании алгоритма пользователь обводит границу между объектом и фоном, указывая точки на границе с некоторым промежутком, а "умные ножницы" проводят граничную линию между последовательно указанными точками.

Рис.1

Представим себе растр изображения в виде графа (рис.1) с ребрами, образованными сторонами пикселей. При указании пользователем двух последовательных точек и алгоритм "ножниц" вычисляет минимальное расстояние между точками и по ребрам графа, при этом условная геометрическая длина каждого ребра на этом пути имеет обратную зависимость от величины цветового перепада пикселей по его сторонам. Поскольку ребра, соответствующие резким цветовым перепадам, будут иметь меньшую условную длину, "умные ножницы" стремятся провести границу именно по таким ребрам. "Умные ножницы" существенно ускоряют процесс выделения объекта. Однако и они работают не очень хорошо при наличии пестрого фона и/или пестрого объекта. В таких случаях требуется указывать большее количество граничных точек. Сегментация при помощи разрезов на графах. Третий способ выделения объекта на фоне также основан на теории графов. Пользователь просто отмечает некоторое множество пикселей, принадлежащих объекту, и некоторое множество пикселей, принадлежащих фону. Поскольку эти пиксели не обязаны быть рядом с границей, такая разметка не требует от пользователя особых усилий. Результатом алгоритма служит сегментация, в которой все множество math>A\,\!</math> относится к объекту, а множество - к фону. Если результат выделения с первого раза не удовлетворяет пользователя, он добавляет в исходные множества пиксели, доотмечая их на изображении. Например, если алгоритм ошибочно отнес кусок объекта к фону, пользователь отмечает часть пикселей этого куска как пиксели объекта (множество math>A\,\!</math>). Результатом перезапуска алгоритма служит уточненная сегментация. Рассмотрим, как работает алгоритм. Построим граф на растре следующим образом. Пиксельные вершины графа расположим в центре каждого пикселя, а под цветом вершины мы будем понимать цвет пикселя. Каждую вершину соединим с соседними вершинами и получим восемь ребер, которые соединяют центры соседних пикселей. Припишем каждому ребру вес:

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

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

Рис.2

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

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

Пример выделения объекта приведен на рис.2.