Journal of Information Science and Engineering, Vol. 38 No. 4, pp. 735-748

Efficient Provably Algorithms for Boundary Bin-Pair Selection Problem

Given a non-negative vector, a boundary bin pair for this vector consists of two different vector entry indices and the boundary bin pair determines a set of bins whose indices are between the boundary bin indices. The sum of these bins is called the bounded area for this given non-negative vector. The boundary bin-pair selection problem (BBPS problem) is an optimization problem in which, *n* non-negative vectors (called histogram vectors) of length *m* and a capacity value *T* are given, the goal is to determine n bin pairs for these *n* histogram vectors such that the sum of corresponding *n* bounded areas is maximized under the constraint that the sum of 2*n* boundary bins is greater than or equal to *T*. The BBPS problem is shown to be equivalent to the modified multiple-histogram-modification problem which is a well-known research topic in reversible data hiding. A brute-force way to solve the BBPS problem requires exponential time. In this paper, we construct several efficient provably algorithms toward solving the BBPS problem. Our proposed algorithms are constructed in a dynamic-programming way. These proposed algorithms achieves the same time complexity *O*(*nm*^{2}*T*). In order to compare their efficiency, we generate experimental data by constructing histogram vectors from the prediction errors of some test images. Experimental results give a clear performance comparison between our proposed algorithms for the BBPS problem.

Keywords:
boundary bin-pair selection, histogram vectors, optimization, dynamic programming, multiple histogram modification