Как на картинке найти линию

Обнаружение прямых линий на изображении

Время прочтения: 4 мин.

Способность распознавать прямые линии важна как в человеческом, так и в компьютерном зрении. Человек может легко распознать многие типы объектов и их положения, просто увидев силуэт или грубый набросок. Обучить систему тому же – задача распознавания изображений. И определение прямых линий – важная часть этой задачи. Способов решения таких задач много. В этой статье я расскажу о преобразовании линии Хафа. Как это работает?

Прямую в пространстве изображения можно выразить двумя переменными. Например:

• В декартовой системе координат: Параметры: (m, b).
• В полярной системе координат: Параметры: (r, θ)

Для преобразований Хафа мы выразим линии в полярной системе. Следовательно, линейное уравнение можно записать как:

В общем, для каждой точки (x₀, y₀) мы можем определить семейство линий, проходящих через эту точку, как:

Это означает, что каждая пара (r_θ, θ) представляет каждую линию, проходящую через (x₀, y₀).

Если для заданного (x₀, y₀) мы построим семейство линий, которые проходят через него, мы получим синусоиду. Например, для x₀ = 8 и y₀ = 6 получаем следующий график (в плоскости θ — r):

Мы рассматриваем только такие точки, что r> 0 и 0 <θ <2π.

Мы можем проделать ту же операцию для всех точек изображения. Если кривые двух разных точек пересекаются в плоскости θ — r, это означает, что обе точки принадлежат одной прямой. Например, следуя приведенному выше примеру и рисуя график еще для двух точек: x₁ = 4, y₁ = 9 и x₂ = 1₂, y₂ = 3, мы получаем:

Три графика пересекаются в одной точке (0.925, 9.6), эти координаты являются параметрами (θ, r) или линией, в которой лежат (x₀, y₀), (x₁, y₁) и (x₂, y₂).

Что означает все вышеперечисленное? Это означает, что в целом линию можно обнаружить, определив количество пересечений между кривыми. Чем больше пересекающихся кривых, тем больше точек на линии, представленной этим пересечением. В общем, мы можем определить порог минимального количества пересечений, необходимых для обнаружения линии.

Это то, что делает метод преобразования линии Хафа. Он отслеживает пересечение кривых каждой точки изображения. Если количество пересечений превышает некоторый порог, то он объявляет это как линию с параметрами (θ, r_θ) точки пересечения.

В библиотеке OpenCV существует два типа нужного нам алгоритма, а именно стандартное преобразование линии Хафа и вероятностное преобразование линии Хафа. Стандартный даст нам уравнение линии, поэтому мы не знаем начало и конец линии. В то время как вероятностное линейное преобразование даст список строк, в котором строка является списком начальной и конечной координаты. Для примера применения данного алгоритма возьмём задачу распознавания границ ячеек в таблице. Для такой задачи вероятностный вариант предпочтительнее. Так же разделим горизонтальные и вертикальные линии.

canny = cv.Canny(img, 50, 150)
cImg = np.copy(img)

houghLines = cv.HoughlinP(canny, 1, 1*np.pi/180, 40 , 250 , None, 250, 6 )

lin_horiz = []
lin_vert = []

if houghLines is not None:
  for i in range(0, len(houghLines))
    lin = houghLines[i][0]
    if (lin[0]==lin[2]):
      lin_vert.append(l)
    elif (lin[1]==lin[3]):
      lin_horiz.append(l)
for i, lin in enumerate(lin_horiz):
cv.lin(cIm, (lin[0], lin[1]), (lin[2], lin[3]), (0,255,0), 3, cv.lin_AA)
for i, lin in enumerate(lin_vert):
cv.lin(cIm, (lin[0], lin[1]), (lin[2], lin[3]), (0,0,255), 3, cv.lin_AA)
cv.imshow("with_line", cIm)

Полученный список координат обнаруженных линий в дальнейшем может помочь распознать содержимое таблицы точнее, вырезая содержимое ячейки и распознавая его в отдельности от остального изображения.

Алгоритм Хафа для обнаружения произвольных кривых на изображениях

