Abnormal behaviour of FIP_SCANPIXELS

[observer]

Hi,
I thought FIP_SCANPIXELS variable sets number of random pixels to scan.
But I don't think so now. And that is why:
Download these two images and run the script provided below.
________Needle__________________________________Haystack


So, set FIP_SCANPIXELS var to 10, 100, 200, 400, 1000 and try to explain the result.

Code: Select all

//Set the Needle and Haystack vars. Then run the script.

Let>Needle=
Let>Haystack=
Let>k=0
Let>f=0
Let>n=0
Label>Start
If>k=100,Finish
//
Let>FIP_SCANPIXELS=100
//
FindImagePos>%Needle%,%Haystack%,0,0,XArr,YArr,NumFound
If>NumFound>0
Let>k=k+1
Let>f=f+1
Goto>Start
Endif
Let>k=k+1
Let>n=n+1
Goto>Start

Label>Finish
MDL>Found=%f%%CRLF%NotFound=%n%

[gdyvig]

Hi observer,


If the FindImagePos algorithm were 100% accurate we would expect your needle to never be found because it contains a cursor at the extreme left. But with FIP_SCANPIXELS set too low we expect to find some false finds.

The needle is 156x15 pixels containing 2340 pixels.
The haystack is 425x211 pixels containing 89675 pixels.

You should modify you script to also show the average value of NumFound, if greater than 1 you are getting false finds.

Expected Results:
Found=0 NotFound=100 NumFound=0

Here are my results:

SCAN_PIXELS=10
Found=100 NotFound=0 NumFound ranges from 10 to 30.

SCAN_PIXELS=100
Found=45-55 NotFound=45-55 NumFound=0-1

SCAN_PIXELS=200
Found=20-30 NotFound=70-80 NumFound=0-1

SCAN_PIXELS=400
Found=8-10 NotFound=90-92 NumFound=0-1

SCAN_PIXELS=1000
Found=0 NotFound=100 NumFound=0

Next I removed the cursor from the needle file
No it is 155x15 pixels containing 2325 pixels

SCAN_PIXELS=10
Found=100 NotFound=0 NumFound ranges from 20 to 40.

SCAN_PIXELS=100
Found=100 NotFound=0 NumFound=1


Will add more results and conclusions later....


Gale

[gdyvig]

Hi observer,

I'm back.

With FIP_SCANPIXELS set very small, FIP was finding lots of patterns in the haystack that matched both for the good and bad needles. As we increased FIP_SCANPIXELS the number of false finds for the bad needle got lower and lower. For the good needle, we got only good finds for FIP_SCANPIXELS of 100 and above. This is as one would expect.

I was wondering what the correct interpretation of FIP_SCANPIXELS is. If it is set to 100 that could mean select 100 unique pixel locations or it could mean run a random number selector 100 times where duplicate pixels could be selected for a total of less than 100 pixels.

I did an experiment with a needle and a haystack that were both 5x5 and differed by only one pixel. I set FIP_SCANPIXELS to 25, 100, and 1000 and ran your script.

The Results:

SCAN_PIXELS=25, 100, 1000
Found=10-20 NotFound=80-90 NumFound=0-1
Same results in all three cases.

FIP is not scanning every pixel, so it must be the random number generator a maximum of 25 times, usually there will be duplicates so not every pixel is compared.

With this behavior, FIP usually finds needls OK if there are no other similar looking needles in the haystack. But for a precision search to distinguish almost identical needles requires an enhancement.

If FIP_SCANPIXELS is equal to or greater than the number of pixels in the needle, an exhaustive search should be done rather than FIP_SCANPIXELS number of random pixel selections performed.

If FIP_SCANPIXELS is greater than half the number of pixels in the needle, more accuracy could be achieved by randomly de-selecting TotalNeedlePixels-FIP_SCANPIXELS from the needle file.

By the way, I did not see the 1/3 coverage problem seen with CompareBitmaps reported in your other thread.


Gale

[observer]

Hi gdyvig!

... it contains a cursor at the extreme left

But... how... could you... detect the cursor?
It's so small...
Well, I need to check my eyes.
So, I confirm FIP_SCANPIXELS parameter is used correctly.

There are some comments about your investigation.

If FIP_SCANPIXELS is equal to or greater than the number of pixels in the needle, an exhaustive search should be done rather than FIP_SCANPIXELS number of random pixel selections performed.

That's right. In this case there is no need to use random number selector at all.

SCAN_PIXELS=25, 100, 1000
Found=10-20 NotFound=80-90 NumFound=0-1
Same results in all three cases.

You will be surprised, but I've got the same result with FIP_SCANPIXELS=0
So, your analysis means the chance of the false finds equals ~10-20% even if you set FIP_SCANPIXELS=TotalNeedlePixels. In other words, a user have no guarantee to get correct result of a search. I suppose this is a serious disadvantage.
I was wondering what time an exhaustive search is really taking. I had added a timer in my script. And then I had made a test with 1920x1200 Haystack-image and 100x100 Needle-image (also I had set FIP_SCANPIXELS=10000). The result is 15 seconds (or 150 milliseconds per search (as k=100)).
Not bad!
So, I agree with you. It would be a good idea to enhance a process of scan pixel selection.
It also would be useful to perform search with all pixels scanning if FIP_SCANPIXELS=Max (or may be FIP_SCANPIXELS=0).

[observer]

Hi gdyvig!
It's me again.
I had performed a test with CompareBitmaps command (instead of FindImagePos) with two images 5760x1200 (5760=3x1920 to eliminate CompareBitmaps rgb issue). The result is 69 seconds (or 690 milliseconds per comparison (as k=100)).
And we are still believe precise graphical comparison is too slow!

[gdyvig]

Hi Observer,

I think the FIP performance for an exact match for small images would be very acceptable and would remove any doubt of a mismatch.

To get an idea of how good the current algorithm is for more common scenarios, try your script like I did where the needle and the haystack are the same size. Vary the size of the files and the number of mismatched pixels to determine where statistically there is little chance of a mismatch.

I did that for my 5x5 images.

With 2 mismatched pixels I got a false match about 1% of the time. With 3 or 4 mismatched pixels a false match occurred less than 1 time in a thousand.

In practical usage, I found this sufficient to distinguish between on/off states of radio buttons and check boxes on screens you are likely to encounter. If you had a special case, like a screen with five thousand radio buttons and you were trying to find the one that is ON, there could be a significant chance finding one of the off buttons.


Gale