Выделение объекта на фоне

10.1. Введение

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

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

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

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

10.2. Алгоритм "Волшебная палочка"

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

Рассмотрим, как производится шаг алгоритма. Пусть у нас есть изображение A с цветами пикселей A(x, y). Будем считать, что на множестве цветов задана метрическая функция $$\rho (C_1,C_2)$$, определяющая расстояние между двумя цветами.

Пусть пользователь указал пиксель (x0, y0) с цветом A(x0, y0). Тогда рассматривается двухцветное изображение B того же размера, что и A, задаваемое правилом

Иными словами, B содержит единицы для пикселей с цветом, отличающимся от цвета пикселя, указанного пользователем, не более чем на $$\tau,$$ где $$\tau$$ - порог чувствительности, задаваемый пользователем. Как мы увидим, чем он выше, тем больше пикселей выделится на данном шаге.

На втором этапе происходит нахождение связной области цвета 1 на изображении B, содержащей пиксель (x0, y0). Это может быть выполнено при помощи любого алгоритма заполнения области с затравкой (см. раздел 6.3). Найденная область $$\Omega$$ является связной и содержит пиксели цветов, похожих на цвет пикселя, который был указан пользователем.

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

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

10.3. Алгоритм "Умные ножницы"

Алгоритм "умные ножницы" (англ. intellegent scissors), представленный в 1996 году, быстро завоевал популярность и был встроен в самый мощный и широко распространенный редактор фотоизображений Adobe Photoshop под именем "магнитное лассо" (англ. magnetic lasso). На первый взгляд, он близок к алгоритму, представленному нами как "нулевой вариант": при использовании "умных ножниц" пользователь обводит границу между объектом и фоном. Однако, в отличие от "нулевого варианта", пользователь не должен указывать все точки границы. Вместо этого он указывает точки на границе с некоторым промежутком, а "умные ножницы" проводят граничную линию между последовательно указанными точками.

Рассмотрим алгоритм проведения граничной линии от одной точки до другой, используемый "умными ножницами". Как и раньше, будем считать, что у нас есть изображение A с цветами пикселей A(x, y) и дана метрическая функция $$\rho (C_1,C_2)$$, задающая расстояние между двумя цветами. Рассмотрим растровую решетку как граф, устроенный следующим образом. Вершинами графа служат углы пикселей, а ребрами графа - стороны пикселей. Будем считать, что пользователь в качестве последовательных граничных точек указал два угла пикселей, соответсвующих вершинам графа P и Q (рис. 10.2).

Припишем каждому ребру длинуЭта длина будет отлична от геометрической длины стороны пикселя., обратно зависящую от разницы между цветами пикселей, которые примыкают к ребру. Например $$d = \frac{L}{K+\rho (C_1,C_2)}$$, где d - приписываемая длина ребра, L - геометрическая длина ребра, C1 и C2 - цвета пикселей по обе стороны от ребра, а K - некоторая константа. В качестве граничной линии на участке между граничными точками P и Q "умные ножницы" выбирают кратчайший путь на графе, т.е. последовательность ребер, соединяющих вершины P и Q и имеющих минимальную суммарную длину. Поскольку ребра, соответствуюшие резким цветовым перепадам, имеют меньшую приписанную длину, "умные ножницы" стремятся провести границу именно по таким ребрам (рис. 10.2).

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

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

10.4. Сегментация при помощи разрезов на графах

Третий способ выделения объекта на фоне также основан на теории графов. Из всех рассматриваемых способов он имеет наиболее естественный интерфейс: пользователь просто отмечает некоторое множество A пикселей, принадлежащих объекту, и некоторое множество B пикселей, принадлежащих фону (см. рис. 10.4). Поскольку эти пиксели не обязаны быть рядом с границей, такая разметка не требует от пользователя особых усилий. Результатом алгоритма служит сегментация, в которой все множество A отнесено к объекту, а множество B - к фону.

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

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

Каждую вершину соединим с соседними вершинами (т.е. вершинами, расположенными в центрах 8-связно соседних пикселей). Таким образом, получившиеся ребра соединяют центры соседних пикселей. Припишем каждому ребру вес

где L - геометрическая длина ребра, C1 и C2 - цвета вершин, соединяемых ребром, $$\lambda$$ и $$\sigma$$ - некоторые (положительные) параметры. Отметим, что данный вес тем меньше, чем больше разница между цветами вершин.

Добавим в граф две вершины, называемые истоком и стоком (граф с этими вершинами называется сетью ). Эти вершины будем называть терминальными. Прочие вершины будем называть пиксельными. Соединим сток и исток ребрами с каждой вершиной графа. Ребрам, соединяющим исток с вершинами множества A, и ребрам, соединяющим сток с вершинами множества B, припишем бесконечный вес.

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

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

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

Что дает нам найденный минимальный разрез на указанном графе? Минимальный разрез будет проходить так, что (рис. 10.5):

Последние два пункта могут входить в противоречие друг с другом. Например, участок изображения может быть похож по цвету на фон (пиксели множества B ), но окружен вокруг по периметру пикселями множества A и при этом не отделен от них резкой границей. В таких случаях выбор параметра $$\lambda$$ в формуле (10.1) устанавливает баланс между последними двумя пунктами. Увеличивая значение $$\lambda,$$ мы увеличиваем важность того, чтобы граница между фоном и объектом проходила между пикселями с разными цветами, а уменьшая, мы увеличиваем важность того, чтобы пиксели, похожие по цвету на пиксели множества A (B), были отнесены к объекту (фону).

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

10.5. Заключение

Алгоритм "умные ножницы" был впервые представлен в [41]. Сегментация при помощи разрезов на графах была впервые представлена в [15]. Алгоритмы поиска кратчайшего пути на графе и минимального разреза на графе могут быть найдены, например, в [4] и [6].