РАСПОЗНАВАНИЕ ОБРАЗОВ И ОБНАРУЖЕНИЕ КОНТУРОВ ОБЪЕКТА НА ИЗОБРАЖЕНИИ

ВВЕДЕНИЕ

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

В последние годы с ростом популярности интеллектуальных / носимых мобильных сенсорных устройств, таких как смартфоны, умные часы и умные очки, различные приложения реального времени, такие как распознавание кода изображения, распознавание лица, оптическое распознавание символов (OCR).), распознавание логотипов, дополненная реальность (AR) и смешанная реальность (MR) появились для сенсорных вычислений. Поскольку интеллек­туальные / носимые мобильные сенсорные устройства обладают ограниченными аппаратными ресурсами, такими как низко производительные процессоры, память небольшого размера, дисплеи с низким разрешением и низкая емкость аккумулятора, им требуются простые и быстрые алгоритмы обработки изображений.

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

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

Статья организована следующим образом. В разделе 2 мы классифицируем традиционные алгоритмы трассировки контуров и вводим их характеристики. Затем, в разделе 3, мы анализируем их производительность на основе точности и скорости. Впоследствии в разделе 4 описывается предложенный алгоритм, а также описываются процедура его трассировки контуров, методика сжатия контурных данных и методика восстановления. В разделе 5 мы представляем сравнение обычных алгоритмов и предложенного алгоритма на основе их производительности, а также экспериментальные результаты, которые включают количество отслеживаемых пикселей и время обработки для изображений в реальном времени для крупных размеров. Кроме того, мы сравниваем размер сжатых данных и их восстановленные результаты с исходными пикселями контура с трассировкой. Наконец, в разделе 6 мы суммируем характеристики и экспериментальные результаты предложенного алгоритма.

2. Связанные работы

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

2.1. Обзор

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

Рисунок 1. Примеры контурных трасс полученные с использованием алгоритмов контурной трассировки

Категория алгоритмов трассировки контуров. (а) алгоритм слежения за пикселями; (б) алгоритм следования за вершиной; (c) алгоритм, основанный на данных прогона.

2.1.1. Пиксельный метод

Метод следования за пикселями отслеживает пиксели контура предварительно определенным образом, а затем сохраняет их координаты в памяти в соответствии с порядком трассировки. На рисунке 1а алгоритм отслеживает контурные пиксели в направлении по часовой стрелке от текущего пикселя, то есть последовательно ищет соседние черные пиксели текущего пикселя с использованием относительного направленного порядка, такого как левый, передний левый, передний, передний правый, справа, сзади, справа и сзади. Методы слежения за пикселями, такие как простой ограничитель границ (SBF), модифицированный SBF (MSBF), улучшенный SBF (ISBF), трассировка соседа Мура (MNT), алгоритм радиальной развертки (RSA) и алгоритм Тео Павлидиса (TPA), имеют простые правила для отслеживания пикселей контура на основе цепного кода. Этим методам требуется память размера кадра, чтобы отслеживать контур и генерировать ошибочные изображения при увеличении контурного изображения, поскольку они поддерживают только пиксельные координаты.

2.1.2. Метод следования вершин

Метод следования вершин отслеживает вершины контурных пикселей, которые располо­жены по краям между контурными пикселями и фоновыми пикселями. Его процедура аналогична процедуре следования за пикселями, потому что она использует цепочечный код и требует памяти размера кадра для трассировки контура; однако, он отслеживает углы пикселей контура и их соединенные края. Кроме того, он сохраняет угловые точки пикселов контура, чтобы сохранить отслеживаемую информацию о контуре, и данные могут быть сжаты путем уменьшения количества точек на прямой линии. Например, на рис. 1, б пять точек контура от s до t могут быть сохранены, поскольку есть только две угловые точки, на основе (x, у) системы координат. Более того, когда контурные изображения увеличиваются, метод следования вершин может обеспечить правильное изображение, поскольку отслеживаемые точки образуют границы контура.

2.1.3. Метод, основанный на данных прогона

