Отслеживание границ

Трассировку границ , также известную как трассировка контуров , двоичной цифровой области, можно рассматривать как метод сегментации , который идентифицирует граничные пиксели цифровой области. Отслеживание границ является важным первым шагом в анализе этого региона .Граница — топологическое понятие. Однако цифровое изображение не является топологическим пространством. Поэтому невозможно математически точно определить понятие границы в цифровом изображении. В большинстве публикаций по отслеживанию границы подмножества S цифрового изображения я описываю алгоритмы, которые находят набор пикселей, принадлежащих S и имеющих в непосредственной близости пиксели, принадлежащие как S, так и его дополнению I - S. Согласно этому определению граница подмножества S отличается от границы дополнения I – S, что является топологическим парадоксом.

Для правильного определения границы необходимо ввести топологическое пространство, соответствующее данному цифровому изображению. Такое пространство может представлять собой двумерный абстрактный клеточный комплекс. Он содержит ячейки трех измерений: двумерные ячейки, соответствующие пикселям цифрового изображения, одномерные ячейки или «трещины», представляющие собой короткие линии, лежащие между двумя соседними пикселями, и нульмерные ячейки или «точки», соответствующие углы пикселей. Тогда граница подмножества S представляет собой последовательность трещин и точек, а окрестности этих трещин и точек пересекают как подмножество S, так и его дополнение I – S.

Граница, определенная таким образом, в точности соответствует топологическому определению, а также соответствует нашему интуитивному представлению о границе, поскольку граница S не должна содержать ни элементов S, ни элементов его дополнения. Он должен содержать только элементы, лежащие между S и дополнением. Это именно трещины и точки комплекса.

Этот метод отслеживания границ описан в книге Владимира А. Ковалевского. ^[1] и на веб-сайте. ^[2]

Алгоритмы

Типы

Следование за пикселями: проходит по ячейкам и записывает их. Обычно отслеживается только внешняя граница и требуется постобработка при изменении размера пространства. Самый простой в реализации
Метод следования за вершинами: проход по краям, запись краев и углов. Обычно отслеживается только внешняя граница. Последовательные ребра можно удалить для упрощения данных.
На основе прогонных данных: обрабатывает все ячейки в пространстве. Отслеживает все границы изображения. Менее эффективен, чем другие типы, для небольших одиночных границ, поскольку необходимо обрабатывать все ячейки. Более эффективен для больших и сложных изображений, поскольку количество шагов на отдельную ячейку обычно меньше, чем у других типов. ^[3]

Примеры

Алгоритмы, используемые для отслеживания границ: ^[4]

Алгоритм трассировки квадратов. ^[5] Может использоваться только для 4-связных (недиагональных) шаблонов и требует, чтобы критерии остановки входили в начальную ячейку в том же направлении, что и начало.
Алгоритм трассировки соседей Мура аналогичен алгоритму трассировки Square с аналогичными недостатками, но работает с 8-связными (диагональными) шаблонами.
Радиальная развертка ^[6]
Алгоритм Тео Павлидиса ^[7] проверяет три ячейки впереди, но чек может быть закорочен. Может потерпеть неудачу на некоторых шаблонах.
Общий подход с использованием векторной алгебры для отслеживания границы можно найти по адресу ^[8]
Расширение отслеживания границ для сегментации прослеживаемой границы на открытые и закрытые части описано в разделе ^[9]

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

Алгоритм трассировки квадратов

Алгоритм трассировки квадратов прост, но эффективен. Его поведение полностью зависит от того, находится ли объект на черной или белой ячейке (при условии, что белые клетки являются частью фигуры). Сначала сканируйте сверху слева направо и ряд за рядом. После ввода первой белой клетки запускается ядро алгоритма. Он состоит в основном из двух правил:

Если вы находитесь в белой камере, идите налево.
Если вы находитесь в черной камере, идите направо.

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

