Processing math: 100%

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

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

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

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

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

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

Ограничения

Гарантируется, что 0min_thetamax_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.051s 0.005s 17