We have a photo fragment. How to find its coordinates on the full photo?

Question

JavaScript

There is a fragment of a photo (image 1).
There is a full photo (image 2).
What is the easiest way to get the coordinates of this fragment on a full photo?
The proportions are the same, no processing took place.

Answer 1

If a fragment is strictly pixel-by-pixel identical to a piece of a large image, then everything is simple.
The first row of pixels of the fragment is taken and its entry into the rows of pixels of the source is checked.
That is, it is actually the task of finding a substring in a large string. This is a superclassical task, tons of scientific papers have been written on it, hundreds of optimized algorithms have been developed, many are implemented in libraries. Yes, even Wikipedia can be viewed:
https://ru.wikipedia.org/wiki/%D0%9F%D0%BE%D0%B8%D...
If found, subsequent rows are checked.
Now, if the entry is not strict (for example, the fragment is scaled, or the brightness does not match, or it's just a little jpeg-recompressed) - then everything is much more complicated.

Answer 2

https://ru.wikipedia.org/wiki/Correlation_digital_...
and further google on the topic

Answer 3

It is clear that you need to start with large objects.
In this example, these are: sky, sand and water.
1. Search for the line of borders of large objects (stroke) and find significant "points" (circular area with automatic radius): those where the line bends uniquely.
2. We compare these points on the fragment and the full image, using the rotations of only these small circular areas in b/w mode.
3. If any two of them match (a fragment with a full image), we immediately know the exact coordinates of the desired fragment in the full image.

Answer 4

I'll contribute to obfuscate...
It's pure mathematics with the theory of probability (it seems) and numerical methods.
You take the hash of the fragment and compare it with the hash of the sections of the full photo.
There are programs for 3-D panoramas that stitch flat photos into a three-dimensional image. The same principles.

Answer 5

opencv surf
Since there is nodejs in the tags, you can use https://www.npmjs.com/package/opencv4nodejs

Answer 6

Let's get the most hardcore production right away. The image has been scaled. That is, a pixel-by-pixel comparison will not give you anything. Something smarter is needed.

Answer 7

Another tip is to pre-shrink the image both proportionally and do it with a gray gradient, this will speed up the preliminary search and then refine the edges