Alternativas más rápidas a cvFindContour()

Question

La detección de contornos ocupa la mayor parte de mi tiempo en la visión de mi computadora, y necesita ser más rápida. He optimizado todo lo demás a través de las instrucciones de NEON y vectorizando que realmente, la detección de contorno domina el perfil. Desafortunadamente, no es obvio para mí cómo optimizar esto.

Estoy haciendo el proceso de detección de rectángulo clásico para encontrar marcadores fiduciales, es decir, cvFindContours(), seguido de cuadrados aproximados de los contornos. En casos con muchos, muchos marcadores visibles (o catastróficamente, cuando una cuadrícula densa de rectángulos que no son marcadores es visible), la llamada a cvFindContours() sola puede tomar más de 30ms en un iPhone.

Ya he reemplazado el increíblemente costoso C++ cv :: FindContours() con cvFindContours(). Particularmente si se pasa un vector>, la versión C++ pasó más tiempo asignando y poblando vectores que su cvFindContours() interno.

Ahora, estoy completamente vinculado por el tiempo en cvFindContours, o más específicamente en cvFindNextContour(). El código dentro de cvFindNextContour es ramificado, y obviamente no es fácil de vectorizar. También implementa un algoritmo complejo en el que no confío para no equivocarme en ningún intento de optimización.

Ya he visto cvBlobLib (para la desambiguación, me refiero a este: http://code.google.com/p/cvblob/) para ver si proporcionaba algoritmos alternativos que pudieran hacer lo mismo más rápido. Una descarga base de la fuente es increíblemente lenta porque registra los contornos en std :: list() y pasa casi todo el tiempo en la asignación de memoria. Reemplazar esa lista con std :: vector pre-sized a 256 elementos para eliminar las copias iniciales en push_back() aún te deja con una función que tarda 3 veces más que cvFindContours(), 66% de eso directamente en cvb :: cvLabel () Entonces no parece viable ir por este camino.

¿Alguien tiene alguna idea de cómo puedo optimizar la detección de muchos rectángulos? Mi handwaving vaga incluye:

1. ¿Hay algunas implementaciones rápidas equivalente a cvFindContour(), idealmente como código fuente que a mí multiplataforma, por ahí?

2. La mayoría de los contornos no son necesarios, solo los rectángulos "exitosos" son útiles. En particular, sus contornos internos no son útiles. Teóricamente, ¿no podría llamar a cvFindContours y, en su lugar, llamar a cvStartFindContours/cvFindNextContour, probar cada contorno como encontrado y no recurrir si encuentro un rectángulo que estoy buscando, ya que entonces se garantiza que los subrectangles serán inútiles?

3. ¿Hay algún algoritmo de detección de rectángulo completamente diferente que pueda usar desde el enfoque clásico FindContours()/ApproxPoly()?

4. ¿Hay alguna manera de "preparar" cvFindContours con las regiones útiles de interés? P.ej. una detección de esquina RÁPIDA casi siempre devuelve las esquinas de mi marcador de referencia incluso con un umbral muy agresivo. ¿Hay alguna manera de usar ese punto establecido para limitar la detección? (Desafortunadamente, no estoy seguro de cuánto ayuda esto, una vez más en el caso de muchos marcadores, o grillas densas no relacionadas con los marcadores, lo que sucede a menudo en mi aplicación).

5. En la misma línea que arriba, ya La detección de blobs puede (si lo entiendo correctamente) implementarse como rellenado recursivo de inundaciones, ¿hay implementaciones vectorizadas rápidas de esto que luego se puedan usar para extraer de algún modo rectángulos de Blob interesantes y detección de contornos de semillas desde allí?

¡Cualquier idea sería bienvenida!

Answer 1

Dado que su objetivo es la detección de rectángulo y no la detección de contorno, le sugiero que haga uso de imágenes integrales para el cálculo. Se puede encontrar una explicación de las imágenes integrales here. Después de calcular la imagen integral de la imagen deseada, se puede calcular la suma de píxeles de un rectángulo con tres operaciones.

Suponiendo que desea dibujar rectángulos alrededor de cada objeto no negro, puede utilizar un método de la siguiente manera. Recursivamente siga dividiendo la imagen y sus subimágenes a 4 y descarte los rectángulos con una suma de píxeles por debajo de su umbral deseado. Te quedarán muchos rectángulos pequeños que se aproximan a tus objetos. La combinación de los rectángulos vecinos proporcionará una aproximación rápida de los objetos detectados.