Como encontro o Waldo no Mathematica?

Isso estava me incomodando no fim de semana: Qual é uma boa maneira de resolver aqueles Onde está o Waldo? Quebra-cabeças [ 'Wally' fora da América do Norte], usando o Mathematica (processamento de imagem e outras funcionalidades)?

Aqui está o que eu tenho até agora, uma função que reduz um pouco a complexidade visual escurecendo algumas das cores que não são vermelhas:

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

E um exemplo de uma URL onde isso 'funciona':

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

(Waldo fica na caixa registradora):

Encontrei Waldo!

Como eu fiz isso

Primeiro, estou filtrando todas as cores que não são vermelhas

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

Em seguida, estou calculando a correlação dessa imagem com um padrão preto e branco simples para encontrar as transições de vermelho e branco na camiseta.

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

Eu uso Binarizepara escolher os pixels da imagem com uma correlação suficientemente alta e desenhar um círculo branco ao redor deles para enfatizá-los usandoDilation

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

Eu tive que brincar um pouco com o nível. Se o nível for muito alto, muitos falsos positivos são detectados.

Finalmente, estou combinando esse resultado com a imagem original para obter o resultado acima

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

Meu palpite sobre uma "maneira à prova de balas para fazer isso" (pense na CIA encontrando Waldo em qualquer imagem de satélite a qualquer momento, não apenas uma única imagem sem elementos concorrentes, como camisas listradas) ... Eu treinaria uma máquina Boltzmann em muitas imagens do Waldo - todas as variações dele sentado, em pé, ocluído, etc .; camisa, chapéu, câmera e todos os trabalhos. Você não precisa de um grande corpus de Waldos (talvez 3-5 seja suficiente), mas quanto mais, melhor.

Isso atribuirá nuvens de probabilidades a vários elementos que ocorrem em qualquer disposição correta e, em seguida, estabelecerá (via segmentação) qual é o tamanho médio de um objeto, fragmentará a imagem de origem em células de objetos que mais se assemelham a pessoas individuais (considerando possíveis oclusões e alterações de pose) ), mas como as imagens do Waldo geralmente incluem MUITAS pessoas na mesma escala, isso deve ser uma tarefa muito fácil, depois alimente esses segmentos da máquina Boltzmann pré-treinada. Isso lhe dará a probabilidade de cada um ser Waldo. Tome um com a maior probabilidade.

É assim que o OCR, os leitores de código postal e o reconhecimento de escrita sem traços funcionam atualmente. Basicamente, você sabe que a resposta está lá, você sabe mais ou menos como deveria ser, e todo o resto pode ter elementos comuns, mas definitivamente é "não é", então você não se incomoda com o "não é", você basta olhar para a probabilidade de "it" entre todas as possíveis "it's que você já viu antes" (em códigos postais, por exemplo, você treinaria BM por apenas 1s, apenas 2s, apenas 3s, etc., depois alimentaria cada dígito para cada máquina e escolha uma que tenha mais confiança.) Isso funciona muito melhor do que um único recurso de aprendizado de rede neural de todos os números.

Concordo com o @GregoryKlopper que a maneira correta de resolver o problema geral de encontrar Waldo (ou qualquer objeto de interesse) em uma imagem arbitrária seria treinar um classificador de aprendizado de máquina supervisionado. Usando muitos exemplos de etiquetas positivas e negativas, um algoritmo como o Support Vector Machine , o Boosted Decision Stump ou o Boltzmann Machine provavelmente poderia ser treinado para obter alta precisão nesse problema. O Mathematica ainda inclui esses algoritmos em seu Machine Learning Framework .

Os dois desafios com o treinamento de um classificador Waldo seriam:

1. Determinando a transformação correta do recurso de imagem. É aqui que a resposta de @ Heike seria útil: um filtro vermelho e um detector de padrões despojados (por exemplo, wavelet ou decomposição DCT) seriam uma boa maneira de transformar pixels não processados ​​em um formato que o algoritmo de classificação pudesse aprender. Uma decomposição baseada em bloco que avalie todas as subseções da imagem também seria necessária ... mas isso é facilitado pelo fato de que o Waldo é a) sempre aproximadamente do mesmo tamanho eb) sempre presente exatamente uma vez em cada imagem.
2. Obtendo exemplos de treinamento suficientes. Os SVMs funcionam melhor com pelo menos 100 exemplos de cada classe. Aplicações comerciais de reforço (por exemplo, o foco no rosto em câmeras digitais) são treinadas em milhões de exemplos positivos e negativos.

Uma rápida pesquisa de imagens no Google mostra bons dados - vou colecionar alguns exemplos de treinamento e codificá-los agora mesmo!

No entanto, mesmo uma abordagem de aprendizado de máquina (ou a abordagem baseada em regras sugerida por @iND) lutará por uma imagem como a Terra dos Waldos !

Eu não conheço o Mathematica. . . que pena. Mas eu gosto da resposta acima, na maior parte.

Ainda há uma grande falha no contando com as listras sozinho para recolher a resposta (eu pessoalmente não tenho um problema com um ajuste manual). Há um exemplo (listado por Brett Champion, aqui ) apresentado que mostra que, às vezes, eles quebram o padrão da camisa. Então, torna-se um padrão mais complexo.

