Abstract: A signature of a binary image contains, for each of a set of parallel lines, the total number of 1s (as opposed to 0s) along that line. We have been studying the recognition of binary images from these signatures. Typically a very large number of binary images would satisfy three signatures. To overcome this difficulty, we have investigated the possibility of modeling the class of binary images of a particular application area as a Markov random field (MRF) and using a stochastic algorithm which seeks to optimize a functional which, in addition to a penalty term for the violation of the signatures, contains a regularization term indicating the likelihood provided by the MRF. We have found that for some MRFs (specified by small regions of the image, which are either uniform or contain edges or corners), the method works remarkably well: binary image randomly selected from the MRF were recovered within one location in nearly all cases we have tried. The time-consuming nature of the stochastic algorithm is ameliorated by a preprocessing step which discovers locations at which the value is the same in all images having the given signatures; this reduces the search space considerably. We discuss, in particular, a linear-programming approach to finding such `invariant' locations.!12
展开▼
