Clasificación de objetos así como reconocimiento de su posición y orientación en el espacio.

Procedimiento para la clasificación de objetos (16) y para el reconocimiento de su posición y orientación en elespacio,

en que con una disposición captadora (18) con resolución de distancia son generados puntos de datos delobjeto medido para una superficie del objeto medido y con ayuda de datos de objeto modelado previamentedeterminados son planteadas y verificadas a partir de los puntos de datos del objeto medido hipótesis acerca de laclase, la posición y la orientación de un objeto medido (16), en que varias pruebas de hipótesis diferentes sonrealizadas en cascada de tal modo que sólo en caso de verificación de una hipótesis mediante una prueba dehipótesis es realizada una prueba de hipótesis subsiguiente dentro de la cascada, hasta que por fallo de una pruebade hipótesis una hipótesis es falsificada o por paso completo a través de la cascada sin falsificación una hipótesis esverificada en conjunto, caracterizado porque la cascada de pruebas de hipótesis incluye los siguientesprocedimientos en esta secuencia: una prueba de caja delimitadora (bounding-box), en la que una selección depuntos de datos del objeto medido es comprobada acerca de si está situada dentro de un cuerpo envolvente delobjeto modelado, una prueba de imagen de distancia (range-image), en la que una imagen de distancia real delobjeto medido (16) es comparada con una imagen de distancia ficticia de un objeto modelado conforme a la clase,posición y orientación hipotéticas, una prueba de vecino más próximo (nearest-neighbour), en la que puntos de unamalla del objeto medido (16) son comparados con los vecinos más próximos de una malla de un objeto modeladohipotético, y una prueba de si tras una optimización de posición y orientación, en la que los puntos de datos delobjeto medido son llevados a coincidencia óptima con una malla de superficie de un objeto modelado, una partesuficientemente grande del objeto medido 16 se solapa de forma suficientemente próxima con el objeto modelado.

Clasificación de objetos así como reconocimiento de su posición y orientación en el espacio La invención se refiere a un procedimiento para la clasificación de objetos y/o para el reconocimiento de su posición y/u orientación en el espacio según el preámbulo de la reivindicación 1, así como a un dispositivo correspondiente según el preámbulo de la reivindicación 12.

La clasificación automatizada de objetos tridimensionales reales plantea grandes exigencias a la sensórica y al tratamiento subsiguiente. Un campo de aplicación importante es la técnica de almacenamiento y de transporte por ejemplo en la rama del automóvil o en otros campos. En este caso deben reconocerse forma y posición de objetos, para poder traspasar las tareas a realizar a sistemas autónomos de robots. Si en este caso no tienen que recorrerse sólo trayectorias fijamente predeterminadas, estos sistemas deben poseer la capacidad de adecuar adaptativamente sus modos de operación al entorno. En concreto se podría tratar aquí del despaletizado de componentes o de su montaje, en que el control de agarre del robot necesita la situación exacta de los objetos, para seleccionar la herramienta de agarre adecuada y situarla.

Los robots de montaje actuales agarran los componentes a montar la mayoría de las veces aún desde dispositivos mecánicos, que han sido diseñados especialmente para esta aplicación y que fijan unívocamente la posición así como la clase del componente. Con ello desaparece la necesidad de una clasificación, pero el sistema es también correspondientemente inflexible, y en realidad se desearía poder agarrar los componentes directamente desde una caja de transporte o desde una cinta transportadora.

La sensórica de sistemas habituales emplea para la determinación de la clase y la posición de los objetos la mayoría de las veces aún algoritmos, en los cuales los objetos están modelados sólo en dos dimensiones. En la reducción de tres a dos dimensiones pueden perderse sin embargo demasiadas informaciones, de modo que la clasificación de los objetos no puede ser fijada ya unívocamente. Las aplicaciones pueden ser solucionadas por ello la mayoría de las veces sólo de forma específica para la tarea y no son portables. En general, la posición y la orientación de los objetos no puede ser arbitraria, para evitar errores de clasificación.

Por ello es deseable captar objetos de forma tridimensional y determinar con ello su situación con tres grados de libertad de posición y tres grados de libertad de orientación en el espacio. Estos seis grados de libertad son denominados en lo que sigue frecuentemente como situación hexadimensional o 6D del objeto.

