Как мне найти Уолдо с Mathematica?

1542

Это беспокоило меня в выходные: какой хороший способ решить те, где Уолдо? Загадки [ 'Wally' за пределами Северной Америки] с использованием Mathematica (обработка изображений и другие функции)?

Вот что у меня есть, функция, которая немного уменьшает визуальную сложность, затемняя некоторые не красные цвета:

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

И пример URL, где это «работает»:

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

(Уолдо у кассы):

Исходное изображение

Графический Mathematica

Арно Бузинг
источник
31
@yoda - вверху слева стол с большим количеством обуви, кассовый аппарат и Уолдо в углу стола.
Арно Бузинг
8
Как аспирант в области компьютерного зрения, я так искушен, чтобы сделать это ... но я должен сопротивляться. Что бы это ни стоило, я бы пошел на Гистограмму Ориентированных Градиентов + скользящее окно SVM, как в этой очень влиятельной работе (предупреждение: pdf).
Диматура
54
"Где Уолли ?" >. <
Гонки легкости на орбите
2
Можем ли мы изменить вопрос для поддержки других языков? Я думал о том, чтобы сделать это с Matlab
Андрей Рубштейн
2
@ArnoudBuzing: В вашем вопросе вы можете найти Уолдо, посмотрев на выбор, в котором больше всего белого. : /
Тамара Вийсман

Ответы:

1640

Я нашел Уолдо!

Уолдо был найден

Как я это сделал

Во-первых, я отфильтровываю все цвета, которые не красные

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

Затем я вычисляю соотношение этого изображения с простым черно-белым рисунком, чтобы найти красные и белые переходы в рубашке.

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

Я использую, Binarizeчтобы выделить пиксели на изображении с достаточно высокой корреляцией и нарисовать белый круг вокруг них, чтобы подчеркнуть их, используяDilation

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

Пришлось немного поиграться с уровнем. Если уровень слишком высок, выявляется слишком много ложных срабатываний.

Наконец, я комбинирую этот результат с исходным изображением, чтобы получить результат выше

found = ImageMultiply[waldo, ImageAdd[ColorConvert[pos, "GrayLevel"], .5]]
Хайке
источник
52
@MikeBantegui Несмотря на то, что решение Heike отличное, я бы не стал так быстро упаковывать его в WhereIsWaldoфункцию, поскольку это не общее решение. Сама Хайке указала, что нужно пройти уровни, чтобы получить позитив. Чтобы понять, что я имею в виду, попробуйте вашу упакованную функцию как есть. "http://www.findwaldo.com/fankit/graphics/IntlManOfLiterature/Scenes/AtTheBeach.jpg"С ней сложнее.
ABCD
17
Это изображение сложнее: Уолдо . Я думаю, однако, что наличие чего-то, что может выделить потенциальный Waldos, все еще полезно (для некоторого определения «полезного».) (Это напоминает мне о некоторых вещах, которые iPhoto иногда идентифицирует как лицо в нашей коллекции фотографий ...)
Бретт Чемпион
33
Пожалуйста, смотрите этот пост в Meta: meta.stackexchange.com/questions/116401/…
Билл Ящерица
155
Вы, кажется, неправильно поняли правила Где Уолдо. Это явно обман.
Стефан Кендалл
91
Хотя это хороший хак, он просто не работает. Требует ручной настройки и работает только на одном изображении. Я не понимаю, почему за это проголосовали и даже выбрали в качестве ответа. Это отговаривает кого-либо еще от попытки ответить с лучшими методами работы.
Сэм Хоцевар
144

Я думаю о «пуленепробиваемом способе сделать это» (подумайте, что ЦРУ находит Уолдо на любом спутниковом снимке в любое время, а не на одном изображении без конкурирующих элементов, таких как полосатые рубашки) ... Я бы тренировал машину Больцмана на многих снимках Уолдо - все варианты его сидения, стоя, окклюзии и т. д .; рубашка, шапка, фотоаппарат и все дела. Вам не нужен большой корпус Waldos (может быть, 3-5 будет достаточно), но чем больше, тем лучше.

Это назначит облака вероятностей различным элементам, встречающимся в любом правильном расположении, и затем установит (посредством сегментации), каков средний размер объекта, фрагментирует исходное изображение в ячейки объектов, которые больше всего напоминают отдельных людей (учитывая возможные окклюзии и изменения позы). ), но поскольку картины Уолдо обычно содержат ОДНО людей примерно одинакового масштаба, это должно быть очень простой задачей, а затем подавать эти сегменты предварительно обученной машины Больцмана. Это даст вам вероятность того, что каждый из них будет Уолдо. Возьмите тот, с наибольшей вероятностью.

