piezas del rompecabezas juego

Question

que no tienen nada útil que hacer y estaba jugando con rompecabezas como esto:

alt text http://manual.gimp.org/nl/images/filters/examples/render-taj-jigsaw.jpg

y me preguntaba si sería posible hacer un programa que me ayuda a poner todo junto.

Imagine que tengo un pequeño rompecabezas, como piezas de 4x3, pero las pestañas y los espacios en blanco no son uniformes; las diferentes piezas tienen estas pestañas en diferentes alturas, de diferentes formas y tamaños. Lo que haría es tomar fotografías de todas estas piezas, dejar que un programa las analice y almacene sus atributos en algún lugar. Luego, cuando recojo una pieza, puedo pedirle al programa que me diga qué piezas deben ser sus "vecinas", o si tengo que completar un espacio en blanco, me dirá cómo funciona la (s) pieza (s) de rompecabezas deseadas. Mira.

Por desgracia nunca he hizo nada con procesamiento de imágenes y reconocimiento de patrones, así que me gustaría pedirles que para algunos punteros - ¿cómo reconozco una pieza de puzzle (básicamente un cuadrado con lengüetas y agujeros) en una imagen?

Entonces probablemente necesitaría rotarlo para que esté en la posición correcta, escalar en cierta proporción y luego medir la pestaña/espacio en blanco en cada lado, y también la pendiente de cada lado, si está presente.

Sé que sería demasiado lento para escanear/fotografiar 1000 piezas de rompecabezas y usarlo, este sería solo un proyecto favorito donde aprendería algo nuevo.

Answer 1

adquisición de datos

(Esto se conoce como Inserción de imagen, pantalla azul o el método de color de fondo)

1. Encuentra una habitación bien iluminada, con la variación de menos de iluminación de la habitación.
2. Encuentra un color (matiz) que rara vez se usa en todo el rompecabezas/imagen.
3. Obtenga un papel de color que tenga exactamente el mismo color.
4. Coloque tantas piezas de rompecabezas en el papel de color como quepa.
   • Puede clasificar los rompecabezas en lotes y usarlos como una sugerencia de computadora más adelante.
   • Asegúrese de que las piezas no se superpongan ni se toquen entre sí.
   • No se preocupe por la orientación todavía.
5. Tome la foto y descargue a la computadora.
   • Puede que sea necesaria la calibración del color porque el fondo Chroma Key puede haber alterado el equilibrio de color incorporado de la cámara digital.

procesamiento de datos Adquisición

1. Obtener algún tipo de software de visión por ordenador
   • OpenCV, MATLAB, C++, Java, Python Imaging Library, etc.
2. Realice el componente conectado en el color de la clave de croma en la imagen.
   • Pregunta para los contornos de los agujeros del componente conectado, que son las piezas del rompecabezas.
3. Corregir errores en la lista detectada.
4. Elija indexing vocabulary (consulte la publicación de Ira Baxter) y mida las piezas.
   • Si las piezas son rectangulares, busque las esquinas primero.
   • Si las piezas son de forma cuadrangular apagada, las longitudes laterales (medidas de esquina a esquina) también son una valiosa firma.
   • Busque "Contexto de forma" en SO o Google o here.
   • Finalmente, obtenga el histograma de color de la pieza, para poder consultar las piezas por color más adelante.
5. Para hacer que se puedan buscar, colóquelos en una base de datos, de forma que pueda consultar las piezas con cualquier combinación de vocabulario de indexación.

Answer 2

Un paso atrás en el problema. El problema de construir un rompecabezas puede ser fácil (P) o difícil (NP), dependiendo de si las piezas se ajustan solo a un vecino, o muchas. Si solo hay un ajuste para cada borde, entonces usted acaba de encontrar, por cada pieza/lado, su vecino y listo (O (# piezas * # lados)). Si algunas piezas permiten múltiples ajustes en vecinos diferentes, entonces, para completar el rompecabezas completo, es posible que necesite retroceder (porque hizo una elección incorrecta y se queda atascado).

Sin embargo, el primer problema para resolver es cómo representar las piezas. Si desea representar formas arbitrarias, probablemente pueda usar transparencias o máscaras para representar qué áreas de un mosaico son realmente parte de la pieza. Si usa formas cuadradas, entonces el problema puede ser más fácil. En este último caso, puede considerar la última fila de píxeles en cada lado del cuadrado y hacerla coincidir con la fila de píxeles más similar que encuentre en todas las demás piezas.

Puede utilizar el segundo enfoque para ayudarlo realmente a resolver un rompecabezas real, a pesar del hecho de que usa fichas cuadradas. Los rompecabezas reales normalmente se construyen sobre una grilla de piezas NxM. Al escanear la imagen desde el recuadro, la divide en la misma cuadrícula NxM de mosaicos cuadrados y el sistema la resuelve. El problema es entonces mapear visualmente la pieza ondulada real que tienes en la mano con una ficha dentro del sistema (cuando son pequeñas y de color uniforme). Pero obtienes el mismo problema si representas formas arbitrarias internamente.