Use numpy to quickly iterate over pixels

user_3188364 0
Viewed 1056

I have two images of resolution 4095x4095 and every pixel has a different color (no duplicate pixels within one image). I am trying to build a "map" describing the movement of each pixel between the two images.

What I have now is a working, but very naive algorithm, that simply loops through all pixels until it finds a match, at which point it moves to the next pixel. This is approach would take several years to iterate over all pixels in my images. I was wondering if I could use numpy to speed this up. So far I wasn't able to make it work.

Working, but slow algorithm:

import PIL
import time
from PIL import Image

raw = Image.open('image1.png')
rawLoad = raw.load()
rendered = Image.open('image2.png')
renderedLoad = rendered.load()
counter = 1
timer = time.time()

for rendered_x in range(rendered.width):
        for rendered_y in range(rendered.height):
            for raw_x in range(raw.width):
                    for raw_y in range(raw.height):
                        if rawLoad[raw_x, raw_y] == renderedLoad[rendered_x, rendered_y]:
                            print('Found pixel no. '+str(counter)+' pos '+str(rendered_x)+' '+str(rendered_y)+' in position '+str(raw_x)+' '+str(raw_y)+'. Took '+str(round(time.time() - timer, 2))+' s.')
                            break
                    else:
                        continue
                    break
            counter += 1
            timer = time.time()

And the output:

Found pixel no. 1 pos 0 0 in position 2710 901. Took 6.29 s.
Found pixel no. 2 pos 0 1 in position 2148 901. Took 4.84 s.
Found pixel no. 3 pos 0 2 in position 1793 1365. Took 3.92 s.
Found pixel no. 4 pos 0 3 in position 774 1365. Took 1.54 s.
Found pixel no. 5 pos 0 4 in position 4049 1365. Took 7.93 s.
Found pixel no. 6 pos 0 5 in position 2982 1373. Took 4.94 s.
Found pixel no. 7 pos 0 6 in position 2163 1373. Took 4.41 s.
Found pixel no. 8 pos 0 7 in position 1286 1822. Took 2.17 s.
Found pixel no. 9 pos 0 8 in position 211 1822. Took 0.34 s.
Found pixel no. 10 pos 0 9 in position 2710 1813. Took 4.23 s.
Found pixel no. 11 pos 0 10 in position 1891 1813. Took 2.98 s.

If somebody with more numpy experience could show me the direction, that would be highly appreciated.

python-imaging-library numpy python
3 Answers

You can get an O(n) algorithm if you're willing to use O(n) space. Make a dictionary containing the pixel values as key and the location of that pixel as the value. Code example:

# Assume raw_img and rendered_img are saved as variables

height, width = raw_img.shape

# Save all values from raw_img in dictionary
img_dict = {}
for i in range(height):
    for j in range(width):
        pixel_val = raw_img[i, j]
        img_dict[pixel_val] = (i, j)


# Loop over the values in the rendered img and lookup in dictionary
for i in range(height):
    for j in range(width):
        pixel_val = rendered_img[i, j]
        if pixel_val in img_dict:
            raw_img_coord = img_dict[pixel_val]
            print(f"Found pixel {pixel_val} at {i, j} in rendered_img matching " +
                  f"pos {raw_img_coord} in raw_img")
user_92487930

I suspect that the best you can do using pure numpy is an O(N log N) solution, using argsort. Numpy does not support hash-tables directly.

Let's say you have a pair of 2D images, A and B. The argsort of one tells you how to place the pixels in sorted order (which is the same for both). The inverted argsort of the other tells you how to place those pixels into the other:

toSortedA = np.argsort(A.ravel())
fromSortedB = np.argsort(np.argsort(B.ravel()))

Now you can convert A into B by indexing it with

index = np.unravel_index(toSortedA[fromSortedB], A.shape)

This assumes that all pixels are the same between images, just shuffled around.

PS

The other answers correctly specify an O(n) algorithm that also works for non-shuffled images using dicts. For completeness, here is a shorter (and likely faster) way to construct the lookup table:

it = np.nditer(raw_image, flags=['multi_index'])
raw_dict = {pixel.item(): it.multi_index for pixel in it}

The pixel value yielded by nditer is a view into the array, so you can actually modify as you go if you need to.

user_29887300

Try using dictionary.
Since you mentioned each image has unique set of pixels within itself, then simply iterate of that image's pixels once to enumerate or store the pixel description as a key in the dictionary with value as its position. Once you are done with both the images' dictionaries, it would be crazy quick to compare the two by checking existence of keys of one in the other.

pseudo-code:

raw = Image.load(raw)
rendered = Image.load(rendered)

raw_dict = {}
rendered_dict = {}

for(i,j in row,col in raw):
    raw_dict[raw[i][j]] = str(i)+"_"+str(j)

for(i,j in row,col in rendered):
    rendered_dict[rendered[i][j]] = str(i)+"_"+str(j)

Now you have two dictionaries with all pixels info.
Iterate over one of those to check presence of key in the other dictionary.

for(key in rendered_dict):
    if(raw_dict.containsKey(key)):
        print("Found match: Rendered(",rendered_dict[key],") at Raw(",raw_dict[key]")")

With this approach, you will at best iterate over the pixels thrice in linear order.

Do share the results in terms of time of execution.

user_35368190
Related