¿Cómo encuentro a Waldo con Mathematica?

Esto me estaba molestando durante el fin de semana: ¿Cuál es una buena manera de resolver esos ¿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 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 esto 'funciona':

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

(Waldo está en la caja registradora):

¡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 simple en blanco y negro para encontrar las transiciones rojas y blancas en la camisa.

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

Utilizo Binarizepara seleccionar los píxeles de la imagen con una correlación suficientemente alta y dibujar un círculo blanco alrededor de ellos para enfatizarlos usandoDilation

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]]

Mi suposición es una "forma a prueba de balas para hacer esto" (piense que la CIA encuentra a Waldo en cualquier imagen satelital en cualquier momento, no solo en una sola imagen sin elementos competitivos, como camisas a rayas) ... Entrenaría una máquina Boltzmann en muchas imágenes de Waldo - todas las variaciones de él sentado, de pie, ocluido, etc. camisa, gorro, 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 varios elementos que ocurran en cualquier disposición correcta, y luego establecerá (a través de la segmentación) cuál 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 pose) ), pero dado que las imágenes de Waldo generalmente incluyen MUCHAS personas en aproximadamente la misma escala, esta debería ser una tarea muy fácil, luego alimentar estos segmentos de la máquina Boltzmann pre-entrenada. Te dará la probabilidad de que cada uno sea Waldo. Tome uno con la mayor probabilidad.

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

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 supervisado de aprendizaje automático. Utilizando muchos ejemplos etiquetados positivos y negativos, un algoritmo como Support Vector Machine , Boosted Decision Stump o Boltzmann Machine probablemente podría entrenarse 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 el entrenamiento de un clasificador de Waldo serían:

1. Determinación de la transformación de la función de imagen correcta. Aquí es donde la respuesta de @ Heike sería útil: un filtro rojo y un detector de patrones despojados (por ejemplo, descomposición wavelet o DCT) sería una buena manera de convertir píxeles en bruto 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 es a) siempre aproximadamente del mismo tamaño yb) siempre presente exactamente una vez en cada imagen.
2. Obteniendo suficientes ejemplos de entrenamiento. Las SVM funcionan mejor con al menos 100 ejemplos de cada clase. Las aplicaciones comerciales de impulso (p. Ej., El enfoque facial en cámaras digitales) se capacitan en millones de ejemplos positivos y negativos.

Una búsqueda rápida de imágenes de Google arroja 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) luchará por una imagen como la Tierra de Waldos !

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

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

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

Obtenga un balance de blancos en la imagen y rojo 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 copia incorrecta. Entonces siempre refiérase a una variedad de colores que Waldo realmente es: rojo, blanco, marrón oscuro, azul, melocotón, {color del zapato}.

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

Por lo tanto, encuentre personas aleatorias para obtener la altura de las personas en esta foto. Mida la altura promedio de un montón de cosas en puntos aleatorios de la imagen (un esquema simple producirá bastantes personas individuales). Si cada cosa no está dentro de alguna desviación estándar entre sí, se ignoran por ahora. Compare el promedio de las alturas con la altura de la imagen. Si la relación es demasiado alta (por ejemplo, 1: 2, 1: 4 o similar), intente nuevamente. Ejecútelo 10 (?) De veces para asegurarse de que las muestras estén bastante 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 flaco, 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 anteojos. Busque dos círculos 0.5: 1 sobre el 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 él usa su camisa corta, por lo que los pies no están demasiado cerca.
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. Manga larga rojo-blanco en algún ángulo del rojo-blanco principal.
5. Pelo oscuro.
6. Color del zapato No se el color.

Cualquiera de esos podría aplicar. Estos también son controles negativos contra personas similares en la foto, por ejemplo, # 2 niega usar un delantal rojo-blanco (demasiado cerca de los zapatos), # 5 elimina el cabello de color claro. Además, la forma es solo un indicador para cada una de estas pruebas. . . El color 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 Waldo. Excluya todas las demás áreas (p. Ej., Para cada área, seleccione un círculo dos veces más grande que el tamaño promedio de persona), y luego ejecute el proceso que @Heike estableció al eliminar todo menos el rojo, y así sucesivamente.

¿Alguna idea sobre cómo codificar esto?

Editar:

Reflexiones sobre cómo codificar esto. . . excluya todas las áreas excepto Waldo rojo, esqueletice las áreas rojas y podelas en un solo punto. Haga lo mismo para el cabello Waldo marrón, los pantalones Waldo azules, el color del zapato Waldo. Para el color de la piel Waldo, excluya, luego busque el contorno.

Luego, excluya no rojo, 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 para comparar todas las demás secciones de color de Waldo.

Desde aquí, usando las áreas rojas esqueletizadas (no las dilatadas), cuente las líneas en cada área. Si hay el número correcto (cuatro, ¿verdad?), Esta es ciertamente un área posible. Si no es así, supongo que simplemente lo excluya (como siendo un centro de Waldo ... aún puede ser su sombrero).

Luego verifique si hay una forma de cara arriba, una punta de cabello arriba, un pantalón abajo, un zapato abajo, y así sucesivamente.

Todavía no hay código, todavía estoy leyendo los documentos.

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

Utilicé la función de coincidencia de plantillas disponible en OpenCV para encontrar Waldo.

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

Luego llamé a la cv2.matchTemplate()función junto con el coeficiente de correlación normalizado como el método utilizado. Devuelve una alta probabilidad en una sola región como se muestra en blanco a continuación (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 cv2.minMaxLoc()función, que luego usé para dibujar el rectángulo para resaltar Waldo: