The Viterbi Optimal Runlength-Constrained Approximation Nonlinear Filter

Abstract

Simple nonlinear filters are often used to enforce ﲨard 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, find another sequence which is piecewise constant of plateau run- length greater than or equal to M, and is closest to the original sequence, in the sense of minimizing a per-letter decomposable distortion measure. 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 and morphological filtering. We also discuss some potential applications.