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

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

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


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


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


http://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)
				) / Math.sqrt(Math.pow(255, 2), 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. Формула_цветового_отличия

Автор: ReklatsMasters