Главная страница
    Top.Mail.Ru    Яндекс.Метрика
Форум: "Прочее";
Текущий архив: 2013.03.22;
Скачать: [xml.tar.bz2];

Вниз

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

 
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]

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


 
Inovet ©   (2012-10-17 19:54) [29]

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

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

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


 
xayam ©   (2012-10-17 19:55) [30]


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

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

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


 
xayam ©   (2012-10-17 19:56) [31]


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

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


 
Inovet ©   (2012-10-17 20:00) [32]

> [31] xayam ©   (17.10.12 19:56)
> вопрос не в "хранить" :)

У тебя уже будет вместо 15 бит 4


 
Inovet ©   (2012-10-17 20:01) [33]

> [32] Inovet ©   (17.10.12 20:00)
> 4

или сколько там?


 
Rouse_ ©   (2012-10-17 20:02) [34]


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

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


 
xayam ©   (2012-10-17 20:05) [35]


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

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


 
Inovet ©   (2012-10-17 20:07) [36]

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

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


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


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


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


 
xayam ©   (2012-10-17 20:12) [38]


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

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

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

:)


 
xayam ©   (2012-10-17 20:15) [39]


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

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

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


 
Inovet ©   (2012-10-17 20:24) [40]

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

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



Страницы: 1 2 3 вся ветка

Форум: "Прочее";
Текущий архив: 2013.03.22;
Скачать: [xml.tar.bz2];

Наверх




Память: 0.55 MB
Время: 0.076 c
15-1343893780
Wadimka
2012-08-02 11:49
2013.03.22
Подскажите куда копать


15-1351711327
Дмитрий С
2012-10-31 23:22
2013.03.22
Логи


15-1349268838
Чтец
2012-10-03 16:53
2013.03.22
Книга в формате Word


15-1349941653
Empleado
2012-10-11 11:47
2013.03.22
some free e-books from MS


15-1329304162
Сергей М.
2012-02-15 15:09
2013.03.22
Аська в очер.раз мудрит ?.. Или я что-то пропустил ?)





Afrikaans Albanian Arabic Armenian Azerbaijani Basque Belarusian Bulgarian Catalan Chinese (Simplified) Chinese (Traditional) Croatian Czech Danish Dutch English Estonian Filipino Finnish French
Galician Georgian German Greek Haitian Creole Hebrew Hindi Hungarian Icelandic Indonesian Irish Italian Japanese Korean Latvian Lithuanian Macedonian Malay Maltese Norwegian
Persian Polish Portuguese Romanian Russian Serbian Slovak Slovenian Spanish Swahili Swedish Thai Turkish Ukrainian Urdu Vietnamese Welsh Yiddish Bengali Bosnian
Cebuano Esperanto Gujarati Hausa Hmong Igbo Javanese Kannada Khmer Lao Latin Maori Marathi Mongolian Nepali Punjabi Somali Tamil Telugu Yoruba
Zulu
Английский Французский Немецкий Итальянский Португальский Русский Испанский