Analytical method for optimum non-negative integer bit allocation

作者：Hatam Mahdi^*; Masnadi Shirazi Mohammad Ali

来源：IET Signal Processing, 2016, 10(8): 936-946.

DOI：10.1049/iet-spr.2014.0336

• video coding
• data compression
• computational complexity
• optimisation
• optimum nonnegative integer bit allocation problem
• ONIBA problem
• OIBA problem
• OBA problem
• optimum bit allocation problem
• optimum integer bit allocation problem
• analytical optimisation approach
• Lagrange unconstraint problem
• Lagrange multiplier removal
• selection and bisection algorithm
• low complexity algorithm
• discrete function
• computational complexity reduction
• video frame compression

The optimum bit allocation (OBA) problem was first investigated by Huang and Schultheiss in 1963. They solved the problem allowing the bits to be signed real numbers. Later, different algorithms were proposed for OBA problem when the bits were constrained to be integer and non-negative. In 2006, Farber and Zeger proposed new algorithms for solving optimum integer bit allocation (OIBA) and optimum non-negative integer bit allocation (ONIBA). None of the existing algorithms for OIBA and ONIBA problems end with an analytical solution. In this study, a new analytical solution is proposed for OIBA and ONIBA problems based on a novel analytical optimisation approach. At first, a closed form solution is derived for Lagrange unconstraint problem. Then, by removing the Lagrange multiplier, an analytical solution is obtained for OIBA and ONIBA problems. Using the selection and bisection algorithms, a low complexity algorithm is proposed for searching in a group of discrete functions which can reduce the computational complexity of the analytical solution. The complexity of computing the analytical solution is O(k) which is much lower than the complexity of existing ONIBA algorithms.

• 出版日期2016-10