Skype / [Из песочницы] Улучшаем картинки в чате Skype

Предисловие

17 января мне, как и многим другим, прислали ссылку на статью zhovner про картинки в чате скайпа — http://habrahabr.ru/blogs/skype/136395/, и понеслось!
Идея прикольная, мы тут же начали перекидываться картинками, сгенерированными сервисом img4skype.com, но оказалось что у многих они отображаются растянуто.
Просмотрев фрагмент кода zhovner мы быстро обнаружили что это легко можно исправить, убрав один пробельный символ.
Нужно всего лишь исправить такой код:
$out .= '███';

на вот такой:
$out .= '██';

Поэтому и была быстро сделана локальная версия сервиса, позволяющая выбирать количество пробельных символов на пиксель — 2 или 3.
* Однако два пробельных символа вместо трех все же меняют размер картинки (вместо 1:1 получается 4:3), поэтому позже мы добавили сжатие оригинальной картинки (1:1 => 3:4, после искажения 4:3 опять получаем 1:1) если выбрано 2 пробела на пиксель.
Оптимизация

1. Объединение похожих цветов

Идея, лежащая на поверхности и озвученная самим zhovner — это объединение похожих цветов.
Если подряд идут два пикселя красного цвета то генерируется такой код:
██████

Вполне очевидно что это можно упростить:
██████

Так мы сэкономим место в сообщении, занимаемое кодом , что освободит нам 29 символов, а это 9 или 14 пикселей (в зависимости от количества пробелов на пиксель).
Это очень важно, потому что размер картинки ограничен максимальной длиной сообщения в Skype.
Эта оптимизация уже реализована несколькими читателями, поэтому не вижу смысла еще раз приводить ее код целиком.
Опишу подробнее только сравнение цветов.
Экспериментальным путем мы пришли к следующей функции:
// compare colors
function compare_clr( $c1, $c2, $max_dif, $img_px_qs )
{
$r1 = ( $c1 >> 16 ) & 0xFF;
$g1 = ( $c1 >> 8 ) & 0xFF;
$b1 = $c1 & 0xFF;

$r2 = ( $c2 >> 16 ) & 0xFF;
$g2 = ( $c2 >> 8 ) & 0xFF;
$b2 = $c2 & 0xFF;

$r_dif = abs( $r1 - $r2 );
$g_dif = abs( $g1 - $g2 );
$b_dif = abs( $b1 - $b2 );

$k = 1;

if( $img_px_qs == 1 ) // max quality
{
$def_k = 0.65;

// check difference in color channels
$dr = ( $r_dif > 0 ) ? $def_k : 0;
$dg = ( $g_dif > 0 ) ? $def_k : 0;
$db = ( $b_dif > 0 ) ? $def_k : 0;

$k = $dr + $dg + $db;

if( $k $max_dif ) || ( $g_dif*$k > $max_dif ) || ( $b_dif*$k > $max_dif ) )
{
$rv = false;
}

return $rv;
}

Первые два параметра — цвета, 3-й параметр — порог сравнения, максимальная разница между каналами цвета (0-255), 4-й параметр — максимальное качество или максимальный размер.
Если сравнивать между собой цвета целиком, не делая разницы между каналами (r, g, b), то качество картинки оставляет желать лучшего. Картинка очень быстро «мажется».
Поэтому мы сравниваем отдельные каналы. Если разница цветов хотя бы по одному каналу превышает порог — цвета считаются разными.
Формула с коэффициентами дает лучшее качество и лучше всего убирает смазывание. Она лучше подходит для сложных многоцветных картинок (фото).
Простое сравнение дает больший размер, но на сложных картинках смазывание появляется даже на маленьких порогах сравнения. Зато эта формула позволяет генерировать бОльшие картинки для простых смайлов и черно-белых троллфейсов.
2. Основной цвет

Еще одна важная оптимизация, так же лежащая на поверхности, это фоновый цвет.Цитата:

«Еще можно не окрашивать черный пиксель, потому что он и так черный.»

Черный пиксель на самом деле не черный, а дефолтный. Его цвет задается первым тегом в коде, который у img4skype не имеет цвета и потому дефолтный (почти черный):

...

...

И тогда для каждого красного пикселя или их последовательности нет нужды вставлять тег , просто закрываем от предыдущего цвета и пишем пробельные символы без тегов.
Если картинка — это лого/смайлик/рисунок на однородном фоне, то эта оптимизация дает очень большое увеличение размера.
Итак, перед генерацией кода картинки надо предварительно пройти по всем пикселям и найти наиболее часто встречающийся цвет: