EVALUATION OF AN ALGORITHM FOR FINDING A MATCH OF A DISTORTED TEXTUREPATTERN IN A LARGE IMAGE DATABASE

Evaluation of an algorithm for finding a match for a random texture pa ttern in a large image database is presented. The algorithm was design ed assuming that the random pattern may be subject to misregistration relative to its representation in the database and assuming that it ma y have missing parts. The potential applications involve authenticatio n of legal documents, bank notes, or credit cards, where thin fibers a re embedded randomly into the document medium during medium fabricatio n. The algorithm achieves image matching by a three-step hierarchical procedure, which starts by matching parts of fiber patterns while solv ing the misregistration problem and ends up by matching complete fiber patterns. Performance of the algorithm is studied both theoretically and experimentally. Theoretical analysis includes the study of the pro bability that two documents have the same pattern, and the probability of the algorithm establishing a wrong match, as well as the algorithm 's performance in terms of processing time. Experiments involving over 250,000 trials using databases of synthetic documents, containing up to 100,000 documents, were used to confirm theoretical predictions. In addition, experiments involving a database containing real images wer e conducted in order to confirm that the algorithm has potential in re al applications.