Row-Centric Lossless Compression of Markov Images
Matthew G. Reyes David L. Neuhoff
















 x  
X
Δ=
𝒳

theoremTheorem[section]
lemma[theorem]Lemma
proposition[theorem]Proposition
corollary[theorem]Corollary
conjecture[theorem]Conjecture

proof[1][Proof]

  #1




































Row-Centric Lossless Compression of Markov Images


    



    Matthew G. Reyes and David L. Neuhoff    

     EECS Department, University of Michigan     



    <mgreyes@umich.edu> and <neuhoff@umich.edu>    




    December 30, 2023
===================================================================================================================================================================

empty






	Motivated by the question of whether the recently introduced Reduced Cutset Coding (RCC) <cit.> offers rate-complexity performance benefits over conventional context-based conditional coding for sources with two-dimensional Markov structure, this paper compares several row-centric coding strategies that vary in the amount of conditioning as well as whether a model or an empirical table is used in the encoding of blocks of rows. The conclusion is that, at least for sources exhibiting low-order correlations, 1-sided model-based conditional coding is superior to the method of RCC for a given constraint on complexity, and conventional context-based conditional coding is nearly as good as the 1-sided model-based coding.







§ INTRODUCTION




Lossless coding of an image involves blocking (equivalently, grouping) and ordering the pixels in some way, and feeding them, together with a corresponding set of coding distributions, to an encoder, which without loss of optimality we can assume to be an Arithmetic Encoder.  
The coding distribution for a given pixel, or block of such, is conditioned on some subset of the 
pixels, referred to as its context, that have already been encoded.

This paper considers how various coding strategies effect coding rate
and complexity. Strategies considered include different ways of blocking and ordering pixels, different contexts,  and two different ways of producing coding distributions:   model-based and  empirical, i.e., parametric and nonparametric.




For simplicity we focus on bilevel images. To provide a well-founded testing ground with interesting
correlation structure, we focus on images produced by a simple, uniform, Ising Markov
Random Field (MRF) model <cit.>,
with each pixel having four neighbors (N, E, S, W), and positive, 
row-stationary edge correlations. MRF models have seen widespread application in image processing, 
in large part due to the reasonable assumption that pixels in an image are dependent 
on some small surrounding region rather than on pixels from the entire rest of the image.  In particular, the Ising model has been proposed as a model for bilevel images <cit.> called scenic, which are complex bilevel images, such as landscapes and portraits, having numerous black and white regions with smooth or piecewise smooth boundaries between them.

The model-based coding distributions are based explicitly on this model.
The empirical methods simply use tables of conditional frequencies.




We focus on what we call row-centric schemes,

which are schemes in which rows are grouped into blocks and within each block, columns are sequentially encoded from left to right.

These include both the recently introduced Reduced Cutset Coding (RCC)
<cit.>, as well as conventional context-based
conditional coding, such as in
<cit.>.
It excludes coding techniques such as when image pixels are coded in Hilbert
scan order <cit.>.

 
By the Markov property, no coding scheme could attain lower
rate than the scheme that encodes each row with coding distribution equal to the row's 
conditional distribution given the previous row as context, which has rate equal to
the entropy-rate H_∞ = 1  W H(𝐗_r_1 | 𝐗_r_0), where W is the width of the image, and 𝐗_r_0 and 𝐗_r_1 denote successive rows. An equivalent row-centric scheme will sequentially encode each pixel in a given row with context equal to the pixel to the left, the one above, and all pixels to the right of the one above.  
While it is easy to say this is optimal,
it is computationally infeasible to attain this rate exactly. 
On the one hand, with model-based coding distributions, due to need for marginalizing over
the pixels below the block, the conditional distribution of one pixel
given the aforementioned context is exorbitantly complex to compute in real time, and
exorbitantly expensive to store even if it were computed in advance.
On the other hand, with 
empirical-distribution-based coding, the distribution is again exorbitantly expensive to store.
Thus, the real question is how to approach rate H_∞ with computationally 
efficient coding techniques. 
With this in mind, this paper explores the merits of several row-centric strategies – some using model-based coding distributions and some using empirically-based distributions.  From now on, 
we call these model-based and empirically-based schemes, respectively.




 §.§ Model-based


Let G = (V,E) denote a grid-graph underlying the MRF.   
For the given Ising model, one can encode an N_b × W block 𝐗_b
consisting of N_b rows with complexity per pixel that increases exponentially with N_b 
and with storage that increases exponentially with N_b and linearly with W.  
This is done by lumping the i-th column _b,i into one super-pixel, and computing the coding distribution of each column in turn using Belief Propagation on the resulting line graph.  This is feasible for moderate N_b, e.g., 10 or so, and as described below, such coding distributions can be computed with conditioning/context from the row above, the row below, both the row above and row below, or from neither, without any appreciable increase in complexity.

If the coding distributions within a block are conditioned on just the row above, then to avoid an exorbitantly complex marginalization, all edges running South from the block must be cut.  This means that the computed coding distribution p_C( 𝐱_b,i ) will not be
the true conditional distribution for the i-th column – the result being that the overall coding rate will be larger than H_∞ due to the divergences between the true and computed conditional distributions for the columns. Similarly, if the coding distributions within a block are computed without conditioning on either the row above or the row below, then all edges running both South and North from the block must be cut. This again means that the computed coding distributions p_C(𝐱_b,i ) will not be the true distributions for the columns – the result being that the overall coding rate will exceed H_∞ due both to the divergences between true and computed distributions for the columns, and the blocks being encoded independently of one another. We refer to these methods as 1-sided and 0-sided model-based coding, respectively. In each of these, the excess rate, i.e., redundancy, decreases as N_b increases, and for each of these, the divergence can be minimized by choosing an appropriate moment-matching correlation for the truncated model.

Two-sided model-based coding of a block of rows is also possible, but unlike 0- and 1-sided coding, this cannot be applied to the entire image.  For example in RCC, blocks are alternately 0-sided coded and 2-sided coded.  On the one hand, the blocks that are 0-sided coded suffer the sources of redundancy mentioned previously.  On other hand, the blocks that are 2-sided coded are coded precisely at rate 1  W N_b H(𝐗_b | 𝐗_S, 𝐗_N), where X_S and X_N denote the rows just North and just South of X_b, respectively. While this was called RCC in <cit.>, here we refer to it as 0/2-sided coding.




 §.§ Empirically-based


With empirically-based coding, there could again be 0-, 1- or 2-sided coding.
However, in this paper we only consider 1-sided coding, where the
pixels in a row are sequentially coded from left to right with context consisting
of the pixel to the left and some number of pixels in the row above, beginning
with the pixel directly above and extending some number of pixels to the right.
(This is conventional context-based coding.)
While H_∞ could be attained if all pixels to the right of the current pixel
in the row above were in  the context,  
the storage required for the empirical coding distribution increases exponentially
with the size of the context, so the size of the context must be limited to a moderate amount, for example 10.
And assuming a sufficient amount of training data that the empirical conditional distributions are
very close to the true conditional distributions, the resulting redundancy is the 
average of the divergences of the true conditional distribution of a pixel given
all values on the previous and the true conditional distribution given the moderately sized context.





 §.§ Summary of main results


In regard to trying to attain H_∞ with 1-sided row-centric coding, we note that empirically-based coding uses a true distribution with a truncated context, whereas model-based coding uses an approximate distribution with full context. Moreover, 1-sided model-based coding uses an approximate distribution on all blocks, while the 0/2-sided coding of RCC uses a more severe approximation on half the blocks and an optimal distribution on the other half. Consequently, we are interested in the relative performances of these three approaches in achieving rate as close to H_∞ as possible.

In this paper, we first compare 0/2-sided model-based coding with 1-sided model-based coding, and then 1-sided model-based coding with 1-sided empirical-based coding. 1-sided model-based coding has rate decreasing monotonically with N_b. For a given complexity, i.e.,  N_b, 1-sided model-based coding outperforms 0/2-sided model-based coding. Moreover, 1-sided model-based coding outperforms 1-sided empirical-based coding, though not by much. In summary, at least for Markov models exhibiting low-order correlations, there are both model-based and empirically-based 1-sided schemes with good performance and low complexity. 

The remainder of the paper is organized as follows. In Section <ref> we cover background on the Ising model, Arithmetic Encoding, model- and empirical-based coding distributions and Reduced Cutset Coding. In Section <ref>, we discuss 0-, 1-, and 2-sided coding, and in Section <ref> we discuss numerical results. 





§ BACKGROUND




In this section we introduce notation and background concepts and results.





 §.§ MRF Source Model


The specific information source that we consider in the present paper is a uniform Ising model on a square grid graph G=(V,E), whose nodes V are the sites of an M× W rectangular lattice and whose edges E are pairs of horizontally and vertically adjacent nodes. The random variable X_i associated with each node i assumes values in the alphabet ={-1,1} and a configuration = (x_i:i∈ V) has probability

    p(;θ)
        =    exp{ θ∑_{i,j}∈ Ex_ix_j - Φ(θ)},

where  Φ(θ) is the log-partition function and θ > 0 is the positive edge correlation parameter of the model.

 
 


 §.§ Row-Centric Arithmetic Coding


As mentioned in the introduction, in row-centric coding, rows are grouped into N_b× W blocks and then within a block _b, columns of pixels are encoded from left to right. Let r_1 and r_N_b denote the first and last rows, respectively, of a block. Similarly, let r_0 and r_N_b+1 indicate, respectively, the row preceding and row succeeding the block.   

When coding column configuration _b,i, a coding distribution 

is passed, together with the configuration _b,i, 

to an Arithmetic Encoder. In 0-sided coding p_C(_b,i) is conditioned only on _b,i-1, the configuration of the the i-1-st column of the block. In 1-sided model-based coding, p_C(_b,i) is conditioned on _b,i-1 and _r_0,i:W, the i-th through final pixels of the previous row. In 1-sided empirical-based coding, p_C(_b,i) is conditioned on _b,i-1 and _r_0,i:i+c-2, the i-th through i+c-2-th pixels of the previous row, where c is the size of the context. In 2-sided model-based coding, p_C(_b,i) is conditioned on _b,i-1, _r_0,i:W, and _r_b+1,i:W, the i-th through final pixels of the next row. The contexts for these schemes can be visualized with Figure <ref>.

The approximate number of bits produced by the AC encoder when encoding the i-th column is
-log p_C(_b_i). The rate R_b,i of encoding the i-th column of block b is the expected number of bits produced, divided by N_b. If the p(_b_i) is the true (conditional) distribution of column i given the context, then the rate of encoding the i-th column is

    R_b,i = 1/N_b[ H(_b,i | C_b,i) + D( p(_b,i) || p_C(_b,i)) ].

where D denote divergence. From this, the rate of encoding block b is 

    R_b = 1/W N_b[ H(_b | C_b) + D],

where D is the sum of the per-column divergences.










 §.§ Model and empirical based coding distributions


For model-based methods, the coding distribution is computed by running BP on the Ising model restricted to the subgraph induced by the block of rows, with a possibly modified correlation parameter. In the 0- and 1-sided cases, the edge correlation parameter is adjusted to account for the truncated edges (on both sides of the block or below the block, respectively). In the case of 1- and 2-sided coding, in which conditioning on either the upper or both the upper and lower boundaries is part of the coding distribution, this conditioning is incorporated by introducing self correlation on the bottom and top rows of the block that bias those sites toward the value of their boundary neighbor. 

Let θ^*_0,N_b and θ^*_1,N_b denote the parameters used for encoding a block with 0-, respectively, 1-sided coding. For 2-sided, the block is encoded using the original parameter θ, and the model becomes




p(_b | _r_0,_r_b+1;θ^*_2,N_b) =





    exp{ θ^*_2,N_b∑_{i,j}∈ E_b x_ix_j + θ^*_2,N_b∑_{i}∈ r_1∪ r_b s_ix_i - Φ(θ^*_2,N_b)},


where E_b is the set of edges both of whose endpoints are in b, and s_i is the self-correlation on pixel i corresponding to the value of its neighbor on the boundary of b.

For 1-sided coding, the model is




p(_b | _r_0;θ^*_1,N_b) =





    exp{ θ^*_1,N_b∑_{i,j}∈ E_b x_ix_j + θ^*_1,N_b∑_i∈ r_1  s_ix_i - Φ(θ^*_1,N_b)}



For 0-sided coding, the model is


    p(_b;θ^*_0,N_b)
        =    exp{ θ^*_0,N_b∑_{i,j}∈ E_b x_ix_j - Φ(θ^*_0,N_b)},


In each of these cases, the coding distribution p(_b,i) for the i-th column within the block is computed using Belief Propagation <cit.>. 
Messages are first passed from right to left on the resulting line-graph of superpixels (columns) in such a way that after the messages are received at the first column, encoding can proceed from left to right with the coding distributions being computed as they are needed. 


The (column) coding distributions for 0-, 1-, and 2-sided model-based coding are denoted p(_b,i | _b,i-1; θ^*_0 ), p(_b,i | _b,i-1, _r_0,i:W ; θ^*_1), and p(_b,i | _b,i-1, _r_0,i:W, _r_b+1,i:W ; θ^*_2), respectively.















Empirical coding distributions are based on a table of the frequencies of different configurations of a column for all possible configurations of the context. Letting _T denote the configuration being encoded and _C denote the configuration of the context, the table consists of values of the form p^*(_T , _C), from which the coding distribution p^*(_b,i | _b,i-1, _r_0,i:i+c-2) can be computed, where c is the size of the context.





There are 1-pass and 2-pass methods. In this paper we consider only the 2-pass method in which the relevant frequencies are collected from a set of training images, and then, in a second pass, the rows of the image are encoded using the collected frequencies as coding distributions. 




 §.§ Reduced Cutset Coding <cit.>

In the Reduced Cutset Coding (RCC) method introduced in <cit.> and further analyzed in <cit.>, an image is divided into alternating blocks of rows _L and _S of sizes N_L × W and N_S × W, called lines and strips, respectively. Lines are encoded first in a 0-sided manner, i.e., with no conditioning. The parameter θ^*_0,N_L used for the coding distributions of columns is chosen to be the one that minimizes divergence with the true distribution of lines. It is referred to as the moment-matching correlation parameter. The coding rate for lines is

    R^L_N_L    =    1/W N_L[ H(_L ; θ^*_0,N_L + D) ],

where D is the divergence between p(_b;θ) and p(_b;θ^*_0,N_L).

Strips are subsequently encoded in a 2-sided manner, i.e., conditioned on the immediately preceding and immediately succeeding rows. The coding rate for a strip is

    R^S_N_S    =    1/W N_SH(_S|_r_0, _r_N_b+1;θ^*_2,N_S).


For a large image, the overall rate of RCC is then

    R_N_S,N_L   ≈   N_S/N_S + N_LR^S_N_S + N_L/N_S + N_LR^L_N_L
       ≈    H_∞
           + N_L/N_L + N_SD + N_S/N_L + N_SI(_r_0 ; _r_N_L+1)

where D is the divergence between p(_b;θ) and p(_b;θ^*_0,N_L), and I(_r_0 ; _r_N_L+1) is the information between the row immediately preceding and the row immediately following a strip.

 

























§ ROW-CENTRIC CODING REDUNDANCY


In this section we return to the question posed in Section <ref>, that of attaining rate as close as possible to the entropy rate H_∞ = H(_r_1 | _r_0), and discuss the redundancies associated with the different coding strategies considered in this paper. While we cannot analytically evaluate the rate of decrease of the redundancies, by performing numerical experiments as in the next section, we can gain a sense of the relative rates of decrease.

We let R^0E_N_b and R^0M_N_b denote the rate for coding N_b rows with 0-sided empirical- and model-based coding, respectively. Likewise for R^1E_N_b, R^1M_N_b, and R^2M_N_b. We focus here on the coding of a single row, i.e., N_b = 1. Moreover, let I(_r_1 ; _r_0) be the mutual information between rows 0 and 1. Some of the results in this section make use of Lemma <ref> in Section <ref>.







The rate for encoding a row with 0-sided model-based coding is 


    R^0M_1 = H_∞ + 1/W [ D^0M_1 + I(_r_1 ; _r_0) ]


where D^0M_1 is the sum of divergences between p(_b,i | _b,i-1; θ ) and p(_b,i | _b,i-1; θ^*_0 ) over all columns. 







	
	
    R^0M_1     =    1/W[ H(X_b) + D(X_b || X̃_b) ] 
        =    1/W[ H(X_b | X_r_0) + I(X_r_1 ; X_r_0) + D(X_b || X̃_b) ] 
        =     H_∞ + 1/W[ I(X_r_1 ; X_r_0) + D(X_b || X̃_b) ],

	which shows the proposition. 









The rate for coding a row with 0-sided empirical-based coding is 


    R^0E_1 = H_∞ + 1/W [ I(_r_1 ; _r_0) ].








	
    R^0E_1     =    1/W H(_b) 
        =    1/W[ H(_b | _r_0) + I(_r_1 ; _r_0)] 
        =     H_∞ + 1/W I(_r_1 ; _r_0),

	which shows the proposition. 





Note that both 0-sided methods suffer the information penalty for independently encoding rows of the image. However, we do not include a divergence term in R^0E_1 because given enough training data, the empirical coding distribution p^*(_b,i | _b,i-1) for the i-th column will well-approximate the true distribution p(_b,i | _b,i-1; θ ). Thus one could estimate D̅^0M_N_b by encoding the source with both 0-sided model-based coding and 0-sided empirical-based coding and forming the estimate R^0M_N_b - R^0E_N_b.







The rate for coding a row with 2-sided model-based coding is


    R^2M_1     =     H_∞ - 1/WI(_r_1 ; _r_2 | _r_0) 
        <     H_∞,








	
    R^2M_1     =    1/WH(_b | _r_0,_r_2) 
        =    1/W[ H(_b | _r_0) - I(_b ; _r_w | _r_0) ] 
        =     H_∞ + 1/WI(_r_1 ; _r_2 | _r_0)




This, of course, is not an actual coding rate, but it can be shown that when combined with R^0M_1 gives the performance of RCC with N_L = N_S = 1.





	Encoding every other row with 0-sided model-based coding and 2-sided model-based coding gives rate
	
    1/2[ R^0M_1 + R^2M_1 ]     =     H_∞ + 1/2 WD̅^0M_1 + 1/2 W I(_r_2 ;_r_0)




	
    1/2[ R^0M_1 + R^2M_1 ]     =    1/2 H_∞ + 1/2 W[ I(_r_1 ; _r_0) + D(_b || _b) ] + 1/2[ H_∞ - 1/WI(_r_1 ; _r_2 | _r_0) ] 
        =     H_∞ + 1/2 WD̅^0M_1 + 1/2 W[ I(_r_1 ; _r_0) - I(_r_1;_r_2 | _r_0) ].

	
	Therefore, to show the proposition we need to show that I(_r_1 ; _r_0) - I(_r_1;_r_2 | _r_0) = I(_r_2 ; _r_0). To do this, we note that under a row stationary Markov model such as the one considered in this paper, we have
	
	
    I(_r_1 ; _r_0) - I(_r_1;_r_2 | _r_0)     =     H(_r_1) - H(_r_1 | _r_0) - H(_r_2 | _r_0) + H(_r_2 | _r_0, _r_1) 
        =     H(_r_1) - H(_r_1 | _r_0) - H(_r_2 | _r_0) + H(_r_2 | _r_1) 
        =     H(_r_2) - H(_r_2 | _r_1) - H(_r_2 | _r_0) + H(_r_2 | _r_1) 
        =     H(_r_2) - H(_r_2 | _r_0) 
        =     I(_r_2 ; _r_0)

	where (<ref>) is from the Markov property and (<ref>) is from row stationarity. This completes the proof. 


By estimating D̅^0M_N_b using the rates R^0M_N_b and R^0E_N_b from 0-sided model-based and 0-sided empirical-based coding, we can then subtract this from the rate of RCC and obtain an estimate of the shape of I(_r_0 ; _r_N_b + 1).


Using the above notation, we can restate Proposition 3.1 of <cit.>, for all N_0 and N_2, as




RCC

    R^0M_N_0+1 < R^0M_N_0,        R^2M_N_2+1 > R^2M_N_2,        R^0M_N_0 > R^2M_N_2.







	The proofs can be found in <cit.>.





We now consider rates of 1-sided coding.







The rate for encoding a row with 1-sided model-based coding is


    R^1M_1 = H_∞ + 1/WD^1M_1


where D^1M_1 is the sum of divergences between p(_b,i | _b,i-1, _r_0,i:W ; θ) and p(_b,i | _b,i-1, _r_0,i:W ; θ^*_1) over all columns. 







	
    R^1M_1     =    1/W[ H(X_r_1 | X_r_0) + D( X_r_1 | X_r_0 || X̃_r_1 | X_r_0) ],

	where D( X_r_1 | X_r_0 || X̃_r_1 | X_r_0) is the divergence between the true conditional distribution of a row conditioned on the previous row and the conditional distribution of a row conditioned on the previous row using the 1-sided model, which can be expressed as the sum of divergences between p(_b,i | _b,i-1, _r_0,i:W ; θ) and p(_b,i | _b,i-1, _r_0,i:W ; θ^*_1). This shows the proposition. 


Similarly, the rate of encoding a row with 1-sided empirical-based coding is







	
The rate for encoding a row with 1-sided empirical-based coding is


    R^1E_1 = H_∞ + 1/WD^1E_1


where D^1E_1 is the sum of divergences between p(_b,i | _b,i-1, _r_0,i:W ; θ) and p^*(_b,i | _b,i-1, _r_0,i:i+c-2) over all columns. 







	
    R^1M_1     =    1/W[ H(X_r_1 | X_r_0) + D( X_r_1 | X_r_0 || X̃_r_1 | X_r_0) ],

	where D( X_r_1 | X_r_0 || X̃_r_1 | X_r_0) is the divergence between the true conditional distribution of a row conditioned on the previous row and the conditional distribution of a row conditioned on the previous row using the 1-sided empirical distributions, which can be expressed as the sum of divergences between p(_b,i | _b,i-1, _r_0,i:W ; θ) and p^*(_b,i | _b,i-1, _r_0,i:i+c-2). This shows the proposition. 





Note that the two 1-sided coding scemes do not suffer an explicit information penalty because there is conditioning on the previous row. On the other hand, if the context size c could be chosen as c = W + 2 - i for each column i, then the divergence term D^1E_1 would vanish. Thus D^1E_1 is really a sum of conditional information terms. However, both D^1M_1 and D^1E_1 are less than D^0M_1, so it is of interest how these smaller divergences on all blocks compare with the 0/2-sided scheme of RCC in which half the blocks have a larger divergence, plus an information penalty, while the other half actually receive a coding rate reduction.

















Analogous to the results of <cit.>, 1-sided model-based coding can be shown to have the following properties.








	For all N_b and N_2,
	
    R^1M_N_b+1 < R^1M_N_b       R^1M_N_b < R^0M_N_b       R^1M_N_b > R^2M_N_2
	
























 
 






























§ NUMERICAL RESULTS AND COMPARISONS


Using Gibbs sampling, we generated configurations ^(1),…,^(17) of a 200× 200 modeled by an Ising MRF with θ = .4. On this dataset we tested three strategies: 0/2-sided model-based coding, 1-sided model-based coding, and 1-sided empirical-based coding. The estimates θ^*_0,n, θ^*_1,n, and θ^*_2,n were found as in <cit.> and are shown in Figure <ref>. 

Figures <ref> and <ref> show the rates attained by the various row-centric coding schemes considered in this paper, as a function of block size parameter n. These rates  were computed  by averaging the negative logarithm of the coding distributions evaluated at the actual pixel/super-pixel values. In <cit.> we observed that for a given complexity, i.e., given the maximum of N_L and N_S, the best performance of 0/2-sided coding was found when lines and strips have the same size, i.e., N_L = N_S = N_b. Thus in the model-based comparison, our 0/2-sided method uses lines and strips of equal height. 

















As predicted by Proposition <ref>, Figure <ref> shows that R^1M_N_b is decreasing in N_b, R^1M_N_b < R^0M_N_b and R^1M_N_b > R^2M_N'_b for all N_b and N'_b. Also in Figure <ref>, we observe that for a given block size N_b, 1-sided model-based coding achieves lower rate than 0/2-sided model-based coding. Indeed, 1-sided model-based coding with N_b=1 nearly as good as 0/2-sided coding with N_b=7. Moreover, using the 2-sided coding rate as a lower bound for H_∞, we can say that with N_b = 3, 1-sided model-based coding comes to within 3.5% of H_∞.













Figure <ref> shows the rate of 1-sided model-based coding with N_b = 1, and 1-sided empirical-based coding for varying sizes of context. Note that context size c = 1 actually corresponds to 0-sided empirical-based coding, since in this scheme, only the pixel to the left is used as context. We observe that 1-sided model-based coding with N_b=1 achieves lower rate than 1-sided empirically-based coding with all context sizes we considered. The difference between the rates of 1-sided model-based and 1-sided empirical-based coding shrinks with context size and when the context size is 5, the difference is about .0025 bpp or .4%. Improvements after that are very slow. Again using the rate of 2-sided model-based coding as a lower bound for H_∞, we observe that 1-sided empirically-based coding with context size 5 comes with 4% of entropy-rate.













Another interesting observation is made by recalling from the previous section that while both 0-sided model-based and 0-sided empirical-based coding methods suffer an information penalty, the model-based scheme suffers an additional divergence penalty D^0M_N_b. Therefore, by comparing the n=1 point on the 0-sided rate curve of Figure <ref> with the c=1 point on the empirical-based rate curve of Figure <ref>, we can estimate that the normalized divergence between p(_b;θ) and p(_b;θ^*_0) for a single row is about .1 bits per pixel. Moreover, by again using the 2-sided model-based rate curve as a lower bound for H_∞, we can bound the normalized information I(_2 ; _1) between successive rows by .041 bits per pixel.





§ CONCLUDING REMARKS


In this paper we posed the problem of considering different approaches to what are called row-centric coding. We presented the problem in the context of a standard MRF image model in order to provide a well-founded testing ground in which model-based and empirical-based approaches can be compared, and moreover, 1-sided coding can be compared to the tradeoffs in 0/2-sided coding.




















