Suppose that we are given a picture having approximately piecewise constant gray leveL Each point P has a largest neighborhood N(P) that is entirely contained in one of the constant regions, and the set of maximal N(P)'s (i.e., N(P)'s not contained in other N(P)'s) constitutes an economical description of the picture, generalizing the Blum "skeleton" or medial axis transformation. This description can be used to construct approximations to the picture (e.g., by discarding small N(P)'s). The picture can be smoothed, without excessive blurring, by averaging over each N(P). By taking differences between pairs of touching maximal N(P)'s, the edges between the regions can be detected; since this edge detection scheme is not based on symmetrical detection operators, it is not handicapped when two adjacent regions differ greatly in size.

A previous report described techniques for creating photomosaics: first, the two overlapping images are brought into register; second, a seam from the top of the overlap region to its bottom is tracked one row at a time; finally, the resultant artificial edge introduced by the seam is locally smoothed by a ramp function. This correspondence describes improved methods for gray-scale registration and for choosing a best seam path with specified endpoints using dynamic programming.

A technique is described which allows overlapping images to be combined into a photomosaic in which the visual impact of the introduced seam. has been minimized. Images which have been brought into geometric and gray scale register are combined on a line-by-line basis by choosing a "best" seam point for each line. The resulting artificial edge at the seam point is then locally smoothed.