1
$\begingroup$

Suppose that you have a thumbnail and the original image from which it was generated. You need to match the thumbnail to an area in the original image that represents the original selection from which that thumbnail was generated. Humans are really good at this sort of matching, but I have no idea how to go about writing an algorithm to do this automatically.

Here are my thoughts on the matter so far:

  1. A thumbnail is created by first cropping then scaling the original selection. Logically, some scaling is required to reverse the process.
  2. A thumbnail's dimensions could be greater than that of the original selection. Therefore, this algorithm should account not only for the common downscaled thumbnails, but also for cases where the cropped original selection has been upscaled to the thumbnail's intended dimensions.
  3. Theoretically, it is possible that a thumbnail was generated such that the entire original image was encompassed inside the original selection, akin to background-size: contain in CSS. All four corners of the original selection thus fall outside of the original image. The extra space could have been filled either with a solid color (possibly transparent) or with Photoshop's Content Aware Fill or a similar algorithm (inpainting). This is an edge case; however, an ideal reverse-thumbnail algorithm should be able to handle such cases.
  4. This algorithm should return the x,y pixel coordinates of the top-left corner of the original selection as it falls on the original image, as well as the width and length of the selection.

I suspect that feature detection is required to make this work, but I don't know where to start. Partial answers are acceptable, but if this is an easier problem than I think it is, please do give it a shot. Any language is fine, but the implementation should not rely on proprietary software, and Python or JavaScript are tentatively preferred.

I've put together a sample set of 30 images from my current project for testing potential algorithms. I tried to include a variety of images to challenge any feature-recognition approach. All selections in this collection have been downscaled to the intended thumbnail size of 300x300 after cropping. I included an info.csv, which contains id,x,y,w,h representing the coordinates and dimensions of the original selection relative to the full-sized image. These values were obtained by applying Deep Zoom coordinates saved from the source tiff files to the full images. Due to floating point inaccuracy, w and h differ by one pixel in three cases (13, 17, 21). These images were included intentionally to test how your algorithm might handle accuracy concerns. A second info_ur.csv includes unrounded values for reference.

Download test images: https://app.box.com/s/65240dlgvfvevw2grhyaqqjjc29jzv65

Finally, here's an illustration of the four cases such an algorithm might encounter:

four ways to generate a thumbnail from an image

$\endgroup$
  • $\begingroup$ My coworkers suggested that OpenCV's template matching functions might be of help here; however, I'm unsure if they can account for scaling. I'll be looking into it next, but I wanted to post the question as-is in case someone has another lead. $\endgroup$ – Illya Moskvin Feb 6 '16 at 1:32
  • $\begingroup$ Tentatively adding computer-vision tag, since I believe that creating a solution for this problem may require computer vision methods. $\endgroup$ – Illya Moskvin Feb 8 '16 at 1:08
  • $\begingroup$ Presently working on a solution using Adrian Rosebrock's multi-scale template matching article as a guide. I know there are other methods, but I'm new to computer vision, and this seems like a good start. $\endgroup$ – Illya Moskvin Feb 9 '16 at 1:59
  • $\begingroup$ Got it working for downscaled thumbnails using iterative scaling and template matching. Hitting within 0-4px of the original values with 50-100 iterations. I want to take a while to improve the algorithm to require fewer iterations (e.g. get best-matching scale, iterate between the two scales higher and lower than it, repeat until it would be unreasonable to continue), run some accuracy and speed benchmarks, as well as add back the CLI commands I removed while experimenting. I might add support for upscaled thumbnails too. Should take about a week. $\endgroup$ – Illya Moskvin Feb 11 '16 at 15:17
  • $\begingroup$ You can use feature detectors. You find a set of keypoints and descriptors for the two images, then you try to match them up. Many of these algorithms have scale in-variance built right in so there is no need to iterate over various sized images. If you have matlab you can do a very quick proof of concept mathworks.com/help/vision/ref/matchfeatures.html FOr open cv here is a full coded example using FLANN descriptors docs.opencv.org/2.4/doc/tutorials/features2d/… and other types of features goo.gl/ZF0sXR $\endgroup$ – andrew Feb 16 '16 at 17:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.