Именно так сегодня работают OCR, устройства для считывания почтовых индексов и распознавания рукописного текста. По сути, вы знаете, что ответ есть, вы более или менее знаете, как он должен выглядеть, и все остальное может иметь общие элементы, но определенно «не это», так что вы не беспокоитесь о «не это», вы просто посмотрите на вероятность «это» среди всех возможных «это вы уже видели» (например, в ZIP-кодах вы тренируете BM всего 1 с, всего 2 с, только 3 с и т. д., затем кормите каждого введите цифру для каждой машины и выберите ту, которая наиболее надежна. Это работает намного лучше, чем функции обучения всех нейронных сетей.

Грегори Клоппер
источник
13
Разве для этого не достаточно простых нейронных сетей? Кроме того, статья в Википедии утверждает, что машины Больцмана не практичны.
GClaramunt
2
Не пытаясь, я не уверен, но если она достаточно большая и достаточно сложная, нейронной сети должно быть достаточно для НИЧЕГО. Особенно с рецидивами. Машины Больцмана работают ОЧЕНЬ ОЧЕНЬ ОЧЕНЬ хорошо для распознавания довольно упрощенного набора данных с большим количеством шума в море данных в отличие от себя.
Грегори Клоппер
14
Почтовые индексы постоянно читаются на машинах Boltzmann, а точность доставки почты достигла предела.
Грегори Клоппер
47

Я согласен с @GregoryKlopper, что правильным способом решения общей проблемы поиска Уолдо (или любого объекта интереса) в произвольном изображении было бы обучение контролируемого классификатора машинного обучения. Используя множество положительно и отрицательно помеченных примеров, алгоритм, такой как « Машина опорных векторов» , « Усиленный пень решений» или «Машина Больцмана», вероятно, может быть обучен для достижения высокой точности по этой проблеме. Mathematica даже включает эти алгоритмы в свою среду машинного обучения .

Две проблемы с обучением классификатора Уолдо будут:

  1. Определение правильной функции преобразования изображения. Вот где будет полезен ответ @ Heike: красный фильтр и детектор полосатой структуры (например, вейвлет или декомпозиция DCT) были бы хорошим способом превратить необработанные пиксели в формат, из которого мог бы извлечь алгоритм классификации. Также потребуется блочная декомпозиция, которая оценивает все подразделы изображения ... но это облегчается тем фактом, что Уолдо а) всегда примерно одинакового размера и б) всегда присутствует ровно один раз в каждом изображении.
  2. Получение достаточного количества обучающих примеров. SVM лучше всего работают не менее чем с 100 примерами каждого класса. Коммерческие приложения повышения (например, фокусировка лица в цифровых камерах) обучаются на миллионах положительных и отрицательных примеров.

Быстрый поиск картинок в Google дает хорошие данные - я собираюсь собрать несколько обучающих примеров и написать их прямо сейчас!

Тем не менее, даже подход машинного обучения (или подход, основанный на правилах, предложенный @iND) будет бороться за такой образ, как Земля Вальдос !

Lubar
источник
Система компьютерного зрения, основанная на машинном обучении, которая пытается решить проблему «Где Уолдо» в реальном мире (т.е. найти конкретного человека на фотографиях толпы на Flickr), была представлена ​​на конференции Computer Vision и Pattern Recognition в прошлом году. Они немного обманывают, добавляя некоторую информацию о 3D-местоположении, используя несколько фотографий одной и той же сцены.
Lubar
41

Я не знаю Mathematica. , , очень плохо. Но мне нравится ответ выше, по большей части.

Еще есть главный недостаток, полагаясь на полосах только , чтобы подобрать ответ (я лично не имею проблемы с одной ручной настройкой). Существует пример (перечисленный Чемпион Бретт, здесь ) представлено , который показывает , что они, порой, разбивают рисунок рубашки. Так что это становится более сложной моделью.

Я хотел бы попробовать подход формы и цвета, а также пространственные отношения. Подобно распознаванию лиц, вы можете искать геометрические узоры в определенных соотношениях друг от друга. Предостережение заключается в том, что обычно одна или несколько из этих форм закрыты.

Получить баланс белого на изображении и красный красный баланс на изображении. Я считаю, что Уолдо всегда имеет одно и то же значение / оттенок, но изображение может быть отсканированным или плохой копии. Затем всегда обращайтесь к массиву цветов, которыми на самом деле является Уолдо: красный, белый, темно-коричневый, синий, персиковый, {цвет обуви}.

Есть рисунок рубашки, а также брюки, очки, волосы, лицо, обувь и шляпа, которые определяют Уолдо. Кроме того, по отношению к другим людям в изображении, Уолдо на худой стороне.

Итак, найдите случайных людей, чтобы получить рост людей на этой картинке. Измерьте среднюю высоту группы вещей в случайных точках на изображении (простой контур даст довольно много отдельных людей). Если каждая вещь не находится в пределах стандартного отклонения друг от друга, они пока игнорируются. Сравните среднее значение высоты с высотой изображения. Если соотношение слишком велико (например, 1: 2, 1: 4 или аналогично близко), попробуйте еще раз. Запустите его 10 (?) Раз, чтобы убедиться, что все сэмплы довольно близки друг к другу, исключая любое среднее значение, выходящее за пределы стандартного отклонения. Возможно в Mathematica?

