This　paper　proposes　a　method　to　embed　data　in　binary　images　with　high　embedding　capacity.　It　is　proved　that,　given　an　mn　image　block　of　the　host　image,　the　upper　bound　of　the　amount　of　bits　that　can　be　embedded　in　that　block　is　⌊(log2(mn+1)⌋　by　changing　at　most　1　pixel　in　the　block.　An　algorithm　whose　embedding　capacity　can　reach　the　bound　is　then　constructed.　We　also　summarize　some　rules　for　selecting　pixels　to　be　changed　in　order　to　maintain　higher　quality　of　the　host　image　after　data　hiding.　The　robustness　and　security　of　the　proposed　algorithm　is　analyzed.　Three　examples,　data　hiding　in　digital　handwritten　signature,　temper　detection　of　digital　binary　documents,　and　invisible　annotation　for　cartoon　image　are　tested　to　illustrate　the　potential　applications.