Decoding grayscale PNG and performing Prewitt operator for edge detection

Question

I'm a hobbyist programmer.

What I try to do here is to read 8-bit grayscale PNG file. Then unfilter it. (That caused a headache). And after that perform Prewitt operator for "edge detection". I know that there is million and five libs for this but I want to learn why and how these things works.

I try follow OOP-principles, but it is hard.

There are still some features I intend to add, but I'd like a review of the existing code before going further.

So what I want to know:

Do I follow OOP-principles? If not, what to do better? (Link to good book would be amazing.)

Should I use bytearray instead of list? Does it affect performance?

Any comments, pointers etc are more than welcome.

---

Input and output of program

And code:

PNG.py

import sys, binascii, math
from Chunk import *
from Filter import Filter
import time
class PNG:

    def __init__(self, f):
        self.data = []
        self.f = open(f, "rb")
        self.mod = sys.modules[__name__]

    def readFile(self):
        f = self.f
        try:
            self.head = f.read(8)
            while True:
                length = f.read(4)
                if length == b'':
                    break
                try:
                    c = getattr(self.mod, f.read(4).decode()) #Class
                except Exception as e:
                    print("Chunk is not implemented yet")
                    raise
                found = [(i, x) for (i,x) in enumerate(self.data) if isinstance(x, c)]
                if len(found) > 0:
                    index, obj = found[0]
                    obj.append(f.read(int.from_bytes(length, byteorder='big')))
                else:
                    i = c(data=f.read(int.from_bytes(length, byteorder='big'))) #Read data
                    self.data.append(i)
                f.read(4)
        finally:
            f.close()

    def getKernels(self, pixels, width):
        kernels = []
        pixels = [x for sublist in pixels for x in sublist]
        for i, px in enumerate(pixels):
            x = (i % width)
            y = math.floor(i / width)
            try:
                kernel = [pixels[(x-1)+((y-1)*width)],pixels[(x)+((y-1)*width)],pixels[(x+1)+((y-1)*width)],pixels[(x-1)+(y*width)],pixels[(x)+(y*width)],pixels[(x+1)+(y*width)],pixels[(x-1)+((y+1)*width)],pixels[(x)+((y+1)*width)],pixels[(x+1)+((y+1)*width)]]
            #TODO Function to generate single kernel with size variations
            except Exception as e:
                kernel = [0] #Bound of image
            kernels.append(kernel)
        return kernels

    def edgeDetect(self, pixels, ihdr, idat):
        kernels = self.getKernels(pixels, ihdr.width) #Generate kernel 3*3
        pixels = self.prewittOperator(kernels) #Apply prewittOprator
        data = b''
        for i, px in enumerate(pixels):
            if i % (ihdr.width) == 0: #New scanline
                data += int(0).to_bytes(1, byteorder='big')  #Filter method not implemented yet so "manually" set filtermethod to 0 (None)
            pxbytes = bytes([px])
            data += pxbytes
        return data

    def prewittOperator(self, kernels):
        data = []
        for kernel in kernels:
            if len(kernel) != 9:
                data.append(0)
            else:
                gx = sum([i*j for i, j in zip(kernel, [-1,0,1,-1,0,1,-1,0,1])])
                gy = sum([i*j for i, j in zip(kernel, [-1,-1,-1,0,0,0,1,1,1])])
                g = int(math.sqrt(int(math.pow(gx, 2))+int(math.pow(gy, 2))))%256
                data.append(g)
        return data

    def editImage(self):
        ihdr=self.getChunk(IHDR) #Get Image header instance
        idat=self.getChunk(IDAT) #Get Image data instance
        data = idat.getImage(ihdr) #Get filtered image data
        pixels = Filter().unfilter(data, ihdr.width) #Unfilter data
        newImage = self.edgeDetect(pixels, ihdr, idat);
        idat.setImage(newImage) #Set new image data


    def getChunk(self,classname):
        found = [(i, x) for (i, x) in enumerate(self.data) if isinstance(x, classname)]
        index, chunk = found[0]
        return chunk;

    def writeFile(self, filename):
        f = open(filename, "wb")
        f.write(self.head)
        for c in self.data:
            f.write(c.getLength())
            f.write(bytes(c.__class__.__name__, 'ASCII'))
            f.write(c.getData())
            f.write(c.getCRC(bytes(c.__class__.__name__, 'ASCII')))




png = PNG("input.png")
png.readFile()
png.editImage()
png.writeFile("output.png")

Chunk.py