Следующий метод, основанный на данных прогона, который включает в себя трассировку конечных точек данных прогона, использует данные прогона в парах, состоящих из левого и правого краев объекта, которые получаются с использо­ванием горизонтальных линий сканирования слева на право на изображении. Объект может иметь внешний контур и дополнительные внутренние контуры. Таким образом, существует пять типов данных прогона: (левый край внешнего контура, правый край внешнего контура), (левый край внешнего контура, левый край внутреннего контура), (правый край внутреннего контура, левый край внутреннего контура), (правый край внутреннего контура, правый край внешнего контура) и (правый край внешнего контура, левый край внешнего контура). Для отслеживания контура метод следования на основе данных прогона создает отношение следования прогона между краевыми точками двух соседних линий сканирования. На рисунке 1c, Scan Line # 3 обнаруживает (левый край 5, правый край 6), и Scan Line # 4 обнаруживает (левый край 7, правый край 8). Впоследствии генерируются последующие отношения между 5 и 7 и между 8 и 6. Этот метод использует только один или два линейных буфера и поэтому требует меньшего объема памяти по сравнению с методами слежения за пикселями и вершинами. Примерами этого метода являются метод кода направления (код RD), метод на основе таблицы PXY и метод OpenCV.

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

Таблица 1.

Сравнение алгоритмов следования контурам

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

2.2. Обычные алгоритмы трассировки контуров

Позвольте мне быть двоичным цифровым изображением с M × N пикселями, где координата крайнего левого верхнего пикселя равна (0, 0), а координата нижнего правого пикселя равна (M - 1, N - 1). В I пиксель может быть представлен как P = (x, y), x = 0, 1, 2, ⋯, M - 1, y = 0, 1, 2, ⋯, N - 1. Большинство алгоритмов трассировки контуров использовать трассировщик T (P, d) с абсолютной информацией о направлении d ∈ {N, NE, N W, W, S W, S, S E, E, N E}, и они имеют следующую основную последовательность:

Трассировщик начинает контурную трассировку на контуре объекта после сохранения начальной точки вместе с ее начальным направлением.

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

Если трассировщик достигает начальной точки, процедура трассировки завершается.

