Сжатие на ATMega, Хаффман с фиксированой таблицей CCITT Group 3 Опции

[crunch]

Кто-то делал, и какие соображения по этому поводу...главный вопрос побыстрее и функция записи во внешнюю SPI память значений не выыровненых по границе байта длиной от 2 до 13 бит

[SasaVitebsk]

Кто-то делал, и какие соображения по этому поводу...главный вопрос побыстрее и функция записи во внешнюю SPI память значений не выыровненых по границе байта длиной от 2 до 13 бит

Я планировал. Но мне необходимо было "на лету". Моделировал. Необходимо около 8К озу только на это. Думаю и так всё на пределе. Распаковку сделать - ещё успеешь, а со сжатием ??? Я бы внешнее озу поставил паралельное.

[sz36]

Необходимо около 8К озу только на это. Думаю и так всё на пределе. Распаковку сделать - ещё успеешь, а со сжатием ???

А зачем для Хафмана с фиксированой таблицей 8К ОЗУ? Там вроде сдвиговый регистр на 8+13байт нужен, и все. Несколько десятков тактов на бит должно получиться без ухищрений.

[SasaVitebsk]

Необходимо около 8К озу только на это. Думаю и так всё на пределе. Распаковку сделать - ещё успеешь, а со сжатием ???

А зачем для Хафмана с фиксированой таблицей 8К ОЗУ? Там вроде сдвиговый регистр на 8+13байт нужен, и все. Несколько десятков тактов на бит должно получиться без ухищрений.

Не буду утверждать, но по-моему, фиксированная таблица - это только начало. А потом она точно также пополняется-модифицируется. Насколько я понимаю, это сделано чтобы изначально не формировать таблицу и этим сэкономить на первоначальном этапе. Можно конечно и с полностью не модифицируемой таблицой, но это если данные передаются практически одни и теже. Сначала формируется таблица, потом устанавливается на оба конца и только потом работает. Для произвольных данных такой метод не даст желаемого коэффициента сжатия. Если таблица будет модифицируема, то средний коэффициен сжатия - 2. Я проверял на файлах.

[crunch]

Необходимо около 8К озу только на это. Думаю и так всё на пределе. Распаковку сделать - ещё успеешь, а со сжатием ???

Да не тут ОЗУ нуно порядка двух длин строки если стараться быстро а если не спешить то и вообще проблемма не рассматривается


А зачем для Хафмана с фиксированой таблицей 8К ОЗУ? Там вроде сдвиговый регистр на 8+13байт нужен, и все. Несколько десятков тактов на бит должно получиться без ухищрений.

Так порядка 40-50 получается...а хотеться меньше вот и думаю



Не буду утверждать, но по-моему, фиксированная таблица - это только начало. А потом она точно также пополняется-модифицируется.

Фиксированая таблица она и есть фиксированая не дополняется ее составили на основе експерументов с факсовыми изображениями и там каждой длине подряд идущих одинаковых бит отвечает код длиной от 2 до 13 бит дело в том что сжиматься будут только черно-белые изображения текстовых документов

Сообщение отредактировал crunch - Sep 5 2006, 12:41

[SasaVitebsk]

Фиксированая таблица она и есть фиксированая не дополняется ее составили на основе експерументов с факсовыми изображениями и там каждой длине подряд идущих одинаковых бит отвечает код длиной от 2 до 13 бит дело в том что сжиматься будут только черно-белые изображения текстовых документов

Просмотрел что я делал. Метод Хаффмана. Т.е. всё правильно. Правда для модема, а не для факса. Возможно в Вашем CCIT... есть отличия. Привожу выдержку из "Руководства ..." по модему USRobotics Courier. "Если модемы успешно уст. соедин., то они договариваются о сжатии (V.42bis). .... Они договариваются о размере словаря ... 9бит - 512, 10 - 1024, 11 - 2048 .... Сжатие V.42bis более эффективно, т.к. этот протокол динамически удаляет неиспользуемые более строки. Кроме этого, он работает лучше с файлами, которые заранее сжаты."

В принципе я это макетировал. (Писал на Паскале) По-моему это у меня где-то есть. Это также есть в книге которую я отправлял на FTP.

Да, кстати, сжатие обеспечивается не за счёт "там каждой длине подряд идущих одинаковых бит отвечает код длиной от 2 до 13 бит". Метод словарей немного интересней работает. И ещё: Все модемы идут с предустановленными словарями. Найти его мне не удалось. Без этого совместимости не будет. Начинать надо с одинаковыми словарями.

[singlskv]

