This paper presents two halftoning methods to improve efficiency in generating structurally similar halftone images using Structure Similarity Index Measurement (SSIM). Proposed Method I reduces the pixel evaluation area by applying pixel-swapping algorithm within inter-correlated blocks followed by phase block-shifting. The effect of various initial pixel arrangements is also investigated. Proposed Method II further improves efficiency by applying bit-climbing algorithm within inter-correlated blocks of the image. Simulation results show that proposed Method I improves efficiency as well as image quality by using an appropriate initial pixel arrangement. Proposed Method II reaches a better image quality with fewer evaluations than pixel-swapping algorithm used in Method I and the conventional structure aware halftone methods.