Чтобы определить следующую точку контура, которая может быть пикселем контура или углом пикселя, трассировщик обнаруживает интенсив­ность своего соседнего пикселя P r и новое абсолютное направление d r для P r, используя информацию об относительном направлении r ∈ {f r o n т, е т о н т - л е е т, л е е т, т е г - л е е т, гe a r, r e a r - r i g h t, r i g h t, r ∈ {f r o n t - r i g h t}. Например, если абсолютное направление текущего индикатора T (P, d) равно N, то левое направление индикатора d L e f t равно W, аналогично, левый пиксель трассера P L e f tравен (x - 1, y). На рис. 2, а, б показана информация о направлении трассировщика, а на рис. 2, в показаны различные типы контурных пикселей. Пиксели контура можно разделить на четыре типа, а именно: прямая линия, пиксель внутреннего угла, пиксель внешнего угла и пиксель внутреннего внешнего угла. На рисунке 2 с, «О» представляет собой внешний угол, «Я» представляет собой внутренний угол, и «Я О» представляет собой внутренний-наружный угол в соответствии с локальным рисунком контура.

Рисунок 2. Представление «О» внешнего угла собой и представление «Я» внутреннего угол собой в соответствии с локальным рисунком контура

Направления и типы контурных пикселей. (а) Абсолютное направление d; (б) относительное направление r; (c) типы контурных пикселей: пиксель внутреннего угла (I), пиксель внешнего угла (O) и пиксель внутреннего внешнего угла (I O).

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

2.2.1. Простой Граничный Последователь

Простой ограничитель границ (SBF) также известен как алгоритм черепахи Пейперта и алгоритм квадратной трассировки, и это самый простой алгоритм трассировки контуров. Первоначально местоположение трассировщика S сохраняется, и трассировщик перемещается в левом или правом направлении. Если средство отслеживания пикселей находится на пикселе контура, средство отслеживания перемещается влево; в противном случае он движется вправо. Процедура показана в Алгоритме 1.

Алгоритм 1. Алгоритм простого граничного повторителя.

1: процедура SBF

2: T (P, d) ← S (P, d)

3: делать

4: если P = черный, то

5: T (P, d) ← T (P L e f t, d L e f t)

6: еще

7: T (P, d) ← T (P R i g h t, d R i g h t)

8: в то время как T (P, d) ≠ S (P, d)

2.2.2. Модифицированный простой последователь границы

SBF не может отследить пиксель внутреннего внешнего угла, который расположен слева сзади, и для отслеживания этих пикселей был разработан модифицированный SBF (MSBF). Если трассировщик примыкает к левому заднему внутреннему внешнему углу, это условие подразумевает, что его левый задний пиксель является черным (объект), а левый и задний пиксели белым (фон); трассировщик переместится в левый задний пиксель, а затем его направление изменится в направлении заднего. После движения трассировщик идет прямо к левому пикселю, чтобы избежать бесконечного цикла. На рисунке 3 показаны примеры путей SBF и MSBF для внутреннего внешнего угла в направлении слева направо. В случае SBF, если трассировщик находится на пикселе A с направлением N, он пропускает пиксель B, Напротив, то MSBF может объезд пиксель B.

Рисунок 3. Примеры путей SBF и MSBF для внутреннего внешнего угла в направлении слева направо

Обход внутреннего-внешнего угла у левого заднего пикселя (модифицированная версия). (а) Простой граничный повторитель (SBF); (б) модифицированный SBF (MSBF).

2.2.3. Улучшенный простой последователь границы

SBF и MSBF требуют операций перемещения для контурных и фоновых пикселей; следовательно, время теряется во время движения на фоновом пикселе, и они не могут проследить внутренний угловой пиксель перед трассером [7, 22]. Следовательно, мы предложили улучшенный SBF (ISBF) [7], который основан на наших предыдущих исследованиях, направленных на преодоление этих ограничений. ISBF имеет шесть случаев для следования контурным пикселям на основе локальных шаблонов контурных пикселей. Модифицированная версия [16] ISBF показана в Алгоритме 2.

Алгоритм 2. Алгоритм улучшенного простого граничного повторителя.

1: процедура ISBF

2: T (P, d) ← S (P, d), где P на черном

3: делать

4: если P L e f t = черный, то

5: // Случай 4a: Левый сосед

6: T (P, d) ← T (P L e f t, d L e f t)

7: еще

8: если P L e f t - R e a r = черный и P R e a r = белый, то

9:// Случай 4b: Внутренний внешний угол слева сзади

10: T (P, d) ← T (P L e f t - R e a r, d R e a r)

11: еще

12: если Р Р г о н т - л е е т = черный, то

13: если P F r o n t = черный, то

14:// Случай 4d: Внутренний стержень спереди

15: T (P, d) ← T (P F r o n t, d)

16: T (P, d) ← T (P L e f t, d)

17: еще

18: // Случай 4c: Внутренний-внешний угол в передней левой части

19: T (P, d) ← T (P Ф р о н т - Л е ф т, д)

20: остальное, если Р Р г о н т = черный, то

21: // Случай 4e: передний сосед

22: T (P, d) ← T (P F r o n t, d R i g h t)

23: еще

24:// Случай 4f: Внешний угол

25: T (P, d) ← T (P, d R e a r)

26: в то время как T (P, d) ≠ S (P, d)

ВЫВОД

В этой статье мы предложили алгоритм трассировки контуров для отслеживания контуров в устройствах с низкой производительностью, таких как мобильные телефоны, КПК и встроенные устройства, которые имеют процессор с ограниченными вычислительными возможностями и небольшой объем памяти. Предложенный алгоритм отслеживает пиксели контура на основе метода следования за пикселями, а также может преобразовывать информацию о контуре в сжатые данные и точно восстанавливать ее до исходного контура с использованием метода следования за вершиной. Предложенный алгоритм многократно выполняет два этапа трассировки. Сначала трассировщик перемещается к следующему пикселю на основе его левого и левого заднего пикселей. Затем он перемещается на основе переднего и переднего левого пикселей. На этих двух этапах трассировки предложенный алгоритм извлекает два смежных пикселя контура вместе. Поскольку предложенный алгоритм отслеживает смежные пары пикселей за один шаг, есть больше возможных случаев формы, которую может принять контур. Поэтому классификация контура сложнее, чем обычные алгоритмы. С другой стороны, эта классификация на самом деле требует меньше времени для вычисления, потому что она уменьшает дублирование обнаружения фоновых пикселей. Кроме того, на основе классифицированных случаев мы можем определить репрезентативные точки и точки внутреннего внешнего угла, которые основаны на координатах вершин, и мы можем сохранить данные контура в виде точек, чтобы уменьшить размер данных. Кроме того, мы предложили алгоритм восстановления, чтобы извлечь все пиксели контура из репрезентативных точек и точек внутреннего внешнего угла. Предложенный алгоритм выполняет точное восстановление и может восстанавливать внутренние и внешние углы, которые не учитывались в обычных алгоритмах, такой как метод кода RD и метод PXY. Другой характеристикой предлагаемого алгоритма является то, что он может отслеживать требуемый тип связности, поскольку он способен различать разные типы соединений контурных пикселей. Например, предлагаемый алгоритм может трассироваться без внутренних углов, что аналогично характеристикам MNT и RSA.