Контур образа: Алгоритм поиска

Проблема найти контур образа рано или поздно возникает почти у каждого. Когда возникла у меня, этот алгоритм, за неимением лучшего, пришлось придумать. Думаю, есть масса аналогов. Проблема алгоритма поиска контура образа в том, что никто не спешит им делиться.

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

Формальное описание алгоритма

Что такое образ

Изначально, у нас есть некое изображение, цветное, чёрно-белое, не важно. Вначале, нужно понять, что является образом, а что — фоном. Например, для изображения, поддерживающих альфа-канал, фоном может считаться пиксель, имеющий прозрачность выше (ниже) какого-то порога. Если нет альфа-канала, мы можем перевести изображение в оттенки серого и по порогу определить, что у нас белое, что чёрное. Что есть фон, что образ. Когда-то пространно распинался об этом в статье.

Допустим, у нас такое изображение

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

Вот такой получился образ по порогу 146

Что такое контур образа

Контур образа — это линия границы, где встречается белое с чёрным. Это черта, за которой белое закончилось… Осталось только чёрное… И так будет продолжаться до тех пор, пока снова не встретиться белое… Вот в этот момент, при переходе из чёрного в белое, снова возникает точка границы, точка контура.

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

Задача алгоритма

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

Основной болью является поиск следующей точки. Вот мы нашли каким-то образом стартовую, наугад, первую попавшуюся чёрную точку. А дальше что, куда? Есть алгоритм жука, но он неточен. Есть ещё ряд каких-то невнятных алгоритмов. Когда искал по этой теме, а это было очень давно, ничего подходящего не нашёл. Поэтому и решил сделать сам.

Особенность алгоритма

Решил отказаться от поиска следующей точки совсем. Мне показалось это очень расточительным и не оптимальным. Я буду искать линии.

Конвертируем образ в набор линий. Каждая линия строго горизонтальна, имеет одну координату Y, и две по оси X — справа и слева. Таким образом, одна линия — это две точки границы образа, между которыми чернота… Пространство между точками линии гарантировано не пересекается с другими контурами или отверстиями. Теперь такая линия — это единица измерения нашего алгоритма. Работаем только с линиями.

Проблема поиска следующей точки перерождается в поиск нужной линии. А линия — это гарантированные точки границы образа и порядок следования в итоговом полигоне.

Постулаты

Если представить, что наш алгоритм идёт сверху вниз, то возникает ряд постулатов, сильно упрощающих и понимание, и количество условных операторов.

Первый постулат
Стартовая линия контура — это линия, над которой нет необработанных линий.
Второй постулат
Если мы идём вниз, то есть Y-координата следующей линии на единицу больше текущей, то мы всегда включаем в контур только левую координату линии.
Третий постулат
Если мы идём вверх, то есть Y-координата следующей линии на единицу меньше текущей, то мы всегда включаем в контур только правую координату линии.
Постулат четвёртый
Куда мы ни шли, в конечном счёте мы обязательно вернёмся в стартовую линию. Мы не потеряемся в бесконечной рекурсии, не завернём в бесконечный цикл, если будем четко соблюдать постулаты 2 и 3.

Теперь детали. Всегда самое важное — это детали. Когда начинаешь смотреть реальные случаи, которые возникают при обработке образа, глаза разбегаются, кажется, что вариантов сотни. На самом деле их шесть.

Шесть вариантов обработки линии

Вариант 1

Сверху нет ни одной необработанной линии, следовательно, линия стартовая (постулат 1). Направление — вниз. Добавляем в контур левую точку (постулат 2).

Вариант 2

Двигаюсь вниз. Смотрю вниз, нахожу линию, проверяю, не накрывает ли её альтернативная линия сверху и слева от меня. Если нет никого, движение остаётся вниз, и добавляю левую координату найденной линии (постулат 2).

Вариант 3

Двигаюсь вниз, нахожу линию ниже меня, определяю, что эту линию накрывает альтернативная линия, которая расположена левее моей левой координаты. Меняю направление на вверх. Запоминаю правую координату альтернативной линии (постулат 3).

Вариант 4

Ниже меня нет ни одной обработанной линии. Меняю направление на вверх. Добавляю свою правую координату (постулат 3)

Вариант 5

Двигаюсь вверх. Нахожу линию сверху меня, проверяю, есть ли альтернативная линия снизу от найденной и правее меня. Если нет никого, движение остаётся вверх, и добавляю правую координату найденной линии (постулат 3).

Вариант 6

Двигаюсь вверх, нахожу линию выше меня, определяю, что эту линию затрагивает альтернативная линия снизу, которая расположена правее моей правой координаты. Меняю направление на вниз Запоминаю левую координату альтернативной линии (постулат 2).

Повторяем варианты 2-6 до тех пор, пока не сработает постулат 4 — мы обязательно вернёмся в стартовую линию. Добавляем правую координату стартовой линии.

Контур найден.

Режим «зануды»

В этом режиме алгоритм идёт ступеньками, сохраняя каждый шаг этих ступенек. На практике оказалось мало толку.

Реализация алгоритма

Подготовка образа

Давайте вначале получим истинное чёрно-белое изображение.

Создание истинного чёрно-белого изображения

[свернуть]

Для конвертации образа в набор линий, введём следующий тип записи:

Для получения контура образа у нас есть класс TIPLineBorders, который хранит в себе список линий образа. Чтобы добавить линию, существует соответствующий метод:

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

Получение из образа списка линий

[свернуть]

Однако, нам ведь незачем тратить время, чтобы вначале найти образ, потом преобразовать его в набор линий. Давайте совместим это в одном методе:

Сортировка линий

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

После выполнения сортировки необходимо проинициализировать поле FIndex в элементе линии.

Тип для контура образа

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

Почему запись называется «узел». Изначально планировалось, что результатом работы алгоритма будет дерево, в котором каждый уровень будет либо силуэт, либо дырка. Но на практике хватило двух уровней — первый уровень, это силуэты. И в каждом силуэте список узлов — отверстий.

Для добавления нового узла существует следующий метод:

Вспомогательные функции для нахождения контура

Функции реализуют действия, описанные в вариантах.

Процедура просто добавляет точку в массив точек контура:

Следующие процедуры добавляют в контур либо левую, либо правую точку линии (для выполнения постулатов 2 и 3). Для отверстий, на единицу корректируется координата по Х. Также, в линию устанавливается признак, в каком качестве эта линия уже включилась в контур, слева или справа.

Следующая функция играет ключевую роль в алгоритме. Она ищет следующую линию от заданной. Список уже отсортирован, поэтому, если задано направление вниз (AForwardDirect=True), значит перебираем линии от заданной линии (ALine) в направлении конца списка, вперёд. Если указано обратное направление, вверх (AForwardDirect=False), значит идём к началу списка.

Линия считается найденной, если она «касается» заданной линии либо сверху, либо снизу, в зависимости от AForwardDirect. При этом, если указана «текущая» линия (ACurrent), то должно быть соблюдено ещё одно условие.

ACurrent — это линия, с которой результирующая линия должна лежать на одной координате Y, но при этом вся находиться либо справа от ACurrent (при AForwardDirect=True), либо вся слева (при AForwardDirect=False).

Находим контур образа

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

Находим все контуры

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

Оптимизация и выпрямление контура

Алгоритм прекрасно находит контур, но в нём чрезвычайно много точек. Чтобы его оптимизировать, убрать точки, которые находятся примерно на одной прямой, используем алгоритм Рамера–Дугласа–Пойкера.

Алгоритм, представленный в статье по ссылке выше, оперирует вещественными точками. Здесь мы работаем с координатами пикселей, поэтому смело копипастим у себя же (ну а для чего ещё публиковалось) и переделываем на целочисленные координаты.

Целочисленный алгоритм Рамера–Дугласа–Пойкера

[свернуть]

Для оптимизации найденного контура в нашем классе присутствует специальный метод. Параметр AEpsilon отвечает за степень «выпрямления».

Убрать шум

В конечном счёте получаем набор хороших контуров. Среди которых большую половину занимают двухточечные линии, длиной в 2-3 пикселя. Конечно, в итоговом изображении, они подчёркивают некоторые детали. Оживляют картинку. Но нам они зачастую не нужны. Поэтому, есть возможность избавиться от них.

Итоговый метод нахождения контура образа

Просто соберём всё в одном методе

Как использовать: На примере выгрузки в WMF

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

Давайте сформируем контуры и выгрузим, например, в метафайл.

Выгрузка контуров в метафайл выглядит так:

Нахождение контура образа по этапам

Немного по интерфейсу

При запуске демки появится следующее окно. Ананас пришёл от Вадима, который в телеге поднял вопрос, и я обещал описать алгоритм. Исполняю обещание.

