Inefficient code

[Bill Marriott]

Bert,

Others have pointed out the delay introduced by updating a progress bar with 
every pixel and suggested updating it every 100 or 500 pixels or so. 
Similarly, comparing byte-by-byte is going to be slow.

An immediate, simple improvement will be achieved by comparing *groups* of 
pixels between the two images. For example, if your image is 10,000 bytes in 
size, comparing 500 bytes at a time results in 20 comparisons instead of 
10,000 comparisons. As you find differences in a block of 500 bytes, you can 
then down-shift to find the differences within that 500-byte block with more 
granularity.

A refinement on this approach is simply to "divide and conquer" by 
constantly dividing the image by half and recursively testing the halves for 
differences. If the differences between the two images are small, the 
comparison can be near-instant.

One of the classic papers on checking for differences between data sets can 
be found here:

http://xmailserver.org/diff2.pdf

Of course, the language in that paper is way beyond my comprehension ;)

I'll putter around with expressing these concepts elegantly in Rev, but 
hopefully this gives you or someone else on the list a starting point for an 
algorithm that is dramatically faster than byte-for-byte testing. (I'd love 
to see the "O(ND)" difference algorithm properly implemented in Rev code.)

- Bill



"Bert Shuler" <bertshuler at yahoo.com> wrote in 
message news:C226BC83-61AC-4267-A24C-E32C8C7CE1F8 at yahoo.com...
>I have written this code a few different ways. Each seems to be  equally 
>inefficient. I am attempting to compare to images, pixel by  pixel, and 
>record the differences.
>
> ON mouseUp pMouseBtnNo
>     put 0 into c
>     set the startvalue of scrollbar Progress to 0
>     set the endvalue of scrollbar Progress to the length of imagedata  of 
> image "Alpha"
>     put the imagedata of image "Alpha" into idataalpha
>     put the imagedata of image "Beta" into idatabeta
>     REPEAT FOR each char myChar in idataalpha
>         set the thumbposition of scrollbar Progress to c
>         IF myChar is not  char (c) of idatabeta THEN
>             put c && char (c) of idatabeta & return after hAll
>         END IF
>         put c+1 into c
>     END repeat
>     put hAll into field "diff"
> END mouseUp
>
> It takes many minutes to process a 200x200 image. I want this code to 
> eventually compare full screen-captures, so if there is any way to  speed 
> it up, I am open for advice.
>
> Thanks
>
> Bert
> _______________________________________________
> use-revolution mailing list
> use-revolution at lists.runrev.com
> Please visit this url to subscribe, unsubscribe and manage your 
> subscription preferences:
> http://lists.runrev.com/mailman/listinfo/use-revolution
>