The recognition of text in everyday scenes is made dif- ficult by viewing conditions, unusual fonts, and lack of lin- guistic context. Most methods integrate a priori appear- ance information and some sort of hard or soft constraint on the allowable strings. Weinman and Learned-Miller [ 14 ] showed that the similarity among characters, as a supple- ment to the appearance of the characters with respect to a model, could be used to improve scene text recognition. In this work, we make further improvements to scene text recognition by taking a novel approach to the incorpora- tion of similarity. In particular, we train a similarity expert that learns to classify each pair of characters as equivalent or not. After removing logical inconsistencies in an equiv- alence graph, we formulate the search for the maximum likelihood interpretation of a sign as an integer program. We incorporate the equivalence information as constraints in the integer program and build an optimization criterion out of appearance features and character bigrams. Finally, we take the optimal solution from the integer program, and compare all “nearby” solutions using a probability model for strings derived from search engine queries. We demon- strate word error reductions of more than 30% relative to previous methods on the same data set.