Преобразование Хафа — это метод обнаружения прямых и кривых линий на полутоновых или цветных изображениях. Метод позволяет указать параметры семейства кривых и обеспечивает поиск на изображении множества кривых заданного семейства. Мы рассмотрим его применение для поиска на изображении прямолинейных отрезков и дуг окружностей.

В алгоритме преобразования Хафа используется аккумуляторный массив, размерность которого соответствует количеству неизвестных параметров в уравнении семейства искомых кривых. Например, при обнаружении прямых, описываемых уравнением y=m*x+b, для каждой прямой необходимо вычислить значения двух параметров m и b. При этом в массиве в элементах A[M,B] накапливаются значения, указывающие на вероятность наличия на изображении прямой y=m*x+b, где M и B соответствуют дискретным значениям m и b.

Массив A используется в алгоритме Хаффа для проверки каждого пиксела изображения и его окрестности. Определяется присутствует ли в данном пикселе выраженный край. Если присутствует, то вычисляются параметры искомой кривой, проходящей через данный пиксел. После оценки параметров прямой в данном пикселе они дискретизируются для получения соответствующих значений M и B, и значение массива A[M,B] увеличивается. В некоторых реализациях увеличение выполняется на единицу, в других на величину мощности края в обработанном пикселе. После обработки всех пикселов выполняется поиск локальных максимумов в аккумуляторном массиве. Точки локальных максимумов соответствуют параметрам наиболее вероятных прямых на изображении.

Аккумуляторный массив позволяет определить параметры бесконечно протяжённых прямых или кривых, но с его помощью невозможно определить, где именно начинаются и заканчиваются отрезки этих линий. Для получения этой информации можно завести ещё одну структуру данных PTLIST. Элемент PTLIST[M,B] содержит список координат всех пикселов, которые внесли вклад в значение аккумуляторного массива A[M,B]. По содержанию этих списков можно найти присутствующие на изображении отрезки или сегменты кривых.

Сейчас мы рассмотрели общие принципы метода Хафа, но мы не рассмотрели некоторые важные детали, которые необходимо знать при программной реализации.

Уравнение прямой y=m*x+b не подходит для представления вертикальных прямых. Удобнее представлять прямые в виде d=x*cos(f)+y*sin(f), где d — это длина перпендикуляра к прямой, а f — угол между перпендикуляром и горизонтальной осью. В системе координат изображения оси направлены вдоль строк и столбцов изображения. Так координата c соответствует x, а координата r — координате (-y), то уравнение прямой принимает вид: d=c*cos(f)-r*sin(f).

Индексы аккумуляторного массива A соответствуют дискретным значениям d и f. В серии экспериментов 1976 О’Горман и Кловс дискретизировали значения d с шагом 3 и значения f с шагом 10. Ниже в виде процедуры accumulate_lines приведён алгоритм О’Гормана и Кловса для заполнения аккумуляторного массива A и массива списков PTLIST.

Алгоритм работает в двумерном координатном пространстве. Функция row_gradient и column_gradiet обрабатывают окрестности пикселов для оценки компонент градиента в направлении строк и столбцов. Функция gradient комбинирует комбинирует две эти компоненты для получения величины градиента. Функция atan2 возвращает по заданным компонентам градиента угол в соответствующем квадранте. Процедура accumulate_lines представляет собой версию преобразования Хафа. Оригинальный метод Хафа не предусматривает стандартного метода выделения отрезков прямых. Поэтому была разработана процедура find_lines. Функция pick_greatest_bin возвращает максимальное значение из аккумуляторного массива, присваивая параметрам DQ и THETAQ соответствующие дискретные значения d и f. Функция reader упорядочивает список точек в элементе массива по координате столбца при f<45 или f>135 и по координате строки при 45<=f<=135. Предполагается, что в массивах D и THETA для пикселов содержатся дискретные значения. Аналогично в массиве GRADIENT должны находиться вычисленные значения величины градиента. Процедура merge объединяет список точек соседнего пиксела со списком точек для данного пиксела. При этом сохраняется пространственное упорядочение точек. Процедура set_to_zero обнуляет элемент аккумуляторного массива, чтобы он не был найден повторно. Наконец, процедура create_segments просматривает окончательный упорядоченный список точек и ищет в нём промежутки длиннее одного пиксела. Важно понимать, что преобразование Хафа может обнаружить посторонние разрывные или фиктивные линии, например образованные тенью.

