Scientific journal
Modern high technologies
ISSN 1812-7320
"Перечень" ВАК
ИФ РИНЦ = 0,940

DEVELOPMENT OF THE MODEL OF ROUTING FOR BRONCHONAVIGATION

Solovieva S.N. 1 no name 2
1 Ural Federal University
2 Research center «Avantrend»
The paper deals with the problem of navigation during bronchoscopy for taking pathological material in the lungs and investigates the problem of finding a way based on the processing and analysis of CT images. The problems justified by anatomical features of the lungs are formulated and analyzed. The perspective and urgency of development of the routing model for bronchial navigation at oncological diagnostics of lungs for biopsy material taking is shown. The literary and analytical review of bronchial navigation methods and path search algorithms is carried out. The criteria for evaluating the algorithms have been established and the criteria for evaluating the model for building a navigation map with the help of an intelligent agent that takes into account the borders and structure of the pathology as well as the anatomical structure of the lung and bronchial tree have been revealed. The package of algorithmic and functional-structural models illustrating the novelty of the proposed solution is developed. The novelty of the received solution consists in the fact that the developed model of routing for bronchial navigation includes all necessary criteria of processing and analysis of CT-images for creation of a navigation map with the use of the intellectual agent which considers borders and structure of pathology, and also anatomic structure of a lung and bronchial tree. The use of such an individual navigation map will increase the efficiency of bronchoscopy methods to obtain informative pathological material, which in turn will allow to make a more likely diagnosis and prescribe the correct treatment.
bronchoscopy
intellectual agent
computed tomography
route search
visualization

Диагностика заболеваний легких является сложной мультидисциплинарной проблемой. Между тем ведущим методом, «золотым стандартом» диагностики патологий легких являются компьютерная томография в совокупности с бронхоскопией или торакоскопией для взятия биопсионного материала [1].

Согласно исследованиям [2, 3], используя этот метод, не всегда удается получить диагностически значимый материал для биопсии из-за ограниченности используемого инструментария, использующегося в данных методах. Выделяют такие важные особенности, которые имеют большее влияние на информативность результатов диагностической бронхоскопии:

- индивидуальные анатомические особенности пациента;

- в применяемых методах нет учета анатомической структуры легких;

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

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

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

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

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

- провести литературно-аналитический обзор существующих методов навигации в легких;

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

- провести моделирование;

- разработать программное обеспечение модели.

Материалы и методы исследования

Информативность стандартного метода зависит от точности попадания в патологический очаг, которая при стандартной методике составляет примерно от 18% до 70% [3]. А точность попадания зависит от таких факторов, как [3]:

- продвижение по бронхиальному дереву;

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

- навигация до образования.

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

- выделения бронхиального дерева (3D реконструкция бронхиального дерева);

- выделения сегментов лёгкого;

- выявление границ патологии;

- определение места на основе текстурного анализа для взятия информативного материала;

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

- построение маршрута до целевой области с использованием интеллектуального агента.

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

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

- методы бронх-навигации;

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

Методы бронх-навигации

В настоящее время есть различные виды навигации при бронхоскопии. Так в работах [1, 4] используется программная среда MeVisLab, для решения задач выделения бронхиального дерева, а также расчета пути до целевой области, расчета попадания зонда прямо в патологическую ткань и глубины погружения биопсийных щипцов. Но в этой работе патология выделяется вручную, а места для взятия биоптата определяются субъективно врачом, проводящим эти действия, и основываются лишь на его предпочтении. Также при навигации не учитываются анатомические особенности легких, а из-за этого могут возникнуть нежелательные осложнения.

Wilbert G. Aguilar [5] в своей работе использует для поиска пути при проведении бронхоскопии метод RRT. Навигация по этому пути проходит в 3D модели легких, реконструированных из КТ изображений. Еще в работе сравниваются несколько алгоритмов RRT, которые ищут оптимальный путь для бронхоскопии. Также используется кинетическая модель бронхоскопа, который ограничивает метод RRT. Но в этой работе не учитываются анатомические особенности легкого, и место для взятия биоптата также выбирается вручную врачом.

Существуют работы, которые при навигации в легких используют анатомические ориентиры. Так в статье [6] описывается метод навигации при видеобронхоскопии до целевой области путем введения анатомических ориентиров, из анализа видеобронхоскопических изображений. Также в [7] используются анатомические ориентиры бронхиального дерева при видеобронхскопии (с гибким бронхоскопом) для взятия биопсии рака легкого. В них используется кодировка бронхиального дерева и на основе этого проверяется, по правильному пути ли движется бронхоскоп или нет.

Отдельно рассмотрим методы выделения бронхиального дерева. Так в статье [8] представлен алгоритм обработки изображений тонкослойной КТ для создания трехмерной модели внешних контуров бронхиального дерева человека. Алгоритм представлен в программе ImageJ-FiJi, созданной на основе языка программирования Java Script.

Для расчета кинематики бронхоскопа используют разные математические модели. В статье [9] рассматривается метод наведения бронхоскопа в оптимальные места для биопсии. Используется метод измерения движения бронхоскопа, чтобы предсказать его положение в 3D пространстве, а также для нахождения оптимального угла и глубины погружения в образование.

Алгоритмы планирования пути

На данный момент известно множество различных алгоритмов планирования пути [10–11]. Выберем самые основные алгоритмы, такие как алгоритм Дейкстры, алгоритм Флойда – Уоршелла, алгоритм Беллмана – Форда, А* и алгоритм Ли.

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

Задача планирования перемещений во многих случаях может быть достаточно эффективно решена с помощью алгоритма A* [13], в котором используется эвристика для обхода вершин и находит оптимальный маршрут от начальной вершины к целевой.

Алгоритм Флойда – Уоршелла также применяется для нахождения кратчайшего пути между всеми вершинами взвешенного ориентированного графа. Он является самым легких в реализации программы по сравнению с алгоритмами Дейкстры и Беллмана – Форда. Алгоритм Ли принадлежит семейству алгоритмов, основанных на методах поиска в ширину. Он ищет оптимальный путь и, если невозможно добраться до цели, выдает сообщение о непроходимости.

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

Для дальнейшего анализа аналогов нами были отобраны критерии их оценки.

Критерии оценки методов бронх-навигации

1. Быстродействие (Б). Критерий оценивает время работы метода. Оценка производится по трёхбалльной шкале:

soloveva01.wmf

2. Простота реализации (ПР). Критерий оценивает сложность написания алгоритма. Оценка производится по трёхбалльной шкале:

soloveva02.wmf

3. Ресурсоемкость (Р). Критерий оценивает объем памяти необходимой методу. Оценка производится по трёхбалльной шкале:

soloveva03.wmf

4. Основные характеристики (ОХ). Критерий состоит из совокупности критериев основных характеристик методов, применяемых для бронхо-навигации, таких как:

а) Реконструкция бронхов (РБ). Критерий оценивает, как реалистично и подробно выделено бронхиальное дерево. Оценка производится по двухбалльной шкале:

soloveva04.wmf

б) Степень автоматизации (СА). Критерий оценивает необходимость вмешательства оператора в работу метода. Оценка производится по двухбалльной шкале:

soloveva05.wmf

в) Анатомические особенности легких (АОЛ). Критерий показывает, учтены ли анатомические особенности легких в методе или нет. Оценка производится по двухбалльной шкале:

soloveva06.wmf

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

ОА = О(РБ)*α(РБ) + О(СА)*α(СА) + О(АОЛ)*α(АОЛ), (1)

где soloveva07.wmf αi – весовой коэффициент i-го критерия.

Таким образом, формула для оценки модели бронх-навигации имеет вид

ОА = О(Б)*α(Б) + О(ПР)*α(ПР) + О(Р)*α(Р) + О(ОХ)*α(ОХ), (2)

где soloveva08.wmf αi – весовой коэффициент i-го критерия.

Картежная модель оценки аналогов моделей бронх-навигации:

ОА(БН) = <О(Б), о(ПР), о(Р), о(ОХ), R)>, (3)

где ОА(БН) – оценка аналогов моделей бронх навигации; О(Б) – быстродействие; О(ПР) – простота реализации; О(Р) – ресурсоемкость; О(ОХ) – основные характеристики; R – матрица связи.

Критерии оценки алгоритмов планирования пути

1. Оптимальность (О). Критерий оценивает свойство алгоритма всегда находить решение с наименьшей стоимостью с учетом ограничений. Оценка производится по двухбалльной шкале:

soloveva09.wmf

2. Временная сложность (ВС). Критерий оценивает время работы алгоритма. Оценка производится по трёхбалльной шкале:

soloveva10.wmf

3. Пространственная сложность (ПС). Критерий оценивает объём памяти, необходимой алгоритму. Оценка производится по трёхбалльной шкале:

soloveva11.wmf

4. Математический подход (МП). Критерий оценивает сложность алгоритма в математической реализации. Оценка производится по двухбалльной шкале:

soloveva12.wmf

