способ сегментации растровых изображений на основе выращивания и слияния областей

Формула изобретения

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

2. Способ сегментации по п.1, отличающийся тем, что вейвлет-статистику вычисляют как функцию от исходного изображения.

Описание изобретения к патенту

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

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

Метод выращивания областей в простейшей его реализации [Гонсалес Р.С. Цифровая обработка изображений [Текст] / Р.С.Гонсалес, Р.Э.Вудс. - М.: Техносфера, 2005. - 1072 с. - ISBN 5-94836-028-8. - с.875] можно описать так:

- на исходном изображении выбираются точки (центры кристаллизации), предположительно принадлежащие выделяемым областям, например, это могут быть точки с максимальным уровнем яркости;

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

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

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

Другим способом, близким к предыдущему, является алгоритм слияния областей [Baatz, М. Multiresolution Segmentation: an optimization approach for high quality multi-scale image segmentation [Text] / M.Baatz, A.Schäpe. - Journal of Photogrammetry and Remote Sensing. Volume 58. Issue 3-4. - Herbert Wichmann Verlag, 2004. - p.239-258]. В его основу заложена идея о том, что пикселы исходного изображения уже, по сути, являются гомогенными областями, но при этом обладают равно минимальными размерами. В этом случае метод сегментации должен выполнять объединение соседних областей, наиболее близких по какому-либо параметру (например, по цвету или текстуре), пользуясь функцией определения расстояния (гетерогенности, функцией стоимости слияния) до тех пор, пока не будет выполнено (либо нарушено) некоторое заданное условие (например, на размер сегментов или их количество). Для данного алгоритма целиком отпадает проблема определения центров кристаллизации, но особенно актуальной становится проблема определения момента завершения процесса слияний. В указанной реализации, как и во многих других, для этого используется ограничение на размер и количество сегментов, которое сильно снижает гибкость метода.

