How to optimize these nested loops?

Question

I'm trying to count the number of times a colour (or a closest match to one of 17 colours) appears in the pixels of an image (given as 300x300x3 np array, float values [0,1]). I've written this but it seems to be extremely inefficient:

for w in range(300):
    for h in range(300):
        colordistance = float('inf')
        colorindex = 0
        for c in range(17):
            r1 = color[c, 0]
            g1 = color[c, 1]
            b1 = color[c, 2]
            r2 = img[w, h, 0]
            g2 = img[w, h, 1]
            b2 = img[w, h, 2]
            distance = math.sqrt(
                ((r2-r1)*0.3)**2 + ((g2-g1)*0.59)**2 + ((b2-b1)*0.11)**2)
            if distance < colordistance:
                colordistance = distance
                colorindex = c
        colorcounters[colorindex] = colorcounters[colorindex] + 1

Are there any ways I can improve the efficiency of this bit? I'm already using multiprocessing for an outer loop.

In your 5th line you are missing the value for range. I'm assuming it's 3? Also, have you considered using generators? I could elaborate on it if you haven't heard of it before — Haris Nadeem, Apr 06 '18 at 16:44
@HarisNadeem it's 17 - checking against each colour. The images are fetched from an h5 file - it's just this loop that takes a very long time. — Alex, Apr 06 '18 at 16:47
You can short-circuit the inner for-loop by first checking for an exact match `if all([a==b for a, b in [(r1, r2), (g1, g2), (b1, b2)]]): colorcounters[c] += 1; continue` — thebjorn, Apr 06 '18 at 16:54
@thebjorn the images are real-world photos and I'm only checking against 17 webcolors, hence why I'm computing the distance. The cases where they're going to be exactly equal are very limited in number. — Alex, Apr 06 '18 at 16:59
ok, but real-world images have lots of the same colors which means you can cache the result of the distance calculation on `(r2,g2,b2)`. Also the implementation of `color` seems inefficient for this many lookups. (and you should probably not use the `**` operator) — thebjorn, Apr 06 '18 at 17:03
ps: processing tiles instead of pixel lines will improve the locality of the color detection (and potentially allow you to spread the calculation to more CPUs). — thebjorn, Apr 06 '18 at 17:05
Getting rid of `math.sqrt` will speed up the computation. Also, what are the constants 0.3, 0.59, and 0.11 in that computation? — Bill the Lizard, Apr 06 '18 at 17:07
By webcolor I mean the colors in css2.1. There's 17 defined by name. — Alex, Apr 06 '18 at 17:10
@BilltheLizard it's the relative contributions to luminance of red green blue. — thebjorn, Apr 06 '18 at 17:11
@BilltheLizard the constants are due to the way human eyes perceive color. Look up how RGB to Grayscale computations are being performed for more on that idea. I've got a reasonable performance increase with numba, thanks jpp. I'll refactor it a bit and let you know if it's any better, thanks for the answers. — Alex, Apr 06 '18 at 17:12
There are much faster ways to calculate rgb to grayscale. This might be a good starting point: https://stackoverflow.com/questions/596216/formula-to-determine-brightness-of-rgb-color — thebjorn, Apr 06 '18 at 17:15
@thebjorn I don't do rgb to grayscale computations, I was just pointing out a good way to understand the constants Bill was asking about. — Alex, Apr 06 '18 at 17:19
Hmm.. I think you might be using those constants incorrectly (see e.g. the color difference article on wikipedia).. in any case, you can remove the call to `math.sqrt` since the relative ordering will stay the same for the squared values. — thebjorn, Apr 06 '18 at 17:44
it depends on what you mean by "efficient". If you mean "computationally efficient" ... this is exactly what numpy "broadcasting" was designed for. Basically breaking up the image into multiple matrices, doing simple operations on each, and then recombining them in some fashion. If you mean "elegant", you need to look into "data driven" programming in combination with "message passing"... meaning, let each cell of the data decide what to do with itself. Broadcasting:https://docs.scipy.org/doc/numpy-1.13.0/user/basics.broadcasting.html — snakes_on_a_keyboard, Apr 06 '18 at 17:47

score 0 · Accepted Answer · answered Apr 06 '18 at 18:19

You mentioned you're using numpy, so you should avoid iterating as much as possible. My vectorized implementation is about 40x faster. I made a few changes to your code so they could use the same arrays and so that I could verify correctness. This may affect the speed.

import numpy as np
import time
import math

num_images = 1
hw = 300 # height and width
nc = 17  # number of colors
img = np.random.random((num_images, hw, hw, 1, 3))
colors = np.random.random((1, 1, 1, nc, 3))

## NUMPY IMPLEMENTATION
t = time.time()

dist_sq = np.sum(((img - colors) * [0.3, 0.59, 0.11]) ** 2, axis=4)  # calculate (distance * coefficients) ** 2
largest_color = np.argmin(dist_sq, axis=3)  # find the minimum
color_counters = np.unique(largest_color, return_counts=True) # count
print(color_counters)
# should return an object like [[1, 2, 3, ... 17], [count1, count2, count3, ...]]

print("took {} s".format(time.time() - t))

## REFERENCE IMPLEMENTATION
t = time.time()
colorcounters = [0 for i in range(nc)]
for i in range(num_images):
    for h in range(hw):
        for w in range(hw):
            colordistance = float('inf')
            colorindex = 0
            for c in range(nc):
                r1 = colors[0, 0, 0, c, 0]
                g1 = colors[0, 0, 0, c, 1]
                b1 = colors[0, 0, 0, c, 2]
                r2 = img[i, w, h, 0, 0]
                g2 = img[i, w, h, 0, 1]
                b2 = img[i, w, h, 0, 2]

                # dist_sq
                distance = math.sqrt(((r2-r1)*0.3)**2 + ((g2-g1)*0.59)**2 + ((b2-b1)*0.11)**2)  # not using sqrt gives a 14% improvement

                # largest_color
                if distance < colordistance:
                    colordistance = distance
                    colorindex = c
            # color_counters
            colorcounters[colorindex] = colorcounters[colorindex] + 1
print(colorcounters)
print("took {} s".format(time.time() - t))

How to optimize these nested loops?

1 Answers1