Pattern matching in a digitized image

The continuous pattern matching problem is defined. Given are two pictures, each consisting of unicolor regions; one picture is called the scene and the other the pattern . The problem is to find all occurrences of the pattern in the scene. As a step towards efficient algorithmic handling of the continuous pattern matching problem by computers, where discretized representations are involved, we give several algorithms. Our strongest algorithmic result is for a one-dimensional version of the problem, where running time which is linear in the length of a digitized representation is achieved. The definitions of our problems are derived from a “digitized-based” approach to object recognition problems in computer vision, which is different from a common computer vision approach. The digitized based approach may lead towards further research within the discrete algorithms community on computer vision problems.