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

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

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

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

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

Этот метод трассировки границ описан в книге Владимира Александровича Ковалевского ^[1] и на сайте ^{[2] .}

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

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

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

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

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

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

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

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 ) // Найден первый белый пиксель SquareTrace ( new Point ( i , j )) ; }                              public void SquareTrace ( Point start ) { HashSet <Point> borderPoints = new HashSet <Point> (); // Используем HashSet для предотвращения двойных вхождений // Мы нашли как минимум один пиксель borderPoints.Add ( start ) ;            // Первый пиксель, с которым вы сталкиваетесь, по определению белый, поэтому мы идем налево. // В этом примере аргументы конструктора Point - это y,x, в отличие от соглашения // Наше изначальное направление было слева направо, поэтому (1, 0) Point nextStep = GoLeft ( new Point ( 1 , 0 )); Point next = start + nextStep ; while ( next != start ) { // Мы нашли черную ячейку, поэтому мы идем направо и не добавляем ее в наш HashSet if(image[next.x,next.y] == 0 ) { next = next - nextStep ; nextStep = GoRight ( nextStep ) ; next = next + nextStep ; } // В противном случае мы нашли белую ячейку , мы добавляем ее в наш HashSet else { borderPoints.Add ( next ) ; nextStep = GoLeft ( nextStep ) ; next = next + nextStep ; } } }                                                       частная точка GoLeft ( точка p ) => новая точка ( p . y , - p . x ); частная точка GoRight ( точка p ) => новая точка ( - p . y , p . x );              

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

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

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

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

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

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

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

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

• Поиск пути
• Эскиз кривой
• Код цепочки
• Пиксельное подключение
• Проблема оптимизации