How i can search small image on big image and get x,y coords of small image?

Dev Shed Forums Sponsor:

November 19th, 2012, 03:14 PM

lapdx

Registered User

Join Date: Nov 2012

Posts: 2

Time spent in forums: 7 m 42 sec
Reputation Power: 0

How i can search small image on big image and get x,y coords of small image?

How i can search small image on big image and get x,y coords of small image?

November 19th, 2012, 04:26 PM

b49P23TIvg

Contributing User

Join Date: Aug 2011

Posts: 3,383

Time spent in forums: 1 Month 2 Weeks 3 Days 13 h 44 m 42 sec
Reputation Power: 383

I solved an image stitching problem in this thread.

__________________
[code]Code tags[/code] are essential for python code!

November 19th, 2012, 07:34 PM

BobS0327

Contributing User

Join Date: Oct 2012

Posts: 118

Time spent in forums: 3 Days 18 h 48 m 29 sec
Reputation Power: 44

Quote:

Originally Posted by lapdx

How i can search small image on big image and get x,y coords of small image?

What is the format of the image? BMP, JPG, GIF TIF PNG etc.

November 20th, 2012, 01:29 AM

lapdx

Registered User

Join Date: Nov 2012

Posts: 2

Time spent in forums: 7 m 42 sec
Reputation Power: 0

JPG - format.

Well. We have big image. We want search coords of small image. Small image be in big image.

c++

November 20th, 2012, 02:50 AM

Lux Perpetua

Contributing User

Dev Shed Intermediate (1500 - 1999 posts)

Join Date: Feb 2004

Location: San Francisco Bay

Posts: 1,936

Time spent in forums: 1 Month 1 Week 2 h 12 m 42 sec
Reputation Power: 1312

Simple way: iterate over all possible positions of the small image in the big image and see how well the small image matches at that position. Evaluating the match requires iterating over all pixel positions in the small image. The resulting loop looks something like this:

Code:

double best_score = HUGE_VAL;
for (int y = 0; y + small_h <= big_h; ++y) {
    for (int x = 0; x + small_w <= big_w; ++x) {
        double score = 0;
        for (int s = 0; s < small_h; ++s) {
            for (int r = 0; r < small_w; ++r) {
                double diff = small_image[s][r] - big_image[x+s][y+r];
                score += diff*diff;
            }
        }
        if (score < best_score) {
            best_score = score;
            // Also keep track of the matching position here
        }
    }
}

How well this works depends on how good the "match" really is. If it's a near-exact match, then you'll almost surely find it, but life is more complicated if the match is just approximate (for example, if you're trying to match one photograph to a different photograph). This fuzzy version of the problem is still a topic of active research, but I think there are various implementations in some popular image processing and computer vision libraries (like OpenCV).

One other thing I should point out is that if you decide to use the simple computation and the images in question are sufficiently large, and especially if the small image is not very small, it can pay to go through the Fourier domain rather than directly implementing the four-level nested loop. If you don't know what I'm talking about, then I'm afraid I can't explain it in a forum post; you should just do it the simple way or find an existing implementation (or learn about the Fourier transform and convolutions).

November 20th, 2012, 04:59 AM

mitakeet

I'm Baaaaaaack!

Dev Shed God 1st Plane (5500 - 5999 posts)

Join Date: Jul 2003

Location: Maryland

Posts: 5,538

Time spent in forums: 2 Weeks 4 Days 2 h 38 m 46 sec
Reputation Power: 242

I have a good friend who recently took classes on image analysis and while there are some basic ways to do analysis, anything 'simple' is seldom realized in the real world and getting something useful entails a massive number of tradeoffs, not the least of which is performance. These sorts of algorithms tend to be highly compute bound and sometimes are very difficult to multi-thread (and see a performance gain). I think, unless you have a highly specific application and are prepared to dive into the math and algorithms, you are way better served by learning to use a package (such as the afore mentioned OpenCV).

__________________

My blog, The Fount of Useless Information http://sol-biotech.com/wordpress/
Free code: http://sol-biotech.com/code/.
Secure Programming: http://sol-biotech.com/code/SecProgFAQ.html.
Performance Programming: http://sol-biotech.com/code/PerformanceProgramming.html.
LinkedIn Profile: http://www.linkedin.com/in/keithoxenrider

It is not that old programmers are any smarter or code better, it is just that they have made the same stupid mistake so many times that it is second nature to fix it.
--Me, I just made it up

The reasonable man adapts himself to the world; the unreasonable one persists in trying to adapt the world to himself. Therefore, all progress depends on the unreasonable man.
--George Bernard Shaw

How i can search small image on big image and get x,y coords of small image?

Developer Shed Advertisers and Affiliates