Interpolation of steganographic schemes

•A major shortcoming of stego-schemes is expressed by the new concept of “waste”.•A new framework is made to measure the waste in terms of new criteria: RCW and ECP.•A mathematical basis is constructed to decrease the waste via combining schemes.•Some algorithms are designed to make optimally efficient low waste stego-schemes.•Combining two (and no more) schemes is proved to be the most efficient combination.

Many high performance steganographic schemes work at a limited or sparsely distributed set of embedding rates. We have shown that some steganographic changes will be wasted as these schemes are utilized individually for messages of various lengths. To measure the wasted changes and compare different schemes in this respect, we have built a framework based on two new criteria: the Relative Change Waste (RCW) and the Expected Changes per Pixel (ECP). To decrease the wasted changes a systematic combination of schemes is introduced and proved to be equivalent to nonlinear interpolation of points in a two-dimensional space. We have proved that a special case which leads to a linear interpolation – named Scheme Interpolation – is the most efficient combination. The Convex Hull Point Selection and the Waste Aware Interpolation algorithms are then proposed to construct optimally efficient scheme interpolations for any given level of RCW. Examples of the combined schemes are simulated and proved to outperform the well-known schemes presented so far in terms of ECP, RCW, PSNR and efficiency. Practical usage of scheme interpolation, the performance of the more general cases – called multi-scheme interpolation – and achieving the lower bounds of ECP and RCW are fully discussed.