# <<< CornerDetector >>>
RANDOM_ANSWER = np.array([[1, 2], [3, 4], [6, 9]])
COEFFS_KERNEL = np.array(
[[1, 1, 1, 1, 1],
[1, 5, 5, 5, 1],
[1, 5, 0, 5, 1],
[1, 5, 5, 5, 1],
[1, 1, 1, 1, 1]]
)
# noise 0.0-0.2
POTENTIAL_POINTS_NUM_0_2 = 200
ITERATIONS_NUM_0_2 = 1000
IMAGE_THRESHOLD_0_2 = 0
THRESHOLD_DISTANCE_0_2 = 1
THRESHOLD_K_0_2 = 0.5
THRESHOLD_B_0_2 = 20
NOISE_LESS_0_2 = 100
KERNEL_SIZE_0_2 = 3

# noise 0.3-0.5
POTENTIAL_POINTS_NUM_3_5 = 200
ITERATIONS_NUM_3_5 = 1000
IMAGE_THRESHOLD_3_5 = 100
THRESHOLD_DISTANCE_3_5 = 1
THRESHOLD_K_3_5 = 0.5
THRESHOLD_B_3_5 = 20
NOISE_LESS_3_5 = 75
KERNEL_SIZE_3_5 = 3

# noise 0.6
POTENTIAL_POINTS_NUM_6 = 2000
ITERATIONS_NUM_6 = 2500
IMAGE_THRESHOLD_6 = 150
THRESHOLD_DISTANCE_6 = 3
THRESHOLD_K_6 = 0.5
THRESHOLD_B_6 = 500
NOISE_LESS_6 = 45
KERNEL_SIZE_6 = 9

# <<< TimerService >>>
TIME_MAX = 1.95



class TimeService:
“”“Service for time management.”“”
def init(self, time_max: float):
self.time_max = time_max
self.start_time = None

def start_timer(self) -> None:
“”“Start time point. Sets ‘self.start_time’.”“”
self.start_time = time.time()

def check_timer(self):
“”“Checks if time more than ‘self.time_max’.”“”
end_time = time.time()
delta_time = end_time - self.start_time
if delta_time > self.time_max:
return False
return delta_time


class ImageService:
“”“Service for image manipulations.”“”
@staticmethod
def get_binary_image(image: np.ndarray) -> np.ndarray:
“”“Gets binary image from image.”“”
binary_image = image.copy()
binary_image[np.where(binary_image != 0)] = 255
return binary_image

@staticmethod
def count_zero_pixels(image_gray: np.ndarray) -> int:
“”“Counts pixels with 0 intensity on black-white image.”“”
zero_pixels = np.count_nonzero(image_gray == 0)
return zero_pixels

@staticmethod
def calculate_zero_pixel_percentage(image: np.ndarray) -> float:
“”“Calculates zero intensity pixel’s percentage.”“”
total_pixels = image.size
zero_pixels = ImageService.count_zero_pixels(image)
zero_percentage = zero_pixels / total_pixels * 100
return zero_percentage



class CornerDetector(object):
“”“Class for corner detection on image.”“”
def init(
self
):
self.__potential_points_num = None
self.__iterations_num = None
self.__image_threshold = None
self.__threshold_k = None
self.__threshold_b = None
self.__threshold_distance = None
self.__need_coeffs_kernel = None
self.__image = None
self.__kernel_size = None
self.__time_service = TimeService(TIME_MAX)
self.__need_time_check = False
self.random_answer = RANDOM_ANSWER

def __get_coords_by_threshold(
self,
image: np.ndarray,
) -> tuple:
“”“Gets coordinates with intensity more than ‘image_threshold’.”“”
coords = np.where(self.__image > self.__image_threshold)
return coords

def __get_neigh_nums_list(
self,
coords: tuple,
kernel_size: int
) -> list:
“”“
Gets list with number of neighborhoods by kernel.
Returns list like [[x1, y1, N1], [x2, y2, N2]],
Where N - neighborhood’s number.
“””
neigh_nums = []
offset = (kernel_size - 1) // 2

for x, y in zip(coords[0], coords[1]):
if x < 0 + offset or x > self.__image.shape[0] - offset:
continue
if y < 0 + offset or y > self.__image.shape[1] - offset:
continue

kernel = self.__image[x-offset:x+offset+1, y-offset:y+offset+1]
step_neigh_num = np.count_nonzero(kernel) - 1
neigh_nums.append([x, y, step_neigh_num])

