nabbla (nabbla1) wrote,
nabbla
nabbla1

Стратегии zlib: RLE рулит!

В продолжение темы об эффективном сжатии в PNG. Тогда мне удалось достичь очень недурственных результатов, всего навсего поменяв стратегию zlib с Z_DEFAULT_STRATEGY на Z_FILTERED - т.е архиватор заранее подготовлен к тому, что на его вход пойдет поток, уже прошедший через фильтр-предиктор. Корреляция между символами тем самым почти убрана, и упор делается в основном на алфавитное (энтропийное) кодирование, когда более часто встречаемым значениям назначаются более короткие коды.

Есть еще две стратегии, имена которых не обещают ничего хорошего:
Z_HUFFMAN_ONLY - название намекает, что мы вообще задвигаем LZ77, и используем исключительно Хаффмана, и в описании говорится, что этот метод даёт меньшую компрессию, зато исключительно быстр.
Z_RLE - сокращение от Run-Length Encoding, это же самое простое кодирование, где повторяющийся n раз одиночный символ a заменяется парой (n,a), и такие пары в выходном потоке идут вперемешку с "литералами", причем необходимы дополнительные биты, чтобы отличить одно от другого. В описании опять же говорится - метод очень быстр, если известно, что в данных будут такие повторяющиеся символы, например, у нас уже обработанный скан с большими белыми областями.

И вот ведь удивительная вещь: именно при использовании Z_RLE для сырых сканов достигается наивысшая компрессия, а второй по эффективности метод - Z_HUFFMAN_ONLY, а Z_FILTERED и DEFAULT_STRATEGY нервно курят в сторонке, выигрывая у RLE и HUFFMAN только лишь на "искусственных" пустых страницах. При этом время кодирования у "легковесных" RLE и HUFFMAN по крайней мере в 3 раза меньше, чем у двух других!

Осторожно, под катом огромная таблица.


Здесь я попробовал свежие сканы книги "Животные близкие и далёкие" сжать разными стратегиями. Получается, что если выбрать только одну какую-то стратегию, то это должна быть RLE. Если мы будем каждый раз пробовать все 4 и выбирать наилучшую, выиграем на этом 0.04% объема, ценой увеличения времени кодирования в 8 раз. Возможно, более разумно будет выбирать Default_strategy на изображениях с 1,2,4 бит/пиксель и 8-битных палитрах, а для всех остальных (256 градаций серого и RGB24) применять RLE. Можно было бы еще пройтись по изображению и "самому" оценить, как много там равномерных областей для RLE, и сделать осознанный выбор между RLE и HUFFMAN, но пока лениво этим заниматься, все равно это сырые сканы, которые по моей философии должны быть преобразованы в выходные файлы с сохранением в .DLRN всей необходимой информации для возвращения в исходное состояние.

  Без сжатия Filtered Default Huffman RLE Минимум
0 100368000 55115452 55115452 55034834 55046426 55034834
1 33343800 15392595 15392595 15126127 15143052 15126127
2 33343800 10997784 10997784 11376154 10772454 10772454
3 30960500 10355634 10355634 10601656 10117121 10117121
4 30960500 11449975 11449975 11672342 11199555 11199555
5 31697920 8697079 8697079 9617583 8493368 8493368
6 31697920 11133544 11133544 11781924 10951909 10951909
7 30725930 12543793 12543793 13122309 12324053 12324053
8 30725930 12948964 12948964 13339406 12735616 12735616
9 31494976 12996738 12996738 13609322 12796777 12796777
10 31494976 14593655 14593655 14530700 14358946 14358946
11 31494976 14676872 14676884 14650582 14463759 14463759
12 31494976 14651456 14651468 14531241 14416746 14416746
13 31494976 15186863 15186875 15036170 14960027 14960027
14 31494976 14768183 14768195 14597344 14516887 14516887
15 31494976 15120711 15120723 15014475 14911021 14911021
16 30206528 14717297 14717309 14514003 14490024 14490024
17 30206528 14079282 14079294 14015900 13857113 13857113
18 30206528 14214865 14214877 14106059 13998945 13998945
19 30206528 13848492 13848504 13843556 13644629 13644629
20 30666000 13432103 13432103 13711237 13245487 13245487
21 32120240 13587991 13587991 14043814 13384823 13384823
22 32120240 13736476 13736476 14052398 13521595 13521595
23 32120240 13849126 13849126 14204336 13648564 13648564
24 32120240 15181728 15181740 15069297 14964900 14964900
25 32120240 14991450 14991462 14932498 14763400 14763400
26 32120240 13561337 13561337 14015133 13365698 13365698
27 32120240 13217434 13217434 13582682 12987202 12987202
28 32120240 12701323 12701323 13524218 12519424 12519424
29 32120240 12157027 12157027 13046190 11938326 11938326
30 32120240 12215124 12215124 12994518 12011850 12011850
31 32120240 12597464 12597464 13323147 12387335 12387335
32 32120240 13486199 13486199 14016038 13303088 13303088
33 32120240 12525214 12525214 13256486 12300575 12300575
34 32120240 12505378 12505378 13329783 12303174 12303174
35 32120240 12890690 12890690 13530180 12693367 12693367
36 32120240 12811662 12811662 13457774 12614175 12614175
37 32120240 12326354 12326354 13146437 12134101 12134101
38 32120240 9697885 9697885 10664673 9519828 9519828
39 32120240 8169204 8169204 9176572 7950117 7950117
40 32120240 12514690 12514690 12520165 12244370 12244370
41 32120240 10095713 10095713 10709844 9877571 9877571
42 32120240 17692121 17692133 17583724 17594748 17583724
43 31625336 15160034 15160046 14866186 14881662 14866186
44 31625336 17156992 17157004 17008976 17022556 17008976
45 31625336 17648519 17648531 17529080 17543103 17529080
46 31625336 19241461 19241473 19211267 19215503 19211267
47 31625336 16014145 16014157 15787918 15803787 15787918
48 31625336 15961845 15961857 15737542 15745348 15737542
49 31625336 15079298 15079310 14816485 14816891 14816485
50 31625336 19107250 19107262 19084899 19088167 19084899
51 31625336 17285829 17285841 17142457 17157544 17142457
52 31625336 19262822 19262834 19238579 19242343 19238579
53 31625336 15446341 15446353 15187046 15188168 15187046
54 31625336 17110799 17110811 16995730 16979607 16979607
55 31625336 17736900 17736912 17669353 17646485 17646485
56 31625336 16686761 16686773 16490576 16516609 16490576
57 30970032 18924537 18924549 18902678 18906123 18902678
58 30865500 16400394 16400406 16245449 16255696 16245449
59 31098752 17740571 17740583 17645808 17653230 17645808
60 30618528 18231321 18231333 18198698 18203359 18198698
61 30618528 17591107 17591119 17508621 17515589 17508621
62 30618528 17357011 17357023 17274540 17279073 17274540
63 30904037 17305325 17305337 17205064 17210068 17205064
64 30904037 17466705 17466717 17392493 17401585 17392493
65 31853904 16739209 16739221 16581834 16593739 16581834
66 31853904 18461101 18461113 18402646 18410298 18402646
67 31853904 18202995 18203007 18147189 18154385 18147189
68 31853904 15773929 15773941 15554677 15569568 15554677
69 31853904 15787088 15787100 15586206 15599700 15586206
70 31853904 16564533 16564545 16420261 16433226 16420261
71 31853904 16563412 16563424 16400243 16411962 16400243
72 31853904 18377086 18377098 18331338 18337513 18331338
73 31853904 16143167 16143179 15955120 15968925 15955120
74 31853904 17958504 17958516 17852979 17853703 17852979
75 31853904 17404034 17404046 17265750 17258606 17258606
76 31853904 18782169 18782181 18752076 18756979 18752076
77 31853904 17809109 17809121 17721289 17690299 17690299
78 31853904 19631209 19631221 19605934 19609470 19605934
79 31853904 18175152 18175164 18104823 18113533 18104823
80 31853904 18533243 18533255 18497399 18502216 18497399
81 31853904 18305769 18305781 18275021 18279776 18275021
82 31853904 14035609 14035621 13650168 13684348 13650168
83 31853904 15811951 15811963 15567887 15584192 15567887
84 31853904 18424044 18424056 18395107 18399216 18395107
85 31853904 18030521 18030533 17922472 17926319 17922472
86 31853904 17821892 17821904 17706932 17717015 17706932
87 31853904 16858528 16858540 16706585 16720014 16706585
88 31853904 16905888 16905900 16768617 16778894 16768617
89 31853904 19216745 19216757 19195156 19198447 19195156
90 31853904 17163341 17163353 17012507 17025454 17012507
91 31853904 15438646 15438658 15155940 15174771 15155940
92 31853904 16187734 16187746 15932403 15949790 15932403
93 31853904 16281888 16281900 16095322 16109429 16095322
94 31853904 16955381 16955393 16777068 16791841 16777068
95 31853904 15260337 15260349 14973986 14990844 14973986
96 31853904 17055831 17055843 16876602 16891476 16876602
97 31853904 18018413 18018425 17941188 17950404 17941188
98 95449632 58090338 58090350 58037563 58044619 58037563
99 3977068 11183 11183 500472 14489 11183
100 31944424 16933226 16933238 16835272 16813054 16813054
101 31551072 17095306 17095318 17044762 17002230 17002230
102 30499380 16482351 16482363 16398097 16379206 16379206
103 30499380 17495964 17495976 17472770 17476453 17472770
104 30499380 16221813 16221825 16086653 16095914 16086653
105 30499380 15015127 15015139 14738631 14763914 14738631
106 30499380 18245163 18245175 18220702 18224395 18220702
107 30499380 15587219 15587231 15355424 15385887 15355424
108 92621376 50868898 50868910 50578268 50603571 50578268
109 3859224 11076 11076 486111 14540 11076
110 30732640 16715859 16715871 16623937 16597890 16597890
111 30732640 15020757 15020757 15212917 14900181 14900181
112 30732640 18699342 18699354 18671052 18675570 18671052
113 30732640 14892303 14892315 14745745 14696813 14696813
114 30732640 14870137 14870149 14661203 14641364 14641364
115 30732640 11611756 11611756 11654067 11323403 11323403
116 30732640 18160950 18160962 18134595 18138459 18134595
117 30732640 14337434 14337446 14221051 14106976 14106976
118 30732640 18247959 18247971 18201646 18206964 18201646
119 30732640 16842969 16842981 16717516 16727485 16717516
120 30732640 18342348 18342360 18308374 18313409 18308374
121 30732640 15600470 15600482 15398180 15393160 15393160
122 30732640 17718582 17718594 17671372 17677743 17671372
123 30732640 15935724 15935736 15762754 15766317 15762754
124 30732640 15819829 15819841 15627782 15642414 15627782
125 30732640 18297291 18297303 18269854 18273964 18269854
126 94584672 54849913 54849925 54729246 54742609 54729246
127 3941028 11158 11158 496563 14540 11158
128 31534752 17100769 17100781 16939912 16956317 16939912
129 31534752 18155693 18155705 18112802 18119324 18112802
130 31534752 16582099 16582111 16443794 16457118 16443794
131 31534752 16779611 16779623 16661270 16641753 16641753
132 31534752 17252523 17252535 17126860 17134045 17126860
133 31534752 16047429 16047441 15994384 15905233 15905233
134 31534752 16302113 16302125 16139014 16146543 16139014
135 31534752 15750416 15750428 15544473 15558000 15544473
136 93060120 51320560 51320572 51073297 51095882 51073297
137 3877505 11160 11160 488212 14674 11160
138 30435660 15424573 15424573 15522020 15339818 15339818
139 30435660 15202671 15202683 14988764 14985312 14985312
140 30476000 17408895 17408907 17354623 17332887 17332887
141 30476000 14631263 14631263 14675766 14480345 14480345
142 30476000 15964836 15964848 15777692 15783678 15777692
143 30476000 18607021 18607033 18585672 18588863 18585672
144 30476000 18292658 18292670 18292109 18281745 18281745
145 30476000 15541314 15541326 15333163 15349201 15333163
146 30476000 18740077 18740089 18719406 18722193 18719406
147 30476000 16842319 16842331 16733219 16745563 16733219
148 30476000 16793602 16793614 16686671 16694309 16686671
149 30476000 18415233 18415245 18398330 18400904 18398330
150 30476000 11858007 11858019 11770646 11567886 11567886
151 30476000 16251420 16251432 16173081 16127075 16127075
152 30476000 16102559 16102571 15927703 15936691 15927703
153 30476000 14300231 14300243 14161348 14068878 14068878
154 30476000 17220494 17220506 17159381 17167117 17159381
155 30476000 15912822 15912834 15824141 15782993 15782993
156 30476000 14866260 14866272 14724763 14684783 14684783
157 30476000 13615218 13615230 13517530 13399456 13399456
158 30476000 17069411 17069423 16971211 16980594 16971211
159 30476000 18426475 18426487 18401885 18406102 18401885
160 30476000 18292490 18292502 18257317 18261153 18257317
161 30476000 17719224 17719236 17682826 17688295 17682826
162 30476000 16719756 16719768 16582738 16593164 16582738
163 30476000 14544951 14544963 14496580 14372208 14372208
164 30476000 17384056 17384068 17333723 17340166 17333723
165 30476000 14392183 14392195 14221178 14146266 14146266
166 30476000 16732166 16732178 16639535 16646083 16639535
167 30476000 15740185 15740197 15619209 15584624 15584624
168 30476000 16789210 16789222 16679439 16689563 16679439
169 30476000 16655966 16655978 16567449 16575508 16567449
170 30476000 15577399 15577411 15408651 15421212 15408651
171 30476000 17338660 17338672 17255168 17261122 17255168
172 30476000 16408663 16408675 16299962 16309138 16299962
173 30476000 16099471 16099483 15954589 15967616 15954589
174 30476000 16459743 16459755 16339066 16349488 16339066
175 30476000 15500677 15500689 15305852 15320551 15305852
176 30476000 16830205 16830217 16753424 16762322 16753424
177 30476000 18936207 18936219 18919898 18922574 18919898
178 30476000 17197732 17197744 17115939 17122497 17115939
179 30476000 16527503 16527515 16361447 16375352 16361447
180 30476000 17743902 17743914 17715221 17719502 17715221
181 30476000 13856470 13856482 13545658 13567293 13545658
182 30476000 17638115 17638127 17601104 17607114 17601104
183 30476000 15778956 15778968 15605394 15620091 15605394
184 30476000 17276498 17276510 17236329 17241918 17236329
185 30476000 14801628 14801640 14697345 14626321 14626321
186 30476000 17387560 17387572 17322094 17329649 17322094
187 30476000 14493011 14493023 14333823 14296022 14296022
188 30476000 18865762 18865774 18845901 18848662 18845901
189 30476000 14097344 14097356 13905585 13850501 13850501
190 30476000 16902347 16902359 16786268 16796240 16786268
191 30476000 16337706 16337718 16157736 16178954 16157736
192 30476000 18776878 18776890 18755296 18758557 18755296
193 30476000 17710806 17710818 17655792 17663069 17655792
194 30476000 15171327 15171339 14933709 14945115 14933709
195 30476000 16075461 16075473 15962235 15934700 15934700
196 30476000 18249561 18249573 18229517 18232422 18229517
197 30476000 15828382 15828394 15638647 15656014 15638647
198 30476000 16770917 16770929 16683931 16691054 16683931
199 30476000 15816670 15816682 15637532 15652379 15637532
200 30476000 18446054 18446066 18427351 18430470 18427351
201 30476000 16515072 16515084 16368240 16379280 16368240
202 30476000 18207188 18207200 18187197 18190344 18187197
203 30476000 18073428 18073440 18050653 18054334 18050653
204 30476000 15971880 15971892 15806600 15805659 15805659
205 30476000 16215046 16215058 16043891 16057650 16043891
206 30476000 18214490 18214502 18194649 18191654 18191654
207 30476000 13563722 13563734 13204283 13230554 13204283
208 30476000 16761891 16761903 16650750 16657526 16650750
209 30476000 16527250 16527262 16396685 16405729 16396685
210 30476000 16566513 16566525 16428491 16439535 16428491
211 30476000 14999779 14999791 14925128 14857987 14857987
212 30476000 15123982 15123994 14949389 14922435 14922435
213 30476000 17108884 17108896 17022797 17007852 17007852
214 30476000 17413472 17413484 17344939 17345380 17344939
215 30476000 15328850 15328862 15136413 15129191 15129191
216 32609400 19263458 19263470 19233208 19236059 19233208
217 32609400 17328440 17328452 17211942 17195473 17195473
218 98164800 59602274 59602286 59543773 59551248 59543773
219 4090200 11299 11299 515074 14540 11299
220 33139800 17253545 17253557 17060944 17077540 17060944
221 33139800 19295567 19295579 19236383 19226035 19226035
222 33139800 19141043 19141055 19072731 19081759 19072731
223 33139800 16961588 16961600 16809054 16821227 16809054
224 33139800 17462854 17462866 17322263 17333084 17322263
225 33139800 17000835 17000847 16787050 16805481 16787050
226 33139800 19998334 19998346 19972703 19976152 19972703
227 33139800 17869401 17869413 17694194 17706298 17694194
228 94199712 53067676 53067688 52969217 52982655 52969217
229 3924988 11162 11162 494157 14539 11162
230 32823600 19136454 19136466 19111282 19115416 19111282
231 32823600 17403830 17403842 17260233 17258705 17258705
232 32823600 16931038 16931050 16823499 16786341 16786341
233 32823600 19149228 19149240 19122761 19126771 19122761
234 32823600 15510635 15510647 15454177 15319309 15319309
235 32823600 16308088 16308100 16048629 16077425 16048629
236 32823600 17888020 17888032 17772144 17781221 17772144
  Без сжатия Filtered Default Huffman RLE Минимум
