5.26. Пошук ліній і відрізків

Деякі ознаки сцени — це не зв’язані кольорові ділянки, а орієнтовані прямі межі: намальована лінія на підлозі, шов між двома поверхнями, бік друкованого прямокутника, край дверного отвору. Просити детектор плям знайти їх — неправильна постановка завдання: межа завтовшки в один піксель, алгоритм плям очікує площу з кольором, і відповідь буде порожньою або зашумленою.

Правильним детектором для орієнтованих країв є перетворення Хафа для ліній. Модуль зображень надає його в двох варіантах: find_lines() повертає нескінченні лінії (кожна лінія простягається через весь кадр); find_line_segments() повертає скінченні відрізки (кожен відрізок має кінцеві точки всередині кадру). Який варіант потрібен програмі, залежить від того, чи проходять цікаві краї безперервно через весь кадр, чи лише через його частину.

5.26.1. Як працює перетворення Хафа

Обидва детектори використовують одну й ту саму основну ідею, тому варто зрозуміти її один раз. Модуль зображень спочатку запускає фільтр меж у стилі Собеля на вхідних даних, щоб оцінити кожен піксель за ймовірністю того, що він лежить на орієнтованому краї. Кожен такий піксель краю потім голосує за всі лінії, на яких він може лежати. Перемагають лінії, що зібрали найбільше голосів.

Лінія параметризується в просторі Хафа двома числами: theta — кут лінії (від 0 до 179 градусів), і rho — перпендикулярна відстань від початку координат зображення до лінії (зі знаком, у пікселях). Кожна лінія, що є у зображенні, відповідає одній точці в просторі (theta, rho). Кожен піксель межі у вхідному зображенні додає один голос до кожної комбінації (theta, rho), сумісної з його позицією — концептуально це крива в просторі Хафа. Де перетинається багато таких кривих, багато пікселів меж погоджуються з однією лінією, і це перетин є виявленням.

Детектор повертає локальні максимуми простору Хафа, чиї суми голосів перевищують поріг. Кожна повернута Line містить обидва представлення: x1, y1, x2, y2 для форми з кінцевими точками (обрізаними до меж зображення у нескінченному випадку), theta, rho для форми Хафа, а також length і magnitude для розміру та кількості голосів відповідно.

5.26.2. Нескінченні лінії

find_lines() виконує перетворення Хафа і повертає найсильніші лінії, кожна з яких простягається через весь кадр:

lines = img.find_lines(threshold=1500, theta_margin=25, rho_margin=25)

for l in lines:
    img.draw_line(l, color=(255, 0, 0))

threshold — це мінімальна сума голосів для прийняття лінії. Сума голосів складається з магнітуд меж Собеля кожного піксель, що бере участь, тому більші значення threshold вимагають довших або сильніших меж для проходження — а це означає, що правильне значення залежить від роздільної здатності зображення (довша лінія при вищій роздільній здатності набирає більше голосів) і від сцени, тому його треба налаштовувати для конкретного застосунку. Як приблизні відправні точки для налаштування: 1000 для скромної лінії на чистому зображенні, 500 або менше для слабкого контрасту або коротких ліній, 2000 або більше для насичених сцен, де хибні лінії утворюються через кластери шуму меж.

theta_margin і rho_margin контролюють об’єднання сусідніх максимумів. Одна фізична межа створює невеликий кластер бінів з великою кількістю голосів навколо свого справжнього (theta, rho), і детектор стягує кожен кластер до його піку перед поверненням результату. theta_margin=25 (градуси) об’єднує будь-які піки в межах 25 градусів орієнтації; rho_margin=25 (пікселі) об’єднує піки в межах 25 пікселів відстані. Значення за замовчуванням є розумними; збільшення повертає менше, але більш виразних ліній, а зменшення повертає більше, іноді дублікатних ліній.

