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: Klaus, FourthWorld, heatherlaine, kevinmiller, robinmiller

Post Reply
capellan
Posts: 409
Joined: Wed Aug 15, 2007 11:09 pm
Contact:

Atkinson Dithering algorithm

Post by capellan » Sat Oct 07, 2017 7:19 am

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 alphadata of img "Image" into tAlphaData
   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
   -- of the alphadata or maskdata
   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
         -- to 6 adjacent pixels
         --         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
   set the alphaData of it to tAlphaData

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

end mouseUp
Thanks in advance!
Al
[EDIT: Download the final version of this stack at the end of this topic thread]
Atkinson_Dithering_Algorithm.zip
Compressed stack
(54.33 KiB) Downloaded 13 times
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

Post by malte » Sat Oct 07, 2017 2:45 pm

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

Post by malte » Sat Oct 07, 2017 2:49 pm

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
VIP Livecode Opensource Backer
Posts: 5462
Joined: Sat Apr 08, 2006 7:05 am
Location: Los Angeles
Contact:

Re: Atkinson Dithering algorithm

Post by FourthWorld » Sat Oct 07, 2017 4:33 pm

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.
Richard Gaskin
Community volunteer LiveCode Community Liaison

LiveCode development, training, and consulting services: Fourth World Systems: http://FourthWorld.com
LiveCode User Group on Facebook : http://FaceBook.com/groups/LiveCodeUsers/

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

Re: Atkinson Dithering algorithm

Post by [-hh] » Sat Oct 07, 2017 11:08 pm

You ask for speed.

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
Marilyn.png
(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: 409
Joined: Wed Aug 15, 2007 11:09 pm
Contact:

Re: Atkinson Dithering algorithm

Post by capellan » Sun Oct 08, 2017 12:08 am

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

Al

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

Re: Atkinson Dithering algorithm

Post by capellan » Sun Oct 08, 2017 4:27 am

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 alphadata of img "Image" into tAlphaData
   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
      add 1 to tCounter
      
      if tCounter mod 4 = 1 then
         put chartonum(W) & comma after fldhex3
         add 1 to tCounter2
         
         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
      
         add 1 to tPixelCounter
         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
         -- to 4 adjacent pixels
         --         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
   set the alphaData of it to tAlphaData
   
   put the millisecs - myStartTime && "milliseconds to create Floyd - Steinberg Dither from image's red channel"
   
end mouseUp
Have a nice weekend!

Al

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

Re: Atkinson Dithering algorithm

Post by capellan » Thu Oct 12, 2017 4:06 pm

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 alphadata of img "Image" into tAlphaData
   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
     
      add 1 to tPixelCounter
      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
      -- to 6 adjacent pixels
      --         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
   set the alphaData of it to tAlphaData
  
   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)
      return toupper(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
      add 1 to tCounter
      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
   -- of the alphadata or maskdata, so when
   -- 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: 409
Joined: Wed Aug 15, 2007 11:09 pm
Contact:

Re: Atkinson Dithering algorithm

Post by capellan » Sun Oct 15, 2017 5:51 am

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
Atkinson Dither Algorithm Final Version.PNG
Stack screenshot
Atkinson Dithering Algorithm - Final Version.zip
Compressed stack
(54.11 KiB) Downloaded 18 times

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

Re: Atkinson Dithering algorithm

Post by [-hh] » Tue Oct 17, 2017 12:19 pm

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 alphadata of img "Image" into tAlphaData
  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"
   set the alphaData of img "i2" to tAlphaData
   set the imagedata of img "i2" to fldhexa8
   unlock messages; unlock screen
  put the millisecs - startTime && "milliseconds to create Atkinson Dither 04 from image's channel"
end mouseUp
You can now easily, by changing a few lines only, implement the algorithms of Burkes, Floyd-Steinberg, Sierra-twoRow and Stucki.
shiftLock happens

Post Reply

Return to “Rich Media”