06-20-10 - Filters for PNG-alike

The problem :

Find a DPCM pixel prediction filter which uses only N,W,NW and does not range-expand (eg. ubytes stay in ubytes). (eg. like PNG).

We certainly could use a larger neighborhood, we could use adaptive predictors that evaluate the neighborhood for edges/etc., we would wind up with GAP from CALIC or something newer. We want to keep it simple so we can have a very fast decoder.

These filters :

    case 0: // 0 predictor is the same as NONE
        return 0;
    
    case 1: // N
        return N;
        
    case 2: // W
        return W;
        
    case 3: // gradient // this tends to win on synthetic images
        {
        int pred = N + W - NW;
        pred = RR_CLAMP_255(pred);
        return pred;
        }
        
    case 4: // average
        return (N+W)>>1;
        
    case 5: // grad skewed towards average // this tends to win on natural images - before type 12 took over anyway
        {
        int pred = ( 3*N + 3*W - 2*NW + 1) >>2;
        pred = RR_CLAMP_255(pred);
        return pred;
        }
    
    case 6: // grad skewed even more toward average
        {
        int pred = ( 5*N + 5*W - 2*NW + 3) >>3;
        pred = RR_CLAMP_255(pred);
        return pred;
        }
        
    case 7: // grad skewed N
        {
        int pred = (2*N + W - NW + 1)>>1;
        pred = RR_CLAMP_255(pred);
        return pred;
        }
        
    case 8: // grad skewed W
        {
        int pred = (2*W + N - NW + 1)>>1;
        pred = RR_CLAMP_255(pred);
        return pred;
        }
    
    case 9: // new
        {
        int pred = (3*N + 2*W - NW + 1)>>2;
        pred = RR_CLAMP_255(pred);
        return pred;
        }
        
    case 10:    // new
        {
        int pred = (2*N + 3*W - NW + 1)>>2;
        pred = RR_CLAMP_255(pred);
        return pred;
        }
        
    case 11: // new
        return (N+W + 2*NW + 1)>>2;
        
    case 12: // ClampedGradPredictor
    {
        int grad = N + W - NW;
        int lo = RR_MIN3(N,W,NW);
        int hi = RR_MAX3(N,W,NW);
        return rr::clamp(grad,lo,hi);
    }   
    
    case 13: // median
        return Median3(N,W,NW);
    
    case 14:
    {
        // semi-Paeth
        // but only pick N or W 
        int grad = N + W - NW;
        // pick closer of N or W to grad
        if ( RR_ABS(grad - N) < RR_ABS(grad - W) )
            return N;
        else
            return W;
    }

perform like this :

