Детектирование границ

Детектирование границ — это фундаментальная задача компьютерного зрения и обработки изображений, заключающаяся в выделении на цифровом изображении точек, в которых яркость или цвет резко изменяются. Такие изменения, как правило, соответствуют физическим границам объектов, краям, линиям, текстурам или теням. Результатом детектирования является бинарное изображение (карта границ), где пиксели, принадлежащие границам, отмечены одним значением (например, 1), а остальные — другим (0). Детектирование границ является важным этапом предобработки для многих задач более высокого уровня, таких как сегментация изображений, распознавание объектов, анализ движения и 3D-реконструкция.

История

Первые алгоритмы детектирования границ появились в 1960-х годах вместе с развитием цифровой обработки изображений. Одним из пионеров в этой области был Лоуренс Робертс, который в 1963 году предложил простой, но эффективный оператор (оператор Робертса), основанный на вычислении разности яркостей по диагоналям. В 1970-х годах Ирвин Собел и Гари Фельдман разработали более устойчивый к шуму оператор Собеля, который до сих пор широко используется в учебных целях и простых приложениях.

Значительный прорыв произошел в 1986 году, когда Джон Канни опубликовал свою работу «A Computational Approach to Edge Detection». Предложенный им алгоритм (детектор границ Канни) стал одним из самых популярных и эффективных классических методов. Он включает в себя несколько этапов: сглаживание изображения, вычисление градиента, подавление немаксимумов и двойную пороговую фильтрацию. Алгоритм Канни остается эталоном качества для многих задач и по сей день.

В 1990-х и 2000-х годах активно развивались методы, основанные на вейвлет-преобразовании, математической морфологии и статистических подходах. С 2010-х годов, с ростом вычислительных мощностей и доступности больших наборов данных, доминирующее положение заняли методы глубокого обучения, в частности сверточные нейронные сети (CNN). Они позволяют достигать значительно более высокой точности и робастности по сравнению с классическими подходами, особенно на сложных изображениях с большим количеством шума и текстур.

Классификация методов

Методы детектирования границ можно разделить на две основные категории: классические (аналитические) и основанные на машинном обучении.

Классические методы

Классические методы обычно основаны на вычислении первой или второй производной функции яркости изображения.

• Методы на основе градиента (первая производная): Ищут локальные максимумы модуля градиента. К ним относятся:
• Оператор Робертса: Использует простые ядра 2x2 для вычисления градиента по диагоналям. Очень чувствителен к шуму.
• Оператор Собеля: Использует ядра 3x3 для вычисления градиента по горизонтали и вертикали. Обладает сглаживающим эффектом, что делает его более устойчивым к шуму, чем оператор Робертса.
• Оператор Превитта: Аналогичен оператору Собеля, но с другим способом аппроксимации градиента.
• Детектор Канни: Многоэтапный алгоритм, включающий фильтрацию Гаусса, вычисление градиента, подавление немаксимумов и двойную пороговую фильтрацию. Обеспечивает хорошее соотношение точности обнаружения, локализации и минимизации ложных срабатываний.

• Методы на основе второй производной: Ищут точки пересечения нуля второй производной (лапласиана). К ним относится:
• Лапласиан гауссиана (LoG): Сначала изображение сглаживается гауссовым фильтром, затем вычисляется лапласиан. Границы находятся в точках, где лапласиан меняет знак (пересечение нуля).

Методы на основе машинного обучения

Современные методы, как правило, превосходят классические по точности.

• Методы на основе глубокого обучения: Используют сверточные нейронные сети (CNN), обученные на больших наборах данных с размеченными границами.
• HED (Holistically-Nested Edge Detection): Одна из первых успешных архитектур, использующая многоуровневое обучение для извлечения признаков на разных масштабах.
• RCF (Richer Convolutional Features): Улучшенная версия HED, использующая все сверточные слои для получения более богатых признаков.
• DexiNed (Dense Extreme Inception Network): Современная архитектура, основанная на плотных соединениях и модулях Inception, демонстрирующая высокое качество детектирования.

• Методы на основе случайных лесов (Random Forests): Классический подход машинного обучения, где каждый пиксель классифицируется как граница или не граница на основе набора признаков (например, интенсивность, градиент, текстурные характеристики).

Характеристики и показатели качества

Для оценки качества детектирования границ используются следующие метрики:

• Точность (Precision): Доля истинно положительных пикселей среди всех пикселей, отмеченных как границы.
• Полнота (Recall): Доля правильно обнаруженных границ среди всех реальных границ на изображении.
• F-мера (F-measure): Гармоническое среднее точности и полноты. Является наиболее распространенной метрикой для сравнения алгоритмов.
• Средняя ошибка (Average Error): Среднее расстояние между обнаруженными и истинными границами.
• ODS (Optimal Dataset Scale) и OIS (Optimal Image Scale): Метрики, используемые в наборе данных BSDS500 (Berkeley Segmentation Dataset and Benchmark). ODS — оптимальный порог для всего набора данных, OIS — оптимальный порог для каждого изображения индивидуально.

Применение

Детектирование границ является ключевым этапом во многих областях компьютерного зрения и обработки изображений:

• Сегментация изображений: Границы часто используются для разделения изображения на отдельные объекты или регионы.
• Распознавание объектов: Выделенные границы служат основой для извлечения признаков (например, контуров), которые затем используются для классификации объектов.
• Анализ медицинских изображений: Выделение границ органов, опухолей, кровеносных сосудов на МРТ, КТ и рентгеновских снимках.
• Автономное вождение: Обнаружение границ дороги, пешеходов, других транспортных средств и препятствий.
• Обработка спутниковых снимков: Выделение границ зданий, дорог, водоемов и сельскохозяйственных угодий.
• Робототехника: Навигация роботов в пространстве, манипуляция объектами.
• Фотография и видео: Улучшение резкости изображения, создание художественных эффектов (например, стилизация под мультфильм).

Примеры

• Детектор Канни: Является классическим примером и используется в библиотеках OpenCV, scikit-image и MATLAB. Настройка параметров (порогов гистерезиса) позволяет адаптировать алгоритм под конкретные задачи.
• HED: Показывает отличные результаты на изображениях с большим количеством текстур и сложных сцен. Модели HED доступны в репозиториях на GitHub.
• DexiNed: Одна из лучших современных моделей, демонстрирующая высокое качество на эталонных наборах данных (BSDS500, NYUDv2).

Критика и ограничения

Несмотря на значительный прогресс, детектирование границ остается сложной задачей. Основные ограничения включают:

• Чувствительность к шуму: Классические методы сильно подвержены влиянию шума, что приводит к ложным срабатываниям.
• Чувствительность к освещению: Изменение освещения может существенно изменить карту границ.
• Проблема масштаба: Границы объектов могут быть видны на разных масштабах. Один алгоритм может хорошо обнаруживать мелкие детали, но пропускать крупные контуры, и наоборот.
• Текстурные границы: Текстуры (например, трава, кирпичная стена) могут создавать множество ложных границ, которые трудно отличить от истинных.
• Неоднозначность определения границы: В некоторых случаях граница объекта может быть размытой или нечеткой, что затрудняет ее однозначное выделение.

Интересные факты

• Алгоритм Канни, несмотря на свой возраст, до сих пор является одним из самых популярных и часто используемых методов в промышленности.
• Набор данных BSDS500 (Berkeley Segmentation Dataset and Benchmark) является одним из самых известных и используемых для оценки алгоритмов детектирования границ. Он содержит 500 изображений с ручной разметкой границ, выполненной несколькими людьми.
• В 2020-х годах методы глубокого обучения достигли точности, сопоставимой с человеческой разметкой на некоторых эталонных наборах данных.

Источники

1. Canny, J. (1986). A Computational Approach to Edge Detection. IEEE Transactions on Pattern Analysis and Machine Intelligence, 8(6), 679-698.
2. Roberts, L. G. (1963). Machine Perception of Three-Dimensional Solids. MIT Lincoln Laboratory Report.
3. Sobel, I., & Feldman, G. (1973). A 3x3 Isotropic Gradient Operator for Image Processing. Stanford Artificial Intelligence Project.
4. Xie, S., & Tu, Z. (2015). Holistically-Nested Edge Detection. Proceedings of the IEEE International Conference on Computer Vision (ICCV).
5. Liu, Y., et al. (2017). Richer Convolutional Features for Edge Detection. Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR).
6. Poma, X. S., et al. (2020). Dense Extreme Inception Network: Towards a Robust CNN Model for Edge Detection. Proceedings of the IEEE/CVF Winter Conference on Applications of Computer Vision (WACV).
7. Martin, D. R., et al. (2001). A Database of Human Segmented Natural Images and its Application to Evaluating Segmentation Algorithms and Measuring Ecological Statistics. Proceedings of the IEEE International Conference on Computer Vision (ICCV).
8. Gonzalez, R. C., & Woods, R. E. (2018). Digital Image Processing (4th ed.). Pearson.