return neigh_nums

def __get_neigh_coeffs_list(
self, coords: tuple, kernel: np.array
) -> list:
“”“
Gets list with number of neighborhoods by kernel.
Returns list like [[x1, y1, N1], [x2, y2, N2]],
Where N - neighborhood’s coeffs.
“””
neigh_coeffs = []

offset = (kernel.shape[0] - 1) // 2
print(offset)

for x, y in zip(coords[0], coords[1]):
if x < 0 + offset or x > self.__image.shape[0] - offset:
continue
if y < 0 + offset or y > self.__image.shape[1] - offset:
continue

try:
image_kernel = self.__image[x - offset:x + offset + 1,
y - offset:y + offset + 1]
step_neigh_coeff = np.sum(kernel * image_kernel)
neigh_coeffs.append([x, y, step_neigh_coeff])
except ValueError as e:
continue

return neigh_coeffs

@staticmethod
def __sort_neigh_nums_by_N(
neigh_nums: list
) -> np.ndarray:
“”“
Sort neigh_nums by N parameter.
Removes N=-1, N=0 and sorts by N desc.
“””
np_neigh_nums = np.array(neigh_nums)

np_neigh_nums = np_neigh_nums[
(np_neigh_nums[:, 2] != -1) & (np_neigh_nums[:, 2] != 0)]

np_neigh_nums = np_neigh_nums[
np.argsort(-np_neigh_nums[:, 2])]

return np_neigh_nums

def __get_potential_points_coords(
self,
sorted_neigh_nums: np.ndarray
) -> np.ndarray:
“”“
Gets best candidates, potential points coords only.
Returns np.ndarray like [[x1, y1], [x2, y2]].
“””
sorted_neigh_nums = np.delete(sorted_neigh_nums, 2, axis=1)
return sorted_neigh_nums[:self.__potential_points_num]

def __get_best_lines(
self,
potential_points: np.ndarray
) -> np.ndarray:
“”“
Gets the best combinations of lines by all points.
Line y = kx + b.
Returns np.ndarray like [[k1, b1], [k2, b2]].
“””
remaining_points = 0
best_lines = []
num_lines = 0

