A switching algorithm for design of optimal increasing binary filters overlarge windows

All known approaches for the design of increasing translation-invariant bin ary window filters involve combinatoric searches. This paper proposes a new switching algorithm having the advantage that the search is over a smaller set than other algorithms. Beginning with an estimate from image realizati ons of the optimal generic (nonincreasing) window function, the algorithm s witches (exchanges) a set of observation vectors (templates) between the op timal function's kernel and the kernel's complement. There are many such "s witching sets" that provide a kernel defining an increasing filter. The opt imal increasing filter is the one corresponding to the switching set that p roduces the minimal increase in error over the optimal generic filter. The core of the search problem is the inversion set of the optimal filter. The inversion set is composed of all vectors in the kernel lying beneath a nonk ernel vector in the lattice of observation vectors and all nonkernel vector s lying above a kernel vector. The new algorithm, which is based on an erro r-related greedy property, recursively eliminates the inversion set until t he optimal increasing filter is obtained. For purposes of computational eff iciency, the actual implementation may be based on a relaxation of the orig inal construction, so that the result may be based on a relaxation of the o riginal construction, so that the result may be suboptimal. For the various models tested, the relaxed algorithm has proven to be optimal or very clos e to optimal. Besides its good estimation precision, the new algorithm has three noteworthy properties: first, it is applicable to relatively large wi ndows; second, it operates directly on the input data via estimates of the determining conditional probabilities; and third, the degree of relaxation serves as an input parameter to the algorithm, so that computation time can be bounded for large windows and the algorithm can run to full optimality for small windows. (C) 2000 Pattern Recognition Society. Published by Elsev ier Science Ltd. All rights reserved.