import zlib, binascii

class Chunk:
    def __init__(self, data = b''):
        self.data = data

    def getLength(self):
        return len(self.data).to_bytes(4, byteorder='big')

    def getData(self):
        return self.data

    def setData(self, data):
        self.data = data

    def getCRC(self, name):
        return (binascii.crc32(name+self.data)).to_bytes(4, byteorder='big') #TODO Own CRC calculation

class IHDR(Chunk):
    def __init__(self, **kwds):
        super().__init__(**kwds)
        self.parse()

    def parse(self):
        data = super().getData()
        self.width =  int(data[:4].hex(), 16)
        self.height = int(data[4:8].hex(), 16)
        self.bit_depth = int(data[8:9].hex(), 16)
        self.color_type = int(data[9:10].hex(), 16)
        if(self.color_type != 0):
            print("Color type not implemented yet")
            raise
        self.compression_method = int(data[10:11].hex(), 16)
        if(self.compression_method != 0):
            print("Compression method not implemented yet")
            raise
        self.filter_method = int(data[11:12].hex(), 16)
        self.interlace_method = int(data[12:13].hex(), 16)

class IDAT(Chunk):
    def __init__(self, **kwds):
        super().__init__(**kwds)

    def append(self, data):
        super().setData(super().getData()+data)

    def parseBytes(self, data, width, length, lines):
        if len(data) > 0:
            lines.append(data[:(1+width*length)])
            return self.parseBytes(data[(1+width*length):], width, length, lines)
        else:
            return lines

    def getImage(self, ihdr):
        return self.parseBytes(zlib.decompress(super().getData()), ihdr.width, int(ihdr.bit_depth/8), [])

    def setImage(self, data):
        super().setData(zlib.compress(data))

class IEND(Chunk):
    def __init__(self, **kwds):
        super().__init__(**kwds)

Filter.py

import math

class Filter:

    def filter(self):
        print("Filter function not implemented yet")
        raise

    def unfilter(self, data, width):
        unfiltered = []
        for y, row in enumerate(data):
            ft = row[0] #Filter method
            nr = [] #new row
            unfiltered.append(nr)
            for x, px in enumerate(row[1:]):
                try:
                    unfiltered[y].append(int(self.method(ft)(px, x, y, unfiltered)))
                except Exception as e:
                    print(e)
                    print("ERROR Filter: "+str(ft)+" Cordinates: "+str(x)+":"+str(y))
                    raise
        return unfiltered

    def none(self,px,x,y,data):
        return px

    def sub(self,px,x,y,data):
        return (px + self.reconA(x,y,data))%256

    def up(self,px,x,y,data):
        return (px + self.reconB(x,y,data))%256

    def average(self,px,x,y,data):
        return (px + math.floor((self.reconA(x,y,data)+self.reconB(x,y,data))/2))%256

    def paeth(self,px,x,y,data):
        a = self.reconA(x,y,data)
        b = self.reconB(x,y,data)
        c = self.reconC(x,y,data)
        p = a + b - c
        pa = math.fabs(p-a)
        pb = math.fabs(p-b)
        pc = math.fabs(p-c)
        if pa <= pb and pa <= pc:
            return (px + a)%256
        if pb <= pc:
            return (px + b)%256
        return (px + c)%256

    def reconA(self,x,y,data):
        if x == 0:
            return 0
        return data[y][x-1]

    def reconB(self,x,y,data):
        if y == 0:
            return 0
        return data[y-1][x]

    def reconC(self,x,y,data):
        if y == 0 or x == 0:
            return 0
        return data[y-1][x-1]

    def method(self, t):
        return {
        0: self.none,
        1: self.sub,
        2: self.up,
        3: self.average,
        4: self.paeth,
        }[t]

Answer 1

Style

Read PEP 8, especially the parts about whitespace and variable naming. You also happen to use super() in various places in Chunk.py (especially super().getData()) but most of these calls can simply use self. instead since you don't override these methods in your class.

There is also various if ...: raise in your code: don't do that, it's a bug. You will run into a RuntimeError: No active exception to reraise. In some sense it works since it generate an exception, but in the end, it's not the one you want. raise alone can only be used in except clauses.

You should raise a specific exception instead. It seems that every time you have this pattern, you print('<something> not implemented yet') before; thus you should raise NotImplementedError instead of these two lines.

Lastly, you should familiarize yourself with the truthy values of Python's objects: empty containers and numbers representing 0 are False, everything else is True by default. So instead of if len(found) > 0:, write if found:; instead of if x == 0: write if not x:, etc.

