Наиболее эффективный алгоритм сжатия

← →
xayam © (2012-10-17 18:32) [0]

для черно-белых изображений типа этого

[

каждый пиксел обозначен черным квадратиком
красный линией обозначен центр симметрии
зелёный цвет, чтобы лучше было видно

очень длинное по высоте означает порядка 10^6 и больше...

]

http://ic.pics.livejournal.com/xayam/26173943/14570/14570_original.png

?

← →
Kerk © (2012-10-17 18:37) [1]

Сжатие с потерями или без?

← →
брат Птибурдукова (2012-10-17 18:43) [2]

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

← →
xayam © (2012-10-17 18:47) [3]

> Сжатие с потерями или без?

БЕЗ

← →
xayam © (2012-10-17 19:04) [4]

> сохраняем координаты условного начала фигуры, бежим по границе,
> каждый пиксель обозначаем направлением (3 бита): вверх,
> вниз, вверх-налево

есть ещё идея центральные пикселы вообще "убрать", поскольку этот прямоугольник легко восстановить:

http://ic.pics.livejournal.com/xayam/26173943/14642/14642_original.png

и сжимать это (левая и правые части соединены):

http://ic.pics.livejournal.com/xayam/26173943/14867/14867_original.png

Похоже на японские свечи у трейдеров на фин.рынков, хотя сама инфа к этому никакого отношения не имеет (честно :)

← →
Rouse_ © (2012-10-17 19:06) [5]

> xayam © (17.10.12 18:32)
> для черно-белых изображений типа этого

Ну для начала перевести все это из байтов в биты - сжатие в 8 раз как никак :) А дальше уже можно придумывать.

← →
Rouse_ © (2012-10-17 19:08) [6]

зы: ну с условием что черно-белое изображение без градаций серово, т.е. 0 - белый пиксель, 1 - черный

← →
xayam © (2012-10-17 19:10) [7]

> Ну для начала перевести все это из байтов в биты

я так не думаю, это помешает увидеть суть

← →
xayam © (2012-10-17 19:11) [8]

> из байтов в биты

опс

из битов в байты?

← →
Rouse_ © (2012-10-17 19:12) [9]

> xayam © (17.10.12 19:10) [7]
> я так не думаю, это помешает увидеть суть

Эмм, вообще-то результатом сжатия обычно является практически идеальный "белый шум", т.е. энтропия блока данных при идеальном сжатии равна восьми, при неидеальном, очень близко находится рядом с этим значением. В результирующем блоке увидеть что-то нереально... Или мы не про то говорим?

← →
Rouse_ © (2012-10-17 19:14) [10]

> xayam © (17.10.12 19:11) [8]
>
> > из байтов в биты
>
> опс
>
> из битов в байты?

эээ :))) Нет, из байтов в биты :) Ну например если у тебя блок 8 на 8 кодируется 64 байтами (по 1 на пицсель) то его можно выразить в 8 байт, каждый байт на одну 8-пиксельную строчку :)

← →
xayam © (2012-10-17 19:18) [11]

> Нет, из байтов в биты

чего-то не понял, это же и так уже биты и есть...

черный квадрат = 1 пиксел = бит установлен в 1

← →
xayam © (2012-10-17 19:19) [12]

картинки

http://ic.pics.livejournal.com/xayam/26173943/14265/14265_original.png
http://ic.pics.livejournal.com/xayam/26173943/14642/14642_original.png
http://ic.pics.livejournal.com/xayam/26173943/14867/14867_original.png

это битовые поля УЖЕ!

← →
Rouse_ © (2012-10-17 19:22) [13]

> xayam © (17.10.12 19:18) [11]

Ну ты же не написал как это у тебя хранится.
Смотри:
картинка такая (* -черны, _ - белый)
"*__*__**"
это можно хранить как
const MyLine: array [0..7] of Byte = (1, 0, 0, 1, 0, 0, 1, 1);
А можно как:
const MyLine: Byte = 147; // 1001001

← →
SergeyIT © (2012-10-17 19:22) [14]

Перфолента?

← →
MBo © (2012-10-17 19:22) [15]

ширина какая?

← →
xayam © (2012-10-17 19:23) [16]

> Ну ты же не написал как это у тебя хранится

да это не важно как хранится,

вопрос как сжать это? наиболее эффективный алгоритм?

← →
Rouse_ © (2012-10-17 19:27) [17]

> xayam © (17.10.12 19:23) [16]
> да это не важно как хранится,

Ну как-же не важно? :)
А алгоритм - тут вариантов не много, хаффман, LZW и RLE

← →
xayam © (2012-10-17 19:27) [18]

> Перфолента?

один из вариантов после японских свечей :)
хотя и на акустич. волну тоже похоже если повернуть на 90 градусов

> ширина какая?

заранее неизвестно, но можно посчитать на небольшом блоке-странице, для больших файлов нереально медленно это, да и не за чем, наверное, наиболее вероятная ширина = 20 пикселам - 2 центральных = 18