Eu tentaria uma abordagem de identificação de forma e cores, juntamente com relações espaciais. Assim como o reconhecimento de rosto, você pode procurar padrões geométricos em determinadas proporções um do outro. A ressalva é que geralmente uma ou mais dessas formas são ocluídas.

Obtenha um equilíbrio de branco na imagem e vermelho e vermelho na imagem. Acredito que Waldo sempre tenha o mesmo valor / matiz, mas a imagem pode ser de uma digitalização ou de uma cópia incorreta. Sempre consulte sempre uma variedade de cores que Waldo realmente é: vermelho, branco, marrom escuro, azul, pêssego, {cor do sapato}.

Há um padrão de camisa e também calças, óculos, cabelo, rosto, sapatos e chapéu que definem o Waldo. Além disso, em relação a outras pessoas na imagem, Waldo está do lado magro.

Então, encontre pessoas aleatórias para obter a altura das pessoas nesta foto. Meça a altura média de várias coisas em pontos aleatórios da imagem (um esboço simples produzirá várias pessoas individualmente). Se cada coisa não estiver dentro de um desvio padrão um do outro, elas serão ignoradas por enquanto. Compare a média das alturas com a altura da imagem. Se a proporção for muito alta (por exemplo, 1: 2, 1: 4 ou similarmente próxima), tente novamente. Execute-o 10 (?) Vezes para garantir que as amostras estejam bem próximas, excluindo qualquer média que esteja fora de algum desvio padrão. Possível no Mathematica?

Este é o seu tamanho do Waldo. Walso é magro, então você está procurando algo 5: 1 ou 6: 1 (ou o que for) ht: wd. No entanto, isso não é suficiente. Se o Waldo estiver parcialmente oculto, a altura poderá mudar. Então, você está procurando um bloco de vermelho-branco que ~ 2: 1. Mas tem que haver mais indicadores.

1. Waldo tem óculos. Procure dois círculos 0,5: 1 acima do vermelho-branco.
2. Calças azuis. Qualquer quantidade de azul na mesma largura a qualquer distância entre o final do vermelho-branco e a distância dos pés. Observe que ele veste a camisa curta, de modo que os pés não estão muito próximos.
3. O chapéu. Vermelho-branco a qualquer distância até o dobro do topo da cabeça. Observe que ele deve ter cabelos escuros abaixo e provavelmente óculos.
4. Mangas compridas. vermelho-branco em algum ângulo do vermelho-branco principal.
5. Cabelo escuro.
6. Cor do sapato. Eu não sei a cor.

Qualquer um desses poderia se aplicar. Também são verificações negativas contra pessoas semelhantes na foto - por exemplo, o item 2 nega usar um avental vermelho-branco (muito perto dos sapatos), o item 5 elimina cabelos claros. Além disso, a forma é apenas um indicador para cada um desses testes. . . somente cores dentro da distância especificada pode dar bons resultados.

Isso reduzirá as áreas a serem processadas.

Armazenar esses resultados produzirá um conjunto de áreas que devem conter o Waldo. Exclua todas as outras áreas (por exemplo, para cada área, selecione um círculo duas vezes maior que o tamanho médio da pessoa) e execute o processo que o @Heike estabeleceu removendo tudo, exceto o vermelho, e assim por diante.

Alguma idéia de como codificar isso?

Editar:

Pensamentos sobre como codificar isso. . . exclua todas as áreas, exceto Waldo, esqueletize as áreas vermelhas e corte-as até um único ponto. Faça o mesmo com os cabelos castanhos Waldo, as calças Waldo azuis, a cor dos sapatos Waldo. Para a cor da pele Waldo, exclua e encontre o contorno.

Em seguida, exclua o não vermelho, dilate (muito) todas as áreas vermelhas e, em seguida, esqueletize e corte. Esta parte fornecerá uma lista dos possíveis pontos centrais do Waldo. Este será o marcador para comparar todas as outras seções de cores do Waldo.

A partir daqui, usando as áreas vermelhas esqueletizadas (não as dilatadas), conte as linhas em cada área. Se houver o número correto (quatro, certo?), Essa é certamente uma área possível. Se não, acho que apenas o excluo (como sendo um centro do Waldo ... ainda pode ser o chapéu dele).

Em seguida, verifique se há um formato de rosto acima, uma ponta de cabelo acima, uma calça abaixo, uma sapato abaixo e assim por diante.

Ainda não há código - ainda está lendo os documentos.

Eu tenho uma solução rápida para encontrar o Waldo usando o OpenCV.

Usei a função de correspondência de modelos disponível no OpenCV para encontrar o Waldo.

Para fazer isso, é necessário um modelo. Então, recortei o Waldo da imagem original e o usei como modelo.

Em seguida, chamei a cv2.matchTemplate()função juntamente com o coeficiente de correlação normalizado como o método usado. Ele retornou uma alta probabilidade em uma única região, como mostrado em branco abaixo (em algum lugar na região superior esquerda):

A posição da região provável mais alta foi encontrada usando a cv2.minMaxLoc()função, que eu usei para desenhar o retângulo para destacar Waldo: