Задача 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 = {ai,j,ai − 1,jai,j,ai,j − 1ai,j,ai + 1,j⩽ ai,j,ai,j + 1⩽ ai,j0,else..

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

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

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

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

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

Функция возвращает список четвёрок (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

0.088s 0.011s 17