Simple least-significant-bit (LSB) substitution is a method used to embed secret data in least significant bits of pixels in a host image. The LSB approaches typically achieve high capacity. A simple LSB substitution, which hides secret data directly into LSBs, is easily implemented but will result in bad quality of the stego-image. In order to reduce the degradation of the host image after embedding, an LSB substitution scheme was proposed by Wang et al. They proposed a genetic algorithm to search for approximate solutions. Also, Chang et al. proposed a dynamic programming strategy to efficiently obtain a solution. In this paper, we propose a more general model of Wang et al.’s LSB substitution scheme, called as transforming LSB substitution. In order to overcome the problem associated with the two previous approaches of a long running time, a more efficient approach, referred to as the matching approach, is proposed to find a better solution. Some experiments, demonstrations and analyses are shown in this paper to demonstrate our new scheme and approach.