Повышение быстродействия алгоритма полуглобального стереосопоставления

Основной объем вычислений, производимых алгоритмом SGM [1], связан с расчетом величины цены сопоставления E data и выбором наиболее подходящего предшествующего пикселя, величина E_smooth для которого минимизирует стоимость пути распространения для каждого значения диспаратности, рассчитываемого в данной точке:

E ( P i , d ) = E data ( P i , d ) + E smooth ( P i - 1 , d ) ;                                                             (1)

^E ( P i - 1 , d ) ;

E smooth ( P i - 1 , d ) = min ‘

E ( P_z .-1 , d - 1 ) + P1;

E ( P_z .-1 , d + 1 ) + P 1;

min [ E ( P i - 1 , d ) ] + P 2.

Большой объем вычислений объясняется тем, что операции расчета цен сопоставления и выбора предыдущего пикселя для вычисления стоимости кратчайшего пути выполняются для каждого направления распространения R , для каждого пикселя p i,j , где i ∈ W , j ∈ H и для каждого значения диспаратности D , то есть R · W · H · D раз.

Снизить объем необходимых вычислений и тем самым уменьшить время работы алгоритма возможно при уменьшении количества производимых итераций, другими словами, уменьшив или, в идеальном случае, сократив до 1, один из параметров R , W , H , D . Поскольку уменьшение высоты H или ширины W кадра приводит к неминуемой и разительной потере качества результирующей карты глубины [2], далее будут рассматриваться лишь возможности минимизации параметров R и D из перечисленных четырех параметров.

Алгоритм SGM производит R [3] (от 8 до 16) проходов по исходному изображению, выполняя операции расчета цен сопоставления для всех возможных значений диспаратности в анализируемой точке. Время работы алгоритма прямо пропорционально числу R , поскольку оно отражает количество цен сопоставления, агрегируемых для каждого значения диспаратности (рис. 1).

С точки зрения результирующей карты глубины, величина R влияет на количество ошибок в карте диспаратностей, а также на размер и количество артефактов искажений в ней (рис. 2).

Результаты работы алгоритма свидетельствуют о том, что снижение количества направлений распространения неминуемо ведет к снижению качества результирующей карты глубины (увеличение количества ошибок от 15,4 до 18,2 %). Однако, наряду с этим, значительно снижается и время работы алгоритма: вычисление карты глубины на рис. 2, а занимает 0,61 с, карты глубины на рис. 2, б – 1,24 с. При постановке вычислительного эксперимента использовалось следующее оборудование:

• 1)    процессор: Intel Core i7-3770 3.40 GHz;

• 2)    оперативная память: 8GB DDR3.

Рис. 1. Пример агрегирования цен для 4 различных направлений распространения R

а)                                                               б)

Рис. 2. Сравнение результирующих карт глубин для 3 (а) и 8 (б) направлений распространения

Размер исходных стереоизображений - 450 x 375 пикселей, количество диспаратностей - 60. Вычисления выполнялись в однопоточном режиме. Следует учитывать возможность распараллеливания алгоритма на несколько процессорных ядер (4 в современных компьютерах), что позволит снизить время вычисления в 4 раза и увеличить количество кадров в секунду от 1,6 до 6,5. Однако стереоалгоритм реального времени должен вычислять 24 кадра в секунду, что означает, что время вычисления одного кадра должно занимать 0,041 с. Для сравнения, в работе [4] на вычисление карты глубины изображения размером 450 x 375 для 60 значений диспаратности, время вычисления равняется 0,258 мс, что позволяет добиться производительности в 3,8 кадров в секунду.

Поскольку функция диспаратности не является непрерывной, для расчета значения диспаратности в точке p i,j недостаточно проанализировать ее окрестность Np i,j . Так как значение диспаратности может меняться скачкообразно, для его определения необходимо проанализировать D значений в каждом пикселе, где величина D равна количеству диспаратностей, анализируемых данной системой.

Диапазон значений диспаратности можно сузить при наличии грубой оценки карты диспаратностей для данной пары стереоизображений. Если допустить, что значение диспаратности в точке X равно d с погрешностью Δ, то для вычисления стоимости кратчайшего пути в точке X необходимо выполнить 2Δ+ 1 операций расчета цен сопоставления и выбора предыдущего пик- селя. Классический алгоритм SGM выполняет D операций для расчета кратчайшего пути в каждой точке [1]. При условии, что 2Δ+ 1 < D, такой подход снижает количество рассчитываемых цен сопоставления на D –2Δ– 1 операций для каждого пикселя. В целом, количество операций снижается на R·W·H·(D –2Δ– 1) для всего алгоритма.

Наряду с выигрышем в количестве операций появляется необходимость в расчете приближенных значений карты диспаратностей. Этот процесс, в свою очередь, требует определенного количества вычислительных операций для выполнения. Описываемый алгоритм может считаться более оптимальным, чем SGM, только в том случае, если время вычисления приближенной карты глубины в совокупности со временем ее уточнения будет меньше, чем время работы оригинального алгоритма, а также при условии, что не будет наблюдаться значительной потери качества в наблюдаемом результате.

В качестве приближенной карты глубины может быть использована карта глубины, вычисленная для уменьшенных исходных стереоизображений. Расчет масштабированной карты глубины используется в [5], однако получаемые значения диспаратности являются не промежуточным, а конечным результатом вычислений для определенных диапазонов диспаратностей. При вычислении масштабированной карты глубины количество необходимых операций составляет R · H · W · D / K ³, где K – коэффициент масштабирования, равный отношению размеров исходных стереоизображений к размерам уменьшенных стереоизображений. Таким образом, для вычисления карты глубины для стереоизображений, уменьшенных в 4 раза, требуется в 64 раза меньше вычислительных операций, чем для вычисления карты глубины исходного размера.

Реализация такого алгоритма и его выполнение на том же оборудовании дало следующие результаты: время вычисления карты глубины составляет 0,34 с, что позволяет вырабатывать 3 кадра в секунду. Наряду с приростом производительности наблюдается также и снижение качества результирующей карты глубины (увеличение количества ошибок от 18,2 до 21,6 %). Источником ошибки являются искажения на границах объектов, причиной которых является масштабированная карта глубины.

В качестве дальнейших направлений исследования рассматривается анализ способов удаления искажений при демасштабировании предварительных карт глубин, оценка способов кеширования цен сопоставления, анализ цен сопоставления и их влияния на процент ошибочно вычисленных значений диспаратности, а также дальнейшая оптимизация алгоритма полуглобального стереосопоставления.