  Estimation of the Embedding capacity is an important problem specifically in
reversible multi-pass watermarking and is required for analysis before any
image can be watermarked. In this paper, we propose an efficient method for
estimating the embedding capacity of a given cover image under multi-pass
embedding, without actually embedding the watermark. We demonstrate this for a
class of reversible watermarking schemes which operate on a disjoint group of
pixels, specifically for pixel pairs. The proposed algorithm iteratively
updates the co-occurrence matrix at every stage, to estimate the multi-pass
embedding capacity, and is much more efficient vis-a-vis actual watermarking.
We also suggest an extremely efficient, pre-computable tree based
implementation which is conceptually similar to the co-occurrence based method,
but provides the estimates in a single iteration, requiring a complexity akin
to that of single pass capacity estimation. We also provide bounds on the
embedding capacity. We finally show how our method can be easily used on a
number of watermarking algorithms and specifically evaluate the performance of
our algorithms on the benchmark watermarking schemes of Tian [11] and Coltuc
[6].
