В предыдущем посте об обнаружении полос мы выяснили, как извлекать края из изображения. В этой статье я извлечу строки.
Матрицы и линии
Изображения хранятся в виде двумерных матриц, поэтому мы можем рассматривать их как декартову систему координат. В этой системе мы можем определить любую строку как следующую функцию:
Чтобы узнать, принадлежит ли пиксель заданной строке, нам просто нужно проверить, дает ли функция по заданной координате x правильное значение y.
Проблема заключается в том, что точка может принадлежать бесконечному числу возможных прямых (поскольку уравнение прямой имеет 2 переменные).
Поэтому вместо этого мы создадим так называемое двумерное пространство Хафа и нанесем на него все возможные значения m и b для данного пикселя. Для каждой точки в нормальном пространстве у нас будет линия в пространстве Hough.
Однако на практике мы поступим немного иначе. Мы используем полярное представление для точек пикселей, поэтому мы можем определить наши линии как расстояние и угол поворота от опорной точки (обычно 0,0 точки изображения). В этом представлении линейное уравнение выглядит следующим образом:
d = x * cos (θ) + y * sin (θ)
Итак, для точки в нормальном пространстве мы получим синусоидальную кривую. Любые d, θ от кривой в пространстве Хафа представляют собой линию в пространстве изображения, которая проходит через точку (x, y). Обратите внимание: это означает, что у нас может быть бесконечно много возможных прямых для одной точки.
Чтобы точно определить линию, нам понадобится как минимум 2 точки. Давайте посмотрим:
А вот и волшебство: у двух кривых есть точка пересечения - и эта точка описывает уравнение нашей линии в пространстве изображения. В основе этого лежит логика: 2 точки независимо могут принадлежать множеству возможных линий (поскольку они d и θ могут различаться). Однако существует только одна возможная линия (d, θ), которая проходит через обе точки.
И это тоже работает с любым количеством точек:
Что произойдет, если у нас будет более одной строки?
У нас будет более одной точки пересечения. Собственно, их у нас будет много. Это имеет смысл, поскольку мы можем знать, что у нас на изображении только 2 линии, а у компьютера их нет. Он просто говорит нам, какие из них наиболее многообещающие. При работе с реальными изображениями мы обычно получаем много шума, а также линий, которые не являются «настоящими» линиями; поэтому мы можем рассматривать точки в пространстве Хафа как значение вероятности данной (d, theta) линии.
Как видите, выполнение алгоритма преобразования Хафа может дать некоторые значимые результаты, но нам все равно нужно его фильтровать, поскольку эта стратегия очень подвержена шумам.
В следующей статье я узнаю, как избавиться от ложноположительных результатов линий и как их построить. Для получения дополнительной информации о преобразовании Хафа я рекомендую эти лекции.
Алгоритм
build_hough_space_fom_image (img)
возвращает Hough-space для изображения. Алгоритм перебирает каждый пиксель и строит кривую для данного изображения в пространстве Хафа. Новая кривая добавляется к существующему пространству Hough, поэтому пиксель, принадлежащий пересечениям, будет иметь более высокие значения. Выделены наиболее важные строки.
def build_hough_space_fom_image(img, shape = (100, 300), val = 1):
hough_space = np.zeros(shape)
for i, row in enumerate(img):
for j, pixel in enumerate(row):
if pixel != val : continue
hough_space = add_to_hough_space_polar((i,j), hough_space)
return hough_space
def add_to_hough_space_polar(p, feature_space):
space = np.linspace(0, pi, len(feature_space))
d_max = len(feature_space[0]) / 2
for i in range(len(space)):
theta = space[i]
d = int(p[0] * sin(theta) + p[1] * cos(theta)) + d_max
if (d >= d_max * 2) : continue
feature_space[i, d] += 1
return feature_space
