Введение

Алгоритмы оценки диспаритета делятся на две широкие категории: локальные методы и глобальные методы. Локальные методы оценивают по одному пикселю за раз, принимая во внимание только соседние пиксели. Глобальные методы учитывают информацию, которая доступна во всем изображении. Локальные методы являются плохими при обнаружении внезапных изменений глубины и окклюзий, и, следовательно, предпочтительны глобальные методы. Полуглобальное соответствие использует информацию из соседних пикселей в нескольких направлениях, чтобы вычислить несоответствие пикселя. Анализ в нескольких направлениях приводит к многим расчетам. Вместо использования всего изображения, дисперсия пикселя может быть вычислена путем принятия меньшего блока пикселей для простоты расчетов. Таким образом, алгоритм Semi-Global Block Matching (SGBM) использует основанное на блоках согласование затрат, которое сглаживается путевой информацией из нескольких направлений.

Используя основанный на блоках подход, этот алгоритм оценивает аппроксимацию пикселя в левом изображении от того же пикселя в правом изображении. Больше информации о Stereo Vision доступно здесь. Прежде чем входить в алгоритм и детали реализации, необходимо понять два важных параметра: Уровни различия и Количество направлений.

Уровни неравенства: уровни Неравенства - параметр, используемый, чтобы определить область поиска для соответствия. Как показано на рисунке ниже, алгоритм ищет каждый пиксель в левом изображении из D пикселей в правом изображении. Сгенерированные значения D являются уровнями D для пикселя в левом изображении. Первые столбцы D «Левого изображения» не используются, поскольку соответствующие пиксели в «Правом изображении» недоступны для сравнения. На рисунке w представляет ширину изображения, а h - высоту изображения. Для заданного разрешения изображения увеличение уровня дисперсии уменьшает минимальное расстояние, чтобы обнаружить глубину. Увеличение уровня несоответствия также увеличивает вычислительную нагрузку алгоритма. При заданном уровне неоднородности увеличение разрешения изображения увеличивает минимальное расстояние для обнаружения глубины. Увеличение разрешения изображения также увеличивает точность оценки глубины. Количество уровней неоднородности пропорционально входу изображения для обнаружения объектов на той же глубине. Этот пример поддерживает уровни неоднородности от 8 до 128 (оба значения включительно). Объяснение алгоритма относится к 64 уровням неоднородности. Модели, представленные в этом примере, могут принимать входные изображения любого разрешения.

Количество направлений: В алгоритме SGBM, для оптимизации функции стоимости, входное изображение рассматривается с нескольких направлений. В целом точность результата расхождения улучшается с увеличением количества направлений. В этом примере анализируются пять направлений: слева направо (A1), сверху слева вниз справа (A2), сверху вниз (A3), сверху справа вниз налево (A4) и справа налево (A5).

Алгоритм SGBM

Алгоритм SGBM принимает за вход пару выпрямленных изображений слева и справа. Пиксельные данные от необработанных изображений могут не иметь одинаковых вертикальных координат из-за небольших изменений положения камеры. Изображения должны быть выпрямлены перед выполнением согласования стерео, чтобы все эпи-полярные линии были параллельными горизонтальной оси и совпадали с вертикальными координатами каждого соответствующего пикселя. Для получения дополнительной информации об исправлении см. rectifyStereoImages (Computer Vision Toolbox) функция. Рисунок показывает блок алгоритма SGBM, используя пять направлений.

Реализация алгоритма SGBM имеет три основных модуля: Вычисление совпадающих затрат, Вычисление Направленных Затрат и Постобработка.

Многие методы были исследованы в литературе для вычисления стоимости соответствия. В этом примере реализации используется преобразование переписи населения, как объяснено в [2]. Этот модуль можно разделить на два этапа: Центрально-симметричное преобразование переписи (CSCT) левых и правых изображений и расчет расстояния Хемминга. Во-первых, модель вычисляет CSCT на каждом из левых и правых изображений с помощью скользящего окна. Для заданного пикселя вокруг него рассматривается окно 9 на 7 пикселей. CSCT для центрального пикселя в этом окне оценивается путем сравнения значения каждого пикселя с соответствующим центрально-симметричным аналогом в окне. Если значение пикселя больше, чем его соответствующий центрально-симметричный пиксель, результат равен 1, в противном случае результат равен 0. Рисунок показывает пример окна 9 на 7. Номер центрального пикселя - 31. 0-й пиксель сравнивается с 62-м пикселем (синий), 1-й пиксель сравнивается с 61-м пикселем (красный) и так далее, чтобы сгенерировать 31 результат. Каждый результат - выход одного бита и результат всего окна - устроен как 31-битовое число. Это 31-битовое число является выходом CSCT для каждого пикселя в обоих изображениях.

