An encoding system converts a grayscale image into an original halftone image according to a predetermined threshold matrix, determines carrier cells from the original halftone image according to reference dot patterns having rotationally asymmetric first-tone patterns, converts the carrier cells into encoded cells according to to-be-embedded codes and rotational states of corresponding asymmetric first-tone patterns, and optimizes non-carrier cells and encoded cells using a direct binary search technique to visually approach the grayscale image.