Generally, conventional transform (DWT and DFT, etc.) -based watermarking techniques provide only one spectrum plane for embedding the watermark, thus the embedding watermark information can be easily removed. To solve this problem, we propose an efficient cellular automata (CA) based watermarking method that CA transform (CAT) with various gateway values can provide many transform planes for watermark embedding according to various CA rules. In this paper, multiple ownership watermarks are first recorded in the form of an elemental image array (EIA), simultaneously, and then the recorded EIA as the watermark data is embedded into the CAT coefficient. An additional advantage of this proposed method is that EIA is composed of many elemental images and each elemental image has its own property of watermarks. Even though most data of elemental images are lost, the watermarks can be reconstructed from the remaining elemental images successfully. Experimental results show that the proposed technique provides good image quality and is robust in varying degree to some image processing attacks.