Результат интеллектуальной деятельности: Устройство сегментации изображений

Предлагаемое изобретение относится к устройствам цифровой обработки сигналов.

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

, (1)

причем

. (2)

Основная решаемая задача - выделение областей , соответствующих объектам .Подобная задача может возникнуть в 1) системах машинного зрения, 2) обработке медицинских изображений, 3) обработке аэрофотоснимков, 4) в задачах распознавания лиц, 5) в системах распознавания отпечатков пальцев и т.д.

Существует множество методов сегментации изображений основанных на методах кластеризации, методах анализа гистограмм, методах раздела графа и других.

Известно устройство и способ сегментации эталонного трехмерного изображения и система распознавания объектов (Three dimensional reference image segmenting method and device and object discrimination system) [Patent USA US5917940A]

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

Недостатками известного устройства являются:

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

Известен способ сегментация изображений на основе пороговой обработки (Грузман И.С., Киричук В.С., Косых В.П., Перетягин Г.И., Спектор А.А. Цифровая обработка изображений в информационных системах: Учебное пособие.- Новосибисрк: Изд-во НГТУ, 2002. - 352 c.) это один из простых способов сегментации изображения.  Метод ориентирован на обработку изображений, отдельные однородные участки которых различаются средней яркостью. Простейшим и вместе с тем часто применяемым видом сегментации является бинарная сегментация, когда имеется только два типа однородных участков. При этом преобразование каждой точки исходного изображения   в выходное   выполняется по правилу:

(3)

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

Недостатками известного метода являются:

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

Известен способ сегментации по водоразделам (Vincent L., Soille P., Watersheds in Digital Spaces: An Efficient algorithm Based on Immersion Simulations, IEEE Transactions of Pattern Analysis and Machine Intelligence, vol.13, no.6, June 1991, pp.583-598.). Пусть — множества точек координатной плоскости, соответствующие локальным минимумам поверхности ; обычно является градиентным изображением. Обозначим через множество точек бассейна, отвечающего локальному минимуму (точки любого бассейна образуют компоненту связности). Обозначения min и max будем использовать для указания наименьшего и наибольшего значений изображения . Наконец, запись означает множество точек , для которых , т. е.

(4)

С геометрической точки зрения, есть множество точек, в которых поверхность лежит ниже плоскости .

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

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

(5)

Другими словами, в тех точках (х, у), для которых одновременно выполняется и ; в остальных точках изображения . Геометрическая интерпретация выражения в правой части (5) понятна: с помощью операции пересечения на n-ом шаге подъема уровня воды мы выделяем ту часть двоичного изображения , которая относится к локальному минимуму .

Пусть теперь — объединение залитых водой частей всех бассейнов на шаге n:

(6)

Тогда C[max+1 ] есть объединение всех имеющихся бассейнов:

(7)

Можно показать, что при работе алгоритма никогда не происходит удаления элементов из множеств и ; таким образом, при увеличении п число элементов этих множеств либо возрастает, либо остается неизменным. Следовательно, является подмножеством . Согласно равенствам (5) и (6), также является подмножеством , а значит, также есть подмножество . Отсюда следует важный результат: каждая компонента связности множества содержится ровно в одной связной компоненте множества .

Алгоритм нахождения линий водораздела начинается с инициализации . После этого алгоритм выполняется рекуррентно, предполагая на n-ом шаге множество уже построенным. Для получения множества из множества применяется следующая процедура. Пусть — множество компонент связности множества . Тогда для каждой связной компоненты есть три возможности:

а) — пустое множество;

б) содержит единственную компоненту связности множества ;

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

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

Недостатками известного метода являются:

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

Наиболее близким к изобретению, принятое за прототип, является устройство по способу автоматической сегментации изображения для цветных документов (Automatic image segmentation for color documents [Patent USA US5341226A]

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

Недостатками известного устройства-прототипа являются:

- невозможность гибкой подстройки параметров поиска границы;

- вычислительная сложность;

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

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

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

На Фиг. 1 изображена блок схема устройства сегментации изображений.

Устройство сегментации изображений состоит из блока хранения входной реализации 1, вход которого является входом устройства, а выход подключен к первому входу блока хранения необработанных данных 2, первый выход которого подключен ко второму входу вычитателя 4, первый выход которого подключен к первому входу блока выбора пикселя 6, выход которого подключен ко второму входу блока выделения области на изображении 7, выход которого подключен ко входу блока расчета значений критерия сравнения 9, выход которого подключен ко входу блока сравнения и принятия решения 10, второй выход которого подключен ко входу блока фильтрации области 11, второй выход которого подключен к первому входу блока хранения выходной реализации 12, выход которого является информационным выходом устройства; второй выход блока хранения необработанных данных 2 подключен ко входу блока определения параметров изображения 3, второй выход которого подключен ко входу блока хранения порогового значения 8, выход которого подключен ко второму входу блока сравнения и принятия решения 10, первый выход которого подключен к первому входу блока выделения области на изображении 7; первый выход блока определения параметров изображения 3 подключен к входу блока хранения параметров изображения 5, выход которого подключен ко второму входу блока выбора пикселя 6; первый выход блока фильтрации области 11 подключен к первому входу вычитателя 4, второй выход которого подключен ко второму входу блока хранения необработанных данных 2; третий выход блока хранения необработанных данных 2 подключен ко второму входу блока хранения выходной реализации 12.

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

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

. (10)

Из выбранной точки происходит разрастание области разделенной на сектора . Каждый из секторов растет на n-ом шаге итерации следующим образом:

К сектору добавляются точки ;

К сектору добавляются точки ;

…

К сектору добавляются точки .

Далее рассчитывается значение , являющиеся критерием оценки границы объекта для всех точек сектора .

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

Поиск границы нестационарности будем осуществлять с использованием двухкритериальных целевых функций вида:

,

где: – получаемая оценка, – постоянный коэффициент.

Определение элементов ряда будем производить согласно условию:

, ,

где ,

(здесь и далее – биноминальные коэффициенты),

.

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

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

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

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

(11)

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

Устройство сегментации изображений работает следующим образом. Входные данные поступают на вход блока хранения входной реализации 1. В блоке хранения необработанных данных 2 хранятся данные, не разделенные на локальные области. В вычитателе 4 происходит вычитание из массива данных поступающих с первого выхода блока блока хранения необработанных данных 2 данных локальной области поступающей с первого выхода блока фильтрации области 11, затем данные с вычитателя 4 поступают на вход блока хранения необработанных данных 2 и перезаписывают хранящуюся там информацию. В блоке выбора пикселя 6 происходит выбор случайного пикселя из диапазона точек необработанного изображения, который вычисляется в блоке определения параметров изображения 3 и записывается в блок хранения параметров изображения 5. В блоке выделения области на изображении 7 происходит выделение области на изображении, для каждой области рассчитывается критерий сравнения в блоке расчета значений критерия сравнения 9. В блоке расчета значений критерия сравнения 9 происходит расчет относительного изменения значения критерия сравнения. В блоке сравнения и принятия решения 10 происходит сравнение критерия рассчитанного в блоке расчета значений критерия сравнения 9 и порогового значения, хранящегося в блоке хранения порогового значения 8, в случае, если рассчитанное значение не превышает пороговое значение, то происходит дальнейшее разрастание области в блоке выделения области на изображении 7, если же рассчитанное значение превышает пороговое значение, то выделенная область на изображении попадает на вход блока фильтрации области 11. В блоке хранения выходной реализации 12 хранятся все локальные области изображения. В том случае, если все значения блок хранения необработанных данных 2 равны нулю, что эквивалентно тому, что объединение локальных областей составляет входное изображение, то данные поступают на выход устройства, если нет то данные возвращаются в блок вычитателя 4 и значения пересчитывается.