This paper presents a reversible data hiding scheme. The proposed scheme is based on the difference histogram shifting to spare space for data hiding. Nine basic scan paths are defined, and this means all-directional adjacent pixel differences can be obtained. Due to the fact that the grayscale values of adjacent pixels are close to each other, the all-directional adjacent pixel difference histogram contains a large number of points with equal values. Hence, more data can be embedded into the cover image than previous works based on histogram shifting. Furthermore, multi-layer embedding is used to increase the hiding capacity. In each embedding process, we can embed a large number of data into the cover image by choosing the best scan path and the optimized pixel difference. As experimental results have shown, the cover images are able to embed secret data at an average 12.5% of the size of the original images while all the PSNR values of the stego images remain larger than 30 dB.