En el estado de la técnica son conocidos planteamientos para generar hipótesis acerca de la clase del objeto y su situación 6D a partir de nubes de puntos tridimensionales o representaciones de otro tipo de la superficie del objeto y verificarlas a continuación con una estrategia de prueba. Aquí se plantea sin embargo la elección de aceptar una estrategia rápida con una tasa elevada de errores o emplear una estrategia de verificación precisa y computacionalmente costosa, cuyo tiempo de operación es en la práctica sin embargo demasiado alto medido por ejemplo respecto a la velocidad de transporte de los objetos delante de un robot.

Para el empleo en procedimientos tridimensionales de este tipo son conocidos entre otras cosas descriptores 3D, que tienen como base distribuciones de propiedades de objetos en forma de histogramas. Entre ellos están las imágenes de revolución (spin images) , contextos de forma 3D (3D-shape contexts) , el método de hashing (dispersión) geométrico o COSMOS. Para informaciones adicionales en particular respecto a imágenes de revolución se hace referencia de forma complementaria a la publicación de Andrew E. Johnson, “Spin-Images: A representation for 3D-Surface Matching”, Tesis, Carnegie Mellon University, Pittsburgh, Pennsylvania, EE. UU. Para aplicaciones en la técnica de automatización apoyada por robots, los resultados de todos modos no son suficientemente precisos dentro de un tiempo de operación aceptable.

Un algoritmo conocido para la verificación de hipótesis es el algoritmo RANSAC (del inglés “RANdom SAmple Consensus”, consenso de muestra aleatoria) de Fischler et al. a partir de “Random sample consensus: a paradigm for model fitting with applications to image analyses and automated cartography”, Communications of the ACM, vol. 24/6, junio de 1981, ACM Press 1981. En este caso se escoge una selección aleatoria de puntos de datos, para generar una hipótesis, preferentemente la selección más pequeña posible que permita una afirmación, y esto se repite iterativamente hasta que pueda verificarse una hipótesis. Una aplicación directa a la exploración tridimensional de un objeto y a su clasificación y determinación de situación 6D no está indicada ahí.

En el trabajo de Shan et al. “Linear Model Hashing and Batch RANSAC for Rapid and Accurate Object Recognition”, Proceedings of the 2004 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR'04) , IEEE, 2004, se emplea un algoritmo RANSAC de este tipo y un clasificador de Bayes para un reconocimiento de objetos y la determinación de su situación 6D. También este algoritmo es demasiado lento para la aplicación práctica.

Finalmente es conocido desplazar y girar la situación de un objeto, por ejemplo en la representación como red poligonal de la superficie, frente a un objeto de modelo correspondiente, hasta que se minimizan las distancias de los puntos de objeto reales respecto a los puntos de modelo. Para ello pueden emplearse por ejemplo procedimientos de mínimos cuadrados promedio conocidos en sí desde hace mucho. En este caso no sólo es comprobada la situación 6D como hipótesis, sino que la hipótesis es optimizada adicionalmente (procedimiento ICP, del inglés “Iterative Closest Point”, iterativo de punto más cercano) . Es desventajoso en el procedimiento ICP la evaluación relativamente lenta, que no puede comprobar un gran número de hipótesis dentro de tiempos de operación aceptables. Además de ello, el procedimiento ICP tiende a converger a extremos locales, y no está en disposición de diferenciar éstos del extremo global deseado. El resultado en un caso así es una clasificación y una determinación de situación 6D erróneas.

En el trabajo de Chu-Song Chen et al., “RANSAC-based DARCES: A new Approach to Fast Automatic Registration of Partially Overlapping Range Images” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 21 (11) , noviembre de 1999, páginas 1229-1234 se describe un algoritmo RANSAC con el que, en el caso de imágenes de distancia parcialmente solapadas, se determina aquella transformación que hace coincidir un modelo 3D con un objeto captado. Para ello, a partir de primeramente tres puntos de control del escenario se determina una transformación hipotética, que transforma estos puntos de control hacia el modelo. A continuación se calcula una medida de solapamiento acerca de lo buena que es en conjunto la coincidencia. En una ampliación se emplean más de tres puntos de control, y para cada punto de control adicional se comprueba primeramente si la transformación hipotética ofrece para él suficiente coincidencia. Si no es éste el caso, la hipótesis es desechada. Sólo para hipótesis en las que todos los puntos de control coinciden suficientemente bien se lleva a cabo realmente el costoso cálculo de la medida de solapamiento.

A partir de Hon-Keat Pong et al., “Object Detection Using a Cascade of 3D Models”, Computer Vision – ACCV 2006 Lecture Notes in Computer Science, Springer Verlag vol. 3852 (2005) , páginas 284-293, es conocido encontrar modelos 3D en imágenes 2D, mediante el recurso de son comprobados en cascada modelos con grado creciente de detalle (LOD, del inglés “Level Of Detail”) .

