An iterative hillclimbing algorithm for discrete optimization onimages: application to joint encoding of image transform coefficients

摘要

We develop an iterative, hillclimbing-based assignment algorithmnfor the approximate solution of discrete-parameter cost minimizationnproblems defined on the pixel sites of an image. While the method isnapplicable to a number of problems including encoding, decoding, andnsegmentation, this article focuses on entropy-constrained encoding. Forntypical statistical image models, the globally optimal solution requiresnan intractable exhaustive search, while standard greedy methods, thoughntractable in computation, may be quite suboptimal. Alternatively, ournmethod is guaranteed to perform no worse (and typically performsnsignificantly better) than greedy encoding, yet with manageablenincreases in complexity. The new approach uses dynamic programming as anlocal optimization "step," repeatedly applied to the rows (or columns)nof the image, until convergence. For a DCT framework, withnentropy-constrained TCQ applied to the coefficient sources, the newnmethod gains as much as 0.8 dB over standard greedy encoding