Pattern-based identity signatures are commonplace in the animal kingdom, but how they are recognized is poorly understood. Here we develop a computer vision tool for analysing visual patterns, NATUREPATTERNMATCH, which breaks new ground by mimicking visual and cognitive processes known to be involved in recognition tasks. We apply this tool to a long-standing question about the evolution of recognizable signatures. The common cuckoo (Cuculus canorus) is a notorious cheat that sneaks its mimetic eggs into nests of other species. Can host birds fight back against cuckoo forgery by evolving highly recognizable signatures? Using NATUREPATTERNMATCH, we show that hosts subjected to the best cuckoo mimicry have evolved the most recognizable egg pattern signatures. Theory predicts that effective pattern signatures should be simultaneously replicable, distinctive and complex. However, our results reveal that recognizable signatures need not incorporate all three of these features. Moreover, different hosts have evolved effective signatures in diverse ways.