A method embeds a watermark image into a host image with adaptive rectangular partition and Lower Upper (LU) decomposition such that a watermarked image is generated with improved computational complexity. The method divides a host image into an Red (R) component, a Green (G) component, and a Blue (B) component, and divides each component of the R, G, and B components into a plurality of M×M size blocks, and partitions each of the plurality of M×M size blocks into a plurality of non-overlapping blocks with adaptive rectangular partition. The method selects a plurality of embedding blocks from the plurality of M×M size blocks for each component of the R, G, and B components of the host image to embed watermark information such that the watermarked image is generated.