  Measuring the similarity between patches in images is a fundamental building
block in various tasks. Naturally, the patch-size has a major impact on the
matching quality, and on the consequent application performance. Under the
assumption that our patch database is sufficiently sampled, using large patches
(e.g. 21-by-21) should be preferred over small ones (e.g. 7-by-7). However,
this "dense-sampling" assumption is rarely true; in most cases large patches
cannot find relevant nearby examples. This phenomenon is a consequence of the
curse of dimensionality, stating that the database-size should grow
exponentially with the patch-size to ensure proper matches. This explains the
favored choice of small patch-size in most applications.
  Is there a way to keep the simplicity and work with small patches while
getting some of the benefits that large patches provide? In this work we offer
such an approach. We propose to concatenate the regular content of a
conventional (small) patch with a compact representation of its (large)
surroundings - its context. Therefore, with a minor increase of the dimensions
(e.g. with additional 10 values to the patch representation), we
implicitly/softly describe the information of a large patch. The additional
descriptors are computed based on a self-similarity behavior of the patch
surrounding.
  We show that this approach achieves better matches, compared to the use of
conventional-size patches, without the need to increase the database-size.
Also, the effectiveness of the proposed method is tested on three distinct
problems: (i) External natural image denoising, (ii) Depth image
super-resolution, and (iii) Motion-compensated frame-rate up-conversion.