В модуле Hamming Distance выходы CSCT левого и правого изображений являются пиксельными XOR 'd, и устанавливаемые биты подсчитываются, чтобы сгенерировать затраты на соответствие для каждого уровня несоответствия. Чтобы сгенерировать уровни несоответствия D, используются D-пиксельные блоки расчета расстояния Хемминга. Стоимость соответствия для уровней разности D при заданном положении пикселя, p, в левом изображении вычисляется путем вычисления расстояния Хемминга с (p до D + p) положениями пикселя в правом изображении. Стоимость соответствия, C (p, d), вычисляется в каждом пиксельном положении, p, для каждого уровня неоднородности, d. Стоимость соответствия не вычисляется для пиксельных положений, соответствующих первой D- столбцов левого изображения.

Второй модуль алгоритма SGBM является оценкой затрат по направлению. В целом из-за шума результат стоимости соответствия неоднозначен и некоторые неправильные матчи могут иметь меньшую стоимость, чем правильные таковые. Поэтому требуются дополнительные ограничения для повышения гладкости путем наказания за изменения соседних различий. Это ограничение реализуется путем агрегирования 1-D минимальных затрат путей с нескольких направлений. Он представлен агрегированной стоимостью из r направлений в каждом пиксельном положении S (p, d), как задано как

Минимальный 1-D путь для заданного направления, L_r (p, d), вычисляется как показано на уравнении.

Как упоминалось ранее, этот пример использует пять направлений для расчета несоответствия. Распространение в каждом направлении является независимым. Получившиеся дисперсии на каждом уровне от каждого направления агрегируются для каждого пикселя. Общая стоимость - это сумма затрат, рассчитанная для каждого направления.

Третий модуль алгоритма SGBM является постобработкой. Этот модуль имеет три шага: вычисление индекса минимальных затрат, интерполяция и функция уникальности. Расчет индекса минимальной стоимости находит индекс, соответствующий минимальной стоимости для заданного пикселя. Субпиксельная квадратичная интерполяция применяется к индексу, чтобы устранить различия на уровне субпикселя. Функция уникальности обеспечивает надежность вычисленного минимального расхождения. Более высокое значение порога уникальности помечает больше различий ненадежными. В качестве последнего шага отрицательные значения дисппаритета признаются недействительными и заменяются на -1.

Реализация HDL

Рисунок ниже показывает обзор модели примера. Блоки leftImage и rightImage импортируют пару стерео изображения как вход в алгоритм. В Подсистеме Входа блок Frame To Pixels преобразует входные изображения из блоков leftImage и rightImage в поток пикселей и сопровождающих управляющих сигналов в pixelcontrol bus. поток пикселей передается как вход в подсистему SGBMHDLAlgorithm, которая содержит три расчета модуля, описанных выше: сопоставление вычисления затрат, вычисление затрат по направлению и постобработка. Выходы подсистемы SGBMHDLAlgorithm являются потоком пикселей значений несоответствия. В Подсистеме Выхода блок Pixels To Frame преобразует выход в карту матричного расхождения. Карта расхождения отображается с помощью блока Video Viewer.

modelname = 'SGBMDisparityExample';
open_system(modelname);
set_param(modelname,'SampleTimeColors','off');
set_param(modelname,'Open','on');
set_param(modelname,'SimulationCommand','Update');
set(allchild(0),'Visible','off');

Сопоставление вычисления затрат

