## Atkinson Dithering algorithm

Visuals, audio, animation. Blended, not stirred. If LiveCode is part of your rich media production toolbox, this is the forum for you.

Moderators: heatherlaine, Klaus, FourthWorld, robinmiller, kevinmiller

capellan
Posts: 492
Joined: Wed Aug 15, 2007 11:09 pm
Contact:

### Atkinson Dithering algorithm

Hi All,

I am stuck trying to make this code for Bill Atkinson dithering algorithm much more faster.
Any ways to speed this code?

Download attached stack or follow the recipe (watch out for lines broken by forum lines length limit)

Recipe:

1) Import an small image (200x200 pixels) and name it as "Image" (you could import a small transparent png or a small jpg image)

2) Optionally, create a scrollbar type slider with a range between 0 and 255. Set the name of this scrollbar to "ThresholdDither" and move the slider to 127 or 0 or 255.

3) Paste the following script in a button and click on it to run this code:

Code: Select all

``````on mouseUp

put the millisecs into startTime
set the cursor to busy

put the imagedata of img "Image" into tVar
-- img "Image" could be a grayscale image
-- where all 3 channels: Red, Green, Blue
-- are identical or a color image where only
-- the red channel is used

delete char 1 of tVar
-- the first char of the imagedata is part
repeat with i = 1 to length(tVar) step 4
put chartonum(char i of tVar) & space after fldhex
end repeat
delete last char of fldhex -- a space
-- fldhex now contains a single channel of the RGB image
-- converted to numbers between 0 and 255

put the number of words of fldhex into lenghtofldhex
put the width of img "Image" into tImageWidth
put the height of img "Image" into tImageHeight

repeat with i = 1 to lenghtofldhex step tImageWidth
-- We need as many words per line, as pixels contains
-- the image width (because each pixel is represented
-- by a word and this word is number between 0 and 255)

put word i to ( i + ((tImageWidth) - 1)) of fldhex & cr after fldhexa2
end repeat

put empty into fldhex
delete last char of fldhexa2
-- deleting the last cr character

put the number of lines of fldhexa2 into sYsize
put the number of words of line 1 of fldhexa2 into sXsize

// get the scrollbar value
-- tThreshold is a value between 0 and 255
if existence(sb the "ThresholdDither") then
put thumbPos of sb the "ThresholdDither" into tThreshold
else
put 127 into tThreshold
end if

repeat with tY = 1 to sYsize
repeat with tX = 1 to sXsize

put tX into tPixelPosition

put word (tPixelPosition) of line tY of fldhexa2 into
tOldPixelValue

if round(tOldPixelValue) <= tThreshold then
put 0 into tNewPixelValue
else
put 255 into tNewPixelValue
end if

put (tOldPixelValue - tNewPixelValue)/8 into tDifusionError

-- Atkinson dither add the diffusion error
--         x o o
--      o o o
--         o

put tNewPixelValue & space after fldhexa3

if tPixelPosition < sXsize then
put tDifusionError + word (tPixelPosition + 1) of line tY of fldhexa2 into word (tPixelPosition + 1) of line tY of fldhexa2

if tPixelPosition < (sXsize-1) then
put tDifusionError + word (tPixelPosition + 2) of line tY of fldhexa2 into word (tPixelPosition + 2) of line tY of fldhexa2
end if

end if

if tY < sYsize then

if tPixelPosition > 1 then
put tDifusionError + word (tPixelPosition - 1) of line tY + 1 of fldhexa2 into word (tPixelPosition - 1) of line tY + 1 of fldhexa2
end if

put tDifusionError + word (tPixelPosition) of line tY + 1 of fldhexa2 into word (tPixelPosition) of line tY + 1 of fldhexa2

if tPixelPosition < sXsize then
put tDifusionError + word (tPixelPosition + 1)  of line tY + 1 of fldhexa2 into word (tPixelPosition + 1) of line tY + 1 of fldhexa2
end if

if tY < (sYsize - 1) then
put tDifusionError + word (tPixelPosition) of line tY + 2 of fldhexa2 into word (tPixelPosition) of line tY + 2 of fldhexa2
end if

end if

end repeat
end repeat

replace "0" with "00" in fldhexa3
replace "255" with "FF" in fldhexa3

repeat with i = 1 to the number of words of fldhexa3
put 00 & word i of fldhexa3 & word i of fldhexa3 & word i of fldhexa3 after tVar2
end repeat
put binaryEncode("H*",tVar2) into tVar3

create img
set the height of it to the height of img "Image"
set the width of it to the width of img "Image"
set the imagedata of it to tVar3

put the millisecs - startTime && "milliseconds to create Atkinson Dither"

end mouseUp
``````
Al
Atkinson_Dithering_Algorithm.zip
Compressed stack
Last edited by capellan on Sun Oct 15, 2017 6:20 pm, edited 1 time in total.

malte
Posts: 1098
Joined: Thu Feb 23, 2006 8:34 pm
Location: Ostenfeld germany
Contact:

### Re: Atkinson Dithering algorithm

Hi Al,

a lot can be done by replacing repeat with with repeat for each where you can.

Code: Select all

``````  --    repeat with i = 1 to the number of words of fldhexa3
--       put 00 & word i of fldhexa3 & word i of fldhexa3 & word i of fldhexa3 after tVar2
--    end repeat
repeat for each word theWord in fldhexa3
put 00 & theword & theword & theword after tVar2
end repeat
``````

malte
Posts: 1098
Joined: Thu Feb 23, 2006 8:34 pm
Location: Ostenfeld germany
Contact:

### Re: Atkinson Dithering algorithm

A sidenode:

I always use strict compile mode, therefore I added the needed variable declarations and noticed you use startTime as a variablename, which is a reserved keyword. That is not a good idea. (I noticed, because I managed to freeze liveCode where I fixed only half of the use of startTime. Booom.)

Cheers,

malte

FourthWorld
VIP Livecode Opensource Backer
Posts: 6112
Joined: Sat Apr 08, 2006 7:05 am
Location: Los Angeles
Contact:

### Re: Atkinson Dithering algorithm

It may be slightly faster to use a delimited other than space, since I would imagine the word parsing algo is at least slightly more complex than the item parsing routine, since words can have any number of spaces.

But maybe a bigger improvement may be to not convert to hex at all, and work directly on the binary image data. With that no delimiters are needed, since of course each byte is exactly one byte long.
Community volunteer LiveCode Community Liaison

LiveCode development, training, and consulting services: Fourth World Systems: http://FourthWorld.com

[-hh]
VIP Livecode Opensource Backer
Posts: 1742
Joined: Thu Feb 28, 2013 11:52 pm
Location: Göttingen, DE

### Re: Atkinson Dithering algorithm

Just now I extended my Basic ImageToolBox to DROI:
D = Dithering
ROI = Region of Interest (selective image processing)

See "Sample Stacks" from the LC Toolbar or
http://livecodeshare.runrev.com/stack/826 (LC 8/9 - Mac/Win/linux)
http://livecodeshare.runrev.com/stack/827 (LC 6/7/8/9 - Mac only)

Dithering is done with one of the methods of Atkinson, Burkes, Floyd-Steinberg, Sierra (twoRow) or Stucki. You may also select other colors as 'Black' or 'White' for the display.

The speed for the Atkinson algorithm is here in average < 300 ms for a full image of 1920x1080 pixels (21.5 inch screen), on a medium fast machine (CPU 2.5 GHz/GPU Intel 4000).
[Of course using ROI is, by checking conditions for each pixel, a bit slower.]

For use of the stacks (also) with MacOS 10.13 I added a custom color chooser.

Once again interesting, comparable on Mac:
LC 9 (using a hidden browser widget) is even faster than LC 6 (using a hidden revBrowser instance).
Attachments
(640x480) Click to zoom.
Dithered with Atkinson's algorithm needed
=> 122 ms by LC 6.7.11
=> 32 ms by LC 9.0.0-dp9
shiftLock happens

capellan
Posts: 492
Joined: Wed Aug 15, 2007 11:09 pm
Contact:

### Re: Atkinson Dithering algorithm

Amazing, Hermann!
Thanks again for sharing your impressive math skills
with all developers in this platform.

Al

capellan
Posts: 492
Joined: Wed Aug 15, 2007 11:09 pm
Contact:

### Re: Atkinson Dithering algorithm

By the way, after applying advice from Malte and Richard, this Floyd-Steinberg dithering version runs (in my computer) 42 times faster. Faster than first version posted in this thread.
For example, if the first version posted runs in 42 seconds then this new version runs in 1 second.

Surely, more optimization is possible but first I need to find why some pixels look different than original version... Probably there are some overflowing values (numbers greater than 255 and numbers smaller than 0 - that is: negative numbers)
[EDIT: The problem appears when using ascii chars from 0 to 255, that only could store integer numbers. This algorithm requires using real numbers like 234.589043 My best option is using two characters to store the real number]

Test this new code following the same instructions from first post but use this new code instead of that first version:

Code: Select all

``````on mouseUp

put the millisecs into myStartTime
set the cursor to busy

put the imagedata of img "Image" into tVar
put the width of img "Image" into tImageWidth
put the height of img "Image" into tImageHeight

delete char 1 of tVar -- get Red Channel

repeat until tVar is empty
put char 1 of tVar after fldhex
delete char 1 to 4 of tVar
end repeat

-- put the number of chars of fldhex && (tImageWidth * tImageHeight)
put fldhex into fldhexa2

repeat for each char W in fldhex

if tCounter mod 4 = 1 then
put chartonum(W) & comma after fldhex3

if tCounter2 mod tImageWidth = 0 then
delete last char of fldhex3 -- deleting a comma
put cr after fldhex3
end if

end  if
end repeat

delete last char of fldhex3 -- a cr

-- get the scrollbar value
-- tThreshold is a value between 0 and 255
if existence(sb the "ThresholdDither") then
put thumbPos of sb the "ThresholdDither" into tThreshold
else
put 127 into tThreshold
end if

repeat for each char H in fldhexa2

put tPixelCounter into tPixelPosition

put chartonum(H) into tOldPixelValue

if round(tOldPixelValue) <= tThreshold then
put 0 into tNewPixelValue
put numtochar(0) into char tPixelCounter of fldhexa2
else
put 255 into tNewPixelValue
put numtochar(255) into char tPixelCounter of fldhexa2
end if

put (tOldPixelValue - tNewPixelValue)/16 into tDifusionError

-- Floyd Steinberg dither add the diffusion error
--         x o
--      o o o

put tNewPixelValue & space after fldhexa4

if tPixelPosition mod tImageWidth <> 0 then
-- pixel position is less than image width

put numtochar( (tDifusionError * 7) + chartonum(char (tPixelPosition + 1) of fldhexa2) ) into char (tPixelPosition + 1) of fldhexa2

end if

if tPixelPosition <= ((tImageWidth * tImageHeight) - tImageWidth) then
-- pixel position is not in the last line of the image

if tPixelPosition mod tImageWidth <> 1 then
-- pixel position is not the first pixel in any line of the image
put numtochar( (tDifusionError * 3) + chartonum(char (tPixelPosition + tImageWidth - 1) of fldhexa2) ) into char (tPixelPosition + tImageWidth - 1) of fldhexa2
end if

put numtochar( (tDifusionError * 5) + chartonum(char (tPixelPosition + tImageWidth) of fldhexa2) ) into char (tPixelPosition + tImageWidth) of fldhexa2

if tPixelPosition mod tImageWidth <> 0 then
-- pixel position is less than image width
put numtochar( (tDifusionError * 1) + chartonum(char (tPixelPosition + tImageWidth + 1) of fldhexa2) ) into char (tPixelPosition + tImageWidth + 1) of fldhexa2
end if

end if

end repeat

replace "0" with "00" in fldhexa4
replace "255" with "FF" in fldhexa4

repeat for each word theWord in fldhexa4
put 00 & theword & theword & theword after tVar2
end repeat

put binaryEncode("H*",tVar2) into tVar3

create img
set the height of it to the height of img "Image"
set the width of it to the width of img "Image"
set the imagedata of it to tVar3

put the millisecs - myStartTime && "milliseconds to create Floyd - Steinberg Dither from image's red channel"

end mouseUp
``````
Have a nice weekend!

Al

capellan
Posts: 492
Joined: Wed Aug 15, 2007 11:09 pm
Contact:

### Re: Atkinson Dithering algorithm

Hi All,

Check a new version of this handler. Beware of lines wrapped by forum line length limits:

Code: Select all

``````on mouseUp

put the millisecs into startTime
set the cursor to busy

put the imagedata of img "Image" into tVar
put the width of img "Image" into tImageWidth
put the height of img "Image" into tImageHeight

put the number of chars of tVar into tImgPixels

delete char 1 to 1 of tVar -- get Red Channel
-- or delete char 1 to 2 of tVar -- get Green Channel
-- or delete char 1 to 3 of tVar -- get Blue Channel

repeat until tVar is empty
put char 1 of tVar after fldhex
delete char 1 to 4 of tVar
end repeat

-- fldhex now only contains the red channel

put tImgPixels && the number of chars of fldhex && (tImageWidth * tImageHeight) into lth
put fldhex into fldhexa2

-- get the scrollbar value
-- tThreshold is a value between 0 and 255
if existence(sb the "ThresholdDither") then
put thumbPos of sb the "ThresholdDither" into tThreshold
else
put 127 into tThreshold
end if

put numtochar(0) & numtochar(255) & numtochar(255) & numtochar(255) into tWP
put numtochar(0) & numtochar(0) & numtochar(0) & numtochar(0) into tBP
put ((tImageWidth * tImageHeight) - tImageWidth) into tHW

put the number of chars of fldhexa2 into tpixelCount

put empty into fldhexa3
repeat tpixelCount
put null after fldhexa3
end repeat

set the itemdelimiter to numtochar(46)
repeat tPixelCount

put tPixelCounter into tPixelPosition

put chartonum(char tPixelCounter of fldhexa2) & "." & chartonum(char tPixelCounter of fldhexa3) into tOldPixelValue

if round(tOldPixelValue) <= tThreshold then
put 0 into tNewPixelValue
put tBP after fldhexa8
else
put 255 into tNewPixelValue
put tWP after fldhexa8
end if

put (tOldPixelValue - tNewPixelValue)/8 into tDifusionError

-- Atkinson dither add the diffusion error
--         x o o
--       o o o
--         o

if tPixelPosition mod tImageWidth <> 0 then
-- pixel position is less than image width

put chartonum(char (tPixelPosition + 1) of fldhexa2) & "." & chartonum(char (tPixelPosition + 1) of fldhexa3) into tDecNumber
put (tDifusionError) + tDecNumber into tDecNumber
if max(0,min(tDecNumber,255)) = 0 then put 0.0 into tDecNumber
if max(0,min(tDecNumber,255)) = 255 then put 255.0 into tDecNumber
put numtochar(item 1 of tDecNumber) into char (tPixelPosition + 1) of fldhexa2
put numtochar(item 2 of tDecNumber) into char (tPixelPosition + 1) of fldhexa3

if tPixelPosition < (tImageWidth - 1) then
-- pixel position is less than image width - 1
put chartonum(char (tPixelPosition + 2) of fldhexa2) & "." & chartonum(char (tPixelPosition + 2) of fldhexa3) into tDecNumber
put (tDifusionError) + tDecNumber into tDecNumber
if max(0,min(tDecNumber,255)) = 0 then put 0.0 into tDecNumber
if max(0,min(tDecNumber,255)) = 255 then put 255.0 into tDecNumber
put numtochar(item 1 of tDecNumber) into char (tPixelPosition + 2) of fldhexa2
put numtochar(item 2 of tDecNumber) into char (tPixelPosition + 2) of fldhexa3
end if
end if

if tPixelPosition <= tHW then -- ((tImageWidth * tImageHeight) - tImageWidth) then
-- pixel position is not in the last line of the image

if tPixelPosition mod tImageWidth <> 1 then
-- pixel position is not the first pixel in any line of the image
put chartonum(char (tPixelPosition + tImageWidth - 1) of fldhexa2) & "." & chartonum(char (tPixelPosition + tImageWidth - 1) of fldhexa3) into tDecNumber
put (tDifusionError) + tDecNumber into tDecNumber
if max(0,min(tDecNumber,255)) = 0 then put 0.0 into tDecNumber
if max(0,min(tDecNumber,255)) = 255 then put 255.0 into tDecNumber
put numtochar(item 1 of tDecNumber) into char (tPixelPosition + tImageWidth - 1) of fldhexa2
put numtochar(item 2 of tDecNumber) into char (tPixelPosition + tImageWidth - 1) of fldhexa3