Да, кстати, сжатие обеспечивается не за счёт "там каждой длине подряд идущих одинаковых бит отвечает код длиной от 2 до 13 бит". Метод словарей немного интересней работает.

Именно так каждой длине подряд идущих одинаковых бит отвечает код длиной от 2 до XX бит".
//-----------------------
So how do the Group 3 and Group 4 compression mechanisms work?

Both schemes encode the source image on a horizontal scanline-by-scanline basis, corresponding to the way in which documents are scanned and printed on a facsimile machine. The difference lies in the way the two standards handle successive scanlines - in Group 3, each scanline is encoded independently, whereas in Group 4, scanlines are encoded with reference to the previous one, resulting in improved compression ratios.

In Group 3, a scanline is encoded as a set of runs, each representing a number of white or black pixels, with white runs alternating with black runs. Every run is encoded using a variable number of bits, which can be uniquely identified upon decoding. This means that frequently occurring lengths of run may be encoded very efficiently, at the expense of the infrequent ones. For example, a black run of 2 or 3 pixels is encoded using just 2 bits, whereas one of 1000 pixels is encoded in 25.
//-------------------------------

Если нужно кодировать именно факсовые данный (black& white), то
Вы вероятно не найдете варианта дающего существенно большую
компрессию ( конечно если у Вас там не сплошные картинки в black& white )
А скорость будет максимальной.

[SasaVitebsk]

Да, кстати, сжатие обеспечивается не за счёт "там каждой длине подряд идущих одинаковых бит отвечает код длиной от 2 до 13 бит". Метод словарей немного интересней работает.

Именно так каждой длине подряд идущих одинаковых бит отвечает код длиной от 2 до XX бит".
//-----------------------
So how do the Group 3 and Group 4 compression mechanisms work?

Both schemes encode the source image on a horizontal scanline-by-scanline basis, corresponding to the way in which documents are scanned and printed on a facsimile machine. The difference lies in the way the two standards handle successive scanlines - in Group 3, each scanline is encoded independently, whereas in Group 4, scanlines are encoded with reference to the previous one, resulting in improved compression ratios.

In Group 3, a scanline is encoded as a set of runs, each representing a number of white or black pixels, with white runs alternating with black runs. Every run is encoded using a variable number of bits, which can be uniquely identified upon decoding. This means that frequently occurring lengths of run may be encoded very efficiently, at the expense of the infrequent ones. For example, a black run of 2 or 3 pixels is encoded using just 2 bits, whereas one of 1000 pixels is encoded in 25.
//-------------------------------

Если нужно кодировать именно факсовые данный (black& white), то
Вы вероятно не найдете варианта дающего существенно большую
компрессию ( конечно если у Вас там не сплошные картинки в black& white )
А скорость будет максимальной.

Я говорю что разбирался и делал прогу, а Вы мне приводите выдержку из статьи. Ещё раз повторяю: немного не так. Последовательность действительно кодируется. Часто используемая - меньшим колличеством бит, редко использующаяся - большим. Но причём здесь картинка??? Какая разница чёрно-белая или цветная или вообще файл программы??? Методу по барабану какую инфу сжимать если словарь образуется в процессе сжатия. Коэффициент сжатия отределяется хаотичностью передаваемых данных. Но если словарь фиксированный, то коэффициент сжатия будет меньше. Я не слышал о фиксированном. Я слышал о предустановленном. Это не одно и тоже.

Но в любом случае, при создании Вам придётся сначала сделать с нормальным словарём. Потом передать большое колличество информации. Таким образом получить словарь предустановленный или фиксированный. Руками или на глаз Вы его не создадите. Я бы например не взялся. Да и никто, я думаю не заполнит его.

Почитайте книгу. Там очень доступным языком описано.

[crunch]

Я вот тоже думаю что спор и емоции ни о чем.
По поводу словаря: Суть CCIT Group 3 сжатия такова:

На основе метода Хаффмана для конкретного вида изображений(отсканированые документы с печатным текстом и глубиной цвета 1 бит) на основе обработки огромного количества таких изображений был сформирован словарь(таблица), которая есть в стандарте.
Каждая строка кодируется отдельно для начала она преобразовывается в длины серий(RLE), а после этого длины серий сжимаються по готовой таблице(словарю) методом замены.
допустим последовательность из 8 белых бит встречается чаще всего и ей отвечает - 10 и т.д. коды готовы для значений от 0 до 63 и далее кратно 64 до 2363 бит.
Действительно применимо к данному типу документов сжатие вероятно будет наилутшим.
НО вопрос был в том не делал ли кто-то подобных вещей и КАКИЕ идеи по организации данного алгоритма, конкретно по побитной записи в память значений с переменной длиной(2-13 бит)