8-подключение не является более точным, и на практике это подходит только для определенных приложений.Чаще всего используется 4-связность, особенно для «естественных» изображений, а не изображений, созданных в лаборатории для тестирования.8-соединенная область будет включать шахматные узоры и зигзагообразные шумы.4-связанный передний план дает 8-связанный фон.
Вы можете покопаться в источнике для функции OpenCV cvFindContours ().Есть привязки OpenCV к Python.http://opencv.willowgarage.com/documentation/python/structural_analysis_and_shape_descriptors.html
http://opencv.willowgarage.com/wiki/PythonInterface
Я бы рекомендовал сначала реализовать алгоритм с 4-мя связями.Вы можете найти псевдокод в книгах, таких как:
- Машинное зрение: теория, алгоритмы, практические действия Э. Р. Дэвиса В 3-м издании см. Раздел 6.3, «Маркировка и подсчет объектов»«
- Цифровая обработка изображений Гонсалеса и Вудса. См. Раздел 9.5.3« Извлечение подключенных компонентов ». Презентация менее ясна, но это стандартный учебник« все в одном »для изображенияобработка.Раздел о пороге для бинаризации хорош.Международное издание стоит около 35 долларов.
- Старые учебники могут иметь простые и понятные описания.Использованные копии
Computer Vision от Ballard и Brown довольно дешевые.В этой книге Алгоритм 5.1 называется Blob Coloring. - Мое любимое краткое описание можно найти в разделе «Алгоритм маркировки области» Справочник по обработке изображений и видео , отредактированный Аль Бовиком.Удобно, что страницы 44 - 45 доступны в Интернете в Google Книгах: http://books.google.com/books?id=UM_GCfJe88sC&q=region+labeling+algorithm#v=snippet&q=region%20labeling%20algorithm&f=false
Для распознавания текста обычно ищут темные связанные области (пятна) на светлом фоне.Наше бинаризованное изображение будет черным передним планом (0) на белом фоне (1) в 1-битном изображении.
Для алгоритма с 4-мя связями вы будете использовать элементы структуры, подобные показанным ниже (что вы также увидите в книге Bovik).После того, как вы возились с 4-связностью, расширение на 8-соединение должно быть очевидным.
Мы сканируем каждый ряд пикселей на изображении слева направо, ивсе ряды сверху вниз.Для любого пикселя (x, y) его левый сосед (x - 1, y) и верхний сосед (x, y - 1) уже отсканированы, поэтому мы можем проверить, был ли номер региона уже присвоен одному или обоимиз тех соседей.Например, если пиксель (x, y-1) помечен как область 8, и если (x, y) также является пикселем переднего плана, то мы назначаем область 8 (x, y).Если pixel (x, y) является пикселем переднего плана, но левый и верхний соседи являются пикселями фона, мы назначаем новый номер области (x, y).
Я рекомендую ссылку на Bovik, но вот краткий обзор алгоритма.
- Инициализация контура номера региона (например, "region = 0")
- Инициализацияструктура данных «эквивалентности регионов» для последующей обработки.
- Создание черно-белого изображения с использованием порога бинаризации.
- Сканирование каждого пикселя изображения сверху вниз, слева направо.
- Назначение области 0 любому белому (1) пикселю.
- Для любого черного пикселя переднего плана (x, y) проверьте следующие условия:
- Если верхний и левый пикселипереднего плана, используйте номер региона для (x-1, y) в качестве номера региона для (x, y) и отслеживайте эквивалентность левого и верхнего номеров регионов.
- Если только левый сосед (x- 1, y) является пикселем переднего плана, используйте номер его области для (x, y)
- Если только верхний сосед (x, y - 1) является пикселем переднего плана, используйте его номер области для (x,y)
- Если левый и верхний соседи являются пикселями фона, увеличьте номер региона и присвойте этот новый номер региона (x, y).
- После завершения этой обработкидля всего изображения проанализируйте матрицу эквивалентности и сведите каждую коллекцию эквивалентных областей к одной области.
Сокращение эквивалентностей - сложная часть. На изображении ниже регионы были правильно помечены в соответствии с алгоритмом. Изображение показывает разные цвета для каждого номера региона. Три соприкасающиеся области должны быть сведены к одной связанной области.
Ваш код должен сканировать структуру данных эквивалентности, чтобы переназначить 2 (красный) и 3 (темно-синий) в область с наименьшим номером, которая равна 1 (желтый). После переназначения номера региона маркировка региона завершается.
Существуют однопроходные алгоритмы, которые полностью исключают необходимость проверки эквивалентности, хотя такие алгоритмы немного сложнее реализовать. Я бы порекомендовал сначала реализовать традиционный алгоритм 4-связности, решить его проблемы, а затем ввести возможность использовать вместо него 8-связность. (Этот параметр распространен в библиотеках обработки изображений.) После того, как у вас будет работать маркировка областей с 4 и 8 подключениями, у вас будет хороший алгоритм, который найдет много применений. При поиске научных работ по этому предмету проверьте «маркировка региона», «пятна», «контуры» и «связность».
Для алгоритмов серой шкалы, которые необходимо преобразовать в двоичную форму, ваш пороговый алгоритм, вероятно, станет слабым звеном в вашей цепочке алгоритмов. Чтобы получить помощь по пороговому значению, получите книгу Гонсалеса и Вудса. Для распознавания текста посмотрите книгу Системы распознавания символов , написанную Шериет, Кармой, Лю и Суен.