This　paper　proposes　a　novel　data　hiding　scheme　with　high　capacity　for　binary　images,　including　document　images,　halftone　images,　scanned　figures,　text　and　signatures.　In　our　scheme,　the　embedding　efficiency　and　the　placement　of　embedding　changes　are　considered　simultaneously.　Given　an　MxN　image　block,　the　upper　bound　of　the　amount　of　bits　that　can　be　embedded　of　the　scheme　is　nlog2((MxN)/n　+　1)　by　changing　at　most　n　pixels.　Experimental　results　show　that　the　proposed　scheme　can　embed　more　data,　meanwhile　maintain　a　better　quality,　and　have　wider　applications　than　existing　schemes.　©　2010　IEEE.