x_stride і y_stride задають крок перебору пікселів меж під час голосування — так само, як вони задають крок перебору пікселів у find_blobs(). Значення за замовчуванням 2 і 1 підходять для загального випадку; їх збільшення прискорює пошук за рахунок роздільної здатності. roi обмежує пошук певною областю кадру, що і звужує повернуті лінії, і зменшує обсяг роботи.

Кожна повернута лінія відразу доступна для малювання: об’єкт Line передається безпосередньо до draw_line(), який зчитує поля кінцевих точок (x1, y1, x2, y2) з його початку. l.theta — кут у градусах, що дозволяє класифікувати лінію як горизонтальну, вертикальну або діагональну одним порівнянням. l.magnitude — загальна кількість голосів, за якою повернуті лінії сортуються від найсильнішої до найслабшої.

5.26.3. Відрізки

find_lines() — правильний детектор для меж, що проходять через весь кадр, але багато реальних меж — ліва сторона друкованого штрих-коду, верхній край наклейки, видима сторона лінійки — проходять лише через частину зображення. find_line_segments() повертає скінченні відрізки, чиї кінцеві точки знаходяться всередині кадру:

segments = img.find_line_segments(merge_distance=5, max_theta_difference=10)

for s in segments:
    img.draw_line(s, color=(0, 255, 0))

Детектор відрізків відслідковує орієнтовані пікселі меж безпосередньо, не голосуючи в просторі Хафа, і результатом є набір коротких прямих ділянок. merge_distance задає максимальний розрив у пікселях, який дві колінеарні короткі ділянки можуть мати і все одно об’єднатися в один повернутий відрізок; max_theta_difference задає, скільки градусів різниці орієнтації терпить об’єднання між сусідніми ділянками. Щедре об’єднання (merge_distance=10, max_theta_difference=15) повертає невелику кількість довгих відрізків ціною іноді з’єднання по-справжньому окремих меж; строге об’єднання (merge_distance=0, max_theta_difference=5) повертає багато коротких відрізків і залишає їх сортування застосунку на Python.

Об’єкти результатів мають той самий тип Line, що й find_lines(), з тими самими властивостями, тому конвеєр може обробляти будь-який тип виявлення через один і той самий downstream код. Єдина практична відмінність полягає в тому, що кінцеві точки відрізків — це справжні кінці лінії у зображенні, тоді як кінцеві точки нескінченних ліній — це місця перетину лінії з межею зображення.

5.26.4. Коли використовувати кожен варіант

Вибір між двома методами зводиться до одного запитання: чи важливо застосунку, де зупиняється лінія?

find_lines() — правильний інструмент, коли відповідь — ні. Роботу, що слідує по лінії, потрібно знати у якому напрямку іде лінія та де вона перетинає нижній край кадру; сама лінія тягнеться до горизонту і далі. Детектор горизонту шукає найсильнішу орієнтовану межу у зображенні; йому не потрібно знати, де горизонт закінчується.

find_line_segments() — правильний інструмент, коли відповідь — так. Ідентифікація чотирьох сторін друкованого прямокутника потребує чотирьох відрізків з відомими кінцевими точками. Відстеження пальця, що вказує на дисплей, означає відстеження короткого відрізка, кінцеві точки якого є кінчиком і основою пальця. Вимірювання довжини видимого подряпання потребує фактичного протяжності відрізка у пікселях.

Обидва детектори мають спільне обмеження: вони потребують контрасту. Фільтр меж Собеля, на якому вони базуються, реагує на градієнти яскравості; кольорова межа на рівному за яскравістю тлі (червона лінія на зеленій стіні тієї ж світлоти) не дає градієнту і не виявляється. Коли такий випадок трапляється на практиці, виправлення полягає у витяганні одного каналу LAB як зображення у відтінках сірого з правильним контрастом перед пошуком: to_grayscale() з вибраним каналом b виділяє червоний на зеленому там, де канал яскравості є плоским, — і це зображення каналу передається детектору ліній.