An extended watermarking method for still pictures is described that can embed watermarks immune to not only rotation, scaling, and translation but also to random geometric distortion and any of their combinations. It requires no searches for treating random distortion. The search for rotation and scaling is combinatorial but is independent of the search for translation. That is, the angle and size of the target picture can be restored without restoring the picture?s origin. Furthermore, the translation search is divided into horizontal and vertical searches that can be carried out independently. The number of searches is thus drastically reduced, making the processing speed high enough for practical application. Experimental evaluation demonstrated that the proposed method can embed watermarks immune to all four types of transformation. Although it was designed for still pictures, it can easily be extended to motion pictures.