автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.17, диссертация на тему:Восстановление пространственной структуры древовидных объектов по нечетко наблюдаемым проекциям

на правах рукописи

КОРЕПАНОВ Андрей Олегович

ВОССТАНОВЛЕНИЕ ПРОСТРАНСТВЕННОЙ СТРУКТУРЫ ДРЕВОВИДНЫХ ОБЪЕКТОВ ПО НЕЧЕТКО НАБЛЮДАЕМЫМ ПРОЕКЦИЯМ

Специальности" 05.13.17 Теоретические основы информатики, 05 13.18 Математическое моделирование, численные методы и комплексы программ

Автореферат

диссертации на соискание ученой степени кандидата физико-математических наук

Самара2005

Работа выполнена в государственном образовательном учреждении высшего профессионального образования «САМАРСКИЙ ГОСУДАРСТВЕННЫЙ АЭРОКОСМИЧЕСКИЙ УНИВЕРСИТЕТ имени академика С П.Королева» (СГАУ) на кафедре технической кибернетики и в Институте систем обработки изображений РАН

Научные руководители член-корреспондент РАН, профессор

Защита состоится « 30 » сентября в 10 00 часов на заседании диссертационного совета Д 212215 07 в Самарском государственном аэрокосмическом университете имени академика С П.Королева по адресу: 443086, г Самара, Московское шоссе, д 34

С диссертацией можно ознакомиться в библиотеке Самарского государственного аэрокосмического университета имени академика С П.Королева.

ВА.Сойфер

кандидат технических наук, доценг

A.Г.Храмов

Официальные оппоненты' доктор физико-математических наук, профессор

B.М.Чернов

кандидат физико-математических наук, доцент М.Н.Осипов

Ведущая организация-

Институт проблем управления сложными системами

РАН.

Автореферат разослан« 29 » августа 2005 г.

Ученый секретарь диссертационного совета, д.т н, профессор

И В Белоконов

Общая характеристика работы

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

Актуальность исследования. Сложность изучения объектов окружающего мира зачастую связана с невозможностью непосредственного получения информации о пространственной форме объекта в целом. Наблюдению, как правило, доступны лишь отдельные проекции объекта. Кроме того, объект исследования в процессе получения проекционных данных может в некоторой степени изменять свою пространственную конфигурацию (подвергаться возмущениям), а проекции на этапе регистрации подвергаются воздействию шумов и искажений. Далее в работе такие проекции будем называть нечетко наблюдаемыми, а сами наблюдения будем называть нечеткими. Восстановление пространственной формы объекта в какой-либо определенный момент времени по наблюдаемым данным не всегда представляется возможным (Хермен Г., 1983; Старк Г., 1992). Вследствие этого возникает задача реконструкции пространственной формы объекта по набору нечетких проекционных данных. В настоящей работе рассматривается класс нечетко наблюдаемых древовидных объектов.

Одним из наиболее ярких примеров задачи восстановления пространственной формы древовидных объектов по нечетким проекционным данным является задача восстановления пространственной структуры коронарных сосудов по результатам рентгеновской ангиографии (Храмов А.Г, Корепанов А 0 , 2002; Blondel С, Devemay F, Mourgues F, 2001) Кроме этого задача реконструкции пространственной структуры древовидных объектов по нечетко наблюдаемым проекциям возникает в целом ряде биомедицинских задач, связанных с анализом сосудистой системы человека, таких как задача анализа сосудов глазного дна человека, задача анализа сосудов головного мозга (Haris К., Efstratiadis S N., 1997) и др.

Традиционные методы решения таких задач (Vaillant R, Devernay F., 2001; Molina С, PrauseG , 1998) позволяют производить восстановление пространственной структуры с высокой точностью, однако обладают существенным недостатком, заключающемся в требовании статичности объекта наблюдения или одновременности регистрации проекций нестационарного объекта Вследствие этого предлагаемые методы не могут быть использованы в условиях нечетких наблюдений.

Другой широко распространенный способ решения указанной задачи предполагает, что на различных проекциях имеются наборы точек геометрической привязки плоскостей проекций, заведомо являющихся проекциями одних и тех же пространственных точек (Mourgues F., Devemay F , 2001 ; Niki N, Kawata Y, 1993; Prinet V, Monga 0, 1997) Предлагаемые в рамках данного подхода методы позволяют производить геометрическую коррекцию проекций и восстанавливать объекты с высокой точностью Существенным недостатком данного подхода является необходимость задания на проекциях точек пространственной привязки, что, как правило, невозможно, либо определение таких точек является приближенным и может вносить существенную погрешность в результат восстановления

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

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

1 Разработка математической модели нечетких наблюдений пространственных древовидных объектов

2 Разработка информационных технологий вое >й структуры

древовидных объектов по нечетко наблюдаемым проекциям

3 Разработка метода и алгоритма восстановления центральной линии ветви древовидного объекта на изображениях проекций.

4 Разработка метода и алгоритма восстановления пространственной структуры ветви древовидного объекта по набору центральных линий на проекциях

5 Экспериментальные исследования разработанных алгоритмов на имитационных моделях и на натурных данных.

Научная новизна работы. В диссертации получены следующие новые научные результаты.

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

2 Вейвлет-методь; построения нечеткого поля направлений, основанные на использовании непрерывного вейвлет-преобразования и методов дифференциальной геометрии

3 Метод восстановления центральных линий на основе анализа поля направлений с использованием динамического программирования

4 Метод и алгоритм восстановления пространственной структуры древовидных объектов по нечетко наблюдаемым проекциям, основанный на пространственной трассировке с пошаговым согласованием пространственных и проекционных направлений.

На защиту выносится:

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

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

3 Решение задачи восстановления центральных линий на проекции древовидного объекта с использованием нечеткого поля направлений методом динамического программирования

4 Алгоритм фассировки с пошаговым согласованием направлений для восстановления пространственной структуры древовидного объекта по нечетко наблюдаемым проекциям при наличии ограниченных возмущений

Апробация работы. Основные результаты диссертационной работы докладывались на следующих конференциях 6-я международная конференция "Распознавание образов и анализ изображении новые информационные технологии" (Великий Новгород, 2002), 17th Internationa) Conference on Pattern Recognition (Кембридж, Великобритания, 2004), 7-я международная конференция "Распознавание образов и анализ изображений новые информационные технологии" (Санкт-Петербург, 2004), конференция «Фундаментальные науки - медицине» (Москва, 2004).

Публикации. По теме диссертации опубликовано 9 работ Работы [5,7] выполнены автором лично, остальные работы написаны в соавторстве.

Исследования по теме диссертационной работы были поддержаны грантами Российского фонда фундаментальных исследований (проект № 03-01-00642), Американского фонда гражданских исследований и развития (проект CRDF SA-014-02) в рамках российско-амеррканской программы «Фундаментальные исследования и высшее образование» (BRHE), при финансовой поддержке фонда «Научный потенциал», а также в рамках программы фундаментальных исследований Президиума РАН «Фундаментальные науки - медицине»

Структура диссертации. Диссертация состоит из введения, четырех глав, заключения, списка литературы (76 наименований) и одного приложения Основной текст работы изложен на 130 страницах (6ej приложения) и содержит 54 рисунка

Краткое содержание работы

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

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

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

Структура древовидного объекта описывается деревом конечного порядка О = где V = {у,,I = ЦУ}- множество вершин дерева, 5 = {?,,/ = 1,^-1} - множество ориентированных ребер дерева Порядок всех вершин графа, за исключением концевых равен 3, порядок последних равен 1 Концевая вершина V, называется начетом или корнем дерева

Каждой вершине V, из множества V ставится в соответствие пространственная точка, называемая узловой точкой или просто узлом В качестве веса ребра 5,, ; = 1, Л' -1 рассмотрим некоторую гладкую пространственную кривую без самопересечений

*,=*,(/), 0</<£,, (1) которую будем называть центральной линией (ЦП) сегмента древовидного объекта

Каждому ребру дерева л, ставится в соответствие гладкая вещественнозначная функция г.; (/) > 0 (функция радиуса сегмента). Множество точек, принадлежащих объединению

множества замкнутых шаров и й[л, (/1г((/)],

она,

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

линии с функцией радиуса сегмента

Под ветвью древовидного объекта, ассо-, циированной с ; -й концевой вершиной, пони-

мается совокупность сегментов соединяющих 1 -ю вершину с корнем дерева.

Древовидным объектом (ДО) называется совокупность сегментов и узловых точек, соответствующих некоторому дереву

Возмущение ДО рассматривается на примере одной ветви и описывается изменением его ЦП При этом полагаем, что пространственная точка О, соответствующая началу дерева сохраняет свое пространственное положение, и не происходит нарушения гладкости ЦЛ

Пусть *(/), / е [0, ¿] - ЦЛ ветви древовидного объекта в некотором статическом состоянии, х{1, г) - центральная линия ветви в момент регистрации г -й проекции, 1 = \,Ы РЛ (возмущенное состояние объекта). Тогда д:(/,<) = .*(/) + £(/,;), где г(/,<) - непрерывная пространственная кривая, описывающая возмущение ЦД. ДО является слабоменяющимся, если существует некоторое с > 0 такое, что для V; в(1, <)||в < с, где |л)в = шах|

,—v,

*4ч у "'о ......—

.____ "О

......-р

Рис 1 Сегменты древовидного объекта

Нечеткие наблюдения - это наблюдения проекций возмущенных состояний объекта Наблюдение проекции ДО описывается проецированием его ЦЛ Проекция возмущенной ЦЛ ветви на плоскость А, описывается кривой- = х,(*,)+£/($<), где х,(.5,) = \Рх\(/) - проекция объекта в стационарном состоянии (четкая проекция), г,(я() = [/>е0]|(/) - возмущение четкой проекции.

В работе рассмотрена математическая модель проекции древовидного объекта Под проекцией понимается пара объектов РА, ={А,, /(*)), где А, - плоскость проекции, /,{х) -функция изображения проекции

Плоскость проекции будем определять единичным бивектором А, =а* л а,2, где а/, а,1 - единичные вектора, задающие базис 1-Й проекции, л - внешнее произведение векторов (О Бопипег, 2001) За начало координатной системы на г -й плоскости О, примем проекцию точки О на эту плоскость.

Обозначим проекцию центральной линии ветви ДО х(/,/) = дс(/, ) В результате параллельного проецирования на г -ю плоскость гладкой пространственной кривой х(1, <) получится кривая

= (2) необязательно гладкая В отличие от центральной линии пространственной ветви, ее проекция может иметь самопересечения Зависимость натурального параметра з, функции х, ) от натурального параметра / пространственной центральной линии л(/,;) определяется'

*,=*,®='ЦГ.(гИ а*- (3)

о

где Г,(/) = Ж0л»„

Задача восстановления пространственной структуры ДО формулируется в следующем виде Пусть имеются нечеткие проекции РА,, / = РЛ ветви ДО По имеющимся проекциям необходимо восстановить пространственную ЦЛ древовидного объекта, согласованную с наблюдаемыми проекциями наилучшим образом Критерий согласованности пространственной ЦЛ будет определен ниже в главе 4

Решение задачи восстановления пространственной структуры в соответствии с рассмотренной моделью наблюдений предлагается разделить на два основных этапа (рис 2) (I) выделение двумерных центральных линий ветвей древовидного объекта на проекциях, (2) восстановление пространственных центральных линий по набору двумерных Построение центральных линий предлагается производить методами динамического программирования на основе анализа нечеткого поля направлений по набору опорных точек, проставленных экспертом Восстановление пространственной структуры объекта предлагается производить по набору двумерных центральных линий ветвей методом пространственной трассировки

Во второй главе рассмотрены понятия пространства направлений, четкого и нечеткого поля направлений (ПН), предлагаются вейвлег-методы формирования нечеткого поля на-

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

Рис 2 Общая схема процедуры восстановления пространственной структуры ДО

Определим некоторую точку О на плоскости. Пространство направлений О2 - это множество всех отрезков прямых на плоскости, центры которых лежат в точке О. В качестве нормы | | направления примем значение длины соответствующего отрезка прямой (аналог ' веса направления в комплексном представлении). В работе определяется сумма направлений,

умножение направления на скаляр, а также скалярное произведение направлений Такое представление направлений удобно с точки зрения геометрической интерпретации и позво-I ляет задать непосредственно сам объект «направление» (безотносительно координатной сис-

темы) как в двумерном, так и в многомерном случае.

Эффективный способ анализа класса изображений сетчатых структур на основе поля направлений предложен в работах Сойфера В.А, Храмова А.Г, Ильясовой Н Ю. и др. При построении полей направлений данного класса изображений учитывается наличие на них ярко выраженных локальных направлений Применительно к анализу изображений древовидных объектов аппарат поля направлений теряет свою эффективность из-за неоднозначности определения направлений в узловых областях древовидного объекта, а также в местах наложения сегментов на изображениях проекций Для устранения указанного недостатка предлагается использовать нечеткое поле направлений.

Рассмотрим нечеткое подмножество ¿ = {//(4^} (Л.Заде, 1965) пространства направлений О2, где (еЕ, £= еО2 = 1}, //( )е[0,1] - характеристическая функция принадлежности направлений

Пусть в каждой точке х = (г1,л2) некоторой области X определено нечеткое множество направлений /-,(*)= {р(х,?(х))/?(х)} Тогда будем говорить, что в пределах области X задано нечеткое ПН.

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

рим их более подробно.

J

а) б) в)

Рис 3 Пример дефазифицированного ПН: исходное изображение коронарных сосудов (а), весовая функция ПН (б); функция направлений (в)

1 Метод оценивания нечеткого поля направлений, основанный на непрерывном вейв-лет-преобразовании

Пусть /(х)е £2(r2) Рассмотрим неизотропный вейвлет у/(х) Тогда семейство базисных функций вейвлет разложения будет Va,et, (*) = а~' ' (*-£)), где а - масштабный коэффициент, b = (b>,b2) - сдвиг, re(x)=Gx - оператор поворота, О - матрица вращения. Тогда вейвлет разложение имеет вид ty¥f\a,0,b) = С~|/2(/, V„,ojb) > где (у) - скалярное

произведение в пространстве £2(r2) (Добегай И , 2001)

В работе предлагается использовать направленные вейвлеты, т е вейвлеты, эффективный носитель которых в частотной области локализован в пределах конуса с вершиной в начале координат Такие вейвлеты наилучшим образом соответствуют задаче выделения направлений, так как обладают угловой избирательностью (Antoine J -Р, Murenzi R, 1996)

Для решения задачи построения поля направлений (вследствие того, что ориентация направления меняется в пределах [О, п) ) предлагается использовать веерный вейвлет, являющийся объединением двух противоположно ориентированных направленных вейвяетов

Результирующий четырехмерный вейвлет образ содержит большое коли-

чество избыточной информации, усложняющей анализ изображения Нечеткое ПН может быть получено при уменьшении размерности вейвлет образа и избавлении от ненужной информации [9]. Нормируем вейвлет образ на максимальное значение его вейвлет коэффициента Для каждой точки х определяется нечеткое множество направлений ¿(х) Угол поворота вейвлета в определяет ориентацию соответствующего единичного направления t(x) с функцией принадлежности р(х,е(х))= тах

