Patch-based image denoising is a process of operating on a select set, or a “patch”, of pixels in an image at a time (also known as a “window” of pixels) to remove/replace noise from the pixels in the image.  For example, an image may be corrupted with some level of Additive White Gaussian Noise (AWGN) creating a sort of “salt and pepper” look in the image.  One patch of pixels is selected at a time to denoise the image by adjusting a grayscale vector of a center pixel value of the patch.  In doing so, a series of comparable “search patches” is selected from the image and compared to the patch undergoing denoising.  Based on distances from the patch being processed, the search patches are weighted and applied to the center pixel of the patch to linearly adjust the grayscale value of the center pixel.  This process is commonly referred to as a Non Local Means (NLM) denoising process and it is generally applied to each pixel in the image to restore the image to its original color values. 
NLM and other similarly complex processes, such as Block-Matching and 3D filtering (BM3D), can be applied to images in other ways to improve image quality.  For example, these processes can be used to “upscale” a lower resolution image by providing comparable pixels to regions in the image.  In other words, when a lower resolution image is upscaled to a higher resolution image (i.e., an image with more pixels), the extra pixels need to be created.  Patch-based imaging processes can be used to create these extra pixels by locating pixels in regions of the image and inserting the comparable pixels. 
Again though, current patch-based processing uses distances between comparable patches to weight a pixel under consideration.  Patches that are farther away from a pixel being operated on may have less effect on visual appearance and are therefore given less weight in adjusting the pixel.  But, the current patch-based processes determine the distances in a computationally intensive and inefficient manner.  For example, in an image where there are “N” pixels and there are “P” patches being used to process the image with “K” pixels in each patch, current patch-based processing performs N×P×K computations.  When N and P are relatively large numbers as is typically the case with high resolution images (e.g., images having N and possibly P values in the millions), current patch based processing uses substantial processor and memory capabilities.  Such may be of lesser concern in larger computing systems.  But, many mobile platforms, such as smart phones and tablet computers, have limited computing resources.  In any case, reducing the number of computations in patch-based image processing conserves power and allows processing resources to be distributed to other tasks.