Direct binary search (DBS) algorithm with constraints

Abstract

In this paper, we describe adding constraints to the Direct Binary Search (DBS) algorithm. An example of a useful constraint, illustrated in this paper, is having only one dot per column and row. DBS with such constraints requires greater than two toggles during each trial operation. Implementations of the DBS algorithm traditionally limit operations to either one toggle or swap during each trial. The example case in this paper produces a wrap-around pattern with uniformly distributed ON pixels which will have a pleasing appearance with precisely one ON pixel per each column and row. The algorithm starts with an initial continuous tone image and an initial pattern having only one ON pixel per column and row. The auto correlation function of Human Visual System (HVS) model is determined along with an initial perceived error. Multiple operation pixel error processing during each iteration is used to enforce the one ON pixel per column and row constraint. The constraint of a single ON pixel per column and row is used as an example in this paper. Further modification of the DBS algorithm for other constraints is possible, based on the details given in the paper. A mathematical framework to extend the algorithm to the more general case of Direct Multi-bit Search (DMS) is presented. © 2013 SPIE.