Задача 04B. Hough Lines ≡

Входной файл:	Стандартный вход		Ограничение времени:	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). После построения аккумулятора должна проводиться его фильтрация согласно правилу â_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..

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

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

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

• image: двумерный массив булевых значений
• rho: разрешающая способность аккумулятора по расстоянию
• theta: разрешающая способность аккумулятора по углу
• threshold: возвращает прямые, для которых количество голосов больше `threshold`
• min_theta: минимальный рассматриваемый угол
• max_theta: максимальный рассматриваемый угол

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

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

Ограничения

Гарантируется, что 0 ⩽ min_theta ⩽ max_theta ⩽ π.

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

№	Стандартный вход	Стандартный выход
1	lines.jpg image = cv2.Canny(cv2.imread('lines.jpg'), 500, 550).astype(bool) print(*(f'{i} {j:.3f} {k}' for i, j, k in hough_lines(image, 1, np.pi / 360, 210)), sep='\n')	450 0.314 636 460 0.314 580 216 0.785 580 -908 2.635 429 522 2.094 420 933 1.370 393 944 1.370 373 532 2.094 369 590 2.199 328 227 0.785 305 -897 2.635 288 -115 2.915 286 1464 0.646 283 57 1.815 281 582 2.199 279 65 1.815 271 373 1.274 265 55 1.815 263 381 1.274 259 63 1.815 258 -106 2.915 255 -833 2.801 225 -826 2.793 218 -824 2.801 218 -817 2.793 217 1475 0.646 212

---