В правом окне, при нажатой кнопке BW, видим силуэт, полученный в результате обработки изображения, представленного слева. Получение образа происходит по пороговому значению, представленному в поле Threshold. Галка в поле Use Alpha, означает, что обрабатывается байт прозрачности. Если галка снята, то обработка происходит путём перевода в оттенки серого и разделения цветов по порогу.

Чтобы загрузить новое изображение, необходимо вызвать контекстное меню в левом окне. Выбрав Paste, вставим картинку из буфера обмена. При выборе Load загрузим файл картинки с диска.

При загрузке изображения, мы можем увидеть справа либо черный квадрат, либо ничего. Это означает, что загруженное изображение не имеет альфа-канал. При этом, галка о том, что мы используем альфа-канал, установлена. В этом случае, просто снимаем галку.

Так выглядит ананас, в котором при получении истинного чёрно-белого изображения не используется альфа-канал.

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

Изображения можно масштабировать через Ctrl+Wheel. Просто Wheel перемещает изображение по вертикали. Shift+Wheel перемещает картинку по горизонтали. Также доступны скроллбары. Они появляются, когда надо, и когда не надо плавно исчезают ))).

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

Этап 1: Получение образа

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

Снимаем галку с Use Alpha, меняем значение в поле Threshold, пока образ справа не станет удовлетворительным.

Этап 2: Формируем список линий

Нажимаем кнопку Lines. После этого, в названии кнопки появится число в скобках — это количество линий в списке. Изображение справа будет состоять из разноцветных линий. По кнопке Ln сверху всегда можно посмотреть, как эти линии выглядят.

Также, внизу видим надпись: Lines: 0,637. Это время выполнения операции в миллисекундах.

Этап 3: Формируем контур образа

Нажимаем кнопку Contour. После этого видим в скобках количество точек во всех обнаруженных контурах. А справа будут отображены эти контуры. Красным рисуются внешние контуры, синим — внутренние. Если масштаб позволяет, то рисуем также и точки контуров. По кнопке Cr сверху всегда можно посмотреть, как выглядит найденный контур.

Как видим, всего точек в контурах задействовано 1750. Время операции также отображается в нижней полосе — Contour: 0,243 мсек.

Галка на Detail Mode активирует режим «зануды». Можно посмотреть отличия в найденных контурах. Лично я его почти не пользую, потому что уж слишком зануда. Каждый пиксел обойдёт.

Этап 4: Оптимизируем контур образа

Нажимая кнопку Ramer, мы тем самым запустим алгоритм Рамера–Дугласа–Пойкера. И удивимся насколько точек стало меньше:

Итак, было 1750, стало 227. Время в нижней полосе — Ramer: 0,156. Если сравнить с рисунком выше, то узелков стало явно сильно меньше.

Параметр Epsilon задаёт параметр «выпрямления» контура. Его можно менять и видеть как меняется контур. Жать кнопку не обязательно, а зрелище довольно залипательное. Значение, передаваемое алгоритму, делится на 10. То есть в алгоритм, судя по скрину, ушёл коэффициент, равный 1.

Этап 5: Убираем шум

За убирание шума отвечает кнопка Noise.

Было 227, стало 185. Время в нижней полосе — Noise: 0,011. Cравнивая с рисунком выше, можно заметить, что некоторые «сгустки» узелков ушли.

Параметр Distance задаёт максимальную длину удаляемых «штрихов» и также делится на 10. То есть, на самом деле мы удаляли отрезки, длиной до 4 пикселов.

Всё сразу

Чтобы выполнить поиск всех контуров и протестировать метод FindContours, жмём кнопку Run. По кнопке RD сверху всегда можно посмотреть, как будет выглядеть образ, нарисованный полигонами и линиями.

Видим справа нарисованное полигонами изображение. Зайчик получился не такой душка, как слева. Не тронь мою морковку. Внизу видим общее время работы алгоритма — All: 0.967.

Воспользуемся контекстным меню в правом окне и выберем выгрузку в SVG.

Небольшие тесты

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

Как видим, алгоритм нашёл правильные точки. А если посмотрим сколько точек было изначально, то это прямо супер-оптимизация.

Посмотрим, что у нас по скорости.

Изображение 1280×915 алгоритм полностью разобрал на атомы за 30,751 миллисекунду. По моему, это очень неплохо.

И немного сюрра в этот оазис (это анимированный гиф, вначале держу драматическую паузу):


Листинг модуля IP76.ImageContour

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

Никаких дополнительных связей нет. Модуль абсолютно автономен. Отвечает только поставленной задаче — найти контур.

IP76.ImageContour: Модуль нахождения контура образа