Обработка и передача изображений fast 3d object model reconstruction algorithm by stereo pair

ИССЛЕДОВАНИЕ ИСПОЛЬЗОВАНИЯ ГРАФИЧЕСКИХ ПРОЦЕССОРОВ ДЛЯ РЕШЕНИЯ НЕГРАФИЧЕСКИХ ЗАДАЧ
Кириленко¹ А.Н., Грызов² Г.Ю., Чобану² М.К.
¹ГОУВПО МЭИ (ТУ), ²ФГУП «ГРЧЦ», Москва
Термин GPU (Graphics Processing Unit) был впервые использован компанией nVidia для обозначения того, что графический ускоритель, первоначально используемый только для ускорения трёхмерной графики, стал мощным программируемым устройством, пригодным для решения широкого класса задач, не всегда связанных с графикой. Современные GPU представляют собой массивно-параллельные вычислительные устройства с очень высоким быстродействием (свыше терафлопса) и большим объёмом собственной памяти (DRAM) (см. Рис. 1).



Рис. 1. Сравнение пиковой производительности систем на CPU и GPU
В результате возникло такое направление, как GPGPU (General-Purpose computing on Graphics Processing Units) – использование графических процессоров для решения неграфических задач [1]. За счёт использования высокой степени параллелизма удалось повысить производительность распараллеливаемых задач. Для организации вычислений использовался один из распространённых графических API (OpenGL или Direct3D). Используя такой API, подготавливались текстуры, содержащие необходимые входные данные, и через операцию рендеринга (чаще всего прямоугольника) на графическом процессоре запускалась программа обработки этих данных. Результат получался также в виде текстур, которые потом считывались в память центрального процессора (CPU).

Фактически программа писалась сразу на двух языках – на традиционном языке программирования, например C++, и на языке для написания шейдеров. Часть программы отвечала за подготовку и передачу данных, а также за запуск на GPU программ, написанных на шейдерных языках.

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

Ещё одним ограничением, свойственным графическим API, является отсутствие поддержки операции типа scatter. Простейшим примером такой операции является построение гистограмм по входным данным, когда очередной элемент входных данных приводит к изменению заранее неизвестного элемента (или элементов) гистограммы. Это связано с тем, что в графических API шейдер может осуществлять запись лишь в заранее определённое место, поскольку для фрагментарного шейдера заранее определяется какой фрагмент он будет обрабатывать, и он может записать только значение для данного фрагмента.

Все эти обстоятельства усложняют использование GPGPU и накладывают серьёзные ограничения на используемые алгоритмы. Поэтому вполне естественно возникла потребность в средствах разработки GPGPU-приложений, свободных от этих ограничений и ориентированных на решение сложных вычислительных задач. В качестве таких средств выступают CUDA, OpenCL и DX11 Compute Shaders.

Предложенная компанией nVidia технология CUDA (Compute Unified Device Architecture) заметно облегчает написание GPGPU-приложений. CUDA не использует графических API и свободна от ограничений свойственных им. Данная технология предназначена для разработки приложений для массивно-параллельных вычислительных устройств. Основным приемуществами технологии CUDA являются её простота – все программы пишутся на «расширенном» языке C, наличие хорошей документации, набор готовых библиотек, кроссплатформенность. CUDA является полностью бесплатной; SDK, документацию и примеры можно скачать с сайта nVidia.

CUDA строится на концепции, что GPU (называемый устройством, device) выступает в роли массивно-параллельного сопроцессора к CPU (называемому host). Программа на CUDA использует как CPU, так и GPU. При этом обычный (последовательный) код выполняется на CPU, а для массивно-параллельных вычислений код выполняется на GPU как набор одновременно выполняющихся нитей (потоков, threads). Таким образом, GPU рассматривается как специализированное вычислительное устройство, которое является сопроцессором к CPU, обладает собственной памятью и возможностью параллельного выполнения огромного количества отдельных потоков. Между потоками CPU и GPU существуют принципиальные различия. Потоки GPU обладают крайне небольшой стоимостью создания, управления и уничтожения (контекст нити минимален, все регистры распределены заранее), для эффективной загрузки GPU необходимо использовать много тысяч потоков, в то время как для CPU обычно использует 10-20 потоков. За счёт того, что программы в CUDA пишутся фактически на обычном языке C (на самом деле для частей, выполняющихся на CPU, можно использовать C++), в который добавлены новые конструкции (спецификаторы типа, встроенные переменные и типы, директива запуска ядра), написание программ с использованием технологии CUDA оказывается заметно проще, чем при использовании графического API.

Реализация и сравнение видеокодеров H.264. Сравнение результатов сжатия видео с настройками кодеров с GPU и без него по умолчанию приведены ниже в табл. 1. Наилучший результат, которого удалось добиться – увеличение производительности на 54% для FullHD 1080p. Эти результаты были получены на РС с мощным CPU и GPU с 14 MP.

Таблица 1. Результаты тестирования кодера Н264 на РС с конфигурацией: Intel Core i7 2.8GHz (4-Core CPU, 8 Threads), 4Gb; 9800GT 1.5GHz 1Gb (14MP).

Видео	Разрешение	H.264 CPU, fps	H.264 GPU (CUDA), fps	Прирост производительности, %
Akiyo	CIF	274.7	274.7	0
Football	CIF	200.8	277.8	38
Mobile	CIF	221.1	249.8	13
Paris	CIF	239.5	256.6	7
Crew	4CIF	109.2	105.7	-3
Stockholm	720p	53	78	47
Station	1080p	26	40	54

Разработчики софта для сжатия видео с GPU отмечают, что для того, чтобы получить ощутимую прибавку в производительности, надо производить сжатие видео формата не ниже 720p на машине с мощными как CPU, так и GPU. Отсюда следует, что применение GPU целесообразно для видео высокого разрешения. Действительно, для сжатия видео небольшого разрешения вполне можно использовать кодеры без применения GPU.

Наличие B-кадров в настройках кодера CPU приводит к снижению производительности, нетипично большая область поиска макроблоков для межкадровой компенсации движения, также приводит к снижению производительности, обычно это значение гораздо меньше, в популярной реализации кодера стандарта H.264 x264 значение по умолчанию для этого параметра 16. Наибольшее значение этого параметра для кодера с CUDA не так критично. Для GPU задачи такого плана являются типичными, так как легко распараллеливаются.

При использовании мощных ПК можно сжимать в реальном времени видео с разрешением до 720p. Стоит отметить, что кодер с использованием GPU с включёнными B-кадрами на мощных РС всегда работает быстрее, чем с выключенными B-кадрами. Из табл. 2 видно, что качество декодированного видео при использовании B-кадров зачастую падает.

Таблица 2. Сравнение качества декодированного видео сжатого разными кодерами.

Видео	Битрейт, Кбит/с	X264 PSNR, dB	CPU PSNR, dB	GPU PSNR, dB	GPU with B-frames PSNR , dB
Akiyo	500	48.13	48.13	48.13	48.13
Football	500	31.23	30.07	28.63	28.00
Mobile	500	29.81	29.04	26.82	27.52
Paris	500	38.13	37.34	35.83	36.37
City	1000	34.51	33.82	31.80	31.50
Crew	1000	35.34	34.15	32.00	31.60
Ice	1000	41.14	40.35	39.10	39.10
Stockholm	2000	36.09	34.51	30.73	30.81

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

Литература

1. 
   Чобану М. Многомерные многоскоростные системы обработки сигналов. М.: ТЕХНОСФЕРА, 2009, 480 с.
   

INVESTIGATION OF GRAPHICAL PROCESSING UNITS USING FOR SOLVING OF NON-GRAPHICAL TASKS

Kirilenko¹ А., Gryzov² G., Tchobanou² М.

¹MPEI (TU), ²GRFC, Moscow
The results of GPU application for H.264-based video coding are given. The comparison with CPU-based video coding implementation is presented. It is shown, that the improvement in calculations speed and reconstructed video quality is not so impressive as it was expected.



НАХОЖДЕНИЕ ДВИЖЕНИЯ СТЕНКИ ЛЕВОГО ЖЕЛУДОЧКА СЕРДЦА ПО ВИДЕОДАННЫМ МРТ И УЗИ
Ятченко А.М.¹, Крылов А.С.¹, Гаврилов А.В.², Архипов И.В.^3
1МГУ имени М.В. Ломоносова, факультет вычислительной математики и кибернетики,

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

²МГУ имени М.В. Ломоносова, научно-исследовательский институт ядерной физики

имени Д.В. Скобельцына,

³Российский Научный Центр Хирургии им. Петровского.
Разработан итерационный метод определения скоростей движения стенок левого желудочка по видеоданным Магнитно-Резонансной Томографии (МРТ) и Ультразвукового исследования (УЗИ). Нормальные составляющие скоростей вычисляются по МРТ снимкам, тангенциальные составляющие - по УЗИ снимкам.
1. Введение

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

