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

[abc_qmost]

Существуе алгоритм сжатия бинарных изображений без потерь, который, н-р, отсканированную книгу с одним текстом в 300 стр. с хорошим разрешением 600 dpi позволяет сохранить на дискете (1.44 Mb). Может быть кто-то знает более эффективный алгоритм сжатия бинарных изображений без потерь?

[maxal]

PNG например:
http://png.simhold.ru/
http://rus-linux.net/zen/png_feature/png_feature.html

[abc_qmost]

maxal писал(а):

PNG например:
http://png.simhold.ru/
http://rus-linux.net/zen/png_feature/png_feature.html

Это Вы, мягко говоря, погорячились. У меня дискета не 1.44 Gb, а 1.44 Mb.

[maxal]

PNG содержит одни из лучших алгоритмов сжатия изображений без потерь. Если результат получается для вас слишком большим, то нужно смотреть в сторону алгоритмов сжатия с потерями - например, djvu.

[abc_qmost]

maxal писал(а):

PNG содержит одни из лучших алгоритмов сжатия изображений без потерь. Если результат получается для вас слишком большим, то нужно смотреть в сторону алгоритмов сжатия с потерями - например, djvu.

Мне надо без потерь. Я думаю, что и с потерями ( в данном случае djvu) на одну дискету отсканированная с разрешением 600 dpi книга в 300 страниц не уместится.

[Someone]

Если это просто текст - без формул и рисунков, его надо распознать (с сохранением строк, страниц и минимальной информации о шрифтах) и потом сжать.

[abc_qmost]

Someone писал(а):

Если это просто текст - без формул и рисунков, его надо распознать (с сохранением строк, страниц и минимальной информации о шрифтах) и потом сжать.

Давайте представим, что это нераспознаваемый текст. Да и с распознаваемым текстом могут возникнуть проблемы. А если это рукописный текст? Я с этим сталкивался - в 1992 году в университете г. Buffalo занимался распознаванием рукописного текста, связанным с почтовой тематикой.

[незваный гость]

Я сделал несколько грубых прикидок.

1) Текст ч/б, лист 5" х 7": размер несжатой книги 450.6 МБ, сжатие 1:313 (на самом деле, нужно лучше).

2) Текст 300 страниц х 2 КБ/стр. = 600 КБ.

Вывод: Очень чистый текст (после скана) может быть так сжат Осталось дело за малым

Но! этот алгоритм сжатия должен быть рассчитан на сжатие именно текста, а не изображения.

Часть алгоритмов можно посмотреть в DJVU. В конце концов, можно выделять глифы и сжимать их без потерь.

Но меня не оставляет вопрос: нафига? Где найти дискету? Где взять флоповод? Почему нужен lossless? Почему такие жесткие требования на сжатие?

И, наверное, мне пока просто не хватает информации о задаче.

Есть много нюансов: размеры памяти, доступной компрессору / декомпрессору, баланс скорости их работы, произвольность доступа к страницам, значимость константных затрат (например, при больших начальных затратах: книга 300 стр. — 1.44 МБ, 600 стр. — 2.0 MБ, 10 стр. — 920 КБ).

[PAV]

Все это очень малореально. Я еще готов допустить, что можно так сжать изначально электронный вариант книги (в смысле - напечатанный сразу с компьютера в графический файл), где все изображения букв идеально одинаковы и нет никаких посторонних шумов. В реальном скане такого не бывает, всегда есть шумы и погрешности, которые при сжатии без потерь тоже все придется закодировать. По объему реальной информации эти шумы могут в разы превосходить объем "полезной" информации, содержащейся в книге.

Я думаю, что если Вы сумеете такое придумать и отладить, то сможете разбогатеть.

[abc_qmost]

PAV писал(а):

Все это очень малореально. Я еще готов допустить, что можно так сжать изначально электронный вариант книги (в смысле - напечатанный сразу с компьютера в графический файл), где все изображения букв идеально одинаковы и нет никаких посторонних шумов. В реальном скане такого не бывает, всегда есть шумы и погрешности, которые при сжатии без потерь тоже все придется закодировать. По объему реальной информации эти шумы могут в разы превосходить объем "полезной" информации, содержащейся в книге.

Я думаю, что если Вы сумеете такое придумать и отладить, то сможете разбогатеть.

