|
Then check how to configure the .NET Security and assign permissions. Sorry I was so busy in ASP.NET stuff that I didn't realized that you are asking for something with windows application 
|
|
|
|
|
Hello.
I have two Bitmaps. I know that the small one is contained within the big one, and I want to search for it and return its position (a Rectangle):
public Rectangle findBitmap(Bitmap smallBmp, Bitmap bigBmp);
I can do this by making lots of pixel comparations in nested fors, but obviously it's too time-consuming since there can be literally hundreds of thousands of comparations. I need a *very* fast way to do this.
I've been reading for a while about Template Matching and I think it could be the way, but it's a difficult subject and I have not found any example or code that could help me. Could you please give me some advice?
Thanks in advance.
|
|
|
|
|
|
Thank you, I will read them all, specially the Image Processing for Dummies series. 
|
|
|
|
|
OK, I've been reading those articles for a while. They are all very interesting and will use them in a future, but they focus on image filtering. There are nothing about finding a Bitmap in another Bitmap, which is what I need. :-/
So I still need help...
|
|
|
|
|
verence333 wrote: for a while
30min = a while?
I guess you skimmed them and saw they where not about what you want/need.
Your best bet would be to wait for CG to pass by or to ask him.
He knows far more about this kind of stuff than I do.
|
|
|
|
|
Yes, a while. There's no need of in-depth reading how to transform an image when what I want is looking for a bitmap inside that image, and the algorithms are very similar in all the examples. Anyway, you're right and I must read them carefully when I have the time: maybe something could be done from the methods used to analyze the surrounding pixels of a given pixel.
I would like to ask CG, but someone already asked him about an algorithm to eliminate red eyes (something that I think would be similar to what I need, since it envolves looking for a pattern through an image) and CG answered that he never did it before.
I'm amazed that so few people has had this problem before. There are lots of possible applications that could be done with such an algorithm, I thought there would be plenty of solutions out there...
|
|
|
|
|
verence333 wrote: I would like to ask CG, but someone already asked him about an algorithm to eliminate red eyes (something that I think would be similar to what I need, since it envolves looking for a pattern through an image) and CG answered that he never did it before.
Don't know how long ago that was but it never hurts to ask. (well as long as you stay professional and polite it doesn't hurt  )
verence333 wrote: I'm amazed that so few people has had this problem before. There are lots of possible applications that could be done with such an algorithm, I thought there would be plenty of solutions out there...
Well I guess it's one of those things that not many people have to do. My job currently doesn't allow for stuff like this so...
|
|
|
|
|
You're right, of course; I will ask him.
|
|
|
|
|
Assuming your small bitmap is really *identical* to a section of your big bitmap (and not just something that *looks* the same) then basically you just want to perform a similar search to finding a substring within a string.
As you mentioned, you can brute force it with nested fors, or you can use a bit of smarts - you should be able to adapt an existing String searching algorithm[^] to search your pixel data instead
|
|
|
|
|
Yes, the bitmap is really identical. What you say about adapting a String searching algorithm seems to be a good idea, thanks!
|
|
|
|
|
Hi verence,
I think what you need is a convolution integral.
I´m not sure (some years ago...) but I think it´s done by transforming both pictures to Fourier space and do a multiplication. In the result you search for the maximum and at that point is the center of your best match (you already know the size, should be the same as the small picture).
If you have no idea of higher mathematics this will be a hard job but I´m sorry I also don´t know more (e. g. code or good web sites that might help you). Try Google with the hints I gave you....
Bye
Thomas
|
|
|
|
|
Hi!
I know something about convolutions (I have an university degree in Telecommunications), although I should rescue my notes... Yours seems to be a perfectly suitable idea!, maybe it's the best way to achieve this (if the method to use Fourier transforms is fast; in Matlab there are methods to do FFT that are very fast so I think there should be possible with C#). I will invest some time searching for code...
Thank you!
|
|
|
|
|
If you really decide to use convolutions I would say that would be worth writing an article about it...
Bye and good luck
Thomas
|
|
|
|
|
Yes, I think I would do so (although my English is, you know, horrible). I hope to have some time this week to investigate this...
|
|
|
|
|
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.
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.
|
|
|
|
|
 Wow! Thank you so much for your detailed answer!
