Извините, ничего не найдено.

Tronix · 06.11.2009, 16:14

Дано изображение 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 точек.

Дальше мысль не пошла. Чувствую что можно еще лучше сделать, и мне это нужно сделать. Если кто-то знает подобные алгоритмы для ч/б изображения прошу поделится.

SBJoker · 06.11.2009, 16:44

RLE работает так (на примере сжатия на уровне байтов):
- анализ данных и выявление самого редкого байта, этот байт будет признаком сжатой алгоритмом последовательности обозначим его буквой U, и сразу записываем его в выходной поток.
- сжатие работает так, читаем первый байт и запоминаем, читаем следующий, если байты неравны записываем первый байт в выходной поток (т.к. сжимать нечего.
Повторяем до тех пор пока вподряд небудет минимум 3х одинаковых байт (только для последовательностей от более 3х байт имеет RLE имеет смысл). Кодируем последовательность одинаковых байт в виде: U B C, где U - байт идентификатор сжатого блока, B - повторяемый байт, C - число повторений.

Если нам во входном потоке попадается байт U, мы его кодируем последовательностью UU.

Эта реализация обладает рядом свойств:
- сжатие не увеличивает размер файла если данные не сжимаемы. (возможно небольшое увеличение если байт U довольно популярен в данных, хотя алгоритмом оговорено четкое условие выбора байта на эту роль, как самого редкого)
- Максимальная длина сжимаемой последовательности 255 повторов. Последовательности длиной 3, сжимаются в эквивалентную последовательность.

Декомпрессия.
- читаем первый байт это наш U идентификатор.
- читаем байт если это U и следующий байт U то пишем в выходной поток U байт. Т.к. это экранирующая последовательность.
- читаем байт если это U, а следующий байт B не U, то читаем третий байт C и записываем B в выходной поток C раз.
- все остальные байты пишем без изменений.

Tronix · 06.11.2009, 16:49

Спасибо за подробное описание. Очень меткая идея с наименее использующимся байтом. Обязательно возьму на заметку для дальнейшего.

Но увы, с битами (ч/б изображением) такой алгоритм как мне кажется не очень эффективен. Буду думать дальше...

06.11.2009, 17:26

можно попробовать словарём сжимать, тут же будет полно одинаковых последовательностей

12121 · 06.11.2009, 17:40

Важно заметить, что изображение - символ какой-либо цифры (а не произвольный набор рандомных точек).
Так может стоит попытатся узнать что это за цифра? (сравнив с образцами цифр) Если конечно цифра не рисуется по разному каждый раз.

Tronix · 06.11.2009, 18:01

Скажем так, цифра - рукописная (нарисованная от руки), то есть каждый раз меняется.

UPD: А вообще почти угадали, хочу написать распозновалку рукописных цифр. Есть огромная база (60000) изображений с нарисованными от руки цифрами. Изначально она в градиентах серого цвета (255 значений) и занимает 49 мегов. Мне же нужно сжать ее как минимум до мегабайта ))

12121 · 06.11.2009, 19:39

Можно попробовать перед кодированием обрезать пустоту по краям. Например размер примера будет 14х24. Сколько обрезали даже можно не сохранять - потом просто расположить по центру и все.

Tronix · 07.11.2009, 11:41

Ммммммм... Можно конечно попробовать....

Пока остановился на таком алгоритме (приведу для распаковки):
1. Читаем байт N.
2. Если оба старших бита N установлены в 1, то это повторитель. Шестой бит - это цвет точек, остальные пять бит - количество повторений. То есть байт раскладывается на 11CAAAAA, где бит C - цвет точек, биты A - количество повторений.
3. Иначе, прочитанный байт - это просто набор восьми точек. Каждый бит в байте - цвет точки.

