¿Cómo encuentro a Waldo con Mathematica?

1542

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):

Imagen original

Gráfico de Mathematica

Arnoud Buzing
fuente
31
@yoda - arriba a la izquierda, mesa con muchos zapatos, una caja registradora y Waldo cerca de la esquina de la mesa.
Arnoud Buzing
8
Como estudiante de doctorado en visión artificial, estoy muy tentado a intentarlo ... pero debo resistirme. Por lo que vale, iría por Histograma de gradientes orientados + ventana deslizante SVM, como en este trabajo muy influyente (advertencia: pdf).
dimatura
54
"¿Dónde está Wally ?" >. <
ligereza corre en órbita el
2
¿Podemos cambiar la pregunta para que también sea compatible con otros idiomas? Pensé en hacerlo con Matlab
Andrey Rubshtein el
2
@ArnoudBuzing: En tu pregunta, puedes encontrar a Waldo mirando la selección que tiene más blanco. : /
Tamara Wijsman

Respuestas:

1640

¡He encontrado a Waldo!

Waldo había sido encontrado

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]]
Heike
fuente
52
@MikeBantegui Si bien la solución de Heike es excelente, no sería tan rápido incluirla en una WhereIsWaldofunción, ya que no es una solución general. Heike misma ha señalado que los niveles deben ser jugados antes de que puedas obtener un resultado positivo. Para ver a qué me refiero, pruebe su función empaquetada tal como está activada. "http://www.findwaldo.com/fankit/graphics/IntlManOfLiterature/Scenes/AtTheBeach.jpg"Es más difícil con esta.
abcd
17
Esta imagen es más complicada: Waldo . Sin embargo, creo que tener algo que pueda resaltar el potencial de Waldos sigue siendo útil (para alguna definición de 'útil'). (Esto me recuerda algunas de las cosas que iPhoto a veces identificará como una cara en nuestra colección de fotos ...)
Brett Champion
33
Consulte esta publicación de Meta: meta.stackexchange.com/questions/116401/…
Bill the Lizard
155
Parece que has entendido mal las reglas de Where's Waldo. Esto es claramente una trampa.
Stefan Kendall
9191
Si bien este es un buen truco, simplemente no funciona. Requiere ajuste manual y solo funciona en una imagen. No entiendo por qué esto es votado e incluso elegido como respuesta. Desalienta a cualquier otra persona incluso a intentar responder con mejores métodos de trabajo.
sam hocevar
144

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.

Gregory Klopper
fuente
13
¿No son suficientes redes neuronales simples para eso? Además, el artículo de Wikipedia afirma que las máquinas de Boltzmann no son prácticas.
GClaramunt
2
Sin intentarlo, no estoy seguro, pero si es lo suficientemente grande y complejo, una red neuronal debería ser suficiente para CUALQUIER COSA. Especialmente con las recurrencias. Las máquinas Boltzmann lo hacen MUY MUY MUY bien por reconocer un conjunto de datos bastante simplista con una gran cantidad de ruido en un mar de datos diferente a sí mismo.
Gregory Klopper
14
Los códigos postales se leen con las máquinas Boltzmann todo el tiempo, y la precisión de la entrega del correo se ha disparado.
Gregory Klopper
47

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 !

lubar
fuente
El año pasado se presentó un sistema de visión por computadora basado en el aprendizaje automático que intenta resolver el problema de "Dónde está Waldo" en el mundo real (es decir, encontrar a una persona en particular en las fotos de la multitud en Flickr). Sin embargo, hacen un poco de trampa al agregar información de ubicación en 3D mediante el uso de múltiples fotos de la misma escena.
lubar
41

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.

Indiana
fuente
8
Quizás pueda mostrar una prueba de concepto en cualquier sistema / idioma con el que esté familiarizado. Esto también le dará una idea de dónde podrían surgir dificultades.
Szabolcs
1
Oh, solo estoy disfrutando el desafío tal como está. Me da algo que hacer entre paseos por la playa y vestirme para la cena.
iND
1
Entonces. . . ¿Por qué los votos negativos? ¿Cómo es esto diferente de la otra respuesta especulativa aquí? ¿Es esta una sugerencia de que esta pregunta debería tomarse más en serio? ¿O simplemente que debería parecer más serio en mi investigación? ¿Mi enfoque es realmente incorrecto?
iND
3
No te voté negativamente y no creo que los votos negativos sean apropiados para los intentos honestos de responder (a menos que den información errónea). La razón más probable para los votos negativos es que no parecía haber probado el enfoque (bastante complicado), y encontrar una buena solución probablemente requeriría una buena cantidad de experimentación práctica y descartar muchas ideas. La otra respuesta especulativa sugiere un método general (como punto de partida) que se ha utilizado en el pasado para problemas similares, y hay una buena cantidad de literatura al respecto. Solo trato de explicar lo que pasó.
Szabolcs el
Gracias por la explicación. Supongo que no me estoy centrando en la historia de las ideas.
iND
2

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.

ingrese la descripción de la imagen aquí

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):

ingrese la descripción de la imagen aquí

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:

ingrese la descripción de la imagen aquí

Jeru Luke
fuente
77
¿Intenta abordar las preguntas de procesamiento de imágenes más famosas de SO? ;) Su solución es agradable y fácil, pero a / solo funciona para esta imagen específica yb / necesita la imagen exacta de Waldo que desea encontrar de antemano, mientras que creo que la pregunta era sobre encontrar cualquier Waldo en cualquier "¿Dónde está la imagen de Waldo"? jugarías el juego normal: sin saber de antemano cómo se ve. Esta pregunta es muy divertida de todos modos
Soltius
@ Solitus ja exactamente !!! Lo trabajé solo para esta imagen en particular. Sin embargo, trabajar para diferentes imágenes sería un desafío.
Jeru Luke