Задача 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).

После построения аккумулятора для центров окружностей должна проводиться его фильтрация согласно правилу ˆai,j={ai,j,ai1,j<ai,j,ai,j1<ai,j,ai+1,jai,j,ai,j+1ai,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.044s 0.007s 17