image processing - ¿Cómo encuentro a Waldo con Mathematica?

image-processing wolfram-mathematica

Question

Esto me estaba molestando durante el fin de semana: ¿Cuál es una buena manera de resolver esos Dónde está Waldo? [ ''Wally'' fuera de América del Norte] rompecabezas, usando Mathematica (procesamiento de imágenes y otras funciones)?

Aquí está lo que tengo hasta ahora, una función que reduce un poco la complejidad visual al atenuar algunos de los colores no rojos:

whereIsWaldo[url_] := Module[{waldo, waldo2, waldoMask},
    waldo = Import[url];
    waldo2 = Image[ImageData[
        waldo] /. {{r_, g_, b_} /;
          Not[r > .7 && g < .3 && b < .3] :> {0, 0,
          0}, {r_, g_, b_} /; (r > .7 && g < .3 && b < .3) :> {1, 1,
          1}}];
    waldoMask = Closing[waldo2, 4];
    ImageCompose[waldo, {waldoMask, .5}]
]

Y un ejemplo de una URL donde este ''funciona'':

whereIsWaldo["http://www.findwaldo.com/fankit/graphics/IntlManOfLiterature/Scenes/DepartmentStore.jpg"]

(Waldo es por la caja registradora):

Answer 1

¡He encontrado a Waldo!

Como lo he hecho

Primero, estoy filtrando todos los colores que no son rojos.

waldo = Import["http://www.findwaldo.com/fankit/graphics/IntlManOfLiterature/Scenes/DepartmentStore.jpg"];
red = Fold[ImageSubtract, #[[1]], Rest[#]] &@ColorSeparate[waldo];

A continuación, estoy calculando la correlación de esta imagen con un patrón blanco y negro simple para encontrar las transiciones de rojo y blanco en la camisa.

corr = ImageCorrelate[red, 
   Image@Join[ConstantArray[1, {2, 4}], ConstantArray[0, {2, 4}]], 
   NormalizedSquaredEuclideanDistance];

Uso Binarize para seleccionar los píxeles de la imagen con una correlación suficientemente alta y dibujar un círculo blanco alrededor de ellos para enfatizarlos usando Dilation

pos = Dilation[ColorNegate[Binarize[corr, .12]], DiskMatrix[30]];

Tuve que jugar un poco con el nivel. Si el nivel es demasiado alto, se seleccionan demasiados falsos positivos.

Finalmente, estoy combinando este resultado con la imagen original para obtener el resultado anterior.

found = ImageMultiply[waldo, ImageAdd[ColorConvert[pos, "GrayLevel"], .5]]

Answer 2

Creo que hay una "forma a prueba de balas para hacer esto" (creo que la CIA encuentra a Waldo en cualquier imagen de satélite en cualquier momento, no solo una imagen sin elementos de la competencia, como camisas a rayas) ... Entrenaría una máquina de Boltzmann en muchas imágenes de Waldo. - todas las variaciones de él sentado, de pie, ocluido, etc .; Camisa, sombrero, cámara, y todas las obras. No necesita un gran corpus de Waldos (tal vez 3-5 será suficiente), pero cuanto más mejor.

Esto asignará nubes de probabilidades a los diversos elementos que aparecen en la disposición correcta, y luego establecerá (a través de la segmentación) qué es el tamaño promedio de un objeto, fragmentará la imagen de origen en celdas de objetos que se parecen más a personas individuales (considerando posibles oclusiones y cambios de postura) ), pero como las imágenes de Waldo generalmente incluyen MUCHAS personas en aproximadamente la misma escala, esto debería ser una tarea muy fácil, luego alimente estos segmentos de la máquina Boltzmann previamente entrenada. Te dará la probabilidad de que cada uno sea Waldo. Tome uno con la mayor probabilidad.

