Угадываем знаменитость

    На кинопоиске есть викторина под названием «Угадай знаменитость». В ней необходимо за 10 секунд отгадать актёра (режиссёра, сценариста, просто известную личность) на фотографии. Правила просты, однако узнать человека бывает не так-то просто. Особенно, если не знаешь. Вот тут-то и родилась идея «помочь» себе в разгадывании.

    Для начала следует определиться с концепцией. Первое, что приходит на ум — узнать ID человека и подгрузить его фотографию. Узнать ID человека не составляет труда, кинопоиск постоянно обновляется и одним из таких нововведений явился автокомплит в поисковой строке (раньше поиск редиректил на другой домен — s.kinopoisk.ru, это ещё больше осложнило бы задачу). Отдельно для поиска людей в нём используются запросы вида:

    www.kinopoisk.ru/handler_search_people.php?q={query}


    В ответ приходит красавец-JSON. Идентификаторы персон у нас есть, осталось подгрузить фотографии. Для ускорения процесса загрузки мы будем использовать уменьшеные копии фотографий. Они находятся по адресу:

    st.kinopoisk.ru/images/sm_actor{id}.jpg


    Как видим, статика находится на другом домене (и это ещё добавит нам проблем). Все данные у нас имеются, осталось добавить немного стилей и оформить в виде юзерскрипта:

    (function(){
    	function doMain(){
    		$('img[name="guess_image"]').css({"border":"1px solid black","margin":"10px 0 10px 0"});
    		$("#answer_table").parent().css({"background":"#f60","padding-left":"130px","padding-bottom":"30px"});
    		for (var i=0; i<4; ++i){
    			$('<div><img src="http://st.kinopoisk.ru/images/users/user-no-big.gif" \
    			class="cheet_image" width=52 hight=82 /></div>')
    			.bind("click", function(){
    				$(".cheet_image").css({'box-shadow':'','border':''});
    			})
    			.bind("load", function() {
    				$(this).css({'box-shadow':'0 0 10px rgba(0,0,0,0.9)',"border":"1px solid red"});
    			})
    			.appendTo("#a_win\\["+i+"\\]");
    		}
    		$('img[name="guess_image"]').bind("load", function(){
    				doLoader(0);
    		});
    	}	
    	function doLoader(i){
    		$.getJSON(
    			"/handler_search_people.php",
    			{
    				q: $("#win_text\\["+i+"\\]").html()
    			},
    			function(data){
    				$(".cheet_image").eq(i)
    					.attr('src','http://st.kinopoisk.ru/images/sm_actor/'+data[0].id+'.jpg');
    				if (i < 4) doLoader(++i);
    			}
    		);
    	}	
    	window.addEventListener('DOMContentLoaded', doMain, false);
    })();
    

    Теперь при каждой загрузке нового изображения у нас подгружаются фотографии из вариантов ответа:



    К недостаткам данного метода можно отнести то, что нам всё ещё необходимо совершать некие действия — визуально распознавать фотографии. В идеале от нас должно требоваться только одно действие — нажатие на кнопку «старт».

    Усовершенствуем наш скрипт. Теперь мы будем сравнивать изображения и на основании сравнения выбирать правильный вариант. Для начала попробуем сравнивать хеши изображения. Нам нужно убедиться, что загаданное изображение и статически доступный аналог — одно и тоже. Открываем изображения в HEX-редакторе и смотрим, что это не так:





    Как видим, изображения генерируются динамически. Остаётся единственный выход — попиксельно сравнивать изображения. И вот тут приходит на помощь HTML5, в частности элемент <canvas>. От нас требуется всего лишь отрисовать изображение и вызвать метод getImageData(x, y, width, height). Однако мы помним, что изображение хранится на другом домене и ни о каком CORS речи не идёт:



    Выходом из данной ситуации является использование межоконного общения — метода postMessage() и событытия message. В скрытом фрейме мы будем загружать главную страницу домена, на котором находятся фотографии, подгружать само изображение, конвертировать в base64 строку и отсылать родительскому фрейму. Хотя конечно, можно поступить и по другому: загружать изображение, динамически создать элемент canvas и получить из него массив значений пикселей. Так как тип полученного объекта будет не просто Array, а Uint8ClampedArray (простой 8 битный массив), у которого нет метода join, придётся использовать JSON для сериализации \ десериализиции данных. Само сабой это очень накладно и проигрывает в производительности первому методу, который мы и будем использовать.

    Первым делом нам необходимо получить base64 закодированное изображение. В скрытом фрейме загружаем главную страницу, а в якоре передаём идентификатор изображения и номер варианта ответа. В самом же фрейме мы загружаем нужное изображение и находим его base64 код:

    xhr = new XMLHttpRequest();
    xhr.open('GET', '/images/sm_actor/'+hash[0]+'.jpg', false);
    xhr.overrideMimeType('text/plain;charset=x-user-defined');
    xhr.onload = function() {
        if (xhr.readyState == 4){
            var resp = xhr.responseText;
            var data = 'data:';
            data += xhr.getResponseHeader('Content-Type');
            data += ';base64,';
    
            var decodedResp = '';
            for(var i = 0, L = resp.length; i < L; ++i)
                decodedResp += String.fromCharCode(resp.charCodeAt(i) & 255);
            data += btoa(decodedResp);
        }
    };
    xhr.send(null);
    

    При отправке изображения в браузере Chrome выяснилась одна неприятная особенность: изображение, полученное таким способом всё ещё защищено политикой CORS и получить его данные из canvas нельзя. Выходом из данного тупика является встраивание скрипта в код страницы и отправка изображения уже таким способом (как выяснилось, и данный метод срабатывает не с первого раза):

    if (typeof window.chrome == 'undefined')
    	window.parent.postMessage(hash[1]+"|"+data, "http://www.kinopoisk.ru/");
    else {
    	var scr = document.createElement("script");
    	scr.setAttribute('type','application/javascript');
    	scr.textContent = "window.parent.postMessage('"+hash[1]+"|"+data+"', 'http://www.kinopoisk.ru/');";
    	document.body.appendChild(scr);
    }
    

    Теперь начинается самое вкусное — сравнение изображений. Первым делом мой выбор пал на библиотеку IM.js (от слов Image Match, к известному Internet Messager не имеет никакого отношения). По непонятным причинам заводиться она у меня отказалась. Пришлось изучать литературу про сравнение изображений. Я остановился на самом простом методе — использование метрики ΔE* и её самой простой реализации CIE76. Хоть она использует цветовое пространство LAB, мы её будем применять в обыкновенном RGB. Из-за этого неизбежно возникнут погрешности, но и даже с ними результат вполне приемлемый. Тем более, что конвертировать RGB -> LAB придётся через промежуточное пространство XYZ, что вызовет ещё большие погрешности. Суть CIE76 сводится к нахождению среднеквадратичного цвета:



    В коде это выглядит следующим образом:

    // В качестве параметра передаём 
    // контекст изображения, полученного из фрейма
    function doDiff(context) {
    
    	var all_pixels = 25*40*4;
    	var changed_pixels = 0;
    
    	var first_data = context.getImageData(0, 0, 25, 40);
    	var first_pixel_array = first_data.data;
    	
    	// получаем данные загаданного изображения
    	// из заранее созданного и отрисованного canvas
    	var second_ctx = $("#guess_transformed").get(0).getContext('2d');
    	var second_data = second_ctx.getImageData(0, 0, 25, 40);
    	var second_pixel_array = second_data.data;
    
    	for(var i = 0; i < all_pixels; i+=4) {
    
    		if (first_pixel_array[ i ] != second_pixel_array[ i ] ||	// R
    			first_pixel_array[i+1] != second_pixel_array[i+1] ||	// G
    			first_pixel_array[i+2] != second_pixel_array[i+2])		// B
    			{
    				changed_pixels+=Math.sqrt(
    					Math.pow( first_pixel_array[ i ] - second_pixel_array[ i ] , 2) +
    					Math.pow( first_pixel_array[i+1] - second_pixel_array[i+1] , 2) +
    					Math.pow( first_pixel_array[i+2] - second_pixel_array[i+2] , 2)
    				) / (255*Math.sqrt(3));
    			}
    	}
    	return 100 - Math.round(changed_pixels / all_pixels * 100);
    }
    

    Всё готово, осталось офомить все части в виде юзерскрипта и протестировать.



    Как мы можем наблюдать, всё работает. Самая затратная часть — загрузка изображений. Именно поэтому все изображения загружаются последовательно (после приёма события message). При одновременной загрузке изображений для обработки всех 4х результатов требовалось иногда более 10 сек. Также стоит обратить внимание на процентное соотношение степени похожести. Оно никогда не бывает выше 96% и меньше 75% даже при абсолютно разных изображениях.

    Финальным аккордом нашей оперы станет добавление автоматического сравнения и клик по нужной кнопке:

    // обработчик события message
    function doMessage(e) {
    	var data = e.data.split("|", 2);
    	var index = parseInt(data[0]);
    	// ...
    	if (index == 3)
    		$(document).trigger("cheetcompare");
    	//...
    }
    
    // в main вешаем обработчик нашего читерского события
    function doMain(){
    	// ...
    	$(document).bind("cheetcompare", function(e){
    	var max = 0;
    	// скрытые input, в них храним результат сравнения
    	var cheetd = $(".cheet_diff");
    	for(var i = 0; i < 4; ++i) {
    		max = (cheetd.eq(max).val() > cheetd.eq(i).val()) ? max : i;
    	}
    	$("#a_win\\["+max+"\\]").trigger("click");
    });
    	// ...
    }
    

    Увы, полностью отказаться от визуального контроля не удалось, время от времени всплывают фотографии не с аватарки, а из галереи. Тем не менее их меньшинство. Простым фильтром визуального контроля станет поиск результата со степенью похожести выше 93. Результат работы скрипта можно посмотреть в этом видео:



    Работа скрипта протестирована в Opera 12, Chrome 22 + Tampermonkey (если не работает — обновите страницу, срабатывает не с первого раза). В Firefox 16.0.1 скрипт заводиться отказался — не срабатывает getImageData загаданного изображения.

    Скачать скрипт можно с userscripts.org: DOWNLOAD

    Литература

    1. Получение кроссдоменных данных в Google Chrome через юзерскрипт
    2. canvas same origin security violation work-around
    3. Обучение canvas
    4. Uint8ClampedArray
    5. IM.js: Quick image comparison pixel by pixel
    6. Сравнение изображений и генерация картинки отличий на Ruby
    7. Формула_цветового_отличия



    UPD #1 Как справедливо заметил хабраюзер Monder в формулу закралась ошибка. А именно в делитель, который является максимальной разницей цвета (maximum color difference). Наглядно представить это можно следующим образом:



    Если предствить семейство RGB в виде куба, то максимальная разница цвета будет являться диагональю, которую можно найти следующим образом:



    Стоит заметить, что разброс значений стал более адекватным: 60% — 95%. Теперь планку визуального фильтра можно понизить до 90%. В этом случае уже почти точно нет похожей фотографии и надо угадываться самому.

    UPD #2 Хабраюзер nick4fake подсказал успешно забытую формулу нормирования на 0… 100:

    new = (old — min) / (max — min) * 100

    Применимо к нашей задаче, она выглядит следующим образом: Y = (X — 55) / 38 * 100. Разброс значений стал ещё более ощутим, особенно для фотографий, на которых преобладают разные оттенки (светлые \ тёмные), теперь он составляет порядка 30% — 90%.

    Similar posts

    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More
    Ads

    Comments 50

      +13
      — Оно никогда не бывает выше 96% и меньше 75% даже при абсолютно разных изображениях.
      Так нормируйте на 0..100%.

      Вообще, круто. Одновременно бесполезно и безбашенно. Наворотили лишнего, но итог заслуживает уважения.

      — При отправке изображения в браузере Chrome выяснилась одна неприятная особенность: изображение, полученное таким способом всё ещё защищено политикой CORS и получить его данные из canvas нельзя
      А в других можно? oO Если да — это очень серьезная уязвимость.
        0
        А я вообще, увидев картинки, еще не читав текста, придумал аж 2 интересных проекта.
        Автор, спасибо, дал пищу для размышлений.
        0
        — Знать бы ещё как нормировать. С другой стороны даже в таком виде разброс значений вполне адекватный.
        — Вроде как это бага code.google.com/p/chromium/issues/detail?id=20773
          0
          в смысле, как нормировать?
          пусть ваш процент = perc, нормированный — normPerc:
          normPerc = (perc — 75) / 21 * 100
          Получите разброс 0..100%
          +8
          должно быть вы шутите?

          goo.gl/O12dM

          задача решается использованием поиска гугла по картинкам в два счёта =)
            –4
            причем здесь я искал по картинке из Вашего поста, и тем не менее результат был найден, так что с конкретной фоткой вообще проблем не должно быть:)
              0
              Там защита типа хотлинкинга, так что не получится.
              –1
              А я бы по-другому делал. Прикрутил бы tineye.com и искал варианты в результатах поиска.
                +3
                хорош был сервис, пока такой же функционал не прикрутили к поиску гугла (позволяет искать как по URL картинки, так и по загружаемой с компа)
                  +1
                  Иногда tineye находит то, чего google найти не может, так что всё ещё использую его как запасной вариант.
                +12
                Задание «Положи Кинопоиск» выполнено успешно.
                  +5
                  You've just earned an «Положи Кинопоиск» achievement… :)
                  0
                  Сильно ли падает точность при маштабировании изображения?

                  > При одновременной загрузке изображений для обработки всех 4х результатов требовалось иногда более 10 сек

                  Сделайте 4 вокера каждому передайте по полной getImageData(0, 0, 25, 40) каждого снимка. Воркеры для таких целей милое дело применить.
                    0
                    — При масштабировании точность не падает, такие же результаты и при сравнении 50x80. Точность падает, если задать делитель (в формуле) константой.

                    -Мне кажется такая задержка появляется именно из-за одновременной загрузки 4х изображений. А обработать массив из 4000 значений дело не хитрое.
                      0
                      Тогда надо замерить где тормоза, мб у кинопоиска на такие картинки большие таймауты стоят. А если кэшем обвесить, индекс какой-нибудь сделать?
                        0
                        По моим субъективным наблюдениям скорость последовательной загрузки даже из кэша выше, чем при одновременной. Причём это и в опере, и в хроме.
                    +3
                    Ага
                      0
                      Опоздал на 1 день. У них по понедельникам сброс рейтинга.
                      Причём второй участник, возможно, пользовался предыдущей версией скрипта.
                        0
                        у меня что-то текущая не завелась, знаки вопроса везде, хром 22+тамперманки, обновлял страницу.
                        +9
                        Второе место круче
                          0
                          Я в исходном коде специально закомментировал строчку, которая так делает.
                        0
                        Вы не одиноки :) Делал то же самое пару лет назад (только не в браузере, а отдельной программой). Поисковых подсказок не было, поэтому выполнял обычный поиск и брал первый результат. Пару недель повисел на первом месте. Да и весь интерес был не в рейтинге, а в разработке :)
                          +1
                          Да и весь интерес был не в рейтинге, а в разработке :)

                          Вот это да. Самое интересное — процесс.

                          Один мой товарищ писал раньше это на автохоткее. Брал самый верхний левый пиксель загаданного изображения, копировал всё изображение в буффер, из личного кэша загружал фотографии и сравнивал. Причём фотки хранились поимённо. Собственно после этого мне и захотелось усовершенствований.
                          –1
                          Оффтопик: Триша Макмиллан, всё-таки, чертовски хороша.
                          0
                          Объясните, что такое Math.sqrt(Math.pow(255, 2), 3)? :)
                            0
                            Я понятия не имею) Я это просто взял у Ализара из статьи. Без этого получаются нереальные данные — порядка 2000%. На stackoverflow что-то находил по этому поводу, но ссыль потерялась.
                              0
                              Если я правильно понял код из другой статьи, там 255 в квадрате, умноженное на три. Откуда вы взяли второй параметр у Math.sqrt, не могу понять.
                              Ну и да, магическое число остается неясным. Если вдруг вспомните, в какую сторону копать, обновите, пожалуйста, пост.
                                +1
                                Кажется я понял что это за число. Это Delta E максимально возможного цвета — 255. Поделив на это число мы получаем степень похожести каждлого пикселя.
                                  0
                                  Как я понимаю, относительно нуля. Т.е. квадатный корень из суммы трех 2552. Спасибо, теперь стало ясно.
                                    0
                                    кубический корень
                                      +2
                                      В js Math.sqrt принимает только 1 аргумент. Потому Math.sqrt(Math.pow(255, 2), 3) всегда равно 255 :-S
                                        0
                                        Вот я лохонулся.
                                        А зачем там второй аргумент 3? да и вообще смысла в этом выражении нет.
                                          0
                                          о том я и вел речь :) Было непонятно как деление, так и не имеющее по сути смысла вычисление в знаменателе дроби.
                                          0
                                          где в формуле кубический корень?
                                      0
                                      Магическое число есть ни что иное как максимальная разница цвета (maximum color difference).
                                      Если представить что цвета — куб — классический RGB, то максимальная разница цветов будет диагональю. Диагональ в классическом виде d = a√3. Данная формула почему-то записана как √(a² * 3).
                                        0
                                        Признаюсь, никогда бы не подумал, что RGB — это куб :) Почему именно он?
                                          0
                                          А чтоже ещё? RGB = 3 измерения, значит куб. Еслиб цвет состоял из четыртех компонентов, то тогда был бы тессеракт.
                                  +1
                                  проклятые читеры ^^
                                    0
                                    кроссдоменно следовало бы грузить через GM_xmlhttpRequest, либо во фрейме, но с помощью img=new Image(); img.src
                                      +11
                                      Шах и мат, программисты:

                                      image

                                      image
                                        0
                                        Белуши, Хэнкс, Мюррей
                                          +15
                                          А теперь тех, кто снизу.
                                          0
                                          Кэти Перри, Перри Кэти, Кэти Перри
                                            +1
                                            Пэти Керри же
                                          –3
                                          У меня знакомый проще решил эту задачу и без формул и без вероятностеей.
                                          vasilisc.com/kinopoisk
                                            +1
                                            Может не так:
                                            changed_pixels+=Math.sqrt(
                                            Math.pow( first_pixel_array[ i ] — second_pixel_array[ i ], 2) +
                                            Math.pow( first_pixel_array[i+1] — second_pixel_array[i+1], 2) +
                                            Math.pow( first_pixel_array[i+2] — second_pixel_array[i+2], 2)
                                            ) / 255*Math.sqrt(3);
                                            А так:
                                            changed_pixels+=Math.sqrt(
                                            Math.pow( first_pixel_array[ i ] — second_pixel_array[ i ], 2) +
                                            Math.pow( first_pixel_array[i+1] — second_pixel_array[i+1], 2) +
                                            Math.pow( first_pixel_array[i+2] — second_pixel_array[i+2], 2)
                                            ) / (255*Math.sqrt(3));
                                              0
                                              Точно, правда ваша. Но проверить что бы то ни было не представляется возможности. Варианты ответов генерятся теперь как изображения. Все читают хабр)

                                            Only users with full accounts can post comments. Log in, please.