Board index » delphi » Find images count in a bigger image...

Find images count in a bigger image...

Hi,
I have taken a image from another window which do not belong to my
application and contains a lot of smaller images(like parts of a chess
desk).What I want to do is get the count of the smaller images within the
the big image(in other words to get the count of the equal looking cells
within the chess grid). I thought when I have the smaller image I can
somehow compare pixels but that seems to be a bad idea. I have no experince
with graphics so I thought it will be better to ask.
Any better ideas,examples,components are welcome.
Thanks

---
Vladimir Alexandrov
Sweden
ICQ# 86729605
<www.f1portal.net>
< F1REM - the best F1 manager game>

 

Re:Find images count in a bigger image...


Quote
> I have taken a image from another window which do not belong to my
> application and contains a lot of smaller images(like parts of a chess
> desk).

Question: Are those images all the same (exactly identical)? If you know
how the image you are searching for looks like, it is relatively easy.
Something like (pseudo code)...

Found := 0;
for y := 0 to BigImage.Height-SmallImage.Height-1 do begin
  for x := 0 to BigImage.Width-SmallImage.Width-1 do begin
    if BigImage.Pixels[x,y] = SmallImage.Pixels[0,0] then begin
      OneMore := true; // might be one more
      y2 := 0;
      while OneMore AND (y2 < SmallImage.Height) do begin
        x2 := 0;
        while OneMore AND (x2 < SmallImage.Width) do begin
          // maybe following is faster (???):
          // while x2 < SmallImage.Width do begin
          // more pixels are checked but less comparisons
          Inc (x2);
          if BigImage.Pixels[x+x2,y+y2] <> SmallImage.Pixels[x2,y2] then
OneMore := False;
        end;
        Inc (y2);
      end;
      if OneMore then Inc (Found);
    end;
  end;
end;

I have not tested this algorithm!

Jens

Re:Find images count in a bigger image...


Thanks for the answer Jens!
I tryed your suggestion but could not get it to work.(maybe because I do not
understand the idea of the algorithm as I am new to graphics handling using
Delphi)

Maybe I can make myself clearer in what I want. I have a small 30x30 pixels
image and one bigger 800x600 image which should contain occurences of the
smaller image. I want to find how many times the big image contains the
small one.
(All the images are bitmaps)
Here is what I tryed to do with the algorithm you supplied:

procedure TForm1.Button1Click(Sender: TObject);
var x,x2,y,y2,found:integer;
      onemore:boolean;
begin
Found := 0;
screen.Cursor:=crhourglass;
for y := 0 to
BigImage.Picture.Bitmap.Height-SmallImage.Picture.Bitmap.Height-1 do begin
  for x := 0 to
BigImage.Picture.Bitmap.Width-SmallImage.Picture.Bitmap.Width-1 do begin
    if BigImage.Picture.Bitmap.Canvas.Pixels[x,y] =
SmallImage.Picture.Bitmap.Canvas.Pixels[0,0] then begin
      OneMore := true; // might be one more
      y2 := 0;
      while OneMore AND (y2 < SmallImage.Picture.Bitmap.Height) do begin
        x2 := 0;
        while OneMore AND (x2 < SmallImage.Picture.Bitmap.Width) do begin
          // maybe following is faster (???):
          // while x2 < SmallImage.Width do begin
          // more pixels are checked but less comparisons
          Inc (x2);
          if BigImage.Picture.Bitmap.Canvas.Pixels[x+x2,y+y2] <>
SmallImage.Picture.Bitmap.Canvas.Pixels[x2,y2] then
OneMore := False;
        end;
        Inc (y2);
      end;
      if OneMore then Inc (Found);
    end;
  end;
end;
screen.Cursor:=crdefault;

showmessage(inttostr(found));
end;

Can you take a look at it and see what is wrong?
Aren't there any better and easier solutions maybe using ScanLine or any
components that can help?

Thanks
---
Vladimir Alexandrov
Sweden
ICQ# 86729605
<www.f1portal.net>
< F1REM - the best F1 manager game>

Re:Find images count in a bigger image...


Hi Vladimir,

As long as you're looking for *exactly identical* parts in the image,
there's definitely faster methods.

1) First of all, change all Pixels[x,y] to Scanline routines.

2) Since you are looking for occurance of a certain sequence:

Suppose that your first scanline (top pixel row of the small image) is
[13 255 14 0 15 254 15 ... etc ]

You will want to find the occurrance of this "search string" inside the
complete "string" of your main image. Once you found it, there's a fat
chance that this occurrance is another one of your pictures.