Это твой размер Уолдо. Уолсо тощий, поэтому вы ищете что-то 5: 1 или 6: 1 (или что-то еще) ht: wd. Однако этого недостаточно. Если Уолдо частично скрыт, высота может измениться. Итак, вы ищете блок красно-белого цвета, который ~ 2: 1. Но должно быть больше показателей.

  1. У Уолдо есть очки. Найдите два кружка 0,5: 1 над красно-белым.
  2. Голубые штаны. Любое количество синего на той же ширине в пределах любого расстояния между концом красно-белого и расстоянием до его ног. Обратите внимание, что он носит короткую рубашку, поэтому ноги не слишком близко.
  3. Шляпа. Красно-белый на любом расстоянии до макушки головы. Обратите внимание, что у него должны быть темные волосы внизу и, вероятно, очки.
  4. Длинные рукова. красно-белый под некоторым углом от основного красно-белый.
  5. Темные волосы.
  6. Цвет обуви. Я не знаю цвет.

Любой из них может подать заявку. Это также негативные проверки против похожих людей на картинке - например, № 2 отрицает ношение красно-белого фартука (слишком близко к обуви), № 5 устраняет светлые волосы. Кроме того, форма является только одним показателем для каждого из этих испытаний. , , один только цвет в пределах указанного расстояния может дать хорошие результаты.

Это сузит области для обработки.

Хранение этих результатов даст набор областей, в которых должен быть Уолдо. Исключите все остальные области (например, для каждой области выберите круг, в два раза превышающий средний размер человека), а затем запустите процесс, который выложил @Heike, удалив все, кроме красного, и так далее.

Есть мысли о том, как это кодировать?


Редактировать:

Мысли о том, как закодировать это. , , исключите все области, кроме красного Уолдо, скелетируйте красные области и обрежьте их до одной точки. Сделайте то же самое для волос Waldo коричневого цвета, брюк Waldo синего цвета, цвета обуви Waldo. Для цвета кожи Уолдо исключите, затем найдите контур.

Затем исключите не красный, расширите (много) все красные области, затем скелетируйте и обрежьте. Эта часть даст список возможных центральных точек Уолдо. Это будет маркер для сравнения всех других цветовых срезов Уолдо.

Отсюда, используя скелетонизированные красные области (не расширенные), подсчитайте линии в каждой области. Если есть правильное число (четыре, верно?), Это, безусловно, возможная область. Если нет, я просто исключаю это (как центр Уолдо ... это все еще может быть его шляпа).

Затем проверьте, есть ли форма лица сверху, точка волос выше, брюки ниже, ботинки внизу и так далее.

Пока нет кода - все еще читаю документы.

IND
источник
8
Возможно, вы можете показать подтверждение концепции на любой системе / языке, с которым вы знакомы. Это также даст вам понять, где могут возникнуть трудности.
Сабольч
1
О, я просто наслаждаюсь вызовом в его нынешнем виде. Это дает мне занятие между прогулками по пляжу и переодеванием к ужину.
IND
1
Так. , , почему негативы? Чем это отличается от другого спекулятивного ответа здесь? Это предположение, что к этому вопросу следует относиться более серьезно? Или просто, что я должен казаться более серьезным в моем расследовании? Мой подход на самом деле неправильный?
IND
3
Я не отрицал вас и не думаю, что отрицательные голоса подходят для честных попыток ответить (если они не дают дезинформации). Наиболее вероятная причина отрицательных голосов заключается в том, что вы, похоже, не опробовали (довольно сложное звучание) подход, и нахождение хорошего решения, вероятно, потребовало бы большого количества практических экспериментов и исключения многих идей. Другой умозрительный ответ предлагает общий метод (в качестве отправной точки), который использовался в прошлом для подобных проблем, и об этом имеется большое количество литературы. Просто пытаюсь объяснить, что случилось.
Сабольч
Спасибо за объяснение. Я думаю, что я не фокусируюсь на истории идей.
IND
2

У меня есть быстрое решение для поиска Уолдо с использованием OpenCV.

Я использовал функцию сопоставления с шаблоном, доступную в OpenCV, чтобы найти Уолдо.

Для этого нужен шаблон. Поэтому я обрезал Уолдо из исходного изображения и использовал его в качестве шаблона.

введите описание изображения здесь

Затем я вызвал cv2.matchTemplate()функцию вместе с нормализованным коэффициентом корреляции в качестве используемого метода. Он возвратил высокую вероятность в одной области, как показано белым цветом ниже (где-то в верхней левой области):

введите описание изображения здесь

Положение самой высокой вероятной области было найдено с помощью cv2.minMaxLoc()функции, которую я затем использовал, чтобы нарисовать прямоугольник, чтобы выделить Уолдо:

введите описание изображения здесь

Джеру Люк
источник
7
Пытаетесь решить самые известные вопросы SO по обработке изображений? ;) Ваше решение приятно и просто, но a / работает только для этого конкретного изображения и b / нуждается в точном изображении Уолдо, которое вы хотите найти заранее, в то время как я думаю, что вопрос был в том, чтобы найти любого Уолдо в любом "образе Уолдо", например Вы бы играли в обычную игру: не зная, как он выглядит заранее. В любом случае, этот вопрос очень интересный
Soltius
@ Солитус ха точно !!! Я работал только для этого изображения в частности. Работать с разными изображениями было бы непросто!
Джеру Лука