Научный журнал
Современные наукоемкие технологии
ISSN 1812-7320
"Перечень" ВАК
ИФ РИНЦ = 0,940

АНАЛИЗ ВЫЧИСЛИТЕЛЬНОЙ СЛОЖНОСТИ АЛГОРИТМОВ ВЫДЕЛЕНИЯ ОБЛАСТЕЙ ИНТЕРЕСА ПО ДАННЫМ МРТ

Шустова М.В. 1
1 Институт программных систем им. А.К. Айламазяна РАН
На сегодняшний день клеточная терапия является одним из актуальных направлений в регенеративной медицине, а применение магнитно-резонансной томографии является одним из основных способов проведения фундаментальных биомедицинских исследований. Анализ данных магнитно-резонансной томографии дает возможность изучения областей интереса и динамики их изменения. Комбинирование современных методов магнитно-резонансной томографии и методов научной визуализации позволяет строить карты миграции и распространения стволовых клеток после их трансплантации, что дает толчок к пониманию механизмов их действия на очаги заболевания, например, при ишемическом инсульте головного мозга. Однако получаемые большие объемы информации с томографа замедляют скорость их интерпретации врачами при проведении клинических и научных исследований. Для повышения эффективности информационной поддержки врача-исследователя были разработаны методы и программные средства автоматического выделения и визуализации областей интереса (скоплений мезенхимальных стволовых клеток и зон ишемического поражения) на снимках магнитно-резонансной томографии. В настоящей работе приведены описания разработанных алгоритмов на языке псевдокодов. Представленные методы и программные средства предназначены для включения в систему информационной поддержки работы врачей-исследователей. Даны оценки их вычислительной сложности. Выполнен экспериментальный анализ быстродействия разработанных алгоритмов.
обработка изображения
вычислительная сложность
магнитно-резонансная томография
мезенхимальные стволовые клетки
ишемический инсульт
алгоритмы
оценки временной сложности
1. Лызиков А.Н., Осипов Б.Б., Скуратов А.Г., Призенцов А.А. Стволовые клетки в регенеративной медицине: достижения и перспективы // Проблемы здоровья и экологии. 2015. № 3. C. 4–8.
2. Lin K., Chai H., Chen K. et al. Intra-carotid arterial transfusion of circulatory-derived autologous endothelial progenitor cells in rodent after ischemic stroke–evaluating the impact of therapeutic time points on prognostic outcomes. Stem Cell Research & Therapy. 2020. Vol. 11. no. 219. DOI: 10.1186/s13287-020-01739-y.
3. Matthew K. Tobin et al. Activated Mesenchymal Stem Cells Induce Recovery Following Stroke Via Regulation of Inflammation and Oligodendrogenesis. Journal of the American Heart Association. 2020. Vol. 9. no 7. DOI: 10.1161/JAHA.119.013583.
4. Фраленко В.П., Хачумов М.В., Шустова М.В. Анализ инструментальных средств обработки и визуализации биомедицинских данных магнитно-резонансной томографии (обзор литературы) // Вестник новых медицинских технологий. 2016. № 4. С. 307–315. DOI: 10.12737/23880.
5. Фраленко В.П., Хачумов М.В., Шустова М.В. Выделение и когнитивная визуализация трансплантированных мезенхимальных стволовых клеток на снимках магнитно-резонансной томографии // Искусственный интеллект и принятие решений. 2017. № 3. С. 10–20.
6. Фраленко В.П., Хачумов М.В., Шустова М.В. Инструментальные средства автоматического поиска и визуализации зон интереса в данных МРТ для поддержки принятия решений врачей-исследователей // Искусственный интеллект и принятие решений. 2016. № 4. С. 27–37.
7. Abbadi N.K., Dahir N.S., Alkareem Z.A. Skin texture recognition using neural networks. Proc. Int’l Arab Conf. on Information Technology. 2008. P. 1–4.
8. Haralick R.M., Shanmugam K., Dinstein I. Textural features for image classification. IEEE Transactions on Systems, Man and Cybernetics. 1973. Vol. 3. P. 610–621.
9. Амелькин С.А., Захаров А.В., Хачумов В.М. Обобщенное расстояние Евклида – Махаланобиса и его свойства // Информационные технологии и вычислительные системы. 2006. № 4. С. 40–44.

Одним из современных направлений исследований в области биомедицины является изучение влияния трансплантированных мезенхимальных стволовых клеток (МСК) на очаги ишемического инсульта, поскольку трансплантированные МСК являются эффективными терапевтическими агентами [1–3]. На данный момент остается до конца не исследованным механизм поведения и взаимодействия стволовых клеток с локальным микроокружением. Автоматизация анализа данных магнитно-резонансной томографии (МРТ) за счет методов научной визуализации предоставит возможность отслеживания МСК после трансплантации и построения карт их миграции, что является крайне важным для понимания механизмов воздействия МСК на очаги ишемического инсульта.

За последние несколько лет в мире было разработано большое количество профессиональных систем и различных программных средств обработки и визуализации данных МРТ. Практически все медицинские программы имеют открытые исходные коды для анализа и обработки изображений и распространяются без лицензионных ограничений. Однако при ближайшем рассмотрении оказывается, что имеющихся программных средств недостаточно для решения конкретных специализированных задач, в частности прижизненной визуализации трансплантированных МСК в головном мозге реципиентов в условиях ишемического инсульта [4]. Для реализации автоматического выделения скоплений МСК и зон ишемического поражения были разработаны (с участием автора) соответствующие методы и алгоритмы. Настоящая работа посвящена подробному описанию этих алгоритмов и оценке их вычислительной сложности.

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

Анализ алгоритма выделения мезенхимальных стволовых клеток

Разработанный алгоритм выделения скоплений МСК построен на одновременной обработке пары снимков МРТ (до введения МСК и после введения) и состоит из нескольких шагов [5]:

1) волновой алгоритм;

2) фильтрация по яркости;

3) удаление неинформативных объектов;

4) обработка T раз с разными наборами параметров.

Определим вычислительную сложность каждого шага алгоритма. Сложность волнового алгоритма известна и составляет O(MN) для матрицы размером M×N.

Фильтрация изображения по яркости размером M×N происходит по следующему правилу: рассматривается каждый пиксель изображения, и если яркость пикселя превышает заданный порог, то он удаляется. Для этого шага требуется O(MN) операций.

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

1. Выполняется маркировка оставшихся после предыдущих шагов объектов (рис. 1). Для обработки одного изображения размером M×N требуется O(MN) операций.

hustov1.tif

Рис. 1. Алгоритм маркировки объектов

2. После маркировки выполняется подсчет площади (количества пикселей) у каждого объекта. Количество требуемых операций – O(MN).

hustov2.tif

Рис. 2. Алгоритм фильтраций

3. Далее последовательно выполняются несколько фильтраций (рис. 2):

- фильтрация по количеству пикселей у объектов;

- удаление неравномерно пересекающихся объектов;

- фильтрация окном круглой формы.

Этот шаг выполняется не больше чем mCounterAfter раз, а поскольку mCounterAfter < M×N, то эта часть шага ограничена сверху O(MN) операциями.

Для улучшения показателей точности и полноты МРТ-снимок обрабатывается T раз с разными наборами параметров – соответственно, получается T масок. После этого выполняется дополнительная фильтрация: полученные изображения накладываются друг на друга и попиксельно считываются. Если рассматриваемый пиксель равен 255 как минимум на 80 % масок, то данный пиксель включается в результирующую маску. Требуемое количество операций: O(MN).

Анализ алгоритма выделения зоны ишемического поражения

Разработанный алгоритм выделения зоны ишемического поражения состоит из двух шагов [6]:

1) вычисление характерных признаков;

2) анализ полученных признаков с применением классификатора.

Для обработки изображений требуется определить два класса – в нашем случае это область здорового мозга («норма», класс Y1) и область ишемического поражения («поражение», класс Y2). Каждая область представляется набором небольших эталонных изображений одного из срезов мозга. Из этих изображений извлекаются признаки, необходимые для настройки классификатора.

Определим вычислительную сложность каждого шага алгоритма.

На первом шаге вычисляются характерные признаки. Всего задействовано три признака общего назначения и четыре текстурных признака Харалика. Признаки общего назначения вычисляются по следующим формулам [7]:

- математическое ожидание μ:

hustov01.wmf,

- стандартное отклонение:

hustov02.wmf,

- асимметричность уровня серого:

hustov03.wmf,

где M и N – размеры сканирующего окна, pij – значение яркости пикселя в i-й строке и j-м столбце сканирующего окна. Признаки общего назначения извлекаются отдельно для каждого канала RGB – таким образом, всего извлекается девять общих признаков.

Основные текстурные признаки Харалика вычисляются следующим образом [8]:

- энтропия: hustov04.wmf

- энергия: hustov05.wmf

- контраст: hustov06.wmf

- гомогенность: hustov07.wmf

где Co(i, j) – элемент матрицы смежности уровня серого (Gray-Level Co-occurrence Matrix) в i-й строке j-го столбца.

Алгоритм извлечения характерных признаков представлен на рис. 3, а. Этот этап алгоритма выделения ишемического поражения построен на обработке изображения размером M×N с помощью сканирующего окна, следовательно, он ограничен сверху O(MN) операциями.

hustov3a.tif

а) извлечение характерных признаков

hustov3b.tif

б) анализ извлеченных признаков

Рис. 3. Алгоритм извлечения признаков и их анализа с помощью классификатора на основе расстояния Евклида – Махаланобиса

На втором шаге для работы с перечисленными признаками применяется классификатор, использующий расстояние Евклида – Махаланобиса [9]. Расстояние между классом Y (например, классом «ишемическое повреждение») и точкой p (точка – вектор признаков, извлеченных из некоторой позиции сканирующего окна) вычисляется по формуле hustov08.wmf, где матрица hustov09.wmf. Ковариационная матрица CY для класса Y вычисляется по формуле

