A reversible data hiding scheme based on graph neighbourhood degree

The perceptibility and capacity are two vital criteria of data hiding scheme. Concerning these criteria, data hiding algorithm used images as cover object based on the graph theory is proposed in this study. Images are quantised according to determined range and then quantised images are divided into nxn sized blocks. Each block is accepted as a graph and vertexes which have the same quantisation value are accepted as neighbours. Neighbourhood degrees of vertexes are calculated and indices of vertexes that have a neighbourhood degree over the threshold value are stored in the codebook. Pixel values indicated by these indices in the codebook are used for data hiding process. In this algorithm, there is no need for edge extraction because of hiding data to pixels containing vertexes having high neighbourhood degrees. The proposed method is compared with similar methods in literature in terms of the perceptibility and capacity. More successful results are provided than the others.