force - Descriptor ORB de OpenCV: ¿cómo se almacena exactamente en un conjunto de bytes?

sift in python opencv

Question

Actualmente estoy usando el extractor de características ORB de OpenCV y noté la forma extraña (al menos para mí) de almacenar el descriptor ORB (básicamente es un BREVE-32 con una modificación que no es relevante para mi pregunta). Como algunos de ustedes saben, ORB toma los puntos clave extraídos utilizando un FAST-9 modificado (radio de círculo = 9 píxeles, también almacena la orientación del punto clave) y usa aquellos con un descriptor BRIEF-32 modificado para almacenar la característica que representa el punto clave.

BREVE (versión ORB) funciona de la siguiente manera: tomamos un parche de 31x31 píxeles (representa una función) y creamos un montón de puntos de prueba aleatorios de 5x5 píxeles. Luego tomamos pares de esos puntos y evaluamos sus intensidades, dando como resultado una decisión binaria (0 o 1) en función de si la intensidad del primer punto del par es mayor o menor que la intensidad del segundo. Luego tomamos todos esos bits y usamos una fórmula suma básica para construir una cadena binaria de longitud n (para BRIEF-32 tenemos 32 bytes * 8 = cadena binaria de 256 bits de longitud):

SUM (2 ^(i-1) * bit_pair_test)

donde bit_pair_test es el valor de bit que hemos calculado a partir de la prueba para un par de puntos de prueba. El resultado final es algo así como (para un conjunto de pruebas binarias (..., 0,1,0,1,1)):

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

Ahora, la forma en que el ORB de OpenCV almacena esas cadenas de bits es lo que es un misterio para mí. Si observamos la matriz que contiene los descriptores de una imagen completa, cada fila es un descriptor único para un solo punto clave, podemos ver que cada descriptor tiene 32 números de 8 bits, lo que en conjunto da como resultado los 256 bits que utiliza BRIEF-32 para almacenar la información. No entiendo por qué dividimos esos 256 bits en 32 bytes . La documentación oficial ( http://docs.opencv.org/trunk/doc/py_tutorials/py_feature2d/py_brief/py_brief.html ) solo dice que OpenCV almacena dichos descriptores en bytes, sin embargo, no explica por qué lo hace. He considerado tres posibilidades sin excluir la posibilidad de que una combinación de ellas sea la respuesta:

• Alguna técnica de almacenamiento que simplemente no puedo ver
• Algún problema de rendimiento con la computación de la distancia de Hamming para una cadena binaria tan larga (256 bits en nuestro caso)
• Optimización en el proceso de correspondencia: la comparación básicamente compara el descriptor de un punto clave de una imagen con el descriptor de un punto clave en una segunda imagen. Debido a que tenemos cadenas binarias, la distancia de Hamming es la elección obvia aquí. Puede ser que de alguna manera cada una de esas 32 sub-cadenas se compare con sus contrapartes en el descriptor del otro punto clave en la segunda imagen (subcadena en la posición 0 (punto clave X, imagen 1) con subcadena en la posición 0 ( punto clave Y, imagen 2). Finalmente, es posible que OpenCV diga: "De acuerdo, tenemos una tasa de coincidencia del 80% del descriptor, ya que aproximadamente 26 de todas las subcadenas son iguales en ambas descripciones), así que tenemos un ganador". Sin embargo, no pude encontrar ninguna evidencia para confirmar eso.

PD: Puedes leer el artículo sobre ORB aquí y el documento sobre BREVE aquí .

Answer 1

La elección del patrón de 8 y 32 bits se debe a problemas de almacenamiento y eficiencia.

• Proceso de coincidencia

El orden de bits en BREVE, ORB y BRISK no es relevante (a diferencia de FREAK). Por lo tanto, todos los bits de estos descriptores tienen la misma importancia, y no se puede simplemente comparar la primera parte del flujo de bits, etc.

Por otro lado, FREAK se diseñó teniendo en cuenta un proceso de coincidencia (llamado cascada en el artículo de FREAK).

• Problemas de almacenamiento

Bueno, las computadoras no almacenan bits individuales. Por lo tanto, no verá a nadie almacenando BREVE y similares en arreglos de bits.

El componente más pequeño que se puede leer de la memoria es un byte (que corresponde generalmente a 8 bits, aunque algunos DSP no pueden leer fragmentos de menos de 16 bits, pero esa es otra historia). Por lo tanto, podría ver a las personas almacenar sus descriptores en matrices de bytes (escriba unsigned char en C / C ++, que es el lenguaje subyacente de implementación de OpenCV).

Además, los accesos a la memoria suelen ser mejores (más rápidos) cuando las variables están alineadas en los límites de palabras de la CPU. La mayoría de las CPU hoy en día tienen palabras de 32 o 64 bits, siendo la mejor elección las palabras de 32 bits porque las arquitecturas de 64 bits se diseñaron teniendo en cuenta los procesadores heredados de 32 bits.

• Problemas de eficiencia

La distancia de Hamming se calcula a través de una operación XOR. Sucede que muchos procesadores tienen conjuntos de instrucciones dedicados que pueden calcular XOR de manera eficiente con palabras de 32 bits (el tamaño común de un entero antes de que las CPU de 64 bits se hicieran más comunes). Aún más, también pueden ayudar a computar varios valores XOR en múltiples palabras de 32 bits en paralelo , que es una técnica de paralelismo llamada SIMD (datos múltiples de entrada única). Por ejemplo, las extensiones de SSE se pueden aprovechar para acelerar aún más el cálculo de la distancia de Hamming de los descriptores BRIEF / ORB / ... cuyo tamaño es un múltiplo de 32 bits.