Популярно: преобазования Хафа и Радона. В чем разница?

[CyberCraft]

Я не математик, а просто немного программер. Наткнулся по случаю на "рецепт" вычисления преобразования Хафа. Коротко: фазовое пространство QP разбивается на ячейки счетчики и вычисляется сумма попаданий(интенсивностей) в каждую ячейку QP для всех точек изображения XY, при условии выполнения уравнения прямой x*cosQ + y*sinQ = P. В результате в QP получаем изображение пучка синусоид, где самые яркие точки соотвествуют прямым линиям на изображении.
Я реализовал это преобразование. Работает достаточно быстро на небольших изображениях(500x300), првильно находит прямые. Хотя на изображениях 4000x4000 будет тормозить.

В другой статье прочитал определение преобразования Радона R(PQ): "это интеграл от функции f(x,y) вдоль прямой, удаленной от начала координат на расстояние P, нормаль которой составляет угол Q с осью абсцисс". На первый взгляд ничем не отличается от Хафа... В чем прикол не пойму. Утверждают, что п.Радона намного быстрее. Однако дальше формализм слишком замороченный и заумный. Хотелось бы популярное изложение, "рецепт" для чайников. Может кто объяснит в чем разница между этими преобразованиеями и как реализовать пр. Радона?

[PAV]

По-моему это одно и то же.

[Brukvalub]

CyberCraft писал(а):

Может кто объяснит в чем разница между этими преобразованиеями

Мне кажется, что эти преобразования различаются не по способу вычисления, а по тем задачам, для решения которых они предназначены. Как я понял, преобразование Хафа бывает только прямым, и служит для выявления прямых линий на изображении - посчитал и выявил. Преобразование Радона же моделирует сканирование плоского сечения прямолинейными лучами (например, сканирование участка человеческого тела рентгеном). Такое сканирование автоматически совершает прямое преобразование Радона, и главным здесь становится корректно выполнение обратного преобразования, которое восстанавливает исходное сечение по сделанному преобразованию. Такой метод лежит в основе, например, компьютерного томографирования (только там решается несколько более сложная задача восстановления изображения пространственного тела по его преобразованию Радона).

[CyberCraft]

Действительно, вот в статье
В http://www.graphicon.ru/2006/proceeding ... _Yurin.doc
пишут, что "для прямых они практически эквивалентны". Читаю и медитирую.... =)
Всё равно не понятно. Если я уже имею п.Хафа (которое очень просто в понимании), как от него перейти(переделать) к п.Радона?

Уточню задачу. Необходимо найти и спозиционировать на большом изображении, имеющем множество коротких, неправильных и нечетких линий, небольшой фрагмент почти в точности топологически совпадающий с одним из участков на большом изображении, повернутым на неизвестный угол, сдвинутым в неизвестную область, слегка неправильно масштабированным и сдвинутым по средней яркости. Афинного и краевого искажения нет. Восстанавливать изображение (т.е. выполнять обратное преобразование) не требуется. Можно выполнить сплошное сканирование в каждой точке под всеми углами (N1*M1*360*N2*M2), но это медленно и неинтересно.

Преобразование Хафа на тестовых изображениях геометрических объектов великолепно работает, но в моей задаче с реальными(даже бинаризованными) снимками работает только в очень простых случаях, практически бесполезно. Ищу более эффективный алгоритм, всвязи с чем заинтересовался п.Радона. Может и оно не подойдет.

[Brukvalub]

Ничего переделывать не нужно - эти преобразования совпадают.

[Yuri Gendelman]

Посмотрите вот этот препринт :
"A short introduction to the Radon and Hough transforms and how they relate to each other".

Один из вариантов ответа на вопрос об их сравнении: преобразование Хафа - это дискретизация преобразования Радона. Как я заметил, в литературе по томографии используют только ПР, а при обработке изображений - почти всегда ПХ.

Кроме того, в литературе по интегральной геометрии рассматривается и ПР размерности выше 2-й (интегралы по гиперповерхностям коразмерности 1).

[CyberCraft]

В целом понятно. Спасибо большое.
А как насчет применимости этих или других методов в даной задаче?
Какой метод посоветуете?

[Yuri Gendelman]

CyberCraft писал(а):

А как насчет применимости этих или других методов в даной задаче? Какой метод посоветуете?

Мой опыт применения пр.Хафа не был особенно успешным. Мне нужно было по полученному томографическому разрезу детали восстановить чертеж, своего рода mechanical reverse engineering. Но чертеж получался слишком неточным, и пользователю приходилось его править вручную в CAD. Наши менеджеры решили, что расходы на доведение этого модуля до автомата не окупятся. Все это было несколько лет назад, так что я уже не в теме.

В общем, ищите специалистов по наведению низколетящих крылатых ракет.

[CyberCraft]

Yuri Gendelman писал(а):

В общем, ищите специалистов по наведению низколетящих крылатых ракет.

Моя задача более простая и мирная. При наведении ракеты на объект таким визуальным способом имеют место афиные искажения(3D проекции), топологическая неточность(наличие новых деталей), искажения оптической системы (рыбий глаз, перспектива) и т.д.

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

[G^a]

CyberCraft писал(а):

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

А попробуйте поискать статьи по корреляционно-экстремальным методам работающим в пространстве коэффициентов некоторых базисных функций.

[CyberCraft]

G^a писал(а):

А попробуйте поискать статьи по корреляционно-экстремальным методам работающим в пространстве коэффициентов некоторых базисных функций.

К сожалению, погуглил не густо. Может быть, есть ссылки на описание метода?