Skip to content
TheChatArchiveThe Chat Archive
gpt-3.5-turbo-0613· openaiHugging Face Suzhen/CodeChat

import numpy as np from csettings import ( ITERATIONSNUM, IMAGETHRESHOLDMIN,…

  1. 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
    

    Есть варианты ускорить этот алгоритм?

  2. Assistant

    Да, есть несколько вариантов, которые могут помочь ускорить этот алгоритм:

    1. Использовать многопоточность или параллельные вычисления для расчета координат с интенсивностью выше порогового значения. Это может увеличить скорость обработки изображения.

    2. Использовать алгоритмы оптимизации для поиска оптимальных линий. Например, можно использовать метод наименьших квадратов для подгонки линий к данным точкам вместо случайной выборки итераций.

    3. Оптимизировать операции матричного умножения и решения систем линейных уравнений. Можно использовать более эффективные алгоритмы, такие как алгоритм Гаусса или алгоритмы разложения LU.

    4. Использовать более эффективные алгоритмы сортировки, такие как быстрая сортировка или сортировка слиянием, при сортировке значений neigh_nums.

    5. Избегать повторных вычислений и ненужных операций в циклах. Например, можно избежать повторных вычислений значений выражения coefficients[0] ** 2 + 1 внутри цикла.

    6. По возможности использовать более эффективные структуры данных для хранения промежуточных результатов. Например, можно использовать numpy массивы вместо встроенных списков для хранения и обработки данных.

    Это только некоторые из возможных оптимизаций. В зависимости от конкретных потребностей и ограничений проекта могут быть и другие оптимизации, которые стоит рассмотреть.

  3. User

    Как второй пункт реализовать? Напиши код

  4. 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 для этих точек и вычисляем сумму квадратов разностей между предсказанными и фактическими значениями. Лучшая линия выбирается на основе наименьшего значения остатков.

    Это более эффективный подход, чем случайная выборка и итеративный поиск, поскольку мы используем информацию о всех точках в каждой итерации и рассчитываем оптимальные параметры линии на основе наименьших квадратов.