|
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
|
|
|
|
|
I need help on how to develop an sms web portal
|
|
|
|
|
Try this: www.ozekisms.com
|
|
|
|
|
Hi all,
I have a generic class internal static class Singleton<T> where T : class. Within the class I declare the following private field private static T _instance;.
Within the generic class contructor I perform the following actions:
Type type = typeof(T);
BindingFlags searchPattern = BindingFlags.NonPublic | BindingFlags.Public | BindingFlags.Instance;
ConstructorInfo constructor = type.GetConstructor(searchPattern, null, Type.EmptyTypes, null);
if (constructor == null)
{
string errorMsg = String.Format("The type {0} does not have a default constructor.", type.FullName);
throw new ArgumentNullException(errorMsg);
}
_instance = (T)constructor.Invoke(new object[0]);
To make use of the class I perform the following line of code:
Singleton < ApplicationProtector > ...
The class ApplicationProtector has a static field within it called expType which is a enum.
How can I make use of this static field expType after creating the instance of the object in the generic class (only when actually running the application and debugging it, can I see the field value which foems part of the _instance):
<br />
...<br />
_instance = (T)constructor.Invoke(new object[0]);<br />
...
The only programmers that are better C# programmers, are those who look like this -> ![Green Alien | [Alien]](https://codeproject.global.ssl.fastly.net/script/Forums/Images/alien.gif) |
Programm3r
My Blog: ^_^
|
|
|
|
|
er...
ApplicationProtector.expType - the same way you would always reference a static member.
Am I missing something? 
|
|
|
|
|
er ... ??
Thanks for the response but....
internal static class Singleton<T> where T : class
{
private static T _instance;
static Singleton()
{
Type type = typeof(T);
BindingFlags searchPattern = BindingFlags.NonPublic | BindingFlags.Public | BindingFlags.Instance;
ConstructorInfo constructor = type.GetConstructor(searchPattern, null, Type.EmptyTypes, null);
if (constructor == null)
{
string errorMsg = String.Format("The type {0} does not have a default constructor.", type.FullName);
throw new ArgumentNullException(errorMsg);
}
_instance = (T)constructor.Invoke(new object[0]);
}
}
| The only programmers that are better C# programmers, are those who look like this -> |
Programm3r
My Blog: ^_^
|
|
|
|
|
Forget about generics, by trying to use an enum defined in that class where you're trying to use it, you've defeated the purpose of your generic singleton wrapper!
What are you trying to achive? The class you've defined should be totally agnostic of the T passed it. It should not need to access any enum in one of the classes. All it should do is attempt to instantiate any class which can be used as a singleton.
|
|
|
|
|
|
First thing i'd do if I were you is go and read up on the singleton design pattern. The class you have found/written is for that purpose, and that purpose alone. You may have accidentally stumbled upon a tried-and-tested pattern of software design. Thats usually how you come accross such things and will make you a better programmer.
In answer to your question, you would use the fields/methods of your class as follows - assume the "T" passed in is the class MyClass which has an instance method void Foo() and an instance property int Bar.
Singleton<MyClass> singleton = new Singleton<MyClass>();
singleton.Instance.Foo();
singleton.Instance.Bar = 5
Crucially, you would never access a static property/method on MyClass, only instance properties/methods. Thats by convention of course, as I stated originally there is nothing stopping you referencing a static member, MyClass.StaticProperty
|
|
|
|
|
I will keep that in mind. Many thanks for your patience and help.
Kind regards,
| The only programmers that are better C# programmers, are those who look like this -> |
Programm3r
My Blog: ^_^
|
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
