# Watermark insertion process in image

I'm new in the field of image processing and I'am trying to implement a watermarking algorithm (for medical images in DICOM format) based on this paper.

As written in the paper, this algorithm is based on the algorithm described by Ni, Shi, Ansari, and Su in the paper "Reversible data hiding" but it avoids modifying the histogram.

Despite having read and reread the paper several times, I did not understand the watermark insertion algorithm that is as follows:

1. Read the host image $I_o$
2. determine the color depth $k$
3. extract the fi rst $k$ pixels and store their LSBs in a variable $S$
4. calculate the histogram of the remaining pixels of $I_o$: the histogram values will be $f(0), f(1), ..., f(2^k - 1)$ for the $k$ bit-depth image
5. determine a list of levels $l_0, l_1, l_2, ..., l_n$ such that $f(l_i) \geq f_{min}$ and $f(l_i + 1) = 0$, where $f_{min}$ is a minimum value that allows to reduce the levels encoding overhead
6. compute the list of delta values $\Delta_i = l_i - l_{i-1}$ with $i = 1...n$
7. encode $l_0$ in the LSBs of the first $k$ pixels
8. compute the bit string $B$ as the concatenation of $W_L$, $S$, $L$, $n$, $\Delta_1, \Delta_2, ..., \Delta_n$, $PayloadData$, $Signature$ where:

1. $W_L$ is the bit length of the following watermark, represented on 32 bits
2. $L$ are 8 bits expressing the bit length of the encoding of each $\Delta$
3. $n$ is the 16 bit representation of the number of the $\Delta$ values
4. $PayloadData$ are the data to be stored in the image (eventually encrypted)
5. $Signature$ is the digital signature of the host image along with the $PayloadData$
9. insert the bits of $B$ into the pixels (in raster scan order from the $(k+1)$-th pixel) having a gray level $l_0$, and then using the pixels with levels $l_1, l_2, ..., l_n$ in raster scan order: the insertion of a bit of value $b$ into $a$ pixel of gray level $l_i$ will assign the gray level $l_i + b$ to the pixel

10. write the obtained image $I_w$.

I try to make a simple example: In this case:

1. I read the 3x3 image $I_o$
2. $k = 2$
3. I extract the first two pixels (I start from the top-left and I move to lines): $k_1=00$, $k_2=01$. So $S=k_{1}^{(2)} | k_{2}^{(2)} = 01$ where the sign $|$ indicates the concatenation operation and $k_{i}^{(2)}$ indicates the second bit (from the left) of the $i$-th pixel
4. I calcule the histogram of the remaining pixels so it's as if my image had now 7 pixels and not 9, right? The histogram is located in the figure at step 4
5. In my case this occurs only if I consider $f_{min}=0$, but it is an extreme case (I think). So $l_i=l_1=1$ and $l_{i+1}=l_2=2$ and so $f(l_1)=1, f(l_2)=0$. What it means with "...to reduce the levels encoding overhead"?
6. $\Delta_1 = l_1-l_0=1-0=1, \Delta_2 = l_2-l_1=2-1=1, \Delta_3 = l_3-l_2=3-2=1$ with $n=2^k-1$ but I think there is an error and the correct form of $\Delta_i$ is $\Delta_i=f(l_i)-f(l_{i-1})$ so $\Delta_1=-3, \Delta_2=-1, \Delta_3=2$
7. now? I don't undertstand what I have to do..

I do not know if I did right up to this point, someone could help me out? I did not find examples that could help me understand the algorithm.

Thank you very much