Таким образом, формула для оценки алгоритмов планирования пути имеет вид

ОА = О(О)*α(О) + О(ВС)*α(ВС) + О(ПС)*α(ПС) + О(МП)*α(МП), (3)

где soloveva13.wmf αi – весовой коэффициент i-го критерия.

Картежная модель оценки аналогов моделей бронх навигации:

ОА(АП) = <О(О), о (ВС), о (ПС), о (МП), R)>, (4)

где ОА (АП) – оценка аналогов алгоритмов планирования пути; О(О) – оптимальность; О(ВС) – временная сложность; О(ПС) – пространственная сложность; О(МП) – математический подход; R – матрица связи.

Была проведена оценка аналогов по критериям с использованием метода Томаса Саати. Итоговые оценки рассмотренных групп аналогов по критериям представлены в табл. 1–2.

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

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

Результаты исследования и их обсуждение

Для описания специфики предлагаемого решения нами был разработан пакет алгоритмической и функционально-структурной моделей.

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

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

На рис. 2 приведена функционально-структурная модель проектируемой модели первого уровня «модель навигационной карты для проведения бронхоскопии». На ней отображены входящие и исходящие данные, а также механизмы управления и функционирования системы в целом.

Таблица 1

Оценка аналогов методов бронх-навигации

Авторы

Б

ПР

Р

ОХ

α

РБ

СА

АОЛ

Интегральная оценка

0,28

0,2

0,22

0,35

1

0,4

0,35

0,25

MeVisLab

0,252

0,08

0,11

0,07

0,0245

0,009

0,5455

Wilbert G. Aguilar

0,196

0,02

0,066

0,028

0,01125

0,009

0,33025

Sanchez

0,14

0,02

0,044

0,112

0,01125

0,035

0,36225

Jason D. Gibbs

0,196

0,1

0,088

0,056

0,0225

0,0262

0,48875

D.C. Cornish

0,084

0,04

0,022

0,07

0,01125

0,009

0,23625

 

Таблица 2

Оценка аналогов алгоритмов поиска пути

Алгоритмы

О

ВС

ПС

МП

α

Интегральная оценка

0,4

0,15

0,35

0,1

1

Дейкстры

0,34

0,03

0,105

0,04

0,515

Флойда – Уоршелла

0,332

0,015

0,07

0,03

0,582

Беллмана – Форда

0,336

0,045

0,07

0,04

0,461

А*

0,36

0,075

0,14

0,02

0,595

Ли

02

0,045

0,14

0,05

0,535

Эволюционные

0,28

0,015

0,035

0,01

0,34

 

solov1.wmf

Рис. 1. Алгоритмическая модель разрабатываемой модели

solov2.tif

Рис. 2. IDEF0-модель первого уровня «модель навигационной карты для проведения бронхоскопии»

На рис. 3 представлена функционально-структурная модель проектируемой модели второго уровня «выделить интересующие объекты», иллюстрирующая основные этапы выделение интересующих объектов на КТ снимков, для дальнейшей работы с ними.

На рис. 4 представлена функционально-структурная модель проектируемой модели второго уровня «выбор ROI для забора материала», иллюстрирующая основные этапы выбора ROI для забора материала.

На рис. 5 представлена функционально-структурная модель проектируемой модели второго уровня «построить модель навигационной карты», иллюстрирующая основные этапы построения модели для навигации.

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

solov3.tif

Рис. 3. IDEF0-модель второго уровня «выделить интересующие объекты»

solov4.tif

Рис. 4. IDEF0-модель второго уровня «выбор ROI для забора материала»

solov5.tif

Рис. 5. IDEF0-модель второго уровня «построить модель навигационной карты»

Математическая модель интеллектуального агента для навигации в пространстве подробно рассмотрена во многих работах. Мы адаптировали и использовали математическую модель из работы [15].

Описание систем проектируемой модели

В результате моделирования были выделены следующие составляющие разрабатываемой модели:

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

Сначала в систему поступают первичные КТ-данные. Потом эти данные используются для построения 3D модели легких и 3D бронхиального дерева, и после система выделяет сегменты легкого.

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

3. Подсистема маршрутизации. Данная подсистема высчитывает маршрут до ROI с помощью интеллектуального агента и визуализирует его.

Выводы

В ходе работы были получены как научные, так и практические результаты:

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

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

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

4. На этапе моделирования были предложены алгоритмическая и функционально-структурная модели.

5. Были описаны подсистемы предлагаемого решения с точки зрения их технологии и функционирования на основе проведенного моделирования и его анализа.

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