  In a typical video rate allocation problem, the objective is to optimally
distribute a source rate budget among a set of (in)dependently coded data units
to minimize the total distortion of all units. Conventional Lagrangian
approaches convert the lone rate constraint to a linear rate penalty scaled by
a multiplier in the objective, resulting in a simpler unconstrained
formulation. However, the search for the "optimal" multiplier, one that results
in a distortion-minimizing solution among all Lagrangian solutions that satisfy
the original rate constraint, remains an elusive open problem in the general
setting. To address this problem, we propose a computation-efficient search
strategy to identify this optimal multiplier numerically. Specifically, we
first formulate a general rate allocation problem where each data unit can be
dependently coded at different quantization parameters (QP) using a previous
unit as predictor, or left uncoded at the encoder and subsequently interpolated
at the decoder using neighboring coded units. After converting the original
rate constrained problem to the unconstrained Lagrangian counterpart, we design
an efficient dynamic programming (DP) algorithm that finds the optimal
Lagrangian solution for a fixed multiplier. Finally, within the DP framework,
we iteratively compute neighboring singular multiplier values, each resulting
in multiple simultaneously optimal Lagrangian solutions, to drive the rates of
the computed Lagrangian solutions towards the bit budget. We terminate when a
singular multiplier value results in two Lagrangian solutions with rates below
and above the bit budget. In extensive monoview and multiview video coding
experiments, we show that our DP algorithm and selection of optimal multipliers
on average outperform comparable rate control solutions used in video
compression standards such as HEVC that do not skip frames in Y-PSNR.
