Периметр не просто связанных двоичных изображений

Question

Я пытаюсь вычислить периметр области в двоичных изображениях. Когда область просто соединена, то есть у нее нет «дыр», все довольно просто: я просто проверяю каждый пиксель, принадлежит ли он области, и имеет хотя бы соседа, который не принадлежит области ... У меня есть переменная, которая считает количество пикселей, удовлетворяющих этому условию.

В случае региона с отверстиями я использую другой способ. Я начинаю с пикселя на границе и «прыгаю» к соседу (увеличивая счетчик), если он сам является граничным пикселем. Процедура, с еще несколькими причудами, заканчивается, когда я возвращаюсь к начальным пикселям. Примерно так:

int iPosCol = iStartCol, int iPosRow = iStartRow;
do 
{
  //check neighbors, pick point on the perimeter
  //condition: value == label, pixel at the border.
  check8Neighbors(iPosCol, iPosRow);
  updatePixPosition(iPosCol, iPosRow);
}
while ( iPosC != iStartC || iPosR != iStartR );

Проблема в том, что этот метод не будет работать, если отверстия в области находятся близко к границе (расстояние в 1 пиксель).

Существуют ли стандартные способы вычисления периметра не просто соединенных областей, или я неправильно подхожу к проблеме?

Answer 1

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

Запись в Википедии для Маркировка подключенных компонентов включает псевдокод для алгоритма "однократного прохода" (http://en.wikipedia.org/wiki/Connected-component_labeling).

http://en.wikipedia.org/wiki/Connected-component_labeling

Другой алгоритм однократного прохода можно найти в статье Чанга и Чена «Алгоритм маркировки компонентов, использующий технику трассировки контуров». Эта статья также включает описание алгоритма следования ребрам, который вы можете использовать, чтобы найти только контур, если хотите. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.58.3213

Эта статья достаточно хорошо описывает следование ребрам, но здесь я опишу основную идею.

Допустим, внешний контур фигуры представлен пикселями от a до f, а пиксели фона представлены символом "-":

- - - - -
- a b - -
- - - c -
- - - d -
- f e - -
- - - - -

Если мы сканируем изображение сверху вниз и вдоль каждой строки слева направо, то первый встреченный пиксель - это пиксель a. Чтобы перейти от пикселя a к пикселю b, а затем от b к c, мы отслеживаем направление каждого перемещения, используя 8 направлений, определенных относительно текущего пикселя, p:

6 7 8
5 p 1
4 3 2

Движение от фона "-" к пикселю "a" происходит вдоль направления 1. Хотя мы знаем, где находится "b", программа этого не делает, поэтому мы проверяем все направления по часовой стрелке относительно "a", чтобы найти следующее пиксель по контуру. Нам не нужно проверять направление 5 (слева), потому что мы только что пришли от фонового пикселя слева от «а». Мы проверяем направления по часовой стрелке 6, 7, 8, 1, 2 и т. Д., Ища следующий контурный пиксель. Мы находим «b» также вдоль направления 1 после нахождения только фоновых пикселей в направлениях 6, 7 и 8 относительно «a».

Если мы посмотрим на переход от c к d, мы сместимся в направлении 3. Чтобы найти следующий пиксель контура "e", мы проверим направления 8, 1, 2, 3, 4 и найдем пиксель контура "e «двигаясь в направлении 4.

Общее правило: если наше последнее движение было в направлении d, первое направление, которое мы проверяем для нашего следующего движения, - это направление d - 3. Если последнее движение было в направлении 5 (движение влево), то мы начинаем наше следующее поиск по часовой стрелке в направлении 2.

В коде мы обычно будем использовать направления 0 - 7, и, очевидно, вы будете использовать операцию по модулю или подобную математику, но я надеюсь, что идея ясна. Статья Чанга и Чена достаточно хорошо описывает основной алгоритм следования контурам, а также упоминает о необходимых проверках, должен ли алгоритм отслеживать некоторые пиксели.

---

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

Для алгоритма подключенного компонента следует помнить одну вещь: то, что вы хотите считать «соседом» пикселя. Вы можете посмотреть только на «4-х соседей»:

-  n  -
n  p  n
-  n  -

где «p» - центральный пиксель, «n» - четыре соседа, а «-» - пиксели, которые не считаются соседями. Вы также можете рассмотреть «8 соседей», которые являются просто всеми пикселями, окружающими данный пиксель:

n  n  n
n  p  n
n  n  n

Как правило, 4-соседи являются лучшим выбором при проверке подключения для объектов переднего плана. Если вы выберете технику с 8 соседями, то образец шахматной доски, подобный следующему, можно будет рассматривать как один объект:

p - p - p - p - p
- p - p - p - p - 
p - p - p - p - p
- p - p - p - p - 
p - p - p - p - p
- p - p - p - p - 

Допустим, у вас есть BLOB-объект, похожий на приведенный ниже, с пикселями переднего плана, помеченными как «p», и пикселями фона, помеченными как «-»:

- - - - - - - - - -
- - - - p p p - - -
- - p p p - p p - -
- - - p p - p p - -
- - - - p p p - - -
- p p p p p p - - -
- - - - - - - - - -

Если вы рассмотрите только пиксели внешнего контура, вы увидите, что вычисление периметра может быть немного сложным. Для пикселей 1, 2, 3, 4 и 5 ниже вы можете рассчитать периметр, используя пиксели 1 - 5, ступенчато перемещаясь от пикселя 1 к 2, затем от 2 до 3 и т. Д. Как правило, лучше рассчитать периметр для этого сегмента, используя только пиксели 1, 3 и 5 по диагонали. Для единственной строки пикселей внизу необходимо соблюдать осторожность, чтобы алгоритм не учитывал эти пиксели дважды.

- - - - - - - - - -
- - - - p p p - - -
- - 1 2 p - p p - -
- - - 3 4 - p p - -
- - - - 5 p p - - -
- p p p p p p - - -
- - - - - - - - - -

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

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

Для пикселя N и пикселя N + 1: если либо X одинаков, либо Y одинаков, то направление от N до N + 1 направлено влево, вправо, вверх или вниз, а расстояние равно 1.

Если X и Y различаются для пикселей N и N + 1, то направление перемещения от одного пикселя к следующему находится под углом 45 градусов к горизонтали, а расстояние между центрами пикселей является квадратным корнем из 2.

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

- - - - - - - - - -
- - - p p p p - - -
- - p p p p p p - -
- - p p p p p p - -
- - p p p p p p - -
- - - p p p p - - -
- - - - - - - - - -

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

1. Выберите порог для бинаризации изображения.
2. Запуск алгоритма маркировки подключенного компонента / региона на бинаризованном изображении
3. Используйте пиксели контура подключенной области для расчета периметра

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

Цифровая обработка изображений (3-е издание) Гонсалеса и Вудса

Книжный сайт: http://www.imageprocessingplace.com/

Вы сможете найти международное издание за 35 долларов США.

Если вы в конечном итоге пишете много кода для выполнения геометрических вычислений, другой удобный справочник - Геометрические инструменты для компьютерной графики - Шнайдер и Эберли.

http://www.amazon.com/Geometric-Computer-Graphics-Morgan-Kaufmann/dp/1558605940

Это дорого, но вы можете найти подержанные копии дешево иногда в поисковых системах, таких как

http://www.addall.com

Исправления, PDF-файлы теории и код из книги можно найти здесь: http://www.geometrictools.com/

Answer 2

Возможно, самое простое, что нужно сделать, - запустить алгоритм подключенного компонента, а затем заполнить дыры.

Answer 3

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

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

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

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

Надеюсь, этот ответ поможет.