¿Cómo encuentro a Waldo con Mathematica?

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

Esto es lo que tengo hasta ahora, una función que reduce un poco la complejidad visual al atenuar algunos de los colores que no son 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 esto 'funciona':

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

(Waldo está junto a la caja registradora):

Dec 13 '11 01:12 Arnoud Buzing

Mi suposición es una "forma a prueba de balas de hacer esto" (piense en que la CIA encuentra a Waldo en cualquier imagen de satélite en cualquier momento, no solo en una imagen sin elementos en competencia, como camisas a rayas)... Entrenaría una máquina Boltzmann con muchas imágenes de Waldo. - todas las variaciones de él sentado, de pie, ocluido, etc.; Camiseta, gorro, cámara y todos los trabajos. No necesitas un corpus grande de Waldos (tal vez 3-5 sean suficientes), pero cuanto más, mejor.

Esto asignará nubes de probabilidades a varios elementos que ocurren en cualquiera que sea la disposición correcta, y luego establecerá (mediante segmentación) cuál es el tamaño promedio de un objeto, fragmentará la imagen de origen en celdas de objetos que más se parezcan a personas individuales (considerando posibles oclusiones y cambios de pose). ), pero dado que las imágenes de Waldo generalmente incluyen MUCHAS personas aproximadamente en 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 OCR, los lectores de códigos postales y el reconocimiento de escritura a mano sin trazos. Básicamente, sabes que la respuesta está ahí, sabes más o menos cómo debería verse y todo lo demás puede tener elementos comunes, pero definitivamente "no es", así que no te molestas con los "no es". simplemente mire la probabilidad de que "eso" entre todos los "eso" posibles que haya visto antes (en los códigos postales, por ejemplo, entrenaría BM por solo 1, solo 2, solo 3, etc., luego alimentaría a cada uno). dígito a cada máquina y elija el que tenga más confianza). Esto funciona mucho mejor que una única red neuronal que aprende las características de todos los números.

Dec 12 '2011 20:12 Gregory Klopper

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 entrenar un clasificador de aprendizaje automático supervisado. Utilizando muchos ejemplos etiquetados positivos y negativos, es probable que se pueda entrenar un algoritmo como Support Vector Machine , Boosted Decision Stump o Boltzmann Machine 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 al entrenar un clasificador Waldo serían:

1. Determinar la transformación de características de imagen correcta. Aquí es donde la respuesta de @Heike sería útil: un filtro rojo y un detector de patrones eliminados (por ejemplo, descomposición wavelet o DCT) serían una buena manera de convertir píxeles sin procesar en un formato del 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 a) siempre tiene aproximadamente el mismo tamaño yb) siempre está presente exactamente una vez en cada imagen.
2. Obtener suficientes ejemplos de formación. Las SVM funcionan mejor con al menos 100 ejemplos de cada clase. Las aplicaciones comerciales del boosting (por ejemplo, el enfoque facial en las cámaras digitales) se basan en millones de ejemplos positivos y negativos.

Una búsqueda rápida de imágenes en Google arroja algunos buenos datos. ¡Voy a intentar recopilar algunos ejemplos de capacitación y codificarlos ahora mismo!

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

Apr 01 '2012 01:04 lubar

No conozco Matemáticas. . . demasiado. Pero me gusta la respuesta anterior, en su mayor parte.

Aún así, existe un error importante al confiar únicamente en las rayas para obtener la respuesta (yo personalmente no tengo ningún problema con un ajuste manual). Se presenta un ejemplo (enumerado por Brett Champion, aquí ) que muestra que, en ocasiones, 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, puedes buscar patrones geométricos en ciertas proporciones entre sí. La advertencia es que normalmente una o más de esas formas están ocluidas.

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

Hay un estampado de camisa, y también los pantalones, gafas, cabello, rostro, zapatos y sombrero que definen a Waldo. Además, en comparación con otras personas en la imagen, Waldo es más bien delgado.

Entonces, busca personas al azar para obtener la altura de las personas en esta foto. Mide la altura promedio de un conjunto de cosas en puntos aleatorios de la imagen (un esquema simple producirá bastantes personas individuales). Si cada cosa no está dentro de una desviación estándar entre sí, se ignoran por ahora. Compare el promedio de alturas con la altura de la imagen. Si la proporción es demasiado grande (p. ej., 1:2, 1:4 o similar), inténtelo de nuevo. Ejecútelo 10 (?) veces para asegurarse de que todas las muestras estén bastante juntas, excluyendo cualquier promedio que esté fuera de alguna desviación estándar. ¿Posible en Mathematica?

Esta es tu talla de Waldo. Walso es delgado, por lo que buscas algo de 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 rojo-blanco que ~2:1. Pero tiene que haber más indicadores.

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

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

Esto reducirá las áreas a procesar.

Almacenar estos resultados producirá un conjunto de áreas que deberían tener a Waldo en ellas. Excluya todas las demás áreas (por ejemplo, para cada área, seleccione un círculo dos veces más grande que el tamaño promedio de una persona) y luego ejecute el proceso que @Heike diseñó para eliminar todo menos el rojo, y así sucesivamente.

¿Alguna idea sobre cómo codificar esto?

Editar:

Pensamientos sobre cómo codificar esto. . . excluya todas las áreas excepto Waldo Red, esqueletice las áreas rojas y podelas hasta un solo punto. Haga lo mismo con el cabello castaño de Waldo, los pantalones azules de Waldo y el color de zapatos de Waldo. Para el color de piel de Waldo, excluya y luego busque el contorno.

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

A partir de aquí, utilizando las áreas rojas esqueletizadas (no las dilatadas), cuenta las líneas en cada área. Si existe el número correcto (cuatro, ¿verdad?), esta es sin duda un área posible. Si no, supongo que simplemente exclúyalo (por ser un centro de Waldo... aún puede ser su sombrero).

Luego verifique si hay una forma de cara arriba, una punta de cabello arriba, una punta de pantalones abajo, puntas de zapatos abajo, y así sucesivamente.

Aún no hay código, sigo leyendo los documentos.

Jan 10 '2012 09:01 iND

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

Utilicé la función de coincidencia 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 la usé como plantilla.

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

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

Apr 11 '2017 11:04 Jeru Luke