A tradeoff between the hiding capacity of a cover image and the quality of a stego-image in steganographic schemes is inevitable. This paper presents overlapping codebook partitioning to challenge this tradeoff. The codewords in a codebook are grouped into sub-clusters, according to similarity. Any size sub-cluster is allowed; moreover, a sub-cluster is permitted to overlap with sub-clusters to increase hiding capacity without sacrificing image quality. As a result of this improved scheme, the hiding capacity of a cover image increases, whereas the quality of a stego-image stays the same.