Расчет стоимости соответствия снова разделяется на две части: вычисление CSCT и вычисление расстояния Хемминга. CSCT вычисляется в каждом окне 9 на 7 пикселей путем выравнивания каждой группы пикселей для сравнения с использованием блоков Tapped Delay (Simulink), For Each Subsystem (Simulink) блоков и буферов. Входные пиксели заполнены нулями, чтобы разрешить расчет CSCT для угловых пикселей. Получившийся поток пикселей передается в подсистему ctLogic. Фигура ниже показывает подсистему ctLogic, которая использует блок Tapped Delay для генерации группы пикселей. Пиксели буферизуются для imgColSize циклы, где imgColSize - количество пикселей в линии изображения. Группа пикселей, которая выровнена для сравнения, генерируется из каждой строки. Блок For Each и Логический Оператор реплицируют логику сравнения для каждого пикселя входа размера вектора. Чтобы реализовать окно 9 на 7, модель использует четыре таких блока For Each. Результатом, сгенерированным каждым блоком For Each, является вектор, который дополнительно конкатенируется, чтобы сформировать вектор размера 31 бит. После использования Bit Concat (HDL Coder), тип выходных данных uint5. Операции CSCT и заполнения нулями выполняются отдельно на левом и правом входных изображениях, и результаты передаются в подсистему Hamming Distance.

open_system('SGBMDisparityExample/SGBMHDLAlgorithm/MatchingCost/CensusTransform/ctLogic','force');

В подсистеме Hamming Distance 65-й результат левого CSCT - XOR 'd с 65-м по 2-й результатами правого CSCT. Заданные биты подсчитываются, чтобы получить Расстояние Хемминга. Это расстояние должно быть рассчитано для каждого уровня неоднородности. Правый результат CSCT передается в подсистему enabledTapedDelay, чтобы сгенерировать группу пикселей, которая затем является XOR 'd с левым результатом CSCT, используя блок For Each. Блок For Each также подсчитывает установленные биты в результате. Блок For Each повторяет вычисление расстояния Хемминга для каждого уровня неоднородности. Результатом является вектор с 64 уровнями дисперсии, соответствующими каждому пикселю. Этот вектор является Совпадающей Стоимостью, и он передается в Подсистему Направленных Затрат.

open_system('SGBMDisparityExample/SGBMHDLAlgorithm/MatchingCost/HammDistA','force');

Расчет затрат по направлению

Подсистема Directional Cost вычисляет расхождение в каждом пикселе в нескольких направлениях. Пять направлений, используемых в примере, это слева направо (A1), верхняя часть-лево-нижнее-правое (A2), сверху-вниз (A3), верхняя часть-правое-нижнее-левое (A4) и справа-налево (A5). Поскольку агрегирование затрат в каждом пикселе в каждом направлении независимо друг от друга, все пять направлений реализуются одновременно.

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

На рисунке выше синий прямоугольник указывает положение текущего пикселя, для которого вычисляются текущие значения затрат. В красном поле указывается положение предыдущих значений затрат, которые будут использоваться для расчета текущих затрат. Для A1 текущая стоимость становится предыдущим значением затрат для следующих расчетов при прохождении слева направо. Таким образом, текущее значение стоимости должно быть немедленно возвращено для вычисления следующих текущих затрат, как описано в [3]. Для A2 при прохождении слева направо текущее значение затрат должно использоваться в качестве предыдущего значения затрат после циклов imgColSize + 1. Текущие значения затрат, следовательно, буферизуются для циклов, равных imgColSize + 1, и затем возвращаются для вычисления следующих текущих затрат.

Точно так же для A3 и A4 текущие значения затрат буферизуются для циклов, равных imgColSize и imgColSize-1, соответственно. Однако для A5 при прохождении слева направо предыдущее значение затрат недоступно. Таким образом, направление обхода для вычисления A5 изменяется назад. Эта настройка выполняется путем обращения входных пикселей каждой строки назад. Текущее значение затрат затем становится предыдущим значением затрат для следующих текущих расчетов затрат, аналогичных A1.

В 1-D пути минимальной стоимости вычисляются текущие затраты в позиции диспаритета d с помощью значения «Совпадающие затраты», предыдущих значений затрат при различиях d-1, d и d + 1 и минимума предыдущих значений затрат. Рисунок ниже показывает подсистему пути минимальной стоимости, которая вычисляет текущую стоимость в положении расхождения для пикселя.

open_system('SGBMDisparityExample/SGBMHDLAlgorithm/DirectionalCost/LeftToRight/lrSubsystem/minCostPath','force');

