Входной файл: | Стандартный вход | Ограничение времени: | 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,ai−1,j<ai,j,ai,j−1<ai,j,ai+1,j⩽ai,j,ai,j+1⩽ai,j0,else.
При выборе радиуса окружности лучшим считается такой радиус r с количеством голосов c, для которого частное cr является максимальным.
При решении задачи запрещено использовать любые готовые реализации алгоритма.
Аргументы функции:
Функция возвращает список четвёрок (x, y, радиус, количество голосов) для каждой окружности в порядке убывания по количеству голосов.
№ | Стандартный вход | Стандартный выход |
---|---|---|
1 |
circles.png
|
|