In this paper, we shall propose a new image steganographic scheme for embedding secret messages into a gray-valued cover image and capable of producing a secret-embedded image that is totally indistinguishable from the original image by the human eye. In addition, the proposed scheme avoids the falling-off-boundary problem by using the Pixel-Value Differencing (PVD) and the Exploiting Modification Direction (EMD). A cover image is partitioned into non-overlapping blocks of four consecutive pixels. First, we derive two pieces of difference value from four consecutive pixels by utilizing the PVD. The hiding capacity of the four consecutive pixels depends on the two pieces of difference value. In other words, the smoother area is, the less secret data can be hidden; on the contrary, the more edges an area has, the more secret data can be embedded, and then secret data embedded by using the PVD. In order to provide high payload capacity, the remainder of two average values of the four consecutive pixels can be computed, and the two average values are capable of embedding secret data by using the EMD. The embedded secret message can be extracted from the resulting stego-image without referencing the original cover image. Moreover, a pseudo-random mechanism may be used to achieve secrecy protection. The experimental results show that the proposed scheme is capable of providing a great payload capacity, and the image quality of the embedded image is better than PVD for a gray-level image.