end if

put chartonum(char (tPixelPosition + tImageWidth) of fldhexa2) & "." & chartonum(char (tPixelPosition + tImageWidth) of fldhexa3) into tDecNumber
put (tDifusionError) + tDecNumber into tDecNumber
if max(0,min(tDecNumber,255)) = 0 then put 0.0 into tDecNumber
if max(0,min(tDecNumber,255)) = 255 then put 255.0 into tDecNumber
put numtochar(item 1 of tDecNumber) into char (tPixelPosition + tImageWidth) of fldhexa2
put numtochar(item 2 of tDecNumber) into char (tPixelPosition + tImageWidth) of fldhexa3

if tPixelPosition mod tImageWidth <> 0 then
-- pixel position is less than image width
put chartonum(char (tPixelPosition + tImageWidth  + 1) of fldhexa2) & "." & chartonum(char (tPixelPosition + tImageWidth + 1) of fldhexa3) into tDecNumber
put (tDifusionError) + tDecNumber into tDecNumber
if max(0,min(tDecNumber,255)) = 0 then put 0.0 into tDecNumber
if max(0,min(tDecNumber,255)) = 255 then put 255.0 into tDecNumber
put numtochar(item 1 of tDecNumber) into char (tPixelPosition + tImageWidth + 1) of fldhexa2
put numtochar(item 2 of tDecNumber) into char (tPixelPosition + tImageWidth + 1) of fldhexa3
end if

if tPixelPosition mod (tImageWidth - 1) <> 0 and tPixelPosition + (tImageWidth * 2) <= (tImageWidth * tImageHeight) - (tImageWidth * 2) then
-- pixel position is less than image width - 1
put chartonum(char (tPixelPosition + (tImageWidth * 2)) of fldhexa2) & "." & chartonum(char (tPixelPosition + (tImageWidth * 2)) of fldhexa3) into tDecNumber
put (tDifusionError) + tDecNumber into tDecNumber
if max(0,min(tDecNumber,255)) = 0 then put 0.0 into tDecNumber
if max(0,min(tDecNumber,255)) = 255 then put 255.0 into tDecNumber
put numtochar(item 1 of tDecNumber) into char (tPixelPosition + (tImageWidth * 2)) of fldhexa2
put numtochar(item 2 of tDecNumber) into char (tPixelPosition + (tImageWidth * 2)) of fldhexa3
end if

end if

end repeat

put fldhexa8 into tVar3

-- ------------------------------------------------------------------------

create img
set the height of it to the height of img "Image"
set the width of it to the width of img "Image"
set the imagedata of it to tVar3

put the millisecs - startTime && "milliseconds to create Atkinson Dither v03 from image's red channel" & cr & lth

end mouseUp

-- ----------------------------------------------------------------------------------------------

Function MD5Var tContainer tEncoding
-- This function returns an MD5 digest from a variable or container.
-- Because MD5 digest is binary data, we need to convert it
-- into Base64 or Hexadecimal numbers, for this conversion
-- we use the parameter tEncoding with one of these
-- two values: H (for hexadecimal) or B (for base64 encoding)

if tEncoding = B then
-- returns a string of 24 characters like
-- T+YY8ZhKxjGmYt0XMwDb9g==
return base64encode(md5digest(tContainer))
else -- by default, this function
-- returns a string of 32 characters like
-- 5EB63BBBE01EEED093CB22BB8F5ACDC3
put 0 into myVar
get binarydecode("H*",md5digest(tContainer),myVar)
end if
end MD5Var

Function ImgToNum vImageData vSeparator vImageWidth
-- This function converts binary imagedata to
-- integer numbers from 0 to 255 separated
-- by space or comma or cr.
--
-- vImageData is a single color channel
-- stored as binary imagedata.
--
-- vSeparator is a comma, a space or cr
-- wrote as an ascii number: space = 32
-- comma =  44 , cr (new line) = 10
--
-- vImageWidth is the image width

