Fast absolute difference of two uint8 arrays

Question

I have two numpy-arrays with dtype=np.uint8 - like this:

img1=np.uint8(np.random.randint(0, 255, (480, 640)))
img2=np.uint8(np.random.randint(0, 255, (480, 640)))

And I want to build the positive difference of these arrays.

Here are my first two approches (and a third one for reference):

def differenceImageV1(img1, img2):
  diff=np.empty_like(img1)
  h, w=img1.shape
  for y in range(h):
    for x in range(w):
      if img1[y, x]<img2[y, x]: diff[y, x]=img2[y, x]-img1[y, x]
      else:                     diff[y, x]=img1[y, x]-img2[y, x]
  return(diff)

def differenceImageV2(img1, img2):
  return(np.uint8(np.absolute(np.int16(img1)-np.int16(img2))))

def differenceImageV3(img1, img2):  # fast - but wrong result
  return(img1-img2)

I get these execution times (and the sums to check, if they are equal):

  10x: 1893.54 ms  np.sum=26122208
1000x:  411.71 ms  np.sum=26122208
1000x:   26.60 ms  np.sum=39123624

Is there a way to get a correct result faster as with V2 ?

Answer 1

Here's one approach that is significantly faster than V2: take img1-img2, and multiply by 1 or -1 depending on img1>img2. Here's how it is implemented:

def differenceImageV6(img1, img2):
  a = img1-img2
  b = np.uint8(img1<img2) * 254 + 1
  return a * b

A test harness for testing performance:

import numpy as np

img1=np.uint8(np.random.randint(0, 255, (480, 640)))
img2=np.uint8(np.random.randint(0, 255, (480, 640)))

def differenceImageV1(img1, img2):
  diff=np.empty_like(img1)
  h, w=img1.shape
  for y in range(h):
    for x in range(w):
      if img1[y, x]<img2[y, x]: diff[y, x]=img2[y, x]-img1[y, x]
      else:                     diff[y, x]=img1[y, x]-img2[y, x]
  return(diff)

def differenceImageV2(img1, img2):
  return(np.uint8(np.abs(np.int16(img1)-img2)))

def differenceImageV3(img1, img2):  # fast - but wrong result
  return(img1-img2)

def differenceImageV4(img1, img2):
  return np.where(img1>img2, img1-img2, img2-img1)

def differenceImageV5(img1, img2):
  a = img1-img2
  b = img2-img1
  c = img1>img2
  return a*c + b*(~c)

def differenceImageV6(img1, img2):
  a = img1-img2
  b = np.uint8(img1<img2) * 254 + 1
  return a * b

import timeit
def testit():
  for fn in [differenceImageV2, differenceImageV3, differenceImageV4, differenceImageV5, differenceImageV6]:
    print fn.__name__, np.sum(fn(img1, img2).astype('int64')),
    print timeit.timeit("%s(img1, img2)" % fn.__name__, "from test import img1, img2, %s" % fn.__name__, number=1000)

if __name__ == '__main__':
    testit()

and resulting performance numbers:

differenceImageV2 26071358 0.982538938522
differenceImageV3 39207702 0.0261280536652
differenceImageV4 26071358 1.36270809174
differenceImageV5 26071358 0.220561981201
differenceImageV6 26071358 0.154536962509

differenceImageV6 is about 6x slower than the incorrect differenceImageV3, but still about 6x faster than the previous best differenceImageV2. differenceImageV1 isn't tested because it's easily a few orders of magnitude slower than the rest.

Note: I included an np.where approach for comparison; I thought it might have good performance but it turns out to be fairly poor. It seems that performing slicing by a boolean array is quite slow in NumPy.

Answer 2

If you have opencv available, you can also use:

def differenceImageV4(img1, img2):
  return cv2.absdiff(img1, img2)

which is almost the same speed as differenceImageV3.