More efficient filtering of multiple lists and nested for loops

user_12001081 0
Viewed 122

I am trying to find the locations of objects across 3 overlayed images. Essentially I take an image in 3 different spectrums and overlay them for data extraction of concentrations. I run a circle analysis on it and then compare each item to see if it is close enough to be overlapping. The below algorithm is working but the number of comparisons makes this algorithm run for around 2 mins each time and I need it to be something like 1-5 seconds each time as I have to do hundreds of the comparisons in the final product.

I am midway in trying more complex algorithms but thought I would ask since there may be a much simpler way and I am overthinking it.

My lists are on average 100-500 items long.

I thought this may be helpful but I don't see how I can run all of my comparisons within it or how it would be faster (I may just be dumb).

"Better" algorithms:

  1. divide the images into multiple overlapping sectors and doing the same comparison in each region then filtering out the overlap. I have done something similar before but the final filter was exceedingly complicated.

  2. Sort all 3 lists into a single list that is "diagonally" sorted and comparing each item to one or two away from its location. Currently, my sorting algorithm is to slow to be useful and I can't fix the "localization" problem.

  3. (Currently the forerunner) I am taking the 3 images mixing them into one, overlaying my previous detection algorithm, taking the average color of the feature, and then running a clustering algorithm to separate it.

  circles_array = [[circles_blue, len(circles_blue)], [circles_green, len(circles_green)], [circles_grey, len(circles_grey)]]
  circles_array = sorted(circles_array, key=lambda x: x[1], reverse=True)

  shortest = circles_array[2][0]
  middle = circles_array[1][0]
  longest = circles_array[0][0]
  
  # CLASSIFYwhe
  perfect_drops = 0
  perfect_list = []

  print("Running sort, please wait...")
  for s in shortest:
    for m in middle:
      for l in longest:
        if s[1] < m[1]+50 and s[1] > m[1]-50:
          if s[1] < l[1]+50 and s[1] > l[1]-50:
            if s[0] < m[0]+50 and s[0] > m[0]-50:
              if s[0] < l[0]+50 and s[0] > l[0]-50: 
                perfect_drops += 1
                perfect_list.append([s,m,l])

EXAMPLE INPUTS

enter image description here

enter image description here enter image description here

opencv image-processing for-loop python performance
1 Answers

In essence your program compares three lists of numbers by iterating over each combination. If the lists have n elements, you are doing n3 comparisons. This is highly inefficient. You could instead map the green to the gray, and then the blue to the gray, leading to only 2n2 comparisons. Still, it is not necessary to do this looping, since images provide a spatial indexing for you. You can find the location of each circle in the gray image, then look at those locations in the green and blue images to see if those pixels are bright enough to consider them "on".

This is made slightly difficult by the slightly overlapping circles, and by the slight displacement between the images. It might be necessary to do an image registration first if the displacement gets worse than in this example.

This is how I would implement it using DIPlib:

import diplib as dip
import numpy as np

gray = dip.ImageRead('kv8A9.jpg')
blue = dip.ImageRead('KZmTq.jpg')
blue = blue(2)
green = dip.ImageRead('nqIwo.jpg')
green = green(1)

blue = blue > 90    # some threshold, tweak as necessary
green = green > 75  # idem

s = dip.Watershed(gray, connectivity=2, maxDepth=20, flags={'labels','high first'})

msr = dip.MeasurementTool.Measure(s, features=['Size'])
msr_blue = dip.MeasurementTool.Measure(s, dip.Convert(blue, 'UINT8'), features=['Mean'])
msr_green = dip.MeasurementTool.Measure(s, dip.Convert(green, 'UINT8'), features=['Mean'])

isblue = np.array(msr_blue['Mean']) > 0.67    # sufficient overlap = 67%
isgreen = np.array(msr_green['Mean']) > 0.67
islarge = np.array(msr['Size']) > 4000        # sufficiently large to be a circle

value = np.ones(isblue.shape)
value[isblue] = 3            # maps to blue in the "labels" color map of DIPlib
value[isgreen] = 2           # maps to green
value[isblue & isgreen] = 5  # maps to cyan=green+blue
value[~islarge] = 0
value = value.squeeze()
index = msr.Objects()
out =  dip.LookupTable(s, value, index, interpolation='nearest', mode='values', lowerValue=0, upperValue=0)

colorized display of out

Of course you don't need to do the last segment, that is just to create the display. isblue & isgreen gives you the regions that have sufficient brightness in both green and blue. You should only count those where islarge is True, as the other regions are too small to be considered a circle.

You will have to tweak thresholds as appropriate.

This code runs in a fraction of a second.

user_73287820
Related