OpenCV ORB дескриптор - как именно он хранится в наборе байтов?

В настоящее время я использую экстрактор возможностей OpenCV ORB, и я заметил странный (по крайней мере для меня) способ хранения ORB-дескриптора (это в основном BRIEF-32 с модификацией, не относящейся к моему вопросу), Поскольку некоторые из вас знают, что ORB извлекает ключевые точки, используя модифицированный FAST-9 (радиус окружности = 9 пикселей, также сохраняет ориентацию ключевой точки) и использует те, у которых есть модифицированный дескриптор BRIEF-32, для хранения функции, отображаемой ключевой точкой.

BRIEF (версия ORB) работает следующим образом: мы берем патч 31x31 пикселей (представляет собой функцию) и создаем кучу случайных контрольных точек 5x5 пикселей. Затем мы берем пары этих точек и оцениваем их интенсивности, приводящие к двоичному решению (0 или 1), исходя из того, является ли интенсивность первой точки в паре большей или меньшей, чем интенсивность второй. Затем мы берем все эти биты и используем базовую формулу sum для построения двоичной строки длины n (для BRIEF-32 у нас есть 32 байта * 8 = двоичная строка длиной 256 бит):

СУММА (2 ^(I-1) * bit_pair_test)

где бит_pair_test - это битовое значение, которое мы вычислили из теста для пары тестовых точек. Конечным результатом является что-то вроде (для набора бинарных тестов (..., 0,1,0,1,1)):

(2 ⁰ * 1) + (2 ¹ * 1) + (2 ² * 0) + (2 ³ * 1) + (2 ⁴ * 0) +...

Теперь то, что OpenCV ORB хранит эти биты, - вот что для меня загадка. Если мы посмотрим на матрицу, содержащую дескрипторы для целого изображения, причем каждая строка является единственным дескриптором для одной ключевой точки, мы можем видеть, что каждый дескриптор имеет 32 8-битных номера, что в итоге приводит к тем 256 битам, которые использует BRIEF-32 для хранения информации. Я не понимаю, почему мы разделили эти 256 бит в 32 байт. Официальная документация (http://docs.opencv.org/trunk/doc/py_tutorials/py_feature2d/py_brief/py_brief.html) говорит только о том, что OpenCV хранит такие дескрипторы в байтах, однако это не объясняет, почему это происходит. Я рассмотрел три возможности, не исключая возможности того, что какая-то комбинация из них может быть ответом:

Некоторая техника хранения, которую я просто не вижу
Некоторая проблема с производительностью при вычислении расстояния Хэмминга для бинарной строки, которая длинна (256 бит в нашем случае)
Оптимизация процесса сопоставления - сопоставление в основном сравнивает дескриптор ключевой точки с одним изображением с дескриптором ключевой точки во втором изображении. Поскольку у нас есть бинарные строки, то выбор Хэмминга - очевидный выбор. Возможно, что каждая из этих 32 подстрок сравнивается со своими коллегами в дескрипторе другой ключевой точки во втором изображении (подстрока в позиции 0 (ключевая точка X, изображение 1) с подстрокой в позиции 0 ( ключевая точка Y, изображение 2). Наконец, может быть, что OpenCV говорит: "Хорошо, мы имеем 80% -ную скорость совпадения дескриптора, так как приблизительно 26 из всех подстрок одинаковы в обоих дескрипторах), поэтому у нас есть победитель". Однако я не смог найти никаких доказательств, подтверждающих это.

PS: Вы можете прочитать статью на ORB здесь и статью о BRIEF здесь.

Ответ 1

Выбор шаблона с 8 и 32 битами обусловлен проблемами хранения и эффективности.

Соответствующий процесс

Порядок бит в BRIEF, ORB и BRISK не имеет значения (в отличие от FREAK). Таким образом, все биты этих дескрипторов имеют одинаковую значимость, и вы не можете просто сравнить первую часть потока битов и т.д.

С другой стороны, FREAK был разработан с таким процессом согласования (называемым каскадом в документе FREAK).

Проблемы с хранением

Ну, компьютеры не хранят отдельные биты. Таким образом, вы не увидите никого, кто хранит BRIEF и т.п. в битовых массивах.

Самый маленький компонент, который может быть прочитан из памяти, является байтом (обычно 8 бит, хотя некоторые DSP не могут читать фрагменты размером менее 16 бит, но это другая история). Таким образом, вы можете видеть, как люди хранят свои дескрипторы в массивах байтов (тип unsigned char в C/С++, который является основным языком реализации OpenCV).

Кроме того, доступ к памяти обычно лучше (быстрее), когда переменные выровнены по границам слов ЦП. В настоящее время большинство процессоров имеют слова 32 или 64 бит, а 32-битные слова - лучший выбор, потому что 64-битные архитектуры были разработаны с учетом унаследованных 32-битных процессоров.

Проблемы с эффективностью

Расстояние Хэмминга вычисляется с помощью операции XOR. Бывает, что многие процессоры имеют выделенные наборы инструкций, которые могут эффективно вычислять XOR с 32-битными словами (общий размер целого числа до 64-битных процессоров стал более распространенным). Более того, они могут также поддерживать вычисление нескольких значений XOR на нескольких 32-битных словах параллельно, что представляет собой метод parallelism, называемый SIMD (Single Input Multiple Data). Например, расширения SSE могут быть использованы для дальнейшего ускорения вычисления расстояния Хэмминга дескрипторов BRIEF/ORB/..., размер которых кратен 32 битам.