Анализ быстродействия и вычислительной сложности алгоритмов 3D-реконструкции с точки зрения их применимости на процессорах с низким энергопотреблением

В настоящее время задача 3D-реконструкции в реальном времени имеет множество решений [1]. Однако развитие робототехники как науки и появление современных портативных устройств, построенных на архитектуре ARM, привели к необходимости в решении задач компьютерного зрения на процессорах с низким энергопотреблением и, соответственно, меньшей производительностью. Задача 3D-реконструкции предполагает высокую алгоритмическую сложность вычислений, связанную с попиксельной переработкой кадров с двух видеопотоков, сравнение величин яркости в некоторой окрестности точки изображения.

Согласно [2], существует 3 наиболее распространенных алгоритма 3D-реконструкции с использованием стереопары: локальный, полугло-бальный и глобальный – и около 15 способов расчета «цен совпадения» [3], используемых в этих методах. В данной статье описывается локальный метод, так как, согласно [2], полуглобальные методы [4] выполняются на 14 % дольше, а глобальные – (graph cuts) – на 50 %.

Алгоритмы 3D-реконструкции и анализ их эффективности

Локальный метод [5] представляет собой метод «скользящего окна», сканирующего изображения с левой и правой камеры и ставящего в соответствие окну ω Є L с центром в точке ( х i , y j ) окно ω' Є R с центром в точке ( х k , y j ), где L , R – пространства левого и правого изображений. Для каждой пары окон вычисляется значение «цены совпадения», в дальнейшем минимизируемое для всех возможных значений disparity (далее – величины рассогласования). Сложность алгоритма «скользящего окна» – O ( N * D * W ), где N – количество точек в исходном изображении; D – максимальная величина сдвига левого изображения относительно правого, или величина максимального рассогласования, W – количество точек, охватываемых скользящим окном.²

Оптимизация локального алгоритма может быть выполнена за счет уменьшения одного из параметров – N , D или W , что приведет к следующим последствиям: уменьшение N снизит разрешение получаемой карты глубины и вызовет эф-

фект либо понижающей качество дискретизации, либо урезания исходного фрагмента изображения. Уменьшение величины D уменьшит различаемое расстояние от камеры, так как величина рассогласования обратно пропорциональна квадрату расстояния от камеры до объекта. Уменьшение W приведет к снижению достоверности функции соответствия и увеличению количества ошибок по причине увеличения вероятности схожих окон. Наименьшая возможная величина W – это 1 пиксель, однако в таком случае некоторые алгоритмы теряют возможно сть построения карты глубины.

Фактором, влияющим на быстродействие алгоритма 3D-реконструкции не менее значительно, чем величины N , D и W , является скорость работы алгоритма, рассчитывающего «цены совпадения» (или степени схожести) окон ω и ω'. Сложность некоторых алгоритмов, а также оценка количества операций процессора, требуемых для их реализации, приведены ниже.

AD [2] является алгоритмом с вырожденным окном (1 пиксель) и производит сравнение окон с помощью поиска наименьшей по модулю разности яркости пикселей в окнах ω и ω'. Таким образом, сложность алгоритма – O (1), так как N всегда равно 1, а количество затрачиваемых операций напрямую зависит от способа реализации функции abs. Функция расчета «цен совпадения» [2], минимизация которой выполняется алгоритмом стереореконструкции, приведена ниже:

С AD ( p , d )=| I L ( p ) – I R ( p – d )|, где p – вектор координат пикселя [ х y ]; d – вектор величин рассогласования по осям координат Х и Y; I R и I L – функции интенсивности цвета левого и правого изображений от вектора координат.

Для расчета «цены совпадения» при использовании высокопроизводительной функции расчета абсолютной величины [6] потребуется выполнить: 2 операции чтения из памяти, 2 операции вычитания, 1 операцию сложения, 1 операцию побитового исключающего ИЛИ (XOR), 15 операций сдвига, 2 операции присваивания, что в сумме дает 23 инструкции процессора. Несмотря на высокие показатели скорости работы, AD-алгоритм дает карту глубины очень низкого качества с большим количеством ошибок, из-за чего его использование в промышленности невозможно.

Алгоритмы SAD [5] и SSD [7] основываются на принципе работы алгоритма AD, но используют невырожденное окно и за счет этого получают более высокое (относительно AD) качество карты глубины. Размер используемого окна подбирается экспериментально, поскольку увеличение количества пикселей повышает количество шума в тестируемом окне, а уменьшение снижает количество информации, содержащейся в окне. Формулы расчета «цен совпадения» для алгоритмов SAD и SSD приведены ниже:

С SAD ( p , d ) = Σ | I L ( q ) – I R ( q – d )|, где q Є Np , Np – окрестность пикселя p ;

