Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 33
то есть выходную последовательность нужно «дожимать» еще архиватором? Или зачем вы сжимали в rar?
Это, чтобы избавиться от избыточности текстового представления и вообще способа кодирования результата. Чтобы можно было сравнить с бинарными контейнерами jpeg'а и прочих алгоритмов.
Я тут вспомнил, что бинарный формат я тоже применял, оказывается. Все стандартные изображения имеют один примерно размер 66614 байт (bmp формат). Мои бинарные эквиваленты занимают где-то 18-20 Кбайт. Это можно увидеть в архиве.
В документе prn2img_2.mcd осуществляется восстановление изображений из *.bin файлов. Можно открыть и посмотреть на работу. Декодирование идёт быстрее, чем кодирование.
Цель этих примеров — показать принципиальную возможность что-то сжимать вообще. Практически использовать алгоритм на гладких изображениях смыла нет. Позже я применил его для коэффициентов вейвлет преобразования. Не знаю только найду или нет эти архивы. Там уже смысла больше будет.
В общем, мы как-то хотели разработать какой-нить новый алгоритм сжатия, используя вейвлеты. Вся теория сжатия основана на «гладких» базисных функциях. Вопрос стоял в том, а как сохранить при этом детали изображения. Они ведь «гладкостью» не обладают, хотя очень важны для восприятия. Это границы, переходы и пр. контуры. Экспериментируя с разными алгоритмами, я понял, что НЧ часть можно пожать только НЧ алгоритмами, а любые попытки подобрать базис для деталей просто переносит ВЧ информацию в коэффициенты для базисных функций.
Вот тогда я и подумал, почему бы не «вырезать» НЧ часть изображения, а оставшуюся часть дожимать уже аналогом алгоритма без потерь. Именно аналогом, т.к. стандартный алгоритм без потерь вряд ли что-то сожмёт в полностью случайных данных. Для изображений же можно сделать небольшую скидку.
Я тут вспомнил, что бинарный формат я тоже применял, оказывается. Все стандартные изображения имеют один примерно размер 66614 байт (bmp формат). Мои бинарные эквиваленты занимают где-то 18-20 Кбайт. Это можно увидеть в архиве.
В документе prn2img_2.mcd осуществляется восстановление изображений из *.bin файлов. Можно открыть и посмотреть на работу. Декодирование идёт быстрее, чем кодирование.
Цель этих примеров — показать принципиальную возможность что-то сжимать вообще. Практически использовать алгоритм на гладких изображениях смыла нет. Позже я применил его для коэффициентов вейвлет преобразования. Не знаю только найду или нет эти архивы. Там уже смысла больше будет.
В общем, мы как-то хотели разработать какой-нить новый алгоритм сжатия, используя вейвлеты. Вся теория сжатия основана на «гладких» базисных функциях. Вопрос стоял в том, а как сохранить при этом детали изображения. Они ведь «гладкостью» не обладают, хотя очень важны для восприятия. Это границы, переходы и пр. контуры. Экспериментируя с разными алгоритмами, я понял, что НЧ часть можно пожать только НЧ алгоритмами, а любые попытки подобрать базис для деталей просто переносит ВЧ информацию в коэффициенты для базисных функций.
Вот тогда я и подумал, почему бы не «вырезать» НЧ часть изображения, а оставшуюся часть дожимать уже аналогом алгоритма без потерь. Именно аналогом, т.к. стандартный алгоритм без потерь вряд ли что-то сожмёт в полностью случайных данных. Для изображений же можно сделать небольшую скидку.
Стандартное тестовое изображение птицы bird.bmp занимает 66614 байт. «Сжатое» двумерным вариантом алгоритма текстовое представление данных в rar архиве занимает 10138 байт.
А сколько занимает стандартное тестовое изображение птицы bird.bmp в rar архиве?
См. комментарий выше.
Попробовал тут: bird.zip — 40867 байт, bird.7z — 35140 байт. Rar'а под рукой нет. Можете попробовать сами, в архиве есть много стандартных тестовых изображений в bmp формате.
Не мешает добавить дельта-кодирование и квантование, будет проще сжимать это каким-нибудь словарным алгоритмом. Любой формат — будь то jpg или png — состоит из обработки сигнала и сжатия deflate (в те времена лучше не знали). Сейчас можно скрестить с более эффективным lzma или bzip2. После этого уже было бы интересно посмотреть на результат.
Но мне кажется природу не обманешь. Если разложить картинку на JPG (7 килобайт) и остатки (шум, оставшийся после сжатия), потом сжать остатки алгоритмом bzip2 — получим исходные 30 килобайт, до которых можно ужать картинку форматом PNG. Сжимать годные остатки каким-то шумом можно, но это всё равно что просто добавить белый шум на изображение — будет создаваться иллюзия отсутствия артефактов сжатия, хотя PSNR упадёт. Такую технику использовали ещё в стародавние времена в играх, как только — чтобы текстуры не казались уж очень размытыми, в них подмешивали более мелкую текстуру шума:
Самое логичное что приходит на ум — сжимать таким методом «годные остатки», но есть предчувствие, что качество от этого не сильно увеличится.
Но мне кажется природу не обманешь. Если разложить картинку на JPG (7 килобайт) и остатки (шум, оставшийся после сжатия), потом сжать остатки алгоритмом bzip2 — получим исходные 30 килобайт, до которых можно ужать картинку форматом PNG. Сжимать годные остатки каким-то шумом можно, но это всё равно что просто добавить белый шум на изображение — будет создаваться иллюзия отсутствия артефактов сжатия, хотя PSNR упадёт. Такую технику использовали ещё в стародавние времена в играх, как только — чтобы текстуры не казались уж очень размытыми, в них подмешивали более мелкую текстуру шума:
Скрытый текст
Самое логичное что приходит на ум — сжимать таким методом «годные остатки», но есть предчувствие, что качество от этого не сильно увеличится.
Интересный факт по поводу текстур.
Оказывается, в архиве есть продолжение моих изысканий. Документ newalg.mcd делает упаковку, а unnewalg.mcd — распаковку с уже усовершенствованным алгоритмом. Как я и говорил, применяем какой-либо нч-алгоритм, гладкую часть не трогаем, а сжимаем только детали. Только для их работы в Mathcad нужна пользовательская dll, в которой находится дискретный алгоритм двумерного вейвлет-Хаар преобразования.
Тут дело даже не в каком-то выигрыше в степени сжатия. Мне хотелось побороть проблему со сжатием деталей и чтобы при восстановлении они не выглядели белым шумом. Я же всё-таки ищу «похожий шум», а не любой попавшийся. Кстати, в втором варианте алгоритма я уже подстраиваюсь под тип распределения «случайного сигнала», т.к. в этом случае искомые совпадения будут больше походи на куски из оригинала.
На картинке ниже при увеличении видны какие-то артефакты. Всё-таки надо было мне писать программу не в Mathcad, так как она значительно усложнилась. Подозреваю, что я где-то напортачил. В целом же никакого белого шума не наблюдается. Дальше не было времени продолжать.
(кликабельно)
Оказывается, в архиве есть продолжение моих изысканий. Документ newalg.mcd делает упаковку, а unnewalg.mcd — распаковку с уже усовершенствованным алгоритмом. Как я и говорил, применяем какой-либо нч-алгоритм, гладкую часть не трогаем, а сжимаем только детали. Только для их работы в Mathcad нужна пользовательская dll, в которой находится дискретный алгоритм двумерного вейвлет-Хаар преобразования.
Тут дело даже не в каком-то выигрыше в степени сжатия. Мне хотелось побороть проблему со сжатием деталей и чтобы при восстановлении они не выглядели белым шумом. Я же всё-таки ищу «похожий шум», а не любой попавшийся. Кстати, в втором варианте алгоритма я уже подстраиваюсь под тип распределения «случайного сигнала», т.к. в этом случае искомые совпадения будут больше походи на куски из оригинала.
На картинке ниже при увеличении видны какие-то артефакты. Всё-таки надо было мне писать программу не в Mathcad, так как она значительно усложнилась. Подозреваю, что я где-то напортачил. В целом же никакого белого шума не наблюдается. Дальше не было времени продолжать.
(кликабельно)
Есть у меня подозрение, что нужно смотреть в сторону super-resolution алгоритмов. Есть тут нечто схожее.
An example with nameplates, showing extreme reconstructions
Another blind deconvolution paper, seems great on car plates
Hallucinating faces
An opensource implementation of video-based SR
Classic paper of single-image super-resolution
Multiple cameras (i.e. surveilance)
etc
An example with nameplates, showing extreme reconstructions
Another blind deconvolution paper, seems great on car plates
Hallucinating faces
An opensource implementation of video-based SR
Classic paper of single-image super-resolution
Multiple cameras (i.e. surveilance)
etc
Очень много непонятного.
1. Вы сравниваете bmp (изображение без сжатия) и полученное сжатое представление. Почему не jpg с вашим вариантом? Как определить, что предложенный алгоритм хоть в чем-то лучше того же jpg?
2. На глаз тут ничего не увидишь, если только разница совсем уж не грубая. Надо использовать хотя бы среднеквадратичное отклонение по всему рисунку при одинаковой длинне сжатого файла.
3. Если судить по визуальному результату, но ваш аглоритм не сжимает случайные данные, а ровно наоборот — извабляется от высокочастотного случайного шума и оставляет существенные низкочастотные составляющие — то есть, делает ровно то, что и все остальные алгоритмы сжатия. Так в чем же фишка?
4. Не надо пользоваться зипом, а надо сразу писать в двоичном формате. Кстати, хорошая проверка — если зип этот двоичный формат сожмет существенно, значит, у вас плохой алгоритм сжатия.
1. Вы сравниваете bmp (изображение без сжатия) и полученное сжатое представление. Почему не jpg с вашим вариантом? Как определить, что предложенный алгоритм хоть в чем-то лучше того же jpg?
2. На глаз тут ничего не увидишь, если только разница совсем уж не грубая. Надо использовать хотя бы среднеквадратичное отклонение по всему рисунку при одинаковой длинне сжатого файла.
3. Если судить по визуальному результату, но ваш аглоритм не сжимает случайные данные, а ровно наоборот — извабляется от высокочастотного случайного шума и оставляет существенные низкочастотные составляющие — то есть, делает ровно то, что и все остальные алгоритмы сжатия. Так в чем же фишка?
4. Не надо пользоваться зипом, а надо сразу писать в двоичном формате. Кстати, хорошая проверка — если зип этот двоичный формат сожмет существенно, значит, у вас плохой алгоритм сжатия.
4. Не надо пользоваться зипом, а надо сразу писать в двоичном формате. Кстати, хорошая проверка — если зип этот двоичный формат сожмет существенно, значит, у вас плохой алгоритм сжатия.
По-вашему, JPEG — плохой алгоритм сжатия, раз ему DCT-коэффициенты после квантования требуется кодировать Хаффманом? (ZIP тоже на Хаффмане основан. Deflate = LZ77+Huffman.)
Это неверно, конечно. Очень часто первый этап — преобразование представления (например, из пространственного в частотное, как в JPEG) не приводит к сжатию, а часто — совсем наоборот. И преимущество такого представления в том, что в таком виде данные легче контролировать потери, а также результат получается более сжимаемым. Другой пример, где преобразование само по себе не сжимает, но улучшает сжимаемость — BZIP2 с его преобразованием Барроуза-Уилера.
Я понятия не имею, о чем вы говорите, но как когдатошний математик и теперешний фотограф, могу сказать, что 1) ваше сжатие совершенно не лучше низкрчастотного жпега, и 2) если оно лучше, давайте сравним среднеквадратичное по пикселям, иначе вся статья напоминает фильм о вызывании душ на сеансах магии.
Это вы мне, наверное.
На самом деле существует около десятка разных критериев оценки качества алгоритмов сжатия изображений и относительный вес искажений — это скорее математический костыль, который что-то может показать в каких-то определённых условиях. Он показывает количественную, но не качественную картину. И тем не менее, я у себя в документах приводил значения PSNR (чисто по привычке).
Цитата отсюда (лень было объяснять самому): Применение новых критериев оценки качества изображений после их сжатия с потерями
И ещё по теме оттуда же:
Вот в общем в чём суть. Дело тут даже не в сжатии (это только для привлечения внимания), а в том что именно предполагается сжимать и для чего.
Правильно нужно сравнивать jpeg и jpeg + вч-алгоритм.
Если вы фотограф, то может быть слышали про так называемые bilaterial-фильтры (двух-весовая фильтрация)? Вот по смыслу цель его работы перекликается. Человек «видит» искажения деталей, но слабо обращает внимание на нч-искажения. Стандартные фильтры тоже имеют гладкие ядра и их свёртка с изображением обладает встроенным побочным эффектом — удаляются вч-детали.
Народ подумал, подумал и придумал делить нч и вч-детали. Что отражено в названии. Если фильтруемый участок гладкий, то мы проходим по нему одним фильтром, если есть переход, то другим. Таким образом, можно убрать слабый шум, но оставить контуры.
Вот и я предлагаю: пусть jpeg сжимает то, что у него получается хорошо, а то, что не получается можно попробовать кодировать моим способом. И критерий оценки тут должен быть не количественный, а качественный, т.к. мы будем сравнивать изображение с деталями и без деталей. Тут PSNR вообще никаким боком не пригодиться.
На самом деле существует около десятка разных критериев оценки качества алгоритмов сжатия изображений и относительный вес искажений — это скорее математический костыль, который что-то может показать в каких-то определённых условиях. Он показывает количественную, но не качественную картину. И тем не менее, я у себя в документах приводил значения PSNR (чисто по привычке).
Цитата отсюда (лень было объяснять самому): Применение новых критериев оценки качества изображений после их сжатия с потерями
Следует отметить, что значение СКО может незначительно изменяться при существенном ухудшении субъективно воспринимаемого качества сжатого изображения. Поэтому СКО, так же как и пиковое отношение сигнал/шум (PSNR), не может быть взято за основу при построении оптимальных с визуальной точки зрения систем преобразования изображений с целью их сжатия.
Необходимо отметить, что значение PSNR не может в полной мере отражать воздействие на изображение различных видов помех (см. рис. 1), т.е. при наличии в изображении разных видов шумов его значение может оставаться постоянным, а качество изображения существенно изменяться.
И ещё по теме оттуда же:
Проведённые исследования показали, что система человеческого восприятия (HVS) менее чувствительна к искажениям на низких частотах, чем к искажениям в высокочастотной области
Вот в общем в чём суть. Дело тут даже не в сжатии (это только для привлечения внимания), а в том что именно предполагается сжимать и для чего.
Правильно нужно сравнивать jpeg и jpeg + вч-алгоритм.
Если вы фотограф, то может быть слышали про так называемые bilaterial-фильтры (двух-весовая фильтрация)? Вот по смыслу цель его работы перекликается. Человек «видит» искажения деталей, но слабо обращает внимание на нч-искажения. Стандартные фильтры тоже имеют гладкие ядра и их свёртка с изображением обладает встроенным побочным эффектом — удаляются вч-детали.
Народ подумал, подумал и придумал делить нч и вч-детали. Что отражено в названии. Если фильтруемый участок гладкий, то мы проходим по нему одним фильтром, если есть переход, то другим. Таким образом, можно убрать слабый шум, но оставить контуры.
Вот и я предлагаю: пусть jpeg сжимает то, что у него получается хорошо, а то, что не получается можно попробовать кодировать моим способом. И критерий оценки тут должен быть не количественный, а качественный, т.к. мы будем сравнивать изображение с деталями и без деталей. Тут PSNR вообще никаким боком не пригодиться.
1. Вы сравниваете bmp (изображение без сжатия) и полученное сжатое представление. Почему не jpg с вашим вариантом? Как определить, что предложенный алгоритм хоть в чем-то лучше того же jpg?
Я предложил алгоритм сжатия. Это означает, что сначала нужно убедиться, что он именно что-то сжимает, пусть и с потерями. Этот факт определяется количественной оценкой размера контейнера до и после операции. Первоначальный контейнер оцифрованного двумерного сигнала был bmp, я его перевёл в другой контейнер и показал, что он занимает меньше места.
После этого этапа уже можно сравнивать с jpeg'ом, но тут нужно понять разницу целей. Большинство обычных алгоритмов предназначены для сжатия гладких изображений. Весь их смысл в том, что все они имеют в своём ядре гладкие базисные функции, с помощью которых информация об изображении переводится в другое пространство. В этом другом пространстве количественно гладкое изображение содержит меньше информации, т.е. информационная ёмкость меньше.
В этом и заключается суть процесса сжатия. Контейнер jpeg'а хранит коэффициенты, которые численно являются проекциями на базис в новом пространстве. По-простому это можно понять так. К примеру, у нас есть одномерный сигнал — синус, длинной в один период. Чтобы хранить информацию о нём во временной области, нам нужны все отсчёты синуса. Это очень много. Если же мы сделаем дискретное преобразование Фурье, то в частотной области нам нужно всего одно комплексное число. Вот эти комплексные числа jpeg и хранит.
Проблема в том, что гладкие ядра преобразований не дают нужного эффекта с широкополосными сигналами. Широкий спектр дают границы, мелкие детали, т.е. импульсного вида сигналы. Их информационная ёмкость в любом пространстве, куда не переводи будет одинакова, насколько я полагаю. Т.е. шум будет шумом везде.
Раз шум — везде шум, то я предлагаю использовать случайные сигналы, чтобы кодировать эти же самые случайные сигналы. Это может поначалу показаться странным, но на картинке выше я привёл пример нахождения ВКФ двух случайных сигналов. Смысл примера в том, что небольшой кусок случайного сигнала можно всегда найти в другом похожем случайном сигнале. Нам не нужно точное совпадение. Это же показано и в документе.
Так вот я к чему. Сравнивать нч-алгоритм сжатия с вч-алгоритмом сжатия не совсем корректно. Они должны друг друга дополнять. Дело в том, что мой алгоритм на самом деле сжимает вот такое изображение (bmp файл сначала превращается в него):
Что на это скажет jpeg? А для вч-алгоритма, чем больше изображение похоже на шум, тем лучше.
2. На глаз тут ничего не увидишь, если только разница совсем уж не грубая. Надо использовать хотя бы среднеквадратичное отклонение по всему рисунку при одинаковой длинне сжатого файла.
В Mathcad документе есть стандартные количественные оценки для изображений (даже формулы приведены). В первом pdf документе также они есть. Но смысла в этом не много для первого варианта алгоритма.
3. Если судить по визуальному результату, но ваш аглоритм не сжимает случайные данные, а ровно наоборот — извабляется от высокочастотного случайного шума и оставляет существенные низкочастотные составляющие — то есть, делает ровно то, что и все остальные алгоритмы сжатия. Так в чем же фишка?
Самая первая картинка показывает просто артефакты, которые неизбежны из-за того, что шума в этом изображении мало. Это же очень гладкое изображение. Я ведь сначала перемешиваю все его точки, чтобы получить хоть какое-то подобие шума, а потом уже применяю алгоритм. Ещё раз повторяю, этот пример просто демонстрирует сам факт того, что такой алгоритм может пожать изображение при помощи случайных сигналов и восстановить его. Вот в этом и фишка. Изображение восстанавливается из псевдослучайных последовательностей. Не из какого-то там базиса, а из упорядоченного хаоса.
В хаосе на самом деле находятся все изображения. Из него можно достать любое. Я лишь предложил метод, который позволяет затрачивать для этого меньше байт, чем занимает само оцифрованное изображение.
4. Не надо пользоваться зипом, а надо сразу писать в двоичном формате. Кстати, хорошая проверка — если зип этот двоичный формат сожмет существенно, значит, у вас плохой алгоритм сжатия.
Это неверно. Это лишь означает, что я использую избыточное кодирование коэффициентов. Только и всего.
> Это означает, что сначала нужно убедиться, что он именно что-то сжимает, пусть и с потерями.
Есть сто тысяч и один способ сжать с потерями. И что? Это сто тысяч первый? В чем смысл? Где обещаянная высокочастотная составляющая?
Давайте перестанем играть в песочнице. Если предлагаете новый способ сжатия, то хотя бы по-взрослому докажите/покажите, что он хоть в чем-то лучше существующих, а не «я научился использовать библиотеку БПФ и это очень круто!».
Есть сто тысяч и один способ сжать с потерями. И что? Это сто тысяч первый? В чем смысл? Где обещаянная высокочастотная составляющая?
Давайте перестанем играть в песочнице. Если предлагаете новый способ сжатия, то хотя бы по-взрослому докажите/покажите, что он хоть в чем-то лучше существующих, а не «я научился использовать библиотеку БПФ и это очень круто!».
Вы не читаете то, что вам пишут и поясняют.
Во-первых, не каждый инженер спокойно воспримет фразу «сжатие случайных сигналов». Они по определению несжимаемы. Поэтому вначале я должен пояснить что именно я понимаю под сжатием случайных сигналов, т.к. у практичных людей, которые работают архиваторами или jpeg'ами может быть неадекватная реакция.
Картинка ниже — это предельный пример. Изображение 256 х 256 серое и в BMP формате, как я уже писал, занимает 66614 байт. Если попытаться его «пожать» jpeg'ом, то мы получим 62646 байт (paint). Мой алгоритм спокойно превратит это в 18 Кб. И как сравнивать?
JPEG такое сжать не может, а если заставить, то получаются смазанные результаты. Это крайний случай, но он явно показывает один из недостатков этого и прочих похожих алгоритмов. Они либо не могут сжать, либо просто удаляют детали, которые на самом деле важны для восприятия человеком.
Есть другие примеры, где показывают PNG и JPEG, который сжимает черный текст на белом фоне. Буквы «поплывут». Поэтому в web дизайне использовать jpeg с такими артефактами никто не будет.
Так вот и возникает вопрос у создателей подобных алгоритмов: «А как оставить достоинства jpeg'а, но убрать его недостатки?»
Поэтому, во-вторых, когда мы удостоверились, что что-то работает, мы думаем о том, а как это можно применить, используя природу используемого преобразования. А природа его в том, что случайные сигналы сохраняют вч-информацию.
Я не утверждаю, что метод этот даст гарантированный результат, а лишь показываю, что потенциально это возможно. Нужны дополнительные исследования.
Во-первых, не каждый инженер спокойно воспримет фразу «сжатие случайных сигналов». Они по определению несжимаемы. Поэтому вначале я должен пояснить что именно я понимаю под сжатием случайных сигналов, т.к. у практичных людей, которые работают архиваторами или jpeg'ами может быть неадекватная реакция.
Картинка ниже — это предельный пример. Изображение 256 х 256 серое и в BMP формате, как я уже писал, занимает 66614 байт. Если попытаться его «пожать» jpeg'ом, то мы получим 62646 байт (paint). Мой алгоритм спокойно превратит это в 18 Кб. И как сравнивать?
JPEG такое сжать не может, а если заставить, то получаются смазанные результаты. Это крайний случай, но он явно показывает один из недостатков этого и прочих похожих алгоритмов. Они либо не могут сжать, либо просто удаляют детали, которые на самом деле важны для восприятия человеком.
Есть другие примеры, где показывают PNG и JPEG, который сжимает черный текст на белом фоне. Буквы «поплывут». Поэтому в web дизайне использовать jpeg с такими артефактами никто не будет.
Так вот и возникает вопрос у создателей подобных алгоритмов: «А как оставить достоинства jpeg'а, но убрать его недостатки?»
Поэтому, во-вторых, когда мы удостоверились, что что-то работает, мы думаем о том, а как это можно применить, используя природу используемого преобразования. А природа его в том, что случайные сигналы сохраняют вч-информацию.
Я не утверждаю, что метод этот даст гарантированный результат, а лишь показываю, что потенциально это возможно. Нужны дополнительные исследования.
«Сравнивать нч-алгоритм сжатия с вч-алгоритмом сжатия не совсем корректно. Они должны друг друга дополнять.» — я не сравниваю НЧ и ВЧ или ЗЧ или ХЧ. Я сравниваю среднеквадратичное попиксельное. Итог? При одном и том же сжатом размере? JPG и ваше??
(и это все с тем же низкочастотным)
(и это все с тем же низкочастотным)
Хотя, если представить, что вы на самом деле утверждаете обратное от того, что хотели сказать (ну есть такой тип людей), тогда алгоритм начинает быть уже интересным. :)
Судя по вашему следу здесь в топике, вы вообще о сжатии и обработке изображений знаете только понаслышке. Ещё один купил камеру и теперь он фотограф, блин.
Чтобы здесь в обсуждении участвовать, разберитесь в первую очередь с понятием «класс изображения». JPEG предназначен для определённого класса изображений, называемых «фотореалистичными». Фотореалистичные — значит, гладкие, с плавными переходами цвета и не особо резкими границами. Другие он сжимает плохо. Например, он не подходит для сжатия схем, графиков, CG — он сжимает их хуже LZ без потерь (как PNG). PSNR получается меньше, а уж визуальные искажения которые он привносит и вовсе во многих случаях недопустимы (PSNR здесь вообще неадекватная метрика, поскольку недооценивает искажения, вносимые алгоритмом, по сравнению с тем, как эти искажения воспринимает человек).
А в статье описан алгоритм, предназначенный вообще-то для другого класса изображений: с большим уровнем высокочастотного шума. Поэтому, некорректно его сравнивать с JPEG, как и PNG, например: каждый из алгоритмов предназначен для своего класса и обычно выигрывает в своём классе, хотя может проиграть в чужом.
Во вторых, разберитесь с тем, как разрабатываются, тестируются и сравниваются алгоритмы сжатия. Сжатие происходит не JPEGа, а оригинальных пиксельных данных (ну или что там пришло с сенсора — может быть вообще не PCM, а в другом домене). Поэтому сравнивать надо с объёмом этих исходных данных, а не с JPEG (тем более, что он для другого класса).
В третьих, современные компрессоры изображений — сложные механизмы, в них довольно используется много странных (на первый взгляд) техник. В звуке уже используются алгоритмы, которые ВЧ и НЧ компоненты сжимают по-разному: например, FLAC сжимает НЧ часть аппроксимацией многочленами, а остаток, который представляет из себя практически белый шум, представляет кодами Райса (которые являются особой разновидностью кодов Хаффмана, специально для белого шума). В статье описана «вторая часть» сходного подхода для сжатия изображений, и речь идёт о том, что это «вторая часть», а первой может быть тот же JPEG, и комбинированный алгоритм для некоторых изображений может быть эффективнее чем каждый из отдельных алгоритмов в отдельности.
Чтобы здесь в обсуждении участвовать, разберитесь в первую очередь с понятием «класс изображения». JPEG предназначен для определённого класса изображений, называемых «фотореалистичными». Фотореалистичные — значит, гладкие, с плавными переходами цвета и не особо резкими границами. Другие он сжимает плохо. Например, он не подходит для сжатия схем, графиков, CG — он сжимает их хуже LZ без потерь (как PNG). PSNR получается меньше, а уж визуальные искажения которые он привносит и вовсе во многих случаях недопустимы (PSNR здесь вообще неадекватная метрика, поскольку недооценивает искажения, вносимые алгоритмом, по сравнению с тем, как эти искажения воспринимает человек).
А в статье описан алгоритм, предназначенный вообще-то для другого класса изображений: с большим уровнем высокочастотного шума. Поэтому, некорректно его сравнивать с JPEG, как и PNG, например: каждый из алгоритмов предназначен для своего класса и обычно выигрывает в своём классе, хотя может проиграть в чужом.
Во вторых, разберитесь с тем, как разрабатываются, тестируются и сравниваются алгоритмы сжатия. Сжатие происходит не JPEGа, а оригинальных пиксельных данных (ну или что там пришло с сенсора — может быть вообще не PCM, а в другом домене). Поэтому сравнивать надо с объёмом этих исходных данных, а не с JPEG (тем более, что он для другого класса).
В третьих, современные компрессоры изображений — сложные механизмы, в них довольно используется много странных (на первый взгляд) техник. В звуке уже используются алгоритмы, которые ВЧ и НЧ компоненты сжимают по-разному: например, FLAC сжимает НЧ часть аппроксимацией многочленами, а остаток, который представляет из себя практически белый шум, представляет кодами Райса (которые являются особой разновидностью кодов Хаффмана, специально для белого шума). В статье описана «вторая часть» сходного подхода для сжатия изображений, и речь идёт о том, что это «вторая часть», а первой может быть тот же JPEG, и комбинированный алгоритм для некоторых изображений может быть эффективнее чем каждый из отдельных алгоритмов в отдельности.
Ага, знаю поначитке. Поэтому перейдем к делу. Отбрасывая слова о разных классах изображений, где хоть одно сравнение по среднеквадратичной погрешности хоть с одним известным алгоритмом при той же степени сжатия? И уж обязательно с jpeg'ом, который должен просто пасть к ногам предлагаемого алгоритма, поскольку «вообще не для того класса». Все остальные общие слова — одни лишь слова ни о чем.
Кстати, так и не пояснили, что же представляют собой два изображения попугая в самом начале статьи?
Кстати, так и не пояснили, что же представляют собой два изображения попугая в самом начале статьи?
Обычно, когда показывают изображения такого рода, то имеется в виду оригинал и восстановленное изображение. Не трудно догадаться где что.
Вы хотите сравнить тёплое с мягким и этого не понимаете. Хочу ещё раз обратить ваше внимание, если вы понять самостоятельно не можете. Классы изображений — это то, что помогает отличать один набор изображений от другого набора. Алгоритмы тестируют на классах изображений, чтобы делать обобщения. К примеру, класс гладких изображений. Большинство фотографий, с точки зрения математики, могут хорошо аппроксимироваться гладкими функциями. Поэтому их можно пожать.
Мой алгоритм с гладкими изображениями в оригинале вообще работать не будет. Именно потому, что оно содержит медленно меняющиеся компоненты. Уже только по этому признаку сравнивать с jpeg'ом не имеет смысла, т.к. это всё равно, что сравнивать тёплое с мягким.
Показываю вам в очередной раз то «изображение», с которым работает алгоритм (я пишу новую статью и это скрин из расчёта для неё):
Если вы хотите сделать сравнение с jpeg-ом, то нужно поставить его в те же условия, т.е. подать на вход изображение Menc (левое нижнее). Предсказать результат работы jpeg'а не трудно.
Мой алгоритм требует для работы только изображение с вч-шумом, поэтому мне, кстати, не важно какое изображение на входе. Я всё равно его перемешиваю, чтобы с ним можно было работать. Для jpeg'а изображение должно быть гладким.
Что здесь непонятно?
Вы хотите сравнить тёплое с мягким и этого не понимаете. Хочу ещё раз обратить ваше внимание, если вы понять самостоятельно не можете. Классы изображений — это то, что помогает отличать один набор изображений от другого набора. Алгоритмы тестируют на классах изображений, чтобы делать обобщения. К примеру, класс гладких изображений. Большинство фотографий, с точки зрения математики, могут хорошо аппроксимироваться гладкими функциями. Поэтому их можно пожать.
Мой алгоритм с гладкими изображениями в оригинале вообще работать не будет. Именно потому, что оно содержит медленно меняющиеся компоненты. Уже только по этому признаку сравнивать с jpeg'ом не имеет смысла, т.к. это всё равно, что сравнивать тёплое с мягким.
Показываю вам в очередной раз то «изображение», с которым работает алгоритм (я пишу новую статью и это скрин из расчёта для неё):
Если вы хотите сделать сравнение с jpeg-ом, то нужно поставить его в те же условия, т.е. подать на вход изображение Menc (левое нижнее). Предсказать результат работы jpeg'а не трудно.
Мой алгоритм требует для работы только изображение с вч-шумом, поэтому мне, кстати, не важно какое изображение на входе. Я всё равно его перемешиваю, чтобы с ним можно было работать. Для jpeg'а изображение должно быть гладким.
Что здесь непонятно?
Я так понимаю автор комментария всё же имел ввиду сравнение PSNR-метрики для восстановленного изображения данным методом в сравнении с каким-либо другим популярным алгоритмом сжатия для разных входных данных. Если алгоритм покажет хоть какие-то практические результаты, у него есть шанс на жизнь пусть не в вебе, но в каких-то специализированных приложениях или играх, где размер имеет значение, но чёткость текстур тоже играет немаловажную роль.
Скажем так, по своему опыту знаю, что нередко стандартные алгоритмы сжатия не подходят и приходится изобретать. Например, jpeg не поддерживает альфа-канал и бывает выгоднее сохранить два жпега (цвет+альфа), чем жать всю картинку в PNG. Если алгоритм покажет хороший результат, он может стать 1) дополнением для стандартного жпега чтобы кодировать ВЧ часть 2) может быть значительно доработан (дельта кодирование, бинарный формат выхлопа, сжатие LZW). Более того, для приемлемого результата достаточно кодировать только яркость.
Ещё бы алгоритм в более удобоваримой форме на GitHub выложить… На Питоне например. Матлаб всё же специфичная прога, не язык программирования.
Скажем так, по своему опыту знаю, что нередко стандартные алгоритмы сжатия не подходят и приходится изобретать. Например, jpeg не поддерживает альфа-канал и бывает выгоднее сохранить два жпега (цвет+альфа), чем жать всю картинку в PNG. Если алгоритм покажет хороший результат, он может стать 1) дополнением для стандартного жпега чтобы кодировать ВЧ часть 2) может быть значительно доработан (дельта кодирование, бинарный формат выхлопа, сжатие LZW). Более того, для приемлемого результата достаточно кодировать только яркость.
Ещё бы алгоритм в более удобоваримой форме на GitHub выложить… На Питоне например. Матлаб всё же специфичная прога, не язык программирования.
Это всё будет, но позже, так как мне самому аналог обычного jpeg'а писать придётся и делать деление на этапы, как с кодированием, так и декодированием. Нет времени всё это быстро закодить.
Часть алгоритмов уже есть на github, но в качестве дополнений к Mathcad (на c#). Я, к примеру, применил сейчас новый генератор ПСП. Очень простой и удобный. У меня сейчас будет ещё одна картинка, поясняющая смысл применения случайного сигнала. Я приведу пример изображения, каждый отсчет яркости которого квантуется 4 интервалами, а не 256. Для этого нужно 2 бита на пиксел, так вот я хочу показать, что если использовать те же 2 бита на пиксел, то можно получить изображение чуть лучшего качества, чем при обычном квантовании.
PSNR будет только после того, как я восстановлю вч-детали у обычного алгоритма, а иначе, как я писал выше, придется jpeg'у вч-шум сжимать. Он его не сожмет, если только не заставить. Мне страшно представить что будет на его выходе. Никакого смысла в PSNR в этом случае не будет. Эту протокольную меру сейчас применять смысла нет. Для ВЧ картинки выше качество тоже особо не оценишь.
Я хочу получить эффект от сжатия деталей. Если, к примеру, использовать вейвлет сжатие, показанное выше, то там видно, что на каждой итерации получается деталей в три раза больше по объему, чем гладких коэффициентов. Основная энергия сигнала находится в гладких функциях, поэтому они важнее считаются, но детали содержат другого характера важную информацию. Обычно их просто сохраняют как есть, либо обрезая слишком высокочастотные.
Часть алгоритмов уже есть на github, но в качестве дополнений к Mathcad (на c#). Я, к примеру, применил сейчас новый генератор ПСП. Очень простой и удобный. У меня сейчас будет ещё одна картинка, поясняющая смысл применения случайного сигнала. Я приведу пример изображения, каждый отсчет яркости которого квантуется 4 интервалами, а не 256. Для этого нужно 2 бита на пиксел, так вот я хочу показать, что если использовать те же 2 бита на пиксел, то можно получить изображение чуть лучшего качества, чем при обычном квантовании.
PSNR будет только после того, как я восстановлю вч-детали у обычного алгоритма, а иначе, как я писал выше, придется jpeg'у вч-шум сжимать. Он его не сожмет, если только не заставить. Мне страшно представить что будет на его выходе. Никакого смысла в PSNR в этом случае не будет. Эту протокольную меру сейчас применять смысла нет. Для ВЧ картинки выше качество тоже особо не оценишь.
Я хочу получить эффект от сжатия деталей. Если, к примеру, использовать вейвлет сжатие, показанное выше, то там видно, что на каждой итерации получается деталей в три раза больше по объему, чем гладких коэффициентов. Основная энергия сигнала находится в гладких функциях, поэтому они важнее считаются, но детали содержат другого характера важную информацию. Обычно их просто сохраняют как есть, либо обрезая слишком высокочастотные.
> мне самому аналог обычного jpeg'а писать придётся и делать деление на этапы
Я предлагаю сделать проще. НЧ составляющую закодировать алгоритмом жпега, положим получится 6 килобайт картинка жпег. Далее сделать grain extract (А-В+0.5) для оригинала и пожатого жпега, получим вот такую картинку:
Это была ваша птица из примера, которую я сначала сжал в жпег 6 кб, а затем применил grain extract с оригиналом. Это и будет та самая ВЧ составляющая, то есть «детали», которые хорошо умеет сжимать ваш алгоритм. Видно, что шум тут очень слабый, кодировать его будет проще. Чтобы было заметнее, я увеличу контраст этого шума:
Далее после кодирования данной ВЧ составляющей получаем вторую картинку, положим, она займёт после сжатия вашим методом 10 килобайт. Восстанавливаем оригинал по обратной формуле А+В-0.5, считаем PSNR, чтобы оценить качество сжатия. Итого — ужали исходное изображение в 2 прохода до 16 килобайт. Далее подгоняем жпег до 16 килобайт и также считаем PSNR, после чего сравниваем, что лучше. Потом для пущей эффективности алгоритм можно скрестить с вейвлетами и поиграться с балансом ВЧ-НЧ, я думаю это тоже как-то влиять будет.
Я предлагаю сделать проще. НЧ составляющую закодировать алгоритмом жпега, положим получится 6 килобайт картинка жпег. Далее сделать grain extract (А-В+0.5) для оригинала и пожатого жпега, получим вот такую картинку:
Это была ваша птица из примера, которую я сначала сжал в жпег 6 кб, а затем применил grain extract с оригиналом. Это и будет та самая ВЧ составляющая, то есть «детали», которые хорошо умеет сжимать ваш алгоритм. Видно, что шум тут очень слабый, кодировать его будет проще. Чтобы было заметнее, я увеличу контраст этого шума:
Далее после кодирования данной ВЧ составляющей получаем вторую картинку, положим, она займёт после сжатия вашим методом 10 килобайт. Восстанавливаем оригинал по обратной формуле А+В-0.5, считаем PSNR, чтобы оценить качество сжатия. Итого — ужали исходное изображение в 2 прохода до 16 килобайт. Далее подгоняем жпег до 16 килобайт и также считаем PSNR, после чего сравниваем, что лучше. Потом для пущей эффективности алгоритм можно скрестить с вейвлетами и поиграться с балансом ВЧ-НЧ, я думаю это тоже как-то влиять будет.
Ах вот оно что. Только сейчас дошло. Однако, ваша статья называется «механизм сжатия», а не «механизм восстановления зашумленного сигнала». Это же совсем разные алгоритмы и задачи. Тщательнее в формулировках.
Собственно, Америку вы не открыли. В звуковых кодеках примерно то же самое применяется давным-давно, как правило, именно для высокочастотных диапазонов, и называется «векторное квантование». В том же Speex'е эта идея используется в комбинации с линейным предсказанием. Правда, там не говорится явно о псевдослучайной последовательности, но суть та же — имеем N (где N зависит от целевого битрейта) «кусков» звука, кодировщик пишет номер наиболее похожего.
Спасибо, мне было интересно узнать к какой области математики это может относиться. Действительно фонемные вокодеры тоже ведь из кусков речь восстанавливают. Я всё искал методику, которая бы позволила быстрее искать кусок сигнала в другом случайном сигнале. В качестве библиотеки я использовал обычный конгруэнтный генератор ПСП.
Странно, что куча математиков, которым я доклад делал, ничего мне про это не сказали.
Странно, что куча математиков, которым я доклад делал, ничего мне про это не сказали.
Я всё искал методику, которая бы позволила быстрее искать кусок сигнала в другом случайном сигнале
В вашем случае, когда начало куска может быть где угодно в случайной последовательности, трюк с преобразованием Фурье заведомо дает точный результат за время порядка O(M log M), где M — просматриваемая длина случайной последовательности (т.е. индекс, дальше которого мы в нее не заглядываем). Ускорение возможно за счет следующих соображений.
1. Отказ от возможности начинать кусок с произвольного места в случайной последовательности. Тупо режем ее на последовательные (без перекрытия) кусочки фиксированной длины, как для классического векторного квантования. Тогда можно просто вычислить скалярное произведение куска входной последовательности с каждым из «эталонных», и это займет всего O(M), где M — сумма длин этих самых эталонных кусков. Сэкономили log(M) вычислений и log(M/N) бит на кусок в выходном потоке, где M/N — длина куска, ценой некоторой потери качества.
2. Отказ от требования найти наиболее похожий кусок в пользу «достаточно похожих». На этом пути классикой являются k-d деревья. Но если хочется набросать что-то на скорую руку, что работает немного хуже (но все равно в разы быстрее, чем честный перебор из п. 1), то вот еще простой алгоритм.
Как уже сказано, есть N эталонных кусков сигнала, много входных кусков и какая-то функция похожести одного куска на другой. Надо найти среди эталонных кусков какой-либо похожий на каждый входной (чем более похожий — тем лучше).
Заранее честным образом вычисляем функцию похожести для всех пар эталонных кусков (A, B). Для каждого эталонного куска A пишем в таблицу 8-16 (подобрать по результатам) номеров наиболее похожих других эталонных кусков. Полученную таблицу сохраняем.
Затем, когда очередной входной кусок будет известен, крутим такой простенький цикл (начиная с первого эталонного куска как с кандидата на роль достаточно похожего), пока он дает переходы на более похожий эталонный кусок. Зная, что эталонный кусок с номером A уже рассмотрен на предыдущем шаге, надо рассмотреть все 8-16 кусков, самых похожих на A согласно таблице, и выбрать среди них наиболее похожий на входной. Получается постепенное улучшение кандидата на роль достаточно похожего эталонного куска, но нахождение действительно наиболее похожего не гарантируется — что-то вроде локального максимума.
Спасибо. Идеи интересные. Надо будет как-нибудь заняться и попробовать. Может чего и выйдет в результате.
Затем, когда очередной входной кусок будет известен, крутим такой простенький цикл (начиная с первого эталонного куска как с кандидата на роль достаточно похожего), пока он дает переходы на более похожий эталонный кусок. Зная, что эталонный кусок с номером A уже рассмотрен на предыдущем шаге, надо рассмотреть все 8-16 кусков, самых похожих на A согласно таблице, и выбрать среди них наиболее похожий на входной. Получается постепенное улучшение кандидата на роль достаточно похожего эталонного куска, но нахождение действительно наиболее похожего не гарантируется — что-то вроде локального максимума.
напоминает алгоритм поиска подходящего доменного блока при фрактальном сжатии
Небольшое пожелание.
Раз уж вы все равно собрались писать вторую статью, неплохо бы в ней привести обоснование, почему перемешивание отсчетов входного сигнала помогает. Т.е. сделать без него и ткнуть носом, что получилось хуже. А то будет контраргумент, что (с малой вероятностью) в случайной последовательности может встретиться какой угодно кусок, и нет каких-либо оснований считать, что похожие на фрагмент перемешанной картинки куски будут встречаться чаще, чем похожие на фрагмент неперемешанной.
Раз уж вы все равно собрались писать вторую статью, неплохо бы в ней привести обоснование, почему перемешивание отсчетов входного сигнала помогает. Т.е. сделать без него и ткнуть носом, что получилось хуже. А то будет контраргумент, что (с малой вероятностью) в случайной последовательности может встретиться какой угодно кусок, и нет каких-либо оснований считать, что похожие на фрагмент перемешанной картинки куски будут встречаться чаще, чем похожие на фрагмент неперемешанной.
Я для этого специальную гистограмму приведу. Беру ПСП, предполагаю, что буду искать интервалы длинной 8. Далее я могу измерить как бы «мощность» множества случайных комбинаций. Можно ведь двигаться и от обратного — разбить на интервалы значения каждого из 8 отсчётов. Далее перебрать все возможные комбинации этих интервалов и отсчетов. Я начал об этом писать выше, когда делил на 4 интервала область значений каждого отсчёта.
Я хотел ввести классификацию интервалов 16-битным ключом. Долго сейчас объяснять, в общем каждый отсчёт кодируется числом от 0 до 3 ( 0b00 — 0b11 — по два бита). Отсчётов 8, поэтому код 16 битный. Это число можно использовать как признак интервала, в котором находится какая-то конкретная реализация из картинки или из ПСП. Далее берём ПСП длиной 2^16 (потом объясню зачем). Далее делаем такой финт. Создаём таблицу из 2^16 строк, каждая строка сопоставляется с кодом интервала. Перебираем все смещения в ПСП по очереди и находим в какой интервал попадает конкретная реализация. В столбце таблицы прибавляем единицу, если смещение в ПСП попало в интервал. Так вот, если оставить такую таблицу, то выглядит она так.
Это означает, что мы имеем минимум 2 «похожих» реализации в ПСП для большинства возможных интервалов. Ниже показан один из интервалов и его код, а также количество смещений в ПСП, которые соотв-ют этому коду (в данном случае 1).
Код функции, которая формирует таблицу:
Я хотел ввести классификацию интервалов 16-битным ключом. Долго сейчас объяснять, в общем каждый отсчёт кодируется числом от 0 до 3 ( 0b00 — 0b11 — по два бита). Отсчётов 8, поэтому код 16 битный. Это число можно использовать как признак интервала, в котором находится какая-то конкретная реализация из картинки или из ПСП. Далее берём ПСП длиной 2^16 (потом объясню зачем). Далее делаем такой финт. Создаём таблицу из 2^16 строк, каждая строка сопоставляется с кодом интервала. Перебираем все смещения в ПСП по очереди и находим в какой интервал попадает конкретная реализация. В столбце таблицы прибавляем единицу, если смещение в ПСП попало в интервал. Так вот, если оставить такую таблицу, то выглядит она так.
Это означает, что мы имеем минимум 2 «похожих» реализации в ПСП для большинства возможных интервалов. Ниже показан один из интервалов и его код, а также количество смещений в ПСП, которые соотв-ют этому коду (в данном случае 1).
Код функции, которая формирует таблицу:
cstable()
uint x = 1, y, z, w;
// A faster Marsaglia's Xorshift pseudo-random generator in unsafe C#
// http://roman.st/Article/Faster-Marsaglia-Xorshift-pseudo-random-generator-in-unsafe-C
byte NextByte() {
uint t = x ^ ( x << 11 );
x = y; y = z; z = w;
w = w ^ ( w >> 19 ) ^ ( t ^ ( t >> 8 ) );
return ( byte ) ( w & 0xFF );
}
public bool NumericEvaluation( object[] args, out object result, ref Context context ) {
x = 1;
y = 0;
z = 0;
w = 0;
var nums = new byte[ 256 * 256 + 8 ];
int k;
for ( k = 0; k < 256 * 256 + 8; k++ ) nums[k] = NextByte();
var list = new List<List<int>>();
for ( k = 0; k < 256 * 256; k++ ) {
list.Add( new List<int>() );
}
for ( k = 0; k < 256 * 256; k++ ) {
var classid = nums[k + 0] >> 6;
classid += ( nums[k + 1] >> 6 ) << 2;
classid += ( nums[k + 2] >> 6 ) << 4;
classid += ( nums[k + 3] >> 6 ) << 6;
classid += ( nums[k + 4] >> 6 ) << 8;
classid += ( nums[k + 5] >> 6 ) << 10;
classid += ( nums[k + 6] >> 6 ) << 12;
classid += ( nums[k + 7] >> 6 ) << 14;
list[ classid ].Add( k );
}
var res = new TComplex[ 256 * 256, 1 ];
for ( k = 0; k < 256 * 256; k++ ) {
res[ k, 0 ] = new TComplex( list[k].Count, 0 );
}
result = res;
return true;
}
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Об одном алгоритме сжатия случайных сигналов (с потерями)