Por ello constituye la tarea de la invención proporcionar una clasificación y una determinación de situación 6D para objetos, que opere de forma tanto rápida como suficientemente precisa.

Esta tarea es resuelta mediante un procedimiento conforme a la reivindicación 1 y un dispositivo conforme a la reivindicación 13 para la clasificación de objetos. Mediante la aplicación en cascada de pruebas de hipótesis pueden combinarse con ahorro de recursos diferentes procedimientos, que se complementan entonces en su precisión y reducen al mismo tiempo muy considerablemente el tiempo de operación.... [Seguir leyendo]

1. Procedimiento para la clasificación de objetos (16) y para el reconocimiento de su posición y orientación en el espacio, en que con una disposición captadora (18) con resolución de distancia son generados puntos de datos del objeto medido para una superficie del objeto medido y con ayuda de datos de objeto modelado previamente determinados son planteadas y verificadas a partir de los puntos de datos del objeto medido hipótesis acerca de la clase, la posición y la orientación de un objeto medido (16) , en que varias pruebas de hipótesis diferentes son realizadas en cascada de tal modo que sólo en caso de verificación de una hipótesis mediante una prueba de hipótesis es realizada una prueba de hipótesis subsiguiente dentro de la cascada, hasta que por fallo de una prueba de hipótesis una hipótesis es falsificada o por paso completo a través de la cascada sin falsificación una hipótesis es verificada en conjunto, caracterizado porque la cascada de pruebas de hipótesis incluye los siguientes procedimientos en esta secuencia: una prueba de caja delimitadora (bounding-box) , en la que una selección de puntos de datos del objeto medido es comprobada acerca de si está situada dentro de un cuerpo envolvente del objeto modelado, una prueba de imagen de distancia (range-image) , en la que una imagen de distancia real del objeto medido (16) es comparada con una imagen de distancia ficticia de un objeto modelado conforme a la clase, posición y orientación hipotéticas, una prueba de vecino más próximo (nearest-neighbour) , en la que puntos de una malla del objeto medido (16) son comparados con los vecinos más próximos de una malla de un objeto modelado hipotético, y una prueba de si tras una optimización de posición y orientación, en la que los puntos de datos del objeto medido son llevados a coincidencia óptima con una malla de superficie de un objeto modelado, una parte suficientemente grande del objeto medido 16 se solapa de forma suficientemente próxima con el objeto modelado.

2. Procedimiento según la reivindicación 1, en que los datos de objeto modelado incluyen histogramas de modelo, que partiendo respectivamente de un punto de la superficie del modelo describen la distribución de la posición o de una propiedad de puntos de superficie de modelo contiguos, empleándose en particular como histogramas de modelos imágenes de revolución (spin-images) , contextos de forma 3D (3D-shape-contexts) o imágenes de reflexión (remissions-images) , y/o en que a partir de al menos una parte de los puntos de datos del objeto medido son generados histogramas de medida correspondientes.

3. Procedimiento según la reivindicación 2, en que los datos de objeto modelado son aprendidos y/o calculados a partir de un fichero CAD y son almacenados en una biblioteca de modelos.

4. Procedimiento según la reivindicación 3, en que histogramas de modelo, que debido a simetrías son iguales o muy similares, sólo son almacenados una vez en la biblioteca de modelos, y mediante referenciación o hashing a los puntos de superficie de modelo respectivamente no es almacenado el histograma de modelo, sino sólo una referencia al histograma de modelo asociado, y/o en que los histogramas de modelo son comprimidos de cara a la reducción de datos.

5. Procedimiento según la reivindicación 2, 3 ó 4, en que son halladas correspondencias, en particular correspondencias de puntos o polígonos, entre puntos de superficie de modelo y puntos de superficie de medida, mediante la valoración de la similaridad entre histogramas de modelo e histogramas de medida, en particular a través de una norma de separación o una correlación, y en que es empleada una fracción pequeña de correspondencias con la mejor valoración de similaridad para las pruebas de hipótesis, en particular una fracción de al menos un 1% de una distribución de la valoración de similaridad de todas las comparaciones posibles entre histogramas de modelo e histogramas de medida.

