Обнаружение фигур на изображениях с помощью преобразования Хафа

Введение

Метод обнаружения фигур на изображениях

Преобразование Хафа – это метод выделения признаков, используемый в анализе изображений, компьютерном зрении и цифровой обработке изображений. Цель данной техники – поиск неидеальных экземпляров объектов, принадлежащих к определенному классу фигур, посредством процедуры голосования. Эта процедура голосования выполняется в параметрическом пространстве, из которого кандидаты в объекты извлекаются как локальные максимумы в так называемом пространстве аккумуляторов, которое алгоритм явно строит для вычисления преобразования Хафа. Классическое преобразование Хафа было ориентировано на идентификацию линий на изображении, но впоследствии оно было расширено для идентификации положений произвольных фигур, чаще всего окружностей или эллипсов. Преобразование Хафа в том виде, в котором оно повсеместно используется сегодня, было изобретено Ричардом Дудой и Питером Хартом в 1972 году, которые назвали его «обобщенным преобразованием Хафа», ссылаясь на патент Пола Хафа 1962 года. Дана Х. Баллард популяризировала это преобразование в сообществе компьютерного зрения в 1981 году в статье под названием «Обобщение преобразования Хафа для обнаружения произвольных форм».

Теория

В автоматическом анализе цифровых изображений часто возникает подзадача обнаружения простых форм, таких как прямые линии, окружности или эллипсы. Во многих случаях детектор границ может использоваться на этапе предварительной обработки для получения точек изображения или пикселей, лежащих на желаемой кривой в пространстве изображения. Однако из-за несовершенства исходных данных изображения или детектора границ могут отсутствовать точки или пиксели на желаемых кривых, а также наблюдаться пространственные отклонения между идеальной линией/окружностью/эллипсом и зашумленными точками границ, полученными с помощью детектора границ. По этим причинам группировка извлеченных характеристик границ в соответствующие линии, окружности или эллипсы часто является нетривиальной задачей. Трансформация Хафа призвана решить эту проблему, позволяя объединять точки границ в кандидаты на объекты путем проведения явной процедуры голосования для набора параметризованных объектов изображения (Шапиро и Стокман, 304).

Обнаружение линий

Самый простой случай преобразования Хафа — обнаружение прямых линий. В общем случае прямая линия может быть представлена точкой (b, m) в параметрическом пространстве. Однако вертикальные линии представляют проблему, поскольку приводят к неограниченным значениям параметра наклона m. Таким образом, по вычислительным соображениям, Дуда и Харт предложили использовать нормальную форму Гессе:

где ρ — расстояние от начала координат до ближайшей точки на прямой, а θ — угол между осью и линией, соединяющей начало координат с этой ближайшей точкой. Интуиция, лежащая в основе этой формы, аналогично уравнению плоскости, заключается в том, что каждый вектор на прямой должен быть перпендикулярен (ортогонален) прямой длины ρ, исходящей из начала координат. Можно заметить, что точка пересечения линии функции и перпендикулярной линии, исходящей из начала координат, находится в точке. Таким образом, для любой точки на прямой вектор должен быть ортогонален вектору. Следовательно, для любой точки на линии функции должно выполняться уравнение. Поскольку ρ = r и θ = θ, получаем. Поскольку ρ ≥ 0, получаем окончательную форму.

Таким образом, каждой линии изображения можно сопоставить пару (r, θ). Плоскость (r, θ) иногда называют пространством Хафа для множества прямых линий в двух измерениях. Такое представление делает преобразование Хафа концептуально очень близким к двумерному преобразованию Радона. Фактически, преобразование Хафа математически эквивалентно преобразованию Радона, но эти два преобразования имеют различные вычислительные интерпретации, традиционно связанные с ними. Для заданной одной точки в плоскости множество всех прямых, проходящих через эту точку, соответствует синусоидальной кривой в плоскости (r, θ), которая уникальна для этой точки. Набор из двух или более точек, образующих прямую линию, создаст синусоиды, пересекающиеся в точке (r, θ) для этой линии. Таким образом, задача обнаружения коллинеарных точек может быть сведена к задаче поиска пересекающихся кривых.