Así es como funcionan hoy en día el reconocimiento de escritura a mano, los códigos postales y el reconocimiento de escritura manual. Básicamente, usted sabe que la respuesta está ahí, sabe más o menos cómo debería ser, y todo lo demás puede tener elementos comunes, pero definitivamente es "no lo es", por lo que no se molesta con el "no es", usted solo mire la probabilidad de "eso" entre todos los posibles "es lo que ha visto antes" (en códigos postales, por ejemplo, entrenaría BM por solo 1s, solo 2s, solo 3s, etc., y luego alimentaría a cada uno para cada máquina, y elija una que tenga más confianza. Esto funciona mucho mejor que las funciones de aprendizaje de una sola red neuronal de todos los números.

Answer 3

Estoy de acuerdo con @GregoryKlopper en que la forma correcta de resolver el problema general de encontrar a Waldo (o cualquier objeto de interés) en una imagen arbitraria sería capacitar a un clasificador de aprendizaje automático supervisado. Usando muchos ejemplos etiquetados positivos y negativos, un algoritmo como la Máquina de vectores de soporte , el Tocón de decisión reforzado o la Máquina de Boltzmann probablemente podría ser entrenado para lograr una alta precisión en este problema. Mathematica incluso incluye estos algoritmos en su Marco de aprendizaje automático .

Los dos desafíos con entrenar a un clasificador de Waldo serían:

1. Determinación de la transformación de la característica de imagen correcta. Aquí es donde la respuesta de @ Heike sería útil: un filtro rojo y un detector de patrón depurado (p. Ej., Descomposición de wavelet o DCT) sería una buena manera de convertir los píxeles en bruto en un formato que el algoritmo de clasificación podría aprender. También se requeriría una descomposición basada en bloques que evalúe todas las subsecciones de la imagen ... pero esto se hace más fácil por el hecho de que Waldo es a) siempre aproximadamente del mismo tamaño yb) siempre presente exactamente una vez en cada imagen.
2. Obtención de suficientes ejemplos de entrenamiento. Los SVM funcionan mejor con al menos 100 ejemplos de cada clase. Las aplicaciones comerciales de refuerzo (por ejemplo, el enfoque facial en cámaras digitales) están capacitadas en millones de ejemplos positivos y negativos.

Una rápida búsqueda de imágenes en Google muestra buenos datos. ¡Voy a intentar recopilar algunos ejemplos de entrenamiento y codificar esto ahora mismo!

Sin embargo, incluso un enfoque de aprendizaje automático (o el enfoque basado en reglas sugerido por @iND) luchará por una imagen como la Tierra de Waldos .

Answer 4

No sé Mathematica. . . demasiado. Pero me gusta la respuesta anterior, en su mayor parte.

Todavía hay una falla importante en confiar solo en las franjas para recoger la respuesta (personalmente no tengo un problema con un ajuste manual). Hay un ejemplo (listado por Brett Champion, here ) presentado que muestra que, a veces, rompen el patrón de la camisa. Entonces se convierte en un patrón más complejo.

Probaría un enfoque de identificación de formas y colores, junto con relaciones espaciales. Al igual que el reconocimiento facial, puede buscar patrones geométricos en ciertas proporciones entre sí. La advertencia es que generalmente una o más de esas formas están ocluidas.

Obtén un balance de blancos en la imagen y un balance de rojo de la imagen. Creo que Waldo siempre tiene el mismo valor / tono, pero la imagen puede ser de un escaneo o una copia incorrecta. Luego siempre refiérase a una variedad de colores que realmente es Waldo: rojo, blanco, marrón oscuro, azul, melocotón, {color del zapato}.

Hay un patrón de camisa, y también los pantalones, gafas, pelo, cara, zapatos y sombrero que definen a Waldo. Además, en relación con otras personas en la imagen, Waldo está en el lado flaco.

Por lo tanto, encuentre personas al azar para obtener la altura de las personas en esta foto. Mida la altura promedio de un montón de cosas en puntos aleatorios en la imagen (un simple contorno producirá bastantes personas individuales). Si cada cosa no está dentro de una desviación estándar entre sí, se ignoran por ahora. Compara el promedio de alturas a la altura de la imagen. Si la relación es demasiado grande (por ejemplo, 1: 2, 1: 4, o similarmente cerca), intente nuevamente. Ejecútelo 10 (?) De veces para asegurarse de que las muestras estén muy juntas, excluyendo cualquier promedio que esté fuera de alguna desviación estándar. Posible en Mathematica?

