В этом примере показано, как вычислить различия между изображениями левой и правой стереокамер с помощью алгоритма сопоставления полуглобальных блоков. Этот алгоритм подходит для реализации на FPGA.
Оценка расстояния является важным измерением для приложений в области автоматизированного вождения и робототехники. Экономически эффективным способом оценки расстояния является использование стереокамеры. При использовании стереокамеры глубина может быть выведена из точечных соответствий с помощью триангуляции. Глубина в любой заданной точке может быть вычислена, если разность в этой точке известна. Несоответствие измеряет смещение точки между двумя изображениями. Чем выше несоответствие, тем ближе объект.
В этом примере вычисляется несоответствие с помощью метода SGBM (Semi-Global Block Matching), аналогичного disparity (Панель инструментов компьютерного зрения). Метод SGBM представляет собой подход, основанный на интенсивности, и создает плотную и гладкую карту различий для хорошей реконструкции 3D. Однако для достижения производительности в реальном времени требуется аппаратное ускорение с использованием FPGA или GPU.
Приведенная здесь примерная модель совместима с аппаратным обеспечением FPGA и поэтому может обеспечивать производительность в реальном времени.
Алгоритмы оценки различий подразделяются на две широкие категории: локальные методы и глобальные методы. Локальные методы вычисляют один пиксель за один раз, рассматривая только соседние пиксели. Глобальные методы учитывают информацию, доступную во всем изображении. Локальные методы плохо обнаруживают внезапное изменение глубины и окклюзии, и, следовательно, предпочтительны глобальные методы. Полуглобальное сопоставление использует информацию из соседних пикселей в нескольких направлениях для вычисления различия пикселя. Анализ в нескольких направлениях приводит к большому количеству вычислений. Вместо использования всего изображения диспаритет пикселя может быть вычислен путем рассмотрения меньшего блока пикселей для простоты вычисления. Таким образом, алгоритм полуглобального согласования блоков (SGBM) использует сопоставление затрат на основе блоков, которое сглаживается информацией по путям из множества направлений.
Используя блочный подход, этот алгоритм оценивает приблизительное несоответствие пикселя в левом изображении от того же пикселя в правом изображении. Более подробную информацию о Stereo Vision можно найти здесь. Прежде чем перейти к алгоритму и деталям реализации, необходимо понять два важных параметра: Уровни несопоставимости и Количество направлений.
Уровни несоответствия - это параметр, используемый для определения пространства поиска для сопоставления. Как показано на рисунке ниже, алгоритм выполняет поиск каждого пикселя в левом изображении из числа D пикселей в правом изображении. Генерируемые значения D представляют собой уровни D различия для пикселя в левом изображении. Первые D-столбцы левого изображения не используются, поскольку соответствующие пикселы в правом изображении недоступны для сравнения. На рисунке w представляет ширину изображения, а h - высоту изображения. Для заданного разрешения изображения увеличение уровня рассогласования уменьшает минимальное расстояние для определения глубины. Увеличение уровня несоответствия также увеличивает вычислительную нагрузку алгоритма. При заданном уровне несоответствия увеличение разрешения изображения увеличивает минимальное расстояние для обнаружения глубины. Увеличение разрешения изображения также повышает точность оценки глубины. Количество уровней рассогласования пропорционально разрешению входного изображения для обнаружения объектов на одной глубине. В этом примере поддерживаются уровни различий от 8 до 128 (оба значения включительно). Объяснение алгоритма относится к 64 уровням несоответствия. Модели, представленные в этом примере, могут принимать входные изображения любого разрешения.
Количество направлений: В алгоритме SGBM для оптимизации функции затрат входное изображение рассматривается с нескольких направлений. В целом точность результата рассогласования повышается с увеличением числа направлений. В этом примере анализируются пять направлений: слева направо (A1), сверху слева направо (A2), сверху вниз (A3), сверху справа вниз налево (A4) и справа налево (A5).
Алгоритм SGBM принимает в качестве входных данных пару исправленных левого и правого изображений. Пиксельные данные из необработанных изображений могут не иметь идентичных вертикальных координат из-за незначительных изменений положений камеры. Изображения необходимо исправить перед выполнением стереосогласования, чтобы сделать все эпи-полярные линии параллельными горизонтальной оси и согласовать вертикальные координаты каждого соответствующего пикселя. Для получения дополнительной информации по исправлению см. rectifyStereoImages (Панель инструментов компьютерного зрения). На рисунке показана блок-схема алгоритма 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 в данной позиции p пикселя в левом изображении вычисляется путем вычисления расстояния Хэмминга с позициями (p-D + p) пикселей в правом изображении. Стоимость согласования, C (p, d), вычисляется в каждой позиции пикселя, p, для каждого уровня различия, d. Стоимость согласования не вычисляется для позиций пикселей, соответствующих первым D столбцам левого изображения.
Вторым модулем алгоритма СГБМ является оценка затрат по направлению. В общем, из-за шума результат стоимости сопоставления неоднозначен и некоторые неправильные совпадения могут иметь более низкую стоимость, чем правильные. Поэтому требуются дополнительные ограничения для повышения гладкости путем наказания за изменения соседних различий. Это ограничение реализуется путем агрегирования путей 1-D минимальными затратами из нескольких направлений. Он представлен агрегированной стоимостью из r направлений в каждой позиции пикселя, S (p, d), как дано
1-D путь минимальных затрат для данного направления, L_r (p, d), вычисляется, как показано в уравнении.
Как упоминалось выше, в этом примере используются пять направлений для вычисления различий. Распространение в каждом направлении является независимым. Результирующие различия на каждом уровне от каждого направления агрегируются для каждого пикселя. Общая стоимость - это сумма затрат, рассчитанных для каждого направления.
Третий модуль алгоритма SGBM - постобработка. Этот модуль состоит из трех этапов: расчет индекса минимальной стоимости, интерполяция и функция уникальности. При вычислении индекса минимальной стоимости обнаруживается индекс, соответствующий минимальной стоимости для данного пикселя. Квадратичная интерполяция под-пикселей применяется к индексу для разрешения расхождений на уровне под-пикселей. Функция уникальности обеспечивает надежность вычисленного минимального несоответствия. Более высокое значение порога уникальности означает, что больше различий ненадежно. В качестве последнего шага отрицательные значения различия признаются недействительными и заменяются на -1.
На рисунке ниже показан обзор примерной модели. Блоки leftImage и reyImage импортируют пару стереоизображений в качестве входных данных алгоритма. В подсистеме ввода блок Frame To Pixels преобразует входные изображения из блоков leftImage и reyImage в поток пикселей и сопровождающие управляющие сигналы в pixelcontrol bus. Поток пикселей передается в качестве входных данных в подсистему SGBMHDLAlgorithm, которая содержит три модуля вычислений, описанных выше: расчет затрат на согласование, расчет затрат на направление и последующую обработку. Выходной сигнал подсистемы SGBMHDLAlgorithm представляет собой поток пикселей с разностным значением. В подсистеме «Output» блок «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, которая использует блок задержки с отводом для генерации группы пикселей. Пикселы буферизуются для imgColSize циклов, где imgColSize - количество пикселей в строке изображения. Группа пикселей, выровненная для сравнения, генерируется из каждой строки. Блоки «Для каждого блока» и «Логический оператор» воспроизводят логику сравнения для каждого пикселя размера входного вектора. Для реализации окна «9 на 7» модель использует четыре таких блока «Для каждого». Результатом, генерируемым каждым блоком Для каждого, является вектор, который дополнительно конкатенируется для формирования вектора размером 31 бит. После использования Bit Concat (кодер HDL) тип выходных данных: uint5. Операции CSCT и заполнения нулем выполняются отдельно на левом и правом входных изображениях и результаты передаются в подсистему Hamming Distance.
open_system('SGBMDisparityExample/SGBMHDLAlgorithm/MatchingCost/CensusTransform/ctLogic','force');
В подсистеме Hamming Distance 65-м результатом левого CSCT является XOR 'd с 65-м по 2-й результатами правого CSCT. Установленные биты подсчитываются для получения расстояния Хэмминга. Это расстояние должно быть рассчитано для каждого уровня различия. Правый результат CSCT передается в подсистему enabledTedDelay для генерации группы пикселей, которая затем является XOR с левым результатом CSCT с использованием блока 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.
Путь к 1-D минимальным затратам вычисляет текущую стоимость на позиции d disparity, используя значение Matching Cost, значения предыдущих затрат на разностях d-1, d и d + 1 и минимальное из значений предыдущих затрат. На рисунке ниже показана подсистема пути минимальной стоимости, которая вычисляет текущую стоимость в позиции несоответствия для пикселя.
open_system('SGBMDisparityExample/SGBMHDLAlgorithm/DirectionalCost/LeftToRight/lrSubsystem/minCostPath','force');
Блок «Для каждого» используется для репликации вычисления пути минимальной стоимости для каждого уровня несоответствия для каждого направления. На рисунке ниже показана реализация A1 для 64 уровней различий. Как показано на рисунке, генерируются 64 вычисления пути минимальной стоимости, представленные подсистемой minCostPath. Затраты на согласование являются входными данными подсистемы Hamming Distance. Текущая стоимость, вычисленная подсистемой minCostPath, немедленно возвращается к себе в качестве предыдущих значений стоимости для следующего текущего вычисления стоимости. Таким образом, значения для prevCost_d теперь доступны. Значения для prevCost_d-1 получают смещением значений с 1-й по 63-ю обратную подачу на позиции со 2-й по 64-ю. Подсистема d-1 содержит блок селектора (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. Затем требуется отдельный модуль Hamming Distance для вычисления стоимости сопоставления для A5. Такая конструкция сокращает использование встроенной памяти. Строки сторнируются после вычисления CSCT, и затраты на согласование вычисляются с использованием отдельного модуля Hamming Distance, который обеспечивает ввод затрат на сопоставление для A5. Кроме того, подсистема dataAligner используется для удаления разрывов данных для каждой строки перед передачей ее подсистемам Hamming Distance. Это упрощает синхронизацию данных во время агрегирования. Текущие затраты, полученные из всех пяти направлений на каждом пикселе, агрегируются для получения общей стоимости на каждом пикселе. Общая стоимость передается в подсистему постобработки.
В подсистеме постобработки индекс минимальной стоимости вычисляется на каждой позиции пикселя из 64 уровней несоответствия с использованием блоков Мин в древовидной архитектуре. Полученное значение индекса является разностью каждого пикселя. Наряду с вычислением индекса минимальных затрат вычисляются также значение минимальных затрат при вычисленном индексе и значения затрат при индексе-1 и индексе + 1. Подсистема Minimum_Cost_Index реализует архитектуру дерева для вычисления минимального значения из 128 значений. 64 значения несоответствия дополняются еще 64 значениями, чтобы сделать вектор из 128 значений. Минимальное значение вычисляется по этому вектору со 128 значениями. В случае, когда вектор со 128 значениями доступен, значение не заполняется вектором или, другими словами, вектор передается непосредственно для вычисления минимального значения. Variant Subsystem, Variant Model (Simulink) используется для выбора между логикой с использованием переменных подсистемы вариантов. Затем к индексу применяется квадратичная интерполяция под-пикселей для разрешения несоответствия на уровне под-пикселей. Кроме того, функция уникальности применяется к индексу, вычисляемому минимальными блоками, для обеспечения надежных результатов различия. В качестве последнего шага недействительные различия идентифицируются и заменяются на -1.
Представленная здесь модель принимает уровни различия и порог уникальности в качестве входных параметров, как показано на рисунке. Уровни несоответствия представляют собой целое число от 8 до 128 со значением по умолчанию 64. Более высокое значение уровня несоответствия уменьшает минимальное обнаруженное расстояние. Кроме того, для большего размера входного изображения больший уровень различия помогает лучше обнаруживать глубину объекта. Порог уникальности должен быть положительным целым числом от 0 до 100 с типичным диапазоном от 5 до 15. Более низкое значение порога уникальности указывает на более надежные различия. Значение порога уникальности по умолчанию равно 5.
Модель примера может быть смоделирована путем указания пути для входных изображений в блоках leftImage и reyImage. В примере используется образец изображений размером 640 на 480 пикселей. На рисунке показан образец входного изображения и вычисленная карта несоответствия. Модель экспортирует эти вычисленные различия и соответствующий действительный сигнал в рабочую область MATLAB с использованием имен переменных. dispMap и dispMapValid соответственно. Выходная карта рассогласования составляет 576 на 480 пикселей, поскольку первые 64 столбца не используются при вычислении рассогласования. Неиспользуемые пиксели дополняются 0 в подсистеме вывода для формирования выходного изображения размером 640-на-480, как показано в Video Viewer. С помощью команд, показанных ниже, создается карта различий с colorbar. Более высокие значения рассогласования в результате указывают на то, что объект находится ближе к камере, а более низкие значения рассогласования указывают на более удаленные объекты.
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™. Конструкция была синтезирована для FPGA Intel ® Arria ® 10 GX (115S2F45I1SG). В таблице ниже показано использование ресурсов для трех уровней несоответствия при различных разрешениях изображений. Рассматривая одну пару стерео входных изображений как кадр, пропускная способность алгоритма оценивается путем нахождения количества тактовых циклов, необходимых для обработки текущего кадра до прихода следующего кадра. Пропускная способность основного алгоритма без служебных данных буферизации входных и выходных данных представляет собой максимальную рабочую частоту, деленную на минимальные циклы, требуемые между входными кадрами. Например, для 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] Гериг С., Эберли Ф. и Мейер Т., движок стереовидения с низкой мощностью в реальном времени с использованием полуглобального сопоставления, Международная конференция по системе компьютерного зрения, 2009.