public void GetBoundary(byte[,] image){    for (int j = 0; j < image.GetLength(1); j++)        for (int i = 0; i < image.GetLength(0); i++)            if (image[i, j] == 255)               // Found first white pixel                SquareTrace(new Point(i, j));}public void SquareTrace(Point start){    HashSet<Point> boundaryPoints = new HashSet<Point>();  // Use a HashSet to prevent double occurrences    // We found at least one pixel    boundaryPoints.Add(start);    // The first pixel you encounter is a white one by definition, so we go left.    // In this example the Point constructor arguments are y,x unlike convention    // Our initial direction was going from left to right, hence (1, 0)    Point nextStep = GoLeft(new Point(1, 0));                   Point next = start + nextStep;    while (next != start)    {        // We found a black cell, so we go right and don't add this cell to our HashSet        if (image[next.x, next.y] == 0)        {            next = next - nextStep;            nextStep = GoRight(nextStep);            next = next + nextStep;        }        // Alternatively we found a white cell, we do add this to our HashSet        else        {            boundaryPoints.Add(next);            nextStep = GoLeft(nextStep);            next = next + nextStep;        }    }}private Point GoLeft(Point p) => new Point(p.y, -p.x);private Point GoRight(Point p) => new Point(-p.y, p.x);

Радиальная развертка

Алгоритм Radial Sweep, часто обсуждаемый в литературе наряду с его более известным аналогом Moore-Neighbor Tracing , представляет, казалось бы, простой подход к трассировке контуров при обработке изображений . Хотя номенклатура алгоритма может вызвать ощущение сложности, его основополагающий принцип тесно связан со знакомой техникой трассировки соседей Мура.

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

Однако алгоритм радиальной развертки, функционально эквивалентный трассировке соседей Мура, открывает новый подход к идентификации следующего черного пикселя в окрестности Мура заданной граничной точки.

Инновация алгоритма заключается в его подходе к определению следующего граничного пикселя. После идентификации нового граничного пикселя, обозначенного как P, алгоритм устанавливает его как текущую точку интереса. Затем он создает воображаемый сегмент линии, соединяющий точку P с предыдущим граничным пикселем. Впоследствии алгоритм систематически вращает этот сегмент вокруг точки P по часовой стрелке, пока он не пересечется с черным пикселем в окрестности Мура точки P. ^[10] По сути, это вращательное движение отражает процесс проверки каждого пикселя, окружающего точку P в окрестности Мура.

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

Алгоритм Тео Павлидиса

Алгоритм Тео Павлидиса — это хорошо известный предложенный метод трассировки контуров в бинарных изображениях, предназначенный для методического обнаружения и отслеживания границ связанных компонентов. Этот метод начинается с определения начального граничного пикселя, который обычно является первым черным пикселем, видимым при сканировании изображения сверху вниз и слева направо. Он начинается с изучения окрестности текущего пикселя для поиска следующего граничного пикселя, часто двигаясь по часовой стрелке, чтобы найти следующий черный пиксель, составляющий границу. ^[10]

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

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

См. также

Ссылки

^ Ковалевский, В., Обработка изображений с помощью клеточной топологии, Springer 2021, ISBN 978-981-16-5771-9
^ http://www.kovalevsky.de , Лекция «Отслеживание границ на 2D-изображениях»
^ Со, Чонхун; Че, Сынхо; Шим, Джинвук; Ким, Дончул; Чонг, Чолхо; Хан, Тэк-Дон (март 2016 г.). «Алгоритм быстрой трассировки контуров на основе метода отслеживания пикселей для датчиков изображения» . Датчики . 16 (3): 353. Бибкод : 2016Senso..16..353S . дои : 10.3390/s16030353 . ПМЦ 4813928 . ПМИД 27005632 .
^ Алгоритмы трассировки контуров
^ Абир Джордж Гунейм: алгоритм трассировки квадратов
^ Абир Джордж Гунейм: Алгоритм радиальной развертки
^ Абир Джордж Гунейм: Алгоритм Тео Павлидиса
^ Отслеживание внешней и внутренней границы объекта в двоичных изображениях на основе векторной алгебры, Журнал достижений в области инженерных наук, том 3, выпуск 1, январь – июнь 2010 г., стр. 57–70 [1]
^ Сегментация прослеживаемой границы на открытые и закрытые подразделы на основе теории графов, Компьютерное зрение и понимание изображений, том 115, выпуск 11, ноябрь 2011 г., страницы 1552–1558 [2]
^ Перейти обратно: ^а ^б Редди, П. Раджашекар; В., Амарнад; Мекала, Бхаскар (январь 2012 г.). «Оценка критерия остановки в алгоритмах трассировки контуров». Международный журнал компьютерных наук и информационных технологий . 3 (3): 3888–3894. ISSN 0975-9646 . [3]

[1] Ковалевский, В., Обработка изображений с помощью клеточной топологии, Springer 2021, ISBN 978-981-16-5771-9

[2] ttp://www.kovalevsky.de , Лекция «Отслеживание границ на 2D-изображениях»

[Fast_Contour-Tracing_Algorithm_Based_on_a_Pixel-Following_Method_for_Image_Sensors-3] Со, Чонхун; Че, Сынхо; Шим, Джинвук; Ким, Дончул; Чонг, Чолхо; Хан, Тэк-Дон (март 2016 г.). «Алгоритм быстрой трассировки контуров на основе метода отслеживания пикселей для датчиков изображения» . Датчики . 16 (3): 353. Бибкод : 2016Senso..16..353S . дои : 10.3390/s16030353 . ПМЦ 4813928 . ПМИД 27005632 .

[4] Алгоритмы трассировки контуров

[5] Абир Джордж Гунейм: алгоритм трассировки квадратов

[6] Абир Джордж Гунейм: Алгоритм радиальной развертки

[7] Абир Джордж Гунейм: Алгоритм Тео Павлидиса

[8] Отслеживание внешней и внутренней границы объекта в двоичных изображениях на основе векторной алгебры, Журнал достижений в области инженерных наук, том 3, выпуск 1, январь – июнь 2010 г., стр. 57–70 [1]

[9] Сегментация прослеживаемой границы на открытые и закрытые подразделы на основе теории графов, Компьютерное зрение и понимание изображений, том 115, выпуск 11, ноябрь 2011 г., страницы 1552–1558 [2]

[Evaluation_of_Stopping_Criterion_in_Contour_Tracing_Algorithms-10] Перейти обратно: ^а ^б Редди, П. Раджашекар; В., Амарнад; Мекала, Бхаскар (январь 2012 г.). «Оценка критерия остановки в алгоритмах трассировки контуров». Международный журнал компьютерных наук и информационных технологий . 3 (3): 3888–3894. ISSN 0975-9646 . [3]

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]