Your assumptions in 1) are correct. Well, they could be synthetic pictures, but only one match is expected.
I must read your message (more times, I've read it three times) slowly and carefully: English is not my mother tongue (obviously); I'm rather new in C# (I usually work with Java); and I've never made complex operations with Bitmaps before, so I have to read about hashing and histogramming them.
But many of the things you say are very useful and will help me to make a method myself rather than copy such-and-such code from anywhere. After all, I'm here to learn. 
I think I will first try to make that method (implementing some of your suggestions, specially 5. and 6b.), accessing pixels in an unsafe way like CG does in his articles (not using GetPixel() nor SetPixel()) for quickness, and see how it works.
It will take some days, I'm making it for myself and not for my boss. But, when I have something, I will let you all know.
Thank you guys! You are so helpful!
|
|
|
|
|
Hi,
good luck.
Java and C# are pretty close to each other.
of course you don't use GetPixel; use pointers, it is the number one example for a pointer application.
and store bitmap dimensions in local variables, don't call Bitmap.Width or Height all the time!
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.
|
|
|
|
|
Thank you! Yep, learning C# is being very easy (I would say that it's even easier than Java), and it's very useful for creating desktop applications, that's why I'm learning it. The productivity is awesome!
I'll try to remove GetPixel from everywhere in my app; not so easy (I'm having problems with nested fors, the inner one trying to lock bits that are already locked by the outer one), but I'm on it...
|
|
|
|
|
verence333 wrote: I'm having problems with nested fors, the inner one trying to lock bits that are already locked by the outer one
That does not make much sense, you should lock the data of the entire image once, then enter your loop(s).
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.
|
|
|
|
|
Yup, but the inner loop calls a function that tries to lock the bits, so I have to either modify it (and every reference to it) or create a new one that doesn't lock them. Anyway it's a minor problem. Thank you again!
|
|
|
|
|
I've made a little method to find a Bitmap inside another one. It's fast enough for what I want. Obviously, the elapsed time depends on the size of the Bitmaps, but it takes about 15-30 ms. to find a small one (like a window button inside a Bitmap of a window, for instance) and 150-180 ms. to find a big one (like a window inside a capture of the screen).
I will try to program other strategies that we've been talking about, specially the convolution alternative (which I think would probably be the fastest if done the right way). In the meanwhile, here is the code so you can tell me your comments and suggestions, hoping that it will help anybody that has the same problem (I really did not find any method like this one anywhere on the Internet).
The method receives a small Bitmap which is expected to be contained in another, bigger Bitmap. It returns a Point which represents the upper left corner of the wanted location.
Note that, if the small Bitmap is not contained in the bigger one, it returns a Point(0,0), exactly the same as if it was contained in such a position. This can and should be easily improved, and I would like to read your comments about other improvements (specially concerning the speed issue) since I'm rather new in C# and I usually work with Java.
Thank you!
private Point searchBitmap(Bitmap smallBmp, Bitmap bigBmp)
{
BitmapData smallData = smallBmp.LockBits(new Rectangle(0, 0, smallBmp.Width, smallBmp.Height), System.Drawing.Imaging.ImageLockMode.ReadOnly, System.Drawing.Imaging.PixelFormat.Format24bppRgb);
BitmapData bigData = bigBmp.LockBits(new Rectangle(0, 0, bigBmp.Width, bigBmp.Height), System.Drawing.Imaging.ImageLockMode.ReadOnly, System.Drawing.Imaging.PixelFormat.Format24bppRgb);
int smallStride = smallData.Stride;
int bigStride = bigData.Stride;
int bigWidth = bigBmp.Width;
int bigHeight = bigBmp.Height;
int smallWidth = smallBmp.Width * 3;
int smallHeight = smallBmp.Height;
Point location = new Point(0, 0);
unsafe
{
byte* pSmall = (byte*)(void*)smallData.Scan0;
byte* pBig = (byte*)(void*)bigData.Scan0;
int smallOffset = smallStride - smallBmp.Width * 3;
int bigOffset = bigStride - bigBmp.Width * 3;
bool matchFound = true;
for (int y = 0; y < bigHeight; y++)
{
for (int x = 0; x < bigWidth; x++)
{
byte* pBigBackup = pBig;
byte* pSmallBackup = pSmall;
for (int i = 0; i < smallHeight; i++)
{
int j = 0;
matchFound = true;
for (j = 0; j < smallWidth; j++)
{
if (pBig[0] != pSmall[0])
{
matchFound = false;
break;
}
pBig++;
pSmall++;
}
if (!matchFound) break;
pSmall = pSmallBackup;
pBig = pBigBackup;
pSmall += (smallWidth + smallOffset) * (1 + i);
pBig += (bigWidth * 3 + bigOffset) * (1 + i);
}
if (matchFound)
{
location.X = x;
location.Y = y;
break;
}
else
{
pBig = pBigBackup;
pSmall = pSmallBackup;
pBig+=3;
}
}
if (matchFound) break;
pBig += bigOffset;
}
}
bigBmp.UnlockBits(bigData);
smallBmp.UnlockBits(smallData);
return location;
}
|
|
|
|
|
hi
how can i convert an color image in to black & white
tell me plzzzzzzzzzz
|
|
|
|
|
shekhar258395 wrote: how can i convert an color image in to black & white
Lots of example here[^]
Manas Bhardwaj
Please remember to rate helpful or unhelpful answers, it lets us and people reading the forums know if our answers are any good.
|
|
|
|
|
If your pictures are small you can try the code below, but its performance poor.
public Image BW(Bitmap bmp)
{
for (int i = 0; i < bmp.Width; i++)
{
for (int j = 0; j < bmp.Height; j++)
{
int hede = (bmp.GetPixel(i, j).R + bmp.GetPixel(i, j).G + bmp.GetPixel(i, j).B) / 3;
bmp.SetPixel(i, j, Color.FromArgb(hede, hede, hede));
}
}
return bmp;
}
Instead of using this method try to google for an algorithm
|
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
