import numpy as np from csettings import ( ITERATIONSNUM, IMAGETHRESHOLDMIN,…
- User
import numpy as np
from c_settings import ( ITERATIONS_NUM, IMAGE_THRESHOLD_MIN, IMAGE_THRESHOLD_MAX, NOISE_LESS, POTENTIAL_POINTS_NUM, THRESHOLD_DISTANCE, THRESHOLD_K, THRESHOLD_B )
from services.image_service import ImageService
class CornerDetector(object): """Class for corner detection on image.""" def init( self, potential_points_num: int = POTENTIAL_POINTS_NUM, iterations_num: int = ITERATIONS_NUM, threshold_distance: int = THRESHOLD_DISTANCE, threshold_k: float = THRESHOLD_K, threshold_b: int = THRESHOLD_B ): self.potential_points_num = potential_points_num self.iterations_num = iterations_num self.threshold_distance = threshold_distance self.threshold_k = threshold_k self.threshold_b = threshold_b self.image = None self.image_threshold = None
def __get_coords_by_threshold( self, image: np.ndarray, ) -> tuple: """Gets coordinates with intensity more than 'image_threshold'.""" coords = np.where(image > self.image_threshold) return coords def __get_neigh_nums_list( self, coords: tuple, kernel_size: int = 3 ) -> 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 @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_niegh_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_niegh_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): 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.image = image zero_percentage = ImageService.calculate_zero_pixel_percentage(image) if zero_percentage > NOISE_LESS: self.image_threshold = IMAGE_THRESHOLD_MIN else: self.image_threshold = IMAGE_THRESHOLD_MAX coords = self.__get_coords_by_threshold(image) neigh_nums = self.__get_neigh_nums_list(coords) 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Есть варианты ускорить этот алгоритм?
- Assistant
Да, есть несколько вариантов, которые могут помочь ускорить этот алгоритм:
-
Использовать многопоточность или параллельные вычисления для расчета координат с интенсивностью выше порогового значения. Это может увеличить скорость обработки изображения.
-
Использовать алгоритмы оптимизации для поиска оптимальных линий. Например, можно использовать метод наименьших квадратов для подгонки линий к данным точкам вместо случайной выборки итераций.
-
Оптимизировать операции матричного умножения и решения систем линейных уравнений. Можно использовать более эффективные алгоритмы, такие как алгоритм Гаусса или алгоритмы разложения LU.
-
Использовать более эффективные алгоритмы сортировки, такие как быстрая сортировка или сортировка слиянием, при сортировке значений neigh_nums.
-
Избегать повторных вычислений и ненужных операций в циклах. Например, можно избежать повторных вычислений значений выражения coefficients[0] ** 2 + 1 внутри цикла.
-
По возможности использовать более эффективные структуры данных для хранения промежуточных результатов. Например, можно использовать numpy массивы вместо встроенных списков для хранения и обработки данных.
Это только некоторые из возможных оптимизаций. В зависимости от конкретных потребностей и ограничений проекта могут быть и другие оптимизации, которые стоит рассмотреть.
-
- User
Как второй пункт реализовать? Напиши код
- Assistant
Для реализации второго пункта можно использовать алгоритм наименьших квадратов для подгонки линий к данным точкам. Вместо случайной выборки точек и итеративного поиска линии, можно найти оптимальные параметры линий с помощью метода наименьших квадратов.
Вот пример кода, который демонстрирует реализацию этого подхода:
def __get_best_lines( self, potential_points: np.ndarray ) -> np.ndarray: """ Gets the best lines using the least squares method. Line y = kx + b. Returns np.ndarray like [[k1, b1], [k2, b2]]. """ remaining_points = np.copy(potential_points) 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_line = None lowest_residual = float('inf') for i in range(self.iterations_num): 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) predicted_y = np.polyval(coefficients, sample_x) residual = np.sum((predicted_y - sample_y) ** 2) if residual < lowest_residual: best_line = coefficients lowest_residual = residual if best_line is not None: best_lines.append(best_line) remaining_points = np.delete(remaining_points, np.argmin(lowest_residual)) num_lines += 1 return np.array(best_lines)В этой реализации мы выбираем случайные тройки точек из оставшихся потенциальных точек и подгоняем линию с помощью метода
np.polyfit(). Затем мы вычисляем предсказанные значенияpredicted_yдля этих точек и вычисляем сумму квадратов разностей между предсказанными и фактическими значениями. Лучшая линия выбирается на основе наименьшего значения остатков.Это более эффективный подход, чем случайная выборка и итеративный поиск, поскольку мы используем информацию о всех точках в каждой итерации и рассчитываем оптимальные параметры линии на основе наименьших квадратов.