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



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

 


Владельцы патента RU 2440609:

Государственное образовательное учреждение высшего профессионального образования "Рыбинская государственная авиационная технологическая академия имени П.А. Соловьева" (RU)

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

 

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

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

Метод выращивания областей в простейшей его реализации [Гонсалес Р.С. Цифровая обработка изображений [Текст] / Р.С.Гонсалес, Р.Э.Вудс. - М.: Техносфера, 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), IPC7 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), IPC7 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-го уровня на квадрате пикселов со стороной 21, рассчитываемый по рекуррентным формулам

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

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

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

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

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

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

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

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

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

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

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

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

.

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

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

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

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

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



 

Похожие патенты:

Изобретение относится к способам оптического распознавания символов и может быть использовано для обработки выходных данных из системы оптического распознавания изображений (OCR), где выходные данные включают изображения дважды отпечатанных символов.

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

Изобретение относится к области цифровой фотографии. .

Изобретение относится к устройству и способу для распознавания жестов в динамике из последовательности стереокадров. .

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

Изобретение относится к способу для разрешения противоречивых выходных данных из системы оптического распознавания символов (OCR)

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

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

Изобретение относится к устройству и способу обработки информации при передаче видеоизображений (видеосвязь или видеочат) по сети связи ADSL (Асимметричная цифровая абонентская линия). Техническим результатом является улучшение качества видеоизображений и сохранение реалистичных ощущений даже на полосе частот восходящей линии связи. Указанный технический результат достигается тем, что клиентское устройство 11А, являющееся передающей стороной, выделяет из полученного изображения только изображение, являющееся преобладающим элементом коммуникации, в качестве первичных данных 21А. Клиентское устройство 11В, являющееся принимающей стороной, принимает от потокового сервера 12А через сеть 13 графические данные текстурного изображения, являющегося альтернативой фону полученного изображения, в качестве вторичных данных 22А. Принятые первичные данные 21А и вторичные данные 22В синтезируются, и комбинированное изображение отображается на мониторе 34. 2 н. и 2 з.п. ф-лы, 12 ил.

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

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

Изобретение относится к способам цифровой обработки изображений. Техническим результатом является повышение помехоустойчивости сегментации, а также повышение степени автоматизации процесса анализа и классификации сегментов изображения. Для решения задач распознавания образов по результатам анализа растровых полутоновых изображений предложен способ, заключающийся в локальной обработке исходного изображения масочным оператором и вычислении градиента полученного изображения, градиент вычисляют у изображения G1, формируемого путем локальной обработки исходного изображения масочным оператором, определяющим «центры тяжести» гистограмм в «пустом» окне. 1 табл., 10 ил.

Изобретение относится к области распознавания и обработки данных. Техническим результатом является повышение скорости преобразования документов, содержащих математические формулы, за счет автоматического преобразования математических формул в элементы нефиксированного формата. В способе обнаружения формул определяют местонахождение формул в части документа фиксированного формата путем идентификации исходных элементов формулы. Исходный элемент формулы является текстовым элементом, который несет указание, что является частью формулы, например текстовые цепочки, записанные шрифтами, используемыми для отображения математических выражений и математических операторов, символы или ключевые слова, которые используются в математических формулах. Создают и расширяют границу вокруг исходного элемента формулы, чтобы задать область формулы. Чтобы устранить перекрытие с окружающим обычным текстом, область формулы делится на несколько областей формулы на основе вертикального положения и горизонтального интервала между элементами формулы. После вертикального упорядочения горизонтально перекрывающиеся области формулы объединяются для восстановления формулы в виде плавающего элемента. 3 н. и 17 з.п. ф-лы, 19 ил.
Наверх