В задаче отслеживания движения границы стенки левого желудочка, на МРТ снимках намного четче видна стенка желудочка, чем на УЗИ снимках, что позволяет качественнее определить нормальные составляющие скоростей стенки желудочка. Однако УЗИ изображения имеют обычно более высокое разрешение и скорость кадров. На МРТ снимках также прослеживается поток крови внутри сердца. Это дает как преимущества, так и недостатки. К преимуществам можно отнести то, что знание потоков крови внутри сердца может помочь в диагностике сердечной функции. К недостаткам относится тот факт, что потоки крови мешают отслеживанию тангенциальных скоростей движения стенок желудочка. При отслеживании точек на границе желудочка, алгоритмы цепляются за движущуюся текстуру крови, которая часто не совпадает с движением стенки желудочка.

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

Цель данной работы состоит в улучшении качества отслеживания границы желудочка, используя обе модальности МРТ для определения нормальных составляющих и УЗИ для определения тангенциальных составляющих скоростей. Так же стоит заметить, что звуковые волны, в виду своей низкой амплитуды и высокой частоты не влияют на МРТ сканирование. Так же, электромагнитный сигнал МРТ не интерферирует с ультразвуковым датчиком [1]. Таким образом, эти модальности могут сниматься одновременно, без заметного влияния друг на друга [2], [3] и предложенный в данной статье алгоритм может использоваться более эффективно.

2. Слежение за контуром на одной модальности

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

Общая схема предлагаемого нами алгоритма состоит в следующем: сначала исследователь вручную обводит границу желудочка на некоторых ключевых кадрах видеопоследовательности. Затем на остальных кадрах контур желудочка вычисляется автоматически. Для прослеживания перемещения контура от кадра к кадру используется алгоритм Канаде-Лукаса [5]. На каждом интервале между двумя ключевыми кадрами, прослеживание стенки проходит сначала в одном направлении, опираясь на один ключевой кадр, затем в обратном по времени направлении, опираясь на второй ключевой кадр. Итоговый контур получается как усреднение этих двух проходов. Исследователь может повышать качество результата добавлением новых ключевых кадров. Такое прослеживание используется и для МРТ и для УЗИ.

Алгоритм Канаде-Лукаса является градиентным методом, потому он плохо определяет тангенциальные скорости движения стенки.

Для их отслеживания используется слежение за текстурой на УЗИ последовательности. Для определения тангенциальных скоростей используется алгоритм сопоставления блоков размера 15x15.

3. Синхронизация фаз разных модальностей

Изначально УЗИ и МРТ серии могут быть несинхронизированными по времени. К тому же серии могут сниматься с разной частотой кадров.

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

В нашем методе мы используем объем левого желудочка для автоматической синхронизации сердечных циклов МРТ и УЗИ. На каждом кадре МРТ и УЗИ серий нормализованный объем сегментированного желудочка определяется его площадью (рисунок 1a). Затем подбирается смещение фазы для МРТ серии, при котором минимизируется сумма квадратов отклонений объемов на цикле. Контуры на МРТ снимках пересчитываются с учетом сдвига фазы и с изменением частоты кадров до частоты кадров УЗИ (рисунок 1b).



Рис. 1. a) нормированные объемы УЗИ(US) и МРТ(MRI), b) синхронизированные сердечные циклы
4. Объединение модальностей. Сопоставление точек.

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

Пусть есть наборы точек и . Будем искать аффинную матрицу подобия , которая минимизирует сумму квадратов расстояний между точками x и m - , где матрица R – матрица поворота и масштабирования , t – вектор параллельного переноса. Решение ищется в явном виде:





Полученное отображение (обозначим его или ) минимизирует расстояния между точками в наборах [6].

5. Совмещение контуров

Поскольку движение точек на контуре МРТ может не соответствовать движениям стенки, то алгоритм сопоставления точек, описанный в разделе 4 будет давать большие погрешности (рисунок 2a). Если переразбить каждый контур МРТ так, чтоб точки на контурах лежали равномерно, то алгоритм сопоставления контуров будет работать лучше (рисунок 2b). Тем не менее, ввиду сложного строения сердечной мышцы, различные участки стенки могут двигаться в разные стоны, поэтому равномерное разбиение контуров также дает большую погрешность.

Для сопоставления контуров нами применяется итеративный алгоритм. Контуры X и M заданны набором точек и (сами контуры апроксимируются сплайнами). Ищется соответствие точек контуров.

Пусть оператор - оператор проектирования на контур М (ищется ближайшая к x точка m на всем контуре M, а не только среди точек ).

Для сопоставления контуров ищется оператор T, минимизирующий расстояния от точек до контура M.

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

На k-й итерации точки проектируются на кривую M: , . Новый оператор соответствия находится как оператор сопоставления наборов точек X и Y: .

При этом сумма расстояний от точек до кривой M будет уменьшаться на каждом шаге (пример работы алгоритма на рисунке 2c).