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

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

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

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

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

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

Ограничения

Гарантируется, что 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

0.133s 0.012s 17