The viterbi optimal runlength-constrained approximation nonlinear filter

Nicholas D. Sidiropoulos

Research output: Contribution to journalArticlepeer-review

8 Scopus citations


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 dn(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.

Original languageEnglish (US)
Pages (from-to)586-598
Number of pages13
JournalIEEE Transactions on Signal Processing
Issue number3
StatePublished - 1996
Externally publishedYes

Bibliographical note

Funding Information:
Manuscnpt received April 10, 1995, revised September 1, 1995. Thls work was supported in part by core funds from the NSF ERC program, made


Dive into the research topics of 'The viterbi optimal runlength-constrained approximation nonlinear filter'. Together they form a unique fingerprint.

Cite this