Блок For Each используется для тиражирования вычисления пути минимальной стоимости для каждого уровня неоднородности для каждого направления. На рисунке ниже показана реализация A1 для 64 уровней несоответствия. Как показано на рисунке, 64 вычисления пути минимальной стоимости сгенерированы как представлено подсистемой minCostPath. Стоимость соответствия является входом от подсистемы Hamming Distance. Текущие затраты, вычисленные подсистемой minCostPath, немедленно возвращаются в себя как предыдущие значения затрат для следующих текущих расчетов затрат. Таким образом, значения для prevCost_d теперь доступны. Значения для prevCost_d-1 получаются путем сдвига 1-го на 63-е значения обратной связи во 2-е на 64-е положения. Подсистема d-1 содержит блок Selector (Simulink), который смещает положение значений и заполняет нуль на 1-й позиции.

Точно так же значения для prevCost_d+1 положения получаются путем смещения значений обратной связи 2-го на 64-е положение в 1-е на 63-е положение и вставки нуля в 64-е положение. Вычисленная текущая стоимость также передается в блок min, чтобы вычислить минимальное значение из текущих значений затрат. Это значение возвращается к входу minPrevCost подсистемы minCostPath. Затем следующая текущая стоимость вычисляется с помощью текущих значений затрат, действующих как предыдущие значения затрат, в следующем цикле для A1. Поскольку минимальная стоимость уровней расхождения от предыдущего набора немедленно необходима для текущего набора, этот путь обратной связи является критическим путем в проекте.

open_system('SGBMDisparityExample/SGBMHDLAlgorithm/DirectionalCost/LeftToRight/lrSubsystem','force');

Текущие расчеты стоимости для A2, A3 и A4 выполняются одинаково. Поскольку текущее значение стоимости не требуется сразу для этих направлений, существует буфер в обоих путях обратной связи. Этот буфер препятствует тому, чтобы этот путь обратной связи был критическим путем в проекте. Рисунок ниже показывает реализацию A3 с буфером в путях обратной связи.

open_system('SGBMDisparityExample/SGBMHDLAlgorithm/DirectionalCost/TopToBottom/tbSubsystem','force');

Текущее вычисление стоимости для A5 имеет дополнительную логику, чтобы изменить строки на входе и снова изменить строки на выходе, чтобы соответствовать пиксельным позициям для вычисления общей стоимости. Один буфер циклов imgColSize достигает этого обращения. Поскольку все направления вычисляются одновременно, время, необходимое для обращения назад строк, должно быть компенсировано на других путях. Задержку, эквивалентную 2 * циклам imgColSize, вводят в других четырех направлениях. Для оптимизации ресурсов вместо буферизации 64 значений стоимости соответствия для каждого пикселя буферизируется 31-битовый результат CSCT. Затем для вычисления стоимости соответствия для A5 требуется отдельный модуль Hamming Distance. Этот проект уменьшает использование памяти на чипе. Строки сторнируются после расчета CSCT и вычисления стоимости соответствия с помощью отдельного модуля Hamming Distance, который обеспечивает вход Matching Cost для A5. Кроме того, подсистема dataAligner используется для удаления разрывов данных для каждой строки перед ее передачей подсистемам Hamming Distance. Это помогает легко синхронизировать данные во время агрегации. Текущая стоимость, полученная из всех пяти направлений в каждом пикселе, агрегируется, чтобы получить общую стоимость в каждом пикселе. Общая стоимость передается Подсистеме постобработки.

Постобработка

В подсистеме постобработки индекс минимальной стоимости вычисляется для каждого положения пикселя из 64 уровней несоответствия при помощи блоков Min в древовидной архитектуре. Полученное значение индекса является неоднородностью каждого пикселя. Наряду с вычислением индекса минимальной стоимости вычисляются также значение минимальной стоимости вычисляемого индекса и значения себестоимости индексов 1 и 1. Подсистема Minimum_Cost_Index реализует древовидную архитектуру, чтобы вычислить минимальное значение из 128 значений. 64 значения дисперсии заполнены еще 64 значениями, чтобы создать вектор с 128 значениями. Минимальное значение вычисляется из этого вектора с 128 значениями. В случае, если вектор со 128 значениями доступен, значение не заполняется вектором или другими словами, вектор передается непосредственно для вычисления минимального значения. Variant Subsystem, Variant Model (Simulink) используется для выбора между логикой с помощью переменных подсистемы исполнения. Субпиксельная квадратичная интерполяция затем применяется к индексу, чтобы устранить несоответствие на уровне субпикселя. Кроме того, функция уникальности применяется к индексу, вычисленному блоками min, чтобы гарантировать надежные результаты различий. В качестве последнего шага идентифицируются недопустимые расхождения и заменяются на -1.