С SSD ( p , d ) = Σ ( I L ( q ) – I R ( q – d ))², где q Є Np , Np – окрестность пикселя p .

Для расчета «цены совпадения» потребуется выполнить: 2 * N операции чтения из памяти, 2 * N операции вычитания; в случае SAD: N *(15 операций сдвига + 1 операцию сложения + 1 операцию побитового исключающего ИЛИ (XOR)); в случае SSD: N * (1 операцию умножения, приравниваемую к 31 операции сдвига и 32 операциям сложения). В сумме, при расчете «цен совпадения» методом SAD с размером окна, равным 9 * 7 (для удобства сравнения с последующими методами), будет выполнено 9 * 7 * (2 + 2 + 15 + 1 + 1) = 1323 инструкции процессора, а при расчете методом SSD 9 * 7 * (2 + 2 + 31 + 32) = 4221 инструкция.

Метод Census [8] относится к группе непараметрических методов, так как основывается не на яркости пикселя непосредственно, а на локальном порядке следования яркостей пикселей. Зачастую реализация этого метода предполагает предподго-товку изображений, называемую трансформацией или фильтрованием. Метод выполняется в 2 этапа. На первом этапе каждое изображение преобразуется в census-матрицу. Каждый пиксель этой матрицы есть битовая маска, i -й бит которой единичный, если яркость i -го пикселя в окне ω выше яркости пикселя в центре окна. Сложность алгоритма получения величины census линейна, O ( N ), где N – количество пикселей в окне ω, так как каждый пиксель в окне сравнивается по яркости с центральным пикселем окна лишь однажды. Формула вычисления «цены совпадения» приведена ниже.

f ( p , q ) = {1, I ( q ) >  I ( p ), где I ( p ) – яркость пикселя в точке p изображения,

• 0, I ( q ) >  I ( p )

census( p ) = || f ( p , q ), где p , q Є ω.

Одна из возможных реализаций на языке C расчета величины census приведена ниже:

uchar ctr = I[x][y];

uchar census =  ((I[y-1][x-1]>ctr)<<7)   |

((I[x][y-1]>ctr)<<6)

|     ((I[x+1][y-1]>ctr)<<5)     |     ((I[x-1]

[y]>ctr)<<4)   |   ((I[x+1][y]>   ctr)<<3)   |

((I[x-1][y+1]>ctr)<<2) | ((I[x][y+1]>ctr)<<1) | ((I[x+1][y+1]>ctr));

Таким образом, для выполнения предподго-товки одной пары пикселей с левого и правого изображения необходимо выполнить: N операций чтения из памяти, N * ( N – 1)/2 операций сдвига, N операций сравнения, N – 1 операций побитового ИЛИ, 2 операции присваивания.

На размеры окна ω накладываются архитектурные ограничения, связанные с моделью оперативной памяти. Количество бит в census должно быть максимально близко к кратному 8. Для окна размером 9 * 7 (census длиной 62 бита), на расчет величины census для двух пикселей (левого и правого изображений) потребуется: 2 * (2 + 63 * 3 – –1 + 63 * (63 – 1)/2) = 4286 инструкций процессора.

Анализ быстродействия и вычислительной сложности алгоритмов 3D-реконструкции с точки зрения их применимости на процессорах с низким энергопотреблением

Вторым этапом является подсчет расстояния Хемминга [9] между величинами census (в отличие от AD, где используется абсолютная величина разности). Из множества алгоритмов для архитектуры ARM при использовании окна 9 * 7 более подходит реализация popcount_2, не использующая 64битного умножения [10]. Для вычисления расстояния Хемминга требуется выполнить: 63 операции сдвига, 5 операций побитового И, 5 операций сложения, 1 операцию вычитания, 6 операций присваивания. Таким образом, суммарное количество инструкций процессора, требуемое на расчет «цены совпадения» по алгоритму Census, равно 4286 + (63 + 5 + 5 + 1 + 6) = 4366.

В данной статье не приводится анализ методов NCC, Z-(SAD, SAD, NCC), BT [11], Rank [12] и MI [2], как более сложных и, соответственно, более медленных, чем перечисленные выше.

Заключение

Подводя итог, можно выделить метод SAD как наиболее быстрый из приведенных, однако, согласно [1], даже оптимизированные алгоритмы SAD и SSD не дают такой точности, как Census. Реализация алгоритма предподготовки для Census во многом определяет вычислительные затраты, поэтому может быть предпринята попытка оптимизации способа расчета величины census и/или способа накопления и сравнения битов, описывающих относительную яркость пикселей в окне ω, однако на текущем этапе его использование затруднительно ввиду чрезмерного количества требуемых операций.