A more efficient way of comparing two images in a python

Python Help
1

I have a task where i need to specify the upper left coordinate of the smaller image in the larger image. I implemented this code, however it is too slow since I have a time limit of 20 seconds, and in some datasets I have 3000 images. How can this be implemented more effectively? I can use numpy, scipy and all packages from the standard python library.

import numpy as np

from PIL import Image

map_image_path = input()
map_image = Image.open(map_image_path)
map_ar = np.asarray(map_image)
map_ar_y, map_ar_x = map_ar.shape[:2]

i = int(input())
dimensions = input()
patches=list()

for k in range(i):
patch_image_path = input()
patches.append(Image.open(patch_image_path))

for j in range(i):
patch_ar = np.asarray(patches[j])
patch_ar_y, patch_ar_x = patch_ar.shape[:2]
stop_x = map_ar_x - patch_ar_x + 1
stop_y = map_ar_y - patch_ar_y + 1

for x in range(0, stop_x):
for y in range(0, stop_y):
x2 = x + patch_ar_x
y2 = y + patch_ar_y
picture = map_ar[y:y2, x:x2]
if np.array_equal(picture, patch_ar):
print(str(x) + “,” + str(y))

1 Like
2

Depending on how big your images are, this may be an unrealistic objective. You are aiming to process 150 images a second. By contrast, a fast video feed is 25 frames per second, and uses some ferocious compression techniques to achieve that.

Actually, you may find some of the tricks and techniques used in video encoding useful. I don’t have any useful references in Python, sorry.

3

Your code performs a per pixel comparison at every position in the original image.
One way to decrease the running time, is to scale the input images and the patch, say using image pyramids (Build image pyramids — skimage v0.19.0.dev0 docs) and if you find a match at a lower resolution try matching at the same relative location (with a range to cover the guassian blur) in a higher resolution until you either fail, or reach the highest resolution.

4

Couple idea

  • use the multi thread for compare multiple image at the time
  • run some image process for extract feature and check if they have same feature before run the inner x y loop scans for exact windows
  • feature extraction with location also help avoid the inner x y loop
  • run multi state machine search like regular expression, combine randomize or pyramid style at the same time. Help avoid generate new matrix during search
  • break matrix to small chunk and use Gpu operation for some parallel search or feature detection