Аннотация 4
1. Введение 5
1.1. Актуальность 5
1.2. Обзор литературы и ключевых работ в предметной области 6
1.2.1. Travel-time томография 6
1.2.2. Compressive Sensing 9
1.3. Предварительный пример 13
1.4. Краткий обзор результатов работы 14
1.5. Структура работы 15
2. Постановка задачи 16
3. Основной результат 17
3.1. Исследование разреженности изображения 17
3.2. Ожидания по масштабированию задачи 19
3.3. Проектирование универсальной матрицы измерений 22
3.4. Алгоритм реконструкции при использовании Compressive Sensing 24
3.5. Архитектура программного решения 24
4. Моделирование 26
4.1. Результаты эксперимента на маломасштабной модели 27
5. Заключение 30
Список литературы 31
Купить

1.1. Актуальность
Ультразвуковая томография по качеству и разрешающей способно­сти достигла сопоставимого с МРТ уровня и активно применяется для исследования мягких тканей [7]. Преимуществами УЗИ являются от­носительно низкая стоимость оборудования и обслуживания, безопас­ность для организма, неинвазивность техники исследования.
Для повышения качества и разрешающей способности получаемо­го в ходе исследования изображения требуется увеличение количества используемых датчиков и частоты дискретизации сигнала. Всё это ве­дёт к значительному увеличению объема передаваемых данных, что усложняет как производственный процесс, так и проведение диагности­ки. Кроме того особенности проведения исследования допускают нали­чие помех и искажений [28].
Опухоли преимущественно имеют более высокую скорость прохож­дения ультразвука, чем окружающие ткани. Это делает возможным ре­конструкцию плотностей тканей в исследуемой зоне с помощью урав­нений с участием предполагаемых путей распространения сигнала и временем его прибытия на датчики кругового массива (travel time tomography) [25]. Современные системы основаны именно на таком под­ходе и получили применение в диагностике рака молочных желез [26][30].
Для метода томографии travel-time типична квадратичная от числа сенсоров зависимость получаемых “сырых” данных для анализа: после­довательно с каждого датчика пускается ультразвуковой импульс, ко­торый принимают остальные к — 1 сенсоров. Это приводит к серьезному повышению требований к вычислительной части устройства томогра­фа, а также к увеличению времени обработки: современные методы реконструкции работают итеративно с временной сложностью итера­ции O(N log N) [11].
На настоящий момент использование ультразвуковой томографии осложнено высокими требованиями к вычислительному комплексу и временем на обработку [24]. Уменьшение объема данных позволит эф­фективно использовать FPGA вычислители для задач определения вре­мени прибытия сигнала на датчик и последующей реконструкции изоб­ражения. Compressive Sensing также позволит сократить время на сбор данных путем уменьшения количества производимых проекций, что ча­стично сократит зашумление данных из-за колебаний пациента в про­цессе обследования.
1.2. Обзор литературы и ключевых работ в пред­метной области
1.2.1. Travel-time томография
Техника томографии по времени прибытия сигнала уже хорошо изу­чена и освещена в работах [20], [25], [7]. В том числе рассмотрены ал­горитмы, устойчивые к присутствию шума (помех) [26]. Далеко не по­следнюю роль в реконструкции изображения играет точное определе­ние времени прибытия сигнала [4]. Общий процесс обработки данных томографии по времени прибытия показан на рис.1. Основная цель аку­стической томографии - восстановить параметры неизвестной среды, изучая характеристики распространения звука в ней. Во-первых, для этого требуется точная модель, хорошо описывающая лежащую в её основе физическую систему, и, во-вторых, высокоточные измерения. Тогда решением обратной задачи составляется оценка неизвестной мо­дели. Корректность физической модели, точность измерений и выбор метода решения обратной задачи имеют прямое влияние на качество реконструкции.
Рис. 1: Общий вид процесса ультразвуковой томографии времени прибытия.
Распространение энергии акустического сигнала в неоднородной среде хорошо описывается дифференциальным уравнением в частных про­изводных второго порядка
∇2p(r, t) - 1/F2(r) d2p(r,t)/dt2 = s(r,t),
где p(r, t) — давление в г в момент времени t, F(г) — неизвестная модель распространения скорости и s(r, — первоначальный сигнал. Зная ис­ходный сигнал s(r,t), решая обратную задачу, находим модель F(г), которая лучше всего описывает измерения p(r, ^)|q, записанные на из­вестных границах Q.
Моделирование прямой задачи по уравнению распространения вол­ны вычислительно весьма трудоемко, вследствие чего в travel-time то­мографии используются принципы геометрической акустики. При предположении, что частота звукового сигнала достаточно высока, можно найти его путь распространения используя принципы Ферма [27]. То­гда обратная задача состоит в реконструкции распределения скорости звука F(г) исходя из времени сигнала в пути, получаемое с показа­ний датчиков. Следует отметить, что в отличии от задач томографии с помощью рентгена, где сигнал распространяется по прямой, распро­странение ультразвукового сигнала в неоднородной среде происходит иначе и зависит от распределения скорости.
В то время как акустическая томография по времени прибытия сигнала берет свои корни из сейсмологии [16], на сегодняшний день уже множество исследований показало, что ультразвуковая томогра­фия имеет большой потенциал в области диагностирования рака груди [15].
Постановка обратной задачи по реконструкции изображения
Время сигнала в пути от передатчика к приемнику вдоль траекто­рии его распространения можно представить как
Y = ∫ Г 1/F(r) ds, (1)
где Y — время прибытия сигнала, Г — путь его распространения, F(г) — скорость звука в точке г. Следует заметить, что проходимый сигналом путь Г зависит от распределения скорости в среде F(г). Существует нелинейная зависимость между временем сигнала в пути и скоростью звука в среде. Можно представить уравнение (1) в дискретной форме, наложив сетку на интересующую для восстановления область с кон­стантными значениями скорости звука в клетках общим количеством N ячеек:
Y = A(F) • F, (2)
где F — вектор [Ж х 1], представляющий интересующее распределение скоростей, а A(F) — матрица Мх Ж], представляющая путь, по которо­му проходит сигнал и t — вектор М х 1], содержащий время прибытия сигнала, полученное анализом показаний с датчиков. Так, имея в уста­новке к датчиков, получаем М = к ■ [к — 1) всевозможных траекторий кратчайшего прохождения сигнала.
Целью обратной задачи является нахождения такой оценки распре­деления скоростей m, которая лучше всего описывает время прохож­дения пути сигналом в уравнении (2). Одним из традиционных алго­ритмов решения является метод LASSO с нормой 1_ и вариацией для регуляризации [26]. Тогда задача представляется как задача миними­зации
min F ||A(F) • F - YЩ + А||ФГF||j + Xn-TV(F), (3)
где Ф — некоторый базис, переводящий F в разреженное представление и A,Atv — положительные весовые коэффициенты.
Этот метод будем в дальнейшем называть исходным.
1.2.2. Compressive Sensing
С начала третьего тысячелетия объемы получаемой и обрабатывае­мой информации существенно возросли. Главным образом это связано с увеличением размерностей передаваемых сигналов (от одномерных “1-D” к дву- и трех- мерным). При этом рост данных происходит по экспоненциальному закону относительно размерности. Также в совре­менных системах происходит постоянный рост требований к частоте из­мерений (теорема Шеннона-Найквиста-Котельникова). Все это влечет необходимость сжатия данных для хранения и пересылки, стоимость суммарной обработки оказывается очень дорогостоящей [2]. Интересу­ющую информацию можно представить как х Е X, которую предстоит получить с помощью набора наблюдений у Е Y. Между х и у существу­ет закономерность явления Ф : X Y. Если Ф линейный обратимый оператор, то известно, что х = Ф-1^. Для систем реального мира более типичным является случай, когда результаты наблюдений подвержены различным помехам
y = Фx + E:
При значительных помехах задача решается статистически, используя т >> N при х G R'V. Известно, что такая задача о восстановлении х может быть решена даже в случае нецентрированных коррелирован­ных помех за счет случайного выбора матрицы Ф [19]. Установлено, что рандомизация позволяет не только устранить эффект смещения, но и уменьшить количество итераций алгоритма оценивания х [1].
На практике интересно рассмотреть возможности восстановления х Е ТЛ' при т << N, что, очевидно, невозможно в общем случае. Од­нако, оказалось, что задача может быть решена с достаточной точно­стью, при выполнении некоторых условий [17]. Подобная парадигма по­лучения и восстановления данных называется Compressive Sensing или Опознание со сжатием.
Постановка задачи о получении и восстановлении данных в общем виде выглядит следующим образом. Пусть х — интересующая информа­ция. Она проявляется себя через сигнал f = Фт. С помощью каких-либо приборов регистрации получают наблюдения у = Af. По ним исследо­вателю необходимо восстановить исходную информацию х, формируя оценки х.
Проектирование матрицы измерений
Получение т << N наблюдений можно представить как скалярное произведение с множеством некоторых векторов {a-i}™^, или умножени­ем на матрицу размерности т х N: у = Af. Тогда из постановки задачи следует у = Af = ИФт = Фт, где Ф — матрица т х N.
Необходимыми и достаточными условиями, предъявляемыми теори­ей опознания со сжатием, являются:
• сигнал f является s—разреженным:
существует такой базис Ф, что f ^2x[j]Ду', где только s коэф­фициентов x[j] / О,
• выполняется “свойство ограниченной изометрии” (Restricted
Isometry Property, RIP):
RIP(б,m) = √1-б ≤ ||Фz||2 / ||z||2 ≤ √1+б
где б E (0,1) и z — произвольный ненулевой m-разреженный век­тор,
• свойство “некогерентности” (малой взаимной зависимости) А и Ф:
u(A,Ф ) = √N max i,j |⟨ai, фj ⟩| / ∥ai∥2.
Установлено, что случайные матрицы А с высокой вероятностью некогерентны с любым фиксированным базисом Ф. Из [9] следует достаточное условие для высокой вероятности точного восстанов­ления s—разреженных векторов по m наблюдениям:
m ≥ cu(A, Ф)2 s log N, (4)
где с — некоторая положительная постоянная.
В замечании из [8] обращают внимание, что на практике часто доста­точно т ~ 4s. Также известно, что условие RIP(5, 2s) является недоста­точным для восстановления в присутствии помех или если в сжимаемом сигнале N — s компоненты малы, но не равно нулю. Для робастности же достаточным условием будет RIP(5,3s).
Явное построение матрицы измерений А: Ф = ЯФ требует проверки условия RIP для каждой комбинации положений s ненулевых компо­нент вектора z длиной N (т. е. CN). Однако, оказывается, что случай­ная матрица т х N с элементами ai,j] ~ М(0, m) имеет следующие полезные свойства [10]:
• если т > cis log N при 0 < 5 < 1, тогда
Р{А E RIP(5,m)} > 1 - 2e-c2m,
где Р — вероятность, СцС2 > 0 — малые постоянные, зависящие от 5. И тогда, следовательно, s—разреженные сигналы длины N могут быть восстановлены по т << N измерениям с высокой ве­роятностью.
• если матрица А, удовлетворяет указанным условиям, то и Ф = АФ также будет являться матрицей с независимо нормально-рас­пределенными элементами, что влечет Ф G RIP(5, rn) с той же вероятностью и для любого ортонормированного базиса Ф.
Для использования опознания со сжатием помимо проектирования матрицы измерений А требуется разработать алгоритм реконструк­ции сигнала, задачей которого восстановить по у Е Rm, матрице изме­рений А и базису Ф сигнал f Е RN, или эквивалентное ему спектральное разреженное представление х.
При т < N для s-разреженных сигналов имеется бесконечное число х' : Фх' = у, т. к. если Фх = у Ф(Х + г) = у для любого г Е Ker Ф. Таким образом, алгоритм реконструкции должен найти вектор разре­женного представления сигнала в (N — т)-размерном подпространстве Р = Ker Ф + х.
Методы решения обратной задачи
Традиционным подходом в решении подобных обратных задач яв­ляется поиск в Р вектора с минимальной энергией (нормой) А:
х^ = argmin ||x'||2 : Фx' = y,
или, что тоже самое, в форме метода наименьших квадратов
х^ = ФТ (Ффt)-1 y.
Поскольку О норма отражает энергию сигнала, а не разреженность, ре­зультат будет содержать много ненулевых компонент. С задачей поиска разреженного решения хорошо справляется “1о_норма”. Однако, задача 10 оптимизации невыпукла и относится к комбинаторному типу, проце­дуры ее решения, в общем случае, NP-сложные [23]. Существует два подхода для приближенного решения таких задач: “жадные” стратегии оптимизации [22] или переход к Д-норме. Хорошо известно, что мини­мизация li нормы способствует разреженности [18] и позволяет хоро­шо приближать разреженные сигналы используя только т > щ s log N случайных измерений [17][10]. Это задача выпуклой оптимизации, сво­димая к известной задаче линейного программирования “выбор базиса” (Basis Pursuit Denoising) [12], эффективные методы решения которого имеют временную сложность O(N log N/s) [5].
Техника обработки сигналов Compressive Sensing может быть ис­пользована для решения проблемы передачи и обработки большого количества информации с массива датчиков. Этот метод уже успеш­но применяется в магнитно-резонансной томографии [21, 13], а также в ультразвуковых исследованиях [14]. Однако, данные, используемые для получения изображения в ультразвуковой томографии имеют иную природу, чем в классическом (B-mode) ультразвуковом исследовании, так как после замера сигнала из него извлекается время прибытия зву­ковой волны, с которой и происходит вся дальнейшая работа по ре­конструкции снимка. Также этот факт отличает ультразвуковую то­мографию от МРТ, где все необходимые для реконструкции данные получают уже в разреженном представлении.
1.3. Предварительный пример
В целях получения наилучшего изображения требуется большое ко­личество датчиков и высокая частота дискретизации сигнала. Всё это ведёт к необходимости обработки серьезного объема данных. Оценить количество данных, поступающих непосредственно с датчиков можно:
V = k2zYmsx v,
где V — общее число измерений сигнала, к — количество датчиков, z — количество исследуемых срезов, Ymax — время прохождения сигнала с учетом затухания эха, и — частота дискретизации.
Примером современного коммерческого ультразвукового томографа является The SoftVue [6], который имеет следующие технические харак­теристики системы:
• Мастер сервер: 2 процессора quad-core Intel Xeon E5620, 192 ГБ ОЗУ
• Сервер реконструкции: 2 процессора quad-core Intel Xeon E5620, 96 ГБ ОЗУ, 2 ГП Nvidia Tesla M2070
Таблица 1: Объем исходных данных ГБ за один срез в зависимости от числа дат­чиков в массиве и частоты дискретизации сигнала [6].
Частота дискретизации (МГц)
Число датчиков
-
256
512
1024
10
0.21
0.86
3.44
12
0.26
1.03
4.13
14
0.30
1.20
4.81
Конец таблицы 1.
Так в таблице 1 производители описали количество данных, полу­чаемых с датчиков за один срез. На обработку такого среза при исполь­зовании только одного сервера для реконструкции требуется несколь­ко минут, а при использовании всего вычислительного комплекса - 20 секунд. Всего производится 70 срезов [6]. Таким образом время, за­трачиваемое только лишь на вычисление томографических снимков, составляет приблизительно 23 минуты.
1.4. Краткий обзор результатов работы
В ходе выполнения работы был разработан метод, позволяющий при разработке ультразвукового томографа внедрить в применяемые алго­ритмы по сбору и обработке данных парадигмы опознания со сжатием. Эксперименты, проведенные на компьютерных моделях, показали со­стоятельность метода. В частности, даже в маломасштабной модели оказалось возможным сокращение используемых данных до 68% от об­щего их объема.
1.5. Структура работы
Сначала в разделе 3 проверяется и демонстрируется факт разрежен­ности восстанавливаемого сигнала, для чего было найдено подходящее трансформирующее кодирование. После чего рассматриваются различ­ные варианты построения рандомизированной матрицы измерений, а также процесс реконструкции и архитектура программного решения. Далее приведены оценки необходимого для реконструкции объема дан­ных при дальнейшем увеличении числа датчиков и разрешения снимка. Раздел 4 описывает проведенные эксперименты, где также анализиру­ются полученные результаты. Наконец, подведение итогов проделанной работы происходит в разделе 5.
Купить