§ APPENDIX



	For random variables _1,…,_N, N≥ 2, let p_i|C_i be the probability of _i given _C_i, where C_i⊂{1,…,i-1} is the context for _i and let q_i|C̅_i be the coding distribution for _i, where C̅_i⊂{1,…,i-1} is the context for _i under the q distribution. Then,
	
    D(∏_i^N p_i|C_i || ∏_i q_i|C̅_i)     =    ∑_i=1^N ∑__C_i∪C̅_ip_C_i D( p_i|C_i || q_i| C̅_i )







	First consider the case where C_i = C̅_i = {1,…,i-1}. We will prove it by induction. Letting N=2 we have that
	
    D( p_1p_1|2 || q_1q_1|2)     =    ∑__1 _2 p_1p_2|1logp_1 p_2|1/q_1 q_2|1
        =    ∑__1, _2 p_1 p_2|C_2[ logp_1/q_1 + logp_2|C_2/q_2|C̅_2] 
        =    ∑__1, _2 p_1 p_2|C_2logp_1/q_1 + ∑__1, _2 p_1 p_2|C_2logp_2|C_2/q_2|C_2
        =    ∑__1 p_1 logp_1/q_1∑__2 p_2|C_2 + ∑__1 p_1 ∑__2 p_2|C_2logp_2|C_2/q_2|C̅_2
        =    ∑__1 p_1 logp_1/q_1 + ∑__1 p_1 ∑__2 p_2|C_2logp_2|C_2/q_2|C̅_2
        =    ∑_i=1^2 ∑__1,…,_i-1 p_1,…,i-1∑__i p_i | C_ilogp_i | C_i/q_i | C̅_i
        =    ∑_i=1^2 ∑__1,…,_i-1 p_1,…,i-1∑__i D( p_i | C_i || q_i | C̅_i),

	which shows that the lemma holds for some N = k≥ 2. Now letting N = k+1, we see that
	
    D(∏_i^k+1 p_i|C_i || ∏_i q_i|C̅_i)     =    ∑__1,…,_k,_k+1∏_i=1^kp_i | C_i p_k+1 | C_k+1log∏_i=1^k p_i | C_i p_k+1 | C_k+1/∏_i=1^k q_i | C̅_i q_k+1 | C_k+1
        =    ∑__1,…,_k∏_i=1^k p_i | C_ilog∏_i=1^k p_i | C_i/∏_i=1^k q_i | C̅_i
           + ∑__1,…,_k∏_i=1^k p_i | C_i∑__k+1 p_k+1 | C_k+1logp_k+1 | C_k+1/q_k+1 | C̅_k+1
        =    ∑__1,…,_k∏_i=1^k p_i | C_ilog∏_i=1^k p_i | C_i/∏_i=1^k q_i | C̅_i
           + ∑__1,…,_k∏_i=1^k p_i | C_i D(p_k+1 | C_k+1 || q_k+1 | C̅_k+1) 
        =    ∑_i=1^k ∑__C_i∪C̅_ip_C_i D( p_i|C_i || q_i| C̅_i ) 
           + ∑__1,…,_k∏_i=1^k p_i | C_i D(p_k+1 | C_k+1 || q_k+1 | C̅_k+1) 
        =    ∑_i=1^k+1∑__C_i∪C̅_ip_C_i D( p_i|C_i || q_i| C̅_i )


 



§ REFERENCES


1



























reyes2010
M.G. Reyes and D.L. Neuhoff, “Lossless Reduced Cutset Coding of Markov Random Fields", DCC, Snowbird, UT, 2010.

reyes2016a
M. G. Reyes and D. L. Neuhoff, “Cutset Width and Spacing for Reduced Cutset Coding of Markov Random Fields," ISIT 2016, July 2016.

baxter
R.J. Baxter, Exactly Solved Models in Statistical Mechanics,
New York: Academic, 1982.

reyes2014
M. G. Reyes, D. L. Neuhoff, T. N. Pappas, “Lossy
Cutset Coding of Bilevel Images Based on Markov Random Fields," IEEE Trans. Img. Proc., vol. 23, pp. 1652-1665, April 2014.

JBIG 
“Progressive bi-level image compression,” ISO/IEC
Int. Std. 11544, 1993. 

MemonW:97
N. Memon and X. Wu, “Recent developments in
context-based predictive techniques
for lossless image compression," 
The Computer J., vol. 40, no. 2, pp. 127-136, 1997.

MemonNS:2000
N. Memon, D.L. Neuhoff, and S. Shende, “An analysis of some common scanning techniques for lossless image coding," IEEE Trans. Image Proc., vol. 9, no. 11, pp. 1837-1848, 2000.

























LempelZiv:1986
A. Lempel and J. Ziv, “Compression of two-dimensional data,” IEEE
	Trans. Inform. Theory, vol. IT-32, no. 1, pp. 1–8, 1986.


reyes2016b
M. G. Reyes and D. L. Neuhoff, “Cutset Width and Spacing for Reduced Cutset Coding of Markov Random Fields," available online at http://arxiv.org/abs/1602.04835.