← →
MBo © (2012-10-17 19:29) [19]

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

← →
SergeyIT © (2012-10-17 19:34) [20]

Черные квадраты без пробелов идут - то есть просто строчка длины К сдвинутая на М пикселей?

← →
Inovet © (2012-10-17 19:36) [21]

Судя по картинке, кождая горизонтальная линия непрерывна - т.е. задаётся смещением от центра и длиной, или двумя длинами. Почему сразу так не хранить?

← →
Rouse_ © (2012-10-17 19:38) [22]

А кстати, недавно нашел еще один оригинальный вариант сжатия: http://podrobnosti.ua/technologies/2012/07/27/849624.html

← →
xayam © (2012-10-17 19:38) [23]

> Черные квадраты без пробелов идут

без пробелов

> то есть просто строчка длины К сдвинутая на М пикселей?

да
отцентрировано просто, можно отцентрировать влево или вправо, но так лучше видно имхо

← →
Rouse_ © (2012-10-17 19:39) [24]

Ой не - не то, это крипто, а был еще один вариант, тоже от японской головоломки, блин забыл как называется... щас попробую поискать

← →
Rouse_ © (2012-10-17 19:41) [25]

А во: http://ru.wikipedia.org/wiki/%D0%AF%D0%BF%D0%BE%D0%BD%D1%81%D0%BA%D0%B8%D0%B9_%D0%BA%D1%80%D0%BE%D1%81%D1%81%D0%B2%D0%BE%D1%80%D0%B4

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

← →
xayam © (2012-10-17 19:42) [26]

> да
> отцентрировано просто, можно отцентрировать влево или вправо,
> но так лучше видно имхо

опс, ошибка нельзя влево вправо. Центр нужно знать.

← →
xayam © (2012-10-17 19:50) [27]

> Rouse_ © (17.10.12 19:41) [25]
> Японский кроссворд

интересно. Можно переделать битое поле на несколько таких ниток в ширину, отцентрировать каждую нить,
оформить в квадрат, и такой алгоритм может быть эффективным...

> Сжимается достаточно хорошо

есть код, примеры?

← →
Rouse_ © (2012-10-17 19:52) [28]

> xayam © (17.10.12 19:50) [27]

Сам не писал, но в инете приводили варианты... Сам тоже хочу как время найдется заняться этой темой...

> [27] xayam © (17.10.12 19:50)
> Можно переделать битое поле на несколько таких ниток в ширину

Зачем тебе вообще битовые поля? Это уже избыточная информация. Ты прочитал?

> [21] Inovet © (17.10.12 19:36)

> Сам тоже хочу как время найдется заняться этой темой

могу любой файл привести к такому виду :)

скоопирируемся?

> Inovet © (17.10.12 19:36) [21]
> Судя по картинке, кождая горизонтальная линия непрерывна
> - т.е. задаётся смещением от центра и длиной, или двумя
> длинами. Почему сразу так не хранить?

вопрос не в "хранить" :)

> xayam © (17.10.12 19:55) [30]
> скоопирируемся?

:) я бы не против, но это у меня стоит в рабочих планах, т.е. пока начальство отмашку не даст на доработку ядра базы след версии, этим не занимаюсь :)

> У тебя уже будет вместо 15 бит 4
> или сколько там?

битовое поле не для хранения, это как бы промежуточное состояние между исходным файлом и сжатым

> [35] xayam © (17.10.12 20:05)
> это как бы промежуточное состояние между исходным файлом и сжатым

Почему тогда акцент сделан на сжатие изображения?

← →
брат Птибурдукова (2012-10-17 20:08) [37]

> есть ещё идея центральные пикселы вообще "убрать"
Ты не понял, центральные пиксели вообще не рассматриваются, мы бежим по контуру фигуры.

> Судя по картинке, кождая горизонтальная линия непрерывна
> - т.е. задаётся смещением от центра и длиной, или двумя
> длинами. Почему сразу так не хранить?
Сколько отвести под эти длины? Байт, два, четыре? Будет ли экономия? ;-)

> центральные пиксели вообще не рассматриваются, мы бежим
> по контуру фигуры

я понял, но без центральных пикселей твои приращения могут занимать меньше места...
аналогично этому:

> Сколько отвести под эти длины? Байт, два, четыре? Будет
> ли экономия?

:)

> Почему тогда акцент сделан на сжатие изображения?

черно-белого изображения

Почему? Битовое поле слишком заумное словечко :)
черное-белое изображение быстрей доходит

> [37] брат Птибурдукова (17.10.12 20:08)
> Сколько отвести под эти длины? Байт, два, четыре? Будет ли экономия? ;-)

Автор умалчивает. В любом случае меньне, чем в битовых масках.

Наиболее эффективный алгоритм сжатия Найти похожие ветки