Для обнаружения окружностей нам придётся добавить в массив A ещё одно измерение, т.к. стандартное описание окружности содержит три параметра:
r=r0+d*sin(f)
c=c0-d*cos(f)
где d — радиус окружности, а r и c — вертикальная и горизонтальная координаты центра окружности.

На самом деле метод Хафа может использоваться для обнаружения любых кривых, описываемых аналитически. пусть кривая представлена в виде f(x,a)=0, где x — точка изображения, а a — вектор параметров. Процедура поиска подобных кривых состоит из трёх шагов:
1. Инициализация массива A нулевыми значениями.
2. Для каждого краевого пиксела x определяется вектор a, что f(x,a)=0 и выполняется увеличение значения соответствующего элемента массива A[a]:=A[a]+1.
3. Локальные максимумы в аккумуляторном массиве A соответствуют вероятным кривым f на изображении.

Если вектор a содержит m параметров и каждый из этих параметров принимает M дискретных значений, то временная сложность алгоритма составляет O(M^(m-2)).

На самом деле, существует множество методов выделения различных линий на изображениях. Если тема интересна, то я могу рассказать о них. Спасибо за внимание.

Обнаружение прямой линии изображения

Обнаружение прямых линий изображения, как следует из названия, заключается в обнаружении прямых линий или сегментов прямых линий на изображении.

Функции HoughLines и HoughLinesP в OpenCV могут выполнять обнаружение строк.

(1) Функция HoughLines: используется стандартное преобразование Хафа.

Прототип функции: HoughLines (изображение, линии, rho, theta, threshold, srn = 0, stn = 0, min_theta = 0, max_theta = CV_PI)

Описание параметра:

image: входное изображение, то есть исходное изображение, которое должно быть 8-битным одноканальным двоичным изображением. Вы можете загрузить любое исходное изображение и изменить его в этом формате с помощью функции, а затем заполнить его здесь.

