Inefficient code - Solutions

[BNig]

Bill,

I like the ideas to speed up the analysis of differences among 2 images. My
impression is that your approach with div 2 is leading to erroneous resutls
because by dividing by 2 you break the 4 byte blocks of imagedata. 150 div 2
= 75, 75 div 2 = 37, 37 div 2 = 18. You get the idea. You eventually compare
blocks of 4 that belong to 2 pixels. That can be alright but not in all
cases. 

By no means did I find a solution to the  formal "O(ND)" problem. In taking
an approach a little different from yours using arrays and then comparing
blocks of 4 bytes I managed to speed up the process considerably, although
your solution is faster.
First I do a row based comparison of the imagedata and only the rows which
differ are taken into an arry with the row number as key and the row data as
data.
This sorts out a number of rows from further analysis, depending of course
on the degree of difference in the images.

the syntax fits into your stack, just make a new button
----------
on mouseUp
   put the imagedata of image "Alpha" of group (the activeTab of btn "Image
Style") into a
   put the imagedata of image "Beta" of group (the activeTab of btn "Image
Style") into b
   set the endvalue of scrollbar "Progress" to \
          the length of imagedata of image "Alpha" of group (the activeTab
of btn "Image Style")
   put the width of image "Alpha" of group (the activeTab of btn "Image
Style")  into tWidth 
   put tWidth * 4 into tWidthBytes
   put the height of image "Alpha" of group (the activeTab of btn "Image
Style") into tRows
   put 0 into n
   
   -- begin timing
   put the milliseconds into t
   -- rows are compared and only if different taken into 2 arrays only those
are of interest
   repeat with i = 0 to (tRows-1)
      if (char i * tWidthBytes +1 to i * tWidthBytes + tWidthBytes of
a)<>(char i * tWidthBytes + 1 to i * tWidthBytes + tWidthBytes of b) then
         put (char i * tWidthBytes +1 to i * tWidthBytes + tWidthBytes of a)
into alphaArray[i+1]
         put (char i * tWidthBytes + 1 to i * tWidthBytes + tWidthBytes of
b) into betaArray[i+1]
      end if
   end repeat
   
   put the keys of alphaArray into tKeys
   -- read out the arrays
   repeat for each line aKey in tKeys
      put alphaArray[aKey] into myAlpha
      put betaArray[aKey] into myBeta
      
      -- do a 4 byte compare = 1 pixel, store differing 4 bytes in the array
hAll
      -- the key of the array is the byte address of the first byte of the
pixel
      repeat with m = 1 to tWidthBytes -4 step 4
         if char m to m + 3 of myAlpha <> char m to m + 3 of myBeta then
            put (akey -1)* tWidthBytes +(m div 4 *4 + 1) into tByteNo
            put char m to m + 3 of myBeta into hAll[tByteNo]
            add 1 to n;  -- if n mod 50000 = 0 then set the thumbPosition of
scrollbar "Progress" to m -- adjust to different parameter
         end if
      end repeat
   end repeat
   
   -- end timing
   put the milliseconds - t into d
   put the keys of hAll into t
   sort t numeric
   put t into field "diff"
   set the thumbposition of scrollbar "Progress" to the endValue of
scrollbar "Progress"
   put the number of lines in fld "Diff" && "pixels changed," && d &&
"milliseconds for" && n && "tests"
end mouseUp
-------------------
please watch out for linebreaks

the timing for your stack on a macbook pro 2.33 GHz
15 msec photoA, 450 msecs photoB, about 980 millisecs Screen Shot. (without
scrollbar)
that seems quite usable, even for the screen shot. (on my computer your
version optimized takes 760 msecs)
I just hope that it gets the number of differing pixels right :)

regards
Bernd

-- 
View this message in context: http://www.nabble.com/Inefficient-code-tp24226458p24255723.html
Sent from the Revolution - User mailing list archive at Nabble.com.