Many EMD-type data hiding schemes have been proposed. However, the data hiding capacity is less than 2bpp when the embedding procedure uses formula operations. In order to improve the data hiding capacity from 1bpp to 4.5bpp, a new data hiding scheme is proposed in this paper based on a formula using the fully exploiting modification directions method (FEMD). By using our proposed theorem, the secret data can be embedded by formula operations directly without using a lookup matrix. The simulation results and performance analysis show the proposed scheme not only maintains good embedding capacity and stegoimage quality but also solves the overflow problem. It does so without using extra memory resources and performs within a reasonable computing time. The resource usage and capabilities of this scheme are well matched to the constraints and requirements of resource-scarce mobile devices.