Использование OpenCV для задач сегментации изображений

Рис. 3.2 - Оригинал изображения «Карты»

После того, как программа откроет изображение, так как мы использовали алгоритм маркерного водораздела, необходимо маркером отметить объекты и фон. (см. рис. 3.3)

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

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

Рис. 3.3 - Маркировка объектов и фона

Рис. 3.4 - Результат сегментации №1

Возьмем изображение посложнее, с более разнообразной цветовой палитрой и произведем те же манипуляции. (см. рис. 3.6)

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

Рис. 3.5 - Вторая карта перекрывает первую

Рис. 3.6 - Маркировка объекта и фона

Рис. 3.7 - Результат сегментации №2

Усложним задачу еще больше и возьмем еще более пеструю картинку с бликами. (см. рис. 3.8) Повторим эксперимент.

Рис. 3.8 - Маркировка объектов

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

Рис. 3.9 - Результат сегментации №3

3.2 Алгоритм сегментации GrabCut

3.2.1 Основная идея алгоритма

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

Алгоритм GrabCut является развитием GraphCut-а. Главной целью разработчиков алгоритма было сведение к минимуму взаимодействия алгоритма с пользователем, а именно они хотели сделать достаточным задание ограничивающего прямоугольника вокруг объекта для получения изначального приближения. Для этого они ввели итеративную схему сегментации. [7]

GrabCut - это итеративный алгоритм, который объединяет статистику и Graph Cut для выполнения детальной 2D-сегментации с очень ограниченным доступом, первоначально разработанным в Microsoft Research Cambridge.

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

Основные этапы алгоритма GrabCut заключаются в следующем:

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

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

3. На переднем плане и в фоновом режиме моделируются модели гауссовых смесей (GMM) с использованием алгоритма кластеризации Орчард-Бумана.

4. Каждому пикселю на переднем плане назначается наиболее вероятный гауссовский компонент в GMM переднего плана. Тот же идентификатор процесса, что и пиксели в фоновом режиме, но с компонентами базовых GMM.

5. Новые GMM выбираются из наборов пикселей, которые были созданы в предыдущем шаге.

6. Создан граф, и GraphCut используется для поиска новой классификации пикселей переднего и заднего фона.

7. Повторяются пункты 4-6 до тех пор, пока классификация не сходится.

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

Рис. 3.10 - Дополнительные метки объекта

3.2.2 Программная реализация

Листинг 3.2

#include "stdafx.h"

#include <opencv2/core/utility.hpp>

#include "opencv2/imgproc.hpp"

#include "opencv2/imgcodecs.hpp"

#include "opencv2/highgui.hpp"

#include <cstdio>

#include <iostream>

using namespace cv;

using namespace std;

const Scalar RED = Scalar(0, 0, 255);

const Scalar PINK = Scalar(230, 130, 255);

const Scalar BLUE = Scalar(255, 0, 0);

const Scalar LIGHTBLUE = Scalar(255, 255, 160);

const Scalar GREEN = Scalar(0, 255, 0);

const int BGD_KEY = EVENT_FLAG_CTRLKEY;

const int FGD_KEY = EVENT_FLAG_SHIFTKEY;

static void getBinMask(const Mat& comMask, Mat& binMask)

{

if (comMask.empty() || comMask.type() != CV_8UC1)

CV_Error(Error::StsBadArg, "comMask is empty or has incorrect type (not CV_8UC1)");

if (binMask.empty() || binMask.rows != comMask.rows || binMask.cols != comMask.cols)

binMask.create(comMask.size(), CV_8UC1);

binMask = comMask & 1;

}

class GCApplication

{

public:

enum{ NOT_SET = 0, IN_PROCESS = 1, SET = 2 };

static const int radius = 2;

static const int thickness = -1;

void reset();

void setImageAndWinName(const Mat& _image, const string& _winName);

void showImage() const;

void mouseClick(int event, int x, int y, int flags, void* param);

int nextIter();

int getIterCount() const { return iterCount; }

private:

void setRectInMask();

void setLblsInMask(int flags, Point p, bool isPr);

const string* winName;

const Mat* image;

Mat mask;

Mat bgdModel, fgdModel;

uchar rectState, lblsState, prLblsState;

bool isInitialized;

Rect rect;

vector<Point> fgdPxls, bgdPxls, prFgdPxls, prBgdPxls;

int iterCount;

};

void GCApplication::reset()

{

if (!mask.empty())

mask.setTo(Scalar::all(GC_BGD));

bgdPxls.clear(); fgdPxls.clear();

prBgdPxls.clear(); prFgdPxls.clear();

isInitialized = false;

rectState = NOT_SET;

lblsState = NOT_SET;

prLblsState = NOT_SET;

iterCount = 0;

}

void GCApplication::setImageAndWinName(const Mat& _image, const string& _winName)

{

if (_image.empty() || _winName.empty())

return;

image = &_image;

winName = &_winName;

mask.create(image->size(), CV_8UC1);

reset();

}

void GCApplication::showImage() const

