Дано изображение 28x28 пикселей, черно-белое. То есть цвет 1 или 0.
Задача - как можно больше его ужать в файле. Теперь вводная:
Важно заметить, что изображение - символ какой-либо цифры (а не произвольный набор рандомных точек). Для наглядности давайте посмотрим на него:
000000000000000000000000000
000000000000000000000000000
000000000011111000000000000
000000000111111000000000000
000000000110111000000000000
000000001110111000000000000
000000011100111000000000000
000000011100111000000000000
000000111000111000000000000
000001110000111000000000000
000000000000111000000000000
000000000000111000000000000
000000000000111000000000000
000000000000111000000000000
000000000000111000000000000
000000000000111000000000000
000000000000111000000000000
000000000000111000000000000
000000000000111000000000000
000000000000111000000000000
000000000000111000000000000
000000000000111000000000000
000000001111111111100000000
000000001111111111100000000
000000001111111111100000000
000000000000000000000000000
000000000000000000000000000
000000000000000000000000000
Рисовал от руки, но идея я думаю ясна. Первое что приходит на ум: двигаемся в циклах по x и y. Берем первые 8 пикселей и запихиваем их в один байт. Далее берем еще 8 пикселей, это будет следующий байт, и еще разок для третьего байта. Так мы закодировали 24 пикселя в 3 байта. Для следующих 4 пикселей (картинка-то у нас в ширину 28 пикселей) берем только половинку следующего байта (4 бита). Далее по циклу с учетом половинного байта, тоесть следующую итерацию начинаем со сдвигом в 4 бита.
Таким образом мы просто переводим битовое изображение в байты.
Посмотрев на изображение, мы видим, что например первая линия состоит полностью из нулей. Тоесть по вышеописанному алгоритму мы получим в hex: 00 00 00 00 (4 байта). Здесь на ум приходит применить что-то типа алгоритма RLE (если не ошибаюсь), то есть если у нас последовательность повторяющихся значений цвета больше одного, ввести повторитель. Тогда формат файла будет таким: первый байт - сколько раз повторить, второй байт - цвет точки. Таким образом, мы можем записать: 28 00 (hex), что значит: повторить вывод точки 28 раз с цветом ноль. Что ж, сократили первоначальную запись в 2 раза. Неплохо, но нужно учитывать, что когда точки не будут повторятся, мы будем терять два байта, так как повторитель будет равен одному и еще один байт цвета. Закодируем линию по такому алгоритму:
0000000111001110000000000000 -> 07 00 03 01 02 00 03 01 0A 00
Весьма не плохо, но мы значительно теряем на втором байте - байте цвета. Зачем нам 256 значений цвета (целый байт) когда цвета всего два? Тогда значит начинаем копаться в битах )) Тут мне вспомнился давний алгоритм кодирования .PCX файлов, а именно: условимся, что если оба старших бита в байте будут равны 1, то остальные 6 бит -это повторитель а следующий за этим байт - цвет. Если же прочитанный байт будет начинаться с 10XXXXXX или с 01XXXXXXX или 00XXXXXXX, то этот байт следует расценивать просто как набор 8 точек.
Дальше мысль не пошла. Чувствую что можно еще лучше сделать, и мне это нужно сделать. Если кто-то знает подобные алгоритмы для ч/б изображения прошу поделится.