PATTERN-MATCHING IN A DIGITIZED IMAGE

For motivation purpose, imagine the following continuous pattern-match ing problem. Two continuous pictures, each consisting of unicolor regi ons, are given; one picture is called the scene and the other the patt ern. The problem is to find all occurrences of the pattern in the scen e. As a step toward efficient algorithmic handling of the continuous p attern-matching problem by computers, where discretized representation s are involved, we consider pattern-matching problems where the patter n and the text are specified either in terms of the ''continuous'' pro perties, or through other exemplar digitized images-a variety of alter native specifications is considered. From the perspective of areas suc h as computer vision or image processing, our problem definitions iden tify an important gap in the fundamental theory of image formation and image processing-how to determine, even in the absence of noise, if a digitized image of a scene could contain an image of a given pattern. This is done using careful axiomatization. Such a ''digitized-based'' approach may lead toward building on the theory of string-matching al gorithms (in one, or higher, dimensions) for the benefit of algorithmi c pattern matching in image processing.