{

if (image->empty() || winName->empty())

return;

Mat res;

Mat binMask;

if (!isInitialized)

image->copyTo(res);

else

{

getBinMask(mask, binMask);

image->copyTo(res, binMask);

}

vector<Point>::const_iterator it;

for (it = bgdPxls.begin(); it != bgdPxls.end(); ++it)

circle(res, *it, radius, BLUE, thickness);

for (it = fgdPxls.begin(); it != fgdPxls.end(); ++it)

circle(res, *it, radius, RED, thickness);

for (it = prBgdPxls.begin(); it != prBgdPxls.end(); ++it)

circle(res, *it, radius, LIGHTBLUE, thickness);

for (it = prFgdPxls.begin(); it != prFgdPxls.end(); ++it)

circle(res, *it, radius, PINK, thickness);

if (rectState == IN_PROCESS || rectState == SET)

rectangle(res, Point(rect.x, rect.y), Point(rect.x + rect.width, rect.y + rect.height), GREEN, 2);

imshow(*winName, res);

}

void GCApplication::setRectInMask()

{

CV_Assert(!mask.empty());

mask.setTo(GC_BGD);

rect.x = max(0, rect.x);

rect.y = max(0, rect.y);

rect.width = min(rect.width, image->cols - rect.x);

rect.height = min(rect.height, image->rows - rect.y);

(mask(rect)).setTo(Scalar(GC_PR_FGD));

}

void GCApplication::setLblsInMask(int flags, Point p, bool isPr)

{

vector<Point> *bpxls, *fpxls;

uchar bvalue, fvalue;

if (!isPr)

{

bpxls = &bgdPxls;

fpxls = &fgdPxls;

bvalue = GC_BGD;

fvalue = GC_FGD;

}

else

{

bpxls = &prBgdPxls;

fpxls = &prFgdPxls;

bvalue = GC_PR_BGD;

fvalue = GC_PR_FGD;

}

if (flags & BGD_KEY)

{

bpxls->push_back(p);

circle(mask, p, radius, bvalue, thickness);

}

if (flags & FGD_KEY)

{

fpxls->push_back(p);

circle(mask, p, radius, fvalue, thickness);

}

}

void GCApplication::mouseClick(int event, int x, int y, int flags, void*)

{

// TODO add bad args check

switch (event)

{

case EVENT_LBUTTONDOWN: // set rect or GC_BGD(GC_FGD) labels

{

bool isb = (flags & BGD_KEY) != 0,

isf = (flags & FGD_KEY) != 0;

if (rectState == NOT_SET && !isb && !isf)

{

rectState = IN_PROCESS;

rect = Rect(x, y, 1, 1);

}

if ((isb || isf) && rectState == SET)

lblsState = IN_PROCESS;

}

break;

case EVENT_RBUTTONDOWN: // set GC_PR_BGD(GC_PR_FGD) labels

{

bool isb = (flags & BGD_KEY) != 0,

isf = (flags & FGD_KEY) != 0;

if ((isb || isf) && rectState == SET)

prLblsState = IN_PROCESS;

}

break;

case EVENT_LBUTTONUP:

if (rectState == IN_PROCESS)

{

rect = Rect(Point(rect.x, rect.y), Point(x, y));

rectState = SET;

setRectInMask();

CV_Assert(bgdPxls.empty() && fgdPxls.empty() && prBgdPxls.empty() && prFgdPxls.empty());

showImage();

}

if (lblsState == IN_PROCESS)

{

setLblsInMask(flags, Point(x, y), false);

lblsState = SET;

showImage();

}

break;

case EVENT_RBUTTONUP:

if (prLblsState == IN_PROCESS)

{

setLblsInMask(flags, Point(x, y), true);

prLblsState = SET;

showImage();

}

break;

case EVENT_MOUSEMOVE:

if (rectState == IN_PROCESS)

{

rect = Rect(Point(rect.x, rect.y), Point(x, y));

CV_Assert(bgdPxls.empty() && fgdPxls.empty() && prBgdPxls.empty() && prFgdPxls.empty());

showImage();

}

else if (lblsState == IN_PROCESS)

{

setLblsInMask(flags, Point(x, y), false);

showImage();

}

else if (prLblsState == IN_PROCESS)

{

setLblsInMask(flags, Point(x, y), true);

showImage();

}

break;

}

}

int GCApplication::nextIter()

{

if (isInitialized)

grabCut(*image, mask, rect, bgdModel, fgdModel, 1);

else

{

if (rectState != SET)

return iterCount;

if (lblsState == SET || prLblsState == SET)

grabCut(*image, mask, rect, bgdModel, fgdModel, 1, GC_INIT_WITH_MASK);

else

grabCut(*image, mask, rect, bgdModel, fgdModel, 1, GC_INIT_WITH_RECT);

isInitialized = true;

}

iterCount++;

bgdPxls.clear(); fgdPxls.clear();

prBgdPxls.clear(); prFgdPxls.clear();

return iterCount;

}

GCApplication gcapp;