name	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14
ryg_t.train.03.bmp	56347	76447	70047	80619	76187	79811	77519	79771	76979	77399	76279	80383	75739	75875	74635
ryg_t.sewers.01.bmp	604843	475991	496067	468727	466363	455359	458111	458727	469203	456399	462727	496691	452663	495931	464915
ryg_t.font.01.bmp	42195	54171	53599	56135	73355	66955	70163	60199	63815	69499	70099	79983	59931	61219	56735
ryg_t.envi.colored03.bmp	316007	147315	136255	158063	139231	154551	148419	155379	149667	148683	143415	145871	148099	144851	153311
ryg_t.envi.colored02.bmp	111763	98835	87711	111367	93123	108867	100003	106275	95927	96391	97383	96907	99275	94371	100707
ryg_t.concrete.cracked.01.bmp	493143	416307	449899	426755	403779	402635	400923	408019	420291	398215	408299	437371	409055	440371	424087
ryg_t.bricks.05.bmp	568755	534267	524243	514563	509375	493923	497639	505267	499007	501079	497419	551687	499855	547935	511595
ryg_t.bricks.02.bmp	684515	590955	577207	557155	560391	537987	545019	551251	544555	549543	544635	602115	545919	600139	557659
ryg_t.aircondition.01.bmp	41595	33215	34279	33535	33199	32695	32683	32619	33207	32503	32987	35795	31507	35171	32243
ryg_t.2d.pn02.bmp	25419	27815	28827	29499	32203	32319	32443	29679	32531	32315	32575	34183	28307	31247	27919
ryg_gemein.bmp	797	801	173	153	565	585	553	521	205	633	529	813	153	825	141
kodak_24.bmp	843281	735561	760793	756509	744021	736037	735797	735989	753709	733105	741801	785077	719185	777905	727221
kodak_23.bmp	865985	593977	616885	617105	591501	592561	588837	595949	609437	586121	595793	620657	585453	617825	601713
kodak_22.bmp	919613	732613	756249	741441	719973	712757	711245	721365	732337	709621	719157	760065	706517	763481	724053
kodak_21.bmp	797741	753057	691653	746033	713469	716065	710321	737017	713845	720525	704129	744785	701733	744633	709445
kodak_20.bmp	624901	563261	538069	571633	540981	548329	541773	559437	548549	546565	540337	559545	539289	557105	545901
kodak_19.bmp	847781	724541	728337	732717	718309	712989	712217	716593	729505	712893	715053	752173	689953	756849	698881
kodak_18.bmp	958657	808577	820253	820429	783373	783089	777377	794965	799449	779117	782541	821717	783005	821025	802569
kodak_17.bmp	782061	664829	655845	685273	651025	657225	650477	666625	666645	653117	652293	680813	644849	675045	656597
kodak_16.bmp	664401	696493	595101	673961	646981	647441	643353	675157	640833	658721	631509	684517	628837	682217	629293
kodak_15.bmp	779289	639009	660137	677649	643985	651729	644809	650525	666229	641669	650377	673545	635441	662389	645817
kodak_14.bmp	912149	800681	742901	787273	754233	754325	749641	778777	758045	760761	744001	795029	743909	791341	755425
kodak_13.bmp	1015697	932969	898929	941109	890989	900533	890221	918073	905705	897865	888113	925757	894461	922701	907029
kodak_12.bmp	690537	641517	583717	641973	613461	617881	612461	635253	617913	620833	607177	644837	598393	638889	602213
kodak_11.bmp	773937	725081	674657	714169	697533	691425	690389	708197	695109	698369	685965	738609	671365	739385	676597
kodak_10.bmp	766701	650637	648349	665309	648997	641961	641481	651741	651785	643369	642133	685733	623437	684949	629193
kodak_09.bmp	703689	640025	628161	659637	635201	637657	633881	644193	647817	636281	634105	662125	615393	662801	621873
kodak_08.bmp	1026037	862013	888589	835329	884329	841405	859717	839193	861917	856097	865405	942073	792833	950005	792201
kodak_07.bmp	725525	654925	605753	629757	633945	622693	627053	643069	621433	634965	620645	673361	597821	666629	604337
kodak_06.bmp	796077	786789	680841	750253	731117	723657	722981	753989	714849	739405	709825	772685	703417	773613	705529
kodak_05.bmp	981245	850313	836165	845001	815801	814429	810709	832337	825073	815897	811729	852385	808993	853785	828145
kodak_04.bmp	845721	672369	679245	692469	659981	663625	657621	670629	678165	658845	661957	691945	653629	688253	670325
kodak_03.bmp	656841	605525	559081	619713	581713	596313	587633	607841	600725	592761	584449	601901	579221	592745	587409
kodak_02.bmp	761633	666601	663837	677385	648117	649785	644985	661253	662077	647553	647545	682089	640501	687305	654309
kodak_01.bmp	896361	850353	811873	828397	822169	807197	810217	827621	815245	818249	807665	869829	781173	875265	788725
bragzone_TULIPS.bmp	1052229	729141	757129	688121	703317	671417	683069	683653	696193	682109	691257	756241	675637	761477	704293
bragzone_SERRANO.bmp	150898	172286	160718	193602	255462	274994	278094	212478	254902	274478	277418	285990	171918	213214	167058
bragzone_SAIL.bmp	1004581	865725	826729	834385	811121	798037	798301	819669	807221	805785	796761	862209	795581	868857	813521
bragzone_PEPPERS.bmp	712087	469243	456511	438211	442695	428627	433227	437215	436595	436059	434359	471587	426191	474595	439575
bragzone_MONARCH.bmp	907737	670825	671745	644513	638201	623613	627513	640213	640485	630941	630941	676401	624925	679553	652849
bragzone_LENA.bmp	745299	484027	513747	506631	478875	481911	477131	481819	494431	474343	483007	498519	478559	498799	489203
bragzone_FRYMIRE.bmp	342567	432867	399963	481259	608567	664895	670755	544963	612075	666279	668187	693467	433755	456899	421263
bragzone_clegg.bmp	806117	691593	511625	518489	1208409	1105433	1167561	733217	951773	1158429	1165953	1289969	502845	1286365	505093

commentary :

The big surprise is that ClampedGradPredictor (#12) is the fucking bomb. In fact it's so good that it hides the behavior of other predictors. For example plain old Grad is never picked. Also predictor #5 (grad skewed towards average) was actually by far the best until #12 came along.

The other minor surprise is that W is actually best sometimes, and N is never best, and generally N is much worse than W. Now, it is no surprise that W is better than N - it is a well known fact that typical images have much stronger horizontal correlation than vertical, but I am surprised just how *big* the difference is.

More in the next post.