Cutset width and spacing for Reduced Cutset Coding of Markov random fields
This paper analyzes the rate, redundancy and complexity of a generalized version of Reduced Cutset Coding (RCC) [4] in which cutset lines can consist of more than one image row. We show that increasing the thickness of the lines reduces coding rate for the cutset, increasing the spacing of the lines increases the coding rate of the non-cutset pixels, though the coding rate of the latter is always strictly less than that of the former. We show that the redundancy of RCC can be decomposed into two terms, a correlation redundancy due to coding the components of the cutset independently, and a distribution redundancy due to coding the cutset as a reduced Ising model [3]. We show that the correlation redundancy decreases with increasing spacing of the lines, and that the parameter of the reduced Ising model approaches the true parameter monotonically in the thickness of the lines. We present a learning phase in which the true parameter of the model is learned as well as the parameter of the reduced model. Numerical simulations show that only small improvements in rate-complexity performance are possible by increasing line widths, though rates within 3 to 4 percent of the entropy rate can be achieved with only 20 to 50 operations per pixel through combinations of line thickness and spacing.