Параметры модели

Модель, представленная здесь, принимает уровни несоответствия и порог уникальности в качестве входных параметров, как показано на рисунке. Уровни неоднородности являются целым значением от 8 до 128 со значением по умолчанию 64. Более высокое значение уровня неоднородности уменьшает минимальное обнаруженное расстояние. Кроме того, для большего размера входного изображения больший уровень дисперсии помогает лучше обнаруживать глубину объекта. Порог уникальности должен быть положительным целым значением, между 0 и 100 с типичной областью значений от 5 до 15. Более низкое значение порога уникальности помечает более надежные различия. Значение по умолчанию порога уникальности 5.

Симуляция и результаты

Пример модели может быть моделирован путем определения пути для входа изображений в блоках leftImage и rightImage. В примере используются выборочные изображения размера 640 на 480 пикселей. Рисунок показывает выборочное входное изображение и вычисленную карту расхождения. Модель экспортирует эти вычисленные расхождения и соответствующий допустимый сигнал в рабочее пространство MATLAB, используя имена переменных dispMap и dispMapValid соответственно. Выходная карта расхождения составляет 576 на 480 пикселей, поскольку первые 64 столбца не используются в расчете расхождения. Неиспользованные пиксели заполняются подсистемой 0 Выходов чтобы сгенерировать выходное изображение размера 640 480, как показано на Video Viewer. Карта расхождения с шкалой палитры генерируется с помощью команд, показанных ниже. Более высокие значения расхождения в результате указывают, что объект ближе к камере, а более низкие значения расхождения указывают на более дальние объекты.

dispMapValid = find(dispMapValid == 1);
disparityMap = (reshape(dispMap(dispMapValid(1:imgRowSize*imgColSize),:),imgColSize,imgRowSize))';
figure(); imagesc(disparityMap);
title('Disparity Map');
colormap jet; colorbar;

Пример модели совместим для генерации HDL-кода. Для генерации HDL-кода необходимо иметь лицензию на HDL Coder™. Проект был синтезирован для Intel ® Arria ® 10 GX (115S2F45I1SG) FPGA. В таблице ниже показано использование ресурсов для трех уровней несоответствия при различных разрешениях изображений. Рассматривая одну пару стерео входных изображений как система координат, пропускная способность алгоритма оценивается путем нахождения количества тактов, необходимых для обработки текущей системы координат до прихода следующей системы координат. Пропускная способность основного алгоритма, без служебных данных буферизации входных и выходных данных, является максимальной рабочей частотой, разделенной на минимальные циклы, необходимые между входными кадрами. Для примера для 128 уровней расхождения и 1280 на 720 разрешения изображения минимальные циклы обработки входного кадра составляют 938 857 тактов/кадр. Максимальная рабочая частота, полученная для алгоритма со 128 уровнями неоднородности, составляет 61,69 МГц, пропускная способность основного алгоритма вычисляется как 65 системы координат в секунду.

% ==================================================================================
% |Disparity Levels        ||       64       ||       96       ||        128       |
% ==================================================================================
% |Input Image Resolution  ||    640 x 480   ||    960 x 540   ||     1280 x 720   |
% |ALM Utilization         ||   45,613 (11%) ||   64,225 (15%) ||    85,194 (20%)  |
% |Total Registers         ||     49,232     ||     64,361     ||      85,564      |
% |Total Block Memory Bits || 3,137,312 (6%) || 4,599,744 (9%) || 11,527,360 (21%) |
% |Total RAM Blocks        ||    264 (10%)   ||    409 (16%)   ||      741 (28%)   |
% |Total DSP Blocks        ||     65 (4%)    ||     97 (6%)    ||      129 (8%)    |
% ==================================================================================

Ссылки

[1] Hirschmuller H., Точная и эффективная стерео обработка полуглобальным совпадением и взаимной информацией, Международная конференция по компьютерному зрению и распознаванию шаблона, 2005.

[2] Spangenberg R., Langner T., and Rojas R., Weighted Semi-Global Matching and Center-Symmetric Censes Transform for Robust Driver Assistance, Computer Analysis of imes and PatTrainturns, 2013.

[3] Gehrig S., Eberli F., and Meyer T., A Real-Time Low-Power Stereo Vision Engine Using Semi-Global Matching, International Conference on Компьютерное Зрение System, 2009.