Эволюционный поиск эффективных последовательностей фильтров в задаче бинаризации УЗ изображений

Рассматривается задача построения последовательностей фильтров, позволяющих бинаризировать УЗ изображения сонных артерий с целью выделения просвета артерии. В работе предлагается алгоритм генетического программирования (ГП), осуществляющий поиск последовательностей фильтров, эффективно бинаризирующи...

Повний опис

Збережено в:

Бібліографічні деталі
Дата:	2011
Автори:	Беликова, Т.А., Скобцов, В.Ю.
Формат:	Стаття
Мова:	Russian
Опубліковано:	Інститут прикладної математики і механіки НАН України 2011
Назва видання:	Труды Института прикладной математики и механики
Онлайн доступ:	http://dspace.nbuv.gov.ua/handle/123456789/124046
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:	Эволюционный поиск эффективных последовательностей фильтров в задаче бинаризации УЗ изображений / Т.А. Беликова, В.Ю. Скобцов // Труды Института прикладной математики и механики НАН Украины. — Донецьк: ІПММ НАН України, 2011. — Т. 23. — С. 23-36. — Бібліогр.: 21 назв. — рос.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-124046
record_format	dspace
spelling	irk-123456789-1240462017-09-20T03:02:47Z Эволюционный поиск эффективных последовательностей фильтров в задаче бинаризации УЗ изображений Беликова, Т.А. Скобцов, В.Ю. Рассматривается задача построения последовательностей фильтров, позволяющих бинаризировать УЗ изображения сонных артерий с целью выделения просвета артерии. В работе предлагается алгоритм генетического программирования (ГП), осуществляющий поиск последовательностей фильтров, эффективно бинаризирующих УЗИ сонных артерий. Предложенный ГП-алгоритм программно реализован и проведен ряд вычислительных экспериментов на реальных УЗИ сонных артерий, подтверждающих его эффективность. Розглянуто задачу побудови послiдовностей фiльтрiв для бiнаризацi УЗ зображень артерiй з метою видiлення просвiту артерi . У роботi пропонується алгоритм генетичного програмування (ГП), який здiйснює пошук послiдовностей фiльтрiв, ефективно бiнаризуючих УЗ зображення сонних артерiй. Запропонований ГП-алгоритм програмно реалiзований i проведено низку обчислювальних експериментiв на реальних УЗД сонних артерiй, що пiдтверджують його ефективнiсть. The problem of constructing a sequence of filters which binarize ultrasound image of arteries is considered in order to separate an arterial lumen. This paper proposes a genetic programming algorithm that searches for sequences of filters wich effectively binarize ultrasound carotid atheroma. A number of computational experiments was performed on real ultrasound of carotid arteries. They confirm it effectiveness. 2011 Article Эволюционный поиск эффективных последовательностей фильтров в задаче бинаризации УЗ изображений / Т.А. Беликова, В.Ю. Скобцов // Труды Института прикладной математики и механики НАН Украины. — Донецьк: ІПММ НАН України, 2011. — Т. 23. — С. 23-36. — Бібліогр.: 21 назв. — рос. 1683-4720 http://dspace.nbuv.gov.ua/handle/123456789/124046 004.048+004.932 ru Труды Института прикладной математики и механики Інститут прикладної математики і механіки НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Russian
description	Рассматривается задача построения последовательностей фильтров, позволяющих бинаризировать УЗ изображения сонных артерий с целью выделения просвета артерии. В работе предлагается алгоритм генетического программирования (ГП), осуществляющий поиск последовательностей фильтров, эффективно бинаризирующих УЗИ сонных артерий. Предложенный ГП-алгоритм программно реализован и проведен ряд вычислительных экспериментов на реальных УЗИ сонных артерий, подтверждающих его эффективность.
format	Article
author	Беликова, Т.А. Скобцов, В.Ю.
spellingShingle	Беликова, Т.А. Скобцов, В.Ю. Эволюционный поиск эффективных последовательностей фильтров в задаче бинаризации УЗ изображений Труды Института прикладной математики и механики
author_facet	Беликова, Т.А. Скобцов, В.Ю.
author_sort	Беликова, Т.А.
title	Эволюционный поиск эффективных последовательностей фильтров в задаче бинаризации УЗ изображений
title_short	Эволюционный поиск эффективных последовательностей фильтров в задаче бинаризации УЗ изображений
title_full	Эволюционный поиск эффективных последовательностей фильтров в задаче бинаризации УЗ изображений
title_fullStr	Эволюционный поиск эффективных последовательностей фильтров в задаче бинаризации УЗ изображений
title_full_unstemmed	Эволюционный поиск эффективных последовательностей фильтров в задаче бинаризации УЗ изображений
title_sort	эволюционный поиск эффективных последовательностей фильтров в задаче бинаризации уз изображений
publisher	Інститут прикладної математики і механіки НАН України
publishDate	2011
url	http://dspace.nbuv.gov.ua/handle/123456789/124046
citation_txt	Эволюционный поиск эффективных последовательностей фильтров в задаче бинаризации УЗ изображений / Т.А. Беликова, В.Ю. Скобцов // Труды Института прикладной математики и механики НАН Украины. — Донецьк: ІПММ НАН України, 2011. — Т. 23. — С. 23-36. — Бібліогр.: 21 назв. — рос.
series	Труды Института прикладной математики и механики
work_keys_str_mv	AT belikovata évolûcionnyjpoiskéffektivnyhposledovatelʹnostejfilʹtrovvzadačebinarizaciiuzizobraženij AT skobcovvû évolûcionnyjpoiskéffektivnyhposledovatelʹnostejfilʹtrovvzadačebinarizaciiuzizobraženij
first_indexed	2025-07-09T00:45:47Z
last_indexed	2025-07-09T00:45:47Z
_version_	1837128167975813120
fulltext	ISSN 1683-4720 Труды ИПММ НАН Украины. 2011. Том 23 УДК 004.048+004.932 c©2011. Т.А. Беликова, В.Ю. Скобцов ЭВОЛЮЦИОННЫЙ ПОИСК ЭФФЕКТИВНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ ФИЛЬТРОВ В ЗАДАЧЕ БИНАРИЗАЦИИ УЗ ИЗОБРАЖЕНИЙ Рассматривается задача построения последовательностей фильтров, позволяющих бинаризировать УЗ изображения сонных артерий с целью выделения просвета артерии. В работе предлагается алго- ритм генетического программирования (ГП), осуществляющий поиск последовательностей филь- тров, эффективно бинаризирующих УЗИ сонных артерий. Предложенный ГП-алгоритм программ- но реализован и проведен ряд вычислительных экспериментов на реальных УЗИ сонных артерий, подтверждающих его эффективность. Ключевые слова: обработка изображений, УЗИ, фильтрация, эволюционные алгоритмы. 1. Введение. Лечение нарушений мозгового кровообращения является одной из наиболее актуальных медицинских проблем. Это обусловлено большой распростра- ненностью цереброваскулярных заболеваний, ведущее место среди которых зани- мает ишемический инсульт, обусловленный атеросклерозом и другими сосудистыми патологиями. Ежегодно в мире регистрируется около 6 млн. случаев инсульта, в странах Западной Европы – 1 млн., США – от 400 до 500 тыс., в Украине – око- ло 130-175 тыс. Cмертность от инсульта составляет 12-15% общего показателя, то есть, занимает 2-3 место после заболеваний сердца и злокачественных новообразо- ваний разной локализации. Уровень смертности от инсульта в Украине в 2,5 раза превышает соответствующие показатели западноевропейских стран [1]. Одной из основных причин ишемического инсульта является образование в сонных артери- ях атеросклеротических бляшек, их дальнейшее разрушение и отрыв, что ведет к тромбозу сосудов головного мозга. Это делает актуальным проблему диагностики и определения опасности разрушения и отрыва атеросклеротических бляшек или эмбологенной опасности, являющихся причиной 82% инсультов в Украине. Несмотря на быстрое развитие технологии УЗИ, анализ атеросклеротического поражения артерий на основании УЗ изображений остаётся субъективным процес- сом, эффективность которого во многом зависит от эксперта [2]. Попытки приме- нения компьютерной обработки результатов УЗИ, с целью определения структуры и степени эмбологенной опасности атеросклеротических бляшек, предпринимаются уже 15 лет [3], однако применяемые в них методы не дают необходимых устойчивых результатов и часто подвергаются критике. Это является следствием сложности по- ставленной задачи, и таких её подзадач как поиск объекта интереса на изображении. До настоящего момента не были найдены универсальные способы выделения и анализа интересующего фрагмента изображения, хотя разработано множество ал- горитмов сегментации растровых изображений, позволяющих с определённой сте- пенью качества решить задачу выделения объектов на изображении. Каждый из 23 Т.А. Беликова, В.Ю. Скобцов этих алгоритмов качественно решает задачу только для определённого класса изоб- ражений, поэтому автоматизированный анализ нового класса изображений диктует необходимость разработки новых или модернизации существующих алгоритмов сег- ментации. Условно такие алгоритмы можно разделить на три класса: бинаризирую- щие изображение с помощью фильтров, векторизирующие изображение и комбини- рованные. Среди второго класса можно выделить волновой метод, метод активных контуров [4], основанный на пространственном анализе и его различные модифи- кации [5], и др. Зависимость эффективности использования подобных алгоритмов векторизации (скорость и корректность) от характеристик исходного изображения влечёт за собой необходимость его предварительной фильтрации. Фильтрацию так- же зачастую используют как самостоятельный способ идентификации объектов на изображении. Построение "вручную" эффективных последовательностей фильтров, для по- лучения ожидаемого эффекта фильтрации, является нетривиальной и творческой задачей, требующей знания предметной области. Одним из способов автоматизации нахождения таких последовательностей является применение эволюционных вы- числений [6-8]. Синтез эффективных цепочек фильтров, выбираемых из заданного множества, эквивалентен нахождению "хороших" точек в пространстве комбинаций фильтров, где каждая точка – цепочка фильтров некоторой длины. Пространство комбинаций фильтров очень велико с точки зрения поиска (например, для цепочки из 20 фильтров, с возможным использованием 30 их разновидностей, существует 3020 вариантов составления) и сложно формализуемо, что делает актуальным при- менение эволюционного поиска для решения данной задачи [7, 8]. Существует ряд работ, посвящённых поиску подобных эволюционных алгоритмов. 2. Анализ существующих исследований. Эволюционные алгоритмы в це- лом, и алгоритмы генетического программирования (ГП) в частности, уже длитель- ное время применяются для обработки изображений, распознавания и идентифика- ции объектов [6]. Так в работе [9] предложен алгоритм ГП для получения эффектив- ных пороговых детекторов при идентификации сигналов, который также применим в задачах обработки изображений и машинного зрения. В работе [10] ГП использу- ется для разработки эффективных фильтров для усиления и выделения признаков или построения алгоритмов сегментации, основанных на классификации пикселей. Предложенные в [11] результаты показывают, что ГП является одним из способов синтеза сложных операторов, позволяющих распознавать объекты. В работе [12] для генерации правил классификации шума/цели и идентификации объектов также ис- пользуется алгоритм ГП, выделяющий зависимые признаки из множества заданных совокупностей признаков изображений. В [13, 14] ГП используется для получения автоматических распознавателей объектов. Попытки фильтрации УЗ изображений с целью снижения шумов и сегмента- ции предпринимаются уже давно и результаты некоторых таких работ позволяют получить дополнительные сведения и выводить взаимосвязи некоторых статисти- ческих параметров УЗ изображений и диагноза пациента, а также устанавливать наиболее оптимальные настройки УЗ оборудования. Так в [15] проводится сравне- 24 Эволюционный поиск последовательностей фильтров в задаче бинаризации УЗИ ние различных фильтров, позволяющих улучшить УЗ изображение путём снижения уровня шума. Результаты обработки изображения такими фильтрами, как медиан- ный, морфологические, основанные на преобразовании Фурье, оценивались двумя экспертами, а также на основании математических статистик. В статье [16] опи- сывается возможность грубой сегментации изображения на основании применения пороговых и сглаживающих фильтров. Используются модификации основанного на Гауссовом фильтре метода активных контуров, винеровское оценивание, статисти- ческие фильтры. В работе [17] производится сегментация на УЗ изображении слоёв тканей артерии с целью измерения их толщины. Эксперименты проводились на 100 УЗ продольных изображениях коронарной артерии, результаты компьютерных расчётов сравнива- лись с измерениями двух экспертов, и не было выявлено никаких значительных различий в компьютерной и экспертной оценке. Тестирование метода проводилось следующим образом. На каждом из изображений вручную выбиралась область, со- держащая стенку артерии. Выделенная область подвергалась фильтрации с целью устранения шумов при помощи фильтров, описанных в [15], затем бинаризирова- лась, проводилась дилатация бинаризированного изображения по множеству 3х3, устранялись границы в нижней части выделенной области и строился контур с по- мощью В-сплайнов. В итоге были получены выделенные границы тканей. Также в [17] приведены статистические расчёты отклонений в компьютерной и экспертной оценке толщин тканей на различных УЗ изображениях артерии. Однако не было приведено результатов работы предложенного метода для менее "хороших" случаев УЗИ артерий, на которых нет такого чёткого различия в яркости слоёв артерии. Учитывая то, что получение УЗ изображений такого качества достаточно редкое явление, применимость предложенного метода в медицинской практике затрудни- тельна. Таким образом, в данной работе предлагается ГП-алгоритм, генерирующий по- следовательности фильтров бинаризации УЗИ. В отличие от алгоритмов, описанных в [9-14], в предложенном ГП-алгоритме, вход и выход каждого узла цепочки филь- тров является изображением, а не числом. Также в работе используется большее число возможных значений узлов. В отличие от работы [17] мы постарались апро- бировать предложенный алгоритм на реальных УЗИ разного качества, в том числе и не очень "хорошего". 3. Пространственные методы обработки изображений. Термин простран- ственная область относится к множеству пикселей, составляющих изображение. Пространственные методы суть процедуры, оперирующие непосредственно значе- ниями этих пикселей. К ним относятся градационные преобразования и простран- ственная фильтрация [18]. В данной работе, помимо вышеупомянутых методов, ис- пользуется также морфологическая обработка изображений. 3.1. Линейная пространственная фильтрация. При пространственной фильтра- ции локальные преобразования оперируют одновременно как со значениями пиксе- лей в окрестности, так и с соответствующими им значениями некоторой матрицы, имеющей те же размеры, что и окрестность. Такую матрицу называют фильтром, 25 Т.А. Беликова, В.Ю. Скобцов маской, ядром или шаблоном. Значения элементов матрицы называют коэффици- ентами. При линейной фильтрации отклик задаётся суммой произведений коэффициен- тов шаблона на соответствующие значения пикселей в области, покрытой маской фильтра. Фильтрация изображения f , имеющего размеры M×N , с помощью филь- тра размерами m× n задаётся выражением общего вида (1) [18]: g(x, y) = a∑ s=−a b∑ t=−b w(s, t)f(x + s, y + t), (1) где a = (m− 1)/2, b = (n− 1)/2;w(s, t) – коэффициенты матрицы фильтра. При фильтрации всего изображения данная формула вычисляется для всех сочета- ний x = 0, 1, 2, . . . , M − 1 и y = 0, 1, 2, . . . , N − 1. В данной работе используются следующие линейные пространственные филь- тры: 1. Простейший усредняющий фильтр. Выход (отклик) простейшего линейного сглаживающего пространственного фильтра есть среднее элементов по окрест- ности, покрытой маской фильтра. Используются фильтры 3х3 и 5х5. 2. Фильтры, возвращающие взвешенное среднее по маске. Пиксели окрестности, покрываемой маской такого фильтра, оказывают неодинаковое влияние на от- клик фильтра   1 1 1 1 1 1 1 1 1 1 1 1 10 1 1 1 1 1 1 1 1 1 1 1 1     1 1 2 1 1 1 2 5 2 1 2 5 10 5 2 1 2 5 2 1 1 1 2 1 1     1 2 1 2 4 2 1 2 1   . 3. Фильтры, используемые для реализации простого и расширенного добавлени- ем диагональных элементов дискретного лапласиана   1 1 1 1 −8 1 1 1 1     0 1 0 1 −4 1 0 1 0     0 −1 0 −1 4 −1 0 −1 0   . 4. Составные фильтры, позволяющие получить сумму либо разность изображе- ния обработанного по маске лапласиана с исходным. Применение таких филь- тров (основанных на второй производной) позволяет подчеркнуть или умень- шить (в зависимости от знаков коэффициентов) разрывы уровней яркости на изображении, подавить области со слабым изменением яркости   −1 −1 −1 −1 9 −1 −1 −1 −1     1 1 1 1 −9 1 1 1 1     0 1 0 1 −3 1 0 1 0     0 −1 0 −1 5 −1 0 −1 0   . 26 Эволюционный поиск последовательностей фильтров в задаче бинаризации УЗИ 5. Фильтр, усиливающий высокие частоты, позволяющий в целом повысить яр- кость изображения  0 −1 0 −1 6 −1 0 −1 0     1 1 1 0 −4 0 1 1 1   . 6. Фильтры, основанные на "дискретных" значениях первых производных (опе- раторы Собела и Превитта), позволяющие выделять горизонтальные, верти- кальные и наклонные контура  −1 −2 −1 0 1 0 1 2 1     −1 0 1 −2 1 2 −1 0 1     −1 −1 −1 0 1 0 1 1 1     2 −1 −1 −1 3 −1 −1 −1 2     −1 −1 2 −1 3 −1 2 −1 −1   . 7. Фильтр Marr-Hildreth (лапласиан гауссиана) – составной оператор, менее чув- ствительный к шумам нежели вторая производная, за счёт сглаживающего эффекта функции Гаусса. (В данном случае сумма исходного изображения с отфильтрованным)   0 0 −1 0 0 0 −1 −2 −1 0 −1 −2 17 −2 −1 0 −1 −2 −1 0 0 0 −1 0 0   . Из нелинейных пространственных фильтров используются медианные фильтры (Median), заменяющие значение пикселя на значение медианы распределения яр- костей всех пикселей в окрестности (включая исходный). Такие фильтры хорошо очищают изображения от импульсных шумов. 3.2. Градационные методы обработки изображений. В данной работе использует- ся: линейное растяжение текущего диапазона яркостей пикселей на весь допустимый интервал яркости; пороговое преобразование (по порогу равному половине текуще- го диапазона яркости изображения); выравнивание (эквализация) гистограммы; а также приведение гистограммы к заданному виду. Гистограммой цифрового изображения с уровнями яркости в диапазоне [0, L−1] называется дискретная функция h(rk) = nk, где rk есть k-ый уровень яркости, а nk – число пикселей на изображении, имеющих яркость rk. Общей практикой является нормализация гистограммы путем деления каждого из ее значений на общее число пикселей в изображении, обозначаемое n. Тем самым, значения нормализованной гистограммы p(rk) = nk/n для k = 0, 1, ..., L−1. А p(rk) есть оценка вероятности по- явления пикселя со значением яркости rk. Заметим, что сумма всех значений норма- лизованной гистограммы равна единице. Дискретным аналогом интеграла функции распределения случайной величины будет sk = T (rk) = k∑ j=0 pr(rj) = k∑ j=0 nj n , k = 0, 1, 2, . . . , L− 1. (2) 27 Т.А. Беликова, В.Ю. Скобцов На основании значений функции (2), согласно алгоритму выравнивания гисто- граммы [18], происходит замена яркостей пикселей. Преобразование (отображение), задаваемое формулой (2), называется эквализацией, выравниванием или линеариза- цией гистограммы. Преобразование направлено на растяжение гистограммы вход- ного изображения и в случае необходимости автоматического улучшения. Это яв- ляется хорошим подходом, поскольку результаты этого метода предсказуемы и он прост в реализации. Кроме выравнивания, существует также метод называемый приведением гисто- граммы, он позволяет получить обработанное изображение с заданной формой ги- стограммы. В данной работе приведение гистограммы выполняется к форме, полу- ченной посредством аппроксимации эмпирических распределений яркостей пиксе- лей (рис. 1) различных легко бинаризируемых изображений. Рис. 1. Гистограмма изображения, хорошо поддающегося бинаризации Для обобщения формы гистограмм были выбраны кривые Джонсона по причине хорошей применимости для построения функций, аппроксимирующих гистограммы всех тестируемых изображений, и принадлежности одному классу. Проверка применимости таких кривых выполняется на основании оценок тре- тьего и четвёртого моментов, рассчитываемых по формулам (3): α3 = 1 ηs3 n∑ 1 (xi − x)3; α4 = 1 ηs4 n∑ 1 (xi − x)4; s2 = 1 n− 1 n∑ 1 (xi − x)2. (3) Если выполнено условие (4), то кривые Джонсона неприменимы α4 < 1 + α3. (4) При выполнении условия (5), считается, что распределение относится к классу Sb кривых Джонсона α4 < 3(1 + 0, 641α2 3). (5) Полученная кривая имеет вид, показанный на рис. 2a, и рассчитывается по формуле (6) f(x) = η√ 2π λ (x− ε)(λ− x + ε) exp { −1 2 [ γ + ηln ( x− ε λ− x + ε )]2 } , (6) где η и γ вычисляются по формулам (7) и (8), ε – нижняя граница диапазона изме- нения случайной величины, λ – ширина диапазона изменения случайной величины η = (u1−α − uα) ln (x1−α−ε)(ε+λ−xα) (xα−α)(ε+λ−x1−α) . (7) 28 Эволюционный поиск последовательностей фильтров в задаче бинаризации УЗИ a б Рис. 2. Фрагмент кривой Джонсона класса Sb (a – по распределению Рис. 1; б – для γ = 0) γ = u1−α − ηln ( x1−α − ε ε + λ− x1−α ) , (8) где uα – alpha-квантиль стандартного нормального распределения, xα-эмпирическая квантиль ([α(n + 1)]-й упорядоченный член выборки x1 ≤ x2 ≤ . . . ≤= xn) [18, 19]. 3.3. Морфологическая фильтрация. Большая часть морфологических алгорит- мов обработки изображений использует операции эрозии и дилатации. Операция дилатации определяется формулой (9): (f ⊕B)(x, y) = sup{f(s, t); (s, t) ∈ Ba}, (9) где a = (x, y) – вектор, задающий смещение множества B, а B – множество, по которому осуществляется операция дилатации. Дилатация по [21] сглаживает пики, поднимает общую яркость неоднородных частей изображения. Операция эрозии определяется формулой (10): (f ªB)(x, y) = inf{f(s, t); (s, t) ∈ Ba}, (10) где a = (x, y) – вектор, задающий смещение множества B, а B – множество, по которому осуществляется эрозия. Эрозия [21] сглаживает впадины, понижает общую яркость неоднородных ча- стей изображения. Графическое представление принципа работы операций эрозии и дилатации для функции одной переменной представлены на рис. 3. Последовательное применение приведенных выше морфологических фильтров называется операциями открытия и закрытия, и осуществляется по формулам (11) и (12), соответственно: (f ◦B)(x, y) = ((f ªB)(x, y)⊕B)(x, y), (11) (f •B)(x, y) = ((f ⊕B)ªB)(x, y). (12) Закрытие сглаживает мелкие "впадины" яркости и линии контура на изображении. Открытие убирает небольшие пики и сглаживает линии контура на изображении 29 Т.А. Беликова, В.Ю. Скобцов Рис. 3. Графическое представление принципа работы операции эрозии и дилатации в плоскости y=0 [21]. В данной работе применяются морфологические фильтры эрозии, дилатации, открытия и закрытия по множествам 3х3 и 5х5. 4. Эволюционный алгоритм поиска. Построение "вручную" последователь- ностей фильтров является нетривиальной и сложной задачей, требующей знания предметной области. Одним из способов автоматизации нахождения таких после- довательностей является применение эволюционных вычислений, в частности ГП [6-8]. В терминах генетического программирования, пространство поиска – это про- странство, из которого выбираются особи популяций, а "хорошие" точки – это особи со сравнительно большим фитнессом. Каждая особь представляет собой ацикличе- ский граф, узлами которого являются фильтры (рис. 4). Рис. 4. Графическое представление особи популяции Начальная популяция генерируется случайным образом, а все последующие по- средством применения операторов кроссинговера и мутации к особям популяции, сгенерированной на предыдущем шаге алгоритма. Селекция особей для скрещива- ния осуществляется на основании значения фитнесс-функции по принципу "колеса рулетки" [7, 8]. Формально алгоритм можно записать следующим образом: 1. случайным образом сгенерировать популяцию G размера N и рассчитать фит- несс функцию для каждой особи популяции, 2. сохранить лучшую особь популяции G, 3. выбрать 2 особи из G для оператора кроссинговера на основании значения фитнесс-функции, выполнить кроссинговер, 4. выбрать 2 особи с наименьшей фитнесс-функцией в G и заменить их получив- шимися на шаге 3 потомками, 30 Эволюционный поиск последовательностей фильтров в задаче бинаризации УЗИ 5. рассчитать значение фитнесс-функции полученных потомков и фитнесс их по- дузлов, сохранить "хорошие" фрагменты хромосом в библиотеку, 6. если заданный уровень кроссинговера не достигнут, перейти к шагу 3, 7. с заданной вероятностью осуществить мутацию над каждой особью текущей популяции, 8. заменить худшую особь в полученной популяции на лучшую особь исходной популяции, 9. перейти к шагу 2, если количество поколений меньше M , иначе выход. Фитнесс-функция каждой особи вычисляется на основании соответствия отфиль- трованных фрагментов желаемым результатам. В данном случае желаемым резуль- татом является высококонтрастное изображение, ярким пикселям которого соответ- ствуют области расположения эхогенных тканей (в т.ч. стенок артерий), а тёмным – кровь и ткани с низкой эхогенностью. Если обозначить множество ярких пикселей эталонного фрагмента Qi, а Q′ i – множество ярких пикселей отфильтрованного с помощью некоторой особи текущей популяции i-го фрагмента, n(Y ) – число пикселей в множестве Y , а m – число фильтруемых фрагментов, то значение фитнесс-функции этой особи вычисляется по формуле (13) Fitness = 1 m m∑ i=1 n(Qi ∩Q′ i) n(Qi ∪Q′ i) . (13) Множество фрагментов изображений (а не изображения целиком, с целью сокра- щения времени обработки) и ожидаемый результат фильтрации (в виде бинарного шаблона) задаются вручную. Для получения, в конечном итоге, наиболее эффек- тивных цепочек фильтров важна репрезентативность множества обрабатываемых фрагментов. Входом и выходом каждого узла графа является изображение. Предложенный алгоритм использует операторы одноточечного случайного и взве- шенного кроссинговера. Суть последнего в том, что родительские особи скрещива- ются в подузлах с наименьшим фитнессом. В зависимости от номера поколения ве- роятность взвешенного кроссинговера повышается. Применяется оператор мутации двух видов: случайная и взвешенная мутация. При мутации первого вида, мутиру- ющий узел заменяется случайно выбранным фильтром из множества допустимых. Вероятность взвешенной мутации узла зависит от его фитнесса. В зависимости от номера поколения вероятность взвешенной мутации, по сравнению со случайной, повышается. Предложенный выше ГП алгоритм, в отличие от разработанных в [9-14], не яв- ляется алгоритмом идентификации объекта на изображении, а используется для первичной его фильтрации, перед последующей векторизацией, с целью повышения эффективности алгоритмов векторизации. 31 Т.А. Беликова, В.Ю. Скобцов 5. Полученные результаты. Вышеописанный алгоритм был реализован в ви- де программного приложения, с помощью которого были получены эксперименталь- ные данные, приведенные в таблице 1 (КЗ – количество запусков, МП – мощность популяции, Ср.зн.ф.ф. – Среднее значение фитнесс-функции, ЧЭ – число эпох). Таблица 1 КЗ Число исп. фильтров Тип исп. филь- тров Вер-ть мутации Вер-ть крос- ра МП КЭ Ср.зн. ф.ф. 10 20 линейные 0,1 0,6 80 70 0,693568 10 30 линейные, морф., Median 0,1 0,6 80 70 0,728416 10 34* линейные, морф., Median, градационные 0,1 0,6 80 70 0,812882 20 34 линейные, морф., Median, градационные 0,1 0,6 80 70 0,835352 В первой строке таблицы приведены усреднённые результаты 10 запусков ал- горитма ГП, строящего последовательности из 20 возможных вариантов линейных пространственных фильтров. Значения фитнесс-функции лучшей особи в среднем было равно 0,693568. Но лучшее значение фитнесс-функции 0,714353 было достиг- нуто на особи, представленной в таблице 2. Таблица 2 1 1 1 1 -8 1 1 1 1 1 1 1 1 1 1 1 1 1 -1 -1 2 -1 3 -1 2 -1 -1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 -1 0 -1 5 -1 0 -1 0 Следует отметить, что качество фильтрации, и в частности бинаризации, зависит от гистограммы исходного изображения. В описанном данном случае поиск после- довательностей производился на изображениях с неблагоприятными для фильтра- ции формами гистограммы. Исходные изображения и их гистограммы, результаты фильтрации данных изображений и желаемый результат (шаблон сравнения), при- ведены на рис. 5. Во второй строке таблицы 1 приведены усреднённые результаты 10 запусков алгоритма ГП, строящего последовательности из 20 линейных пространственных фильтров, 2-х медианных фильтров различных размеров и морфологических филь- тров (эрозии, дилатации, открытия и закрытия), всего 30 вариантов значений хромо- сом особи. Значения фитнесс-функции лучшей особи в среднем было равно 0,7284157. Но лучшее значение фитнесс-функции 0,787312 было достигнуто на особи, представ- ленной в таблице 3. 32 Эволюционный поиск последовательностей фильтров в задаче бинаризации УЗИ Рис. 5. Результаты фильтрации, исходные изображения, шаблон сравнения, гистограммы Таблица 3 0 1 0 1 -3 1 0 1 0 Dilation (5x5) Dilation (3x3) Dilation (5x5) Dilation (5x5) Изображения, результаты фильтрации данных изображений и желаемый резуль- тат (шаблон сравнения), приведены на рис. 6. Исходные изображения для тестиро- вания были взяты для всей таблицы 1 одинаковыми с целью сравнить результаты работы алгоритма в зависимости от набора возможных узлов последовательности фильтрации. Рис. 6. Результаты фильтрации, исходные изображения, шаблон сравнения В третьей строке таблицы 1 приведены усреднённые результаты 10 запусков алгоритма ГП, строящего последовательности из 20 линейных пространственных фильтров, 2-х медианных фильтров различных размеров и морфологических филь- тров (эрозии, дилатации, открытия и закрытия), а также 4-х градационных преобра- зований (линейное растяжение диапазона яркостей, пороговый фильтр, выравнива- ние гистограммы и приведение гистограммы), всего 34 варианта значений хромосом особи. Значения фитнесс-функции лучшей особи в среднем было равно 0,812881778. Но лучшее значение фитнесс-функции 0,842733 было достигнуто на особи, представ- ленной в таблице 4. 33 Т.А. Беликова, В.Ю. Скобцов Таблица 4 -1 -1 2 -1 3 -1 2 -1 -1 Dilation (5x5) Dilation (3x3) Dilation (5x5) Equalization Erosion (3x3) Изображения, результаты фильтрации данных изображений и желаемый резуль- тат (шаблон сравнения), приведены на рис. 7. Рис. 7. Результаты фильтрации, исходные изображения, шаблон сравнения Количество фильтров в третьей строке таблицы 1 отмечено звездочкой, потому что градационное преобразование – приведение гистограммы, в данном случае про- изводилось к виду, показанному на рисунке 2б, и по итогам тестирования не дало результатов, т.к. не вошло в состав хромосомы лучшей особи. Функция распределения рис. 2б была выбрана на основании визуальной оцен- ки внешнего вида гистограмм и построена с помощью кривых Джонсона класса Sb (γ = 0). В методе приведения гистограммы, использованном в тестах, результаты которых отображены в четвёртой строке таблицы 1, использовалась функция, коэф- фициенты которой были посчитаны программно на основании гистограмм изобра- жений, хорошо поддающихся фильтрации. График этой функции был приведен на рисунке 2а. Среднее значение фитнесс-функции, полученное на 20 тестовых запус- ках программы при использовании 34 возможных вариантов фильтров – 0,8353516. При этом фитнесс лучшей особи приведенной в таблице 5 был равен 0,868683. Таблица 5 Dilation (5x5) -1 -1 2 -1 3 -1 2 -1 -1 Median (3x3) Hitigram Matching Median (5x5) Dilation (5x5) Результаты обработки тестовых изображений таким фильтром представлены на рис. 8. 6. Выводы. По результатам бинаризации видно, что сами по себе линейные про- странственные фильтры не могут обеспечить приемлемый вид бинаризированного изображения. Добавление возможностей морфологической фильтрации значительно улучшает ситуацию, однако очерчивает линии контура грубо. Градационные преоб- разования позволяют добиться плавных контуров бинаризированных изображений, 34 Эволюционный поиск последовательностей фильтров в задаче бинаризации УЗИ Рис. 8. Результаты фильтрации, исходные изображения, шаблон сравнения однако не могут предоставить достаточно точное соответствие заданному шаблону. В дальнейшем для улучшения результатов планируется добавить градационные фильтры, основанные на локальных статистиках, адаптивные пороговые фильтры, а также усовершенствовать ГП алгоритм, снизив вероятность его схождения к ло- кальным экстремумам. 1. Кобза I. Патологiя сонних артерiй: поciбник-атлас. – Львiв: Манускрипт – Львiв, 2008. – 106 с. 2. Sayed Aly, Christopher C. Bishop An Alternative Method to Identify Unstable Plaque // Stroke, № 31. – PP. 1921-1924. – 2000. 3. Suri S.J., Molinari F. Atherosclerosis disease management. – Springer, 2011. 4. Kaas M., Witkin A., Terzopoulos D. Snakes: Active Contour Models // Int. Journal of Computer Vision. – 1987. – № 1. – P. 312-331. 5. Петров В.О., Привалов О.О. Модификация алгоритма активных контуров для решения зада- чи интерактивной сегментации растровых изображений дефектов металлических отливок // Физико-математические науки. – № 6. – 2008. – C. 14-16. 6. Lin Y. Feature synthesis and analysis by evolutionary computation for object detection and recog- nition. – University of California, Riverside, 2003. 7. Mitchell M. Introduction to genetic algorithms. – MIT Press, 1999. 8. Скобцов Ю.А. Основы эволюционных вычислений. – Донецк: ДонНТУ, 2008. 9. Harris C., Buxton B. Evolving edge detectors with genetic programming // Genetic Programming, Proceedings of the 1st Annual Conference, Stanford University, PP. 309–314. The MIT Press, Cambridge, 1996. 10. Poli R. Genetic programming for feature detection and image segmentation // Evolutionary Compu- tation, T.C.Forgarty Ed., PP. 110-125. – 1996. 11. Bhanu B., Lin Y. Learning composite operators for object detection // Proc. Genetic and Evolutio- nary Computation Conference, PP. 1003-1010. – July, 2002. 12. Stanhope S.A., Daida J.M. Genetic programming for automatic target classification and recognition in synthetic aperture radar imagery// Evolutionary Programming VII: Proceedings of the Seventh Annual Conference on Evolutionary Programming, Berlin: Springer-Verlag, pp. 735–744. – 1998. 13. Roberts S.C., Howard D. Evolution of vehicle detectors for infrared line scan imagery. – Berlin, Germany: Springer-Verlag, PP. 110-125. – 1999. 14. Bhanu B. et al. Guest Editorial Introduction To The Special Issue On Automatic Target Detection And Recognition // IEEE Transactions On Image Processing. – Vol. 6, № 1. – Jan 1997. 15. Loizou С.P., Pattichis C.S. Comparative Evaluation of Despeckle Filtering In Ultrasound Imaging of the Carotid Artery // Transactions on ultrasonics, ferroelectrics, and frequency control, vol. 52, N 10. – 2005. 16. Lin N., Yu W., Duncan J.S. Combinative Multi-Scale Level Set Framework for Echocardiographic Image Segmentation // Medical Image Analysis, Volume 7, Issue 4, December 2003. – P. 529-537. 35 Т.А. Беликова, В.Ю. Скобцов 17. Loizou C. P., Pattichis C. S., Pantziaris M., Nicolaides A. Snakes based segmentation of the common carotid artery intima media, Med Bio Eng Comput. – № 45. – PP. 35-49. – 2007. 18. Гонсалес, Вудс Р. Цифровая обработка изображений. – Москва:Техносфера, 2005. – 1072 с. 19. Кобзарь А. Прикладная математическая статистика. – Москва:Физматлит, 2006. – 816 с. 20. Хан Г., Шапиро С. Статистические модели в инженерных задачах. – Москва: Мир, 1969. – 395 с. 21. Serra J. Image analysis and mathematical morphology. – Academic Press, London, 1982. T. Belikova, V. Skobtsov Evolutionary search of effective filters sequences in the ultrasound images binarization problem. The problem of constructing a sequence of filters which binarize ultrasound image of arteries is considered in order to separate an arterial lumen. This paper proposes a genetic programming algorithm that searches for sequences of filters wich effectively binarize ultrasound carotid atheroma. A number of computational experiments was performed on real ultrasound of carotid arteries. They confirm it effecti- veness. Keywords: image processing, ultrasound, filtration, evolutionary algorithms. Т.О. Бєлiкова, В.Ю. Скобцов Еволюцiйний пошук ефективних послiдовностей фiльтрiв у задачi бiнаризацiї УЗ зоб- ражень. Розглянуто задачу побудови послiдовностей фiльтрiв для бiнаризацiї УЗ зображень артерiй з ме- тою видiлення просвiту артерiї. У роботi пропонується алгоритм генетичного програмування (ГП), який здiйснює пошук послiдовностей фiльтрiв, ефективно бiнаризуючих УЗ зображення сонних артерiй. Запропонований ГП-алгоритм програмно реалiзований i проведено низку обчислюваль- них експериментiв на реальних УЗД сонних артерiй, що пiдтверджують його ефективнiсть. Ключовi слова: обробка зображень, УЗД, фiльтрацiя, еволюцiйнi алгоритми. Ин-т прикл. математики и механики НАН Украины, Донецк belikova.taisija@gmail.com skobtsov@iamm.ac.donetsk.ua Получено 11.12.11 36

Эволюционный поиск эффективных последовательностей фильтров в задаче бинаризации УЗ изображений

Репозитарії

Схожі ресурси