Spectra of shape contexts: An application to symbol recognition

•Pixel-level constraint (PLC) histogram is robust but with O(N3) complexity.•Spectra of shape contexts (SSC) inherit the robustness with reduced complexity.•Through rigorous theoretical deduction, PLC is correlated to SSC via FFT.•SSC outperforms PLC in robustness and shape context in invariance experimentally.

The pixel-level constraint (PLC) histograms are known for robustness and invariance in symbol recognition but limited in O(N3) complexity. This paper proves that matching two PLC histograms can approximately be solved as matching the power spectra of the corresponding shape contexts. As a result, spectra of shape contexts (SSC) inherit robustness and invariance from PLC while the computational cost can be reduced. Moreover, a maximum clique based scheme is proposed for outlier rejection. The theoretical and experimental validation justifies that SSC possesses the desired properties for symbol recognition, that is, robustness, invariance, and efficiency. It outperforms PLC in terms of robustness and time efficiency, and shape context in terms of rotation invariance.