So… I’m just getting back into python coding to see if my idea for a custom codec is viable. I’ve been working on implementing the Hoffman algorithm. I go through each pixel in a picture and find how often the rgba values are used. I’ve come up with this code: http://pastebin.com/t5kPS6yf
I set up a test 512x512 image. The script has to read slightly over 1million bytes. The problem is that it takes forever. Is creating a custom codec viable in blender.
The main reason for the slow performance is the way you access the .pixels, never ever access them directly, but use a copy!
Here’s some of your script, made pythonic:
import bpy
import os.path
from collections import defaultdict
dirpath = r"C:\Users\Joe\Desktop\codec est"
numFrames = 1
for frameNum in range(numFrames):
filename = "stills%04i.png" % frameNum
img = bpy.data.images.load(filepath=os.path.join(dirpath, filename))
pixels = img.pixels[:]
d = defaultdict(int)
for p in pixels:
d[int(p*255)] += 1
print("%s completed" % filename)
Note that the elements in .pixels are R, G, B and Alpha values after another in a flat list. You might want to count them separately?!
You should consider using numpy, which is bundled with Blender since 2.70 on all platforms. It has a great performance at number crunching and comes with a lot of features for statistical analysis.
Thank you, that does make sense on the performance.
I thought python couldn’t be having such speed issues soley by it beeing an interpreted language.
I will have to get more familiar with the string operators, but that will come in time.
I’ve been trying to uderstand this old example of Hoffman algorithm:http://stackoverflow.com/questions/11587044/how-can-i-create-a-tree-for-huffman-encoding-and-decoding
It’s incomplete and from what I understand the walk_tree function was never completed.
This is what I believe would make sense for that function to look like:
def walk_tree(node, prefix="1", code={}):
code[key] = prefix
j , k = node.children()
if j != None and k != None:
walk_tree(j,prefix+'0',code)
walk_tree(k,prefix+'1',code)
return(code)
The ‘1’ and ‘0’ might be reversed.
What I don’t understand is why “node” is a tuple or how I’m suppose to know the key inside walk_tree.
I thought python couldn’t be having such speed issues soley by it beeing an interpreted language.
It’s Blender’s fault, not python’s. .pixels is a Blender data structure, and it’s not very fast if accessed for individual pixels. If you make it a python tuple - img.pixels[:] is equivalent to tuple(img.pixels) - it will become pretty fast. Fast enough for what you try, although C code could do much faster.
I have no time to read about that algorithm, so just a quick note on your if-condition:
if j != None and k != None:
!= to check for None is discouraged, use “is” or “is not” instead (equality check, it’s always the same object):
if j is not None and k is not None:
You could also make it shorter and more pythonic by using:
if None not in (j, k):
I took a little break came back and look at it(gotta do it sometimes to get a fresh view)
I got it working with this code:
def walk_tree(node, prefix="", code={}):
weight , k = node
if type(k) is str:
code[k] = prefix
else:
left , right = k.children()
walk_tree(left,prefix+'0',code)
walk_tree(right,prefix+'1',code)
return(code)
I don’t see any problem with testing the type of a variable.
Now I’m going to work on implementeing the method in my code.
That’s great!
Can you share the full code?
if type(k) is str:
works ok, but recommended is:
if isinstance(k, str):
You can actually leave out the parenthesis here:
return(code)Well, it outputs data, not sure if it’s valid data
A test would be that all the codes are unique and none of the smaller codes are the beginning of longer codes.
I don’t know if I understood this correctly, but when I tried making the keys of the priorityqueue into ints, it found identical values and didn’t know how to order it. I assume it tried to compare the other object in the tuple(the hoffmanNode object). It have me this error
TypeError: unorderable types: HuffmanNode() < str()
I don’t think it matters the order of values that are the same, but I just overloaded some boolean operators to make it work.
import bpy
import os.path
import queue
from collections import defaultdict
dirpath = r"C:\Users\Joe\Desktop\codec est"
numFrames = 1
d = defaultdict(int)
pq = queue.PriorityQueue()
class HuffmanNode(object):
def __init__(self, left=None, right=None, root=None):
self.left = left
self.right = right
self.root = root # Why? Not needed for anything.
def children(self):
return((self.left, self.right))
def __gt__(self, other):
return True
def __lt__(self, other):
return False
for frameNum in range(numFrames):
filename = "stills%04i.png" % frameNum
img = bpy.data.images.load(filepath=os.path.join(dirpath, filename))
pixels = img.pixels[:]
for p in pixels:
d[int(p*255)] += 1
print("%s completed" % filename)
def create_tree():
for value in range(d.__len__()):
pq.put((d[value],value))
while pq.qsize() > 1: # 2. While there is more than one node
l, r = pq.get(), pq.get() # 2a. remove two highest nodes
node = HuffmanNode(l, r) # 2b. create internal node with children
pq.put((l[0]+r[0], node)) # 2c. add new node to queue
return pq.get() # 3. tree is complete - return root node
node = create_tree()
print("tree created")
# Recursively walk the tree down to the leaves,
# assigning a code value to each symbol
def walk_tree(node, prefix="", code={}):
weight , k = node
if type(k) is int:
code[k] = prefix
else:
left , right = k.children()
walk_tree(left,prefix+'0',code)
walk_tree(right,prefix+'1',code)
return(code)
code = walk_tree(node)
for i in range(255):
print(i, ' ' + str(d[i]) + ' ', code[i])
Edit : After some thinking I added some code to test that the codes are unique and that none of the smaller codes are the beginning of any of the bigger codes. Here is what I used:
boo = False
for i in range(255):
foo = code[i]
length = len(foo)
for j in range(255):
if(i != j and foo == code[j][:length]):
boo == True
print(boo)
I can’t definitively say the codes are valid, but the test didn’t disprove it either. Next step is creating a file header that contains the code and a body that contains the compressed data.
Edit: Edit: I just added some code to estimate the file size. Uncompressed, the pictures would average 1megabyte, I’m predicting the compressed file size will be 129kbytes. The test images are 93kbytes. Not bad for 1 layer of compression. I might be able to 93kbyts if I do multiple passes or incorporate other compression algorithms.
Thought I would just post my progress. The size is about double was a thought it was going to be. Maybe I didn’t factor in that some of the codes are longer then others, but it is smaller then the uncompressed versions. File size so far is compressed from 1MG to 253kb. I’ve verified the length of everything except for the main body of data.
import bpy
import os.path
import queue
from collections import defaultdict
dirpath = r"C:\Users\Joe\Desktop\codec est"
numFrames = 1
d = defaultdict(int)
pq = queue.PriorityQueue()
class HuffmanNode(object):
def __init__(self, left=None, right=None, root=None):
self.left = left
self.right = right
self.root = root # Why? Not needed for anything.
def children(self):
return((self.left, self.right))
def __gt__(self, other):
return True
def __lt__(self, other):
return False
#load and count pixel data
for frameNum in range(numFrames):
filename = "stills%04i.png" % frameNum
img = bpy.data.images.load(filepath=os.path.join(dirpath, filename))
pixels = img.pixels[:]
for p in pixels:
d[int(p*255)] += 1
print("%s completed" % filename)
def create_tree():
for value in range(d.__len__()):
pq.put((d[value],value))
while pq.qsize() > 1: # 2. While there is more than one node
l, r = pq.get(), pq.get() # 2a. remove two highest nodes
node = HuffmanNode(l, r) # 2b. create internal node with children
pq.put((l[0]+r[0], node)) # 2c. add new node to queue
return pq.get() # 3. tree is complete - return root node
node = create_tree()
print("tree created")
# Recursively walk the tree down to the leaves,
# assigning a code value to each symbol
def walk_tree(node, prefix="", code={}):
weight , k = node
if type(k) is int:
code[k] = prefix
else:
left , right = k.children()
walk_tree(left,prefix+'0',code)
walk_tree(right,prefix+'1',code)
return(code)
code = walk_tree(node)
myArray = bytearray()
pictureWidth = 512
pictureHeight = 512
myArray.append((pictureWidth >> 8) & 0xff)
myArray.append((pictureWidth << 8) & 0xff)
myArray.append((pictureHeight >> 8) & 0xff)
myArray.append((pictureHeight << 8) & 0xff)
#get max length of code
maxLen = 0
for i in range(len(code)):
if(len(code[i]) > maxLen):
maxLen = len(code[i])
print('longest code is ' + str(maxLen) + ' bits')
myArray.append(maxLen)
currentLen = 1
while True:
myArray.append(0)
for i in range(256):
if(len(code[i]) == currentLen):
#print(code[i])
myArray[len(myArray)-1] += 1
if currentLen == maxLen:
break
else:
currentLen += 1
currentLen = 1
outputString = ""
while True:
for i in range(256):
if(len(code[i]) == currentLen):
#append value
outputString += "{0:08d}".format(i)
#append code
outputString += code[i]
if currentLen == maxLen:
break
else:
currentLen += 1
#add body
for frameNum in range(numFrames):
filename = "stills%04i.png" % frameNum
img = bpy.data.images.load(filepath=os.path.join(dirpath, filename))
pixels = img.pixels[:]
for p in pixels:
outputString += code[int(p*255)]
#add padding to end of file
for i in range(8-(len(outputString)%8)):
outputString += "0"
#convert outputString to bytearray
for j in range(int(len(outputString)/8)):
tempNum = 0
substring = outputString[j:j+8]
for k in range(1,9):
tempNum += 256/(2**k)
myArray.append(int(tempNum))
f = open("C:\\Users\\Joe\\Desktop\\codec\ est1234","wb")
f.write(myArray)
f.close()