The viterbi optimal runlength-constrained approximation nonlinear filter

Simple nonlinear filters are often used to enforce "hard" syntactic constraints while remaining close to the observation data, e.g., in the binary case, it is common practice to employ iterations of a suitable median, or a one-pass recursive median, openclose, or closopen filter to impose a minimum symbol run-length constraint while remaining "faithful" to the observation. Unfortunately, these filters are - in general - suboptimal. Motivated by this observation, we pose the following optimization: Given a finite-alphabet sequence of finite extent y = {y(n)}_n=0 ^N-1, find a sequence x̂ = {x̂(n)}_n=0 ^N-1 that minimizes d(x, y) = ∑_n=0 ^N-1 d_n(y(n), x(n)) subject to the following: x is piecewise constant of plateau run-length ≥M. We show how a suitable reformulation of the problem naturally leads to a simple and efficient Viterbi-type optimal algorithmic solution. We call the resulting nonlinear input-output operator the Viterbi optimal runlength-constrained approximation (VORCA) filter. The method can be easily generalized to handle a variety of local syntactic constraints. The VORCA is optimal, computationally efficient, and possesses several desirable properties (e.g., idempotence); we therefore propose it as an attractive alternative to standard median, stack, and morphological filtering. We also discuss some applications.