Atkinson dither algorithm
alex at tweedly.net
Tue Oct 17 01:21:54 CEST 2017
On 16/10/2017 19:37, Alejandro Tejada via use-livecode wrote:
> Hi Bob,
> Bob Sneidar wrote:
>> I didn't post any code I don't think, but I will certainly
>> take some credit for having done so! ;-)
> In fact, you are not late! :-D
But I am too late - the file is called "...Final Version ..." :-) :-)
Let's have a look anyway....
> Please, take a look at the script of
> Atkinson Dither 04 (Fastest Version)
> and make it faster.
OK, did that :-)
I've been aware of this interesting discussion, but had no time to look
at it at all (until tonight). Sorry to be late to the party.
I made a few changes, as follows:
1. (Just on principle).
I would change all these reference to "char" to "byte" when we are
really talking about bytes in binary data.
Probably doesn't make any difference to performance - the engine will
most likely realize that there aren't any Unicode strings involved - but
it's just "right" to call them bytes, and to use the byte functions to
manipulate them :-)
2. there's a function ImgToCh which extracts a single channel of data
out the image data.
It does this with a cute 'delete' method - but that is over-thinking the
You can (i.e. the engine can) access a single byte within a byte string
in constant time (it's surely a single offset in the C library).
so instead of
> repeat untiltempVar isempty
> putchar1oftempVar aftertResult
> end repeat
we can simply do
> *repeat* withi = 1tothenumberofcharsintempVar step4*
> put*bytei oftempVar aftertemp*
> end* *repeat*
(I kept the initial delete to select which channel, just because it's so
clever :-) - but that could have been removed and the repeat changed to
* repeat* withi = tChannel+1tothenumberofcharsintempVar step4*
3. The result of that function is then passed to another function that
converts the byte string into a sequential array of numbers (and that's
all that's done with the byte string).
So those two should be combined into a single pass - to get :
> Function ImgToChToArrayNum2 tImageData, tChannel
> -- extract a single channel's data, and convert to sequential array
> of numbers
> puttImageData intotempVar
> deletebyte1totChannel oftempVar
> repeat withi = 1tothenumberofbytesintempVar step4
> putbytetonum(bytei oftempVar) intotResult[tCounter]
> end repeat
> end ImgTochToArrayNum2
This takes the time for this part of the whole process down from 250ms
to about 75ms, and therefore the total process time down from around
750-800ms to 600-650ms (on my aging MBP).
Trying repeated runs, the times do seem to vary more than usual - not
I haven't tackled the second half (i.e. the actual dithering bit yet -
More information about the use-livecode