Abstract: Proposed in this paper is a non-uniform partition scheme for digital images, by which the digital image region is triangulated based on the gray value of pixels. A steganography algorithm is obtained using this partition method. Fitting the given data, the gray value of the pixels with the least squares method, a self-adaptive non-uniform partition algorithm is realized. The detailed non-uniform triangulation process for an image is shown. Recording the triangulation information of the secret image as quatemary number, triangulating the carrier digital image accordingly and embeding the triangulation information and gray information of the secret image into the carrier digital image. A new steganography algorithm is obtained by utilizing the image reconstruction under triangulation. Saving coding and decoding time is its outstanding advantages. The new algorithm is applied on several kinds of images, and it is shown that the hidden data in camouflage image is difficult to perceived, the reconstruction image is satisfying, and the new algorithm is feasible.