OOP

Many of the methods on your objects does not make use of the self parameter. Or only to call other methods. This often indicates that OOP is not required there and you may use regular functions instead.

Moreover, the PNG class seems disturbing. First off, since you can not perform any operation before reading the file, you should merge __init__ and readFile; this will also allow you to use the with statement to deal with the file (kuddos for using finally: f.close(), btw) for you. Second, I trully feel that your class hierarchy is the wrong one. Why is it the responsibility of the PNG class to perform image transformation? The day you’ll want to support JPEG format, will you repeat the same code for edge detection? Is the Chunk class usefull for something else than PNG?

Instead, you should provide classes that knows about file formats: how to read them, how to write to them and how to extract pixels blobs out of them. And provide utility functions to modify the pixels blobs returned by such classes. This will also allow you to remove this weird hack using sys.modules.

Sketching this new layout would turn your code into something like:

PREWITT_X_MASK = [-1, 0, 1, -1, 0, 1, -1, 0, 1]
PREWITT_Y_MASK = [-1, -1, -1, 0, 0, 0, 1, 1, 1]


def get_kernels(pixels, width, radius=1):
    for y in range(len(pixels)):
        y_min = y - radius
        y_max = y + radius + 1
        for x in range(width):
            x_min = x - radius
            x_max = x + radius + 1
            yield [
                pixel for row in pixels[y_min:y_max]
                for pixel in row[x_min:x_max]]


def prewitt_operator(kernel):
    if len(kernel) != 9:
        return 0

    gx = sum(i*j for i, j in zip(kernel, PREWITT_X_MASK))
    gy = sum(i*j for i, j in zip(kernel, PREWITT_Y_MASK))
    return int((gx**2 + gy**2)**(1/2)) % 256