Сумма 7692350079 3995907547 3995909899 3992066703 3964211146 3962746684
отн 1,94116624 1,00836815 1,00836874 1,00739891 1,00036956 1


И поясню, как же так получается, что RLE всех рвет. Дело в том, что это все-таки Хаффман+RLE. Подозреваю, что RLE "отвечает" за эффективное кодирование равномерной черной области скана вне страницы, и от размера этой зоны зависит, будет ли RLE эффективнее только Хаффмана или выйдет вперед. Почему добавление новой альтернативы может снизить степень сжатия - тоже понятно, делается по сути "жадный выбор" - кодер заметил повторяющиеся символы и сразу их закодировал, не подумав о том, что из-за его жадности битовые коды каждого символа будут получаться длиннее - кроме 256 "литералов" теперь еще будут коды смещений, и лишь в половине ситуаций игра стоит свеч.

Ну и еще хочу обратить внимание - сжатие получается примерно в 2 раза - весьма недурный результат для сжатия без потерь на реальных изображениях, TIFF в этой ситуации становится на лопатки - сжатый по LZW файл может получиться даже больше несжатого, но все-таки, можно было бы и лучше... Проблема в том, что исследований по сжатию изображений и видео без потерь почти не ведется, все силы брошены на мегаэффективное сжатие с потерями, а тут считается, что ловить нечего, и вообще "если вы такие упертые чтобы хранить оригиналы, купите себе винчестеры побольше". Посмотрим, получится ли ScanCombine'у стать в некотором роде архиватором, вычленяя по мере обработки изображения его характерные детали.
Tags: scancombine, программки
Subscribe

  • Нахождение двух самых отдалённых точек

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

  • Слишком общительный счётчик

    Вчера я чуть поторопился отсинтезировать проект,параметры не поменял: RomWidth = 8 вместо 7, RamWidth = 9 вместо 8, и ещё EnableByteAccess=1, чтобы…

  • Балансируем конвейер QuatCore

    В пятницу у нас всё замечательно сработало на симуляции, первые 16 миллисекунд полёт нормальный. А вот прошить весь проект на ПЛИС и попробовать "в…

  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your IP address will be recorded 

  • 7 comments