title: Run Length Encoding an Image
body: <p>I am writing an Run Length Image Encoder for an assignment. My code works very well for binary and <em>8 bit</em> images but when I want to encode an <em>4 bit</em> image it doesn't work correctly. I am using Ubuntu 13.10, Python 3.3.4 and Pillow. Executing following code should print <code>True</code> and <code>True</code> but it prints <code>True</code> and <code>False</code>. </p>
  
  <p>To test my code I generate <em>random</em> list to simulate an image. It works, first value presents it, but this <a href="https://dl.dropboxusercontent.com/u/21699640/baboon_4bit.bmp" rel="nofollow" title="image">image</a> is not working. There is 4 more image like this but none of them works. Am I missing some point? </p>
  
  <pre><code>from PIL import Image
  import random
  
  def _encodeImage4bit(imagePixels, width, height):
      encodedImage = bytearray()
  
      count = 0
  
      prev = imagePixels[0]
      tempmap = ""
  
      for pixel in imagePixels:
          if count &gt;= 15:
              encodedImage.append(15)
              encodedImage.append(pixel)
              tempmap += "1"
              tempmap += "0"
              count = 0
  
          if pixel == prev:
              count += 1
          else:
              if count &gt; 1:
                  encodedImage.append(count)
                  tempmap += "1"
              encodedImage.append(prev)
              tempmap += "0"
              count = 1
              prev = pixel
  
      if count &gt; 1:
          encodedImage.append(count)
          tempmap += "1"
  
      encodedImage.append(prev)
      tempmap += "0"
  
      encodedImage.extend([0] * _remaining(len(encodedImage)))
      tempmap += "1"*_remaining(len(tempmap))
  
      encodedImage = _set4bitMap(tempmap, encodedImage)
  
      return encodedImage
  
  def _set4bitMap(imgMap, encodedImage):
      newImgMap = _divideByRow(imgMap, 8)
  
      tempImg = [_merge4bitTo8bit(encodedImage[i], encodedImage[i + 1]) for i in range(0, len(encodedImage), 2)]
      tempImg = _divideByRow(list(tempImg), 4)
  
      return bytearray(_flattenListOfList(_mergeMap(tempImg, newImgMap)))
  
  def _decodeImage4bit(encodedImage, width, height):
      decodedImage = []
  
      imgMap, encImg = _get4bitMap(encodedImage)
  
      for index, i in enumerate(imgMap):
          if i == '1' and encImg[index] == 0:
              break
  
          if i == '1':
              decodedImage.extend([encImg[index + 1]] * encImg[index])
          elif imgMap[index - 1] != '1' or index == 0:
              decodedImage.append(encImg[index])
  
      return decodedImage
  
  def _get4bitMap(encodedImage):
      imgMap = ""
  
      newEncodedImage = list(encodedImage)
  
      I = range(0, len(newEncodedImage), 5)
  
      for i in I:
          imgMap += '{0:08b}'.format(newEncodedImage[i])
  
      for i in sorted(list(I), reverse = True):
          del newEncodedImage[i]
  
      newEncodedImage = _flattenListOfList([_split8bitTo4bit(i) for i in newEncodedImage])
  
      return (imgMap, newEncodedImage)
  
  def _split8bitTo4bit(eightbit):
      leftmask = 240
      rightmask = 15
      left = (eightbit &amp; leftmask) &gt;&gt; 4
      right = eightbit &amp; rightmask
  
      return (left, right)
  
  def _merge4bitTo8bit(left, right):
      return (left &lt;&lt; 4) | right
  
  _remaining = lambda x, y = 8: 0 if x % y == 0 else y - (x % y)
  _mergeMap = lambda z, x:[[int(x[index], 2)] + i for index, i in enumerate(z)]
  _flattenListOfList = lambda flat:[item for sublist in flat for item in sublist]
  _divideByRow = lambda flat, size: [flat[i:i + size] for i in range(0, len(flat), size)]
  
  
  if __name__ == "__main__":
      img = [15] * 100
      img.extend([random.randrange(0, 16) for n in range(300)])
      encImg = _encodeImage4bit(img, 20, 20)
      decImg = _decodeImage4bit(encImg, 20, 20)
      print(str(decImg == img))
  
      imgpath = "../../images/4bit/baboon_4bit.bmp"
      img2 = Image.open(imgpath)
      encImg2 = _encodeImage4bit(list(img2.getdata(0)), img2.size[0], img2.size[1])
      decImg2 = _decodeImage4bit(encImg2, img2.size[0], img2.size[1])
      print(str(decImg2 == list(img2.getdata(0))))
  </code></pre>
  
  <p>Algorithm from Data Compression The Complete Reference 4th Edition Page 26</p>
  
  <blockquote>
    <p>Again, one bit is devoted to each byte to indicate whether the byte
    contains a grayscale value or a count. This time, however, these extra
    bits are accumulated in groups of 8, and each group is written on the
    output stream preceding (or following) the 8 bytes it “corresponds
    to.”</p>
  </blockquote>
  
  <p>I changed it to support 4 bit images.</p>
  
  <blockquote>
    <p>Example
    Original image: 12, 12, 12, 12, 12, 12, 12, 12, 12, 14, 3, 7, 10,10, 10, 10, 5, 5, 5, 5, 5, 5, 1, . . .</p>
    
    <p>First step: Find repetitions
    9, 12, 14, 3, 7, 4, 10, 6, 5, 1, . . .</p>
    
    <p>Second step: Generate map to identify which element is pixel value(0), which is repetition number(1)
    1 0 0 0 0 1 0 1 0 . . .</p>
    
    <p>Third step:
    Fill values with zero to make length a multiple of eight.
    Fill map with one to make length of multiple of eight.</p>
    
    <p>Fourth step:
    Divide map to pieces of eight and convert every piece to integer.
    133, . . .</p>
    
    <p>Fifth step:
    Couple every two 4 bit to make one eight bit. Shift left value to left 4 times and OR it with right number. 
    156, 227, 116, 166, 81, . . .</p>
    
    <p>Sixth step:
    Merge map with values. Every integer number in map now presents 4 values in values.
    133, 156, 227, 116, 166, . . .</p>
    
    <p>Decoding is reverse of this operation.</p>
  </blockquote>