# Decoding grayscale PNG and performing Prewitt operator for edge detection

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__]

f = self.f
try:
while True:
if length == b'':
break
try:
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]
else:
self.data.append(i)
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):
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")
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.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]


# 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]

for y in range(len(pixels)):
y_max = y + radius + 1
for x in range(width):
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
# 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

• Thank you for review. I also noticed myself about adding 'Image-functions' like edge_detect into fileformat class, that happens when I don't have clear idea what I want to do. Do you have any comments about Filter class? Especially about use of method function – Evus Nov 25 '16 at 18:18
• @Evus Updated the answer to try to answer. – Mathias Ettinger Nov 25 '16 at 20:43
• Is there reason why filter-methods is outside of PNG class? – Evus Nov 26 '16 at 11:06
• @Evus Because if they were @staticmethods of PNG, then you couldn't define UNFILTER_METHOD as a class constant since PNG.paeth for instance would raise a NameError: name 'PNG' is not defined – Mathias Ettinger Nov 26 '16 at 11:09

## 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 = []

with open(filename, 'rb') as f:

…

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 *
…

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.
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.
• Thank you for your review. I knew about NumPy and ScriPy but because this is my learning excercise I didn't want to use any 3th party-libs. I tried to use struct.unpack, but docs weren't clear to me so I made hacky-choice. On algorithm side if len(kernel) != 9 is way to avoid unnecessary math. Well I really need to dig into PEB8 and get my style right and try to find another way for chunks. – Evus Nov 26 '16 at 11:03