Вероятностная интерпретация

При условии, что форма параметризована функцией , принимающей значения в множестве , называемом пространством форм, преобразование Хоуга можно интерпретировать как обратное преобразование распределения вероятностей из пространства изображения в пространство форм , а обнаружение формы – как оценку максимального правдоподобия. В частности, преобразование Хоуга выполняет приближенный наивный байесовский вывод. Мы начинаем с равномерного априорного распределения на пространстве форм. Мы учитываем только положительные свидетельства и игнорируем все отрицательные, чтобы обнаруживать частично перекрытые формы. Мы суммируем логарифмическую функцию правдоподобия в пространстве форм с точностью до аддитивной константы. Предположение наивного Байеса означает, что все пиксели в пространстве изображения предоставляют независимые свидетельства, поэтому их правдоподобия перемножаются, то есть их логарифмические правдоподобия складываются. Свобода в выборе аддитивной константы позволяет не учитывать "фоновые пиксели" в пространстве форм. Наконец, мы выполняем оценку максимального правдоподобия, выбирая пики логарифмической функции правдоподобия в пространстве форм.

Реализация

Линейный алгоритм преобразования Хауфа оценивает два параметра, определяющие прямую линию. Пространство преобразований двумерно, и каждая точка в этом пространстве используется как аккумулятор для обнаружения или идентификации линии, описываемой каждой точкой в обнаруженных границах изображения, что вносит вклад в аккумуляторы. Размерность аккумулятора равна числу неизвестных параметров, то есть двум, учитывая квантованные значения ρ и θ в паре (ρ, θ). Для каждого пикселя и его окрестности алгоритм преобразования Хауфа определяет, достаточно ли доказательств наличия прямой линии в этом пикселе. Если да, то он вычисляет параметры (ρ, θ) этой линии, затем ищет ячейку аккумулятора, в которую попадают эти параметры, и увеличивает значение этой ячейки. Находя ячейки с наибольшими значениями, обычно путем поиска локальных максимумов в пространстве аккумулятора, можно извлечь наиболее вероятные линии и получить их (приблизительные) геометрические определения (Шапиро и Стокман, 304). Самый простой способ найти эти максимумы – применить некоторый вид порога, но другие методы могут дать лучшие результаты в различных ситуациях – определяя, какие линии найдены, а также их количество. Поскольку возвращаемые линии не содержат информации о длине, часто на следующем этапе необходимо определить, какие части изображения соответствуют каким линиям. Более того, из-за погрешностей на этапе обнаружения границ обычно возникают ошибки в пространстве аккумулятора, что может затруднить поиск соответствующих максимумов и, следовательно, соответствующих линий. Конечным результатом линейного преобразования Хауфа является двумерный массив (матрица), аналогичный аккумулятору, одно измерение которого – квантованный угол θ, а другое – квантованное расстояние ρ. Каждый элемент матрицы имеет значение, равное сумме точек или пикселей, расположенных на линии, представленной квантованными параметрами. Таким образом, элемент с наибольшим значением указывает на прямую линию, которая наиболее представлена на входном изображении.

Пример 1

Рассмотрим три точки данных, изображенные здесь черными точками. Для каждой точки данных построено несколько линий, проходящих через нее, все под разными углами. Они показаны здесь разными цветами. Преобразование Хафа накапливает вклад всех пикселей на обнаруженном крае. Для каждой линии существует опорная линия, перпендикулярная ей и пересекающая начало координат. В каждом случае одна из них показана стрелкой. Вычисляется длина (то есть перпендикулярное расстояние до начала координат) и угол каждой опорной линии. Длины и углы представлены в таблицах под диаграммами. Из расчетов видно, что в обоих случаях опорная линия под углом 60° имеет схожую длину. Следовательно, можно заключить, что соответствующие линии (синие на изображении выше) очень похожи. Таким образом, можно предположить, что все точки лежат близко к синей линии.

Пример 2

