Комментарии 24
Верно ли, что ваш алгоритм вычисляет взаимнокорреляционную последовательность? И поэтому, по теореме о свёртке, такую взаимную корреляцию можно вычислять с помощью преобразования Фурье?
Да алгоритм как промежуточный результат для вычисления PT это использует, вычисление TT тоже имеет свое математическое название хоть и является частным случаем первого.
Но вместо известных математических определений подразумевающих выводы из индукции, и последующего дедуктивного применения я остановился в изложении только на первом, для того чтоб показать значения смещений и длин искомых массивов.
Но вместо известных математических определений подразумевающих выводы из индукции, и последующего дедуктивного применения я остановился в изложении только на первом, для того чтоб показать значения смещений и длин искомых массивов.
Если вы обратите внимание, то в определении свертки и взаимной корреляционной последовательности есть различие, в интегральной форме смещение незаметно так как пределы интегрирования бесконечны, но для понимания алгоритма нахождения искомой суммы определение свертки менее подходящее. Потому я тоже избегал упоминания теоремы о свертке так как это требует пусть не значительной но замены переменных и дополнительных преобразований.
Если вы обратите внимание, то в определении свертки и взаимной корреляционной последовательности есть различиеЕдинственное различие между свёрткой и корреляцией — это знак функции времени второго аргумента, а так они вполне однозначно выражаются через друг друга.
в интегральной форме смещение незаметно так как пределы интегрирования бесконечныЭто очень спорное утверждение, сможете его подтвердить реальным примером, или я что-то не так понял? Потому что смещение во времени — это просто линейный наклон фаз вне зависимости от того, дискретное или непрерывное преобразование используется.
сможете его подтвердить реальным примером,
разумеется:
— использование инверсии и взаимнокорреляционной функции приводят началу последовательности PT с позиции m
— использование свертки и сопряжения, приводят началу последовательности PT с позиции 1
Такое смещение в точности соответствует преобразованию для изменения «знака функции времени второго аргумента».
В комментарии, на который вы сослались, я не увидел ответа на свой вопрос. Бесконечные пределы интегрирования предполагают аналитическое решение с привлечением аналитических же функций типа такой.
В DFT интегрирования нет вообще, наиболее простое его определение связано со значением полинома в точке, приводящему при подстановке к подобию части ряда Фурье. Соответственно и имеет все свойства этого преобразования, доказательство обычно проводят индукцией, но все же отличие DFT и ряда есть, первое это точное преобразование.
Теперь про интегрирование(приведу без комплексного варианта),
— в сверточном определении f(x)g(y-x)dx
— для взаимнокорреляционной функции f(x+y)g(x)dx
переход от одного к другому это замена переменных
x=x+y — вот откуда смещение.
Если вы будете искать t[i+j]p[j] в произведении полиномов
A×B=InvDFT(DFT(A)×DFT(B))
то получите начальную позицию m.
Я использую именно свойство DFT так как оно определено аналитически точно, но в пределах машинной точности вычислений.
Тогда как для использования теоремы о свертке мне придется сделать логический переход от бесконечных сумм в преобразованиях Фурье к конечным, сделать замену переменных, и обосновать исходя из редукции размеры используемых массивов.
Дополнительные действия есть как при использовании DFT, так и при FT, но для первого их меньше. В названии статьи приведено DFT и именно его свойствами я и пользовался в создании алгоритма, хотя можно использовать и свойства FT
Теперь про интегрирование(приведу без комплексного варианта),
— в сверточном определении f(x)g(y-x)dx
— для взаимнокорреляционной функции f(x+y)g(x)dx
переход от одного к другому это замена переменных
x=x+y — вот откуда смещение.
Если вы будете искать t[i+j]p[j] в произведении полиномов
A×B=InvDFT(DFT(A)×DFT(B))
то получите начальную позицию m.
Я использую именно свойство DFT так как оно определено аналитически точно, но в пределах машинной точности вычислений.
Тогда как для использования теоремы о свертке мне придется сделать логический переход от бесконечных сумм в преобразованиях Фурье к конечным, сделать замену переменных, и обосновать исходя из редукции размеры используемых массивов.
Дополнительные действия есть как при использовании DFT, так и при FT, но для первого их меньше. В названии статьи приведено DFT и именно его свойствами я и пользовался в создании алгоритма, хотя можно использовать и свойства FT
Что-то я не пойму, о чём спор. Есть же дискретный вариант теоремы о свёртке, там всё прекрасно выражается через ДПФ. А знак времени для одной из функций (то, чем различается свёртка от автокорреляции) — это уже мелочи.
Спор о выборе теории для иллюстрации действия алгоритма. Автокорреляция это еще один термин который от темы уводит дальше чем свертка.
Дело в разных размерах массивов, на практике можно получить нужную последовательность несколькими способами, но они отличаются разными способами подготовки массивов и позициями в них. Что говорить на остаток и саму позицию здесь и разбираем.
В лекциях и статьях уделяют внимание больше самой последовательности а остальное или чем то обозначают или просто оставляют как несущественное, иногда наговаривают и наукообразие.
К той же близкой по виду взаимнокорреляционной функции уже есть вопросы, инверсия порядка и отрицательное время похожи вот только для ряда нет отрицательных индексов, или значения нужно дополнительно определять, или иметь константу обеспечивающую положительность разницы, или и то и другое. На все эти вопросы более просто отвечает DTF.
В лекциях и статьях уделяют внимание больше самой последовательности а остальное или чем то обозначают или просто оставляют как несущественное, иногда наговаривают и наукообразие.
К той же близкой по виду взаимнокорреляционной функции уже есть вопросы, инверсия порядка и отрицательное время похожи вот только для ряда нет отрицательных индексов, или значения нужно дополнительно определять, или иметь константу обеспечивающую положительность разницы, или и то и другое. На все эти вопросы более просто отвечает DTF.
Этот метод легко обобщается до 2+ измерений, просто решили не тратить место в статье?
Существует еще такая вариация, как БПФ на кольцах по модулю простых чисел, она точная. (Хотя, вариант с плавающей точкой зачастую все равно выигрывает по времени, проигрывая по используемой памяти).
Относительно утверждения про легко, я сомневаюсь, и именно поиску изображения в изображении планирую создать еще одну публикацию. Насколько видно из [1] там автор с легкостью то и не справился, забыв указать про инверсию массива образца, оставив только не существенное комплексное сопряжение которое к стати в приведенном одномерном алгоритме исключено. Как и используется другая функция для определения позиции образца.
Еще актуально? Мне как-то когда я был в лучшем состоянии, хватило меньше часа, чтобы написать 2-х мерный вариант по практическим таким же формулам.
Не понимаю, зачем тут привлекать тождество свертки и перемножением полиномов в точках единичной комплексной окружности. Может эта аналогия и препятствует обощению на 2 измерения.
Для целочисленного вычисления сверки по вместо длинной арифметики есть еще такой вариант, как сделать операцию по модулю нескольких различных простых, а потом использовать как-то вернуть обратно (https://scask.ru/g_book_s_alg.php?id=20)
Да актуально, но приведенная статья посвящена больше внутренней работе функций преобразования, я сразу перешел к следующей главе, но и там не заметил упоминания или построения функции сравнения.
«Существует еще такая вариация, как БПФ на кольцах по модулю простых чисел, она точная.» аналитически может и точная, но при использовании численного расчета на действительный числах обойти минимум машинную точность вычисления не получится. Поэтому пишу про приближение и возможный диапазон яркостей.
Если использовать сопряжение и прямой порядок, тогда нумерация PT начинается с первой позиции, длинна же как и в публикации будет n-m+1
(*PT*)
PolyT = {1, 2, 3, 4, 5}; LT = Length[PolyT];
PolyP = {3, 2, 1}; LP = Length[PolyP];
PolyR = {}; LR = LT + LP - 1;
eT = Table[If[i > LT, 0, PolyT[[i]]], {i, 1, LR}]
eP = Table[If[i > LP, 0, PolyP[[i]]], {i, 1, LR}]
PolyR = InverseFourier[
Fourier[eT, FourierParameters -> {1, 1}]*
Conjugate[Fourier[eP, FourierParameters -> {1, 1}]]
, FourierParameters -> {1, 1}]Результат:
{1, 2, 3, 4, 5, 0, 0}
{3, 2, 1, 0, 0, 0, 0}
{10., 16., 22., 22., 15., 1., 4.}Причина в разнице начальной позиции в использовании различных функций в определении. При теории основанной на свойствах полиномов необходима инверсия, тогда как использование теоремы о свертке подразумевает дополнительную замену переменных, которая и приводит к величине изменения позиции.
В публикации использовал часть теории связанной с полиномами так как опираясь на них строят функцию для определения позиции образца. Плюс удобно показать получаемые размеры, что может быть важно при оптимизации. При использовании свертки последнее получить сложнее.
Вот как выглядит попытка объяснения различий для варианта свертки, в действительности же сдвиги относятся к свойству преобразования, а не к свойствам самого изображения.
Именно из-за таких мелочей которые будучи смешаны в кучу дают «абракадабру» я и написал статью.
В публикации использовал часть теории связанной с полиномами так как опираясь на них строят функцию для определения позиции образца. Плюс удобно показать получаемые размеры, что может быть важно при оптимизации. При использовании свертки последнее получить сложнее.
Вот как выглядит попытка объяснения различий для варианта свертки, в действительности же сдвиги относятся к свойству преобразования, а не к свойствам самого изображения.
При использовании дискретного преобразования Фурье, матрица M содержит также элементы от циклического сдвига изображений между собой. Поэтому, если не требуется анализировать циклический сдвиг кадров, то поиск максимального элемента в матрице M нужно ограничить областью (0,0)-(N1-M1, N2-M2).
Именно из-за таких мелочей которые будучи смешаны в кучу дают «абракадабру» я и написал статью.
Если у вас под рукой есть ссылка на теорию по построению функции сравнения для варианта 2D напишите ее пожалуйста. Вариант TT-2PT очевиден именно для одномерного случая, тогда как для двумерного случая уже не понятно, ведется суммирование по строке или столбцу, а если и то и другое то как это соотносится с точечной разницей яркости.
В своей практике я в основном работал с рядами и интегралами Фурье, они удобны при подстановке в дифференциальные уравнения тем что превращают их в систему линейных уравнений, потому ожидал что обрезка ряда по частотам приведет к некоторым ошибкам которые можно будет уточнить другим способом.
Однако как оказалось несмотря на близость названий, DFT имеет другой набор свойств хотя и совместим со свойствами обычного преобразования. Само определение DFT для полинома это его значение в точке x=Exp(2*i*Pi/n), — точное, как и формула преобразования, которая вроде похожа на сверточную версию но все же без сопряжения. Соответственно не имеет ошибки связанной с конечностью ряда, а содержит только ошибку связанную точностью машинного вычисления. Которую, как вы упомянули, возможно устранить при сведении вычислений к целочисленным преобразованиям.
Мне лично это все было новым, без практики про DFT из университетского курса оказывается совершенно забыл. Потому и проверял величину расхождения, хотя так же потому что мои попытки использовать функцию сравнения из некоторых статей давали просто неприемлемые величины ошибок.
В итоге как оказалось вроде бы очевидное и легкое дополнение для каждой лекции и статьи которые просматривал, в реализации дюжины строчек кода, показали страшную ретивость и потребовали уйму времени для их отладки и согласования.
Однако как оказалось несмотря на близость названий, DFT имеет другой набор свойств хотя и совместим со свойствами обычного преобразования. Само определение DFT для полинома это его значение в точке x=Exp(2*i*Pi/n), — точное, как и формула преобразования, которая вроде похожа на сверточную версию но все же без сопряжения. Соответственно не имеет ошибки связанной с конечностью ряда, а содержит только ошибку связанную точностью машинного вычисления. Которую, как вы упомянули, возможно устранить при сведении вычислений к целочисленным преобразованиям.
Мне лично это все было новым, без практики про DFT из университетского курса оказывается совершенно забыл. Потому и проверял величину расхождения, хотя так же потому что мои попытки использовать функцию сравнения из некоторых статей давали просто неприемлемые величины ошибок.
В итоге как оказалось вроде бы очевидное и легкое дополнение для каждой лекции и статьи которые просматривал, в реализации дюжины строчек кода, показали страшную ретивость и потребовали уйму времени для их отладки и согласования.
Не понял что с чем сравниваете, точнее что ищите?
Спасибо за замечание, тоже думаю внести правку в статью, так как это написано только в коде. Ищется отрезок длинной W/8 с началом в точке W/4 на линии рисунка с вертикальной координатой H/2.
где W-ширина (width), H-высота(height) рисунка в пикселях.
где W-ширина (width), H-высота(height) рисунка в пикселях.
...
y = IntegerPart[H/2]; (*Pattern width and coordinates*)
x = IntegerPart[W/4];
w = IntegerPart[W/8];Задача которая привела к написанию статьи была связана с нахождением величины смещения двух изображений, меня не устроила скорость «наивной» реализации. Потому такой развлекательный вариант исходного массива.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Одномерный поиск образца с использованием дискретного преобразования Фурье