In this paper, we consider the problem of automatically reading graffiti tags. As a preparatory step, we create a large set of synthetic graffiti-like characters, generated from publicly available true type fonts. For each character in the database, we extract a number of scale independent local binary descriptors. Then, using binary non negative matrix factorization, a sufficient number of basis functions are learned. Basis function coefficients of novel images can then be directly used for hashing characters from the database of prototypes. Finally, graffiti tags are recognized by means of a localized, spatial voting scheme.