Ниже приведен другой пример, демонстрирующий результаты преобразования Хафа, примененного к растровому изображению, содержащему две толстые линии. Результаты преобразования были сохранены в матрице, где значение каждой ячейки соответствует количеству кривых, проходящих через данную точку. Более высокие значения ячеек отображаются более светлым цветом. Два отчетливо ярких пятна соответствуют параметрам Хафа для двух линий. По координатам этих пятен можно определить угол и расстояние от центра изображения до этих линий на исходном изображении.

Использование направления градиента для уменьшения количества голосов

Улучшение, предложенное О’Горманом и Клоузом, может быть использовано для обнаружения линий, если учитывать, что локальный градиент интенсивности изображения обязательно будет ортогонален к границе. Поскольку обнаружение границ обычно включает вычисление модуля градиента интенсивности, направление градиента часто определяется как побочный результат. Если данная точка с координатами (x, y) действительно лежит на линии, то локальное направление градиента дает параметр θ, соответствующий этой линии, а параметр r затем немедленно вычисляется. (Шапиро и Стокман, 305) Направление градиента можно оценить с точностью до 20°, что сокращает траекторию синусоиды с полных 180° примерно до 45°. Это уменьшает время вычислений и оказывает интересный эффект – снижает количество бесполезных "голосов", тем самым повышая видимость пиков, соответствующих реальным линиям на изображении.

Трансформация Хауфа на основе ядра (KHT)

Фернандес и Оливейра предложили усовершенствованную схему голосования для преобразования Хафа, позволяющую программной реализации достигать производительности в реальном времени даже при работе с относительно большими изображениями (например, 1280×960). Преобразование Хафа на основе ядра использует ту же параметризацию, предложенную Дудой и Хартом, но оперирует с кластерами приблизительно коллинеарных пикселей. Для каждого кластера голоса подаются с использованием ориентированного эллиптического гауссовского ядра, которое моделирует неопределенность, связанную с наилучшей аппроксимирующей линией относительно данного кластера. Этот подход не только значительно повышает эффективность схемы голосования, но и обеспечивает более чистый аккумулятор и делает преобразование более устойчивым к обнаружению ложных линий.

3-D-трансформация Хауга для обнаружения плоскости (3DKHT)

Лимбергер и Оливейра предложили детерминированный метод обнаружения плоскостей в неорганизованных облаках точек, вычислительная сложность которого линейна по количеству образцов, обеспечивая работу в реальном времени для относительно больших наборов данных (до точек на процессоре 3,4 ГГц). Метод основан на быстрой стратегии голосования с использованием преобразования Хоуга для плоских областей, вдохновленной преобразованием Хоуга, основанным на ядрах (KHT). Это трехмерное преобразование Хоуга, основанное на ядрах (3DKHT), использует быстрый и надежный алгоритм для сегментации кластеров приблизительно компланарных образцов и производит голосование за отдельные кластеры (вместо отдельных образцов) на сферическом аккумуляторе, используя тривариатное гауссово ядро. Этот подход на несколько порядков быстрее существующих (недетерминированных) методов обнаружения плоскостей в облаках точек, таких как RHT и RANSAC, и лучше масштабируется с ростом размера наборов данных. Он может быть использован в любом приложении, требующем быстрого обнаружения планарных признаков в больших наборах данных.

Трансформация Хоуга кривых и ее обобщение для аналитических и неаналитических форм

