Click here to Skip to main content
11,481,404 members (64,336 online)
   

C#

 
QuestionHow can I find a Bitmap within another Bitmap? Pin
verence33323-Jul-09 2:12
memberverence33323-Jul-09 2:12 
AnswerRe: How can I find a Bitmap within another Bitmap? Pin
Tom Deketelaere23-Jul-09 2:46
memberTom Deketelaere23-Jul-09 2:46 
GeneralRe: How can I find a Bitmap within another Bitmap? Pin
verence33323-Jul-09 3:00
memberverence33323-Jul-09 3:00 
GeneralRe: How can I find a Bitmap within another Bitmap? Pin
verence33323-Jul-09 3:26
memberverence33323-Jul-09 3:26 
GeneralRe: How can I find a Bitmap within another Bitmap? Pin
Tom Deketelaere23-Jul-09 4:01
memberTom Deketelaere23-Jul-09 4:01 
GeneralRe: How can I find a Bitmap within another Bitmap? Pin
verence33323-Jul-09 4:11
memberverence33323-Jul-09 4:11 
GeneralRe: How can I find a Bitmap within another Bitmap? Pin
Tom Deketelaere23-Jul-09 4:17
memberTom Deketelaere23-Jul-09 4:17 
GeneralRe: How can I find a Bitmap within another Bitmap? Pin
verence33323-Jul-09 21:32
memberverence33323-Jul-09 21:32 
AnswerRe: How can I find a Bitmap within another Bitmap? Pin
benjymous23-Jul-09 5:09
memberbenjymous23-Jul-09 5:09 
GeneralRe: How can I find a Bitmap within another Bitmap? Pin
verence33323-Jul-09 21:34
memberverence33323-Jul-09 21:34 
AnswerRe: How can I find a Bitmap within another Bitmap? Pin
ThomasManz23-Jul-09 7:30
memberThomasManz23-Jul-09 7:30 
GeneralRe: How can I find a Bitmap within another Bitmap? Pin
verence33323-Jul-09 21:41
memberverence33323-Jul-09 21:41 
GeneralRe: How can I find a Bitmap within another Bitmap? Pin
ThomasManz24-Jul-09 6:16
memberThomasManz24-Jul-09 6:16 
GeneralRe: How can I find a Bitmap within another Bitmap? Pin
verence33326-Jul-09 21:00
memberverence33326-Jul-09 21:00 
AnswerRe: How can I find a Bitmap within another Bitmap? [modified] Pin
Luc Pattyn23-Jul-09 7:59
mvpLuc Pattyn23-Jul-09 7:59 
Hi,

here are some ideas, trying not to use much extra memory:

1.
I will assume the small bitmap "bmSmall" indeed is an exact subset of the larger one, no rescales, no resampling, no color shifts; I will also assume lots of different colors are present, and there is exactly one match (so no checker board situations, and preferably real pictures, not synthetic ones)
2.
if bmSmall had a single pixel in a very particular color C1, then all it would take is scan the large bitmap bmLarge for C1. If only one is found, that must be it. If multiple, each is a candidate, now check other pixels at some distance (dx,dy) from the matching one.
3.
Q: how to find C1?
A: I don't recommend histogramming 32-bit colors, so I would suggest hashing the colors to a smaller number (I would prefer 12 bits, maybe 8 works well enough, say B bits) and then histogramming those, by counting their occurence in an array of size 2^B). This takes a single scan of the bmSmall.
4.
Q: What hashing function?
A: A fast one; if going for 8-bit result XOR red,green,blue,alpha (or add ignoring overflow); if going for 12-bit, add red,green,blue,alpha (that's 10 bits actually). And not a real method, just one line of inline code!
5.
Now scan the bmLarge, comparing each pixel with C1; on a match perform a full bitmap compare, don't do that in the classic order though, step through rows and columns in a smart way, say x=(x+prime) modulo width, and y=(y+prime) modulo height, so you aren't first checking all adjacent pixels and probability increases you don't get caught by a part of the bitmaps locally being identical.
[EDIT] Make sure the primes don't evenly divide width or height [/EDIT]
6.
Obvious refinements:
6a. a second special color
- while histogramming, build a second array of size 2^B, holding the last Point found with that color.
- choose a second color C2, the next most special color in bmSmall, and calculate the distance DIST from the last C1 pixel to the last C2 pixel
- now when a C1 match is found at pointLarge1, go check for C2 at pointLarge1+DIST
that reduces the probability of an accidental match
6b. ignore part of bmLarge while searching for C1
assuming one of the C1 pixels in bmSmall is at (x1,y1) there are four rectangles in bmLarge that you don't need to scan for C1: the regions where x<x1, or x>bmLargeWidth-(bmSmallWidth-x1), or similar for y.

[EDIT]
instead of using a second color C2, use C1 again, however build two arrays, one for first location, the other for last location (same memory cost, lower probability of a false hit, and bigger effect of 6b!)
[/EDIT]

==========================================================================================

Alternative strategy, using more memory; less dependent on image reality, would work for synthetics too.
However expected to be a lot slower.
1.
perform some transformation, both on bmSmall and bmLarge; the goal is to reduce their memory size so they become a smaller bmSmall2 and bmLarge2.
Example: replace 32-bit pixels by 8-bit pixels, using a hashing like before
with 1 byte/pixel, you can still address pixels easily, and either do a direct compare (nested loops), or apply the former strategy
2.
Extreme case: hash to a single bit per pixel (just store the least significant bit of the earlier hash);
with less than 1 byte/pixel the problem is bmSmall2 and bmLarge2 may have different byte boundaries (say bmSmall is located at bmLarge offset 7, anything but a multiple of 8)
3.
store 8 copies of bmSmall2, each shifted over 1 more pixel; now search for exact matches between those bmSmall2 and the one bmLarge2
minor problem: bmSmall2 and its shifted versions would have wrong boundary pixels (horizontally only), they would never match bmLarge2. Hence reduce width a bit so each bit is real pixel information.


That's it for now. Let us know what you decide and how it works out.

Smile | :)

Luc Pattyn [Forum Guidelines] [My Articles]

The quality and detail of your question reflects on the effectiveness of the help you are likely to get.
Show formatted code inside PRE tags, and give clear symptoms when describing a problem.

GeneralRe: How can I find a Bitmap within another Bitmap? Pin
verence33323-Jul-09 22:00
memberverence33323-Jul-09 22:00 
GeneralRe: How can I find a Bitmap within another Bitmap? Pin
Luc Pattyn24-Jul-09 2:13
mvpLuc Pattyn24-Jul-09 2:13 
GeneralRe: How can I find a Bitmap within another Bitmap? Pin
verence33324-Jul-09 3:12
memberverence33324-Jul-09 3:12 
GeneralRe: How can I find a Bitmap within another Bitmap? Pin
Luc Pattyn24-Jul-09 3:42
mvpLuc Pattyn24-Jul-09 3:42 
GeneralRe: How can I find a Bitmap within another Bitmap? Pin
verence33324-Jul-09 3:53
memberverence33324-Jul-09 3:53 
AnswerRe: How can I find a Bitmap within another Bitmap? Pin
verence33328-Jul-09 4:16
memberverence33328-Jul-09 4:16 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.


Advertise | Privacy | Mobile
Web04 | 2.8.150520.1 | Last Updated 24 May 2015
Copyright © CodeProject, 1999-2015
All Rights Reserved. Terms of Service
Layout: fixed | fluid