Быстрое преобразование Хафа (, сокр. БПХ) — модификация преобразования Хафа, позволяющая параметрически идентифицировать прямые (а также с дополнительной модификацией отрезки и четырехугольники) с меньшей вычислительной сложностью за счет использования факта самопересечения рассматриваемых дискретных прямых.
История Алгоритм впервые был предложен М. Л. Брейди в 1992 году, в дальнейшем переизобретался несколько раз различными авторами.
Определение
Пусть дано изображение размера . Рассмотрим диадических прямых (прямых специального вида), состоящих из пикселей на изображении каждая (один пиксель в столбце).
Пусть — интенсивность -го пикселя, принадлежащего диадической прямой, заданной параметрами ; — Хаф-образ этой диадической прямой.
Образ дискретного преобразование Хафа определяется следующей формулой:
Прямое вычисление всех значений требует операций: перебор по различных значений параметров , , перебор для каждой пары значений .
В свою очередь, алгоритм БПХ, основанный на учёте пересечений отрезков друг с другом, требует действий, на одну прямую необходимо операций (для квадратных изображений ). По теореме, сформулированной Т. М. Ханиповым, невозможно сложить диадические прямые с асимптотически меньшей вычислительной сложностью.
Алгоритм Алгоритм основан на принципе «разделяй и властвуй». Задача состоит в нахождении сумм значений пикселей вдоль отрезков, соединяющих «левый» и «правый» края изображения. Изображение делится пополам, в каждой части задача решается независимо. Для получения итоговой суммы на каждом из отрезков складываются ответы на «левой» и «правой» его половинах.
В алгоритме БПХ пиксели прямых произвольного вида дискретно приближаются диадическими прямыми. Пиксели диадического приближения прямой на изображении размера удалены от исходной прямой не более, чем на пикселей.
Отрезки параметризуются центрами соединяемых пикселей. Поэтому разбиение отрезка на подотрезки лишь приближенно составляет исходный отрезок. Ошибка аппроксимации с шагами рекурсии накапливается, однако не более чем на пикселей. Построенная таким образом дискретизация отрезка до пикселей называется диадической аппроксимацией.
Порождающие диадические паттерны
Далее паттерном называется множество пикселей , содержащее по элементу в каждой вертикали изображения. Отклонением паттерна будет называться значение , а координатой — значение . Сдвигом паттерна будет называться множество Порождающие диадические паттерны ширины и наклона определяются рекурсивно. При паттерн состоит из одного пикселя, а при выражается через .
Диадические прямые Преимущественно горизонтальные, направленные вверх, диадические прямые получаются из всех сдвинутых по вертикали порождающих паттернов , построенных со всеми возможными координатами на изображении .
Для приближенного вычисления преобразования Хафа требуется найти суммы по всем диадическим прямым на изображении. В этой сумме прямых по точек каждая. За счет рекурсивного перехода это суммирование сводится к подсчету отдельно левых, отдельно правых половин, что позволяет свести вычисление к подсчету сумм по точек каждая.
Рассмотрим бинарные слова, состоящие из чисел 0 и 1. Множество диадических слов определяется рекурсивно. будет называться диадическим словом, если имеет вид или , где — пустое или диадическое слово. Все диадические слова длины не больше трех: 0, 1, 000, 010, 101, 111.
Для каждого диадического слова рассматривается кумулятивная сумма . Будем говорить, что последовательность пикселей — диадическая прямая, соединяющая центры пикселей и .
Существует ровно диадических прямых длины . По одной на каждую пару и .
Формальное описание Алгоритм БПХ устроен следующим образом:
Исходное состояние матрицы — исходное изображение размера . Затем происходит вычисление на -их уровнях по очереди, начиная с первого: на -том уровне матрица в текущем состоянии делится на группы по принципу равенства целой части координаты второй оси после деления на ; получаются подматрицы ; объединим соседние в пары (без пересечений, это возможно, так как размер матрицы — степень двойки) и назовем в этой паре первой ту подматрицу, что расположена на меньших координатах по второй координате в матрице, а другую — второй; вместо первых в каждой паре записывается ее сумма с соответствующей ей второй, а вместо второй — сумму первой и второй с циклическим сдвигом на один влево. Таким образом считается Хаф-образ таких прямых, что для любой пары точек с координатами с этой прямой выполняется , с помощью аппроксимации диадическими прямыми. Для того, чтобы посчитать образ для остальных прямых, достаточно поворачивать изображение и проводить ту же самую операцию, а полученные результаты сложить.
Полученные таким образом на каждом уровне матрицы являются элементами БПХ-пирамиды. Формальное описание БПХ-пирамиды: Нулевым уровнем БПХ-пирамиды является исходное изображение (размером , а последним — Хаф-образ, содержащий суммы по диадическим прямым длины . Для описания -ого уровня пирамиды исходное изображение разбивается на горизонтальные полосы , где — номер полосы, . Для каждой полосы в -ом уровне БПХ-пирамиды хранятся суммы по всевозможным паттернам полосы, имеющим длину и параметры . Количество таких паттернов для полосы — , поэтому -й уровень пирамиды занимает столько же памяти, сколько исходное изображение.
Инвариантность количества затрачиваемой памяти и возможность хранить каждый уровень в матрице того же размера, что оригинальное изображение, без потери интерпретируемости дает следующее свойство: можно хранить БПХ-пирамиду в форме матрицы с размерностью, на одну большую, чем размерность исходного изображения (по одной оси — количество уровней, ), по остальным — размер изображения).
Программные реализации Пример реализации на языке python:
import numpy as np W = 2**5 H = 2**5 img = np.random.random([H, W])
def calc_sums(img, xmin, xmax): res = np.zeros([W, xmax-xmin]) if xmax - xmin == 1: res[:, 0] = img[:, xmin] else: mid = (xmin + xmax) // 2 ans1 = calc_sums(img, xmin, mid) ans2 = calc_sums(img, mid, xmax) for x in range(W): for shift in range(xmax-xmin): res[x, shift] = ans1[x, shift//2] + ans2[(x + shift//2 + shift%2) % W, shift//2] return res res = calc_sums(img, 0, W)
Алгоритм реализован в библиотеке opencv и может быть использован, например, для быстрого нахождения точки схода.
Обобщения на трехмерный случай
БПХ для плоскостей Решение этой задачи подразумевает использование алгоритма для двумерного случая.
Хаф-образ плоскостей будет так же трехмерным (плоскость задается через три координаты вектора, перпендикулярного ей). Пусть он будет задан параметризацией , где — координата пересечения плоскости с границей изображения на луче , — координата точки пересечения с границей изображения, параллельной лучу в плоскости , — разница координат второй и первой точки пересечения плоскости с границами изображения. Первая точка находится в пересечении содержащих границу изображения плоскостей и плоскости, параллельной . Вторая точка — в пересечении содержащих границу изображения плоскостей, параллельных и .
Будем называть плоскость преимущественно-перпендикулярной к оси координат, если нормаль к ней образует с данной осью меньший угол, чем с двумя другими. Будем рассматривать только плоскости, преимущественно-перпендикулярные к оси y. Они разделяются на 4 типа наклонов, как это показано на рисунке 4. Без ограничения общности будем считать, что рассматриваемые плоскости имеют тип I.
Построение Хаф-образа методом перебора плоскостей имеет асимптотическую сложность (количество плоскостей, умноженное на количество операций для суммирования одной плоскости), где m, n, k — размеры изображения в каждой размерности.
Быстрым преобразованием Хафа в данном случае будет следующий алгоритм: Для каждой плоскости перпендикулярной оси с координатой по этой оси считается быстрое преобразование Хафа, а результат кладется в трехмерное пространство по координатам . Для каждой плоскости в получившемся трехмерном пространстве перпендикулярной оси с координатой по этой оси считается быстрое преобразование Хафа, а результат кладется в куб по координатам .
Сложность такого преобразования складывается из сложности первого шага () и сложности второго шага (), которые считаются, как произведение количества рассматриваемых плоскостей и количества операций на одну плоскость. Итого, , в пересчете на одну плоскость .
БПХ для трехмерных прямых Хаф-образ трехмерной прямой будет четырехмерным (по два параметра на каждую из двух точек на прямой). Пусть он будет задан параметризацией . — координаты x, y точки на плоскости , — координаты x, y точки пересечения прямой с границей изображения, параллельной плоскости .
Построение Хаф-образа методом перебора трехмерных прямых имеет асимптотическую сложность (количество прямых умноженное на количество операций для суммирования одной прямой), где m, n, k — размеры изображения в каждой размерности.
Быстрое преобразование Хафа для такого случая формулируется подобно определению для двумерного случая. В двумерном случае возможность сдвига была только вдоль одной оси, теперь же сдвиг будет вдоль одной оси, вдоль второй оси и вдоль двух осей одновременно.
Подсчет паттернов длины два требует (количество групп суммируемых плоскостей), умноженное на (сложность проводимых сложений для каждой группы), операций. Подсчет паттернов длины 4 требует операций. Длины паттернов — , где определяется, как , то есть номер рассматриваемой длины паттерна. Суммируя слагаемых (количество возможных для рассматриваемого изображения длин паттернов) с использованием формулы суммы геометрической прогрессии, получается сложность алгоритма , а сложность на одну прямую . При сложность будет константной.
Сочетание БПХ и принципа четырёх русских Несмотря на то, что количество операций на одну прямую константное при равном размере изображения в каждой размерности, для всех прямых надо потратить . Но если не нужны все прямые, а нужна только часть их, то можно совершить предпосчёт первых шагов , сохранить их в память, а затем посчитать суммы только для тех прямых, которые нужны.
Этот концепт был закреплен в методе четырех русских. Метод назван в честь первооткрывателей В. Арлазаров, М. Кронрод, Е. Диниц, И. Фараджев.
В оригинальном алгоритме БПХ для трёхмерных прямых совершается на каждом из уровней подсчет для прямых определенной длины. С другой стороны можно сделать предпосчёт только для первых шагов, а затем производить подсчёт для нужных прямых.
Для того, чтобы определить оптимальное количество шагов предпосчёта, необходимо решить такое уравнение ( — количество прямых, которое необходимо найти алгоритму):
Слева — количество операций для выполнения предпосчёта. Справа — количество операций на нахождение сумм вдоль запрошенных прямых. Пусть необходимо найти все прямые, тогда , тогда решением уравнения будет , а левая и правая части равны , что в меньше, чем без предпосчёта. Тем не менее за уменьшение количества операций необходимо заплатить памятью в том же размере, что занимает Хаф-образ (свойство инвариантности занимаемой памяти на каждом уровне подсчёта алгоритмом БПХ).
Вычисление суммы по отрезку на изображении Принцип вычисления основан на использовании значений не только последнего уровня БПХ-пирамиды (то есть непосредственно самого Хаф-образа), но и других уровней БПХ-пирамиды.
Задача делится на две подзадачи: Найти диадическую прямую проходящую через два заданных пикселя Из суммы значений вдоль этой прямой выделить ту часть суммы, которая относится к паттерну между заданными пикселями
Поиск диадической прямой проходящей через два заданных пикселя Без ограничения общности считаем, что . Здесь будут рассмотрены только преимущественно вертикальные паттерны с наклоном вправо, то есть и . Также используется -параметризация и значение равное , где — размер изображения по оси .
Пусть двоичное разложение параметра диадической прямой выглядит как Тогда паттерн может быть записан так ( — округление до ближайшего целого.):