![](http://www.nedopc.org/nedopc/image/nedobanner3.gif) |
nedoPC.orgCommunity for electronics hobbyists, established in 2002 |
![](http://www.nedopc.org/nedopc/image/nedobanner4.gif) |
Last visit was: 31 Aug 2024 16:59
|
It is currently 31 Aug 2024 16:59
|
Создаём подобие JPEG для ретрокомпов (Walsh+Huffman)
Author |
Message |
Shaos
Admin
Joined: 08 Jan 2003 23:22 Posts: 23199 Location: Silicon Valley
|
Вот попробовал отбрасывать "слабые" отсчёты без квантования, пользуясь старым функционалом "фильтрование по уровню" Отбрасываем -1 и +1 (процент ненулевых отсчётов упал до 58%): Далее ещё и -2 и +2 убираем (процент ненулевых стал 42%): Ну чисто для примера -3 и +3 (31% ненулевых остался - тут пожалуй уже надо квантование включать, а не просто отбрасывать):
You do not have the required permissions to view the files attached to this post.
|
24 Nov 2023 00:16 |
|
![](./styles/getaway/theme/images/spacer.gif) |
Shaos
Admin
Joined: 08 Jan 2003 23:22 Posts: 23199 Location: Silicon Valley
|
Вот более полная таблица коэффициентов сжатия K, фактора качества Q и ошибки ERR в зависимости от параметров квантования картинки FEMALER.BWS: В каждой колонке звёздочка означает точку с которой (и ниже) кодирование идёт без квантования (т.е. шаг квантования равен 1.0) - при этом качество устанавливается в 99 и отсчёты кодируются как есть без искажений (если не считать отбрасывание дробной части из-за которой ошибка ERR обычно не бывает меньше 2%), а всё что выше звёздочки будет с искажениями (даже если Q=99). Наверное надо брать по верхней планке - скажем если пользователь заказал Q=60, то в каждой колонке ищем самую верхнюю строчку, где получающееся качество <=60 (в данном примере Q=69) и далее убираем столько -1 и +1 отсчётов, сколько потребуется, чтобы уменьшить процент ненулевых отчётов до нужного числа (60%) и далее считаем коэффициент сжатия для разных вариаций обходов матрицы и способов сжатия - выбираем тот вариант, что меньше (а если размеры получились одинаковыми для разных вариантов, то выбираем вариант с меньшей ошибкой). По процентам наверное от 99 до 90 делаем без квантования (на уровне звёздочки в каждой колонке), от 89 до следующей перед 99 величине - в данном случае 69 - берём Q=99 по верхней планке, далее по верхней планке Q=69 и т.д. Убирать -1 и +1 чтобы подогнать итоговое качество к заказанному Q по-видимому надо с конца в соответствии с выбранной стратегией обхода матрицы, чтобы выиграть на отбрасывании хвостовых нулей (и если все отсчёты -1 и +1 исчерпались, то надо убирать -2 и +2 и т.д.).
|
27 Nov 2023 20:36 |
|
![](./styles/getaway/theme/images/spacer.gif) |
Shaos
Admin
Joined: 08 Jan 2003 23:22 Posts: 23199 Location: Silicon Valley
|
Или всё-таки по нижней планке? Чтобы ошибка была поменьше, правда и сжатие в этом случае будет похуже... P.S. Вот пример квантования для 6 битов на отсчёт начиная со значения 145 (нижняя планка для Q=49 с усреднённой ошибкой 4% и коэффициентом сжатия K=2.57): и начиная со значения 125 (верхняя планка для Q=69 с усреднённой ошибкой 5% и коэффициентом сжатия K=2.15): Как можно видеть в первом случае самым маленькими по амплитуде ненулевыми отсчётами в восстановленной последовательности отсчётов (средний столбик) являются -5 и +5, а во втором -4 и +4 - т.е. когда будем подгонять под требуемое качество нужно будет отбрасывать именно их (т.к. -1 +1 -2 +2 и т.д. уже убиты более грубым квантованием): P.P.S. Вот обе восстановленные картинки рядом увеличенные в 2 раза, чтобы можно было их сравнить визуально (слева Q=49, справа Q=69): Очевидно, что левая картинка чуть более размытая (хоть и с меньшей ошибкой), а вот по шуму даже сложно сказать где больше шумит...
You do not have the required permissions to view the files attached to this post.
|
28 Nov 2023 21:54 |
|
![](./styles/getaway/theme/images/spacer.gif) |
Shaos
Admin
Joined: 08 Jan 2003 23:22 Posts: 23199 Location: Silicon Valley
|
Ладно - будет по верхней планке. И поиск можно делать не тупым перебором, а бинарный т.к. коэффициенты сжатия K всегда идут по возрастанию снизу-вверх, а детерминированное качество Q всегда идёт по убыванию снизу-вверх (а вот ошибка нет - она скачет ибо "по нижней планке" ошибка всегда ниже, чем у предыдущей "верхней планки", хотя в пределах одного и того же значения Q ошибка тоже всегда увеличивается снизу-вверх - её придётся подсчитывать на месте уже после выбора точки по которой мы будем работать). P.S. Смотрю на современные форматы и их алгоритмы во всяких разных статьях в интернете - сейчас стало модным указывать не коэффициент сжатия, а битность на пиксел bpp - например K=2.57 в моём случае стал бы 2.33 bpp, а K=8.96 стал бы 0.66 bpp. Зная K можно легко вычислить битность на пиксел как 6/K (в нашем случае изначально имеется 6 битов на пиксел). Удобство такого представления состоит в том, что по сути не имеет значения сколько бит было изначально в пикселе (это если не вычислять коэффициент сжатия как таковой) - можно считать сколько их стало. И например JPEG2000 на основе вейфлетов даёт показатели 0.32 и 0.25 bpp терпимого качества в случае чёрно-белых изображений, что для меня пока недостижимо (хотя наверное надо попробовать преобразования на больших квадратах типа 512х512 и даже 1024х1024 - там сжатие должно быть сильнее).
|
29 Nov 2023 01:12 |
|
![](./styles/getaway/theme/images/spacer.gif) |
Shaos
Admin
Joined: 08 Jan 2003 23:22 Posts: 23199 Location: Silicon Valley
|
В моём старом коде 1996 года интересно рассчитывается переиндексация спектра Уолша, чтобы он был в порядке увеличения частоты после того, как значения отсчётов получены быстрым преобразованием "бабочками" (FWT = Fast Walsh Transform): Получается чтобы вычислить новые индексы, программа выполняет FWT над специально подготовленным массивом - вот его содержимое до FWT: А вот после FWT (на самом деле тут слегка подправленный FWT - в случае обработки этого массива идёт деление не на sqrt(N) то бишь 8, а просто на N т.е. на 64 - по идее можно поправить изначальный массив так, чтобы делить стандартно на ![8)](./images/smilies/icon_cool.gif) : Как можно видеть теперь тут индексы для перестановки отсчётов. Совершенно не помню откуда я взял этот алгоритм (помню только, что обратил внимание тогда, что переиндексация в обратную сторону соответствует кодам Грэя, но тут явно не про коды Грэя) - в те времена у нас интернетов ещё небыло (первый интернет на кафедру я провёл лично в конце 1996 года выделенной линией, которую подцепил к линукс-маршрутизатору, который в свою очередь уже раздавал интернет через Ethernet на другие лабораторные компы с Win3.11 и Netscape). P.S. Чтобы увидеть тут коды Грэя надо переставить строчки в соответствии с новым индексом и представить старый индекс (число в квадратных скобках) в бинарном виде: Как можно видеть в бинарном виде от строчки к строчке меняется всегда ровно один бит (причём оно закручивается в кольцо) т.е. налицо коды Грэя, правда судя по всему реверснутые ![geek :egeek:](./images/smilies/icon_e_geek.gif)
|
01 Dec 2023 00:06 |
|
![](./styles/getaway/theme/images/spacer.gif) |
Shaos
Admin
Joined: 08 Jan 2003 23:22 Posts: 23199 Location: Silicon Valley
|
И точно - поправил код вот таким образом: и теперь внутри FWT всё делиться единообразно для всех случаев на sqrt(N) разве что в случае обработки spi нету перестановки - вот так теперь выглядит входной массив (все значения в 8 раз меньше): P.S. Правда это означает, что sqrt(N) должно быть целым числом, значит это работает только для N=4,16,64,256 и т.д. Вот например расчёт для N=16: P.P.S. Пожалуй верну как было - лучше всё таки все 2^n поддерживать, а не через один...
|
01 Dec 2023 23:41 |
|
![](./styles/getaway/theme/images/spacer.gif) |
Shaos
Admin
Joined: 08 Jan 2003 23:22 Posts: 23199 Location: Silicon Valley
|
![](images/spacer.gif) | ![](images/spacer.gif) | ![](images/spacer.gif) | ![](images/spacer.gif) | Shaos wrote: Вот более полная таблица коэффициентов сжатия K, фактора качества Q и ошибки ERR в зависимости от параметров квантования картинки FEMALER.BWS: В каждой колонке звёздочка означает точку с которой (и ниже) кодирование идёт без квантования (т.е. шаг квантования равен 1.0) - при этом качество устанавливается в 99 и отсчёты кодируются как есть без искажений (если не считать отбрасывание дробной части из-за которой ошибка ERR обычно не бывает меньше 2%), а всё что выше звёздочки будет с искажениями (даже если Q=99). Наверное надо брать по верхней планке - скажем если пользователь заказал Q=60, то в каждой колонке ищем самую верхнюю строчку, где получающееся качество <=60 (в данном примере Q=69) и далее убираем столько -1 и +1 отсчётов, сколько потребуется, чтобы уменьшить процент ненулевых отчётов до нужного числа (60%) и далее считаем коэффициент сжатия для разных вариаций обходов матрицы и способов сжатия - выбираем тот вариант, что меньше (а если размеры получились одинаковыми для разных вариантов, то выбираем вариант с меньшей ошибкой). По процентам наверное от 99 до 90 делаем без квантования (на уровне звёздочки в каждой колонке), от 89 до следующей перед 99 величине - в данном случае 69 - берём Q=99 по верхней планке, далее по верхней планке Q=69 и т.д. Убирать -1 и +1 чтобы подогнать итоговое качество к заказанному Q по-видимому надо с конца в соответствии с выбранной стратегией обхода матрицы, чтобы выиграть на отбрасывании хвостовых нулей (и если все отсчёты -1 и +1 исчерпались, то надо убирать -2 и +2 и т.д.). | ![](images/spacer.gif) | ![](images/spacer.gif) | ![](images/spacer.gif) | ![](images/spacer.gif) |
Первый диапазон адаптивного алгоритма готов - пока от 90 до 99 с минимальными искажениями (и отбрасыванием единичек в хвосте для уменьшения Q) на примере всё той же FEMALER.BWS: Вот как оно считало по каждой колонке для каждого Q: Программа делает перебор по всем вариациям сжатия (HUF+RLE,HUF,RLE) и по всем шести вариациям обхода спектра - как можно видеть для этой конкретной картинки 7-битное квантование всегда показывало лучший результат, однако вариации алгоритмов сжатия для разных Q отличаются. Ошибка по восстановленной картинке во всех случаях показывается как 2%
|
03 Dec 2023 15:32 |
|
![](./styles/getaway/theme/images/spacer.gif) |
Shaos
Admin
Joined: 08 Jan 2003 23:22 Posts: 23199 Location: Silicon Valley
|
А вот например чёрно-белые картинки с высоким качеством сжимаются плохо:
You do not have the required permissions to view the files attached to this post.
|
03 Dec 2023 15:43 |
|
![](./styles/getaway/theme/images/spacer.gif) |
Shaos
Admin
Joined: 08 Jan 2003 23:22 Posts: 23199 Location: Silicon Valley
|
А вот эта картинка не то, что не сжимается при Q=90, а даже наоборот - расширяется P.S. Презалил результат для этой картинки т.к. тут потребовалось удаление не только -1 и +1, но и -2/+2 для полной корректировки Q (если удалять только -1/+1 то Q корректировалось только до 94), но всё равно - результат получился "расширяющимся"...
You do not have the required permissions to view the files attached to this post.
|
03 Dec 2023 15:55 |
|
![](./styles/getaway/theme/images/spacer.gif) |
Shaos
Admin
Joined: 08 Jan 2003 23:22 Posts: 23199 Location: Silicon Valley
|
С высоким качеством хорошо сжимаются те картинки, где уже спектр подрезан: ![Image](http://www.nedopc.org/forum/download/file.php?id=13227) P.S. Интересной особенностью этого спектра является то, что ненулевые отсчёты начинаются с -4 и +4 т.к. весь спектр расположен в левом-верхнем квадранте (картинка увеличена в 2 раза и в ней просто нету мелких деталей), поэтому удаление началось именно с них...
You do not have the required permissions to view the files attached to this post.
|
03 Dec 2023 16:34 |
|
![](./styles/getaway/theme/images/spacer.gif) |
Shaos
Admin
Joined: 08 Jan 2003 23:22 Posts: 23199 Location: Silicon Valley
|
Приступаю к реализации алгоритма "по верхней планке", чтобы покрыть факторы качества ниже 90 - для начала надо пройтись по самой первой строчке таблицы, чтобы узнать верхние Q для каждой колонки. Далее находим нижние значения, от которых надо начинать плясать вверх - они вычисляются элементарно - минимально разумная точка это число, которое можно представить указанным количеством бит без квантования (это я уже умею вычислять - см.выше) либо самое нижнее возможное (у меня количество отчётов "выскочек" ограничено 99, поэтому если там в 99-й позиции уже стоит число, которое невозможно представить без искажений данным количеством бит, то танцуем от этого самого числа вверх). Далее бинарным поиском находим точку "по верхней планке" для Q=99 в каждой колонке и далее скачем вверх (опять же бинарным поиском), чтобы найти следующее Q не равное 99 - в таблице для FEMALER приведённой выше за 99 идёт 69 потом 49 потом 36 потом 28 и т.д. По этим цепочкам чисел выбираем самое ближайшее сверху для задаваемого пользователем значения Q (например если пользователь указал Q=50, то выбираем Q=69) и считаем по уже отработанному алгоритму, отбрасывая лишние единички для подгонки Q и перебирая все способы сжатия и все способы обхода матрицы для каждой из колонок (заранее отбросив все колонки, в которых не попадается выбранное значение Q, чтобы не тратить на них вычислительное время), выбирая лучший вариант в колонке и далее выбираем самое лучшее сжатие среди лучших по колонкам...
|
03 Dec 2023 18:00 |
|
![](./styles/getaway/theme/images/spacer.gif) |
Shaos
Admin
Joined: 08 Jan 2003 23:22 Posts: 23199 Location: Silicon Valley
|
Пока суть да дело прогнал ELAINE.BWS для Q=99 и для Q=90, чисто чтобы сравнить со старыми результатами: ![](http://www.nedopc.org/forum/download/file.php?id=13221) Результаты прогона адаптивного алгоритма:
You do not have the required permissions to view the files attached to this post.
|
04 Dec 2023 00:56 |
|
![](./styles/getaway/theme/images/spacer.gif) |
Shaos
Admin
Joined: 08 Jan 2003 23:22 Posts: 23199 Location: Silicon Valley
|
![](images/spacer.gif) | ![](images/spacer.gif) | ![](images/spacer.gif) | ![](images/spacer.gif) | Shaos wrote: А теперь порешаем интересный вопрос - если мы вводим произвольный размер картинок, то надо быть готовым к тому, что наши квадратики будут обрезаться где не попадя - а именно справа или снизу (т.к. слева и сверху они очевидно будут выровнены по левому и верхнему краям) и надо понять что делать с закрытыми краями, чтобы сжатие занимало как можно меньше места. Очевидные варианты, который приходят в голову: 0. закрашиваем край чёрным 1. закрашиваем край белым 2. копируем туда копию того что остаётся видимым 3. копируем туда зеркальную копию того что остаётся видимым Соответственно вот такие спектры Уолша у нас получаются для вышеописанных вариантов - для обрезания справа: ![Image](http://www.nedopc.org/forum/download/file.php?id=13229) ![Image](http://www.nedopc.org/forum/download/file.php?id=13231) ![Image](http://www.nedopc.org/forum/download/file.php?id=13233) ![Image](http://www.nedopc.org/forum/download/file.php?id=13235) И для обрезания снизу: ![Image](http://www.nedopc.org/forum/download/file.php?id=13228) ![Image](http://www.nedopc.org/forum/download/file.php?id=13230) ![Image](http://www.nedopc.org/forum/download/file.php?id=13232) ![Image](http://www.nedopc.org/forum/download/file.php?id=13234) А теперь выясним, какие из этих вариантов лучше всего сжимаются в WHI, если выбирать 6-битное квантование и разные варианты обхода (в названиях файлов они отражаются так - диагональный без дополнительного суффикса, горизонтальный - дополнительный суффикс H, вертикальный - дополнительный суффикс V): Как можно видеть краевая картинка справа (вертикальный отрез) лучше сжимается, если в скрытой части сидит копия видимой части и обход идёт вертикально (HALF2VV.WHI), и краевая картинка снизу (горизонтальный отрез) лучше сжимается, если в скрытой части сидит копия видимой части, но обход идёт уже горизонтально (HALF2HH.WHI). Зеркальные варианты отстают только на 12 байтов (HALF3VV.WHI и HALF3HH.WHI), а варианты с чёрными или белыми половинами судя по всему сжимаются плохо (причём когда обход идёт "перпендикулярно" отрезу, то сжатие несколько лучше). | ![](images/spacer.gif) | ![](images/spacer.gif) | ![](images/spacer.gif) | ![](images/spacer.gif) |
А теперь всё тоже самое с адаптивным алгоритмом при Q=90 Оригинал: ![Image](http://www.nedopc.org/forum/download/file.php?id=13327) Для ВЕРТИКАЛЬНЫХ половинок хуже всего сжимается картинка с чёрной половиной: ![Image](http://www.nedopc.org/forum/download/file.php?id=13229) Далее картинка с белой половинкой: ![Image](http://www.nedopc.org/forum/download/file.php?id=13231) И далее картинка с серой половинкой (чисто на пробу): Далее картинка с зеркальной половинкой: ![Image](http://www.nedopc.org/forum/download/file.php?id=13235) И самое лучшее сжатие показывает картинка с двумя одинаковыми половинками: ![Image](http://www.nedopc.org/forum/download/file.php?id=13233) Для ГОРИЗОНТАЛЬНЫХ половинок хуже всего сжимается картинка с белой половиной: ![Image](http://www.nedopc.org/forum/download/file.php?id=13230) Далее идёт чёрная половина: ![Image](http://www.nedopc.org/forum/download/file.php?id=13228) Потом зеркальная: ![Image](http://www.nedopc.org/forum/download/file.php?id=13234) И самая сжимаемая картинка с двумя одинаковыми половинками (как и в предыдущем случае): ![Image](http://www.nedopc.org/forum/download/file.php?id=13232) Как можно видеть и для вертикальных, и для горизонтальных половинок лучше всего сжимается вариант, когда обе половинки повторяют друг-друга (как я и писал ранее). Для угловой картинки, когда остаётся только левая-верхняя часть очевидно надо скопировать этот квадрант остальные 3 раза для получения лучшего результата по сжатию.
You do not have the required permissions to view the files attached to this post.
|
05 Dec 2023 00:17 |
|
![](./styles/getaway/theme/images/spacer.gif) |
Shaos
Admin
Joined: 08 Jan 2003 23:22 Posts: 23199 Location: Silicon Valley
|
Далее ещё попробовал с 1/4 и 3/4 вертикальными обрезами Картинка занимает 1/4 квадрата, остальное серая заливка: Картинка занимает 1/4 квадрата, остальное занимают 3 её копии - сжимается сильно лучше: Картинка занимает 3/4 квадрата, остальное серая заливка - сжимается плохо (чуть лучше цельной картинки): Картинка занимает 3/4 квадрата, остальное копия третей четвертины - сжимается ещё хуже (хоть и всё ещё лучше цельной картинки): По сути оно сравнимо по сжимаемости с цельной картинкой - смысла копировании четвертины в данном случае нет - просто заливаем остаток одним тоном (как я уже и писал ранее). А в случае 1/4 отреза копирование четвертинок даёт лучший результат нежели заливка одним тоном.
You do not have the required permissions to view the files attached to this post.
|
05 Dec 2023 02:19 |
|
![](./styles/getaway/theme/images/spacer.gif) |
Shaos
Admin
Joined: 08 Jan 2003 23:22 Posts: 23199 Location: Silicon Valley
|
После того как закончу адаптивный алгоритм и выкачу версию 1.0.5 надо будет написать полноценный WHI-энкодер для больших картинок (чёрно-белых и цветных) - он будет под ДОС и скорее всего просто будет резать картинку на BWS-файлы размером 64x64 и сжимать их запуская WALSHEXP.EXE много-много раз через автоматизацию (которую я добавил ещё в версии 1.0.4) по сгенерированному программно скрипту - так для меня будет быстрее всего. А вот WHI-декодер больших картинок уже можно будет начать писать под линух - для начала конвертер из командной строки в PNG и/или TIFF, а далее уже можно и прототип nedopixels городить Или лучше сначала сделать плугин для GIMP? Или аддон для Firefox?...
|
05 Dec 2023 03:03 |
|
Who is online |
Users browsing this forum: Claude AI [Bot] and 13 guests |
|
You cannot post new topics in this forum You cannot reply to topics in this forum You cannot edit your posts in this forum You cannot delete your posts in this forum You cannot post attachments in this forum
|
|