Задача 4C. Hough Circles ≡

Входной файл:	Стандартный вход		Ограничение времени:	3 сек
Выходной файл:	Стандартный выход		Ограничение памяти:	512 Мб
Максимальный балл:	3000

Условие

Требуется реализовать на языке Python функцию, выполняющую преобразование Хаффа для поиска окружностей. Функция должна иметь следующий интерфейс

import numpy as np
from typing import List, Tuple

def hough_circles(
    image: np.ndarray,
    accumulator_resolution: float,
    min_distance: int,
    canny_threshold: int,
    center_threshold: int,
    radius_threshold: int,
    min_radius: int,
    max_radius: int) -> List[Tuple[float, float, float, int]]:
    """Finds circles in a gray image using Hough transform
    
    Arguments:
        image: 2d np.ndarray of float
        accumulator_resolution: step size for accumulators
        min_distance: minial distance between circle centers
        canny_threshold: upper threshold for Canny edge detector
        center_threshold: minimal number of votes for a center to be accepted
        radius_threshold: minimal number of votes for a radius to be accepted
        min_radius: minimal circle radius
        max_radius: maximal circle radius
        
    Returns:
        circles: a list of tuples (x, y, radius, votes), detected circles sorted by votes in descending order
    """
    pass

При построении аккумуляторов, голос отдаётся за индекс, округлённый к ближайшему целому (rounding half to even).

После построения аккумулятора для центров окружностей должна проводиться его фильтрация согласно правилу â_i,j = {a_i,j,a_{i − 1,j} < a_i,j,a_{i,j − 1} < a_i,j,a_i + 1,j ⩽ a_i,j,a_i,j + 1 ⩽ a_i,j0,else..

При выборе радиуса окружности лучшим считается такой радиус r с количеством голосов c, для которого частное cr является максимальным.

При решении задачи запрещено использовать любые готовые реализации алгоритма.

Формат входных данных

Аргументы функции:

• image: двумерный массив чисел с плавающей точкой, чёрно-белое изображение
• accumulator_resolution: разрешающая способность аккумуляторов
• min_distance: минимально допустимое расстояние между центрами окружностей
• canny_threshold: верхний порог алгоритма Кэнни, нижний порог считать равным canny_threshold / 2
• center_threshold: минимальное количество голосов для принятия центра
• radius_threshold: минимальное количество голосов для принятия радиуса
• min_radius: минимально допустимый радиус окружности
• max_radius: максимально допустимый радиус окружности

Формат выходных данных

Функция возвращает список четвёрок (x, y, радиус, количество голосов) для каждой окружности в порядке убывания по количеству голосов.

Примеры тестов

№	Стандартный вход	Стандартный выход
1	circles.png image = cv2.cvtColor(cv2.imread('circles.png'), cv2.COLOR_BGR2GRAY) print(*(f'{x} {y} {r} {c}' for x, y, r, c in hough_circles(image, 1, 50, 250, 50, 50, 50, 250)), sep='\n')	301 217 203 143 216 163 100 139 384 273 101 138 352 135 101 131 246 305 100 126

---