How to do that? The approach by Jens is the "classical search algorith". But
it is not very fast. Look up "Boyer Moore" to get an idea of what *is* fast.
There's a component called

FastStrings by Peter Morris, found on www.stuckindoors.com

where you can find an example of the Boyer Moore algorithm. You will have to
manipulate a bit to get it done, but once you have, you'll see an incredible
improvement in speed.

If you want to find occurances that are *similar*, then you need to consider
completely different methods. This goes much more into the "pattern
matching" technology. Depending on your image, you would perhaps want to
find the edges instead of the image itself (e.g. the checkers checkboard
vertical and horizontal edges). Convert your picture to a gradient picture
and try to find the boundaries.

By the way, if you want to play an intelligent version of the checkers game
then you can download a free one at my site (it's the Dutch variant Dammen):
http://www.abc-view.com/dampc.html

(grin)

Nils
www.abc-view.com

Quote
Vladimir Alexandrov <valexandrovNOS...@hotmail.com> wrote in message

news:3ca35b6f_2@dnews...
Quote
> Thanks for the answer Jens!
> I tryed your suggestion but could not get it to work.(maybe because I do
not
> understand the idea of the algorithm as I am new to graphics handling
using
> Delphi)

> Maybe I can make myself clearer in what I want. I have a small 30x30
pixels
> image and one bigger 800x600 image which should contain occurences of the
> smaller image. I want to find how many times the big image contains the
> small one.
> (All the images are bitmaps)

Re:Find images count in a bigger image...


Hi Nils,
Thanks for the great info.
I tryed to make what I want using ScanLine. But I have a bit stupid
question:
How do I make the bitmap to a string? And also how do I get from ScanLine to
the string which I will search for in the complete string of the main image.
I have never used ScanLine and in the help there is just a very simple
example which didn't help me a lot. I will try to search google and other
sites to see if I will find some examples.

Thanks.
---
Vladimir Alexandrov
Sweden
ICQ# 86729605
<www.f1portal.net>
< F1REM - the best F1 manager game>

Quote
"Nils" <n.ha...@quicknet.nl> wrote in message news:3ca36c96_2@dnews...
> Hi Vladimir,

> As long as you're looking for *exactly identical* parts in the image,
> there's definitely faster methods.

> 1) First of all, change all Pixels[x,y] to Scanline routines.

> 2) Since you are looking for occurance of a certain sequence:

> Suppose that your first scanline (top pixel row of the small image) is
> [13 255 14 0 15 254 15 ... etc ]

> You will want to find the occurrance of this "search string" inside the
> complete "string" of your main image. Once you found it, there's a fat
> chance that this occurrance is another one of your pictures.

> How to do that? The approach by Jens is the "classical search algorith".
But
> it is not very fast. Look up "Boyer Moore" to get an idea of what *is*
fast.
> There's a component called

> FastStrings by Peter Morris, found on www.stuckindoors.com

> where you can find an example of the Boyer Moore algorithm. You will have
to
> manipulate a bit to get it done, but once you have, you'll see an
incredible
> improvement in speed.

> If you want to find occurances that are *similar*, then you need to
consider
> completely different methods. This goes much more into the "pattern
> matching" technology. Depending on your image, you would perhaps want to
> find the edges instead of the image itself (e.g. the checkers checkboard
> vertical and horizontal edges). Convert your picture to a gradient picture
> and try to find the boundaries.

> By the way, if you want to play an intelligent version of the checkers
game
> then you can download a free one at my site (it's the Dutch variant
Dammen):
> http://www.abc-view.com/dampc.html

> (grin)

> Nils
> www.abc-view.com

Re:Find images count in a bigger image...


There are some very good scanline examples on Earl F. Glynn's site.

Nils
www.abc-view.com

Quote
Vladimir Alexandrov <valexandrovNOS...@hotmail.com> wrote in message

news:3ca4a862_1@dnews...
Quote
> Hi Nils,
> Thanks for the great info.
> I tryed to make what I want using ScanLine. But I have a bit stupid
> question:
> How do I make the bitmap to a string? And also how do I get from ScanLine
to
> the string which I will search for in the complete string of the main
image.
> I have never used ScanLine and in the help there is just a very simple
> example which didn't help me a lot. I will try to search google and other
> sites to see if I will find some examples.

> Thanks.
> ---
> Vladimir Alexandrov
> Sweden

Re:Find images count in a bigger image...


Quote
> There are some very good scanline examples on Earl F. Glynn's site.

Many thanks, I will take a look at it.

---
Vladimir Alexandrov
Sweden
ICQ# 86729605
<www.f1portal.net>
< F1REM - the best F1 manager game>

Other Threads