In　an　earlier　paper　[1],　we　propose　a　high　capacity　data　hiding　scheme　for　various　types　of　binary　images.　The　scheme　ensures　that　in　an　MxN　image　block,　the　upper　bound　of　the　amount　of　bits　that　can　be　embedded　is　⌊nlog　2((MxN)/n　+　1)⌋　by　changing　at　most　n　individual　pixels.　However,　changing　individual　pixels　in　halftone　images　will　introduce　undesirable　＇salt-and-pepper＇　noise,　or　local　black　or　white　clusters.　In　this　paper,　we　propose　a　new　scheme　for　halftone　images　which　improves　[1]　in　its　capability　to　maintain　better　quality　of　the　host　image　after　data　hiding　by　changing　pixels　in　pairs　rather　than　individually.　The　new　scheme　can　still　offer　a　high　embedding　efficiency.　Experimental　results　show　that　the　new　scheme　can　maintain　better　image　quality.　©　2013　Springer-Verlag.