Certain types of digital image processing invoke identifying sufficiently similar patches in two different image regions (e.g., two different or two different regions of the same image). In one example, a similarity between two image patches is evaluated based on a metric indicating a patch distance, wherein one of the image patches is selected from a source image region and the other image patch is selected from a target image region. For instance, the pixel values in the two patches may be represented as vectors, and a similarity score is laced based on a similarity between the vectors. An example of a similarity score is a sum-of-square distances between pixel values in the patches, where patches with identical image content will be at a distance of zero. Identifying these similarities between source image patches and target image patches allows the target images to be used for manipulating the source image. Examples of these manipulations include image in-painting, stereo matching, and texture synthesis.
Some image manipulation applications use one or more patch-matching algorithms to find similarities between source image patches and target image patches. A patch-matching algorithm identifies correspondences between source image patches and sufficiently similar target image patches using offset vectors. For example, the patch-matching algorithm generates at least one transform that maps a given source image patch to a corresponding target image patch. The offset vector identifies an offset from the source image patch to a target image patch that is sufficiently similar to the source image patch. In one example, a source image patch in the source image region is defined using pixel coordinates S(i,j), which indicates that the source image patch has its center (or some other reference point) at column i and row j of the pixels in the source image region S. A target image patch in the target image region T is similarly defined using pixel coordinates T(k,l), which indicates that the target image patch has its center (or some other reference point) at column k and row l of the pixels in the target image region T. A transformation of S to T is represented using an offset vector O between patches S(i,j) and T(k,l), where the offset vector is defined as O=(k−i,l−j).
In certain patch-matching algorithms, an offset vector for a first source image patch is propagated to a neighboring source image patch. The propagation is performed due to the likelihood of adjacent patches in the source image being sufficiently similar to adjacent patches in the target image. For example, a source image patch and its neighboring source image patches may depict a brick wall. A patch-matching algorithm, when attempting to find a sufficiently similar target image patch for the source image patch, identifies an offset vector (e.g., a vector of (5, 5)) that has already been determined for the neighboring source image patch. A target image with one image patch depicting a brick wall is likely to have an adjacent image patch depicting a brick wall. To take advantage of this circumstance, the patch-matching algorithm searches for a target image patch that is offset from the source image patch by the same offset vector (e.g., a target image patch five pixels up and five pixels right from the source image patch) that was determined for the neighboring source image patch.
In some cases, the target image patch identified via the offset may not be sufficiently similar to the source image patch. For example, the offset may identify a target image patch that depicts a window instead of a brick wall. In this case, the patch-matching algorithm continues searching for a more similar target image patch.
Relying on the propagation of offset vectors from neighboring patches may cause processing inefficiencies. For instance, nearest-neighbor propagation may be sub-optimal for propagating offsets through a source image that includes occluding objects, which hinder the propagation. In a simplified example, a source image region depicts a brick wall with a lamp post (i.e., an occluding object) in the middle of the wall, and a target image region depicts a similar brick wall without a lamp post. The source image region includes a first “brick wall” image patch depicting a portion of the brick wall on one side of the lamp post, a “lamp post” image patch depicting a portion of the lamp post, and a second “brick wall” image patch depicting a portion of the brick wall on another side of the lamp post.
In this example, the same offset vector (e.g., a “brick wall” offset of (5, 5)) would allow sufficiently similar target image patches to be found for both the first “brick wall” image patch and the second “brick wall” image patch. But the “brick wall” offset does not allow a sufficiently similar target image patch to be found for the “lamp post” image patch. For instance, moving five pixels up and five pixels right from the lamp post may select a target image patch depicting the brick wall rather than an image patch that is similar to the “lamp post” image patch. The patch-matching algorithm would therefore select some other offset vector (e.g., a “lamp post” offset of (11, 11)) that locates a sufficiently similar target image patch for the “lamp post” image patch.
Since the “lamp post” image patch is a neighbor of the second “brick wall” image patch, the “lamp post” offset, rather than the “brick wall” offset, will be propagated to the second “brick wall” image patch even if the “brick wall” offset would locate a more similar target image patch for the second “brick wall” image patch. The “lamp post” offset will not locate a target image patch that is sufficiently similar to the second “brick wall” image patch. Therefore, the patch-matching algorithm continues searching for a more similar target image patch and thereby re-creates the “brick wall” offset that would have been propagated between the first and second “brick wall” patches if the “lamp post” image patch had not been positioned between them. In this manner, the lamp post's image patch occludes the “brick wall” offset from being propagated between the two “brick wall” patches. Thus, the patch-matching algorithm must expend processing resources on re-creating the same “brick wall offset” for both of the “brick wall” patches. The processing resources being expended can increase further if additional search techniques, such as image patch rotations and changes in scale, increase the dimensionality of the search space of target image patches.
Thus, existing patch-matching algorithms may present computationally inefficiencies for reasons such as (but not limited to) those described above.