Хотя версия преобразования, описанная выше, применима только к поиску прямых линий, аналогичное преобразование может быть использовано для поиска любой формы, которую можно представить набором параметров. Например, круг можно преобразовать в набор из трех параметров, представляющих его центр и радиус, в результате чего пространство Хафа становится трехмерным. Таким образом можно найти произвольные эллипсы и кривые, а также любую форму, которую можно легко выразить в виде набора параметров. Обобщение преобразования Хафа для обнаружения аналитических форм в пространствах любой размерности было предложено Фернандесом и Оливейрой. В отличие от других подходов, основанных на преобразовании Хафа для аналитических форм, техника Фернандеса не зависит ни от формы, которую необходимо обнаружить, ни от типа входных данных. Обнаружение может быть направлено на определенный тип аналитической формы путем изменения предполагаемой модели геометрии, в которой закодированы данные (например, евклидово пространство, проективное пространство, конформная геометрия и т. д.), в то время как предложенная формулировка остается неизменной. Кроме того, она гарантирует, что искомые формы представлены с минимально возможным количеством параметров, и позволяет одновременно обнаруживать различные типы форм, которые наилучшим образом соответствуют входному набору данных с различными размерностями и различными геометрическими определениями (например, одновременное обнаружение плоскостей и сфер, наилучшим образом соответствующих набору точек, прямых линий и окружностей). Для более сложных форм на плоскости (то есть форм, которые не могут быть представлены аналитически в некотором 2D пространстве) используется обобщенное преобразование Хафа, которое позволяет признаку «голосовать» за определенное положение, ориентацию и/или масштаб формы, используя предварительно определенную таблицу поиска. Преобразование Хафа аккумулирует вклад от всех пикселей на обнаруженной границе.

Процесс обнаружения круга

Изменение алгоритма для обнаружения круговых форм вместо линий относительно просто. Сначала мы создаём аккумуляторное пространство, состоящее из ячейки для каждого пикселя. Изначально каждая ячейка устанавливается в 0. Для каждой точки границы (i, j) на изображении увеличиваем все ячейки, которые, согласно уравнению окружности, могут являться центром окружности. Эти ячейки представлены буквой в уравнении. Для каждого возможного значения, найденного на предыдущем этапе, находим все возможные значения, удовлетворяющие уравнению. Ищем локальные максимумы в аккумуляторном пространстве. Эти ячейки представляют собой окружности, обнаруженные алгоритмом. Если мы заранее не знаем радиус искомой окружности, мы можем использовать трёхмерное аккумуляторное пространство для поиска окружностей с произвольным радиусом. Естественно, это требует больших вычислительных затрат. Этот метод также может обнаруживать окружности, частично выходящие за пределы аккумуляторного пространства, если в нём всё ещё присутствует достаточная площадь окружности.

Обнаружение трехмерных объектов (самолетов и цилиндров)

Трансформация Хафа также может использоваться для обнаружения 3D-объектов в данных о дальности или 3D-облаках точек. Расширение классической трансформации Хафа для обнаружения плоскостей достаточно прямолинейно. Плоскость представляется своим явным уравнением, для которого можно использовать 3D-пространство Хафа, соответствующее , и . Это расширение страдает от тех же проблем, что и его 2D-аналог, то есть почти горизонтальные плоскости могут быть обнаружены надежно, в то время как производительность снижается по мере приближения направления плоскости к вертикальному (большие значения и усиливают шум в данных). Эта формулировка плоскости использовалась для обнаружения плоскостей в облаках точек, полученных с помощью воздушного лазерного сканирования, и работает очень хорошо, поскольку в этой области все плоскости почти горизонтальны. Для обобщенного обнаружения плоскостей с использованием трансформации Хафа плоскость может быть параметризована по нормальному вектору (с использованием сферических координат) и расстоянию от начала координат, что приводит к образованию трехмерного пространства Хафа. В результате каждая точка входных данных "голосует" за синусоидальную поверхность в пространстве Хафа. Пересечение этих синусоидальных поверхностей указывает на наличие плоскости. Для более общего подхода, охватывающего более трех измерений, требуются эвристические методы поиска для обеспечения практической реализуемости. Трансформация Хафа также использовалась для поиска цилиндрических объектов в облаках точек, используя двухэтапный подход. На первом этапе определяется ориентация цилиндра, а на втором – его положение и радиус.

Использование взвешенных функций

Одна распространенная деталь реализации. А именно, определение корзин с наибольшим количеством элементов на одном этапе может быть использовано для сужения диапазона значений, которые ищутся на следующем этапе.

Тщательно выбранное пространство параметров