put empty into tResult
put 0 into tCounter
repeat for each char K in vImageData
put chartonum(K) & numtochar(vSeparator) after tResult
if vImageWidth is not empty and vSeparator <> 10 and tCounter mod vImageWidth = 0 then
delete last char of tResult -- a separator character (space or comma)
put cr after tResult
end if
end repeat
delete last char of tResult -- a separator character
return tResult
end ImgToNum

Function ImgToCh tImageData tChannel
-- This function returns binary data.
--
-- tImageData is unmodified original imagedata of image
-- with 4 chars for each pixel: 1 alphadata and 3 color channels.
--
-- tChannel is a number from 1 to 3:
-- 1 is red channel, 2 is green channel and 3 is blue channel

put tImageData into tempVar

delete char 1 to tChannel of tempVar
-- the first char of the imagedata is part
-- we delete char 1, the next char is part
-- from red channel... if we delete 2 first
-- chars, then next char is green channel
-- if we delete 3 first chars, then we get
-- the blue channel

repeat until tempVar is empty
put char 1 of tempVar after tResult
delete char 1 to 4 of tempVar
end repeat

return tResult

end ImgToCh``````
Have a nice week!

Al

capellan
Posts: 492
Joined: Wed Aug 15, 2007 11:09 pm
Contact:

### Re: Atkinson Dithering algorithm

Hi All,

This message contains the final version of this stack. It includes a Color version of this algorithm.
Thanks again to Malte Brill, Richard Gaskin, Hermann Hoch, Mark Waddingham, Peter Reid, Ben Rubinstein, Bob Sneidar and Lagi Pittas for posting scripts and writing ideas to improve this handler.

Al
Stack screenshot
Atkinson Dithering Algorithm - Final Version.zip
Compressed stack

[-hh]
VIP Livecode Opensource Backer
Posts: 1742
Joined: Thu Feb 28, 2013 11:52 pm
Location: Göttingen, DE

### Re: Atkinson Dithering algorithm

Hi Alejandro,

find attached the LCS version of my javascript routine (which does your image in LC 6, using a revBrowser instance, here in 6 ms in average).
I used at about your variable names and for the array creation the method proposed by Alex Tweedly in the use-list. This is now here, using LC 6.7.11, down to 120 ms avg.
Probably Alex and you can improve this even more.

The main thing below: All your limit checking for the pixelcounter is unneeded. It is much faster, especially for large images, to do some unneeded additions instead of doing all these checks. Note, that this cannot create an 'out of bounds' of the array.

Hermann

Code: Select all

``````on mouseUp
put the millisecs into startTime
lock messages; lock screen
--if there is an img "i2" then delete img "i2"
set the cursor to watch
put the imageData of img "image" into tImageData
put the height of img "Image" into tImageHeight
put the width of img "Image" into tImageWidth
put 2*tImageWidth into tImageWidth2
-- extract channel data: tChannel 1=red, 2=green, 3=blue
put 1 into tChannel
repeat with i = 1 + tChannel to 4*tImageWidth*tImageHeight - 3 step 4
put byteToNum(byte i of tImageData) into tArray[1 + (i div 4)]
end repeat
if existence(sb the "ThresholdDither") then
put thumbPos of sb the "ThresholdDither" into tThreshold
else put 127 into tThreshold
put numToByte(0) into c0
put numToByte(255) into c255
put c0 & c255 & c255 & c255 into tWP
put c0 & c0 & c0 & c0 into tBP
repeat with tPixelCounter=1 to tImageWidth*tImageHeight
put tArray[tPixelCounter] into tOldPixelValue
if tOldPixelValue <= tThreshold then
put tOldPixelValue/8 into tDiffusionError
put tBP after fldhexa8
else
put (tOldPixelValue - 255)/8 into tDiffusionError
put tWP after fldhexa8
end if
add tDiffusionError to tArray[tPixelCounter + 1]
add tDiffusionError to tArray[tPixelCounter + 2]
add tDiffusionError to tArray[tPixelCounter + tImageWidth - 1]
add tDiffusionError to tArray[tPixelCounter + tImageWidth]
add tDiffusionError to tArray[tPixelCounter + tImageWidth + 1]
add tDiffusionError to tArray[tPixelCounter + tImageWidth2]
end repeat
if there is no img "i2" then create img "i2"
set the height of img "i2" to the height of img "Image"
set the width of img "i2" to the width of img "Image"