For our final project in Massively Parallel Computing, Bob Kinney and myself wrote a basic GPU implementation (in CUDA) of the PatchMatch algorithm.
Image/Video editing is an important part of any production. Issues outside of your control can otherwise ruin a good photo or photo shoot. You can try cropping, and typical image editing techniques (averaging out, etc), but the results can suffer as a result.
That's where PatchMatch comes in. Using a combination of a number of algorithms (including Nearest Neighbor and Bidirectional Similarity) you can remove unwanted aspects of any video or photos.
We did not get to implement all of the aspects of PatchMatch, and focused on NNF and BDS and implemented two sample applications that demonstrate the applications. One "reconstructs" an image using data from another image, and the other "retargets" an image, doing a semi-smart resize, finding unique aspects of an image and ensuring they are included in resized image.
NNF:
- Start with random selection of source data, compare to target image
- Scan nearby data, look for better matches
- Do random scans for better data
- ...
- Iterate
Next steps:
For video/image editing, you would start targeting regional image reconstruction with the image itself (or possibly another image of the same subject).
BDS:
- Construct NNF of resized image (starting with a guess).
- Do "voting" of NNF to generate new image
- Voting averages for "completeness" and "coherence"
- ...
- Iterate
Next steps:
For "smart" retargeting, you'll need importance masks and constraints to choose which data is more important.
The code may be interesting for a reference, but there are all sorts of ways that it might fail. For example, it expects to be able fit the images into the texture cache of your GPU.