Высокоразмерное пространство параметров для преобразования Хафа не только замедляет работу, но и, если реализовано без должной подготовки, может легко привести к переполнению доступной памяти. Даже если программная среда позволяет выделить массив, превышающий доступное пространство памяти, с помощью виртуальной памяти, количество операций подкачки, необходимых для этого, будет очень велико, поскольку массив-аккумулятор используется с произвольным доступом, редко останавливаясь в смежных областях памяти при переходе от индекса к индексу. Рассмотрим задачу поиска эллипсов на изображении размером 800x600. Если предположить, что радиусы эллипсов ориентированы вдоль главных осей, пространство параметров будет четырехмерным. (x, y) определяет центр эллипса, а a и b обозначают два радиуса. Разрешение центру находиться в любом месте изображения добавляет ограничения 0 < x < 800 и 0 < y < 600. Если радиусам задать те же значения, что и ограничениям, останется разреженный массив-аккумулятор, содержащий более 230 миллиардов значений. Программа, разработанная таким образом, вряд ли сможет выделить достаточно памяти. Это не означает, что проблему нельзя решить, а лишь то, что необходимо найти новые способы ограничить размер массива-аккумулятора, что сделает решение осуществимым. Например:

Если разумно предположить, что каждый эллипс полностью содержится в изображении, можно уменьшить диапазон радиусов. Максимальный радиус возможен, если центр эллипса находится в центре изображения, позволяя краям эллипса достигать границ. В этом крайнем случае каждый радиус может быть не более половины размера изображения в соответствующем направлении. Уменьшение диапазона a и b таким образом сокращает массив-аккумулятор до 57 миллиардов значений. Пожертвовать точностью радиусного центра: если прогнозируется отклонение центра на 3 пикселя по осям x и y, размер массива-аккумулятора уменьшится примерно до 6 миллиардов значений. Пожертвовать точностью радиусов: если предполагается отклонение радиусов на 5, размер массива-аккумулятора дополнительно сократится примерно на 256 миллионов значений. Обрежьте изображение до интересующих областей. Это зависит от изображения и, следовательно, непредсказуемо, но представьте себе случай, когда все интересующие края изображения находятся в верхнем левом квадранте. В этом случае массив-аккумулятор можно еще больше уменьшить, ограничив все 4 параметра коэффициентом 2, что даст общий коэффициент уменьшения 16. Применив только первые три из этих ограничений к приведенному примеру, размер массива-аккумулятора уменьшится почти в 1000 раз, приведя его к размеру, который гораздо вероятнее поместится в память современного компьютера.

Эффективный алгоритм обнаружения эллипсы

Юнхон Сье и Цян Цзи предлагают эффективный способ реализации преобразования Хафа для обнаружения эллипсов, решая проблемы с памятью. Как описано в алгоритме (на странице 2 статьи), этот подход использует лишь одномерный аккумулятор (для малой оси) для обнаружения эллипсов на изображении. Вычислительная сложность составляет O(N³) относительно количества ненулевых точек на изображении.

Ограничения

Трансформация Хауфа эффективна только в том случае, если значительное количество голосов попадает в нужную ячейку, чтобы её можно было легко обнаружить на фоне шума. Это означает, что ячейка не должна быть слишком маленькой, иначе часть голосов попадет в соседние ячейки, что снизит заметность основной ячейки. Кроме того, когда число параметров велико (то есть, при использовании трансформации Хауфа, как правило, с более чем тремя параметрами), среднее количество голосов в одной ячейке очень мало, и ячейки, соответствующие реальной фигуре на изображении, не обязательно будут иметь значительно больше голосов, чем их соседи. Вычислительная сложность возрастает пропорционально с каждым дополнительным параметром, где – размер пространства изображения, а – число параметров. (Шапиро и Стокман, 310) Таким образом, трансформацию Хауфа следует использовать с большой осторожностью для обнаружения чего-либо, кроме линий или окружностей. Наконец, эффективность трансформации Хауфа во многом зависит от качества входных данных: для эффективной работы трансформации Хауфа необходимо хорошо обнаруживать границы. Применение трансформации Хауфа к зашумленным изображениям – задача деликатная, и обычно перед этим требуется этап подавления шума. В случае, когда изображение содержит зернистый шум, как это часто бывает на радарных изображениях, для обнаружения линий иногда предпочтительнее использовать преобразование Радона, поскольку оно ослабляет шум за счет суммирования.