Cellular automata are discrete dynamical systems, which provide the basis for the synthesis of complex emergent behavior. This paper proposes a new algorithm of digital watermarking based on cellular automata transform (CAT). The idea of two-dimensional CAT is introduced into the algorithm. After the original image is disassembled with 2D CAT, the watermark information is embedded into the Middle-frequency of the carrier picture. Cellular automata have a huge number of combinations, such as gateway values, rule numbers, initial configuration, boundary condition, etc. Using CAT, the robustness of the watermark will be tremendous strengthened as well as its imperceptibility. Experimental results show that this algorithm can resist some usual attacks such as compression, sharpening and so on. The proposed method is robust to different attacks and is more security.