lines: после вызова функции HoughLines сохраняется выходной вектор линий, обнаруженных преобразованием линии Hough. Каждая линия представлена ​​вектором с двумя элементами, где – расстояние от начала координат ((0,0) (то есть верхний левый угол изображения). Это угол поворота линии в радианах (0 ~ вертикальная линия, π / 2 ~ Горизонтальная линия).

rho: точность расстояния в пикселях. Другой способ описать это – единичный радиус прогрессивного размера при поиске по прямой. PS: / rho означает латекс.

theta: Точность угла в радианах. Другой способ описать это – единичный угол прогрессивного размера при поиске по прямой.

Порог: пороговый параметр плоскости накопления, то есть значение, которое должно быть достигнуто в плоскости накопления, когда определенная часть распознается как прямая линия на рисунке. Только сегмент линии, превышающий пороговое значение, может быть обнаружен, пройден и возвращен в результат.

srn: значение по умолчанию – 0. Для многомасштабного преобразования Хафа это третий параметр, увеличивающий расстояние делителя размера rho. Приблизительный размер опережения аккумулятора является третьим параметром rho, а точный размер опережения аккумулятора – rho / srn.

stn: значение по умолчанию – 0. Для многомасштабного преобразования Хафа srn представляет собой расстояние делителя тета единичного угла четвертого параметра. И если srn и stn оба равны 0, это означает, что используется классическое преобразование Хафа. В противном случае оба этих параметра должны быть положительными.

min_theta: для стандартного и многомасштабного преобразования Хафа проверьте минимальный угол линии. Должно быть от 0 до max_theta.

max_theta: для стандартного и многомасштабного преобразования Хафа проверьте максимальный угол линии. Должен быть между min_theta и CV_PI.

(2) Функция HoughLinesP: используйте вероятностное преобразование Хафа, то есть только путем анализа подмножества точек и оценки вероятности того, что эти точки принадлежат прямой линии, это быстрее по скорости вычислений.

Прототип функции: HoughLinesP (image, rho, theta, threshold, lines = None, minLineLength = None, maxLineGap = None)

Описание параметра:

изображение: должно быть двоичным изображением, рекомендуется изображение результата обнаружения хитрых краев;

rho: точность расстояния до сегмента линии в пикселях, для двойного типа рекомендуется 1,0;

theta: угловая точность сегмента линии в радианах, рекомендуется numpy.pi / 180;

Порог: параметр порога совокупной плоскости, тип int, сегмент линии обнаруживается при превышении порога. Чем больше значение, тем длиннее обнаруженный сегмент линии и тем меньше обнаруженных сегментов линии. В зависимости от ситуации рекомендуется сначала попробовать 100;

lines: значение этого параметра неизвестно.Оказалось, что разные строки не влияют на результат, но не игнорируют его существование;

minLineLength: минимальная длина отрезка линии в пикселях, установленная в соответствии со сценарием приложения;

maxLineGap: два линейных сегмента в одном направлении считаются максимально допустимым разрывом (разрывом) одного линейного сегмента. Если установленное значение превышено, два линейных сегмента будут считаться одним линейным сегментом. Чем больше значение, тем больше допустимый разрыв на линейном сегменте, тем более вероятно, что это Обнаружение потенциальных отрезков прямой линии.
 

Код здесь:

# Обнаружение прямой линии
 #Hough введение в линейное преобразование
         # Преобразование горизонтальной линии используется для обнаружения линии
         # Precondition-Edge обнаружение завершено
         # Пространство плоскости для преобразования пространства полярных координат
 # Связанная демонстрация кода API

import cv2
import numpy as np

 def line_detection (image): # заданы прямые линии HoughLines
         gray = cv2.cvtColor (image, cv2.COLOR_BGR2GRAY) # перейти в оттенки серого
         canny = cv2.Canny (gray, 50, 150, apertureSize = 3) # обнаружение ловушек на краю
         lines = cv2.HoughLines (canny, 1, np.pi / 180,200) # Преобразование линии Hough
         для строки в строках: # пройти полученную строку Хафа
        print(type(lines))
                 rho, theta = line [0] # Получить угол и расстояние до линии
        a = np.cos(theta)
        b = np.sin(theta)
        x0 =a*rho
        y0 =b*rho
        x1 = int(x0+1000*(-b))
        y1 = int(y0+1000*a)
        x2 = int(x0-1000*(-b))
        y2 = int(y0-1000 * a)
                 cv2.line (image, (x1, y1), (x2, y2), (0,0,255), 1) # Рисуем линию на изображении
    cv2.imshow("image-lines",image)

 def line_detect_possible_demo (image): # Обычно используется этот тип, сегмент линии задается
         gray = cv2.cvtColor (image, cv2.COLOR_BGR2GRAY) # перейти в оттенки серого
         canny = cv2.Canny (gray, 50, 150, apertureSize = 3) # обнаружение границ
         lines = cv2.HoughLinesP (canny, 1, np.pi / 180, 100, minLineLength = 50, maxLineGap = 10) # Преобразование строк в Hough
         для строки в строках: #traversal
        print(type(line))
        x1,y1,x2,y2=line[0]
                 cv2.line (image, (x1, y1), (x2, y2), (0, 0, 255), 1) # Рисуем линию на изображении
    cv2.imshow("image-lines-detect", image)


print("-------hello world--------")
src=cv2.imread("line.png")
cv2.imshow("source_image",src)
line_detection(src)
line_detect_possible_demo(src)
cv2.waitKey(0)
cv2.destroyAllWindows()

Исходное изображение:

График преобразования HoughLines

График преобразования HoughLinesP

Here is an approach that accumulates arrays for columns and rows. Then one can search for maxima in such accumulations (above a certain threshold) and deduce in which row or column there is a vertical or horizontal line.

If you want to quickly test the code, use the following Google Colab Notebook.
Google Colab Notebook

import numpy as np
import cv2
import scipy
from scipy.signal import find_peaks
from matplotlib import pyplot as plt

url = "https://i.stack.imgur.com/S00ap.png"
!wget $url -q -O input.jpg
fileName = 'input.jpg'
img = cv2.imread(fileName)
img = cv2.cvtColor(img, cv2.COLOR_BGR2RGB)

tmp = img.copy()
gray = cv2.cvtColor(tmp, cv2.COLOR_BGR2GRAY)
blurred = cv2.bilateralFilter(gray, 11, 61, 39)
edges = cv2.Canny(blurred, 0, 255)

v_kernel = cv2.getStructuringElement(cv2.MORPH_RECT, (1,3))
h_kernel = cv2.getStructuringElement(cv2.MORPH_RECT, (7,1))

v_morphed = cv2.morphologyEx(edges, cv2.MORPH_OPEN, v_kernel, iterations=2)
v_morphed = cv2.dilate(v_morphed, None)
h_morphed = cv2.morphologyEx(edges, cv2.MORPH_OPEN, h_kernel, iterations=2)
h_morphed = cv2.dilate(h_morphed, None)

v_acc = cv2.reduce(v_morphed, 0, cv2.REDUCE_SUM, dtype=cv2.CV_32S)
h_acc = cv2.reduce(h_morphed, 1, cv2.REDUCE_SUM, dtype=cv2.CV_32S)

def smooth(y, box_pts):
    box = np.ones(box_pts)/box_pts
    y_smooth = np.convolve(y, box, mode='same')
    return y_smooth

s_v_acc = smooth(v_acc[0,:],9) 
s_h_acc = smooth(h_acc[:,0],9) 

v_peaks, v_props = find_peaks(s_v_acc, 0.70*np.max(np.max(s_v_acc)))
h_peaks, h_props = find_peaks(s_h_acc, 0.70*np.max(np.max(s_h_acc)))

for peak_index in v_peaks:
    cv2.line(tmp, (peak_index, 0), (peak_index, img.shape[0]), (255, 0, 0),2)
for peak_index in h_peaks:
    cv2.line(tmp, (0, peak_index), (img.shape[1], peak_index), (0, 0, 255),2)
v_height = v_props['peak_heights'] #list of the heights of the peaks
h_height = h_props['peak_heights'] #list of the heights of the peaks

def align_axis_x(ax, ax_target):
    """Make x-axis of `ax` aligned with `ax_target` in figure"""
    posn_old, posn_target = ax.get_position(), ax_target.get_position()
    ax.set_position([posn_target.x0, posn_old.y0, posn_target.width, posn_old.height])

def align_axis_y(ax, ax_target):
    """Make y-axis of `ax` aligned with `ax_target` in figure"""
    posn_old, posn_target = ax.get_position(), ax_target.get_position()
    ax.set_position([posn_old.x0, posn_target.y0, posn_old.width, posn_target.height])

fig = plt.figure(constrained_layout=False, figsize=(24,16))
spec = fig.add_gridspec(ncols=4, nrows=2, height_ratios=[1, 1])
ax1 = fig.add_subplot(spec[0,0])
ax1.imshow(tmp)
ax2 = fig.add_subplot(spec[0, 1])
ax2.imshow(v_morphed)
ax3 = fig.add_subplot(spec[0, 2])
ax3.imshow(h_morphed)
ax4 = fig.add_subplot(spec[0, 3], sharey=ax3)
ax4.plot(h_acc[:,0], np.arange(len(h_acc[:,0])), 'y', marker="o", ms=1, mfc="k", mec="k")
ax4.plot(s_h_acc, np.arange(len(s_h_acc)), 'r', lw=1)
ax4.plot(h_height, h_peaks, "x", lw="5")
ax5 = fig.add_subplot(spec[1, 1], sharex=ax2)
ax5.plot(np.arange(len(v_acc[0,:])), v_acc[0,:], 'y', marker="o", ms=1, mfc="k", mec="k")
ax5.plot(np.arange(len(s_v_acc)), s_v_acc, 'r', lw=2)
ax5.plot(v_peaks, v_height, "x", lw="5")
plt.tight_layout()
align_axis_y(ax4,ax3)
align_axis_x(ax5,ax2)