Abstract: Inspired by Steghide and diamond encoding, we develop a new steganographic method which preserves the first-order statistics of the cover data and has high embedding efficiency. Pixels are allowed to change only by 1 or ?1 so that distortion of the cover image is small. As with Steghide, the proposed method embeds a 13-ary digit in two sections of pixels to increase the exchange rate. For some sections, two exchanges are necessary since the diamond encoding requires that data be changed by 2, and this cannot be done in +-1 embedding. An embedding is constructed by finding a maximum matching of hypergraph. Experiments demonstrate that the proposed method outperforms Steghide and the diamond encoding in terms of embedding efficiency, visual quality and anti-detection ability.