Patch priority and its effect on Criminsi's Exemplar Based Inpainting

Question

I am trying to implement exemplar based in-painting, as proposed by Criminsi et. al. in its original format (before moving into further optimisations).

I have a few theoretical doubts which I would like to clarify.

I am not sure how the patch priority and the determination of fill-order works to propagate linear structures into the user-selected target region.

From what I understand, Criminsi suggests the following:

1. Determine the fill front dΩ.
2. Compute the patch priorities [C(p)D(p)] on patches lying on the fill front.
3. Propagate texture into the patches - in order of their patch priorities.
4. Update confidence values.
5. Re-compute fill front dΩ from the remaining unfilled section.

[Repeat these 5 steps till all of the target region is filled].

Now, if this understanding of the algorithm is correct (and, please do correct me if the interpretation is wrong), I have the following doubt:

• If I'm always filling patches from the fill front only, and if the patches are fixed in their spatial location (w.r.t other patches on the fill-front), then I don't see how the order of filling-in matters. The patches are filled in by direct sampling of the source region, which stays constant for all iterations. Hence, I do not understand how the order of filling will result in any pixel level difference on the propagated textures. From what I gather, the best match from the source region should remain unaltered, irrespective of the order. What am I missing here?

• Based on this video (and assuming it is correct), the patch filling does not always occur on the fill-front only. How does this work? Does this mean we are to compute the priorities for all patches in the target region at once and go on filling them based on their priorities? Then, how does the fill-front determination matter and why does Criminsi determine dΩ at all? I understand Criminsi's approach was a step ahead of the traditional onion-peel technique. But how, exactly?

I really wish to clarify these questions before I delve into 2-3 days of intense coding.

Please help.

Thanks in advance.

+++++++++++++++++++++++++++++++++++++++

One more concern I'm facing while implementing this algorithm:

While propagating structure and texture information, I'm directly sampling the source region for patches with minimal SSD of the already filled pixels in the two patches.

The question bugging me is: SSD of what? I tried SSD of RGB/HSV values but that did not work out. I've just started referencing the original citation of Criminisi for SSD, but I'm just wondering... is there an easier way out?

Any help would be appreciated.

Answer 1

Fill front:

The idea of the paper is to inpaint first patches where the information is the most reliable, hence the fill front. In this thin border, a part of the patch is made of the original image (at the beginning) or from the previous result. Thus, the video is wrong (and the results are not so good btw).

If you do not follow the fill front approach, then you need some global optimization process to ensure the correctness of your result (see the popular graphcut-based textures for example).

Patch propagation:

When inpainting a patch, you just copy the content of a source patch (that lies inside a larger source region) that intersects the current $\Omega$ domain. The source area is fixed but not the place where you put it, that depends on the current fill front pixel.

Priority function:

The intuition here is that since you are going to copy source patches, then you should copy the most textured patches first. Why is that? Suppose that you have a purely half black (left and half white (right) image, and the inpainting domain i sin the middle. Without priority, you are likely to copy purely black or white patches first. With priority function, you will detect pixels in the fill front that belong to the border between the black and white areas, copy some half-black half-white patches at the correct positions, and then only add pure black/white patches at relevant positions.

Why order matters, even with small fronts

In the example from the comment below, we suppose that we have a fill front of 5 pixels (1, 2, 3, 4, 5) with priority order (3, 4, 5, 2, 1).

Since the fill front is very small, one can infer that the remaining domain to inpaint is very small. Consequently, the patches used to fill the hole will intersect.

Then, what happens is that:

1. you copy a source patch for pixel 3. The remaining hole is empty, you can copy all the patch that intersects $\Omega$
2. you look for a patch that matches pixel 4. Once found, you copy it into $\Omega$ minus the intersection with the previous patch (the one for pixel 3). If you swap the priority of 3 and 4, then you will not retain the same part of the source patches.
3. process the next fill front pixel, etc.