Таким образом, если исходное изображение содержало 28x28 пикселей и цвет каждой точки занимал один байт, получается 784 байта. С помощью вышеприведенного алгоритма такая картинка ужимается как правило до 55-60 байт. И в целом, файл с набором картинок 28x28, занимающий ~49 Mb ужался до ~3 Mb. Все равно очень много, не влезет в heap никакого телефона (((
Чтож, займусь пока обрезкой, скоро взглянем на результаты.

UPD: Для наглядности просто приведу небольшую картинку какими могут быть символы:
UPD2: Сделал обрезание, в итоге файл сжался до ~2,7 Mb. Много ((((((

impersonalis · 07.11.2009, 15:36

http://forum.boolean.name/showthread.php?t=1231

SubZer0 · 11.11.2009, 01:00

а если замутить прямоугольниками...

написать прогу которая будет искать прямоугольники черного цвета, потом сортировать их по размеру...

допустим в фигуре данной к примеру по координатам (12,2) располагается большой прямоугольник 3 на 23 пикселя...

найденные прямоугольники пишем в файл... первый "байт" позиция (х - 6 бит; y - 6 бит), второй "байт" размер (х - 6 бит; y - 6 бит)... итого три байта на прямоугольник...

В данной фигуре можно насчитать 8 прямоугольников... 24 байта...

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

это вот что сходу на ум пришло...

программа по закодировке будет ресурсоемкой, зато разкодировка еще быстрей чем чтение файла

Добавлено:

вместо шести бит можно заюзать и пять, а оставшиеся 4 бита от трех байт (5*4=20, а в трех байтах 24) можно за управляющую инфу взять... мож цвет кодировать или еще ченить...

ViNT · 11.11.2009, 01:59

Даже если удастся так сильно скомпрессить базу изображений (хотя в 50 раз врядли получится), то все равно, задача будет слишком сложной для телефона - для каждой введенной цифры нужно распаковать и проверить 60000 масок (на сколько я понял, планируется использовать всю базу?). Даже если хватит памяти - процессор не потянет, будет неприемлемо долго. Лучше уж сделать систему с обучением - пусть пользователь один раз введет все 10 цифр, дальше на их основе сформировать маски (допустим, немного утолстить линии, чтобы учесть неоднородность почерка). Думаю, для системы с низкой производительностью это самый подходящий вариант.

BlackDragon · 11.11.2009, 12:43

Может лучше описывать введенные цифры кривыми, вычислять соответствующуе функции и сравнивать ее параметры с теми, которые соответствуют функции "идеального" написания цифры, ну а затем выбрать наиболее подходящую цифру. Примерно как то так. Наверняка такой (или похожий) алгоритм есть в нете.

Tronix · 11.11.2009, 14:10

Ребят, есть интересные идеи, спасибо. Буду думать, сейчас вообще запутался со своим алгоритмом, наверное буду заново все переписывать.

И еще, вдруг кто-то тоже захочет размять мозги, поэтому предлагаю мини-конкурс -)) Победителю - всяческие регардсы и гридзы )))

Дано:
1) файл numbers.bin, содержащий в себе изображения 10-ти символов. Каждый символ имеет размерность 28x28 пикселей. Каждый пиксель занимает в файле 1 байт и значение этого байта указывает на цвет пикселя. Учесть, что если байт равен 0 - то цвет пикселя череый, если больше нуля - белый.
2) простейшая программа на Turbo/Borland/Virtual/Free Pascal'е, которая отображает на экране в текстовом виде любой из 10 символов из вышеописанного файла. Программа - просто для лучшего понимания формата файла.

Задание:
1) Преобразовать исходный файл numbers.bin в другой файл с минимальным размером. Учесть, что простым преобразованием оригинального файла в битовое представление (8 пикселей = 1 байт, 28x28=784 байт / 8 бит =>98 байт) каждый символ занимает 98 байт, а файл - 98x10 символов = 980 байт. Таким образом, получившийся выходной файл должен быть меньше 980 байт.
2) Написать простую программу, которая работает с получившемся ужатым файлом и позволяет вывести на экран любой из 10 символов.

Вышеобозначенная програмка:



Const 
      num = 0;        {Номеp символа, котоый нужно вывести, от 0 до 9} 
Var 
      f     : File; 
      buf   : Array [1..28,1..28] of Byte; {Массив для одного символа} 
      x, 
      y     : Byte;     {Пеpеменные циклов по x и по y} 
 
Begin 
      assign(f,'numbers.bin'); 
      reset(f,1);                   {Откpываем файл} 
      If IOResult <> 0 then         {Если файл не найден} 
            Begin                   {Выводим сообщение об ошибке} 
                  Writeln('File numbers.bin not found'); 
                  Halt(1);          {и завеpшаем погpамму} 
            End; 
 
      Seek(f,784*num);              {Смещаемся по файлу к нужному символу} 
      BlockRead(f,buf,784);         {Читаем 28x28 байт в буффеp} 
      close(f);                     {Закываем файл} 
 
      For x := 1 to 28 do           {Двигаемся по стокам} 
        Begin 
            For y := 1 to 28 do     {Двигаемся по столбцам} 
                  If Buf[x,y] > 0 then {Если байт больше 0, значит} 
                        Write('1')     {это белый цвет, выводим 1} 
                  else 
                        Write(' ');    {Если pавен нулю - цеpный цвет} 
            WriteLn;            {После завешения pисования стоки} 
                                {пеpеводим куpсоp на следующую стоку} 
        End; 
      WriteLn('Press ENTER to exit...');  {Что-бы окно не сазу закывалось} 
      ReadLn;                             {Ждем нажатия ENTER} 
End.

В архиве файл numbers.bin, простейшая програмка для просмотра файла numbers.bin.