| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Декодер для JPEG. |
| Автор: Pogreb 13.10.2006, 21:30 |
| Мне надо написать свой алгоритм декодирования JPEG'а (для просмотра). Не могу разобраться с алгоритмом Хаффмана, все остальное выглядит понятным. Как я понял из лит-ры, он предназначен для сжатия монохромных изображений, но тогда как поступить с тем ,что jpeg цветной формат. Или же каждая компонента кодируется отдельно? Помогите, кто что знает... |
| Автор: Earnest 14.10.2006, 17:59 |
| Где Хаффман, а где JPEG... что-то ты напутал... Хаффман действительно предназначен для сжатия бинарных растров, и используется, например, в tiff-формате, и некоторых других... Проще найти исходник, я думаю, должны быть, алгоритм давно используемый. |
| Автор: Alexeis 14.10.2006, 19:25 | ||
да нет не напутал все верно. Вот тут на английском http://www.filedonkey.com/url/681C93FF04F613A0B3FBF77DB2D3674C А вот тут на русском http://www.matrix-wb.h1.ru/article/formats/jpeg-rus.html |
| Автор: Pogreb 15.10.2006, 02:52 |
| Например, для байта 6 (эквивалент (0,6)) у нас есть код Хаффмана = 111000; для байта 69 = (4,5) (например) у нас есть 1111111110011001 21 = (1,5) — 11111110110 4 = (0,4) — 1011 33 = (2,1) — 11011 0 = EOB= (0,0) — 1010 поясните мне данный кусочек. Я не могу найти никаких закономерностей с таблицей Хаффмана. ( Это последний этап кодирования Хаффмана) |
| Автор: maxim1000 15.10.2006, 03:15 |
| каждому байту ставится код из некоторого количества битов в последовательности байт каждый элемент заменяется своим кодом - получается последовательность бит для того, чтобы можно было раскодировать такое, есть необходимое и достаточное условие: ни один байт не должен иметь код, который совпадает или является началом кода другого байта тогда декодирование делается просто: берём один бит, если он является кодом какого-нибудь байта, то вот он - очередной элемент, если нет добавляем к нему второй бит и т.д. как только получили чей-то код, записываем соответствующий байт в декодированную последовательность и продолжаем единственное неудобство - нужно знать таблицу соответствия кодов на приёмном конце теперь, собственно, сжатие: оно основанно на присвоении коротких кодов часто встречающимся байтам, т.е. для построения хорошей таблицы нужно знать реальное распределение вероятности (его можно получить, анализируя сжимаемые данные) или, по крайней мере, иметь какую-то модель, которая хорошо аппроксимирует распределение в большинстве случаев преимущество первого способа - по реальному распредлению строится действительно оптимальная таблица кодов, приближённое распределение будет давать менее хорошие результаты (зависит от качества аппроксимации) преимущество второго способа - если модель "вбита в исходник", то её не надо передавать по каналу связи или сохранять в файле, т.к. она и так известна, в первом способе нужно передавать либо таблицу кодов, либо распределение, по которому она должна быть построена (не в курсе, какой способ выбран в JPEG) всю эту схему часто называют сжатием по Хаффманну, однако, он, насколько я слышал, предложил только сам способ построения оптимальной таблицы по распределению: ищем два символа с самыми маленькими вероятностями, присваиваем последний бит кода одному 1, другому 0 и дальше рассматриваем их как один символ (вероятность объединённого символа - сумма исходных) потом повторяем процедуру в конце концов получим бинарное дерево, листьями которого будут исходные символы, а код можно будет получить двигаясь от корня к нужному символу и записывая по пути 0 или 1 в зависимости от ветки (левой или правой) |
| Автор: Pogreb 15.10.2006, 14:23 |
| Если я все правильно понял - кол-во нулей и категория(по Хаффману) кодируются по встроенной таблице в один байт |
| Автор: Pogreb 1.11.2006, 00:23 |
| Ну у меня еще вопрос будет. Народ кто имел дело с jpeg, подскажите!!! В начале скана во всех файлах идут три одинаковых байта 00 3F 00(hex). Что это за байты и что с ними делать??? |
