Using a lexicon can often improve character recognition under challenging conditions, such as poor image quality or unusual fonts. We propose a flexible probabilistic model for character recognition that integrates local language prop- erties, such as bigrams, with lexical decision, having open and closed vocabulary modes that operate simultaneously. Lexical processing is accelerated by performing inference with sparse belief propagation, a bottom-up method for hy- pothesis pruning. We give experimental results on recogniz- ing text from images of signs in outdoor scenes. Incorpo- rating the lexicon reduces word recognition error by 42% and sparse belief propagation reduces the number of lexi- con words considered by 97%.