СПОСОБ АВТОМАТИЧЕСКОЙ СЕГМЕНТАЦИИ ПОЛУТОНОВЫХ СЛОЖНОСТРУКТУРИРОВАННЫХ РАСТРОВЫХ ИЗОБРАЖЕНИЙ
METHOD FOR AUTOMATIC SEGMENTATION OF HALF-TONE COMPLEX-STRUCTURED RASTER IMAGES

Изобретение относится к способам цифровой обработки изображений. Для решения задач распознавания образов по результатам анализа растровых полутоновых изображений необходимо решить задачу разделения исходного изображения на части (сегменты), различающиеся по своему семантическому содержанию. От качества сегментации зависит эффективность дальнейшего анализа и классификации изображений.
Известен способ сегментации изображения, называемый наращиванием областей (см., например, Якушенков Ю.Г. Техническое зрение роботов. - М.: Машиностроение, 1990, - с. 49-51; Путятин Е.П., Аверин С.И. Обработка изображений в робототехнике. - М.: Машиностроение, 1990, с. 18-25). Суть его заключается в том, что элементы изображения с одинаковыми или близкими уровнями яркости группируют, объединяя в однородные области. Для этого на исходном изображении ищут элементарные области, где пиксели объединяются в группы, если они обладают одинаковым уровнем яркости и являются соседями в смысле четырехсвязности. Затем элементарные области, имеющие общие границы, сливаются воедино согласно различным эвристическим правилам. Недостатком этого способа является необходимость подбора яркостных порогов в интерактивном режиме.
7
При проведении выращивания и слияний областей часто используется текстурная информация [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]]. Однако использование текстурной информации при выращивании ограничивается тем, что для анализа текстуры (обычно это вычисление различных признаков, описанных в математической статистике), как правило, уже требуется иметь область размером более одного пикселя, что при выращивании (добавление единственного пикселя к области) невозможно.
Выделение контуров объектов на полутоновых растровых изображениях можно осуществлять совместно с выделением самих объектов. Для этого обычно используют пороговые методы сегментации на основе среднего значения яркости пикселей, например [патент РФ №2325044 «Градиентный способ выделения контуров объектов на матрице полутонового растрового изображения»], где предложен градиентный способ выделения контуров объектов на матрице полутонового растрового изображения, заключающийся в том, что для всех пикселей растрового изображения вычисляют норму или квадрат нормы градиента изменения их яркости, затем на новой черно-белой монохромной матрице черным цветом на белом фоне выделяют все элементы, у которых значение нормы или квадрата нормы градиента больше порогового значения, а в качестве контуров объектов на монохромной матрице принимают связные конфигурации элементов черного цвета, для выбранного способа вычисления градиента экспериментально определяют коэффициент, затем рассчитывают пороговое значение квадрата нормы градиента как произведение данного коэффициента на сумму квадратов средних величин модулей изменения яркости соседних пикселей по строкам и столбцам, у которых значения превышают общие средние уровни ненулевых изменений, соответственно, по строкам и столбцам, а среди связных конфигураций элементов черного цвета на монохромной матрице сразу отбрасывают конфигурации, у которых число входящих элементов менее 5-7 элементов, для оставшихся конфигураций вычисляют среднюю степень соседства - частное от деления суммы по всем элементам конфигурации соседних с ним элементов на сумму элементов в конфигурации, причем те конфигурации, у которых средняя степень соседства менее 3, отбрасывают, а оставшиеся принимают в качестве искомых контуров объектов.
К недостаткам данного способа можно отнести слишком большое число эмпирически настраиваемых параметров, что не позволяет получить решающие правила, пригодные для изображений одного и того же класса, полученных при различных условиях или при различных уровнях помех. При нечетких сегментах такие параметры подобрать практически невозможно.
Близким к заявленному способу является способ сегментации [патент РФ №2148858 «Способ автоматической сегментации полутонового изображения по форме яркостной гистограммы»], который заключается в определении унимодального или бимодального типа исходной яркостной гистограммы в «пустой» маске и порогового уровня яркости. Этот пороговый уровень позволяет разделить бимодальную гистограмму на два унимодальных фрагмента, а также обеспечить обратный переход от фрагментов гистограммы к сегментам изображения. Яркостную гистограмму в «пустых» масках аппроксимируют полиномами, после чего строят кривую динамики центра гистограмм и определяют яркостные интервалы заданных значений яркости. Затем вычисляют вес области разделения для каждого интервала, идентифицируют яркостной интервал для области разделения с максимальным весом. При превышении максимального веса области разделения над нормативным весом, принимают решение о бимодальном типе исходной яркостной гистограммы. В качестве порогового уровня яркости для обеспечения операции порогового среза исходного изображения принимают глобальный минимум аппроксимирующего полинома на яркостном интервале с максимальным весом области разделения.
Недостатки данного способа заключаются в том, что гистограмма в «пустой» маске, центр которой лежит на границе сегмента, не всегда получается бимодальной. В этом случае пиксель, лежащий на границе сегмента, не идентифицируется как граница сегмента, и, наоборот, гистограмма в «пустой» маске может быть не унимодальной или многомодальной на границе сегмента, что также ведет к потере пикселя, лежащего на границе сегмента.
7
Наиболее близким к предлагаемому является способ сегментации [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 пикселей), тогда как при поиске центров кристаллизации было бы полезным исследовать окрестность точки на больших масштабах, чтобы учесть низкочастотные изменения функции яркости изображения и, таким образом, провести более точное последующее определение центров роста.
Технической задачей предлагаемого способа является повышение точности выделения границ сегментов полутоновых изображений (большее соответствие выделяемых сегментов субъективному восприятию изображения человеком) и как следствие, повышение помехоустойчивости сегментации, а также повышение степени автоматизации процесса анализа и классификации сегментов изображения.
Поставленная задача достигается тем, что в способе сегментации, заключающемся в локальной обработке исходного изображения масочным оператором и вычислении градиента полученного изображения, градиент вычисляют у изображения G1, формируемого путем локальной обработки исходного изображения масочным оператором, определяющим «центры тяжести» гистограмм в «пустом» окне по формуле
<mrow><mi>g</mi><msub><mn>1</mn><mrow><mi>i</mi><mi>j</mi></mrow></msub><mo>=</mo><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>q</mi><mo>=</mo><mn>1</mn></mrow><mi>s</mi></munderover><mrow><msub><mi>h</mi><mrow><mi>i</mi><mi>j</mi></mrow></msub><mo stretchy="false">(</mo><mi>q</mi><mo stretchy="false">)</mo><mo>⋅</mo><mi>Δ</mi><mo>⋅</mo><mi>q</mi></mrow></mstyle></mrow>
,
<mrow><msub><mi>h</mi><mrow><mi>i</mi><mi>j</mi></mrow></msub><mo stretchy="false">(</mo><mi>q</mi><mo stretchy="false">)</mo></mrow>
где q - номер интервала разбиения диапазона яркостей пикселей в «пустом» окне, s - число интервалов разбиения диапазона яркостей пикселей в «пустом» окне,
- q-й отсчет гистограммы в «пустом» окне с координатами ij, ∆ - ширина интервала разбиения диапазона яркостей пикселей в «пустом» окне.
Сегменты изображения выделяют посредством пороговой обработки градиентного изображения.
На фиг.1 представлена структурная схема устройства, осуществляющего предлагаемый способ.
На фиг.2 представлена схема алгоритма, реализующего представленный способ.
На фиг.3 представлена схема алгоритма формирования изображения G1.
На фиг. 4 показано интерфейсное окно с исходным изображением F, на котором обозначено «пустое» окно с гистограммой яркостей пикселей фрагмента этого изображения, попавших в это окно.
На фиг.6 представлены гистограммы яркости пикселей в «пустом» окне, полученные при пересечении окном границы левого легкого в горизонтальном направлении.
На фиг. 6 представлены графики изменения «центра тяжести» гистограммы в «пустом» окне при его продвижении в горизонтальном направлении и пересечении границ сегментов «норма» - «патология» - «средостение».
На фиг. 7 представлены примеры сегментации изображения флюорограммы грудной клетки (а), реализованной посредством известного способа (б) и предлагаемого способа (в).
Способ осуществляется устройством, структурная схема которого показана на фиг. 1.
Устройство состоит из компьютера 1; блока памяти данных 2, состоящего из блока памяти 3, предназначенного для хранения файлов данных с полутоновыми изображениями (изображениями F) и подключенного к первому входу компьютера 1, и блока памяти 4, предназначенного для хранения файлов данных с сегментированными изображениями (бинарными изображениями G3) и подключенного к первому выходу компьютера 1; блока памяти 5, предназначенного для хранения программного обеспечения по сегментации полутоновых изображений, и подключенного ко второму входу и второму выходу компьютера 1; и видеомонитора 6, подключенного к третьему выходу компьютера 1.
Способ реализуется согласно схеме алгоритма, представленной на фиг.2. В блоке 7 осуществляется ввод в компьютер пикселей исходного растрового полутонового изображения F, размер которого по вертикали N1, а по горизонтали N2. В блоке 8 формируется «пустое» окно, размером М1хМ2. Блок 9 организует вычисление гистограмм фрагментов изображения, попадающих в «пустое» окно в процессе его продвижения по изображению F, и формирует из изображения F изображение G1, яркость пикселей которого определяется гистограммами фрагментов изображения F, попавших в «пустое» окно. Блок 10 организует вычисление градиента изображения G1 - формирует изображение G2. Окончательное выделение сегментов изображения осуществляется в блоке 11, в котором выполняется переход от полутонового изображения G2 к бинарному изображению G3. После анализа сегментированного изображения (блок 12) принимается решение о целесообразности изменения размеров окна (блок 13). Изменение размеров окна позволяет адаптировать процесс сегментации к выделяемым фрагментам изображения. Увеличение окна делает процесс сегментации менее чувствительным к изображениям малого размера (соизмеримым с размерами окна), но повышает помехоустойчивость сегментации.
На фиг.3 представлена схема алгоритма получения изображения (изображения G1). Блоки 14 и 15 осуществляют продвижение «пустого» окна по изображению F.
На фиг. 4 показано интерфейсное окно с исходным изображением F, на котором обозначено «пустое» окно, и гистограммой яркостей пикселей фрагмента этого изображения, попавших в это «пустое» окно.
ij
Во вложенном цикле (блок 15) осуществляется вычисление гистограммы H в «пустом» окне (блок 16), формирование яркости пикселя изображения G1, соответствующего ij-й координате «пустого» окна осуществляется в блоке 17 по формуле
<mrow><mi>g</mi><msub><mn>1</mn><mrow><mi>i</mi><mi>j</mi></mrow></msub><mo>=</mo><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>q</mi><mo>=</mo><mn>1</mn></mrow><mi>s</mi></munderover><mrow><msub><mi>h</mi><mrow><mi>i</mi><mi>j</mi></mrow></msub><mo stretchy="false">(</mo><mi>q</mi><mo stretchy="false">)</mo><mo>⋅</mo><mi>Δ</mi><mo>⋅</mo><mi>q</mi></mrow></mstyle></mrow>
, (1)
<mrow><msub><mi>h</mi><mrow><mi>i</mi><mi>j</mi></mrow></msub><mo stretchy="false">(</mo><mi>q</mi><mo stretchy="false">)</mo></mrow>
где q - номер интервала разбиения диапазона яркостей пикселей исходного изображения в «пустом» окне, s - число интервалов разбиения диапазона яркостей пикселей в «пустом» окне,
- q-й отсчет гистограммы в «пустом» окне с координатами ij, ∆ - ширина интервала разбиения диапазона яркостей пикселей в «пустом» окне.
Определение количества интервалов s на гистограмме осуществляем по формуле Стерджесса [Hyndman, R.J. (1995). The problem with Sturges' rule for constructing histograms Business, Issue: July, 1-2.]
<mrow><mi>s</mi><mo>=</mo><mn>1</mn><mo>+</mo><mn>3,322</mn><mi>lg</mi><mo stretchy="false">(</mo><mi>M</mi><mn>1</mn><mo>⋅</mo><mi>M</mi><mn>2</mn><mo stretchy="false">)</mo></mrow>
, (2)
<mrow><mi>M</mi><mn>1</mn><mo>⋅</mo><mi>M</mi><mn>1</mn></mrow>
где
- общее количество пикселей в «пустом» окне.
При этом ширина интервала гистограммы ∆ определяется согласно формуле
<mrow><mi>Δ</mi><mo>=</mo><mfrac><mrow><msub><mi>d</mi><mrow><mi>max</mi></mrow></msub><mo>−</mo><msub><mi>d</mi><mrow><mi>min</mi></mrow></msub></mrow><mi>s</mi></mfrac></mrow>
, (3)
max
min
где d - максимальная яркость пикселя в окне, d - минимальная яркость пикселя в окне.
Рекомендуемые числа интервалов гистограммы, которые получаются при использовании формулы Стерджесса, представлены в таблице 1.
Таблица 1 Рекомендуемые числа интервалов на гистограмме в зависимости от числа пикселей в «пустом» окне
Количество пикселей в окне
Число интервалов
23 - 45
6
46 - 90
7
91 - 180
8
181 - 361
9
362 - 723
10
724 - 1447
11
1448 - 2885
12
В настоящее время формула (2) подвергается критике за то, что она явным образом использует биномиальное распределение для аппроксимации нормального распределения, что не всегда корректно. Считается, что эта формула позволяет строить удовлетворительные гистограммы при объеме выборки менее 200.
Существует целый ряд альтернативных формул, некоторые из которых вычисляют длину интервала, после чего определяется число требуемых классов, например формула Скотта (Scott, 1979)
<mrow><mi>Δ</mi><mo>=</mo><mfrac><mrow><mn>3,5</mn><mi>σ</mi></mrow><mrow><mroot><mrow><mo stretchy="false">(</mo><mi>M</mi><mn>1</mn><mo>⋅</mo><mi>M</mi><mn>2</mn><mo stretchy="false">)</mo></mrow><mn>3</mn></mroot></mrow></mfrac></mrow>
, (3)
где ∆ - длина интервала гистограммы, σ - стандартное отклонение значений яркостей пикселей в окне,
или формула Фридмана Диакониса (Freedman and Diaconis, 1981)
<mrow><mi>Δ</mi><mo>=</mo><mfrac><mrow><mn>2</mn><mo stretchy="false">(</mo><mi>I</mi><mi>Q</mi><mo stretchy="false">)</mo></mrow><mrow><mroot><mrow><mo stretchy="false">(</mo><mi>M</mi><mn>1</mn><mo>⋅</mo><mi>M</mi><mn>2</mn><mo stretchy="false">)</mo></mrow><mn>3</mn></mroot></mrow></mfrac></mrow>
, (4)
где ∆ - длина интервала, (IQ) - разница между верхним и нижним квартилем в окне.
Формулы (3) и (4) более обоснованы статистической теорией и считаются предпочтительнее формулы Стерджесса. Поэтому в блоке 16 предусмотрена возможность определения числа интервалов в гистограмме различными способами.
На фиг. 5 приведены девять гистограмм в «пустом» окне, полученных при пересечении «пустым» окном границы сегмента (контур левого легкого на изображении флюорограммы грудной клетки фиг. 7а), по которому можно наблюдать эволюцию «центров тяжести» в «пустом» окне при пересечении границы сегмента.
Графики на фиг. 6 иллюстрируют изменение величины «центра тяжести» гистограмм в окне (ряд 1) и градиента «центра тяжести» гистограмм (ряд 2) при пересечении окна изображения флюорограммы грудной клетки в горизонтальном направлении. Графики на фиг. 6а и фиг. 6б получены при различных размерах «пустого» окна. На фиг. 6а размер окна в два раза больше, чем на фиг. 6б. Эти графики иллюстрируют тот факт, что уменьшение размера «пустого» окна ведет к более четкому выделению границ малых сегментов и не оказывает влияние на четкость выделения больших сегментов, а также показывают, что снижение размерности окна приводит к увеличению зашумленности контуров границ выделяемых сегментов.
Анализ экспериментальных результатов по обработке тестовых сложнотекстурированных изображений посредством предложенного способа сегментации показал его преимущества относительно известных методов сегментации. На фиг. 7б показан результат сегментации тестового сложнотекстурированного изображения, представленного на фиг. 7а, в качестве которого выбрана флюорограмма грудной клетки у больного пневмонией, известным способом. Сегмент изображения флюорограммы, определяющий этот диагноз, обведен на тестовом изображении окружностью. В качестве известного способа сегментации использовался контурный детектор Кенни, построенный также на градиентной обработке предварительно фильтрованного изображения. Его алгоритм реализован в виде процедуры в пакете Matlab [Гонсалес, Р. Цифровая обработка изображений в среде Matlab /Р. Гонсалес, Р. Вудс, С. Эддинс. М.: Техносфера, 2006. 616 с.].
Экспертный анализ представленных на фиг. 7 изображений показывает более высокую помехозащищенность предлагаемого способа по сравнению с аналогом.