Atkinson dither algorithm

Alex Tweedly 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 
problem.
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
>   deletechar1to4oftempVar
> 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
>    putemptyintotResult
> put0intotCounter
>    repeat withi = 1tothenumberofbytesintempVar step4
>       add1totCounter
>       putbytetonum(bytei oftempVar) intotResult[tCounter]
>    end repeat
>    returntResult
> 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 
sure why.

I haven't tackled the second half (i.e. the actual dithering bit yet - 
maybe tomorrow).

-- Alex.



More information about the use-livecode mailing list