6. Procedimiento según una de las reivindicaciones precedentes, en que es recorrida varias veces la cascada de las pruebas de hipótesis en particular sobre la base de un algoritmo RANSAC, hasta que se verifica una hipótesis con la precisión requerida, ha transcurrido un tiempo de operación máximo o se ha superado un límite superior de un número de hipótesis a comprobar, en que para cada pasada por la cascada se establece una hipótesis para la clase de objeto, posición y orientación del objeto medido (16) , mediante el recurso de que un subconjunto de correspondencias de puntos, en particular tres correspondencias de puntos, son determinadas aleatoriamente bajo la condición de que todas las correspondencias de puntos del subconjunto pertenezcan a la misma clase de objeto, y a partir de la posición y/u orientación asociada a las correspondencias de puntos del subconjunto es derivada una posición y orientación del objeto medido (16) .

7. Procedimiento según una de las reivindicaciones precedentes, en que la optimización de posición y orientación es un procedimiento iterativo de mínimos cuadrados promedio.

8. Procedimiento según una de las reivindicaciones precedentes, en que la prueba de vecino más próximo es la iteración número 0 de la optimización de posición y orientación sobre la base de una selección de los puntos de datos del objeto medido.

9. Procedimiento según una de las reivindicaciones precedentes, en que la prueba de imagen de distancia

comprende los siguientes pasos:

captación de una imagen de distancia de medida del objeto medido (16) , en la que las distancias están codificadas en particular en color o en grises;

cálculo de una imagen de distancia de modelo virtual del objeto modelado de la hipótesis en posición y orientación de la hipótesis y en particular desde la perspectiva de la disposición captadora;

comparación de la imagen de distancia de medida y la imagen de distancia de modelo, en particular cálculo de una norma de separación o de una correlación, y aceptación de la hipótesis, cuando la comparación muestra coincidencia en el marco de una tolerancia prefijada.

10. Procedimiento según una de las reivindicaciones precedentes, en que las hipótesis son comprobadas de forma paralelizada en un conducto (pipeline) , mediante el recurso de que la siguiente hipótesis es generada ya mientras que una o más de las hipótesis previas aún son comprobadas y/o mediante el recurso de que la cascada de una prueba de hipótesis adicional es comenzada mientras que la hipótesis previa es comprobada aún, de modo que en particular cada prueba de hipótesis individual dentro de la cascada puede ser realizada paralelamente sobre un bloque propio, y/o mediante el recurso de que varias hipótesis son generadas y comprobadas en paralelo en varios hilos (threads) o sobre varios bloques.

11. Procedimiento según una de las reivindicaciones precedentes, en que el objeto medido (16) es segmentado con anterioridad mediante el recurso de que subconjuntos de los puntos de datos del objeto medido, que pertenecen respectivamente a un segmento, son agrupados y para cada segmento en sí son determinadas la clase, posición y orientación, para clasificar con ello objetos medidos (16) compuestos o una pluralidad de objetos medidos (16) dispuestos uno junto a otro o uno sobre otro.

12. Procedimiento según una de las reivindicaciones precedentes, en que los puntos de datos del objeto medido son captados ventajosamente de forma tridimensional por exploración con un escáner de láser o mediante un sensor de imágenes (18) con resolución de distancia como toma total o mediante composición de líneas de un objeto medido (16) relativamente móvil, en que las distancias son determinadas por un procedimiento de tiempo de recorrido de luz, un procedimiento de corte de luz, triangulación activa por valoración de un patrón de contraste o estereoscopía.

13. Dispositivo (10) para la clasificación de objetos (16) y/o para el reconocimiento de su posición y/u orientación en el espacio, en que el dispositivo (10) tiene una disposición captadora optoelectrónica (18) con resolución de distancia para la generación de puntos de datos de objeto medido de una superficie del objeto medido, una memoria de modelos (30) para el almacenamiento de datos de objetos modelados y una unidad de valoración (32) , la cual está conformada para llevar a cabo un procedimiento según una de las reivindicaciones 1 hasta 12.

14. Dispositivo según la reivindicación 13, en que la disposición captadora (18) es un escáner de láser o una cámara estereoscópica o en que la disposición captadora tiene un elemento de iluminación que puede emitir impulsos de luz o luz modulada, y en que la unidad de valoración (32) está conformada para determinar distancias a partir de un tiempo de recorrido de luz o de un desplazamiento de fase.

15. Dispositivo según la reivindicación 13 ó 14, en que la disposición captadora (18) tiene un sensor de imágenes

(20) por líneas o en forma de matriz con resolución de píxeles, y en que la unidad de valoración (24, 32) está conformada para determinar puntos de datos del objeto medido en un área de captación de forma tridimensional como toma total o mediante exploración por líneas de un objeto medido (16) relativamente móvil.