Plain rotation, scaling, and/or translation (RST) of an image can lead to loss of watermark synchronization and thus authentication failure with standard techniques. The block-based approaches in particular, albeit strong against frequency and cropping attacks, are sensitive to geometric distortions due to the need for repositioning the blocks’ rectangular grid of reference. In this paper, we propose a block-based approach for watermarking image objects in a way that is invariant to RST distortions. With the term image object we refer to semantically contiguous parts of images that have a specific contour boundary. The proposed approach is based on shape information since the watermark is embedded in image blocks, the location and orientation of which are defined by Eulerian tours that are appropriately arranged in layers, around the object’s robust skeleton. The object’s robust skeleton is derived by its boundary after applying an extraction technique and not only is invariant to RST transformations but also to cropping, clipping, and other common deformation attacks, difficult to defend with current methods. Experiments using standard benchmark datasets demonstrate the advantages of the proposed scheme in comparison to alternative state-of-the-art methods.