Введение

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

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

Уровни несоизмеримости: уровни Несоизмеримости являются параметром, используемым, чтобы задать пространство поиска для соответствия. Как показано на рисунке ниже, алгоритм ищет каждый пиксель в Левом Изображении из числа пикселей 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. 0th пиксель сравнивается с 62-м (синим) пикселем, 1-й пиксель сравнивается с 61-м (красным) пикселем, и так далее, чтобы сгенерировать 31 результат. Каждый результат один битный выход и результат целого окна располагается как 31-битный номер. Этим 31-битным номером является CSCT выход для каждого пикселя в обоих изображениях.

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

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

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

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

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

Реализация HDL

Фигура ниже показов обзор модели в качестве примера. Блоки leftImage и rightImage импортируют пару стереоизображения, как введено к алгоритму. Во Входной подсистеме блок Frame To Pixels преобразует входные изображения от leftImage и блоков rightImage к пиксельному потоку и сопроводительным управляющим сигналам в pixelcontrol шина. Пиксельный поток передается как вход подсистеме 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 пиксельное окно путем выравнивания каждой группы пикселей для сравнения с помощью Коснувшейся Задержки (Simulink) блоки Для Каждой Подсистемы (Simulink) блоки и буферы. Входные пиксели дополнены нулями, чтобы позволить расчет CSCT для угловых пикселей. Получившийся поток пикселей передается ctLogic подсистеме. Изобразите ниже показов ctLogic подсистему, которая использует блок Tapped Delay, чтобы сгенерировать группу пикселей. Пиксели буферизуются для imgColSize циклы, где imgColSize является количеством пикселей в линии изображений. Группа пикселей, которая выравнивается для сравнения, сгенерирована из каждой строки. Блок For Each и блок Logical Operator реплицируют логику сравнения для каждого пикселя размера входного вектора. Чтобы реализовать 9 7 окно, модель использует четыре таких Для Каждого, блокируется. Результатом, сгенерированным каждым блоком For Each, является вектор, который далее конкатенирован, чтобы сформировать вектор из размера 31 бит. После того, как Битный Concat (HDL Coder) используется, типом выходных данных является uint5. CSCT и дополняющие нуль операции выполняются отдельно на левых и правых входных изображениях, и результаты передаются подсистеме Расстояния Хемминга.

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

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

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

Направленный расчет стоимости

Направленная подсистема Стоимости вычисляет несоизмеримость на уровне каждого пикселя в нескольких направлениях. Эти пять направлений, используемых в примере, слева направо (A1), верхняя часть, оставленная правому нижнему (A2), от начала до конца (A3), главное право на левую нижнюю часть (A4), и справа налево (A5). Когда агрегация стоимости на уровне каждого пикселя в каждом направлении независима друг от друга, все пять направлений реализованы одновременно.

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

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

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

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

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

Блок For Each используется, чтобы реплицировать минимальное вычисление пути к стоимости для каждого уровня несоизмеримости для каждого направления. Фигура ниже показов реализация A1 для 64 уровней несоизмеримости. Как показано на рисунке, 64 минимальных вычисления пути к стоимости сгенерированы, как представлено minCostPath подсистемой. Стоимость соответствия является входом от подсистемы Расстояния Хемминга. Текущая стоимость, вычисленная 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. Этот проект уменьшает использование памяти на чипе. Строки инвертируются после расчета CSCT и соответствия со стоимостью вычисляется с помощью отдельного модуля Расстояния Хемминга, который предоставляет вход Matching Cost A5. Кроме того, dataAligner подсистема используется, чтобы удалить разрыв данных для каждой строки прежде, чем передать его подсистемам Расстояния Хемминга. Это помогает легкой синхронизации данных во время агрегации. Текущая стоимость, полученная из всех пяти направлений на уровне каждого пикселя, агрегирована, чтобы получить общую стоимость на уровне каждого пикселя. Общая стоимость передается подсистеме Последующей обработки.

Последующая обработка

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

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

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

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

Модель в качестве примера может быть симулирована путем определения пути для входных изображений в блоках rightImage и leftImage. Пример использует демонстрационные изображения размера 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 Coder™, чтобы сгенерировать HDL-код. Проект синтезировался для 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] Хиршмаллер Х., точная и эффективная обработка стерео полуглобальной переменной, соответствующей и взаимной информацией, международной конференцией по вопросам компьютерного зрения и распознавания образов, 2005.

[2] Шпангенберг Р., Лэнгнер Т. и Рохас Р., Взвешенная Полуглобальная переменная, соответствующая и Центрально-симметричное Преобразование переписи для Устойчивой Помощи Драйвера, Компьютерного Анализа Изображений и Шаблонов, 2013.

[3] Гериг С., Эберли Ф., и Мейер Т., Engine видения стерео малой мощности в реальном времени Используя полуглобальное соответствие, международную конференцию по вопросам системы компьютерного зрения, 2009.