|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Alexander Kamotsky 2:463/544.9 21 May 2002 00:14:47
To : Alexandre Korushkin
Subject : сжатие монохромных изображений
--------------------------------------------------------------------------------
AK> Поделитесь плиз алгоритмами сжатия монохромных изображений.
Hе помню как называется, что-то вроде "древовидного".
Идея в следующем: допустим есть квадратное изображение с размером равном степени
двойки. Строим кодирование, рассматривая картинку по квадратам уменьшающихся
размеров и запоминая только один бит 1 или 0 в зависимости от того, сколько
пикселов преобладает в квадрате. Также используем ещё один бит, чтобы запомнить,
какие квадраты нужно дробить.
Попробую показать на примере. Имеем картинку 8х8
00000000
00111100
00111100
00111100
00000000
00000000
00000000
00000000
1. квадрат 8х8 - больше нулей, пишем в файл бит 0, нужно дробить - бит 1.
итого в файле: 01
2. 4 квадрата 4х4 - им соответствуют биты 0, 0, 0, 0. Биты-флаги продолжения
будут соответственно 1, 1, 0, 0. (я рассматриваю квадраты сверху вниз, слева
направо)
итого в файле: 01 01010000 (биты и флаги я сгруппировал попарно)
3. далее дробим ТОЛЬКО оставшиеся квадраты и для них рассматриваем подквадраты:
им будут соответствовать биты + флаги:
00 01 00 10 (для верхнего левого 4х4)
01 00 10 00 (правый верхний 4х4)
4. осталось раздробить два квадратика 2х2 вверху (по середине): так как это
квадраты 2х2, то можем просто записать биты им соответствующие:
0011 и 0011
итого, имеем файл:
01 01010000 00 01 00 10 01 00 10 00 0011 0011 = 34 бита, если я нигде не ошибся
понятно, что этот алгоритм хорошо сожмёт картинки с прямоугольной графикой и
большими однородными областями...
(не забыть в файл записать размеры исходной картинки)
Полностью белый квадрат любого размера закодируется всего двумя битами - 00.
(чёрный тоже -- 10)
Ещё один плюс этого алгоритма -- возможность эффекта появления картинки при
раскодировании (типа как в JPEG).
Угадай, что нужно сделать, чтобы инвертировать картинку в таком формате? =)
Инвертировать каждый нечётный бит в файле и всё!
P.S. Есть ещё кодирование "уголками", но он намного сложнее и дольше
объясняется. Идея -- выделять и запоминать только вершины чёрных прямоугольников
на изображении. Для чертежей - идеальный формат.
Всего доброго, Alexandre Korushkin.
--- #include <"tearline.cpp">
* Origin: (-: "ниждиро йынтарбо" (2:463/544.9)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