К/¡("Л*)

2 Метод оценивания нечеткого поля направлений с использованием дифференциальной геометрии

Основная идея метода заключается в представлении функции яркости изображения как

поверхности в трехмерном пространстве и вычислении главных кривизн и соответствующих главных направлений.

Рассмотрим некоторую гладкую функцию /(*), где л: = (х\дг2). Отображение г х к> (лг, /(*)) задает регулярную поверхность в трехмерном пространстве Кривизна поверхности определяется первой и второй фундаментальными формами Матрицы первой и второй фундаментальной формы имеют вид-

где/=/;,/, <,/ = 1,2

Для нахождения главных кривизн Я,,^ и главных направлений . поверхности необходимо определить собственные числа пары квадратичных форм, решив уравнение <Ы(<2~ М3)= О С целью уменьшения влияния шумов и одновременного анализа элементов, имеющих различные геометрические характеристики, производим фильтрацию исходной

функции яркости изображения фильтром g{a,x) = e~as° ^ , где а > 0 - масштабная переменная Результирующая фильтрованная функция будет И(а, х) = / * ¿{а,х)

Оценивание кривизны производится по функции И(а,х) при фиксированном значении параметра масштаба. Для вычисления производных первого и второго порядка воспользуемся формулой: = /*Ща,х).

дх, дх,

Рассмотрим двумерные гауссовы вейвлеты вида.

1//',(а,х)=~а~1 х,%{а,х), ^(а,х) = а~ъ (V'*,)2 '^^(^х), Ч/г{а,х) = а~!' х, х2 г{а,х),

где 1 = 1,2. Частные производные функции /(а,х) в матрице первой и второй фундаментальных форм можно рассчитать по формулам

/>М = /Ь>)*г!(а,у), /„{",*)=У). /¡2(с,х)=/{у)*^3(а,у),тДе / = 1,2

Получаемый в результате в каждой точке набор главных направлений может быть интерпретирован как нечеткое множество с функцией принадлежности, численно равной минимальной главной кривизне, нормированной на максимальное значение минимальной главной кривизны //(*,£)= Д(а,х|/тах/1(а, Соответствующие элементы нечеткого ПН равны

((а х)= 1^(а,х), где оператор ¿е каждому вектору х ставит в соответствие единичное направление (, такое, что (\\х

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

ЦЛ проекции ветви ДО в дискретном представлении получается в результате дискретизации кусочно-гладкой кривой (2) и описывается последовательностью точек плоскости X = \х" , либо последовательностью векторов, У = {у" , гДе у" = - х" Для учета непрерывности и кусочной гладкости исходной кривой введем следующие ограничения Ограничение на расстояние между соседними точками дискретной ЦЛ

/„.^У^'«,, » = 0,^-1. (4)

где 0 < /тш < 7гаах - положительные константы дискретизации Ограничение на угловое отклонение дискретных разностей

тах((С£е/,МС£е/+'));,-со, (5)

где с0 =cos(2tp0), р0 - угол, определяющий максимальное возможное отклонение дискретных разностей ЦЛ от значения касательной („ к кривой (2) в точке х" (рис 4)

В диссертационной работе задачу восстановления двумерной ЦЛ предлагается представить в виде задачи динамической оптимизации (Беллман Р, Дрейфус С . 1965), то есть отыскания оптимальной траектории движения

от начальной опорной точки к конечной _

Опорными являются точки, проставляемые /

экспертом и заведомо принадлежащие ЦЛ х" /'^у'

ДО.

Пусть на изображении /(*), * е .Доопределена пара опорных точек , 62 е Df, заведомо принадлежащих ЦЛ

Введем обозначения х" - переменная состояния - и-я точка центральной линии,

и = 0- переменная управления, Plic. 4ограничение на угловое отклонение левой n = 0,N-\, R, - ограничение на возмож- дискретной разности

ные значения х" • F - функция потерь, зависящая от переменных управления и состояния,

Ф - целевая функция Динамическая модель процесса движения с дискретным временем хп+] - х"

имеет вид —-= у" Везде далее будем считать At -1 Целевая функция, подлежащая

At

n-l , .

минимизации, равна ф(х) = ^F(x" ,у" j, где функция потерь определяет потери при движете

ник из точки х" в точку х" +у" Ограничения Л,, Л2 определяют краевые условия траектории R, • х° =b', Я2 х" ~ Ь2 Ограничения Я3, Л4, Rs - определяют вид траектории и отражают ограничения (4) и (5)' Л3 |>'"|г/тт; Л4: Jy| < 1тшх;

Количество точек N центральной линии также подлежит определению В качестве функции потерь f{x" ,у" ) выбирается некоторая функцию, зависящая от нечеткого множества направлений взятого либо в точке х", либо в точке х" + у" В работе рассматривалась следующая функции потерь

x'eDj-

f(x\/')==o, x"eD/

Минимизация целевой функции производится по всевозможным наборам X =

В качестве оценки касательного направления 1"п к кривой (2) в точке х" выбирается направление из нечеткого множества направлений /.(.г"), имеющее максимальное значение

функция принадлежности Ч'п = arg max(w(x",

ые

Рассмотрим алгоритм восстановления центральной линии по двум опорным точкам Будем рассматривать классы точек Хр = " множество точек изображения, для

которых оценка оптимальной траектории до начальной точки х° в текущий момент времени (на текущем шаге итерации) состоит из р точек (не считая х°) Оценку функции потерь для

оптимальной траектории от некоторой точки Хрт до х" в текущий момент времени обо-

точки х" = х На множестве точек изображения введем отношение -< • х ч у, если выполняются следующие условия- 1. х е или у е , 2 ф(у)>ф(х)+Г(х,у-х); 3 ф(х)<ф[х"), для любых двух точек х,у^П{ Если какая-либо точка х е Ду находится в отношении с некоторой точкой изображения, то будем говорить, что она нарушает порядок

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

0-й шаг Положим, что в начальный момент времени' для изображения определено нечеткое поле направлений ¿(дг), х° =б'; ф(х°)= 0; ф(х) = оо, V*е

р -й шаг Рассматриваются все точки класса Хр~1 Пусть некоторая точка ХрА,т находится в отношении с точкой х Тогда точка х относится к классу Хр (пусть, для определенности, под номером к), значение функции потерь для этой точки определяется как

Точка Хр~'-т становится точкой-предшественником для точки Хр* Все точки изображения (включая точки, принадлежащие классу ХрЛ), с которыми точки класса ХрА находятся в отношении, образуют класс Хр

Условие выхода Шаги продолжаются до исчерпания в последнем рассматриваемом классе Xм точек, нарушающих порядок.

Пусть точка Ь2 принадлежит классу X", тогда общее количество точек в центральной линии равно N и х" = Ь2 Так как для каждой точки определен предшественник, то можно определить последовательность X точек, соединяющих конечную точку х" с начальной х", которая и является искомой центральной линией.

Восстановление по множеству опорных точек производится последовательно для каждой пары опорных точек

Экспериментальные исследования работы алгоритма выделения центральных линий проводятся на двух видах изображений модельных изображениях и изображениях, полученных в реальных физических условиях Модельное изображение представляет собой искусственно сгенерированное изображение ветви ДО с известными характеристиками Исследуется погрешность восстановления двумерной ЦЛ ветви в зависимости от различных параметров модельных изображений' отношения сигнал/шум (А) (рис 5), коэффициента корреляции соседних отсчетов фона, частоты колебаний ЦП, относительной частоты колебаний диаметра ветви объекта Погрешность восстановления рассчитывается по следующей формуле

значим ф(хрт)=Фр'т.

Обозначим 5(д:) - область изображения, определенную ограничениями й3, Я4, Д5 для

8 = 5(х,х)=Х- /И/)-^/)|Ы\

Ь л

(I-

(6)

где *(/), / е [о, ¿] - исходная ЦЛ, *(/), / е [о, ¿] - восстановленная ЦЛ, г] = ^ - коэффициент сжатия восстановленной центральной линии

Экспериментальные исследования на натурных изображениях проводились на изображениях ангиографиче-ских проекций коронарных сосудов. Исследовались 10 изображений ДО (коронарных сосудов), каждое из которых содержит от 3 до 7 изображений ветвей. Качество работы алгоритма оценивалось визуально

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

В четвертой главе рассмотрен метод восстановления пространственной структуры древгьид;ш1 объектов по набору двумерных центральных линий Проведены экспериментальные исследования предложенного метода

Вследствие нелинейности искажений, возникающих в системе наблюдения при регистрации объекта, мы вынуждены отказаться от существующих линейных подходов к реставрации пространственных изображений (Прэтг У, 1982). Для решения задачи реконструкции пространственной структуры необходимо определить критерии согласованности восстанавливаемой пространственной ЦЛ с имеющимися ЦЛ на проекциях В ряде работ (Paiker D L , Wu J 1998, Prmet V, Monga О , 1997, Stevenson D J, 1997) предлагаются различные критерии согласованности, которые используются для реконструкции пространственной ветви при наличии априорной информации о соответствии друг другу наборов точек на проекциях Однако такая информация зачастую недоступна, поэтому при разработке критерия мы будем считат ь что точек пространственной привязки проекций нет

П)сл имеется набор проекций РА,, t = 1, N ¡,A и на каждой проекции определена ЦЛ ветви ДО xt{s). где s - натуральный параметр кривой, x¡ (о) = О, Обозначим

у, (\, = \х (s)) s Пусть X = {i(w)}„=¡¡"¡7 - дискретное представление пространственной ЦЛ,

У = {3>(") Lï.vTi. где >>(«) = х(п + 1)- х(п) и |Р(и]|| = Д.

Точка х, (.s (ni) называется идеальной проекцией пространственной точки х{п) на i-ю плоскость, если параметры s - s(n) и / = Д п связаны выражением (3) (рис 6) Идеальной проекцией точки х(н -t i) на ; -й плоскости является точка je, (.s(")+Цд', {"Л), гДе у, (») = [Ру\{п), х (s(n)) - идеальная проекция точки х(п) Тогда критерий согласованности пространственной ЦП с наблюдаемыми проекциями будет Ns

III У, (А, V (у(г<) л п, ))f wfl , (7)

где п - нормаль .- -и плоскости, v - пересечение бивекторов То есть необходимо найти точку i), для которой вектор у(п) имел бы в проекциях минимальное среднеквадратиче-ское откл мнение о ¡ соответствующих векторов у, (s) (от своих идеальных проекций)

Дня решения задачи восстановления пространственной ЦЛ ДО предлагается метод, ос-нованчый на пространственной трассировке с пошаговым согласованием пространственных направлений с направлениями ЦЛ на проекциях Каждый шаг трассировки можно разделить на два основных этапа

1 Поиск оптимального в смысле (7) вектора центральной линии Минимизация (7)

! ; 1 h LI - ; i i -

|* i

i* -

--r

- t: -

-

« ~~1 - i

У •

• • 1 - -

1

I* ft • 1 i

f • i 4 • • »

107 4ое 474 sea esz аш 12« ггзо вам

Рис 5 Зависимость погрешности восстановления ЦЛ от отнтиения сигнал/и/ум

% Ai(/0)

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

Пусть на предыдущем шаге определена точка *(п) пространственной ЦЛ, и ее идеальные проекции х, (з(п)) Искомый вектор у = у(п) имеет фиксированную длину Д и определяет пространственную сферу = Д как множество возможных положений точки ;Е(л + 1) пространственной ЦЛ. На поверхности сферы для /-Й проекции можно определить функцию /, (у) как квадрат расстояния от проекции у, вектора у на плоскость РА, до своей идеальной проекции

/,(у)=1у, -хДЦу,!)!2 Суммарная функция Рис 6 Отклонение проекции пространствеино-" го объекта от центральных линий наблюдав-

будет /М = "£/,(У). ^проекции

1=1

Поиск минимума осуществляется итерационно методом градиентного спуска Градиент функции ft (у) на г -м шаге итерации равен

{{у'-а.Ч^а.Чу

2-[(1 -г, смв,)-*, + (| - Г/СО!!0,)А]ЗША • где в1 - угол между вектором у' и вектором его идеальной проекции х, (Цу," ||), ф, - угол

(fr-

Р,

между плоскостью РА, и вектором /,w,= \х,(р,\[х,(р,% )> Y, =., ,

Следующее приближение уг*' вектора у(п) определяется выражением yr = А|v| 'v, где v = /"'-aV/(j;r"1), ae(0,l) Итерации продолжаются до тех пор, пока не будет выполнено условие | уг - I <, е, для некоторого е>0

2 После нахождения вектора определяется следующая точка пространственной центральной линии i(n + l)= х(л) + _р(л) и соответствующие ей точки на проекциях (те ее идеальные проекции) s, (га +1) = s, (л)+|р, (и|

Рассматривая задачу восстановления объектов по проекциям, можно ввести некоторую характеристику, которая показывала бы, насколько полно рассматриваемый объект представлен на той или иной проекции Пусть x(l) - исследуемая пространственная ЦЛ,

y(l) = (х(/)) Степенью наблюдаемости объекта на проекции называется величина.

= /."' Lk, где Lk - длина наблюдаемой проекции ЦЛ, L - длина исследуемой пространст-

венной ЦП, к = 1, N РЛ.

Введем соответствующую характеристику наблюдаемости объекта на наборе проекций Степенью наблюдаемости объекта на паре проекций назовем величину'

1 1

<ц =7Л| "</ л уЩа <Я' где пц=п,/\п1 о

То есть наблюдаемость объекта на паре проекций равна среднему значению проекции единичного касательного вектора ЦЛ на линию пересечения проекций (рис.7) Тогда для набора проекций степень наблюдаемости объекта будет

1 Чм

/ = —-— . Степень наблюдаемости обь-

СЫрА Рис 7 Степень наблюдаемости объекта на

паре проекций

екта на наборе проекций максимальна в случае,

когда ЦЛ объекта параллельна всем проекциям, и равна 0 (т е минимальна) в случае, когда наблюдается юффект книги»

Рассмотрим случаи, когда восстановление объекта по набору проекций невозможно

1 Набор проекций (или взаимное расположение проекций) является вырожденным, если дня V;,у = 1,NРЛ выполняется условие я, лл; =0, те все плоскости компланарны Восстановление объекта по такому набору проекций, очевидно, невозможно, если только 1к* 1

2 «Эффект книги» Пусть имеется невырожденный набор проекций, на каждую из которых некоторый участок ЦЛ проецируется в виде прямой, задаваемой вектором с, Условие

возникновения «эффекта книги» запишется в виде с, ли, л(су +и^)=0, для = NГА Т е все проекции пересекаются по одной прямой и все векторы с, перпендикулярны ей Наблюдаемость рассматриваемого участка ЦЛ на таком наборе проекций / = 0 и его восстановление невозможно

Экспериментальные исследования работы алгоритма восстановления пространственных центральных линий производятся на двух видах объектов- модельных древовидных объектах и на древовидных объектах, проекции которых получены в реальных физических условиях (на коронарных сосудах, представленных ангиографическими проекциями) Погрешность восстановления пространственных центральных линий (<$) рассчитывается аналогично погрешности в двумерном случае по формуле (7)

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

Рис 8 Зависимость погрешности восстановления пространственной ЦЛ от количества проекций

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

Заключение

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

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

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

3 Предложен и исследован метод восстановления центральных линий на основе анализа нечеткого поля направлений с использованием динамического программирования

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

5 Предложен количественный показатель степени наблюдаемости объекта на наборе проекций для оценки возможности и качества восстановления пространственной структуры древовидного объекта по д анному набору проекций

6 Получены численные оценки зависимости качества восстановления пространственной структуры от геометрических параметров исследуемых объектов и условий регистрации проекций с использованием имитационных моделей Проведены экспериментальные исследования на натурных данных.

Основные результаты опубликованы в следующих работах:

1 Н.Ю.Ильясова, А.О. Корепанов, А В Куприянов, В Г. Баранов, А Г. Храмов «Анализ структуры сосудистой системы сердца методом трассировки изображений проекций», Сб Компьютерная оптика, N23,2002, с. 53-57.

2 АО Корепанов, Н Ю Ильясова, А В. Куприянов, А Г Храмов «Метод определения оптимального пространственного направления сосудов в задаче восстановления 3D топологии коронарной системы», Труды 6-й международной конференции РОАИ-2002, с. 299-303

3 А.О Корепанов, Н Ю Ильясова, А В Куприянов, А Г Храмов «Метод определения оптимального пространственного направления сосудов в задаче восстановления 3D топологии коронарной системы», сб Компьютерная оптика, N24,2002, с 152-154

4 А.О Корепанов, А.В Куприянов, А В Устинов, А Г, Храмов, А А Ковалёв «Метод пространственного восстановления коронарных артерий по малому числу ангиографических проекций», сб.Компыотерная оптика, N 26,2004, с 89-97

5 А.О.Корепанов, Вейвлет-методы выделения центральных линий на ангиографических изображениях проекций коронарных сосудов, Вестник Самарского государственного аэрокосмического университета имени академика С П Королева, Вторая летняя школа молодых ученых по дифракционной оптике и обработке изображений, 2004 г., с 36-38

6 В А Сойфер, В В.Котляр, А Г Храмов, Н Ю Ильясова, А.В Куприянов, А О Корепанов, А А Ковалев, А В.Устинов Компьютерная система ранней диагностики глазных заболеваний на основе анализа изображений глазного дна. - Фундаментальные науки - медицине Материалы конференции Москва, 2-3 декабря 2004 г - М Фирма "Слово", 2004, с 131-137

7 АО Korepanov, Central lmes extraction on the diagnostic vessel images using the methods of wavelet-analysis and differential geometry // Proceedings of the 7th International Conference on

№15363

Pattern Recognition and Image Analysis (PRIA-7-2004), Vol 3,2004, pp 740-743.

8 AO Korepanov, N.Yu.Il'yasova, a.V Kupriyanov, and AG Khramov «A Method for Determination of an Optimal Spatial Direction of Vessels in the Problem of Reconstructing the 3D Topology of a Coronary System», Pattern Recognition and Image Analysis, Vol. 13, No 2, 2003, pp 287-289.

9 V A. Soifer, A G Khramov, A O Korepanov "Fuzzy Direction Field Method for Fringe and Tree-like Patterns Analysis", Proceedings of the 17th International Conference on Pattern Recognition (ICPR), Vol. 2,2004, pp 779-782

РНБ Русский фонд

2006-4 16246

Подписано в печать 01 04 05 Формат 60 х 84 1/16 Бумага офсетная Усл. печ. л 1,0 Тираж 100 экз.

Заказ ¿49

ВВЕДЕНИЕ

ГЛАВА 1 МАТЕМАТИЧЕСКАЯ МОДЕЛЬ ДРЕВОВИДНЫХ ОБЪЕКТОВ И ВОССТАНОВЛЕНИЕ ИХ ПРОСТРАНСТВЕННОЙ СТРУКУТУРЫ ПО

НАБЛЮДАЕМЫМ ПРОЕКЦИЯМ

1.1 Математическая модель пространственного древовидного объекта

1.2 Математическая модель нечетких наблюдений древовидного объекта

1.3 Математическая модель проекции древовидного объекта

1.4 Основные этапы решения задачи восстановления пространственной структуры древовидных объектов

1.5 Проблема устойчивости методов реконструкции пространственной структуры древовидных объектов по нечетко наблюдаемым проекциям 32 Выводы и результаты

ГЛАВА 2 НЕЧЕТКОЕ ПОЛЕ НАПРАВЛЕНИЙ И МЕТОДЫ ЕГО ОЦЕНИВАНИЯ

2.1. Идея нечеткого поля направлений

2.2. Пространство направлений

2.3. Поле направлений

2.4. Нечеткое поле направлений

2.5. Арифметические операции над нечеткими множествами направлений

2.6. Вейвлет-методы оценивания нечеткого поля направлений

2.6.1. Метод оценивания нечеткого поля направлений, основанный на непрерывном вейвлет-преобразовании

2.6.2. Метод оценивания нечеткого поля направлений с использованием дифференциальной геометрии

Выводы и результаты

ГЛАВА 3 ВОССТАНОВЛЕНИЕ ДВУМЕРНОЙ СТРУКТУРЫ ДРЕВОВИДНЫХ

ОБЪЕКТОВ НА ИЗОБРАЖЕНИЯХ ПРОЕКЦИЙ

3.1 Описание центральной линии проекции ветви древовидного объекта в дискретном представлении

3.2 Задача восстановления центральных линий по опорным точкам

3.3 Восстановление дискретной центральной линии по двум опорным точкам методом динамического программирования

3.4 Алгоритм восстановления центральной линии по двум опорным точкам

3.5 Восстановление центральной линии по множеству опорных точек ф 3.6 Экспериментальные исследования метода восстановления центральных линий

Выводы и результаты

ГЛАВА 4 ВОССТАНОВЛЕНИЕ ПРОСТРАНСТВЕННОЙ СТРУКТУРЫ

ДРЕВОВИДНЫХ ОБЪЕКТОВ

4.1 Восстановление пространственной структуры ветви древовидного объекта по набору центральных линий проекций

4.2 Метод пространственной трассировки с пошаговым согласованием пространственных и проекционных направлений

4.3 Степень наблюдаемости объекта на наборе проекций

4.4 Анализ неблагоприятных случаев расположения проекций

4.5 Экспериментальные исследования метода восстановления пространственной центральной линии древовидного объекта 104 Выводы и результаты

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

Актуальность работы

Сложность изучения объектов окружающего мира зачастую связана с невозможностью непосредственного получения информации о пространственной форме объекта в целом. Наблюдению, как правило, доступны лишь отдельные его проекции [16, 18]. Кроме того, объект исследования в процессе получения проекционных данных может в некоторой степени изменять свою пространственную конфигурацию (подвергаться возмущениям), а проекции на этапе регистрации подвергаются воздействию шумов и искажений [29, 57]. Далее в работе такие проекции будем называть нечетко наблюдаемыми, а сами наблюдения будем называть нечеткими. Восстановление пространственной формы объекта в какой-либо определенный момент времени по таким данным не всегда представляется возможным [21, 59, 63]. Вследствие этого возникает задача реконструкции некоторой пространственной формы объекта по набору нечетких проекционных данных.

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

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

Рис. В. 1 — Ангиографические изображения коронарных сосудов

Одним из наиболее ярких примеров задачи восстановления пространственной формы древовидных объектов по нечетким проекционным данным является задача восстановления пространственной структуры коронарных сосудов человека по результатам рентгеновской ангиографии [6*, 28, 57]. Рентгеновская ангиография широко распространена в кардиологии и используется для выявления патологических изменений кровеносных сосудов сердца человека. На основе данных рентгеновской ангиографии выносится решение об операбельности пациента. Однако визуальное наблюдение проекций зачастую не позволяет дать количественное определение характера поражения сосудов, так как пораженный сосуд может выглядеть критическим на одной проекции, в то время как на другой проекции тот же сосуд может не обнаруживать признаков заболевания. Визуальное представление пространственной формы сосудов пациента существенно облегчит врачу определение характера заболевания, позволит наглядно увидеть структуру сердечных сосудов и оценить общее ее состояние в целом.

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

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

Традиционно задача восстановления пространственной структуры решается либо для статического объекта, либо для набора проекций, наблюдаемых одновременно [28, 49, 51, 52, 56]. Предлагаемые в рамках этого подхода методы позволяют производить восстановление пространственной структуры с высокой точностью, однако обладают существенным недостатком, заключающемся в требовании статичности объекта наблюдения или одновременности регистрации проекций нестационарного объекта. Вследствие этого предлагаемые методы не могут быть использованы в условиях нечетких наблюдений.

Другой широко распространенный способ решения предполагает, что на различных проекциях имеются наборы точек геометрической привязки плоскостей проекций, заведомо являющихся проекциями одной и той же пространственной точки [57, 59, 63, 64, 66]. Предлагаемые в рамках данного подхода методы позволяют производить геометрическую коррекцию проекций и восстанавливать объекты с высокой точностью. Существенным недостатком данного подхода является необходимость задания на проекциях точек пространственной привязки, что, как правило, невозможно, либо определение таких точек является приближенным и может вносить существенную погрешность в результат восстановления. Автору не удалось найти работ, анализирующих зависимость погрешности восстановления пространственной структуры древовидного объекта от погрешности определения точек соответствия.

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

Обзор существующих методов решения задачи восстановления пространственной структуры древовидных объектов

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

1. Методы восстановления и анализа пространственной плотности объекта.

Характерной особенностью данных методов является то, что первоначально производится восстановление пространственной плотности (интенсивности) области пространства, содержащей объект, без анализа формы и топологии самого объекта [44, 46, 59, 47]. Визуализация таких объектов может производиться с использованием воксельной графики. Информация об объекте получается при дальнейшем анализе функции пространственной интенсивности. Например, в работах Н. Schmitt [71], W. Е. Higgins и др. [45] предложены методы анализа пространственных ангиограмм, такие как адаптивная пороговая обработка, адаптивная заливка и др., которые позволяют получить информацию о форме исследуемого объекта. В работах Е. Bullitt и S.R. Aylward [29] для выявления пространственного дерева кровеносных сосудов предложен метод анализа «хребтов» пространственной функции интенсивности (аналогичные работы тех же авторов [27, 30, 31, 26]). Метод выделения центральных линий объектов и реконструкции их пространственной формы, на основе анализа восстановленной пространственной интенсивности предложен Y. Kawata, N. Niki, и T. Kumazaki в работе [48].

Рассмотренные методы хорошо работают в условиях, когда пространственная интенсивность может быть восстановлена достаточно точно, либо определена изначально. В условиях, когда имеется малое количество проекций (а также при наличии динамического объекта), при восстановлении пространственной плотности возникают различного рода артефакты [21], которые делают невозможным дальнейший анализ формы объекта. Недостатком рассмотренных методов является также необходимость расстановки набора начальных точек на пространственном изображении, что является непростой задачей для пользователя. 2. Методы, основанные на пространственном моделировании.

Эта группа представляет широкий класс методов связанных с моделированием пространственных объектов и дальнейшим согласованием с имеющимися данными проекций [38, 67]. Например, в работах Y. Sato, T. Araki, M. Hanayama, H. Naito, S. Tamura [70] и T. Kayikcioglu, S. Mitra [49] используется обобщенная цилиндрическая модель сосудов. В работах С. Pellot, A. Herment, M. Sigelle [64], J. A. Fessier, A. Macovski [39] используется эллиптическая модель сечения ветвей объекта для восстановления пространственной формы. Уточнение формы производится в этом случае, например, с использованием алгоритма модельной "закалки" [64] или модифицированным методом Marquardt-Levenberg'a [51, 52]. Одним из наиболее эффективных методов уточнения модели является метод активных контуров, используемый, например, в [56] для уточнения параметров 2?-сплайновой модели сечения ветвей древовидных объекта.

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

3. Методы, основанные на анализе изображений проекций и выделении на них ветвей (или их центральных линий) с последующим восстановлением пространственных ветвей (или их центральных лини).

Примерами такого подхода могут служить работы D. L. Parker, J. Wu и R.E. van Bree [63], V. Prinet, O. Monga и J.M. Rocchisani [66], DJ. Stevenson [75]. Рассмотренные работы имеют общую схему восстановления пространственной структуры: на первом этапе производится выделение центральных линий на изображениях проекций, на втором этапе на их основе производится пространственное совмещение и реконструкция объекта.

Данный класс методов является наиболее широким, так как он лишен специфических ограничений на характеристики проекций, присущих другим методам. Такой подход позволяет производить восстановление пространственной структуры объектов в условиях сильного рассогласования проекций (т.е. при наличии погрешности задания геометрических параметров проекций и при регистрации динамического объекта), а также при малом их количестве (2-5 проекций) [28, 57]. Далее, при разработке методов восстановления пространственной структуры древовидных объектов мы будем придерживаться именно этого подхода.

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

Методы выделения центральных линий на изображениях могут быть также разделены на несколько категорий: (1) методы, основанные на моделировании (работы [68, 55, 60, 32, 65]), (2) методы с использованием нейросетей ([36, 58, 56, 72]), (3) методы трассировки (работы [6*, 78, 42, 62, 33, 44]), (4) методы, основанные на распознавании образов ([69, 35, 63, 66, 25]) и др. Названия категорий говорят сами за себя. Мы не будем подробно описывать существующие методы анализа изображений древовидных объектов, отметим лишь следующее. Анализ литературы показал, что наиболее эффективной при решении рассматриваемой задачи является последняя категория методов, основанных на распознавании образов. Среди существующих методов наиболее перспективными представляются методы, основанные на мультимасштабном анализе изображений [73*, 69, 35, 76], а также методы, основанные на анализе дифференциальных свойств изображений [53*, 66]. Наиболее гибкий аппарат предоставляют методы, являющиеся совмещением указанных подходов, т.е. методы, использующие дифференциальные свойства изображений и мультимасштабный анализ для выделения ветвей (или их центральных линий) на изображениях проекций [25, 53*]. Аналогичные методы с некоторыми модификациями будут использованы для формирования нечетких полей направлений, при разработке методов анализа центральных линий на изображениях проекций древовидных объектов [53*, 73*].

Цель и задачи исследований

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

1. Разработка математической модели нечетких наблюдений пространственных древовидных объектов.

2. Разработка и исследование информационной технологии восстановления пространственной структуры древовидных объектов по нечетко наблюдаемым проекциям.

3. Разработка метода и алгоритма восстановления центральной линии ветви древовидного объекта на изображениях проекций.

4. Разработка метода и алгоритма восстановления пространственной структуры ветви древовидного объекта по набору центральных линий на проекциях.

5. Экспериментальные исследования разработанных алгоритмов на имитационных моделях и на натурных данных.

Научная новизна работы

В диссертации получены следующие новые научные результаты:

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

2. Вейвлет-методы построения нечеткого поля направлений, основанные на использовании непрерывного вейвлет-преобразования и методов дифференциальной геометрии.

3. Метод восстановления центральных линий на основе анализа поля направлений с использованием динамического программирования.

4. Метод и алгоритм восстановления пространственной структуры древовидных объектов по нечетко наблюдаемым проекциям, основанный на пространственной трассировке с пошаговым согласованием пространственных и проекционных направлений.

Апробация работы

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

1. 6-й Международной конференции "Распознавание образов и анализ изображений: новые информационные технологии" (РОАИ-2002), Великий Новгород, 2002 г.

2. 17th International Conference on Pattern Recognition (ICPR), г. Кембридж, Великобритания, 2004 г.

3. 7-й Международной конференции "Распознавание образов и анализ изображений: новые информационные технологии" (РОАИ-2004), (Санкт-Петербург), 2004 г.

4. Конференции «Фундаментальные науки - медицине», Москва, 2004 г. По теме диссертации выполнено 9 работ. Работа [53*] выполнена автором единолично, остальные работы написаны в соавторстве. В работе [6*] автором предложен алгоритм двумерной трассировки сосудов и алгоритм выбора направления движения на основе анализа локальной оценки толщины сосуда. В работах [7*, 8*, 54*] автору принадлежат алгоритм построения полусферы возможных направлений, методы поиска минимумов функции, определенной на сфере, метод пространственной трассировки. В работе [73*] автору принадлежат вейвлет-методы оценивания нечеткого поля направлений. В работе [50*] автором предложен вейвлет-метод оценивания центральных линий кровеносных сосудов. В работе [13*] автору принадлежит метод пространственной трассировки. В работе [19*] автору принадлежит алгоритм оценивания локальных направлений сосудов. В диссертацию включены только результаты, полученные соискателем лично.

Исследования по теме диссертационной работы были поддержаны грантами Российского фонда фундаментальных исследований (проект № 0301-00642), Американского фонда гражданских исследований и развития (проект CRDF SA-014-02) в рамках российско-американской программы «Фундаментальные исследования и высшее образование» (BRHE), при финансовой поддержке фонда «Научный потенциал», а также в рамках программы фундаментальных исследований Президиума РАН «Фундаментальные науки - медицине» 2004 г.

Основные положения диссертации, выносимые на защиту

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

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

3. Решение задачи восстановления центральных линий проекции древовидного объекта с использованием нечеткого поля направлений методом динамического программирования.

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

Выводы и результаты

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

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

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

ЗАКЛЮЧЕНИЕ

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

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

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

3. Предложен и исследован метод восстановления центральных линий на основе анализа нечеткого поля направлений с использованием динамического программирования.

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

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

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

1. БеллманР., Дрейфус С. Прикладные задачи динамического программирования, М.: Наука, 1965, 457 с.

2. Винберг Э.Б., Курс алгебры, M.: Факториал Пресс, 2002, 544 с.

3. Дубровин Б.А., Новиков С.П., Фоменко А.Т., Современная геометрия: Методы и приложения, М.: Эдиториал УРСС, Т.1., 1998, 334 с.

4. Игнатьева A.B., Краснощекова Т.И., Смирнов В.Ф., Курс высшей математики, М.: Высшая школа, 1968, 692 стр.

5. Ильясова Н.Ю. Методы и алгоритмы оценивания геометрических параметров диагностических изображений, Дисс. на соиск. учен. ст. канд. техн. наук., Самара, 1997,155 с.

6. Ильясова Н.Ю., Корепанов А.О., Куприянов A.B., Баранов В.Г., Храмов А.Г. «Анализ структуры сосудистой системы сердца методом трассировки изображений проекций», Сб. Компьютерная оптика, N23, 2002, с. 53-57.

7. Ильясова Н.Ю., Корепанов А.О., Куприянов A.B., Храмов А.Г. «Метод определения оптимального пространственного направления сосудов в задаче восстановления 3D топологии коронарной системы», Труды 6-й международной конференции РОАИ-2002., с. 299-303.

8. Ильясова Н.Ю., Корепанов А.О., Куприянов A.B., Храмов А.Г. «Метод определения оптимального пространственного направления сосудов в задаче восстановления 3D топологии коронарной системы», Сб.Компьютерная оптика, N24, 2002, с. 152-154.

9. Ильясова Н.Ю., Устинов A.B., Храмов А.Г. Методы анализа дактилоскопических изображений на основе поля направлений, Научное приборостроение, Т.З, с.89-101,1993, Санкт-Петербург.

10. Князев П.Н., Функциональный анализ, М.: Высшая школа, 1985.

11. Лебедев В.И., Функциональный анализ и вычислительная математика: Учебное пособие, М.: Физматлит, 2000, 296 с.

12. Ли Т.Г., Адаме Г.Э., Гейнз У.М. Управление процессами с помощью вычислительных машин. Моделирование и оптимизация, М.: «Советское радио», 1972, 312 с.

13. Корепанов А.О., Куприянов А.В., Устинов А.В., Храмов А.Г., Ковалёв А.А. «Метод пространственного восстановления коронарных артерий по малому числу ангиографических проекций», Сб.Компьютерная оптика, N 26, 2004, (принята к публикации).

14. Круглов В.В., ДлиМ.И., Годунов Р.Ю., Нечеткая логика и искусственные нейронные сети, М.: Физматлит, 2001, 224 с.

15. Методы компьютерной обработки изображений (под ред. В.А, Сойфера). -М.: Физматлит, 2001.

16. Наттерер Ф., Математические аспекты компьютерной томографии, пер. с англ.-М.: Мир, 1990.

17. Прэтт У., Цифровая обработка изображений, кн. 2, М.: Мир, 1982, 790 с.

18. Реконструкция изображений, под ред. Г. Старка, пер. с англ., М.: Мир, 1992.

19. Тарханов В.И., Геометрическая алгебра язык творческого мышления, Айрэс (С.-Пб.), 2004

20. Хермен Г., Восстановление изображений по проекциям: Основы реконструктивной томографии, пер. с англ. -М.: Мир, 1983.

21. Шварц Дж., Дифференциальная геометрия и топология, М.: Мир, 1970.

22. Antoine J.-P. and MurenziR., Two-dimensional directional wavelets and the scale-angle representation, Signal Proc. 1996. -No.53. - P. 259-281.

23. Antoine J.-P., Vandergheynst P., and Murenzi R., Two-dimensional directional wavelets in image processing, Int. J. Imag. Syst. Tech. 1996. -No.7: - P. 152-165.

24. Armande N., Montesinos P., and Monga O., Thin nets extraction using multi-scale approach, Computer Vision and Image Understanding, vol. 73, pp. 248257,1999.

25. Aylward S.R. and Bullitt E., Initialization, noise, singularities, and scale in height ridge traversal for tubular object centerline extraction, IEEE Trans, on Med. Img., vol. 21, pp. 61-75, February 2002.

26. Aylward S.R., Pizer S., Bullitt E., and Eberl D., Intensity ridge and widths for tabular object segmentation and registration, in Wksp on Math. Methods in

27. Biomed. Image Analysis,^- 131-138, 1996.

28. Blondel C., Vaillant R., Devernay F., Malandain G., Ayache N., Automatic trinocular 3D reconstruction of coronary artery centerlines from rotational X-ray angiography, CARS, 2002

29. Bullitt E. and Aylward S.R., Analysis of time-varying images using 3D vascular models // in Proc. Applied Imagery Pat. Recog. Works., pp. 9-14, October 2001.

30. Bullitt E., Aylward S.R., Smith S., Mukherji K., JiroutekM., and MullerK., Symbolic description of intracerebral vessels segmented from mra and evaluation by comparison with x-ray angiograms, IEEE Medical Image Analysis, vol. 5, pp. 157-169, 2001.

31. ChanR.C., Karl W.C., and LeesR.S., A new model-based technique for enhanced small-vessel measurements in x-ray cine-angiograms, IEEE Trans, on Med. Img, vol. 19, pp. 243-255, March 2000.

32. Chandrinos K.V., Pilu M., Fisher R.B., and Trahanias P.E., Image processing techniques for the quantification of atherosclerotic changes, in Mediterranian Conf. Medical and Bio. Eng. and Computing, June 1998.

33. Chui C., An Introduction to Wavelets, San Diego, Academic Press, 1992.

34. Chwialkowski M.P., Ibrahim Y.M., Hong F.L., and Peshock R.M., A method for fully automated quantitative analysis of arterial flow using flow-sensitized MR-images, Comp. Med. Imaging and Graphics, vol. 20, pp. 365-378, 1996.

35. Cronemeyer J., HeisingG., and Orglmeister R., A fast skeleton finder for parallel hardware, in IEEE Computers in Cardiology, pp. 23-26, 1992.

36. Daubechies I., Ten Lectures on Wavelets, CBMS-NSF Reg. Conf. Series in Appl. Math. 61, Soc. Ind, Appl. Math., Philadelphia. 1992.

37. Dong Y., Hillman G.R., Three-dimensional reconstruction of irregular shapes based on a fitted mesh of contours, Image and Vision Computing, 19 (2001), 165 176.

38. Fessler J.A. and Macovski A., Object-based 3-d reconstruction of arterial trees from magnetic resonance angiograms, IEEE Trans, on Med. Img, vol. 10, pp. 25-39, March 1991.

39. Geometric Computing with Clifford Algebras: Theoretical Foundations and Applications in Computer Vision and Robotics / Ed.: G. Sommer. Berlin etc.: Springer-Verlag, 2001, p. 542.

40. HarisK., Efstratiadis S.N., Maglaveras N., and Pappas C., Semi-automatic extraction of vascular networks in angiograms, in IEEE Conf. Eng. in Medicine and Bio., pp. 1067-1068, 1997.

41. Hart M. and Holley L., A method of automated coronary artey tracking in unsubtracted angiograms, in IEEE Computers in Cardiology, pp. 93-96, 1993.

42. HestenesD. and ZieglerR., Projective Geometry with Clifford Algebra // Acta Applicandae Mathematicae, Vol. 23, (1991) 25-63.

43. Higgins W.E., Sypra W.J.T., Karwoski R.A., and Ritman E.L., System for analyzing hig-resolution three-dimensional coronary angiograms, IEEE Trans, on M?d. Img., vol. 15, pp. 377-385, June 1996.

44. Higgins W.E., Spyra W.J.T., RitmanE.L., Kim Y., and SpelmanF.A., Automatic extraction of the arterial tree from 3-d angiograms, in IEEE Conf. Eng. in Medicine and Bio., vol. 2, pp. 563-564, 1989.

45. Hunter I.A., Soraghan J J., and McDonagh Т., Fully automatic left ventricular boundary extraction in echocardiographic images, in IEEE Computers in Cardiology, pp. 741-744, 1995.

46. Kawata Y., Niki N., and Kumazaki Т., An approach for detecting blood vessel diseases from cone-beam ct image, in IEEE Int. Conf. on Image Processing, pp. 500-503, 1995.

47. Kawata Y., NikiN., Kumazaki Т., and MoonierP.A., Characteristics measurement for blood vessel diseases detection based on cone-beam ct images, in IEEE Nuclear Science Symposium and Medical Imaging Conference, vol. 3, pp. 1660-1664, 1995.

48. Kayikcioglu T. and Mitra S., A new method for estimating dimensions and 3d reconstruction of coronary arterial trees from biplane angiograms, in IEEE Comp.-BasedMed. pp. 153-158, 1993.

49. KitamuraK., Tobis J.M., and SklanskyJ., Biplane analysis of atheromatous coronary arteries, in Proc. Int. Conf. Pattern Rec., vol.2, pp. 1277-1281, 1988.

50. Kitamura K., Tobis J.M., and Sklansky J., Estimating the 3-d skeletons and transverse areas of coronary arteries from biplane angiograms, IEEE Trans, on Med. Img., vol. 7, pp. 173-187, September 1988.

51. Korepanov A.O., Central lines extraction on the diagnostic vessel images using the methods of wavelet-analysis and differential geometry //

52. Proceedings of the 7th International Conference on Pattern Recognition and Image Analysis (PRIA-7-2004), Vol. 3, pp. 740-743, 2004.

53. Kozerke S., Botnar R., Oyre S., Scheidegger M.B., Pedersen E.M., and BoesingerP., Automatic vessel segmentation using active contours in cine phase contrast flow measurements, J. of Mag. Res. Imaging, vol. 10, pp. 4151, July 1999.

54. Molina C., Prause G., Radeva P., and Sonka M., 3D catheter path reconstruction from biplane angiograms, in SPIE, vol. 3338, pp. 504-512, 1998.

55. Mourgues F.,Devernay F., Malandain G., and Coste-Maniere E., 3D+t Modeling of Coronary Artery Tree from Standard Non Simultaneous Angiograms // in Proc. on MICCAI. 2001. - P. 1320 1322.

56. Nekovei R. and Sun Y., Back-propagation network and its configuration for blood vessel detection in angiograms, IEEE Trans, on Neural Nets, vol. 6, pp. 64-72, January 1995.

57. Niki N., Kawata Y., Satoh H., and Kumazaki T., 3D imaging of blood vessels using x-ray rotational angiographic system, IEEE Med. Imaging Conf., vol. 3, pp. 1873-1877, 1993.

58. O'DonnellT., BoultT.E., FangX., and Gupta A., The extruded generalized cylinder: A deformable model for object recovery, in Proc. of the IEEE Conf on CVPR, pp. 174-181, 1994.

59. Ososkov G., and Shitov A., Gaussian Wavelet Features and their Applications for Analysis of Discretized Signals, Computer Physics Communications, vol.126, 2000, pp. 149-157.

60. Park S., Lee J., Koo J., Kwon O., and Hong S., Adaptive tracking algorithm based on direction field using ml estimation in angiogram, in IEEE

61. Conference on Speech and Image Technologies for Computing and Telecommunications, vol. 2, pp. 671-675, 1997.

62. Parker D.L., WuJ., and BreeR.E. van, Three dimensional vascular reconstruction from projections: A theoretical review, in IEEE Conf Eng. in Medicine and Bio., 1988.

63. PellotC., HermentA., and SigelleM., A 3d reconstruction of vascular structures from two x-ray angiograms using an adapted simulated annealing algorithm, IEEE Trans, on Med. Img, vol. 13, pp. 48-60, March 1994.

64. Petrocelli R.R., ElionJ., and ManbeckK.M., A new method for structure recognition in unsubtracted digital angiograms, in IEEE Computers in Cardiology, pp. 207-210, 1992.

65. Prinet V., Monga O., and Rocchisani J.M., Multi-dimensional vessel extraction using crest lines, in IEEE Conf. Eng. in Medicine and Bio., vol. 1, pp. 393-394, 1997.

66. Rockwood A.P., Winget J., Three-dimensional object from two dimensional images, Computer-Aided Design, Vol. 19, No.4, 1997, 279 285.

67. RueckertD., Burger P., ForbatS.M., Mohiaddin R.D., and YangG.Z., Automatic tracking of the aorta in cardiovascular mr images using deformable models, IEEE Trans, on Med. Img., vol. 16, pp. 581-590, October 1997.

68. Sarwal A. and Dhawan A.P., 3-d reconstruction of coronary arteries, in IEEE Conf. Eng. in Medicine and Bio., vol. 1, pp. 504-505, 1994.

69. Sato Y., Araki T., Hanayama M., Naito H., and Tamura S., A viewpoint determination system for stenosis diagnosis and quantification in coronary angiographic image acquisition, IEEE Trans, on Med. Img., vol. 17, pp. 121137, February 1998.

70. Schmitt H., Grass M., Rasche V., Schramm O., Haehnel S., and Sartor K., An x-ray-based method for the determination of the contrast agent propagation in 3-d vessel structures, IEEE Trans, on Med. Img, vol. 21, pp. 251-262, March 2002.

71. Shiffman S., Rubin G.D., and Napel S., Semiautomated editing of computed tomography sections for visualization of vasculature, vol. 2707, SPIE, 1996.

72. Soifer V.A., Khramov A.G., Korepanov A.O. "Fuzzy Direction Field Method for Fringe and Tree-like Patterns Analysis", Proceedings of the 17th International Conference on Pattern Recognition (ICPR), Vol. 2, pp.779-782, 2004.

73. Soifer V.A., Kotlyar V.V., Khonina S.N., and Khramov A.G., The Method of the Directional Field in the Interpretation and Recognition of the Images with Structure Redundancy // Pattern Recognition and Image Analysis, v.6, No.4, pp.710-724 (1996).

74. Stevenson D.J., Working towards the automatic detection of blood vessels in x-ray angiograms, Pattern Rec. Let., vol. 6, pp. 107-112, July 1987.

75. Summers P.E. and Bhalerao A.H., Derivation of pressure gradients from magnetic resonance angiography using multi-resolution segmentation, in Proceedings of International Conference on Image Processing and its Applications, pp. 404-408, 1995.

76. SuterJ., Geometric Algebra Primer, http://home.student.utwente.n1/i.suter/, 2003.

77. Tolias Y. and Panas S.M., A fuzzy vessel tracking algorithm for retinal images based on fuzzy clustering, IEEE Trans, on Med. Img., vol. 17, pp. 263273, April 1998.