static void on_mouse(int event, int x, int y, int flags, void* param)

{

gcapp.mouseClick(event, x, y, flags, param);

}

int main(int argc, char** argv)

{

string filename = "C:\\Image.jpg";

if (filename.empty())

{

cout << "\nDurn, empty filename" << endl;

return 1;

}

Mat image = imread(filename, 1);

if (image.empty())

{

cout << "\n Durn, couldn't read image filename " << filename << endl;

return 1;

}

const string winName = "GrabCut segmentation";

namedWindow(winName, WINDOW_AUTOSIZE);

setMouseCallback(winName, on_mouse, 0);

gcapp.setImageAndWinName(image, winName);

gcapp.showImage();

for (;;)

{

int c = waitKey(0);

switch ((char)c)

{

case '\x1b':

cout << "Exiting ..." << endl;

goto exit_main;

case 'r':

cout << endl;

gcapp.reset();

gcapp.showImage();

break;

case 'n':

int iterCount = gcapp.getIterCount();

cout << "<" << iterCount << "... ";

int newIterCount = gcapp.nextIter();

if (newIterCount > iterCount)

{

gcapp.showImage();

cout << iterCount << ">" << endl;

}

else

cout << "rect must be determined>" << endl;

break;

}

}

exit_main:

destroyWindow(winName);

return 0;

}

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

Алгоритм GrabCut с высокой точностью отделил объект от фона. (см. рис. 3.11 и 3.12)

Рис. 3.11 - Оригинальное изображение

Рис. 3.12 - Результат сегментации алгоритма GrabCut

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

Рис. 3.13 - Оригинальное изображение

Рис. 3.14 - Результат сегментации

Поэтому алгоритм предусматривает возможность дополнительной маркировки переднего и заднего плана. (см. рис 3.15 и 3.16)

Рис. 3.15 - Маркировка переднего и заднего плана

Рис. 3.16 - Сегментация нескольких объектов

3.3 Алгоритм среднего сдвига (MeanShift)

3.3.1 Основная идея алгоритма

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

Метод среднего сдвига (MeanShift) первоначально был представлен в 1975 году Фукунагой и Хостетлером.

Алгоритм MeanShift относится к классу алгоритмов кластеризации, однако, в отличие от других алгоритмов кластеризации (k-means и др.), метод сдвига среднего не требует задания количества кластеров. MeanShift не является эвристическим алгоритмом и имеет математическое обоснование.

На вход подается изображение, представляющее из себя множество точек в двумерном пространстве. Предположим, что круговое окно сосредоточено на C и имеет радиус r в качестве ядра. Сдвиг среднего - это алгоритм восхождения к вершине, который включает итеративное перемещение этого ядра в область с более высокой плотностью до сходимости. Каждый сдвиг определяется средним вектором сдвига. Средний вектор сдвига всегда указывает на направление максимального увеличения плотности. На каждой итерации ядро смещается в центр. Метод вычисления этого среднего зависит от выбора ядра. В этом случае, если вместо плоского ядра выбирается гауссовское ядро, каждой точке сначала присваивается вес, который будет экспоненциально убывать по мере увеличения расстояния от центра ядра.

В OpenCV функция cvPyrMeanShiftFiltering реализует алгоритм, основанный на среднем сдвиге скопления цветов. Сегментация методом среднего сдвига находит пики распределения цвета в пространстве. Общим у алгоритмов сегментации и слежения является то, что они оба полагаются на способность среднего сдвига находить режимы (пики) распределения. Для множества многомерных точек (x, y, синий, зеленый, красный) алгоритм среднего сдвига может найти самую высокую плотность "сгустка" данных в данном пространстве при оконном сканировании над ним. Однако стоит обратить внимание на то, что пространственные переменные (x, y) могут сильно различаться в зависимости от величины цветового диапазона (синий, зеленый, красный). В данном случае необходимо иметь один радиус для пространственных переменных (spatialRadius) и ещё один для величины цвета (colorRadius). Средний сдвиг движущегося окна, все те точки которого сходятся в пике данных, становятся связанными или "принадлежащими" этому пику. Эта принадлежность, исходящая из самых плотных пиков, формирует сегментацию изображения. Сегментация на самом деле это градация пирамид (cvPyrUp(), cvPyrDown()), поэтому цветовое скопление на верхних уровнях пирамид (съежившиеся изображения) имеют границы, уточненные пирамидами нижнего уровня.

У cvPyrMeanShiftFiltering() имеется исходное src и конечное dst изображения. Оба изображения должны быть 8-битными, трехканальными цветными изображениями одинакового размера. spatialRadius и colorRadius определяют, как алгоритм среднего сдвига оперирует средними цвета и пространства для формирования сегментации. Для 640x480 изображения, алгоритм показывает хорошие результаты для значений spatialRadius = 2 и colorRadius = 40. Аргумент max_level определяет количество уровней пирамид, которые будут использованы для сегментации. Для 640x480 изображения max_level равен 2 или 3.

3.3.2 Программная реализация

Листинг 3.3