Este es tu tamaño de Waldo. Walso es delgado, por lo que está buscando algo 5: 1 o 6: 1 (o lo que sea) ht: wd. Sin embargo, esto no es suficiente. Si Waldo está parcialmente oculto, la altura podría cambiar. Entonces, estás buscando un bloque de rojo-blanco que ~ 2: 1. Pero tiene que haber más indicadores.

1. Waldo tiene gafas. Busca dos círculos 0.5: 1 arriba del rojo-blanco.
2. Pantalones azules. Cualquier cantidad de azul en el mismo ancho dentro de cualquier distancia entre el final del rojo-blanco y la distancia a sus pies. Tenga en cuenta que lleva la camisa corta, por lo que los pies no están demasiado cerca.
3. El sombrero. Rojo-blanco a cualquier distancia hasta dos veces la parte superior de su cabeza. Tenga en cuenta que debe tener pelo oscuro debajo, y probablemente gafas.
4. Mangas largas. Rojo-blanco en algún ángulo desde el principal rojo-blanco.
5. Pelo oscuro.
6. Color del zapato. No sé el color.

Cualquiera de esos podría aplicar. Estos también son controles negativos contra personas similares en la foto: por ejemplo, el # 2 niega el uso de un delantal rojo-blanco (demasiado cerca de los zapatos), el # 5 elimina el cabello de color claro. Además, la forma es solo un indicador para cada una de estas pruebas. . . Color solo dentro de la distancia especificada puede dar buenos resultados.

Esto reducirá las áreas a procesar.

El almacenamiento de estos resultados producirá un conjunto de áreas que deberían incluir a Waldo. Excluya todas las demás áreas (por ejemplo, para cada área, seleccione un círculo dos veces más grande que el tamaño de la persona promedio), y luego ejecute el proceso que @Heike estableció eliminando todo menos el rojo, etc.

¿Alguna idea sobre cómo codificar esto?

Editar:

Reflexiones sobre cómo codificar esto. . . excluya todas las áreas excepto el rojo de Waldo, esqueletice las áreas rojas y recórtelas en un solo punto. Haz lo mismo con el pelo Waldo marrón, los pantalones Waldo azules y el color del zapato Waldo. Para el color de la piel de Waldo, excluye, luego encuentra el contorno.

A continuación, excluya todas las áreas rojas que no sean rojas, dilate (mucho), luego haga un esqueleto y pode. Esta parte le dará una lista de posibles puntos centrales de Waldo. Este será el marcador para comparar todas las demás secciones de color de Waldo.

A partir de aquí, utilizando las áreas rojas esqueletonizadas (no las dilatadas), cuente las líneas en cada área. Si hay el número correcto (cuatro, ¿verdad?), Este es ciertamente un área posible. Si no, supongo que simplemente lo excluyo (por ser un centro de Waldo ... todavía puede ser su sombrero).

Luego, verifique si hay una forma de cara arriba, una punta de cabello arriba, una punta de pantalón abajo, una punta de zapato abajo, etc.

No hay código todavía - sigue leyendo la documentación.

Answer 5

Tengo una solución rápida para encontrar a Waldo usando OpenCV.

Usé la función de comparación de plantillas disponible en OpenCV para encontrar a Waldo.

Para ello se necesita una plantilla. Así que recorté a Waldo de la imagen original y lo usé como plantilla.

Luego llamé a la función cv2.matchTemplate() junto con el coeficiente de correlación normalizado según el método utilizado. Devolvió una alta probabilidad en una sola región como se muestra en blanco abajo (en algún lugar en la región superior izquierda):

La posición de la región más alta probable se encontró usando la función cv2.minMaxLoc() , que luego usé para dibujar el rectángulo para resaltar Waldo: