In an earlier paper , we proposed a steganography scheme for hiding a piece of critical information in a host binary image. That scheme ensures that, in each m × n image block of the host image, as many as ⌊log 2(mn + 1)⌋ bits can be hidden in the block by changing at most 2 bits in the block. In this paper, we propose a new scheme that improves  in its capability to maintain higher quality of the host image after data hiding by sacrificing some data hiding space. The new scheme can still offer a good data hiding ratio. It ensures that, for any bit that is modified in the host image, the bit is adjacent to another bit which has a value equal to the former's new value. Thus, the hiding effect is quite invisible.