An Adjustable Interpolation-based Data Hiding Algorithm Based on LSB Substitution and Histogram Shifting

Introduction

Interpolation is a common multimedia processing technique. The main concept of interpolation is to use known discrete data to estimate the value at an unknown position. The familiar interpolation techniques include nearest-neighbor interpolation, linear interpolation, and bilinear interpolation. The nearest-neighbor interpolation is the simplest method that selects the value of the nearest point as the predicted value for the unknown position, not considering the values of other neighboring points. For example in Figure 1, each point is characterized by x coordinate value, y coordinate value, and its corresponding value V. Assume and are known points with corresponding value and . The predicted value for point equals because point is closer to than other points. However, the nearest-neighbor interpolation causes undesirable jagged interpolation results. Another simple interpolation method is called linear interpolation, and it is determined by searching the closest two neighboring points and interpolating the predicted value with the concept of similar triangle. For example in Figure 1, the value of point can be interpolated using Equation 1. Finally, bilinear interpolation is an extension of linear interpolation for two variables on a regular 2D grid. For interpolating the point on a 2D grid, linear interpolation is performed three times to interpolate one unknown point on a 2D grid (See Equations 2 and 3).

Figure 1.

An interpolation example