La coincidencia semiglobal ( SGM ) es un algoritmo de visión por computadora para la estimación de un mapa de disparidad denso a partir de un par de imágenes estéreo rectificadas , presentado en 2005 por Heiko Hirschmüller mientras trabajaba en el Centro Aeroespacial Alemán . [1] Dado su tiempo de ejecución predecible, su equilibrio favorable entre la calidad de los resultados y el tiempo de cálculo, y su idoneidad para una implementación paralela rápida en ASIC o FPGA , ha encontrado una amplia adopción en aplicaciones de visión estéreo en tiempo real como la robótica. y sistemas avanzados de asistencia al conductor . [2] [3]
Problema
La coincidencia estéreo por píxeles permite realizar cálculos en tiempo real de mapas de disparidad midiendo la similitud de cada píxel en una imagen estéreo con cada píxel dentro de un subconjunto en la otra imagen estéreo. Dado un par de imágenes estéreo rectificadas, para un píxel con coordenadas el conjunto de píxeles en la otra imagen generalmente se selecciona como , dónde es un cambio de disparidad máximo permitido. [1]
Una simple búsqueda del mejor píxel de coincidencia produce muchas coincidencias falsas, y este problema se puede mitigar con la adición de un término de regularización que penaliza los saltos en la disparidad entre píxeles adyacentes, con una función de costo en la forma.
dónde es el costo de disimilitud de píxeles en píxeles con disparidad , y es el costo de regularización entre píxeles y con disparidades y respectivamente, para todos los pares de píxeles vecinos . Dicha restricción se puede aplicar de manera eficiente por línea de exploración mediante el uso de programación dinámica (por ejemplo, el algoritmo de Viterbi ), pero dicha limitación aún puede introducir artefactos de rayas en el mapa de profundidad, porque se realiza poca o ninguna regularización a través de las líneas de exploración. [4]
Una posible solución es realizar la optimización global en 2D, que sin embargo es un problema NP-completo en el caso general. Para algunas familias de funciones de costo (por ejemplo, funciones submodulares ), se puede encontrar una solución con fuertes propiedades de optimización en tiempo polinómico usando optimización de corte de gráfico , sin embargo, tales métodos globales son generalmente demasiado costosos para el procesamiento en tiempo real. [5]
Algoritmo
La idea detrás de SGM es realizar la optimización de línea en múltiples direcciones y calcular un costo agregado sumando los costos para alcanzar el píxel con disparidad desde cada dirección. El número de direcciones afecta el tiempo de ejecución del algoritmo y, aunque 16 direcciones suelen garantizar una buena calidad, se puede utilizar un número menor para lograr una ejecución más rápida. [6] Una implementación típica de 8 direcciones del algoritmo puede calcular el costo en dos pasadas, una pasada hacia adelante acumulando el costo desde la izquierda, arriba a la izquierda, arriba y arriba a la derecha, y una pasada hacia atrás acumulando el costo desde la derecha. , abajo a la derecha, abajo y abajo a la izquierda. [7] Se puede implementar un algoritmo de un solo paso con solo cinco direcciones. [8]
El costo está compuesto por un término coincidente y un término de regularización binario . La primera puede ser, en principio, cualquier medida de disimilitud de imagen local, y las funciones de uso común son la diferencia de intensidad absoluta o cuadrada (generalmente se suma en una ventana alrededor del píxel y después de aplicar un filtro de paso alto a las imágenes para obtener cierta invariancia de iluminación), Disimilitud de Birchfield-Tomasi , distancia de Hamming de la transformada del censo , correlación de Pearson ( correlación cruzada normalizada ). Incluso la información mutua puede aproximarse como una suma sobre los píxeles y, por lo tanto, usarse como una métrica de similitud local. [9] El plazo de regularización tiene la forma
dónde y son dos parámetros constantes, con . La comparación de tres vías permite asignar una penalización menor para los cambios unitarios en la disparidad, permitiendo así transiciones suaves correspondientes, por ejemplo, a superficies inclinadas, y penalizando los saltos más grandes mientras se preservan las discontinuidades debido al término de penalización constante. Para preservar aún más las discontinuidades, el gradiente de la intensidad se puede utilizar para adaptar el término de penalización, porque las discontinuidades en profundidad generalmente corresponden a una discontinuidad en la intensidad de la imagen., configurando
por cada par de píxeles y . [10]
El costo acumulado es la suma de todos los costos para alcanzar el pixel con disparidad a lo largo de la dirección . Cada término se puede expresar de forma recursiva como
donde el costo mínimo en el píxel anterior se resta para la estabilidad numérica, ya que es constante para todos los valores de disparidad en el píxel actual y, por lo tanto, no afecta la optimización. [6]
El valor de la disparidad en cada píxel viene dado por , y se puede lograr una precisión de subpíxeles ajustando una curva en y sus costos vecinos y tomando el mínimo a lo largo de la curva. Dado que las dos imágenes en el par estéreo no se tratan simétricamente en los cálculos, se puede realizar una verificación de coherencia calculando la disparidad por segunda vez en la dirección opuesta, intercambiando el papel de la imagen izquierda y derecha e invalidando el resultado para el píxeles donde el resultado difiere entre los dos cálculos. Otras técnicas de posprocesamiento para el refinamiento de la imagen de disparidad incluyen filtrado morfológico para eliminar valores atípicos, controles de consistencia de intensidad para refinar regiones sin textura e interpolación para completar píxeles invalidados por controles de consistencia. [11]
El volumen de costos para todos los valores de y puede calcularse previamente y en una implementación del algoritmo completo, utilizando posibles cambios de disparidad y direcciones, cada píxel se visita posteriormente veces, por lo tanto, la complejidad computacional del algoritmo para una imagen de tamaño es . [7]
Variante de memoria eficiente
El principal inconveniente de SGM es su consumo de memoria. Una implementación de la versión de 8 direcciones de dos pasos del algoritmo requiere almacenar elementos, ya que el volumen de costo acumulado tiene un tamaño de y para calcular el costo de un píxel durante cada pasada es necesario realizar un seguimiento de la costos de ruta de su vecino izquierdo o derecho a lo largo de una dirección y de la costos de ruta de los píxeles en la fila superior o inferior a lo largo de 3 direcciones. [7] Una solución para reducir el consumo de memoria es calcular SGM en mosaicos de imágenes parcialmente superpuestos, interpolando los valores sobre las regiones superpuestas. Este método también permite aplicar SGM a imágenes muy grandes, que no cabrían en la memoria en primer lugar. [12]
Una aproximación de memoria eficiente de SGM almacena para cada píxel solo los costos de los valores de disparidad que representan un mínimo a lo largo de alguna dirección, en lugar de todos los posibles valores de disparidad. Es muy probable que el mínimo verdadero sea predicho por los mínimos a lo largo de las ocho direcciones, lo que arroja resultados de calidad similar. El algoritmo utiliza ocho direcciones y tres pasadas, y durante la primera pasada almacena para cada píxel el costo de la disparidad óptima a lo largo de las cuatro direcciones de arriba hacia abajo, más los dos valores inferiores y superiores más cercanos (para la interpolación de subpíxeles). Dado que el volumen de costes se almacena de forma dispersa, también es necesario almacenar los cuatro valores de disparidad óptima. En la segunda pasada, se calculan las otras cuatro direcciones ascendentes, completando los cálculos para los cuatro valores de disparidad seleccionados en la primera pasada, que ahora se han evaluado a lo largo de las ocho direcciones. Se calcula un valor intermedio de costo y disparidad a partir de la salida de la primera pasada y se almacena, y la memoria de las cuatro salidas de la primera pasada se reemplaza con los cuatro valores óptimos de disparidad y sus costos de las direcciones en la segunda pasada. Una tercera pasada vuelve a seguir las mismas direcciones utilizadas en la primera pasada, completando los cálculos de los valores de disparidad de la segunda pasada. A continuación, se selecciona el resultado final entre los cuatro mínimos del tercer pase y el resultado intermedio se calcula durante el segundo pase. [13]
En cada pasada se almacenan cuatro valores de disparidad, junto con tres valores de costo cada uno (el mínimo y sus dos costos vecinos más cercanos), más los valores de disparidad y costo del resultado intermedio, para un total de dieciocho valores por cada píxel, haciendo el total consumo de memoria igual a , a costa de una pasada adicional sobre la imagen. [13]
Ver también
- Reconstrucción 3D
- Visión estéreo por computadora
- Estructura del movimiento
Referencias
- ↑ a b Hirschmüller (2005), págs. 807-814
- ^ Hirschmüller (2011), págs. 178-184
- ^ Spangenberg y col. (2013), págs. 34–41
- ^ Hirschmüller (2005), p. 809
- ^ Hirschmüller (2005), p. 807
- ↑ a b Hirschmüller (2007), p. 331
- ^ a b c Hirschmüller y col. (2012), pág. 372
- ^ "OpenCV cv :: StereoSGBM Class Reference" . Archivado desde el original el 5 de octubre de 2019.
- ^ Kim y col. (2003), págs. 1033–1040
- ^ Hirschmüller (2007), p. 330
- ^ Hirschmüller (2007), p. 332-334
- ^ Hirschmüller (2007), p. 334-335
- ^ a b Hirschmüller y col. (2012), pág. 373
- Hirschmüller, Heiko (2005). "Procesamiento estéreo preciso y eficiente mediante coincidencia semi-global e información mutua". Conferencia IEEE sobre visión artificial y reconocimiento de patrones . págs. 807–814.
- Hirschmuller, Heiko (2007). "Procesamiento estéreo por coincidencia semiglobal e información mutua". Transacciones IEEE sobre análisis de patrones e inteligencia de máquinas . IEEE. 30 (2): 328–341. doi : 10.1109 / TPAMI.2007.1166 . PMID 18084062 .
- Hirschmüller, Heiko (2011). "Emparejamiento-motivación semi-global, desarrollos y aplicaciones". Semana fotogramétrica . 11 . págs. 173-184.
- Hirschmüller, Heiko; Buder, Maximiliano; Ernst, Ines (2012). "Emparejamiento semi-global eficiente de la memoria" . ISPRS Annals of the Photogrametry, Remote Sensing and Spatial Information Sciences . 3 : 371–376. Código bibliográfico : 2012ISPAn..I3..371H . doi : 10.5194 / isprsannals-I-3-371-2012 .
- Kim, Junhwan; Kolmogorov, Vladimir; Zabih, Ramin (2003). "Correspondencia visual mediante minimización de energía e información mutua". Actas de la Novena Conferencia Internacional IEEE sobre Visión por Computador . págs. 1033–1040.
- Spangenberg, Robert; Langner, Tobias; Rojas, Raúl (2013). "Emparejamiento semi-global ponderado y transformación del censo simétrico al centro para una asistencia robusta al conductor". Congreso Internacional de Análisis Informático de Imágenes y Patrones . págs. 34–41.
enlaces externos
- "Visión estéreo" . Archivado desde el original el 1 de enero de 2019.