Distance d1 between the right edges of A1 and B2, and distance d2 between the right edges of A3 and B4 are calculated. If data to be embedded is 1, one or a combination of a process for increasing the size of B2 in the column direction or decreasing the size of B4 in the column and a process for moving the position of B2 toward B3 or moving the position of B4 toward B3 is executed to meet d1>d2. If data to be embedded is 0, one or a combination of a process for decreasing the size of B2 in the column direction or increasing the size of B4 in the column direction, and a process for moving the position of B2 toward B1 or moving the position of B4 toward B5 is executed to meet d1