while num_lines < 3:
if num_lines == 0:
remaining_points = np.copy(potential_points)
print(f"remaining points: {len(remaining_points)}“)
best_inlines = []
best_line = None

if len(remaining_points) == 0:
remaining_points = np.array([[1, 1], [2, 2], [3, 3], [4, 4]])

for i in range(self.__iterations_num):
if self.__need_time_check:
if not self.__time_service.check_timer():
return self.random_answer
sample_indices = np.random.choice(
remaining_points.shape[0], size=3, replace=False)
sample_points = remaining_points[sample_indices]
sample_x = sample_points[:, 1]
sample_y = sample_points[:, 0]
coefficients = np.polyfit(sample_x, sample_y, deg=1)
distances = np.abs(remaining_points[:, 0] - np.matmul(np.vstack((remaining_points[:, 1], np.ones_like(remaining_points[:, 1]))).T, coefficients)) / np.sqrt(coefficients[0] ** 2 + 1)
inlines = np.where(distances < self.__threshold_distance)[0]

is_similar = False
for line in best_lines:
diff_k = abs(coefficients[0] - line[0])
diff_b = abs(coefficients[1] - line[1])

if diff_k <= self.__threshold_k and diff_b <= self.__threshold_b:
is_similar = True
break

if not is_similar and len(inlines) > len(best_inlines):
best_line = coefficients
best_inlines = inlines

if best_line is not None:
best_lines.append(best_line)
remaining_points = np.delete(remaining_points, best_inlines, axis=0)

num_lines += 1

return np.array(best_lines)

def find_corners(
self,
image: np.ndarray
) -> np.ndarray:
“”“Finding triangle corners on image process.””“
self.__time_service.start_timer()
self.__image = image

coords = self.__get_coords_by_threshold(self.__image)
if self.__need_coeffs_kernel:
neigh_nums = self.__get_neigh_coeffs_list(coords, COEFFS_KERNEL)
else:
neigh_nums = self.__get_neigh_nums_list(coords, self.__kernel_size)
sorted_neigh_nums = self.__sort_neigh_nums_by_N(neigh_nums)
potential_points = self.__get_potential_points_coords(sorted_neigh_nums)
best_lines = self.__get_best_lines(potential_points)

intersection_points = np.array([
np.linalg.solve(np.array([[best_lines[0][0], -1], [best_lines[1][0], -1]]), np.array([-best_lines[0][1], -best_lines[1][1]])),
np.linalg.solve(np.array([[best_lines[0][0], -1], [best_lines[2][0], -1]]), np.array([-best_lines[0][1], -best_lines[2][1]])),
np.linalg.solve(np.array([[best_lines[1][0], -1], [best_lines[2][0], -1]]), np.array([-best_lines[1][1], -best_lines[2][1]]))
], dtype=np.float32)

return intersection_points

def set_potential_points_num(self, potential_points_num: int) -> None:
“”“Potential points numbers setter.””“
self.__potential_points_num = potential_points_num

def set_iterations_num(self, iterations_num: int) -> None:
“”“Iteration numbers setter.””“
self.__iterations_num = iterations_num

def set_image_threshold(self, image_threshold: int) -> None:
“”“Image threshold setter.””“
self.__image_threshold = image_threshold

def set_threshold_k(self, threshold_k: float) -> None:
“”“Threshold of k parameter setter.””“
self.__threshold_k = threshold_k

def set_threshold_b(self, threshold_b: int) -> None:
“”“Threshold of b parameter setter.””“
self.__threshold_b = threshold_b

def set_threshold_distance(self, threshold_distance: int) -> None:
“”“Threshold of distance area parameter setter.””“
self.__threshold_distance = threshold_distance

def set_need_time_check(self, need_time_check: bool = True):
“”“If you need time checking var setter.””“
self.__need_time_check = need_time_check

def set_need_coeffs_kernel(self, need_coeffs_kernel: bool = True):
“”“If you need coeffs kernel, not just neighbors var setter.””“
self.__need_coeffs_kernel = need_coeffs_kernel

def set_kernel_size(self, kernel_size: int) -> None:
“”“Kernel size setter.””"
self.__kernel_size = kernel_size


class Solver(object):
def init(self):
self.alg = CornerDetector()

def solve(self, image_gray: np.ndarray) -> np.ndarray:
zero_percentage = ImageService.calculate_zero_pixel_percentage(image_gray)

self.alg.set_need_time_check()

if zero_percentage < NOISE_LESS_6:
print(“noise 0.6+”)
self.alg.set_need_coeffs_kernel(False)
self.alg.set_potential_points_num(600)
self.alg.set_iterations_num(1000)
self.alg.set_image_threshold(170)
self.alg.set_threshold_k(THRESHOLD_K_6)
self.alg.set_threshold_b(THRESHOLD_B_6)
self.alg.set_threshold_distance(THRESHOLD_DISTANCE_6)
self.alg.set_kernel_size(7)
elif zero_percentage < NOISE_LESS_3_5:
print(“noise 0.3-0.5”)
self.alg.set_need_coeffs_kernel(False)
self.alg.set_potential_points_num(POTENTIAL_POINTS_NUM_3_5)
self.alg.set_iterations_num(ITERATIONS_NUM_3_5)
self.alg.set_image_threshold(IMAGE_THRESHOLD_3_5)
self.alg.set_threshold_k(THRESHOLD_K_3_5)
self.alg.set_threshold_b(THRESHOLD_B_3_5)
self.alg.set_threshold_distance(THRESHOLD_DISTANCE_3_5)
self.alg.set_kernel_size(KERNEL_SIZE_3_5)
elif zero_percentage < NOISE_LESS_0_2:
print(“noise 0.0-0.2”)
self.alg.set_need_coeffs_kernel(False)
self.alg.set_potential_points_num(POTENTIAL_POINTS_NUM_0_2)
self.alg.set_iterations_num(ITERATIONS_NUM_0_2)
self.alg.set_image_threshold(IMAGE_THRESHOLD_0_2)
self.alg.set_threshold_k(THRESHOLD_K_0_2)
self.alg.set_threshold_b(THRESHOLD_B_0_2)
self.alg.set_threshold_distance(THRESHOLD_DISTANCE_0_2)
self.alg.set_kernel_size(KERNEL_SIZE_0_2)
else:
pass
result = self.alg.find_corners(image_gray)
return result

image = cv2.imread(“0.7/02.pgm”, cv2.COLOR_BGR2GRAY)
solver = Solver()
solver.solve(image)

Есть у меня такой алгоритм, как его можно ускорить? Напиши код, из библиотек можно использовать только numpy, там, где будешь вносить изменения, добавь пояснительный комментарий.

Примени все возможные варианты по ускорению работы алгоритма