def edge_detect(image):
    pixels = image.pixels
    width = image.width

    detected = [prewitt_operator(kernel) for kernel in get_kernels(pixels, width)]
    new_image = [detected[i*width:(i+1)*width] for i in range(len(detected)//width)]
    image.pixels = new_image

For the image detection part. And you would use this code like:

image = PNG('input.png')
edge_detect(image)
image.write('output.png')

And voilà. The whole logic of reading the file, converting its data into a list of list of pixels and converting back a list of list of pixels should be hidden in the PNG class. And it will be much easier to provide alternate image format support like JPEG.

The PNG class would look a bit like:

class PNG:
    def __init__(self, filename):
        self.name = filename
        with open(filename, 'rb') as f:
            # process f and store into self.data
            # combines your PNG.__init__ and PNG.readFile
            # and helper methods on the class to create the
            # equivalents of your chunks objects directly as
            # attributes:
            #   self.width, self.height, self.bit_depth, self.color_type ...

    @property
    def pixels(self):
        # process self.data and return a list of lists of pixels
        # combines your IDAT.getImage + Filter.unfilter

    @pixels.setter
    def pixels(self, new_image):
        # process new_image to store into self.data

    def write(self, filename=None):
        if filename is None:
            filename = self.name

        with open(filename, 'wb') as f:
            # write back metadata and self.data into f

    # other utility methods

The @propertys allowing for easy, attribute like, retrieval or update of data, as shown in edge_detect.

Miscelaneous

• You can feed a whole list at once to bytes:

  >>> bytes([72, 101, 108, 108, 111, 32, 87, 111, 114, 108, 100, 33])
  b'Hello World!'
  

• Your use case of math can easily be simplified using ** (exponentiation) or // (integral division) for instance.

• If you implement the "chunks" as class methods, you can use getattr(self, f.read(4).decode()) to get a bound method without having to rely on sys.modules.
• As such, you won't need to use an from <whatever> import * which is bad practice.
• You can remove your try ... except in Filter.unfilter as the generated traceback shoud have as much information as what you are printing.

• You can reduce the need for the Filter class, which is very PNG specific by integrating unfilter into the pixel property and using something along the lines of:

  def sanitize_along_x(x, y, data):
      return 0 if not x else data[y][x - 1]
  
  def sanitize_along_y(x, y, data):
      return 0 if not y else data[y - 1][x]
  
  def paeth(x, y, data):
      a = sanitize_along_x(x, y, data)
      b = sanitize_along_y(x, y, data)
      c = 0 if not (x and y) else data[y - 1][x - 1]
      # p = a + b - c  ## Was it right and not p = a + b + c ???
      pa = abs(b - c)
      pb = abs(a - c)
      pc = abs(a + b - 2 * c)
      if pc => pa <= pb:
          return a
      if pb <= pc:
          return b
      return c
  
  
  class PNG:
      UNFILTER_METHOD = [
          lambda *nil: 0,
          sanitize_along_x,
          sanitize_along_y,
          lambda x, y, data: (sanitize_along_x(x, y, data) + sanitize_along_y(x, y, data)) // 2,
          paeth,
      ]
  
      @property
      def pixel(self):
          # prepare self.data according to IDAT.getImage
          unfiltered = []
          for y, row in enumerate(self.data):
              filter_method, *data = row
              current_row = []
              unfiltered.append(current_row)
              for x, pixel in enumerate(data):
                  px = self.UNFILTER_METHOD[filter_method](x, y, unfiltered)
                  current_row.append((px + pixel) % 256)
          return unfiltered
  
      # rest of the class
  

Answer 2

Words to the wise

It's great that you are doing this as a learning exercise, but you should know what you are getting into. Image decoders are hard to write well — you're wandering onto a bloody battlefield. It helps that you are using Python, which eliminates concerns like buffer overflow, but you've introduced other dangers (particularly with c = getattr(self.mod, f.read(4).decode()). (More on that below.)

The other general advice I have is that if you're going to be working with matrices, you should consider using NumPy / SciPy. The code would be more expressive, and possibly faster, if you used library functions such as scipy.signal.convolve2d().

Naming and interfaces

Try to adhere to PEP 8 naming guidelines, particularly the lower_case_with_underscores convention for method names.

Writing C.getBlah() and C.setBlah(…) methods is more of a Java-like approach. In Python, where everything tends to be "public" anyway, you just access c.blah directly. If you need c.blah to do something other than the obvious, then you can intercept the access by making a property. Also, super().getData() is overkill by Python standards; self.data is probably fine.

You use the instance variable data in many places, but what exactly does it mean? It would be clearer, for example, if the PNG class had chunks instead of data. Inside, you are storing (index, chunk) tuples, but you always end up discarding the index anyway, so you might as well not store it.

The method names in PNG tend to follow a verb-noun convention, so I suggest renaming edgeDetect to detect_edges.

Printing a message and calling raise is not an appropriate way to handle errors. First, library code shouldn't print anything. Second, raise re-throws an exception that has already been caught. What you should do instead is raise NotImplementedError('Color type not implemented yet').

File handling

Splitting work between the PNG constructor and PNG.readFile() is awkward. When would you ever open(…, "rb") but not proceed to read it too? My suggestion is to design the class this way:

class PNG:
    def __init__(self):
        self.data = []

    def read_file(self, filename):
        with open(filename, 'rb') as f:
            self.read(f)

    def read(self, stream):
        …

    def write_file(self, filename):
        with open(filename, 'wb') as f:
            self.write(f)

    def write(self, stream):
        …

Note that by always calling open() in the context of a with block, you avoid the file handle leak that you had with your writeFile().

Also, I've offered two methods for reading and two methods for writing, in case you want to use, say, a network stream instead of a disk.

Deserialization

This chunk of code in IHDR.parse() is cumbersome:

self.width =  int(data[:4].hex(), 16)
self.height = int(data[4:8].hex(), 16)
self.bit_depth = int(data[8:9].hex(), 16)
self.color_type = int(data[9:10].hex(), 16)

You're taking some bytes, formatting it as an ASCII hex string, and parsing it as a number. To deserialize two 32-bit unsigned ints and five 16-bit unsigned ints, use struct.unpack():

(self.width, self.height, self.bit_depth, self.color_type,
 self.compression_method, self.filter_method, self.interlace_method
) = struct.unpack('>2I5H', data)

---

from Chunk import *
…
c = getattr(self.mod, f.read(4).decode()) #Class
…
i = c(data=f.read(int.from_bytes(length, byteorder='big'))) #Read data

Here, you are instantiating a chunk, whose class is determined by the four-byte string you read from the file. That makes me very nervous. You could end up calling any four-character function or constructor in the main namespace, based merely on whatever chunk code the "image" specified. At the very least, you should check issubclass(c, Chunk) is true before proceeding.

Algorithm

It seems wasteful to use if len(kernel) != 9 to check whether a pixel is at the edge of the image, especially since the way getKernels() works in those cases is by catching an Exception when it tries to access an out-of-bounds neighbor. But as I said, SciPy is probably the way to go if you want to perform a convolution.