В статье расскажу как достаточно быстро перечислить связные объекты на бинарном растре. Этот алгоритм мы использовали для распознавания изображений и текстов; он отличается от подобных высокой скоростью обработки (на картинках до 3200x2400, с некоторыми оговорками, он отрабатывает за миллисекунды) и доступностью в понимании (при наличии некоторых знаний C++). Отмечу, что исходная картинка будет трактоваться алгоритмом как «только для чтения» (зачем портить то, с чем могут работать другие методы), и в связи с этим, алгоритму потребуется небольшое количество дополнительной памяти. Кроме того, внешние контуры являются полезным объектом для анализа и векторизации изображений.
Итак, задача: исходное изображение (массив точек Image) преобразовать в список контуров. Контур — это просто набор внешних точек для связной части изображения. Например, контур для залитого круга — окружность, полученная из всех внешних точек.
Используется восьми-связность, то есть, две точки связны, если они являются соседями по отношению к направлениям вверх-влево-вправо-вниз и по диагоналям. Таким образом, у каждой точки может быть до восьми соседей. Небольшая подготовка
Начнем построение алгоритма, который достаточно эффективно получает контур по заданной начальной внешней точке объекта со следующей структуры:
class Contour : public Points
{
// references to the constructor params
const Image& SourceImage;
ImageMap& CurrentImageMap;
public:
/* here we assume that image is coherent in any of 8 ways,
* so if the pixel will not have neighbor in any of 4 diagonal and 4 straight directions
* then it will be considered as separate image part */
// extract contour and mark all coherent points on image map
Contour(const Image& img, ImageMap& map, const Point& start);
private:
// private methods for contour pass implementation only
void passDownLeft(Point& p, bool InvertedAxis = false);
Point movePoint(const Point& src, int x, int y, bool InvertedAxis = false);
Point commitPoint(const Point& p);
};Здесь перечислены все необходимые объекты и методы, которые мы рассмотрим. Конструктор сомнений не вызывает, SourceImage тоже.
Что такое ImageMap? В действительности, алгоритму построения контура необходимо как-то помечать точки, чтобы предотвращать повторное их посещение, поэтому рассмотренные точки будут маркированы номером объекта, к которому они принадлежат.
Казалось бы, это потребует памяти столько же, сколько занимает исходная картинка, но мы будем использовать более эффективную структуру. Нет смысла тратить память на точки, не принадлежащие контуру или лежащие внутри него, так что хочется хранить только граничные точки с небольшими накладными расходами и уметь быстро их адресовать.
В основе структуры лежит индекс блоков изображения размером STEP2. Сам индекс представляет собой массив ссылок на блоки, размером X/STEP * Y/STEP, где X и Y — разрешение исходной картинки. При обращении к блоку на запись, он выделяется в памяти и соответствующий индексный элемент маркируется его указателем. В самом худшем случае, мы получим использование памяти равное размеру картинки, если каждая (n*STEP,m*STEP) точка будет промаркирована, но в среднем мы экономим 50-90% памяти. Индексация, как вы уже догадались, производится просто делением координат на STEP, и если STEP — степень двойки, то это работает замечательно быстро.
Кстати, после выполнения алгоритма, ImageMap представляет собой результат задачи перечисления объектов на изображении.
Метод commitPoint служит для добавления точки в контур и ассоциации ImageMap с текущим контуром:
Point Contour::commitPoint(const Point& p)
{
if (!CurrentImageMap.isAssigned(p) && SourceImage.isFilled(p))
{
CurrentImageMap.assignSegment(p, this);
push_back(p);
}
return p;
}
Конечно, это уже детали реализации, но здесь все просто, и может быть переиспользовано. Функция movePoint тоже совсем несложная, просто добавляет к точке заданное приращение:
Point Contour::movePoint(const Point& src, int x, int y, bool InvertedAxis)
{
Point p = src;
if (InvertedAxis)
{
x = -x;
y = -y;
}
p.X += x;
p.Y += y;
return p;
}
Параметр InvertedAxis, как нетрудно догадаться, просто меняет приращение на противоположное (это нам потом пригодится).
Ядро алгоритма
Что ж, теперь интересное. Собственно, сама функция обхода: passDownLeft. Для заданной начальной точки мы хотим обойти объект, двигаясь вниз, и по возможности влево.
Пока мы находимся в пределах объекта (т.е. цвет текущей точки не равен цвету фона):
- Опустимся на одну точку вниз, относительно текущей.
- Если левая точка, относительно новой текущей заполнена — то нам повезло, двигаемся влево «до упора». Если точка над самой левой заполнена — то мы нашли самопересечение и выходим из обхода.
- Если не заполнена, двигаемся вправо, пока не достигнем заполненной точки.
Звучит достаточно просто, но точная реализация выглядит чуть сложнее:
void Contour::passDownLeft(Point& p, bool InvertedAxis)
{
while (SourceImage.isInside(p))
{
commitPoint(p);
// step one point down
p = movePoint(p, 0,1, InvertedAxis);
// select one of neighbors which is filled, prefer left one...
Point left = movePoint(p, -1,0, InvertedAxis);
if (SourceImage.isFilled(left))
{
p = commitPoint(left);
// ...and shift left as many as possible
while (SourceImage.isInside(p))
{
Point left = movePoint(p, -1,0, InvertedAxis);
if (!SourceImage.isFilled(left))
break; // no more left neighbors
p = commitPoint(left);
Point up = movePoint(p, 0,-1, InvertedAxis);
if (SourceImage.isFilled(up))
return; // crossed inside area
}
}
else
{
// selection still unfilled...
while (SourceImage.isInside(p) && !SourceImage.isFilled(p))
{
// ...shift right by connected points and test again
Point right = movePoint(p, 1,0, InvertedAxis);
Point rightUp = movePoint(right, 0,-1, InvertedAxis);
if (!SourceImage.isFilled(rightUp))
return; // no more bottom right neighbors
commitPoint(rightUp);
p = commitPoint(right);
}
}
}
}Функция isInside проверяет, лежит ли точка в пределах картинки, дабы не выйти за ее границы.
Запустив этот обход на тестовой картинке (салатовые точки — стартовые для обхода каждого объекта) мы, как и следовало ожидать не получим контуров, так как процесс построения упрется в самые нижние точки каждого объекта. Поэтому одной такой функции не достаточно. Но, дополнить контур можно производя обход вверх-вправо, что легко получается предусмотренным на этот случай флажком InvertedAxis! Таким образом, дополнить алгоритм построения контура позволит специально оставленный напоследок конструктор:Сontour::Contour(const Image& img, ImageMap& map, const Point& start)
: SourceImage(img), CurrentImageMap(map)
{
bool doneSomething = true;
Point p = start;
for (int iter = 0; doneSomething; iter++)
{
size_t count = size();
passDownLeft(p, iter % 2 == 1);
doneSomething = size() > count;
}
}
Мы будем чередовать обходы вниз-влево и вверх-вправо, до тех пор, пока это будет добавлять новые точки в контур.
Итак, мы получили рабочий метод перечисления всех точек внешнего контура для заданного объекта изображения, работающий за линейное время, относительно количества точек этого контура.
Перечисление стартовых точек
Дело осталось за малым — по исходной картинке найти все стартовые точки для построения контуров:
void Vectorization::getContours()
{
Point p(0,0); // line-by-line scan to extract contours of objects
for (p.Y = 0; p.Y < SourceImage.getHeight(); p.Y++)
{
for (p.X = 0; p.X < SourceImage.getWidth(); p.X++)
{
if (SourceImage.isFilled(p) && !ImageMap.isAssigned(p))
{
// that pixel is unprocessed yet, so extract the contour starting from it
Contour* c = new Contour(SourceImage, ImageMap, p);
// add new contour
ContoursStorage.push_back( c );
}
}
}
}Вот он-то пока и является самой медленной частью алгоритма: ведь нужно обойти каждую точку изображения.
Но его оптимизация тоже практически лежит на поверхности: будем использовать такую же индексную структуру, как при хранении ImageMap, поделив изображение на блоки размера STEP2.
void Vectorization::getContoursOptimized()
{
Point pIndex(0,0); // step-by-step scan
for (pIndex.Y = 0; pIndex.Y < SourceImage.getHeight(); pIndex.Y += STEP)
{
for (pIndex.X = 0; pIndex.X < SourceImage.getWidth(); pIndex.X += STEP)
{
if (!SourceImage.isEmptyIndex(pIndex))
{
Point pLocal = pIndex;
for (pLocal.Y = pIndex.Y ; pLocal.Y < STEP; pLocal.Y++)
{
for (pLocal.X = pIndex.X ; pLocal.X < STEP; pLocal.X++)
{
if (SourceImage.isFilled(pLocal))
{
if (Map.isAssigned(pLocal))
{
pLocal.X = dynamic_cast<Contour*>(Map.getSegment(pLocal))->getMaxX(pLocal.Y);
break; /* skip already processed points by getting the max contour X for the specified Y */
}
// that pixel is unprocessed yet, so extract the contour starting from it
Contour* cntr = new Contour(SourceImage, Map, pLocal);
// add new contour
ContoursStorage.push_back( cntr ) ;
}
}
}
}
}
}
}Сложность такого алгоритма пропорциональна количеству точек внешних контуров для объектов изображения.
Подвох
Из последнего факта следует, что данный метод в общем-то не очень хорош на изображениях, где практически нет ни одной группы связанных точек, при этом заполнение точками близко к полному из возможных (25% — каждая вторая точка по каждой координате заполнена, остальные — нет).
Но с точки зрения проблематики обработки изображений такие картинки — просто шум, который легко срезается предварительными фильтрами. Так что все хорошо :)
