06-20-10 - Searching my PNG-alike

Okay so stealing some ideas from pngcrush let's check out the search space. I decide I'm going to examine various filters, Loco or no loco, LZ min match len, and LZ compress "level" (level = how hard it looks for matches).

Here are the results for my PNG-alike with the modes :

0 = no filter
Loco = no filter (in loco space)
Normal = select a single DPCM filter for the whole image
N+L = Normal in LOCO space
Adaptive = per row best DPCM filter
A+L = you get it by now

The left six columns are these modes with default LZ parameters (Fast match, min match len = 4). The right six columns are the same modes with LZ parameters optimized for each mode.

name	0	Loco	Normal	N+L	Adaptive	A+L	optimized LZs		0	Loco	Normal	N+L	Adaptive	A+L
ryg_t.yello.01.bmp	458255	435875	423327	427031	438946	431678			372607	359799	392963	395327	415370	401618
ryg_t.train.03.bmp	56455	55483	69635	76211	68022	67678			36399	35195	31803	40155	37582	36638
ryg_t.sewers.01.bmp	599803	610463	452287	452583	466154	452834			593935	593759	421779	420091	443786	421166
ryg_t.font.01.bmp	42239	32207	38855	38855	53070	36746			33119	26911	35383	35383	40998	33798
ryg_t.envi.colored03.bmp	297631	309347	150183	165803	142658	157046			265755	278103	102487	114923	95394	109022
ryg_t.envi.colored02.bmp	109179	112623	100687	113867	89178	98374			90039	93535	62139	68027	54662	57514
ryg_t.concrete.cracked.01.bmp	481115	407759	355575	356911	408054	361602			384795	353235	299963	301907	342810	310342
ryg_t.bricks.05.bmp	551475	485271	418907	417655	492622	418406			469063	448279	372195	370459	429066	373310
ryg_t.bricks.02.bmp	665315	632623	482367	481347	538670	483106			590319	577699	455431	455203	522158	455426
ryg_t.aircondition.01.bmp	41635	29759	26011	26011	32866	25738			29023	25103	20547	20547	23946	20522
ryg_t.2d.pn02.bmp	25075	26539	28303	29259	28046	28974			22147	22723	25915	26179	26194	25790
kodak_24.bmp	826797	771829	640137	634141	726892	633308			723681	712285	567693	558085	684060	559564
kodak_23.bmp	835449	783941	576481	569981	608476	565172			724641	712001	481577	478041	551292	479240
kodak_22.bmp	898101	879949	655461	651213	722096	651000			803429	804073	577433	571301	689664	574252
kodak_21.bmp	781077	708861	617565	629401	705608	618424			647881	633069	549865	549025	665724	545584
kodak_20.bmp	609705	561957	495509	500161	537692	494484			501293	490849	434865	431745	506592	429556
kodak_19.bmp	822045	733053	630793	624897	697020	619064			673953	658345	550669	541845	660444	541424
kodak_18.bmp	941565	912081	691161	692425	789736	693804			850705	848353	618961	619949	764004	622628
kodak_17.bmp	758089	678233	597225	592941	660016	590292			617097	606045	507169	504961	610092	508672
kodak_16.bmp	650557	587537	543001	543001	607916	545244			522829	511833	466277	466277	536280	468136
kodak_15.bmp	759109	697257	595353	590321	648656	586324			643385	628481	511193	504213	593304	506728
kodak_14.bmp	891629	793553	661505	657357	745816	649928			749085	731569	584645	580301	707596	581520
kodak_13.bmp	997161	891637	729425	730901	878212	729580			853557	829057	677041	678613	802224	680196
kodak_12.bmp	672361	602825	545921	562749	606004	549292			539305	526793	465297	472693	539532	467088
kodak_11.bmp	758197	691697	604869	597125	665364	587264			639537	625145	523649	512685	608388	510200
kodak_10.bmp	747121	681213	592637	589561	635972	578888			625961	611553	504573	499753	576284	497400
kodak_09.bmp	688365	629429	587233	583245	627916	571652			565449	562329	501377	495637	567772	491896
kodak_08.bmp	1001257	882153	686961	684177	792916	684056			860269	825757	615657	610505	766620	610524
kodak_07.bmp	709829	673917	568649	563561	616820	561636			605177	600157	480705	473233	551136	473500
kodak_06.bmp	779709	694229	600145	600145	687824	601564			642525	626449	534037	534037	637180	534804
kodak_05.bmp	962357	873793	700581	695257	810688	694828			845905	823025	633581	623341	783400	624368
kodak_04.bmp	813869	729865	613241	606849	672176	607280			677345	660057	531533	522061	622904	528064
kodak_03.bmp	639809	586873	522049	542681	581880	527856			519549	510309	437765	452965	511900	443948
kodak_02.bmp	729069	649709	603853	591781	654408	585916			598913	584941	515437	502941	602364	500964
kodak_01.bmp	872669	747333	661481	655597	772808	653388			699945	682005	593001	582389	689436	586328
bragzone_TULIPS.bmp	1032589	1021309	646905	652213	701508	652128			966881	969913	565997	571377	662504	570796
bragzone_SERRANO.bmp	150142	151706	169982	169302	173229	175217			103462	103566	139306	139074	142609	143457
bragzone_SAIL.bmp	983473	941993	686013	686117	795152	686204			892301	887097	613845	609953	762420	610008
bragzone_PEPPERS.bmp	694247	679795	424603	423679	451006	424262			655987	650771	369291	366611	416426	368106
bragzone_MONARCH.bmp	887917	868533	600373	598985	654864	598976			810325	805725	507937	508085	598348	508096
bragzone_LENA.bmp	737803	733251	493703	498299	498274	502150			710215	704763	467103	475179	471586	477638
bragzone_FRYMIRE.bmp	342667	344807	419859	420811	420506	419026			241899	242355	335063	336859	335990	335894
bragzone_clegg.bmp	760493	799717	525077	541329	523580	536244			557529	571413	445897	468265	444736	465376

One important note :

The "Normal" filters include the option to do a post-filter Loco conversion. This is different than the "loco space" option in the modes above. Let me elaborate. "Loco" in the modes listed above means transform the image into Loco colorspace, and then proceed with filtering and LZ. Loco built into a filter mode means, on each pixel do the filter delta, then do loco conversion. This can be integrated directly into the DPCM pixel delta code, so it's just considered a filter type. In particular, in "loco space", then the N,W,NW neighbors are already in loco colorspace. When loco is part of the filter, the neighbors are in RGB space and the delta is converted after the fact. If everything was linear, these would be equivalent.

Okay, what do we see?

It's very surprising to me how much LZ optimization helps. In particular it surprises me that making the LZ search *worse* (by turning down compression "level") helps a lot; as does increasing match len; on natural images a min match len around 8 or 10 is usually best. (or even more, I forbid a min match len > 10 because it starts to hurt decode speed).

Well we were hoping that we could pick the mode based on the default LZ parameters, and then just optimize the LZ parameters for that one mode. It is often the case the the best mode after optimization is the same as the best mode before optimization, but not always. When it is not the case, it is usually a small mistake. However, there is one case where it's a very bad mistake - on ryg_t.yello.01.bmp you would make output of 393k instead of 360k.

Natural images are the easiest; for them you can pretty much just pick A+L (or N+L) and you're very close to best if you didn't get the best. Synthetic images are harder, they are very sensitive to the exact mode.

We can also say that no filter + loco is almost always wrong, except for that same annoying one case. Unfortunately I don't see any heuristic that can detect when 0+loco needs to be checked. Similarly for adaptive + noloco.

Obviously there's a fundamental problem when the initial sizes are very close together, you can't really differentiate between the modes. When the sizes are very far apart then it is a reliable guess.

Let me briefly note things I could be searching that I'm not :

Rearranging pixels in various ways, eg. RGBRGB -> RRRGGGBB , or to whole planes; interleaving lines, different scan orders, etc. etc.

LSQR fits for predictors. This doesn't hurt decode speed a ton so it would fit in my design spec, I'm just getting sick of wasting my time on this so I'm not bothering with it.

Predictors on different regions instead of per row. eg. a predictor type per 16x16 tile or something.

Anything that hurts decode speed, eg. bigger predictors, adaptive predictors, non-LZ coder, etc.

Oh I'm also not looking at any pixel format conversions; I assume the client has put it in the pixel format they want and won't change it. Obviously some of the PNG optimizers can win by palettizing when not many colors are actually used, and of course there are lots of other pixel formats that might help, blah blah.

Oh while I'm at it, I should also note that my LZ is actually kind of crippled for this comparison. I divide the data stream into 256k chunks and compress them completely independently (no LZ window across the chunk boundary). This lets me seek on compressed data and decompress portions of it independently, but it is quite a bad penalty.