CODEWITHSUNDEEP
pythonperformancenumpyopencvoptimization
Program232323
Program232323

Reputation: 57

Fastest way of finding nearest pixel in relation to another pixel while satisying conditions. OpenCV Numpy

I am looking for the fastest way that I can read an image in, specify a pixel, and find the nearest pixel to that pixel given my conditionals.

I originally had a nested loop that would go through each pixel in my 2D image array, check for conditional, than add it to a new array. Than go through the new array and do the distance calculations on each member. That was terribly slow, and has a time complexity of n^2 I believe.

I am now doing the distance calculations, and sorting the array by that, which is quite fast when using numpy. But then I still have to go through that 2D sorted array with a nested loop to check for conditionals, which again is a time complexity of n^2. It does save some time though because I can normally find the pixel I am looking for sooner in the array. 

img2=cv2.imread(filename)
distances = numpy.sqrt((img2[:,:] - currR) ** 2 + (img2[:,:] - currC) ** 2)
nearest = numpy.sort(distances)
for row in range(nearest.shape[0]):
    for col in range(nearest.shape[1]):
        if pixelInLine[row*imgCol + col] == 0  and colorCheck(row,col) and numpy.any(img2[row, col] != 0):
            #do my calculations on the specified pixel. and break the loop

I am unsure how I can optimize this further, and potentially lower the time complexity from n^2 to something more reasonable.

Upvotes: 1

Views: 655

Answers (1)

user1196549
user1196549

Reputation:

Go spiraling away from the target pixel and stop as soon as you meet the "conditionals". For convenience, you can use a square spiral (in fact nested squares).

If the distance is Euclidean, the cost of the search will be between 2d² and 4d² where d is the distance to the hit.

Upvotes: 1

Related Questions