Входной файл: | Стандартный вход | Ограничение времени: | 4 сек | |
Выходной файл: | Стандартный выход | Ограничение памяти: | 1024 Мб | |
Максимальный балл: | 3000 |
Требуется реализовать на языке Python функцию, выполняющую классическое преобразование Хаффа для поиска прямых. Функция должна иметь следующий интерфейс
import numpy as np
from typing import List, Tuple
def hough_lines(
image: np.ndarray,
rho: float,
theta: float,
threshold: int,
min_theta: float = 0,
max_theta: float = np.pi) -> list[tuple[float, float, int]]:
"""Finds lines in a binary image using the standard Hough transform.
Arguments:
image: 2d np.ndarray of bool
rho: distance resolution
theta: angle resolution
theshold: only lines with votes > `threshold` are returned
min_theta: minimal angle value
max_theta: maximal angle value
Returns:
lines: a list of tuples (distance, angle, votes), detected lines sorted by votes in descending order
"""
pass
При реализации функции сетка по расстоянию должна строиться на интервале [−(w+h),w+h+rho). При построении аккумулятора голос отдаётся за расстояние, округлённое к ближайшему индексу (round 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.
При решении задачи запрещено использовать любые готовые реализации алгоритма.
Аргументы функции:
Функция возвращает список троек (расстояние, угол, количество голосов) для каждой прямой в порядке убывания по количеству голосов.
№ | Стандартный вход | Стандартный выход |
---|---|---|
1 |
lines.jpg
|
|