9
\$\begingroup\$

In the picture below there are some regions which are very bright (i.e. more white). Some bright regions are wide and some are narrow or thin. The red box covers one such wide bright spot, and blue box covers one thin bright spot. Thin bright spots are called edges and wide bright spots are called hot-spots.

I want to remove all the hot-spots from the image (i.e. make them black), but no edge should be removed.

I've written Python code (using OpenCV) to remove all hot-spots but not the edges.

enter image description here

My code:

import cv2 import numpy as np # Load the image image1 = cv2.imread('orange.jpg', cv2.IMREAD_GRAYSCALE) original_image = image1 # Otsu's thresholding _, image2 = cv2.threshold(image1, 0, 255, cv2.THRESH_BINARY + cv2.THRESH_OTSU) # Erosion kernel = np.ones((5, 5), np.uint8) image3 = cv2.erode(image2, kernel, iterations=1) # Define the threshold distance K K = 2 # Create the circular mask mask = cv2.getStructuringElement(cv2.MORPH_ELLIPSE, (2 * K, 2 * K)) # Iterate over image1 pixels and generate the final image final_image = np.copy(image1) for y in range(image1.shape[0]): for x in range(image1.shape[1]): # Check if any illuminated pixel exists within K distance in image3 if image2[y, x] > 0: neighborhood = image3[max(y - K, 0):min(y + K + 1, image3.shape[0]), max(x - K, 0):min(x + K + 1, image3.shape[1])] if np.sum(neighborhood) > 0: final_image[y, x] = 0 # Display the original and final image cv2.imshow('Original', original_image) cv2.imshow('Final Image', final_image) cv2.waitKey(0) cv2.destroyAllWindows()

Output: output image

My question:

How can I reduce the computational complexity of my code? My code's complexity is O(n²) because of the two nested for loops; how can I make it O(n) or O(n log n)?

\$\endgroup\$
1
  • 2
    \$\begingroup\$ Please do not edit the question, especially the code, after an answer has been posted. Changing the question may cause answer invalidation. Everyone needs to be able to see what the reviewer was referring to. What to do after the question has been answered. \$\endgroup\$ Commented Jun 6, 2023 at 14:02

1 Answer 1

Reset to default
9
\$\begingroup\$

np.sum(neighborhood) is computing the mean filter with a rectangular neighborhood (sum filter, really, but since you compare to 0, the scaling doesn’t matter). This filter can be applied in OpenCV with cv.blur.

You then compare to 0 for pixels where image2 is larger than 0. So you can combine the result of the two full-image comparisons with the logical AND operator, and use the result to index into the output image.

I think the following code is equivalent to your loop (not tested, use with care):

final_image[ (cv.blur(image3, [2*K+1, 2*K+1]) > 0) & (image2 > 0) ] = 0

Note that the complexity of you code is O(n), for n pixels in the image. The double loop iterates once over all pixels. The complexity of the line I wrote here is still O(n). The difference is that the loop over all pixels in OpenCV is written in a compiled language, which is much faster than the Python interpreter.

Note also that the code in the OP computes the sum over the neighborhood only for some pixels, the code in this answer does it for all pixels. But in the OP, each sum is O(K²), whereas here it is O(1), independent of the size of the neighborhood. It is computed with only 3 additions per pixel. So even if we compute the filter at many more pixels, we’re computing it with fewer operations overall (even when ignoring the extra overhead of the Python interpreter).

As I commented on your (now deleted) post over at Stack Overflow, you are using names well established in the field of image processing, and giving them a different meaning. This makes communication difficult. An edge is a sharp transition in intensity, which typically marks the boundary of an object in the image. You referring to a line as an edge is highly confusing.

Now for the code review itself:

image1, image2, image3 are not meaningful names. Other variables holding images have good names. image1 seems to be an alias for original_image, which is not used.

People will complain about variable names K and x, y, because variable names are supposed to be long and descriptive. I personally like x, y for loops over a coordinate system, it is very clear and any other names will be less clear IMO. K could be threshold_distance, for example.

Another typical comment here would be to put your code in a reusable function, scripts are easy to type but much less flexible.

I would also suggest adding more vertical space, a blank line between code blocks can increase readability significantly.

\$\endgroup\$
7
  • 1
    \$\begingroup\$ I have used two for loops that means brute force approach, how would you say it is O(n) ? Not understand. \$\endgroup\$ Commented Jun 4, 2023 at 17:58
  • 2
    \$\begingroup\$ @AlokMaity OK, one loop does image1.shape[0] iterations, the other does image1.shape[1]. The code in the middle is run image1.shape[0] * image1.shape[1] times. This product is the total number of pixels, which is n in my O(n) notation. If an algorithm touches each pixel once, we say it’s an O(n) algorithm. O(n^2) would be an algorithm that touches each pixel in the image for each pixel in the image, for example a direct computation of the DFT sum, rather than using the FFT algorithm which is O(n log n). \$\endgroup\$ Commented Jun 4, 2023 at 18:03
  • 2
    \$\begingroup\$ @AlokMaity O(1) per pixel, yes. You’re doing that. O(1) per image, no. You need to visit each pixel to determine whether you need to set it so 0 or not. There is no way to make this less than O(n). Even displaying an image to the screen is an O(n) operation. You have n values, and you need to do something with each of them. That is O(n) per definition. —— Note that this has nothing to do with speed. Your code is slow because Python is interpreting your code, not because it is O(n). \$\endgroup\$ Commented Jun 4, 2023 at 19:46
  • 2
    \$\begingroup\$ @AlokMaity O() notation is not about speed, it is about scaling. If processing an image with 1M pixels takes 1s, then processing one with 10M pixels will take 10s if it’s O(n), or 100s if it’s O(n^2). That processing that 1M image takes 1s depends on many, many factors, but the O() notation has nothing to do with it. —— For example, for a small image an O(n^2) operation could be faster than a O(n) operation, depending on the all the other factors that make an implementation fast or slow. But as you grow the image, the slower O(n) algo might become faster. \$\endgroup\$ Commented Jun 4, 2023 at 19:49
  • 2
    \$\begingroup\$ @AlokMaity yes, but also on the algorithm itself, how much work is it doing per pixel? Something that takes 10s per pixel to compute could still be O(n). Time is 10s x n. Another algorithm takes 0.00001 s x n^2, is an O(n^2) algorithm. If you have n=1000, then the O(n) algorithm is 10,000s, whereas the other is 10s. 1000 times faster, even though it scales quadratically. \$\endgroup\$ Commented Jun 4, 2023 at 19:56

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.