Here's a different approach - a recursive algorithm that is very
compact. Its only the fastest of the examples when very few pixels
differ, but it hangs in there pretty well throughout. I had no idea
how it would do - its very heavy on handler calls and I wondered if it
would hit the recursion limit (which is what?). It doesn't seem to,
with the given test images. I'm wondering if taking advantage of
adjacent changed pixels more than the algorithm already does could
help a bit. Or anything else anybody can think of, of course!
Anyway, an expanded versioin of your test stack is here:
http://jhj.com/Compare-Jerry2.rev.zip
Bill, all told, I think yours is still the overall king of the heap!
The algorithm:
pixDive 1, length(imageA)
on pixDive pStart, pEnd -- WARNING: RECURSION
local tMid
if byte pStart to pEnd of imageA <> byte pStart to pEnd of imageB
then
if pEnd - pStart <= 4 then -- its a single changed pixel, mark
it and move along
put pStart & return after diffPixels
else -- not dived down to one pixel yet
--split it in two and dive into each part
put pStart + ((((pEnd - pStart + 1) / 4) div 2) * 4) into
tMid
pixDive pStart, tMid - 1 -- RECURSION
pixDive tMid, pEnd -- RECURSION
end if -- comparing one pixel or more
end if -- nothing to see here, move along
end PixDive
On Jun 30, 2009, at 2:43 PM, Bill Marriott wrote:
Thanks for the encouragement! I have uploaded the test stack to [the
new] revOnline, with some enhancements to make it easier and more
fun to test. the tags are:
compare algorithm benchmark bitmap difference
imageData performance pixels
I've also uploaded it here:
http://bill.on-rev.com/linked/Compare2.zip
The full script for my algorithm is:
--
--
put 0 into currPixel
-- ImageA contains the imageData of image A
-- ImageB contains the imageData of image B
-- script assumes both images are the same dimension
put the length of ImageA into dataLength
put dataLength into rangeToCheck
-- check a range of pixels for differences.
-- the range begins with the full image
repeat while currPixel < dataLength
-- keep slicing the range in half until we find unchanged pixels
repeat while byte currPixel+1 to currPixel+rangeToCheck of
ImageA <> \
byte currPixel+1 to currPixel+rangeToCheck of ImageB
-- aha, the range we're testing has changes
if rangeToCheck >= 8 then
-- eight bytes is at least two pixels...
-- it's still too big; slice it in half
put rangeToCheck div 4 div 2 * 4 into rangeToCheck
else
-- we're down to a single changed pixel now
-- record which pixel has changed (offset within the
imageData)
put 1 into bytesChanged[currPixel+1]
-- move to the next pixel;
-- assume that changed pixels are near each other
add 4 to currPixel
end if
end repeat
-- we found one or more unchanged pixels; skip this section of
data
add rangeToCheck to currPixel
-- and update the range to encompass the remainder of the image
put dataLength - currPixel into rangeToCheck
end repeat
--
--
"Jerry J" <[email protected]> wrote in message news:[email protected]
...
Bill, I'd like to see your final test stack also. I have another
approach, but it doesn't give correct answers yet, at least I
don't think so - at this point I'm no longer sure what the right
answers are. Mine's recursive, and I can't wait to get it running
right so we can see how fast it is (or not).
--Jerry J
_______________________________________________
use-revolution mailing list
[email protected]
Please visit this url to subscribe, unsubscribe and manage your
subscription preferences:
http://lists.runrev.com/mailman/listinfo/use-revolution
_______________________________________________
use-revolution mailing list
[email protected]
Please visit this url to subscribe, unsubscribe and manage your subscription
preferences:
http://lists.runrev.com/mailman/listinfo/use-revolution