Алгоритм, о котором я сообщал, использует информацию для кодирования из всей отсканированной книги. Вот соответствующая выдержка для legal document (http://www.cartesianinc.com/Tech/samples.html):

число страниц 1 2 3 4 5 6
сжатие 325 434 486 533 574 610

Что касается фотографий, то для применения сжатия их необходимо перевести в Halftoned photograph, но сжатие не такое эффективное, хотя заметно лучше чем для CCITT4 (раз в 5 с хвостиком). Но для этого надо владеть искусством преобразавания грея в хороший halfton. Этим искусством владеют алгоритмы, зашитые в PostScript'овские принтеры. У меня есть реализации этого преобразования, которые в чем-то превосходят эти алгоритмы, а в чем-то уступают. Возможно, есть и свободно распространяемые хорошие алгоритмы, но я этого не знаю.
Хорошо изданную книгу в 311 стр. с 32 фото мне удалось сжать до 1.8 Mb.

[незваный гость]

ОК. Мы убедились, что это возможно. Мы даже догадались о некоторых свойствах, еще до того, как прочитали материалы сайта.

PAV писал(а):

Я думаю, что если Вы сумеете такое придумать и отладить, то сможете разбогатеть.

Разбогатеть не так-то просто. Не очень понятен способ извлечения денег.

ZIP стал de facto стандартом Интернета, но Phil Katz не стал Ларри Эллисон. DJVU как источник дохода тоже не очень понятен.

Продать? Кому? Фирмам с большим количеством документов? Производителям сканеров? Adobe?

Раскручивать как стандарт интернета?

~~~

abc_qmost, Вы предлагаете бросить им вызов?

[Zai]

Книга в 300 страниц содержит около 850000 букв. Пусть каждая буква имеет длину после сжатия полбайта. Итого получается 425 Кб. Если при комрессировании учитывать частотность слов (библиотека слов 4000 при длине слова 6 букв) можно провести компрессию до 150 Кб. Средняя компрессация gzip тоже не менее 6.
При размере несжатой книги в 450 МБ и сжатие 300 раз Вы неявно создали библиотеку символов букв но с несколькими реализациями а также библиотеку слов. Текст был очень контрастным без характерных для сканирования шумов на границе, что не всегда получается для книг старых изданий.

[PAV]

незваный гость писал(а):

Разбогатеть не так-то просто. Не очень понятен способ извлечения денег.

Порассуждаю гипотетически.

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

Также нужно представить себе, какие возможные коммерческие приложения могут быть заинтересованы в новом эффективном алгоритме сжатия. Возможно, подумать о том, какие еще материалы помимо книг могут быть охвачены этим способом.

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

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

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

[abc_qmost]

Zai писал(а):

Книга в 300 страниц содержит около 850000 букв. Пусть каждая буква имеет длину после сжатия полбайта. Итого получается 425 Кб. Если при комрессировании учитывать частотность слов (библиотека слов 4000 при длине слова 6 букв) можно провести компрессию до 150 Кб. Средняя компрессация gzip тоже не менее 6.
При размере несжатой книги в 450 МБ и сжатие 300 раз Вы неявно создали библиотеку символов букв но с несколькими реализациями а также библиотеку слов. Текст был очень контрастным без характерных для сканирования шумов на границе, что не всегда получается для книг старых изданий.

Я говорил о принципиальной возможности, которая, как я указал, практически реализуема.
Не все так просто. Например, результаты для halfton'а можно улучшить.
Кроме того, очень хорошо сжимаются рисунки (всяческие графики) для научных журналов.

[respekt]

Zai писал(а):

Книга в 300 страниц содержит около 850000 букв. Пусть каждая буква имеет длину после сжатия полбайта. Итого получается 425 Кб. Если при комрессировании учитывать частотность слов (библиотека слов 4000 при длине слова 6 букв) можно провести компрессию до 150 Кб. Средняя компрессация gzip тоже не менее 6.
При размере несжатой книги в 450 МБ и сжатие 300 раз Вы неявно создали библиотеку символов букв но с несколькими реализациями а также библиотеку слов. Текст был очень контрастным без характерных для сканирования шумов на границе, что не всегда получается для книг старых изданий.

Алгоритм более иезуитский, чем Вы его представляете.