Содержание к диссертации
Введение
ГЛАВА 1 Математическая модель древовидных объектов и восстановление их пространственной струкутуры по наблюдаемым проекциям 14
1.1 Математическая модель пространственного древовидного объекта 14
1.2 Математическая модель нечетких наблюдений древовидного объекта 20
1.3 Математическая модель проекции древовидного объекта 22
1.4 Основные этапы решения задачи восстановления пространственной структуры древовидных объектов 28
1.5 Проблема устойчивости методов реконструкции пространственной структуры древовидных объектов по нечетко наблюдаемым проекциям 32
Выводы и результаты 33
ГЛАВА 2 Нечеткое поле направлений и методы его оценивания 34
2.1. Идея нечеткого поля направлений 34
2.2. Пространство направлений 35
2.3. Поле направлений 39
2.4. Нечеткое поле направлений 40
2.5. Арифметические операции над нечеткими множествами направлений 42
2.6. Вейвлет-методы оценивания нечеткого поля направлений 42
2.6.1. Метод оценивания нечеткого поля направлений, основанный на непрерывном вейвлет-преобразовании 43
2.6.2. Метод оценивания нечеткого поля направлений с спользованием дифференциальной геометрии 51
Выводы и результаты 57
ГЛАВА 3 Восстановление двумерной структуры древовидных объектов на изображениях проекций 58
3.1 Описание центральной линии проекции ветви древовидного объекта в дискретном представлении 58
3.2 Задача восстановления центральных линий по опорным точкам 59
3.3 Восстановление дискретной центральной линии по двум опорным точкам методом динамического программирования 61
3.4 Алгоритм восстановления центральной линии по двум опорным точкам 63
3.5 Восстановление центральной линии по множеству опорных точек 67
3.6 Экспериментальные исследования метода восстановления центральных линий 67
выводы и результаты 88
ГЛАВА 4 Восстановление пространственной структуры древовидных объектов 89
4.1 Восстановление пространственной структуры ветви древовидного объекта по набору центральных линий проекций 89
4.2 Метод пространственной трассировки с пошаговым согласованием пространственных и проекционных направлений 93
4.3 Степень наблюдаемости объекта на наборе проекций 100
4.4 Анализ неблагоприятных случаев расположения проекций 103
4.5 Экспериментальные исследования метода восстановления пространственной центральной линии древовидного объекта 104
Выводы и результаты 120
Заключение 122
Литература
- Математическая модель нечетких наблюдений древовидного объекта
- Арифметические операции над нечеткими множествами направлений
- Задача восстановления центральных линий по опорным точкам
- Метод пространственной трассировки с пошаговым согласованием пространственных и проекционных направлений
Введение к работе
Диссертация посвящена разработке информационной технологии восстановления пространственной структуры древовидных объектов по нечетко наблюдаемым проекциям
Актуальность работы
Сложность изучения объектов окружающего мира зачастую связана с невозможностью непосредственного получения информации о пространственной форме объекта в целом. Наблюдению, как правило, доступны лишь отдельные его проекции [16, 18]. Кроме того, объект исследования в процессе получения проекционных данных может в некоторой степени изменять свою пространственную конфигурацию (подвергаться возмущениям), а проекции на этапе регистрации подвергаются воздействию шумов и искажений [29, 57]. Далее в работе такие проекции будем называть нечетко наблюдаемыми, а сами наблюдения будем называть нечеткими. Восстановление пространственной формы объекта в какой-либо определенный момент времени по таким данным не всегда представляется возможным [21, 59, 63]. Вследствие этого возникает задача реконструкции некоторой пространственной формы объекта по набору нечетких проекционных данных.
Предметом исследования настоящей работы является класс нечетко наблюдаемых древовидных объектов. К таким объектам с некоторой степенью приближения можно отнести русла рек, сети дорог, ветви деревьев, сосуды кровеносной системы человека и другие. Примеры древовидных объектов показаны на рисунке 1.1.
В диссертационной работе рассматривается задача восстановления пространственной структуры древовидных объектов по результатам нечетких наблюдений, то есть по результатам наблюдений проекций возмущенных состояний объекта.
в кардиологических клиниках задача реконструкции пространственной структуры древовидных объектов по нечетким проекционным данным представляется актуальной.
Помимо рентгеновской ангиографии задача реконструкции пространственной структуры древовидных объектов по нечетко наблюдаемым проекциям возникает в целом ряде биомедицинских задач, связанных с анализом сосудистой системы человека, таких как задача анализа сосудов глазного дна человека, задача компьютерной томографии сосудов головного мозга [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, и Т. Kumazaki в работе [48].
Рассмотренные методы хорошо работают в условиях, когда пространственная интенсивность может быть восстановлена достаточно точно, либо определена изначально. В условиях, когда имеется малое количество проекций (а также при наличии динамического объекта), при восстановлении пространственной плотности возникают различного рода артефакты [21], которые делают невозможным дальнейший анализ формы объекта. Недостатком рассмотренных методов является также необходимость расстановки набора начальных точек на пространственном изображении, что является непростой задачей для пользователя. 2. Методы, основанные на пространственном моделировании.
Эта группа представляет широкий класс методов связанных с моделированием пространственных объектов и дальнейшим согласованием с имеющимися данными проекций [38, 67]. Например, в работах Y. Sato, Т. Araki, М. Hanayama, Н. Naito, S. Tamura [70] и Т. Kayikcioglu, S. Mitra [49] используется обобщенная цилиндрическая модель сосудов. В работах С. Pellot, A. Herment, М. Sigelle [64], J. A. Fessler, A. Macovski [39] используется эллиптическая модель сечения ветвей объекта для восстановления пространственной формы. Уточнение формы производится в этом случае, например, с использованием алгоритма модельной "закалки" [64] или модифицированным методом Marquardt-Levenberg a [51, 52]. Одним из наиболее эффективных методов уточнения модели является метод активных контуров, используемый, например, в [56] для уточнения параметров 5-сплайновой модели сечения ветвей древовидных объекта.
Рассмотренные методы обладают большими возможностями и высокой точностью восстановления объектов в случае, когда имеются согласованные, либо слабо рассогласованные проекции (большинство предложенных методов предназначены для синхронной биплановой съемки объекта). Одним из существенных недостатков рассмотренных методов является необходимость в априорной информации о примерной форме объекта и низкая степень автоматизации.
3. Методы, основанные на анализе изображений проекций и выделении на них ветвей (или их центральных линий) с последующим восстановлением пространственных ветвей (или их центральных лини).
Примерами такого подхода могут служить работы D. L. Parker, J. Wu и R.E. van Bree [63], V. Prinet, O. Monga и J.M. Rocchisani [66], D.J. 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 ] автору принадлежит алгоритм оценивания локальных направлений сосудов. В диссертацию включены только результаты, полученные соискателем лично.
Исследования по теме диссертационной работы были поддержаны грантами Российского фонда фундаментальных исследований (проект № 03-01-00642), Американского фонда гражданских исследований и развития (проект CRDF SA-014-02) в рамках российско-американской программы «Фундаментальные исследования и высшее образование» (BRHE), при финансовой поддержке фонда «Научный потенциал», а также в рамках программы фундаментальных исследований Президиума РАН «Фундаментальные науки - медицине» 2004 г.
Основные положения диссертации, выносимые на защиту
1. Метод построения нечеткого поля направлений, основанный на использовании непрерывного вейвлет-преобразования и учитывающий локальные пространственно-частотные характеристики изображения при построении характеристической функции принадлежности направлений.
2. Метод построения нечеткого поля направлений, основанный на вычислении кривизны функции яркости, позволяющий производить предварительное оценивание характеристической функции принадлежности направлений и учитывать локальные дифференциальные свойства функции яркости.
3. Решение задачи восстановления центральных линий проекции древовидного объекта с использованием нечеткого поля направлений методом динамического программирования.
4. Алгоритм трассировки с пошаговым согласованием направлений для восстановления пространственной структуры древовидного объекта по нечетко наблюдаемым проекциям при наличии ограниченных возмущений.
Математическая модель нечетких наблюдений древовидного объекта
Под нечеткими наблюдениями будем понимать наблюдение проекций возмущенных состояний объекта. Термин «нечеткость наблюдений» в работе используется для характеристики физических свойств системы наблюдения и подразумевает наличие геометрических искажений наблюдаемого объекта, а также присутствие шумов регистрации.
Наблюдение проекции древовидного объекта будем описывать проецированием его центральной линии. Рассмотрим проецирование на примере центральной линии одной ветви древовидного объекта (рис. 1.4). Пусть определен набор плоскостей проекций At, i = \,N, в которых наблюдается объект и [р\ - оператор проецирования точек трехмерного пространства на плоскость В результате нечетких наблюдений имеется набор проекций возмущенного объекта, полученных в различные моменты времени, который будем называть набором нечетких проекций:
Так как z -ю проекцию будем ассоциировать с проекцией объекта в t(-n момент времени, то далее будем опускать параметр t(, при записи характеристик проекций, например, х{ (st) = х( (s{, tl).
В силу аддитивности оператора проецирования можно записать М (1.3) где Дя,) = [Ріс], (/) - проекция объекта в стационарном состоянии (четкая проекция), i(si) = [Ps(ti)]i(l) - возмущение четкой проекции. Очевидно, что для кривой ,-(.5,-) также выполняется условие ограниченности возмущений Результатом наблюдения объекта является набор его проекций. Под проекцией понимается пара объектов РА, = (А,,/,{х)), (1.4) где Ai - плоскость проекции, fi(x) - функция изображения проекции. Плоскость проекции Для описания геометрии будем использовать понятия геометрической алгебры [40,43]. Плоскость проекции будем определять единичным 12 12 бивектором Aj = ai л а, , где at , at - единичные вектора, задающие базис /-й проекции [20]. Единичный вектор нормали плоскости проекции определяется выражением nt=Atr\ где / = е1ле2ле3,Г1= -/ [77].
За начало координатной системы на / -й плоскости О, примем проекцию точки О на эту плоскость. Так как рассматривается параллельное проецирование, то смещение плоскости проекции от начала координат О является несущественным. Поэтому будем предполагать, что взаимное расположение плоскости проекции и точки начала координат таково, что
Проекция пространственной точки х на плоскость проекции определяется выражением [40, 77]: xt=(x-At)A-\ где А = а2 л ах.
Отклонение пространственной точки от плоскости проекции определяется выражением [40, 77]: ф)={хлА,)АГ1. Проекция центральной линии ветви древовидного объекта Прежде чем определить функцию изображения проекции рассмотрим проекцию центральной линии ветви древовидного объекта. Обозначим x(l,i) = x(l,tt). В результате параллельного проецирования на і -ю плоскость гладкой пространственной кривой JC(/, /) получится кривая ,( ,) = ( (/, ) 4 Л (1.5) необязательно гладкая. В отличие от центральной линии пространственной ветви, ее проекция может иметь самопересечения.
Рассмотрим вопрос о соотношении натуральных параметров s{ и параметра / и определим точки, в которых проекция центральной линии теряет гладкость. Для этого необходимо установить связь между производной пространственной центральной линии в некоторой точке и производной ее проекции в соответствующей точке. Обозначим y(l,i) и yj{sj) производные функций (/,/) и ,($,) соответственно.
Арифметические операции над нечеткими множествами направлений
Благодаря определению операции сложения в пространстве направлений, помимо логических операций над нечеткими множествами направлений можно ввести арифметические операции. Арифметические операции вводятся по аналогии с операциями над нечеткими числами [14].
Пусть ,ь2еЕ, тогда Ь = Ц Ь2, //(/) = S (\МЄіУі / 2 2) І 2ІІ где S( ) - треугольная конорма [14], знак " " означает какую-либо арифметическую операцию. Так как в пространстве направлений определены операции сложения и вычитание направлений, то арифметические операции также ограничиваются этими двумя операциями. В случае, когда 5(-) = тах(-) сумма и разность нечетких множеств будут иметь вид: L = Ц ± L2, где ju() = max ( /, ± 2 ), (26) т.е. единичное направление принадлежит нечеткому множеству направлений с весом max (fl i ± 2 )» где максимум берется по всем парам l±2\\i направлений { = ,( ,)-- ,-, t єL(, / = 1,2, таким что направление х+2 коллинеарно с .
Очевидно, в результате рассмотренных логических и арифметических операций, носитель результирующего нечеткого множества направлений также будет содержать только направления единичной длины, то есть удовлетворять определению нечеткого множества направлений.
Различные методы формирования поля направлений рассмотрены в работе [15 стр. 459-523]. Логическим продолжением идеи поля направлений является построение поля направлений, зависящего в каждой точке от анализируемых локальных пространственных частот [74]. В спектральной области это соответствует анализу различных частотных интервалов в пределах некоторого сектора частот. Далее рассмотрены различные методы формирования нечеткого поля направлений.
Предлагается два метода построения: метод, основанный на вейвлет разложении исходного изображения, и метод, основанный на анализе кривизны изображения. Оба подхода используют методы вейвлет анализа, позволяющие производить выделение элементов изображения, имеющих различные локальные частоты. В основе первого подхода лежит непрерывное вейвлет преобразование с неизотропным вейвлетом, за счет чего достигается его угловая избирательность. Второй метод базируется на анализе главных кривизн изображения, интерпретируемого как поверхность в трехмерном пространстве. Частотная избирательность достигается за счет применения вейвлет метода оценивания производных в матрицах первой и второй фундаментальной формы. Рассмотрим более подробно методы формирования нечеткого поля направлений.
Непрерывное вейвлет разложение Рассмотрим непрерывную двумерную функцию конечной энергии f(x)e L2(R2), где JC = (х\х2) и /2= J/W «. R2
В качестве функции изображения f(x) могут быть также взяты обобщенные функции, такие как, например, единичный импульс, прямоугольный импульс и др. Порождающим вейвлетом может быть выбрана любая функция у/ є і} (R2 )n L2 (R2 J, удовлетворяющая условию допустимости: где \J/(co) - спектр вейвлета, со - частота [34]. Последнее условие в данном случае означает просто нулевое среднее вейвлета у (0) = 0 = fy(x)d2x = 0. R2 Существует несколько способов расширения одномерного непрерывного вейвлет преобразования в Z2(R J [37]. Один из способов заключается в выборе вейвлета с круговой симметрией. В этом случае вейвлет преобразование легко обобщается на двумерный случай, однако является непригодным для анализа направлений. Второй способ расширения одномерного вейвлет преобразования основывается на выборе вейвлета без сферической симметрии (неизотропного вейвлета) и введении в вейвлет преобразовании наряду с параметрами сдвига и сжатия параметра вращения вейвлета. Такой способ расширения позволяет производить анализ направлений, поэтому далее используется вейвлет преобразование с неизотропным вейвлетом.
Рассмотрим неизотропный двумерный порождающий вейвлет у/(х). Семейство базисных функций вейвлет разложения получается из порождающего вейвлета посредством сдвигов, растяжений и поворотов последнего [23].
Задача восстановления центральных линий по опорным точкам
Задача выделения центральных линий объектов возникает во многих практических приложениях обработки изображений. Примерами могут служить задачи анализа медицинских изображений кровеносной системы [19 , 68, 36], задачи анализа изображений интерферометрических полос, задача анализа результатов каротажных измерений и т.п. [9, 73 , 74]. В данной работе необходимость выделения центральных линий на проекциях вызвана тем, что для восстановления пространственной структуры объекта необходимо иметь информацию о структуре его проекций.
Ангиографическое изображение коронарных сосудов Вследствие сложности структуры пространственного объекта на изображениях проекций могут присутствовать наложения теней от различных ветвей объекта, а также частичное или полное затенение одних частей объекта другими [13 ]. Поэтому зачастую даже человеку сложно определить центральную линию той или иной ветви на изображении проекции (рис. 3.2). По этой причине мы вынуждены отказаться от полностью автоматического распознавания центральных линий. Будем считать, что при восстановлении центральной линии ветви на изображении проекции древовидного объекта имеется упорядоченный набор опорных точек, заведомо принадлежащих исследуемой центральной линии.
Задачу восстановления центральной линии проекции ветви древовидного объекта можно сформулировать следующим образом. Пусть определено дискретное изображение проекции ветви древовидного объекта f[x), x = (xi,x2), и -Dy- = \х:0 х{,х2 Nf \ - область его определения. Пусть также имеется набор опорных точек В=\р )yjr, b eD, заведомо принадлежащих центральной линии ветви. Необходимо по имеющимся данным в соответствии с некоторым критерием произвести оптимальное восстановление упорядоченного множества X точек, являющегося дискретным описанием центральной линии.
В работе предлагается подход к решению данной задачи, основанный на динамической оптимизации траектории движения точки из начальной опорной точки к конечной. Для определения целевой функции предлагается использовать нечеткое поле направлений рассматриваемого изображения.
Задача восстановления двумерной центральной линии может быть представлена как задача динамической оптимизации [1], то есть отыскания оптимальной траектории движения от начальной опорной точки к конечной. Рассмотрим более подробно эту задачу.
Пусть на изображении f(x), xeDf определена пара опорных точек Ъх, b2eDf. Введем обозначения: JC" - переменная состояния - п-я точка центральной линии, n = 0,N , уп - переменная управления, п - 0,N -1; Rt - ограничение на возможные значения х"; F - функция потерь, зависящая от переменных управления и состояния; Ф - целевая функция. Тогда задачу поиска оптимальной траектории можно сформулировать в следующем виде [12, стр. 166]. Ограничения Rx, R2 определяют краевые условия траектории: Rx:x=tf\ R2:xN=b2. Ограничения R3, R4, R5 - определяют вид траектории и отражают ограничения (3.1) и (3.2): R, уп — mm » RA: УИ max і R5: тах(( ,Іе(у"))(Гя,4(/+,)Ь . Количество точек N центральной линии также подлежит определению. Рассмотрим более подробно функцию потерь и целевую функцию.
Целевая функция и функция потерь Пусть на основе изображения f(x) получено нечеткое поле направлений L(X). Будем считать, что в каждой точке имеется непрерывное нечеткое множество направлений L\xn)=[ju{x )j/j, в противном случае оно может быть получено интерполяцией функции принадлежности направлений ju\x",J. Тогда в качестве функцию потерь F\x",y"J можно выбрать некоторую функцию от направления Le\yn), зависящую от функции принадлежности направления, взятой либо в точке хп, либо в точке хп + уп.
Это связано с тем, что производная исходной кривой (1.5) может быть непрерывна в точке хп - как справа, так и слева. Причем эта зависимость должна быть «обратной», то есть функция потерь должна иметь максимумы только в точках, где функции принадлежности направлений имеют минимумы и наоборот. Помимо этого, чтобы предотвратить выход центральной линии за пределы изображения, необходимо значения функции потерь вне области D сделать бесконечно большими.
Метод пространственной трассировки с пошаговым согласованием пространственных и проекционных направлений
Для решения задачи восстановления пространственной структуры древовидного объекта предлагается метод, основанный на пространственной трассировке с пошаговым согласованием пространственных направлений с направлениями центральных линий на проекциях. Каждый шаг трассировки можно разделить на два основных этапа:
1. Поиск оптимального в смысле (4.6) вектора центральной линии. Минимизация (4.6) производится методом градиентного спуска по функции заданной на поверхности сферы, которая определяет в пространстве множество возможных положений следующей точки центральной линии.
2. После нахождения вектора определяется следующая точка пространственной центральной линии и соответствующие ей точки на проекциях (т.е. ее идеальные проекции).
После выполнения обоих этапов производится следующий шаг трассировки. Построение пространственной центральной линии продолжается до тех пор, пока, по крайней мере, на одной из проекций не будет достигнут конец центральной линии наблюдаемой проекции. Общая схема метода представлена на рисунке 4.2. Далее рассмотрены подробно этапы каждого шага восстановления пространственной структуры.
Пусть на предыдущем шаге определена точка х(п) пространственной центральной линии, а также определены соответствующие ей точки на проекциях xt(s{n$. Т.к. далее мы будем анализировать вектора, то без ущерба для решения поместим пространственное начало координат О в точку х(п), а начало координат 0, на каждой проекции в точку Xi(s(n)) (соответственно производится перенос начала отсчета параметров s,) [7 ].
Так как вектор у{п) пространственной центральной линии имеет фиксированную длину А, то можно определить пространственную сферу S радиуса А: = А с центром в точке О, задающую множество возможных положений последующей точки пространственной центральной линии (или возможные положения конца векторау(п)) [54 ]. Рассмотрим і-ю плоскость проекции РА( и лежащую на ней центральную линию x((s). На поверхности сферы можно определить функцию fiiy) как квадрат расстояния от проекции у( вектора у на плоскость PAt до соответствующей ей точки на кривой xi(s(nf) (до идеальной проекции), т.е ЛМ= - .(Ы)2. (4-8 где у1;= {у АІ)АІГ - проекция вектора у на плоскость РАп At=at ля, х бивектор, определяющий плоскость РАІ.
Определим некоторые свойства функции (4.8). Для некоторого р А имеем точку кривой х((р). Определим множество С±(р) точек сферы S для которых точка х((р) является идеальной проекцией, т.е таких что .У; = / (рис. 4.3). Последнее выражение определяет на плоскости РАІ окружность С((р). Точкой на этой окружности ближайшей к точке кривой xt{p) (т.е. к своей идеальной проекции), является проекция точки xt(p) на окружность СД/?) (рис. 4.3): уГ=рхі{р), (4.9) где хАр)=.. , !... А наиболее удаленной точкой, соответственно, является llw)l max диаметрально противоположная к у( точка УГ=-РЧР\ (4-Ю)
При движении по окружности Ct(p) от точки у0І к точке у1 І расстояние до точки xt{p) монотонно увеличивается. Пространственный вектор у длины Д, проекцией которого на плоскость РА; является вектор ут, определяется выражением у=уГ±Рпі, (4.11) А -р , щ нормаль плоскости PAt. Будем называть ее минимальной точкой для радиуса р (рис. 4.3).
Точки множества С±(р) определяются выражением )= minV где Яф =cos— + sin—Ап ф є[-л ,л\. Т.е. множество точек С±(р) определяет пару окружностей в пространстве, симметричных относительно плоскости РА; и лежащих в плоскостях ей компланарных. Заметим, что у(х) = у{-ж) = у.
Рассмотрим окружность С+(р) лежащую в положительной (относительно плоскости РА,) полусфере. Рассмотрим значения функции fiiy) на этой окружности. При ф = 0 достигается минимальное значение функции fiiy) (равно квадрату расстояния от точки у(тт до точки х,(р)), при ф = ±ж - максимальное (равно квадрату расстояние от точки у(тах до точки Xiip)). При движении по окружности С+ІР) ОТ точки утт к точке ута значение функции fiy) монотонно возрастает. Аналогично для окружности C_ip) второй полусферы.
