Abstract: In order to solve the low capacity and poor visual quality of binary image watermarking algorithm, a high-capacity lossless watermarking algorithm is presented. The proposed algorithm first encodes the original image and then determines parameter values of watermark locations according to image block characteristic coefficient of RS code. We randomly select cross-substitution process model blocks according to value of replace degree factor. Finally, binary image watermark is embedded through difference of replace methods in two modes. Experimental results show that the algorithm effectively enhances visual quality of watermark in secret image. The effective capacity of embedded watermark is obviously increased and the original image can be losslessly recovered in watermark extraction.