[ 1 ] [ 2 ] [ 3 ] [ 4 ] [ 5 ] [ 6 ] [ 7 ] [ 8 ] [ 9 ] [ 10 ] [ 11 ] [ 12 ] [ 13 ]

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

Efficient Provably Algorithms for Boundary Bin-Pair Selection Problem

Department of Computer Science and Information Engineering
National Taipei University
New Taipei City, 237 Taiwan
E-mail: liang851015@gmail.com; hsinlung@mail.ntpu.edu.tw

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 2n 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(nm2T). 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

  Retrieve PDF document (JISE_202204_04.pdf)