Наиболее близким к заявленному является способ сегментации [Pat. WO 2009143651 (A1), IPC⁷ G06T 5/00. Fast image segmentation using region merging with a k-nearest neighbor graph [Text] / Mantao X. [CN], Qiyong G. [CN], Hongzhi L. [CN], Jiwu Z. [CN]], принципиально состоящий из двух этапов: выращивания и последующего слияния сегментов. Выращивание областей в данном случае используется для выполнения начальной заведомо избыточной сегментации (initial oversegmentation), а слияние областей, основанное на методах теории графов, имеет своей целью достижение окончательного оптимального состояния сегментации. Определение центров кристаллизации в данном методе происходит в автоматическом режиме на основе градиентного изображения, полученного из исходного с помощью масочного оператора Кирша (Kirsch). Использование здесь градиентного изображения позволяет достаточно универсально решить проблему автоматического обнаружения центров кристаллизации, так как минимумам функции градиентного изображения будут соответствовать точки с максимально однородной окрестностью (потенциальные центры роста сегментов). Однако недостатком применения оператора Кирша в данной ситуации является его пространственная ограниченность (анализируется окрестность только 3×3 пикселов), тогда как при поиске центров кристаллизации было бы полезным исследовать окрестность точки на больших масштабах, чтобы учесть низкочастотные изменения функции яркости изображения и, таким образом, провести более точное последующее определение центров роста. Данного недостатка лишен подход [Минченков М.В. Алгоритм автоматической сегментации растровых изображений, основанный на росте кластеров от максимумов R-величины [Электронный ресурс] / М.В.Минченков. - Материалы конференции Graphicon 2004. - Режим доступа:

http://www.graphicon.ru/2004/Proceedings/Technical_ru/sl[2].pdf. - с.2], основанный на релеевском детекторе границ площадных объектов, который использует области анализа различных размеров.

При проведении выращивания и слияний областей часто используется информация о цвете области. Иногда также во время слияний используется текстурная информация [Pat. US2009080773 (Al), IPC⁷ G06K 9/34. Image segmentation using dynamic color gradient threshold, texture, and multimodal-merging [Text] / Shaw M. [US]; Bhaskar R. [US]; Ugarriza L. G. [US]; Saber E. [US]; AmusoV. [US]]. Однако использование текстурной информации при выращивании ограничивается тем, что для анализа текстуры (обычно это вычисление различных признаков, описанных в математической статистике), как правило, уже требуется иметь область размером более одного пиксела, что при выращивании (добавление единственного пиксела к области) невозможно. Наконец, общим недостатком всех указанных способов является жесткое правило для завершения процесса слияний, основанное на количестве сегментов на изображении либо их размерах. Такое условие резко снижает универсальность метода при заданной конфигурации.

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

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

Изобретение поясняется чертежами: фиг.1 - схема предложенного алгоритма сегментации, фиг.2 - один квадрант области расчета вейвлет-статистики, фиг.3 - полная область расчета вейвлет-статистики для трех уровней преобразования, фиг.4 - примеры автоматической сегментации изображений описанным методом.

Способ осуществляют следующим образом.

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

Сначала необходимо вычислить градиентное изображение для последующего определения по нему центров кристаллизации. Как уже упоминалось, применение масочных дифференциальных операторов с областью анализа 3×3 пикселов здесь должно уступить место методам расчета градиента на разных уровнях масштаба. Используем с этой целью идеи вейвлет-преобразования. Известно, что вейвлет-анализ изображения состоит в представлении оригинала в виде двух пирамид: приближений и деталей, отображающих локальные изменения изображения на разных масштабах. Отсюда следует, что, используя вейвлет-детали, можно выделить информацию о поведении функции изображения в окрестности исследуемой точки на разных масштабах (частотах), а не на единственном верхнем уровне, как в дифференциальных операторах. При этом должен быть применен способ фильтрации с плавающей маской, где для каждой точки изображения полностью рассчитываются вейвлет-детали ее окрестности.

Итак, с каждым пикселом можно связать некоторую окрестность на исходном изображении (фиг.2), по которой будут рассчитаны коэффициенты многомасштабного анализа. Тогда для выбранной точки изображения можно рассчитать несколько значений детализации (на фиг.2 - три), число которых определяется уровнем преобразования. Для более глубокого уровня анализа используется большая окрестность. Но, как видно из примера, эта окрестность покрывает лишь один квадрант в области пиксела. Остальные квадранты перекроем путем отражений шаблона преобразования (фиг.3) и получим количественную меру изменчивости функции изображения на определенном масштабе (назовем ее вейвлет-статистикой) как сумму где l - уровень анализа; - составляющие вейвлет-статистики, рассчитанные в четырех квадрантах окрестности базовой точки. Эти слагаемые отличаются направлением своего расчета на плоскости изображения. Для их определения введем вспомогательный вектор среднего значения l-го уровня на квадрате пикселов со стороной 2¹, рассчитываемый по рекуррентным формулам

где - оператор расчета средней точки в трехмерном RGB-пространстве на множестве

Теперь, используя данные формулы, можно описать расчет составляющих вейвлет-статистики для l-го масштаба как

где D - оператор вычисления евклидова расстояния в RGB-пространстве.

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

где Z - глубина расчета вейвлет-статистики; X, Y- общее количество строк и столбцов на исходном изображении. Получив данную функцию, следует перейти к определению центров кристаллизации путем поиска на ней локальных минимумов.

С целью снижения избыточности начальной сегментации и экономии вычислительных ресурсов введем в начале поиска центров кристаллизации квантование (огрубление) уровней многомасштабного градиентного изображения (функции UW^Z(х,у)). Число уровней должно задаваться пользователем. Однако данное введение не сильно снижает универсальность метода при фиксированной конфигурации, так как квантование в большинстве случаев позволяет отсеять неглубокие локальные минимумы градиента, обычно соответствующие шумам.

Поскольку исследуемая функция UW^Z(х,у) определена на двумерном дискретном пространстве, то использование классических методов оптимизации функций многих переменных здесь будет неэффективно. Здесь возможно применение метода подавления немаксимумов применительно к задаче минимизации. Его использование предполагает сканирование изображения с помощью маски 3×3 с целью определения точек, окруженных пикселами с наибольшими значениями. Но в такой постановке окажутся потерянными точки нестрогого локального минимума, а, исходя из требований, предъявляемых к задаче обнаружения центров кристаллизации, в области равно малых значений функции должна быть определена как минимальная одна точка, желательно лежащая в центре области равных значений. Для этого необходимо после нахождения точки нестрогого локального минимума выполнить морфологическую заливку связной с ней области того же уровня с целью определения и сохранения средней точки выделенной компоненты как центра кристаллизации. Математическое описание морфологических операций обычно дается с помощью теории множеств. Для выделения компоненты связности в морфологии используется операция дилатации , то есть расширение множества на его границах. Итак, если известная точка с находится внутри искомой области, то операция выделения компоненты связности C_k на множестве значений функции UW^Z(x,у) выглядит как C_k=(C _k-1 В) A; k=0,1, ; А={UW^Z(х,у)|(UW^Z(х,у)=с)}; С ₀=с; где В - примитив дилатации, здесь это квадрат 3×3.

Выполнение заливки завершается, когда C_k =C_k-1. Элементы множества C_k представляют изображение связной области равных значений, для которого необходимо определить центр тяжести. Центр тяжести для области, где все значения равны, можно определить путем нахождения точки внутри ограничивающего область прямоугольника, в которой пересекаются горизонтальная и вертикальная линии так, что по обе стороны от каждой из них лежат равномощные подмножества исследуемой области C_k. Далее необходимо найти ближайшую, в смысле евклидова расстояния от центра тяжести, точку, принадлежащую C_k (так как область может иметь, например, форму кольца), и признать ее новым центром роста.

Определив центры кристаллизации, следует непосредственно перейти к выращиванию областей. Выращивание областей должно начинаться из выделенных центров кристаллизации, представляющих будущие области, и заканчиваться в момент полного заполнения сегментами всего изображения. Естественно, все пикселы-кандидаты, претендующие на включение в какой-либо сегмент, должны быть смежными со своими областями, то есть находиться на внешней их границе, которую удобно выделять с помощью методов морфологии. Внешняя граница Gr области Reg (Gr и Reg - множества пикселов) может быть определена как Gr=(Reg В)Reg.

Далее следует искать среди выделенных граничных пикселов единственный максимально близкий к смежной области по какому-либо признаку (цвету или текстуре). Близость граничного пиксела и исследуемой области будем определять двумя способами:

- расстоянием (цветовым) между значением цвета пиксела и средним значением области, , где

- расстоянием (текстурным) в Z-мерном пространстве вейвлет-статистики l=1,2, Z между вектором , принадлежащим граничному пикселу, и средним значением для соответствующей области; здесь расширим операции нахождения среднего и евклидова расстояния на случай Z-мерного пространства,

.

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

Так как начальная стадия сегментации (выращивание областей) на практике неминуемо приводит к избыточной сегментации, то необходимо провести последующее слияние областей на уже сегментированном изображении. Используем здесь тот же принцип действия, что и при выращивании, и будем искать на каждом шаге пару соседних областей, наиболее близких друг к другу. Кандидатами на объединение могут быть любые две соседние области, при этом расстояние ( или ) может определяться с помощью тех же выражений, что и при выращивании, с той лишь разницей, что вместо значения параметра для одного пиксела в обоих случаях используются средние значения для областей. Те две области, которые будут иметь минимальное расстояние d^k друг от друга на k-м шаге слияний, должны быть объединены, и так до тех пор, пока не останется единственная область, равная всему изображению. Но тогда встает вопрос о критерии окончания процесса, о шаге, на котором сегментированное изображение будет наилучшим образом соответствовать человеческому восприятию оригинала либо давать информацию, максимально облегчающую задачу дальнейшего распознавания образов. Выявление этого момента может быть осуществлено при анализе последовательности допущенных отклонений характеристик областей во время их объединения. Можно предположить, что в большинстве случаев эта функция будет монотонно возрастать, так как по мере объединения областей придется допускать все большие отклонения их параметров. В таком случае с помощью дифференцирования данной последовательности можно определить момент, после которого при слиянии очередной пары пришлось сделать допущение, сильно отличающееся от соседних, то есть необходимо найти глобальный максимум первой производной последовательности отклонений d ^k. Тогда шаг остановки слияний t найдем как

В завершении необходимо сделать возврат в слияниях сегментов к результатам шага t и завершить работу метода.