Курсовая работа на тему: "Реализация алгоритма Stereo Block Matching на архитектуре SIMD и VLIW"
У нас на сайте представлено огромное количество информации, которая сможет помочь Вам в написании необходимой учебной работы.
Но если вдруг:
Вам нужна качественная учебная работа (контрольная, реферат, курсовая, дипломная, отчет по практике, перевод, эссе, РГР, ВКР, диссертация, шпоры...) с проверкой на плагиат (с высоким % оригинальности) выполненная в самые короткие сроки, с гарантией и бесплатными доработками до самой сдачи/защиты - ОБРАЩАЙТЕСЬ!
Курсовая работа на тему:
"Реализация алгоритма Stereo Block Matching на архитектуре SIMD и VLIW"
Оглавление
Введение 3
1. Постановка задачи 4
2. Обзор 5
2.1. Описание алгоритма . . . . . . . . . . . . . . . . . . . . . 5
2.2. Архитектура процессора . . . . . . . . . . . . . . . . . . . 6
2.3. Обзор существующих решений . . . . . . . . . . . . . . . 7
3. Реализация 9
3.1. Инструменты . . . . . . . . . . . . . . . . . . . . . . . . . . 9
3.2. Скорость алгоритма и использование памяти . . . . . . . 9
3.3. Описание работы алгоритма . . . . . . . . . . . . . . . . . 11
3.4. Векторизация . . . . . . . . . . . . . . . . . . . . . . . . . 11
3.5. Переход от int16 к short32 . . . . . . . . . . . . . . . . . . 13
4. Результаты 14
Заключение 15
Введение
Построение карты диспаритетов (disparity map) по стереопаре яв- ляется важной задачей компьютерного зрения. Это - процесс преобра- зования двух изображений с восстановлением информации о расстоя- нии от точек сцены до картинной плоскости. Карта диспаритетов со- держит данную информацию в качестве интенсивности пикселя (рис. 1). Большее значение интенсивности означает меньшее значение рас- стояния до картинной плоскости. Карта диспаритетов применяется в восстановлении 3D-модели объекта по нескольким его фотографи- ям, снятым с разных ракурсов; для выделения фона на изображениях; склейки панорам.
Основные методы решения данной задачи разделяются на глобаль- ные и локальные [10]. Глобальные выигрывают в качестве у локальных, но проигрывают им в скорости. Некоторые алгоритмы компьютерного зрения могут быть реализованы эффективно на специализированном оборудовании - видеокартах или цифровых сигналных процессорах.
Одной из архитектур является линейка процессоров EV6x [3], произ- веденная компанией Synopsys. Ускорение происходит за счет совмещен- ной архитектуры SIMD [7] (Single Instruction Multiple Data) и VLIW [4] (Very Long Instruction Word). На данном процессоре реализован алго- ритм построения карты диспаритетов Semi-Global Matching [6]. Он восстанавливает карту диспаритетов, обладающую хорошим качеством, но его скорость недостаточна. Необходим алгоритм с более высокой ско- ростью.
В рамках данной курсовой работы рассматривается Stereo Block Matching [2]. Целью данной работы является его реализация на архи- тектуре процессора EV6x.
Рис. 1: Карта диспаритетов, соответствующая стереопаре
1. Постановка задачи
Целью данной работы является реализация алгоритма Stereo Block Matching для архитектуры процессора EV6x.
Для достижения цели были поставлены следующие задачи:
• Изучение:
– Алгоритмов стереозрения;
– Алгоритма Stereo Block Matching;
– Архитектуры процессора EV6x;
• Определение наилучшей асимптотики алгоритма;
• Построение алгоритма для данной архитектуры;
• Улучшение алгоритма;
• Реализация алгоритма.
2. Обзор
2.1. Описание алгоритма
Входом являются два изображения одной сцены c двух камер с раз- ных точек обзора в конкретный момент времени.
Для корректной работы алгоритма изображения выравнивают так, чтобы для каждой точки соответствующая ей парная точка находилась в той-же строке на изображении со второй камеры. Данный процесс выравнивания изображений называют ректификацией.
Для каждого пикселя левого изображения выполняется поиск со- ответствующего пикселя на правом изображении. Если пиксель левого изображения имеет координаты (x0, y0), то соответствующий ему пик- сель правого изображения будет иметь координаты (x0 − d, y0), где d
— величина, называемая смещением (disparity). Для каждого d от ну- ля до максимального значения смещения выделяются два квадратных блока одинакового размера (рис. 2), центрами которых являются со- ответствующие пиксели. Далее для блоков вычисляется метрика SAD (Sum of absolute differences).
s
s
sady,x,d = ∑ ∑ |Ly+i, x+j − Ry+i, x+j+d|
i=−s j=−s
disparityy,x = argmind sady,x,d,
где L - левое изображение, R - правое.
Блок на правом изображении с наименьшим значением метрики определяет оптимальную пару.
Значение расстояния от точки сцены до картинной плоскости обрат- но пропорционально величине смещения:
T − d = T Z − f Z
Z = f · T
⇒
d
2.2. Архитектура процессора
Рис. 2: Поиск смещения [11]
Процессор (рис. 3), для которого необходимо реализовать данный алгоритм, имеет архитектуру SIMD с 512-битовыми регистрами. Под- держиваются типы int16, short32, char64, над которыми осуществляют- ся операции с 16-ю числами типа int, 32-мя числами типа short и 64-мя числами типа char соответственно. Архитектура поддерживает VLIW инструкции, существует три слота для векторных операций, и один для скалярных. Таким образом, одновременно могут выполняться четыре инструкции. При этом некоторые типы инструкций, например, vload могут выполняться лишь на ограниченном наборе векторных слотов.
При разработке алгоритма следует учитывать количество вектор- ной памяти, равное 128 КБ. Необходимо обрабатывать изображения по частям, не храня в памяти все данные. Например, размер Full HD изображения - 2 МБ, оно не поместится в векторную память.
На процессоре имеются 32 векторных регистра, в каждом из ко- торых может хранится значение int16, short32 или char64. Некоторые регистры могут использоваться как аккумуляторные. В таком случае к ним добавляется некоторое количество дополнительных бит. К приме- ру, тип acc24x32 имеет дополнительные 8 бит у каждого из 32-х элемен- тов вектора. Также существуют функции, работающие с предикатами. Они позволяют производить операции над заданными элементами век- тора.
2.3. Обзор существующих решений
Алгоритм полного перебора имеет асимптотику:
Рис. 3: Архитектура процессора EV6x
O(w ∗ h ∗ b2 ∗ d),
где w и h - ширина и высота изображения, b - размер окна, для которого считается метрика SAD, d - максимальное смещение.
Метрику можно считать за константное время с предварительной обработкой [8]. Зная для данного смещения для каждого пикселя сум- марное значение SAD на прямоугольнике, одним углом которого явля- ется пиксель с координатами (0, 0), а вторым - данный пиксель, сумму на конкретном прямоугольнике можно вычислить методом скользяще- го окна. В таком случаеасимптотика алгоритма составляет:
O(w ∗ h ∗ d)
Также существуют решения, использующие SIMD, такие как [5] и [1]. В [1] происходит одновременное вычисление нескольких значений sad.
3. Реализация
3.1. Инструменты
Для написания алгоритмов для процессора используется язык Си, так как программы на этом языке являются достаточно эффективны- ми.
Также используется язык OpenCL, который является расширением языка Си. OpenCL - стандарт, разработанный группой Khronos. OpenCL реализуется производителями оборудования и позволяет разрабаты- вать приложения независимо от платформы. Таким образом избегается необходимость разработки приложений для каждой целевой платфор- мы. Целью данной работы является написание OpenCL kernel-a (функ- ция в OpenCL, входящая в интерфейс). В действительности, использу- ется вариация OpenCL - Metaware OpenCL. Для тестирования исполь- зуется тестовый набор данных Tsukuba [9] Middlebury колледжа и ком- пании Microsoft. Этот набор данных является мировым стандартом для задач стереозрения. Для тестирования было реализовано два дополни- тельных решения. Первое - метод полного перебора, которое исполь- зовалось в качестве референсного. Это решение было затруднительно использовать для отладки основного алгоритма в силу его высокой вы- числительной сложности, поэтому было реализовано второе решение - скалярная версия с улучшенной асимптотикой, результат которой срав- нивался с результатом первого решения. Второе решение оказалось до- статочно быстрым для отладки.
3.2. Скорость алгоритма и использование памяти
Для того, чтобы показать идею алгоритма и оценить используемую векторную память, введем величину column_sad.
column_sady,x,d =
s
∑
|Ly+i, x − Ry+i, x+d|
i=−s
Покажем, как ее посчитать, зная column_sady−1,x,d
column_sady,x,d =
s
∑
|Ly+i, x − Ry+i, x+d| =
i=−s
∑
s−1
= |Ly+s, x − Ry+s, x+d| + |Ly+i, x − Ry+i, x+d| =
i=−s
= |Ly+s, x − Ry+s, x+d| +
s−1
∑
∑
i=−s−1 s
|Ly+i, x − Ry+i, x+d| −|Ly−s−1, x − Ry−s−1, x+d| =
= |Ly+s, x −Ry+s, x+d|+ |Ly−1+j, x −Ry−1+j, x+d|−|Ly−s−1, x −Ry−s−1, x+d| =
j=−s
= |Ly+s, x − Ry+s, x+d| + column_sady−1,x,d − |Ly−s−1, x − Ry−s−1, x+d|
Таким образом, column_sad для текущей строки зависит лишь от column_sadдля предыдущей строки и пикселей изображения в преде- лах размера окна. При этом новое значение считается за константное время.
Покажем, как с помощью column_sad посчитать sad.
s s−1
sady,x,d =
∑column_sady,x+i,d = column_sady,x+s,d+∑column_sady,x+i,d =
i=−s
= column_sady,x+s,d +
s−1 i=−s−1
∑
∑
s
i=−s
column_sady,x+i,d − column_sady,x−s−1,d =
= column_sady,x+s,d +
column_sady,x−1+j,d − column_sady,x−s−1,d =
j=−s
= column_sady,x+s,d + sady,x−1,d − column_sady,x−s−1,d =
Таким образом, sad также считается за константное время. При этом используя лишь column_sad с единственным индексом y.
Пересчитывая для каждого значения y сначала значения column_sad, а затем, зная эти значения, вычисляя sad для данного пикселя и дан- ного смещения, получаем асимптотику:
O(w ∗ h ∗ d)
При этом используя дополнительное количество памяти для column_sad, равное w ∗ d.
Повышению эффективности способствуют одновременный подсчет sad для различных смещений благодаря SIMD инструкциям и возмож- ность выполнять несколько инструкций одновременно на архитектуре VLIW.
Также можно заметить, что значения sad и column_sad для различ- ных смещений не зависят друг от друга, поэтому их можно считать от- дельно, а соответственно хранить лишь w памяти дляcolumn_sad. Если хранить значения column_sad для 32-х смещений для Full HD изобра- жения, то объем памяти равняется 64 КБ. Дополнительно, необходимо осуществлять доступ в векторную память к строкам двух изображений с индексами y − s − 1 и y + s, А также к строке sad и disparity. Таким образом, используется дополнительно 12 КБ. Итоговое количество ис- пользуемой векторной памяти - 76 КБ, что укладывается в допустимое количество памяти, 128 КБ.
3.3. Описание работы алгоритма
3.4. Векторизация
Алгоритм заключается в следующем. Фиксируется смещение d. Вы- числяется column_sad для первых block_size−1 строк. Далее идет ите- рация по строкам. Вычисляется column_sad,необходимый для опреде- ления sad текущей строки. Итерируясь по столбцам, вычисляется sad для конкретного пикселя. В зависимости от минимального значения SAD для данного пикселя и предыдущего значения смещения, обнов- ляется минимальное значение SAD и смещение, соответствующее ему.
Так как значения sad и column_sad для различных смещений не зависят друг от друга, в элементах вектора можно хранить информа- цию, соответствующую различным смещениям, и производить опера- ции над векторами. sad накапливается в аккумуляторном регистре ти- па acc24x32. Для корректных вычислений на границах используются
предикаты.
Единственный момент, когда происходит работа с несколькими сме- щениями сразу - поиск минимального sad среди различных смещений. Для этого необходимо использовать доступную в OpenCL функцию reduc_min. Она находит минимальный элемент в векторе. Также с по- мощью этой функции можно реализовать argmin для получения сме- щения, зная SAD.
ственной инструкции min.
3.5. Переход от int16 к short32
Рис. 4: Избавление от reduc_min
Необходимая для этой функции инструкция не реализована на про- цессоре, она раскладывается в ряд других. Для вектора типа short32 она раскладывается в 9 инструкций. Это неэффективно, поэтому был найден другой способ поискаминимального значения (рис. 4).
Вместо того, чтобы непосредственно вычислить минимальное значе- ние SAD с помощью функции reduc_min, накопим 32 вектора для смеж- ных пикселей в строке. Таким образом, изменив направление вектори- зации, вместо reduc_min становитсявозможным использование един-
Необходимо правильно рассчитать используемый тип. Для блока 21х21 (размер окна по умолчанию) таким типом является int. Но можно заметить, что минимальный SAD превосходит максимальное значение типа short лишь изредка. Этот замечание было проверено на тестовых данных (рис. 5). Первый график показывает, что среднее значение sad для конкретного смещенияне превосходит 20.000, в то время как макси- мальное значение типа short - 65.536. При этом, максимальное значение минимального sad - 29.106. Таким образом, было решено использовать тип short32 для более эффективной реализации для значений размера окна не более 21.
Было рассчитано теоретическое значение эффективности. Оно необ-ходимо для понимания скорости работы алгоритма перед реализацией. Некоторые типы инструкций на процессорах с архитектурой VLIW могут быть выполнены лишь на ограниченном количестве слотов. На процессоре EV6x инструкции типа shuffleзадействуют модуль для пе- рестановки элементов вектора, доступны только на 3-ем слоте. Ин- струкции типа vmem осуществляют операции с памятью, также до- ступны только на 3-емслоте. Инструкции типа alu, представляющие собой арифметические операции, доступны на всех слотах. Для каждо- го слота отдельно считается количество тактов процессора на пиксель, и берется максимум, а также учитывается их суммарное значение. Ито-
Рис. 5: На левом графике показана зависимость среднего значения sad взависимости от смещения. На правом графике количество пикселей в определенном интервале минимальных значений sad. Количество пик- селей с высокими значениями минимального sad мало.
4. Результаты
Скорость реализованного алгоритма (без reduc_min, с типом short32) составляет 107 тактов процессора на пиксель. Замедление более чем в два раза можно объяснить не до конца идеальной работой компилятора с разложением VLIW инструкций, длительным копированием данных в векторную память, и большой загрузкой скалярного слота, который не был учтен в расчетах.
E = 4 ∗ max(mem + shuffle, (mem + shuffle + alu)/3)
Рис. 6: Теоретическая оценка
Результат работы алгоритма представлен на рис. 7.
Рис. 7: Слева - истинная карта диспаритетов. Справа - карта диспари- тетов, полученная алгоритмом Stereo Block Matching.
Заключение
В рамках курсовой работы были выполнены следующие задачи:
• Изучена предметная область и алгоритм, который необходимо ре- ализовать;
• Изучена архитектура процессора;
• Построен алгоритм для данной архитектуры;
• Улучшен алгоритм:
– Избавление от неэффективной функции;
– Переход к типу short32;
• Оценена скорость работы и количество требуемой памяти;
• Реализован алгоритм.
В дальнейшем планируется интеграция OpenCL kernel-а в фреймворк OpenVX, который является стандартом кроссплатформенных приложе- ний компьютерного зрения.
Список литературы
[1] Bodkin Bryan Hale. Real-Time Mobile Stereo Vision // Master’s Thesis, University of Tennessee. – 2012. – Proceedings from the 15th International Conference on Vision Interface. Access mode: https:
//trace.tennessee.edu/utk_gradthes/1313.
[2] Brown M. Z., Burschka D., Hager G. D. Advances in computational stereo // IEEE Transactions on Pattern Analysis and MachineIntelligence. – 2003. – Aug. – Vol. 25, no. 8. – P. 993–1008.
[3] DesignWare EV6x Vision Processors. – Access mode: https://www. synopsys.com/dw/ipdir.php?ds=ev6x-vision-processors.
[4] Fisher Joseph A. Very Long Instruction Word Architectures and the ELI-512 // Proceedings of the 10th Annual International Symposium on Computer Architecture. – ISCA ’83. – New York, NY, USA : ACM, 1983. – P. 140–150. – Access mode: http://doi.acm.org/10.1145/ 800046.801649.
[5] Hachaj T., Ogiela M. R. Real time area-based stereo matching algorithm for multimedia video devices // Opto-Electronics Review. – 2013. – Dec. – Vol. 21, no. 4. – P. 367–375. – Access mode: https:
//doi.org/10.2478/s11772-013-0107-5.
[6] Hirschmüller Heiko. Accurate and Efficient Stereo Processing by Semi- Global Matching and Mutual Information. – Vol. 2. – 2005. – 06. – P. 807–814.
[7] Patterson David A., Hennessy John L. Computer Organization and Design, Fifth Edition: The Hardware/Software Interface. – 5th edition. – San Francisco, CA, USA : Morgan Kaufmann Publishers Inc., 2013. – ISBN: 0124077269, 9780124077263.
[8] Stefano Luigi Di, Marchionni Massimiliano, Mattoccia Stefano. A fast area-based stereo matching algorithm // Image and Vision
Computing. – 2004. – Vol. 22, no. 12. – P. 983 – 1005. –
Proceedings from the 15th International Conference on Vision Interface. Access mode: http://www.sciencedirect.com/science/ article/pii/S0262885604000733.
[9] Tsukuba Dataset. Middlebury Stereo Vision. – Access mode: vision. middlebury.edu/stereo/.
[10] Мокаев Руслан. Реализация алгоритма Semi-Global Matching. – 2012. – Access mode: http://se.math.spbu.ru/ SE/YearlyProjects/2012/YearlyProjects/2012/445/445_Mokaev_ report.pdf.
[11] Основы стереозрения. – Access mode: https://habr.com/ru/post/ 130300/.