hustov10.wmf,

где hustov11.wmf – i-й признак k-й точки из класса Y, а hustov12.wmf – математическое ожидание значения этого признака в классе Y.

На рис. 3, б, приведен алгоритм анализа извлеченных признаков с помощью классификатора.

Этот этап алгоритма выделения ишемического поражения выполняется в том же цикле, что и предыдущий этап, следовательно, он также ограничен сверху O(MN) операциями.

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

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

Анализ алгоритма выделения МСК

Алгоритм выделения МСК построен на одновременной обработке пары изображений, поэтому в качестве входных дан- ных использовались два снимка МРТ в разных разрешениях: от 64x44 пикселей до 512x352 пикселей. Для получения среднего времени обработки снимки обрабатывались 1000 раз. Программная реализация алгоритма запускалась на компьютере со следующей конфигурацией: Intel Core i3-8100 3.60 GHz, 16 GB RAM. В табл. 1 и рис. 4 приведены данные измерений времени работы алгоритма и аппроксимированные значения оценки.

hustov4.wmf

Рис. 4. Графики роста (скорость работы алгоритма выделения МСК)

Таблица 1

Экспериментальные данные измерения времени работы алгоритма выделения МСК

Разрешение, px

Площадь, px

Масштаб, %

Среднее время, мс

Аппроксимированное значение оценки, мс

64x44

2816

100

187,093

175,2634

96x66

6336

225

332,48

280,8634

128x88

11264

400

371,381

428,7034

160x110

17600

625

474,037

618,7834

192x132

25344

900

656,502

851,1034

224x154

34496

1225

861,543

1125,6634

256x176

45056

1600

1114,689

1442,4634

288x198

57024

2025

1493,989

1801,5034

320x220

70400

2500

1962,928

2202,7834

352x242

85184

3025

2441,073

2646,3034

384x264

101376

3600

2635,321

3132,0634

416x286

118976

4225

3178,921

3660,0634

448x308

137984

4900

3790,305

4230,3034

480x330

158400

5625

4536,728

4842,7834

512x352

180224

6400

5386,007

5497,5034

Анализ алгоритма выделения зон ишемического поражения

В качестве входных данных использовался снимок МРТ в разных разрешениях: от 64x45 пикселей до 512x360 пикселей. Для получения среднего времени обработки снимки обрабатывались 1000 раз. Программная реализация алгоритма запускалась на компьютере со следующей конфигурацией: Intel Core i3-8100 3.60 GHz, 16 GB RAM. В табл. 2 и рис. 5 приведены данные измерений времени работы алгоритма и аппроксимированные значения оценки.

Таблица 2

Экспериментальные данные измерения времени работы алгоритма выделения зон ишемического поражения

Разрешение, px

Площадь, px

Масштаб, %

Среднее время, мс

Аппроксимированное значение оценки, мс

64x45

2880

100

37,706

43,2

96x68

6528

226,7

89,931

97,92

128x90

11520

400

161,107

172,8

160x113

18080

627,8

256,721

271,2

192x135

25920

900

373,501

388,8

224x158

35392

1228,9

513,973

530,88

256x180

46080

1600

674,432

691,2

288x203

58464

2030

856,569

876,96

320x225

72000

2500

1058,62

1080

352x248

87296

3031,1

1280,49

1309,44

384x270

103680

3600

1532,801

1555,2

416x293

121888

4232,2

1806,694

1828,32

448x315

141120

4900

2095,11

2116,8

480x338

162240

5633,3

2413,322

2433,6

512x360

184320

6400

2746,128

2764,8

Из рис. 4 и 5 видно, что подбором уточняющих коэффициентов удается достаточно точно приблизить теоретические оценки к экспериментальным результатам.

hustov5.wmf

Рис. 5. Графики роста (скорость работы алгоритма выделения зон ишемического поражения)

Заключение

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

Исследование выполнено при финансовой поддержке РФФИ в рамках научного проекта № 17-29-07002-офи_м.


Библиографическая ссылка

Шустова М.В. АНАЛИЗ ВЫЧИСЛИТЕЛЬНОЙ СЛОЖНОСТИ АЛГОРИТМОВ ВЫДЕЛЕНИЯ ОБЛАСТЕЙ ИНТЕРЕСА ПО ДАННЫМ МРТ // Современные наукоемкие технологии. – 2020. – № 8. – С. 90-96;
URL: https://top-technologies.ru/ru/article/view?id=38179 (дата обращения: 29.03.2024).

Предлагаем вашему вниманию журналы, издающиеся в издательстве «Академия Естествознания»
(Высокий импакт-фактор РИНЦ, тематика журналов охватывает все научные направления)

«Фундаментальные исследования» список ВАК ИФ РИНЦ = 1,674