[Tutor] speeding code along

[Danny Yoo]

Hi Thomi,


Let's take a look at the loop, since that's where all the action is.


>         for x in range(convfile.size[0] - 1):
>                 for y in range(convfile.size[1] - 1):
>                         pixel = convfile.getpixel((x,y))
>                         tempdistance = 6000
>                         for color in inpalette:
>                                 distance = sqrt( (color[0] -
> pixel[0])**2 + (color[1] - pixel[1])**2 + (color[2] - pixel[2])**2 )
>                                 if distance < tempdistance:
>                                         tempdistance = distance
>                                         tempcolor = color
>                                 if tempdistance == 0:
>                                         break
>                         convfile.putpixel((x,y),tempcolor)


This chunk of code is trying to match, for every pixel on your image, the
closest color that's available in a list of palette colors.  The innermost
loop is concerned about grabbing the best palette color it can that
matches an arbitrary color.



We can refactor this temporarily by pulling the inner part into a separate
function:

###
def best_fitting_color(pixel):
    tempdistance = 6000
    for color in inpalette:
        distance = sqrt( (color[0] - pixel[0])**2
                       + (color[1] - pixel[1])**2
                       + (color[2] - pixel[2])**2 )
        if distance < tempdistance:
            tempdistance = distance
            tempcolor = color
        if tempdistance == 0:
            return tempcolor
###

The refactoring will temporarily slow the actual program down, but will
help us to concentrate on the performance critical stuff.


It looks like you're trying to find the right palette color that minimizes
color distance, with the following:

###
for color in inpalette:
    distance = sqrt(  (color[0] - pixel[0])**2
                    + (color[1] - pixel[1])**2
                    + (color[2] - pixel[2])**2 )
###

where you're taking the Euclidean distance of the colors.  However, we
really only care about picking the palette color that minimizes distance,
and we really don't need to keep track of the exact distance.  We can
reduce some of the cost by omitting the square root calculation
altogether!


###
for color in inpalette:
    distance = (color[0] - pixel[0])**2
               + (color[1] - pixel[1])**2
               + (color[2] - pixel[2])**2 )
###



Also, does your palette change a lot?  If not, then it might be really
worth precalculating the optimum palette colors for all possible colors.


If precalculation is possible, then you can do all of the calculation work
up front.  That way, all future color-fittings look like a very fast
lookup.  Sorta like this:


###
class _PrecachedColorFitting:
    def __init__(self, palette,
                 r_range=range(256),
                 g_range=range(256),
                 b_range=range(256)):
        self.palette = palette
        self.bestchoice = {}
        for r in r_range:
           for g in g_range:
               for b in b_range:
                   pixel = (r,g,b)
                   self.bestchoice[pixel] = best_fit(pixel)


    def best_fit(self, pixel):
        tempdistance = 6000
        for color in self.palette:
            distance = ( (color[0] - pixel[0])**2
                       + (color[1] - pixel[1])**2
                       + (color[2] - pixel[2])**2 )
            if distance < tempdistance:
                tempdistance = distance
                tempcolor = color
            if tempdistance == 0:
                break
        return tempcolor


    def __call__(self, pixel):
        return self.bestchoice[pixel]

best_fitting_color = _PrecachedColorFitting
###


And if calculating this is expensive at the beginning of every program
start, we can always save the whole dictionary to disk, so that we only
pay the cost of calculation once.  Disk space is cheap: use it!  *grin*


With these changes, your loop will look much cleaner:

###
for x in range(convfile.size[0] - 1):
    for y in range(convfile.size[1] - 1):
        pixel = convfile.getpixel((x,y))
        convfile.putpixel((x,y), best_fitting_color(pixel))
###

and will probably run faster, to boot!


Good luck to you!