Fundamental error analysis and geometric interpretation for block truncation coding techniques

Various variants and hybrid approaches evolved from the origin of Delp and Mitchell's block truncation coding (BTC) or moment preserving quantizer (MPQ) have formed a niche as an effective and simple image compression methodology with attractive coding performance achieved at moderate bitrates. As BTC is still lacking a fundamental error analysis, in this paper we present some fundamental insights regarding one-bit (or two-level) BTC's truncation error by providing mathematical analysis as well as novel geometric interpretation. We further show that the mean-square error (MSE) of Lema and Mitchell's absolute moment block truncation coding (AMBTC) is always bounded below (i.e., less than or equal to) that of BTC. Therefore, with additional advantages in computation and implementation, AMBTC is always superior. Furthermore, we developed a new adaptive equal sign position optimization (ESPO) algorithm for optimum pixel classification. Our quantization error analysis shows that incorporating the ESPO algorithm into conventional AMBTC or BTC achieves minimum MSE in either case.