Каждый день каждый человек своими глазами видит как всё вокруг происходит. От этого выработалась не только знание как всё будет дальше, но и её подтверждённая часть — интуиция. Но у такой интуиции, которая по происхождению основана на прошлом есть один явный недостаток — она основана именно на прошлом опыте, к новым открытиям она не готова. Это явно выражается, например, в том с каким отношением к квантовой механике рассказывали те кто её открывал. «Мы творим лютую дичь» — говорили они. А что такого в том чтобы так говорить? Несоответствие интуиции есть, и никто пока до конца не разобрался. Студенты: «Так и запишем, «Мы творим лютую дичь. И разбираться не нужно»» (фейспалм). И до сих пор иногда это проскакивает в виде слова «заткнись» в описаниях — во вполне академических. И исчезать не торопится. Что ж, не все прежде чем делать открытия учились тому как надо делать открытия. Но если придумать новую интуицию, всё было бы гораздо, гораздо симпатичней.



«Чёткость» и «Плавность» — два раздела статьи.

Чёткость


Начну с абстрактной задачи.

Представьте, что сотрудников вашего института вывели на улицу и построили в линейку. И раздали всем наборы конфет. Скажем, в наборе круглое число, 1024 конфеты, делить пополам можно аж десять раз. Но количество наборов меньше, чем количество человек и поэтому наборы достались не всем. Количество конфет очень важно на поляне чаепития, поэтому вы даёте команду: каждому, половину того что есть — отдать соседу слева. Распределение немного размылось.

И вот такой интересный вопрос: можно ли сформировать такую следующую команду по раздаче, чтобы обратить предыдущую команду, то есть, чтобы наоборот, собрать? Можно ли достичь чёткости через «размытие»? Оказывается, можно. Только, придется величину раздачи допустить отрицательной и оперировать на любом расстоянии, а не только обмениваться с соседями.


Влево надо раздавать чередуя минус и плюс. Себе оставить долю. И вправо чередуя плюс и минус. Например, если всего пять человек, то схема обмена будет такой:

$\begin{matrix} + & + & - & + & -\\ - & + & + & - & +\\ + & - & + & + & -\\ - & + & - & + & +\\ + & - & + & - & + \end{matrix}$

Строка соответствует человеку который раздаёт, колонка человеку который принимает.

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

Тут есть пара проблемок. Первая: непонятно, кому же отдаст половину самый левый. Но это решить просто, надо изначально левому не давать конфет. Хех. Ну, или пусть отнесёт самому правому, то есть, линейку можно зациклить.

А вторая проблемка: алгоритм хорошо работает для нечётного количества человек, а если число чётное, то уже нет. Ну, представьте что у вас всего два человека, после первого распределения у них всегда оказывается количество одинаковое, и какая часть от кого перешла — никак не восстановить.

И, например, для четырёх человек можно заметить, что распределение плюсов и минусов при зацикливании начинает противоречить само себе: знаки при наложении соседних циклов противоположны. Так что, остаётся только использовать алгоритм для пяти, но пятый участник будет отсутствовать: то есть, ни раздавать конфеты, ни получать.

Надеюсь, бесконечность не является чётной? А то, в этом случае обобщить на линейку с бесконечным количеством элементов может и не получиться. Думаю, надо обязательно, чтобы этот сотрудник, попавший на линейку на бесконечное место, гарантированно не участвовал в обмене. И все его соседи тоже. А может, бесконечность тем и отличается, что можно рассчитывать на тот вариант, который получше? Тогда — пожалуйста, пусть она будет нечётная. Тогда в обмене будут участвовать все.

Это важный момент — один лишний отсчёт и точное восстановление в общем виде не работает, появляюся варианты.

(* Вставить иллюстрацию, промт: одинокий сотрудник стоит на «бесконечном месте», никаких конфет, темно.)

Свёртка


При переходе с шутливых аналогий на математическое описание надо рассказать о понятии свёртка. Это именно то что происходило при команде поделиться конфетами. Сама операция свёртки — это операция над двумя функциями, которая даёт третью, в которой каждое из значений первой линейно перераспределено по схеме из второй.

Например, эхо. Это же свёртка функции того что вы крикнули и схемы повторения. Или, например, если в небе происходит солнечное затмение, то тень становится покрытой множеством маленьких солнечных месяцев. Результат здесь — это свёртка того что видно в небе и схемы расположения отверстий в преграде для света.



Математически это выражается так:

$[f * g]_n=\sum_{k=-\infty}^{\infty} f_k\cdot g_{(n-k)}= \sum_{k=-\infty}^{\infty} f_{(n-k)}\cdot g_k$

$[f * g](x)=\int\limits_{-\infty}^{\infty} f(v)\cdot g(x-v) \,dv= \int\limits_{-\infty}^{\infty} f(x-v)\cdot g(v) \,dv$

Функции входят в эту формулу наравне, и порядок не важен. Но при вычислении есть разделение, одна функция под интегралом зависит только от переменной интегрирования, и значит, представляет собой множитель для заданного сдвига, а у второй функции аргумент сдвинут, она показывает, как именно будет выглядеть сдвинутая функция, к которой применяется этот множитель.

Или можно применить нечто среднее:

$[f*g](x)=\frac{1}{2}\int\limits_{-\infty}^{\infty}\,f\left(\frac{x+v}{2}\right)\cdot g\left(\frac{x-v}{2}\right)\,dv $

Для суммы тоже есть подобная формула. Только, там нужно чтобы чётность у переменных совпадала и множитель не появляется.

Самое характерное свойство у свёртки это линейность, оно выражается в том что если взять две функции, каждую свернуть с третьей и потом результаты сложить, то это будет то же самое как если бы функции сначала были сложены, а потом была произведена свёртка. То есть, не важно когда складывать, до свёртки или после.

К этому моменту у нас кроме начального распределения есть пара функций: функция размытия и функция возвращения резкости. Свёртка со второй — обращает свёртку с первой.

Множество шагов размытия


Размывающее распределение «отдай соседу половину» можно повторять много раз. Раздачу лучше чередовать влево и вправо, тогда после каждой такой пары начальный элемент будет оставаться в центре распределения. Ситуацию можно рассмотреть только с одним установленным вначале элементом, остальные варианты получаются свёрткой. Посмотрим на формулу для расчёта значений, которые получаются сразу на выбранном шаге.

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

Следующий, второй соседний элемент, точно так же последовательно суммирует предыдущие суммы. И дополнительно нужно учесть, что в цепочке суммирования последнее слагаемое будет на единицу меньше, чем номер шага, поэтому формула второго элемента будет $n(n-1)/2$, с минусом перед единицей.

Чтобы получить третий элемент нужно умножить второй на $(n-2)/3$. Просматривается общая формула:

$a_0=1 \qquad a_{k}=a_{k-1}\cdot \frac{(n-(k-1))}{k} \qquad \\\Downarrow \\a_{\{\}}=\left\{ 1,\quad \frac{n}{1},\quad \frac{n(n-1)}{1\cdot 2},\quad \frac{n(n-1)(n-2)}{1\cdot2\cdot3},\quad \ldots \quad , \frac{n\cdot\ldots\cdot 1}{1\cdot\ldots\cdot n}=1,0,\ldots\right\} \\\Downarrow \\ a_k=\frac{n!/(n-k)!}{k!}=\frac{n!}{k!(n-k)!}=C_n^k=\binom{n}{k}\qquad C_{k+v}^k=\frac{(k+v)!}{k!v!}$

Для вычисления используются биномиальные коэффициенты, для их вычисления используются факториалы.

Теперь останется отменить умножение на два на каждом шаге — поделить на двойку в степени номера шага — и значение результата размытия будет получено. Расчёт в случае отсчёта позиции от крайнего элемента:

$L(k,n)=\frac{C_{n}^{k}}{2^{n}} $

На иллюстрации видно, что после десяти шагов распределение одного набора представляет собой холмик.


И вот тут такой вопрос — при увеличении шагов этот холмик расширяется или сужается? С одной стороны размытие это расширение в разные стороны. С другой стороны, взгляните график распределения распределения после 200 шагов.


Относительно всей области размытия холмик выглядит как узенький всплеск посередине, относительно всей широты фигура с каждым шагом только сужается.

Если на масштабе одного элемента распределение расширяется, а на масштабе всей области распределение сужается, то сохраняется фигура холмика с увеличением шагов только на среднем масштабе. Ориентировочные размеры — это корень из количества шагов. Или, наоборот, количество шагов соразмерно квадрату от количества делений для выбранной ширины.

При увеличении шагов до бесконечности на среднем масштабе распределение приближается к функции Гаусса. Вы встречали в фотошопе «размытие по Гауссу»? Это многократно повторяющееся размытие на один пиксел, которое приводит к замутнению картинки. Если не брать во внимание сдвиг от центра и всевозможные коэффициенты для аргумента и для значения, формула гауссианы будет такой:

$g_0(x)=e^{-x^2}$

Для установления взаимосвязи с пошаговым размытием нужно вывести коэффициенты.

Пусть у среднего элемента индекс $n^2$. У крайнего элемента тогда будет индекс $2n^2$. Отслеживать масштаб будем по элементу $n$ от центра, с индексом $n^2+n$. Отношение его значения и значения среднего элемента при увеличении $n$ будет стремиться к некоторому числу, выразим его.

$ L_1=L(n^2+n,2n^2)={C_{2n^2}^{\,n^2+n}/2^{2n^2}}={(2n^2)!}\;/\;{{2^{2n^2}}(n^2+n)!(n^2-n)!} \\L_0=L(n^2,2n^2)={C_{2n^2}^{\,n^2}}/{2^{2n^2}}={(2n^2)!}\;/\;{{2^{2n^2}}(n^2!)^2} $

$K_n=L_1/L_0=\frac{(2n^2)!}{{2^{2n^2}}(n^2+n)!(n^2-n)!} / \frac{(2n^2)!}{{2^{2n^2}}(n^2!)^2}=\frac{(n^2!)^2}{(n^2-n)!(n^2+n)!} $

$ K_{\{\}}=\left\{ 1 ,\;\frac{1}{2} ,\;\frac{3\cdot4}{5\cdot6} ,\;\frac{7\cdot8\cdot9}{10\cdot11\cdot12} ,\;\frac{13\cdot14\cdot15\cdot16}{17\cdot18\cdot19\cdot20} ,\;\frac{21\cdot22\cdot23\cdot24\cdot25}{26\cdot27\cdot28\cdot29\cdot30} ,\;\ldots \right\}$

${K_n=\prod_{k=1}^{n}\frac{n^2+k-n}{n^2+k} =\exp \sum_{k=1}^{n}\ln\left(1-\frac{1}{n+\frac{k}{n}}\right) }$

$ \lim_{n\to\infty}\sum_{k=1}^{n}\ln\left({1-\frac{1}{n+\frac{k}{n}}}\right)= -1 \qquad K_\infty=\frac{1}{e}$

Получилось, что коэффициента перед $x$ не нужно, отслеживаемая точка среднего масштаба $e^{-x^2}$ расположена при $x=1$.

Дальше считаем интеграл функции, чтобы нормировать до единицы, как у первоначального элемента. Производная от $e^{-x^2}$ равна $-2xe^{-x^2}$, это позволяет проинтегрировать это выражение обратно.

$I^2=\int\limits_{-\infty}^{\infty}\int\limits_{-\infty}^{\infty} e^{-(x^2+y^2)}\,dx\,dy=\int\limits_{0}^{\infty}\int\limits_{-\pi r}^{\pi r}e^{-r^2}\,d\varphi\,dr =\int\limits_{0}^{\infty}2\pi re^{-r^2}\,dr=\pi \qquad I=\sqrt{\pi}$

Это расчёт происходит так. Интеграл гауссианы в двух размерностях преобразован в другой интеграл, немного по другим размерностям. По одной размерности это интеграл на пол диапазона, по другой размерности на один оборот круга — так как координаты на плоскости можно представлять в виде вектора, имеющего длину и угол. Угол для интеграла угла должен выражаться с коррекцией на то что по метрике это должно быть пройденным путём, то есть, угол будет умноженным на радиус. При взятии интеграла пределы превращаются в константу диапазона кружения, умноженную на радиус. Этот радиус для интеграла по радиусу играет роль множителя уже взятой производной, который позволяет взять интеграл, оставляя только константу диапазона кружения. После этого осталось учесть, что мы считали квадрат величины.

Нормированная гауссиана

$g_n(x)=\frac{e^{-x^2}}{\sqrt{\pi}}$

Есть ещё вариант нормировки, когда и интеграл единичный и значение в нуле единица.

$g_\pi(x)=e^{-\pi x^2} $

Интеграл можно оставить единичным, применяя любой коэффициент сжатия по аргументу при увеличении по значению:

$g_\pi(x,k)=k e^{-\pi (kx)^2} \qquad g_h(x,h)=\frac{e^{-\frac{x^2}{h}}}{\sqrt{h\pi}} $

Не смотря на то что количество шагов размытия бесконечное, мы можем представить как будет выглядеть в зафиксированном масштабе размытие с другим, пропорциональным количеством шагов.

$g_k(x,k)=\sqrt{\frac{k}{\pi}}e^{-{x^2k}}$

Ширина холма пропорциональна корню из количества шагов. А, ну да, я же и исходил из этого предположения.

Теперь можно задаться вопросом, как в таком же пределе выглядит отрицательное количество шагов размытия.

Множество шагов наведения резкости


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


Диаграмма применения второго шага наведения резкости по принципу первой диаграммы (из плюсов и минусов), но уже с применённым изменением знака, в соответствии с множителем внутри свёртки. Светлым обозначен плюс, тёмным минус. Описать расстановку можно так: знак зависит от чётности места получателя, и у тех мест что ниже диагонали знак изменён на противоположный. Суммирование по колонкам приводит к распределению: одно из значений равно количеству элементов в линейке, и отдаляющиеся от неё в обе стороны — уменьшаются по абсолютной величине на два, и ещё меняют знак, сходясь до минус единиц на двух противоположных ему в цикле элементах.


При дальнейшем наведении резкости знак в расстановке так и продолжит чередоваться. Эту постоянную смену знака можно исключить из внимания, оставив только положительные значения на каждом шаге. Меняем знак у колонок с нечётным индексом на противоположный. Тогда, на этом же примере, можно подсчитать, что суммы по колонкам будут от -9 до 11 с шагом 2. Но все числа распределения теперь же уже положительные, что делать с отрицательными? В получившуюся функцию отрицательные числа не попадают, потому что с каждым шагом схема чередования знака сдвигается — и для мест, где знак отрицательный он при этом меняется.

Если количество шагов размытия превысит количество элементов, то конечно, значения, разошедшиеся в разные стороны, снова сойдутся и произойдёт наложение. Для вычисления соответствующего наведения резкости это дополнительно усложнило бы распределение. Но восстанавливающие значения расстановки для этого случая всё равно существуют и работают.

На одиннадцати элементах третий шаг наведения резкости приводит к таким значениям:

$\{1,3,5,7,9,11,9,7,5,3,1\}\to\{11,29,43,53,59,61,59,53,43,29,11\} $

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

При рассмотрении размытия был интересен масштаб для стабилизации холмика. Здесь же значения занимают всю линейку, какой бы она ни была, и уже на третьем шаге нет ни одного значения меньше, чем количество элементов. Никаких холмиков здесь не наблюдается. Тогда, какие же здесь закономерности? Ну, кроме уже принятого во внимание чередования знака.

Первый шаг наведения резкости выражается просто.

$ R^{[1]}_k(n)=1 $

На втором шаге расстановка это нечто вроде модуля числа, только с ограничением и снизу, и сверху. Поэтому стоит немного поменять отсчёт индекса. Нулевой $n$ будет означать место максимума.

$R^{[2]}_k\left(n+\frac{k-1}{2}\right)=k-2|n| $

Для $k=11$ значение $R^{[2]}_{11}=\{1,3,5,7,9,11,9,7,5,3,1\}$. Сумма в общем виде получилась равной $\frac{k^2+1}{2}$.

На третьем шаге форма распределения парабола.

$R^{[3]}_k\left(n+\frac{k-1}{2}\right) = \frac{k^2+1-4n^2}{2}$

Значение $R^{[3]}_{11}=\{11,29,43,53,59,61,59,53,43,29,11\}$. Сумма в общем виде $\frac{k^3+2k}{3}$.

Для перехода на следующий шаг нужно из выражения для предыдущего уровня вывести выражение суммы диапазона элементов. Так как зависимость значений от $n$ это зависимость от $|n|$, то сумму можно подсчитать только в одну сторону на половину всех элементов, умножить на два, и от суммы отнять максимум прошлого уровня, потому что он попал туда два раза.

$ R^{[4]}_k\left(n+\frac{k-1}{2}\right)=2\sum_{} R^{[3]}_k - c^{[3]}_k= {\small \sum_{v=0}^{(k-1)/2-|n|} \left[k^2+1-4v^2 \right]-\frac{k^2+1}{2}=} \\{\small= \left(k^2+1\right)\left(1+\frac{k-1}{2}-|n|\right) -4 \frac{ \left(\frac{k-1}{2}-|n|\right) \left(\frac{k-1}{2}-|n|+1/2\right) \left(\frac{k-1}{2}-|n|+1\right) }{3}-\frac{k^2+1}{2} =}\\=\frac{k^3 + 2 k - 4 |n| - 6 k |n|^2 + 4 |n|^3}{3} $

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


Пятый шаг:

$ R^{[5]}_k{}\left(n+\frac{k-1}{2}\right)=\frac{5 k^4 + 10 k^2 - 24 k^2 n^2 - 40 n^2 + 16 n^4 + 9}{24} $

При расчёте каждый шаг как будто состоит из двух этапов, суммирование степеней $v$ до предела $\frac{k-1}{2}-|n|$, и перевод $n$ в $v$. В верхнем пределе расчёта суммы есть разворот $(\text{константа})-n$, то есть, верхний предел суммы и переменная различаются. И это для меня похоже на дополнительное усложнение. Поэтому стоит попробовать рассмотреть расстановку в другой системе отсчёта — от другого из двух «центров» замкнутой линейки.

Переориентируем систему отсчёта так:

$ x+n=k/2$

$ R^{[l]}_k\left(-n+\frac{k-1}{2}\right)=\left|R^{[l]}_k\left(x-1/2\right)\right| $

Для чётных и нечётных шагов соответствие немного различается:

$\small n\in \left[0;\frac{k-1}{2}\right] \qquad (l/2 \in \mathbb{N}) \Rightarrow x\in \left[-\frac{k}{2};\frac{k}{2}\right] \qquad (l/2+1/2 \in \mathbb{N}) \Rightarrow x\in \left[\frac{1}{2};k-\frac{1}{2}\right] $

Получится:

$R^{[1]}_k\left(x-1/2\right)=1 \\ R^{[2]}_k\left(x-1/2\right)=|2x| \\ R^{[3]}_k\left(x-\frac{1}{2}\right) = 2 x (k - x)+\frac{1}{2} \\ R^{[4]}_k\left(x-\frac{1}{2}\right) = \left|\frac{x (3 k^2 - 4 x^2 + 4)}{3}\right| \\ R^{[5]}_k\left(x-\frac{1}{2}\right) =\frac{x(k-x)(2 (k^2-x^2+k x)+ 5)}{3}-\frac{1}{8}+\frac{1}{2} $

Интересно, что выдаваемые значения всегда нечётные.


Ну что, пятый шаг выполнен, бесконечность — уже совсем близко.

Можно подумать, что график распределения это косинус, но он может совпадать с ним только в пределе. При ограниченном количестве шагов всегда есть очень важное, даже принципиальное отличие.

Немного усилий
Будем использовать формулу для суммы.

$S^{b}_{n}=1^b+\ldots+n^b={1\over b+1}\sum_{j=0}^{b} B_j C_{b+1}^j (n+1)^{b+1-j } $

$(B_j$ — это числа Бернулли)

И обычный бином Ньютона.

$(a+b)^k=\sum_{y=0}^{k}C_k^y a^{k-y}b^y $

Представим распределение в виде суммы.

$R^{[l]}_k\left(-n+\frac{k-1}{2}\right)=\sum_{b} N_l^{[b]}n^b$

Дальше надо выписать как преобразуется $n^b$. Суммирование:

$\sum_{v=0}^{\left(\frac{k-1}{2}-n\right)} v^b=S^b_{\left(\frac{k-1}{2}-n\right)}={1\over b+1}\sum_{j=0}^{b} B_j\cdot C_{b+1}^j\cdot \left(\frac{k+1}{2}-n\right)^{b+1-j }=$

$={1\over b+1}\sum_{j=0}^{b} \sum_{y=0}^{b+1-j} B_j\cdot C_{b+1}^j \cdot C_{b+1-j}^{y} \left(\frac{k+1}{2}\right)^{b+1-j-y}(-n)^y $

$ C_{b+1}^j \cdot C_{b+1-j}^{y}=\frac{(b+1)!}{j!(b+1-j)!}\cdot\frac{(b+1-j)!}{y!(b+1-j-y)!}= \frac{(b+1)!}{y!j!(b+1-j-y)!} $

Чтобы получить коэффициент для $n$ в нужной степени нужно рассчитать значение вклада при выбранном $y$:

$\small N_{l+1}^{[y]}=2\sum_{b=0}^{l-1}\left[\frac{N_l^{[b]}}{b+1}\sum_{j=0}^{b+1-y-\delta_y} B_j\frac{ (b+1)!}{y!j!(b+1-j-y)!} \left(\frac{k+1}{2}\right)^{b+1-j-y}(-1)^y\right] -\delta_y N_l^{[0]} $



Получилась вот такая общая формула:

$N_{l+1}^{[y]}=(-1)^y\sum_{b=0}^{l-1} 2\left(1-\frac{\delta_{by}}{k+1}\right)N_l^{[b]}\frac{b!}{y!}\sum_{j=0}^{b+1-y-\delta_y} \frac{\quad B_j\,\cdot \left(\frac{k+1}{2}\right)^{b+1-j-y}}{j!(b+1-j-y)!\quad}$

Всё же, чуть сложнее косинуса. Это выражение через $n$. А теперь это всё хотелось бы выразить через $x$.

Но зачем заходить так далеко?
Можно просто просуммировать коэффициенты, используя закономерность.

$x^b=(k/2-n)^b=\sum_{v=0}^b(-1)^vC^v_b {(k/2)^{b-v}n^v}$

Эта закономерность симметрична, $x$ и $n$ можно поменять между собой.

Для коэффициентов пересчёт будет таким:

$ \sum_{j=0}^{b}X^{[j]}x^j=\sum_{v=0}^{b}N^{[v]}\sum_{j=0}^b(-1)^j C^j_v {(k/2)^{v-j}x^j}\Rightarrow X^{[j]}=\sum_{v=j}^{b}(-1)^jC^j_v {(k/2)^{v-j}N^{[v]}} $

С этими координатами нужно обратить внимание вот на что. Координаты выбраны так чтобы максимум у распределения в линейке находился в середине, при $n=0$, а место смены чередования знака лежало при $x=0$. Но каждый раз при расчёте свёртки максимум сдвигается на половину линейки. И значит, что при расчёте расстановки чередуются и действительные координаты — это то $x$, то $n$. Для такой стабилизации надо чередовать направления сдвигов размытия. Максимум распределения при отсутствии компенсации чередования знака будет то положительным максимумом то отрицательным минимумом. Ещё, чтобы получить расстановку кроме возвращения правильного знака нужно, как и в формуле для размытия, поделить на 2 в степени номера шага.

Ещё одна заметка
На основе того, что преобразования координат туда и обратно не меняет значения, можно обнаружить, что сумма по определёной выборке равна нулю:

$n^b=\sum_{v=0}^b(-1)^vC^v_b (k/2)^{b-v}\sum_{j=0}^{v}(-1)^j C^j_v (k/2)^{v-j}n^j$

$ \sum_{v=0}^b\sum_{j=0}^{v-\delta_{(v-b)}}(-1)^{v+j}\frac{b!}{j!}C^{v-j}_{b-j} (k/2)^{b-j} n^j = 0 $

Объяснить это можно так: $\sum_{k=0}^n (-1)^k C_n^k = \delta_n$ — если у биномиальных коэффициентов при суммировании чередовать знак, то в сумме получится ноль. Коэффициенты получены размытием, и теперь его части компенсируют друг друга. А если коэффициент только один, то результат станет единицей, потому что размытия в этом случае не было.



Этого для поверхностного представления того как выглядит изнанка размытия хватит.

Объединяем направления


Наведение резкости можно назвать отрицательной степенью размытия. Если подставить в формулу $g_k(x,k)=\sqrt{\frac{k}{\pi}}e^{-{x^2k}}$ отрицательное число для степени размытия, то возникнет чисто мнимая функция с неопределённым знаком, которая в обе стороны только возрастает. Для мнимого значения этой функции в дискретном распределении явно просматривается соответствие с чередованием знака. Попробуем разобраться с остальным.

Между размытием и резкостью есть ещё одно общее свойство — постоянное значение они оба переводят в постоянное значение. Но если для размытия это выглядит как суммирование соседних значений и затем деление на два — что для одинаковых значений возвращает к нему же — то для резкости расчёт происходит немного по-другому.

Если мы знаем, что элемент чёткой линейки равен $a$, при том что у соответствующей размытой линейки всё заполнение константа $c$, то мы можем сказать, что соседние элементы для $a$ это $c-a$, ведь в сумме должны давать $c$. Это, в случае если мы при размытии не делим на два. Если делим, то $2c-a$. Следующие соседние элементы должны быть опять значением $a=2c-(2c-a)$. Такой расчёт происходит до тех пор пока оба потока расчёта соседей не встречаются на противоположной стороне замкнутой линейки. А там происходит такое наложение, что для равенства значений должно выполняться $a=2c-a$. Значит, $a=c$.

У линейки можно отделить общее постоянное значение, чтобы его пересчитывать на следующий шаг просто добавлением, не проводя через расчёты. При таком отделении от линейки размером $k$ только с одним установленным элементом $a$ все значения уменьшатся на $a/k$. У самого элемента значение станет $a\left(1-\frac{1}{k}\right)$.


С постоянным значением всё просто. Но кроме постоянного значения есть и другие формы распределения, которые при размытии не меняют формы.

Что будет если вы сложите две синусоиды, которые не отличаются ни амплитудой, ни частотой, а только фазой? Если фазы будут не противофазами друг другу, то результат тоже будет синусоидой, с той же частотой. Поэтому, если распределение будет гармонической функцией по частоте кратной размеру линейки, то и при размытии и при резкости она останется гармонической функцией той же частоты, поменяв только амплитуду.

В полном соответствии со школьной формулой $\small\cos(a)+\cos(b)=2\cos\left(\frac{a+b}{2}\right)\cos\left(\frac{a-b}{2}\right)$ размытие выглядит так:

$\small \cos\left(n \frac{2\pi w}{k}+u\right) + \cos\left((n+1) \frac{2\pi w}{k}+u\right) = \cos\left(\left(n+\frac{1}{2}\right) \frac{2\pi w}{k}+u\right) \cdot 2 \cos\left(\left(\frac{1}{2}\right)\frac{2\pi w}{k}\right) $

$\small \cos\left(\left(x-\frac{1}{2}\right) \frac{2\pi w}{k}+u\right) + \cos\left(\left(x+\frac{1}{2}\right) \frac{2\pi w}{k}+u\right) = \cos\left(x \frac{2\pi w}{k}+u\right) \cdot 2 \cos\left(\left(\frac{1}{2}\right) \frac{2\pi w}{k}\right) $

Здесь $w$ — частота или кратность превышения размера линейки над длиной волны, целое значение расположено в диапазоне от $0$ до $(k-1)/2$. Если ставить больше, то правый множитель в правой части переключит свой знак.

Думаю, сильно заметно, что после пары одинаковых шагов размытия центр на один отсчёт уплывает, постоянно приходится следить куда уплыл. Пора вводить третью координату, которая остаётся нулём в месте центра размытия.

Новая координата такая:

$ a = x + \frac{1}{2} = n $

В чём отличие от использования $x+n=k/2$? В равенстве $x+n=k/2$ координаты $x$ и $n$ определены на одном и том же шаге размытия, чтобы $x+1/2$ и $n$ были целыми. А здесь шаги разные. Положение центра размытия с каждым шагом чередует привязку к отсчётам расстановки: оно то попадает на элемент линейки, то находится между двумя элементами. Поэтому положение центра будет чередовать эту привязку. Для нового равенства не только $n$, но и $x$ будет целым. И ещё у $n$ исправлено направления возрастания, чтоб совпадало с $a$.

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

$\cos\left(a \frac{2\pi w}{k}+u\right)\quad \xrightarrow{\text{размытие}}\quad \cos\left(a \frac{2\pi w}{k}+u\right) \cdot \cos\left(\left(\frac{1}{2}\right)\frac{2\pi w}{k}\right) $

$ \cos\left(a \frac{2\pi w}{k}+u\right)\quad \xrightarrow{\text{резкость}}\quad \cos\left(a \frac{2\pi w}{k}+u\right) / \cos\left(\left(\frac{1}{2}\right)\frac{2\pi w}{k}\right)$

И пусть целое $a$ не всегда соответствует целому номеру элемента, теперь можно отделять не только постоянную составляющую, но и все кратные колебательные составляющие, и преобразовывать их раздельно, а потом складывать.

Тут может заинтересовать функция, которая остаётся после отделения всех гармонических составляющих.

$\Delta(a)=R_k(a)-\sum_{w=0}^{(k-1)/2} b_w\cos\left(2\pi \frac{w}{k}a+u_w\right)$

Только, если посмотреть на пространство всех вариантов, то окажется что $k$ отсчётов переходит в коэффициенты, количеством два по $((k-1)/2+1)$, это $k+1$. Здесь на один можно убавить, так как фаза для постоянной компоненты не используется. Тогда при разложении на коэффициенты пространство вариантов совпадает по размерности, поэтому остатка может и не быть.

Как отделять частотные составляющие? Чтобы рассчитать одну из них нужно просуммировать функцию, умножив на косинус заданной частоты и отдельно просуммировать, умножив на синус заданной частоты.

${\small a=n: \\c_w=\frac{1}{k}\sum_{n=-(k-1)/2}^{(k-1)/2} R(a) \cdot \cos(2 \pi a w /k) \\s_w=\frac{1}{k}\sum_{n=-(k-1)/2}^{(k-1)/2} R(a) \cdot \sin(2 \pi a w/k)} \qquad{\small \\a=x+\frac{1}{2}: \\c_w=\frac{1}{k}\sum_{x=0}^{k-1} R(a) \cdot \cos(2 \pi a w/k) \\s_w=\frac{1}{k}\sum_{x=0}^{k-1} R(a) \cdot \sin(2 \pi a w/k)} $

По соотношению может быть получена величина сдвига фазы.

$ u_w=-\arg(c_w,s_w) $

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

$ b_w=(2-\delta_w)\sqrt{c_w^2+s_w^2} $

Расстановку с одним ненулевым элементом можно собрать из гармоник, которые просто компенсируют друг друга в ноль для других позиций:

$ \delta_{n}=\frac{1}{k}\sum_{w=0}^{(k-1)/2}(2-\delta_w)\cos(2 \pi n w / k) =\frac{1}{k}\sum_{w=-(k-1)/2}^{(k-1)/2}\cos(2 \pi n w / k) $

Вариант справа использует то что для косинуса коррекция амплитуды может быть заменена расширением диапазона частот. С синусами такое тоже можно провернуть, только расширять диапазон нужно вверх, а не вниз.

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

Используя такое разложение на косинусы, вместе с полученным выше расчётом для косинуса одного шага размытия, можно вывести выражение для расчёта расстановок для любого количества шагов размытия одного элемента.

$ R^{[L]}_k(a)=\frac{1}{k}\sum_{w=-(k-1)/2}^{(k-1)/2} \cos\left(2\pi \frac{aw}{k}\right) \left(\cos\left(\pi\frac{ w}{k}\right)\right)^L $

При этом $L$ может быть отрицательным, определяя расстановку для наведённой резкости.

Какая симпатичная формула получилась, простая и ясная, мне нравится. Теперь для распределения имеется три формулы: для размытия, для резкости и общая, которая позволяет расчитать результаты для обеих.

У этого варианта есть одно дополнительное свойство. Похоже, расстановку можно так определять не только для целых, но и для действительных значений — как для позиции, так и для степени размытия.

Количество элементов $k$ можно не ограничивать, получится сумма значений бесконечности элементов. При таком суммировании есть свои особенности. В первую очередь, что все элементы могут быть околонулевыми, а их сумма будет отличаться от нуля, произвольно сильно. Поэтому между количеством элементов и их значением следует добавить коэффициент, который задаст сумме неограниченного количества элементов ограничение. Его суть — согласование двух разных масштабов.

Задаётся он через отношение суммы из таких околонулевых значений элементов, которые соответствуют единице, и количеством суммируемых элементов. Коэффициент стремится к нулю, но ему не равен. Множитель $dx$ в интеграле — это он и есть. Он переводит значение функции в значение элементов, чтобы интеграл как сумма элементов перевёл это в масштаб значения функции. Значение каждого элемента будет неотличимо от нуля, но при делении на коэффициент значение становится привычного порядка единицы.

Превратим общую формулу размытия в интеграл. Дробь $1/k$, которая тут уже есть, становится $dx$. Отношение $w/k$ становится $x$. Пределы тоже меняются соответственно, становясь плюс и минус одной второй. После этого можно не опасаться превышения количества шагов над количеством элементов, и частоты оказываются ограниченными — не по количеству, а по величине.

$ R(a,L)=\int\limits_{-1/2}^{1/2} \left(\cos\left(\pi x\right)\right)^L \cos\left(2\pi ax\right) \, dx $

О, формула ещё симпатичней. Плавнее.

Я сразу решил посмотреть, как выглядит Гауссиана, выраженная как предел бесконечности шагов размытия с сохранением масштаба.

$ \frac{e^{-a^2}}{\sqrt{\pi}}=\lim_{b\to\infty}{b\,}R(ab,2b^2) =\lim_{b\to\infty} \int\limits_{-1/2}^{1/2} \left(\cos\left(\pi x\right)\right)^{2b^2} \cos\left(2\pi abx\right)\,b \, dx $

А-ха-ха, оказывается, гауссиана в частотах это такой основательно прижатый степенью косинус! Но степенью его до нуля не дожать.

Как собирать распределение из гармонических функций для неограниченного числа элементов — ясно, а как его на эти гармонические функции разбирать?

Если начальный элемент будет не по нулевой координате, то его распределение будет содержать не только косинусы — фаза будет сдвинута, а значит, и синусы появятся. Значит, при разборе распределения нам опять понадобится отдельно выявлять косинусы и отдельно синусы. И после этого у нас получится целых два значения. Лучше это сразу объединить в одно.

Стоит использовать комплексные числа, и вместо двух функций результата иметь одну функцию, значение у которой содержит одно комплексное число, две составляющих, реальную и мнимую. Кроме того, сама гармоническая функция может быть выражена как косинус в реальной части и синус в мнимой. $e^{2\pi iwx}=\cos(2\pi wx)+\sin(2\pi wx)i$. И тогда чтобы определить отдельные составляющие нужно подсчитать сумму или интеграл исходной функции, просто умножив на соответствующую этой составляющей двухкомпонентную гармоническую функцию.

Реальная часть разделяемой функции при умножении на реальную часть гармонической функции будет выделять косинус, а при умножении на мнимую часть гармонической функции будет выделять синус, и в результате число, которое получено, само определяет амплитуду и фазу, своим модулем и аргументом.

Кроме этого, мнимая часть разделяемой функции при умножении на мнимую часть гармонической функции будет образовывать отрицательный вклад в реальную часть результата, и при умножении мнимой на реальную в мнимой части результата тоже будет вычет. Но из-за того что детектируемые частоты разделяются на отрицательные и положительные, через то что у синуса в мнимой части различный знак, по итогу детектируется именно нужная частота, а противоположная, если её там нет, приводит к нулевому результату.

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

Сбор расстановки из гармоник:

$R(a)=\int\limits_{-\infty}^{\infty} U(x)e^{2\pi axi}\, dx $

Разбор на гармоники:

$ U(w)=\sum\limits_{a=-\infty}^{\infty} R(a) e^{-{2\pi wai}}$

Расстановка у нас задана по целым или полуцелым числам, поэтому не обязательно чтобы её разбор был интеграл, может быть и суммой. Такая сумма определяет значение только для частот, которые не больше половины от частоты элементов расстановки, а для больших частот надо брать ноль.

Но интегралом разбор тоже может быть, потому что в «плавном представлении» каждый отсчёт свёрнут с функцией $\operatorname{sinc}(x)=\{\sin(\pi x)/(\pi x),(1\Leftarrow (x=0))\}$, которая имеет нули при всех целых аргументах, кроме нулевого, и её интеграл равен единице. И, кроме того, будут присутствовать все частоты в рамках $[-1/2;1/2]$. Точнее, только они и будут.

Здесь уже можно отметить: свёртка двух расстановок будет давать такую же раскладку как произведение соответствующих раскладок от этих двух функций. Например, размытие получается свёрткой заданной расстановки с расстановкой размытия, но при сборе из гармоник раскладка из косинусов, которая получилась бы без размытия, умножается на косинусы, которые сами являются раскладкой от размытия. Короче,

$[R_1*R_2](a)=\Sigma_w (U_1(wa)\cdot U_2(wa))$

Поэтому, если свернуть расстановку по целым числам и функцию $\operatorname{sinc}()$, которая ограничена по частоте, то в частотном диапазоне функция тоже будет ограничена по частоте. И наоборот, такое ограничение по частотам это свёртка отдельных регулярных отсчётов с $\operatorname{sinc}()$.


Эти преобразования можно сделать однообразными, использовав вместо суммы интеграл и избавившись от коэффициента перед частотой в показателе в выражени для $R$.

$R(a)=\int\limits_{-\infty}^{\infty} U(x)e^{2\pi axi}\, dx=\frac{1}{2\pi}\int\limits_{-\infty}^{\infty} U(x/2\pi)e^{axi}\, dx$

Чтобы убрать множитель внутри скобок аргумента функции нужно переопределить масштаб частот. От этого множитель в показателе в выражении для самого $U$ тоже уйдёт. Частотный диапазон у $\operatorname{sinc}(x)$ из-за такого перопределения станет $[-\pi;\pi]$.

После этого образовавшийся общий коэффициент перед интегралом можно раскидать между прямым и обратным преобразованием, будет:

$U(w)=\frac{1}{\sqrt{2\pi}}\int\limits_{-\infty}^{\infty} R(x) \, e^{-{wxi}} \, dx \qquad R(a)=\frac{1}{\sqrt{2\pi}}\int\limits_{-\infty}^{\infty} U(x)\, e^{axi}\, dx $

Вот и получилось прямое и обратное преобразование Фурье. Отличие у них между собой небольшое. Если вместо применения обратного преобразования сделать второй раз подряд прямое, то функция развернётся по аргументу.

Первая функция, которая испытает преобразования Фурье на себе, у нас будет, конечно же, гауссиана.

$ \operatorname{FT}_{x\to w}\left[\frac{e^{-x^2}}{\sqrt{\pi}}\right]=\frac{1}{\sqrt{2\pi}}\int\limits_{-\infty}^{\infty} \frac{e^{-x^2}}{\sqrt{\pi}} e^{-{wxi}} \, dx= \frac{1}{\sqrt{2\pi}}\int\limits_{-\infty}^{\infty} \frac{e^{-x(x+wi)}}{\sqrt{\pi}} \, dx= \\= \frac{1}{\sqrt{2\pi}}\int\limits_{-\infty}^{\infty} \frac{e^{-(y-wi/2)(y+wi/2)}}{\sqrt{\pi}} \, dy= \frac{1}{\sqrt{2\pi}}\int\limits_{-\infty}^{\infty} \frac{e^{-(y^2+w^2/4)}}{\sqrt{\pi}} \, dy=\frac{e^{-w^2/4}}{\sqrt{2\pi}} $

Здесь видна возможность поправить коэффициенты так, чтобы преобразование от гауссианы давала ту же самую функцию.

$\operatorname{FT}_{x\to w}\left[{\frac{e^{-x^2/2}}{\sqrt{2\pi}}}\right]= \frac{1}{\sqrt{2\pi}}\int\limits_{-\infty}^{\infty} \frac{e^{-\frac{(y-wi)(y+wi)}{2}}}{\sqrt{2\pi}} \, dy= {\frac{e^{-w^2/2}}{\sqrt{2\pi}}} $

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

$ \frac{1}{\sqrt{2\pi}}\int\limits_{-\infty}^{\infty}\frac{e^{-x^2/2}}{\sqrt{2\pi}}\cos(ax)\,dx \leftrightarrow \frac{1}{\sqrt{2\pi}}\lim_{b\to\infty} \int\limits_{-\pi b/\sqrt{2}}^{\pi b/\sqrt{2}}\frac{\left(\cos\left(x/(\sqrt{2}b)\right)\right)^{2b^2} }{\sqrt{2\pi}} \cos\left(ax\right)\ \, dx $

Результат таков: если гауссиана идеальная, то в частотах она раскладывается на точно такую же гауссиану. А выражение через косинус, при $b=5$, соответствующее частотному представлению после 50 шагов размытия одного элемента, хорошо её приближает.


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

А третий гребень, удаляясь, знака не меняет.

В общем, интересный получился предел.

$\lim_{n\to\infty} \cos^{n}\left(x/\sqrt{n/2}\right)=e^{-x^2} \qquad \lim_{n\to\infty}n\sqrt{-2\ln\cos\left({x/n}{}\right)}=x$

И при этом простой. Для решения хватает приближения для косинуса $1-x^2/2$.

Плавность


Теперь, когда преобразование фурье выведено, мы займёмся дальнейшими экспериментами над гауссианой.

Эталонная гауссиана не меняется при преобразовании фурье, и её фурье-образ с ней совпадает.


С общим множителем преобразование ничего не делает, оставляет каким был.


$ k\frac{e^{-x^2/2}}{\sqrt{2\pi}}\quad\xrightarrow{\operatorname{FT}}\quad k\frac{e^{-w^2/2}}{\sqrt{2\pi}} $

Разумеется, ведь преобразование фурье — линейная операция.

Если через коэффициент к аргументу у гауссианы менять ширину, расширять, то её фурье-образ меняется сразу в двух направлениях: он и сужается и растёт.


$ \frac{e^{-(xk)^2/2}}{\sqrt{2\pi}}\quad\xrightarrow{\operatorname{FT}}\quad \frac{e^{-(w/k)^2/2}}{\sqrt{2\pi}}/k $


Используя линейность преобразования можно изменение высоты распределить между исходником и результатом преобразования, тогда получится, что когда одна из функций растёт, другая уменьшается.


$ \sqrt{k}\cdot\frac{e^{-(xk)^2/2}}{\sqrt{2\pi}}\quad\xrightarrow{\operatorname{FT}}\quad \frac{e^{-(w/k)^2/2}}{\sqrt{2\pi}}/\sqrt{k} $



Следующий эксперимент — со сдвигом.


$ \frac{e^{-(x-k)^2/2}}{\sqrt{2\pi}}\quad\xrightarrow{\operatorname{FT}}\quad \frac{e^{-w^2/2-ikw}}{\sqrt{2\pi}} $

Сдвиг гауссианы вдоль аргумента меняет фурье-образ, сворачивает в спираль соответственно частоте.

Если точно так же сворачивать гауссиану в оригинале, то фурье-образ сдвигается. Только, в обратную сторону.


$ \frac{e^{-x^2/2-ikx}}{\sqrt{2\pi}}\quad\xrightarrow{\operatorname{FT}}\quad \frac{e^{-(w+k)^2/2}}{\sqrt{2\pi}} $


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


$ \frac{e^{-(x-k)^2/2}}{2\sqrt{2\pi}}+\frac{e^{-(x+k)^2/2}}{2\sqrt{2\pi}} \quad\xrightarrow{\operatorname{FT}}\quad \frac{e^{-w^2/2-ikw}}{2\sqrt{2\pi}}+\frac{e^{-w^2/2+ikw}}{2\sqrt{2\pi}}=\\= \frac{e^{-w^2/2}}{\sqrt{2\pi}}\cdot \frac{e^{-ikw}+e^{ikw}}{2}= \frac{e^{-w^2/2}}{\sqrt{2\pi}}\cdot \cos(kw) $

Если хочется вместо косинуса синус, то одну гауссиану перед преобразованием нужно умножить на i, а другую поделить на i.

Что будет, если попробовать применить сразу оба сдвига? Обнаружится, что если сначала сдвинуть гауссиану в пространстве, а затем сдвинуть по частоте, то получится совсем не то же самое если сначала сдвинуть по частоте, а потом в пространстве. При изменении частоты одна точка обязательно оставляет постояной свою фазу, являясь центром. И в одном случае это начало отсчёта координат, а в другом случае это центр гребня.

Для точного определения функции после двух сдвигов нужна такая процедура, которая оставляет центр сдвига фазы ровно посередине между началом отсчёта и местом гребня гауссианы. И такая процедура есть. Например, если сначала наполовину сделать первый сдвиг, потом сделать второй сдвиг полностью, а потом доделать оставшуюся часть первого, место сохранения фазы будет ровно посередине. В нулевой точке фаза сдвинется на половину величины сдвигаемой фазы назад, а в на гребне фаза сдвинется на половину вперёд.


Первый график это гауссиана. Второй — результат совмещённого сдвига на величину два. Центр фазового сдвига находится в единице, содержит действительное значение. Второй ряд — результат сдвига сначала по пространству, затем по частоте. Третий ряд — сдвиг сначала по частоте, затем по пространству.

Два различных варианта представления показателя взаимозаменяемы:

$ (x-c)^2+2xsi-csi=x^2-(2x-c)(c-si) $

Если на фазовом пространстве отметить точку с параметрами сдвига гауссианы, то фурье-образ будет на этом графике располагаться точно на том же расстоянии и в перпендикулярном направлении.

$g(x,c,s)=\frac{e^{-((x-c)^2+2isx-isc)/2}}{\sqrt{2\pi}}\quad \xrightarrow{\operatorname{FT}}\quad \frac{e^{-((w+s)^2+2icw+isc)/2}}{\sqrt{2\pi}}=g(w,-s,c) $


Как будто это поворот на четверть круга.

Их даже можно вместе по кругу гонять.


Ну, то есть, преобразование фурье гауссианы можно делать плавно.


Ради этой весёлой гифки стоило написать статью. Гауссиана испытывает плавное преобразования фурье, а из-за первоначального отклонения это выглядит как колебания вокруг центра, словно на пружинке.

А если вспомнить про свёртку и про линейность преобразования, то выходит, что для каждой функции, которая может быть разложена на гауссианы, преобразование фурье тоже можно делать плавно.

$ f(x)=\frac{1}{\sqrt{2\pi}}\int\limits_{-\infty}^{\infty}\int\limits_{-\infty}^{\infty} P(c,s)\cdot {e^{-(x^2-(2x-c)(c-si))/2}} \;ds \;dc \\ \Downarrow \\ { \operatorname{FT}(\varphi)_{x\to w}[f(x)] =\frac{1}{\sqrt{2\pi}}\int\limits_{-\infty}^{\infty}\int\limits_{-\infty}^{\infty} P_{\varphi}(c,s)\cdot {e^{-(w^2-(2w-c)(c-si))/2}} \;ds \;dc }\\ P_{\varphi}(c,s)=P(c\cos(\varphi)-s\sin(\varphi),s\cos(\varphi)+c\sin(\varphi)) $

Формула плавного преобразование фурье, это плавный поворот распределения функции в фазовом пространстве.

Чтобы не путать направления поворота, нужно расставить ориентиры: обратное преобразование фурье, которое по заданной частоте даёт её волновое представление, поворачивает распределение в фазовом пространстве против часовой стрелки, соответственно тому как меняется комплексное число при сдвиге фазы в положительную сторону. Прямое преобразование фурье является детектором частоты, поэтому поворачивает значение функции разложения по часовой, переводит мнимое значение комплексной координаты $c+si$ в действительное, с сохранением знака составляющей.

Если интересно, как примерно выглядит плавное преобразование фурье для одной выделенной частоты, то вот полуторамегабайтная гифка. Для приближения использована сотня гауссиан. А в этой гифке немного перераспределён масштаб времени, чтобы сборка всплеска не была слишком быстрой.

Экспериментируем дальше.

Если две гауссины между собой свернуть, то получится как будто после размытия одной процесс продолжили на величину размытия другой, и в результате получится фигура с двойным размытием. Посмотрим как это выглядит. Возьмём два гауссианы заданной ширины.

$\frac{e^{-(x/h_1)^2/2}}{\sqrt{2\pi}h_1}\qquad\frac{e^{-(x/h_2)^2/2}}{\sqrt{2\pi}h_2}$


Подробный вывод
Переобозначим на коэффициенты частоты

$ a=1/h_1\qquad b=1/h_2 $

Свёртка выглядит так: нужно под интегралом умножить две функции, в одной заменив аргумент на $v$, в другой заменив аргумент на $(x-v)$

$\int\limits_{-\infty}^{\infty}\frac{ae^{-(va)^2}/2}{\sqrt{2\pi}}\cdot \frac{be^{-((x-v)b)^2}/2}{\sqrt{2\pi}}\, dv$

В первую очередь стоит вынести перед интегралом коэффициенты

$ \frac{ab}{2\pi}\int\limits_{-\infty}^{\infty}{e^{-(va)^2/2}}\cdot{e^{-((x-v)b)^2/2}}\, dv$

После этого стоит объединить экспоненты и раскрыть в показателе скобки.

$ \frac{ab}{2\pi}\int\limits_{-\infty}^{\infty}{e^{-(v^2a^2+x^2b^2+v^2b^2-2xvb)/2}}\, dv$

После этого нужно сгруппировать по степени переменной интегрирования

$ \frac{ab}{2\pi}\int\limits_{-\infty}^{\infty}{e^{-(x^2b^2+v(v(a^2+b^2)-2xb)/2}}\, dv$

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

$\frac{ab}{2\pi}\int\limits_{-\infty}^{\infty}{e^{-\left(x^2b^2+(a^2+b^2)v\left(v-\frac{2xb}{a^2+b^2}\right)\right)/2}}\, dv=$

$ \left[v\to u+\frac{xb}{a^2+b^2}\right]$

$= \frac{ab}{2\pi}\int\limits_{-\infty}^{\infty}{e^{-\left(x^2b^2+(a^2+b^2)\left(u+\frac{xb}{a^2+b^2}\right)\left(u-\frac{xb}{a^2+b^2}\right)\right)/2}}\, du=$

$=\frac{ab}{2\pi}\int\limits_{-\infty}^{\infty}{e^{-\left(x^2b^2+(a^2+b^2)u^2-\frac{x^2b^2}{a^2+b^2}\right)/2}}\, du$


После этого под интегралом можно оставить только степень с переменной интегрирования, остальное вынести из интеграла.

$\frac{ab}{2\pi} e^{-\left(x^2b^2 \left(1-\frac{b^2}{a^2+b^2}\right) \right)/2} \int\limits_{-\infty}^{\infty}{e^{-\left((a^2+b^2)v^2\right)/2}}\, dv=$

Интеграл гауссианы это корень из $\pi$, умноженного на коэффициент перед переменной интегрирования в показателе, включая деление на два, это добавляет двойку перед $\pi$. Результат будет

$ \frac{ab}{2\pi}e^{-\left(x^2b^2\left(1-\frac{b^2}{a^2+b^2}\right)\right)/2}\frac{\sqrt{2\pi}}{\sqrt{a^2+b^2}}= \frac{1}{\sqrt{2\pi}}\cdot \frac{ab}{\sqrt{a^2+b^2}}e^{-\left(\frac{x^2a^2b^2}{a^2+b^2}\right)/2} $



Получилась гауссиана

$\frac{e^{-(x/h_3)^2/2}}{\sqrt{2\pi}h_3} \qquad h_3=\frac{\sqrt{a^2+b^2}}{ab}=\sqrt{{\frac{1}{a^2}+\frac{1}{b^2}}}=\sqrt{h_1^2+h_2^2} $

$h_1^2+h_2^2=h_3^2$

Как и предполагалось, за повтор размытия ширина увеличивается не в два раза, а в корень из двух раз.

Если допустить, что ширина может выражаться комплексными числами, то функция, которая при свёртке должна была бы обращать размытие, будет представлена гауссианой с отрицательным квадратом ширины, то есть с мнимой величиной ширины. Рассмотрим форму графика гауссианы, задавая квадрат ширины действительным числом. Вот как выглядит переход через нулевое значение:


Менять знак у квадрата комплексных чисел можно не только проходя через ноль, значение можно повернуть в комплексном пространстве, плавно от единицы до мнимой единицы. Гауссиана тогда будет меняться так:


Интересно здесь то что при промежуточном значении $h=\sqrt{i}=(1+i)/\sqrt{2}$ гауссиана расправляется во всю ширь, везде с одинаковым абсолютным значением, отличаясь по пространству только комплексной фазой.


А что если физика-наблюдателя и наблюдаемую микрочастицу одновременно свернуть с такой гауссианой? И частица и физик будут занимать всю вселенную, для линейных взаимодействий не фиксируя никаких изменений друг в друге. Начало волновой интуиции — в понимании того, что размытие относительно. И не только математически, но и физически.

По теме физики можно добавить ещё: усиление взаимодействия кварков с расстоянием напоминет гауссиану с отрицательным квадратом от ширины — она тоже, чем дальше от нуля, тем больше. Но это ей не мешает быть претендентом для свёртки для обращения размытия.

Характеристики


Будем называть гауссиану ${e^{-x^2/2}}/{\sqrt{2\pi}}$ базовой. А гауссиану ${e^{-(x^2+(2x-c)(c-si))/2}}/{\sqrt{2\pi}}$ смещённой. Если свернуть базовую с любой другой, то в фазовом пространстве преобразования фурье, в котором функция была сконцентрирована в одной точке, значение расплывётся вдоль линейного направления именно так как эта вторая гауссиана. После этого можно повернуть фазовое пространство на четверть оборота и затем произвести свёртку со смещённой гауссианой, чтобы получить преобразование фурье. При этом результат интеграла гауссиан с разнообразием их комплексных фаз соберётся в подтянутую гауссианту, в соответствии (обратном) изначально растолстевшей.

Для обобщения можно сразу рассчитать свёртку размытия — с указанием направления размытия в фазовом пространстве.

$ \left[\frac{{e}^{-v^2/2}}{\sqrt{2\pi}};x\to v\right]*\left[\frac{ {e}^{\Large-(x^2+(2x-c)(c-si))/2}}{\sqrt{2\pi}};\begin{matrix}c\to vc\\s\to vs\end{matrix}\right]=\\=\frac{1}{2\pi}\int\limits_{-\infty}^{\infty} {e}^{\Large -(v^2(1+c^2-csi)-2v(xc-xsi) +x^2)/2}dv=\frac{{e}^{ -x^2\left({\LARGE \frac{1+s^2+csi}{1+c^2-csi}}\right)/2}}{\sqrt{2\pi}\sqrt{1+c^2-csi}} $

Здесь видно, что два параметра $c$ и $s$ задают характеристики $n=\sqrt{1+c^2-csi}$ и $m=\sqrt{1+s^2+csi}$.

$\frac{e^{-x^2(m/n)^2/2}}{\sqrt{2\pi}n}$

Которые вместе определяют ширину и высоту гауссианы. Ширину через отношение $n/m$, а высоту через $1/n$. Через $1/m$ определено значение интеграла гауссианы. Как обычно, произведение ширины и высоты это площадь.

Преобразование фурье обменивает $m$ и $n$. При плавном преобразовании фурье они будут обмениваться также плавно.

$ c= b\cos(\varphi)\qquad s= b\sin(\varphi)\qquad a=m_0 \quad b^2 = n^2_0-m^2_0 \\n=\sqrt{a^2+b^2\cos(\varphi)(\cos(\varphi)-\sin(\varphi)i)} \\m=\sqrt{a^2+b^2\sin(\varphi)i(\cos(\varphi)-\sin(\varphi)i)} $

Значит, у самого цикла есть две характеристики: некоторая неизменная величина и фаза. Неизменная величина:

$ b^2=c^2+s^2=n^2+m^2-2a^2 $

Квадрат ширины равен соотношению квадратов характеристик, выражается так:

$h^2=\frac{n^2}{m^2}=1 + \frac{1}{\frac{\frac{a^2}{b^2}+\frac{1}{2}}{\cos(2 \varphi) - \sin(2 \varphi)i}-\frac{1}{2} }=1+\frac{2b^2}{(2a^2 + b^2)e^{2\varphi i}-b^2} =\\=\frac{(b^2 + 2a^2) e^{2\varphi i}+b^2}{(b^2 + 2a^2) e^{2\varphi i}-b^2} =\frac{(b^2 + 2a^2) e^{\varphi i}+b^2e^{-\varphi i}}{(b^2 + 2a^2) e^{\varphi i}-b^2e^{-\varphi i}} =\frac{a^2e^{\varphi i}+b^2\cos(\varphi)}{a^2e^{\varphi i}+b^2 \sin(\varphi)i} $

Это очень симметричная формула.

$ h^2-1=\frac{1}{\frac{\frac{a^2}{b^2}+\frac{1}{2}}{\cos(2 \varphi) - \sin(2 \varphi)i}-\frac{1}{2}}\qquad \frac{b^2}{a^2}=\frac{1}{\frac{\frac{1}{h^2-1}+\frac{1}{2}}{\cos(2\varphi) + \sin(2\varphi)i}-\frac{1}{2}} $

Из неё можно вывести выражение для фазы.

$ e^{-2\varphi i} =\frac{\left(\frac{n^2+m^2-2a^2}{a^2}\right)^{-1}+\frac{1}{2}}{\left(\frac{n^2}{m^2}-1\right)^{-1}+\frac{1}{2}}=\frac{(n^2-a^2)-(m^2-a^2)}{(n^2-a^2)+(m^2-a^2)} $

Центр вращения характеристик вычисляется как $(n^2+m^2)/2$, а радиус вращения зависиот от $(n^2-m^2)/2$. Если абсолютные значения будут равны, то путь изменения будет проходить через нулевую точку, в которой — или высота, или интеграл гауссианы уходит в бесконечность. Свёртка с такой гауссианой похожа на поворот. Как при умножении чисел, когда степень у комплексного множителя ни положительная, ни отрицательная, а мнимая, происходит поворот в комплексной плоскости.

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

Думаю, на этом можно закончить. Получилась, на мой взгляд, и развлекательная и познавательная статья. И пусть рассказано в основном про преобразование фурье, это достаточно большая часть волновой интуиции. Если задуматься, какую роль имеют чёткость и плавность в нашей жизни, может оказаться, что переоценить просто невозможно.

Ссылки на другие мои статьи
Cортировка по степени рекомендации.

  1. «Экскурсия в подвал» — как выглядит подвал математики.
  2. «????-повар и ????-торт» — о том что у числа ???? есть простая формула.
  3. «Скучные числа» — обо всех числах. Натруальные числа, дроби, иррациональные, бесконечность, i, e, ????, ????, числа бернулли, нули дзета-функции.
  4. «Как устроены волны» — до конца не объяснено, но что есть — интересно.
  5. «Удивительная и загадочная ????» — кроме e и ???? есть ещё «круглые» константы.
  6. «Взгляд программиста на гипотезу Коллатца» — развлекательная переформулировка гипотезы.
  7. «Простое и точное решение задачи про колодец лотоса» — задача с виду простая, а решит не каждый.
  8. «Новые нули дзета-функции» — недоказуемое веселье.
  9. «Тридцать шесть градусов красоты» — подробный разбор мозаики пенроуза, из приведённого кода можно собрать рисующую программу.
  10. «Гипотеза Эскобара» — о том что не всё просто. Кватернионы, функция ламберта, константа эйлера-маскерони. А поставленный вопрос не решён.
  11. «Искусственная соображалка без фатальных недостатков без нейросетей разработать» — мечта об искусственной соображалке. Обзорная статья, тег «философия». Голосование читателей — «Статья в основном безвредна». Написано в 2019, до GPT. Со временем стала только актуальней.
  12. «Два вида последовательного перебора пикселей» — дербаним плоскость на отдельные квадраты, расположенные последовательно.
  13. «Чаепитие из rvalue» — взгляд на аспект C++ как на сказку. Статья «шаблонно» заминусована.
  14. «Раскрытие заговора против себя дураки отложили на неопределённый срок» — попытка поумничать. По дате это май 2021-го.
  15. «Сто-пятьсот цифр числа пи на коленке» — как в экселе подсчитать до тысячи цифр числа пи.
  16. «Не простая координатная система, а золотая» — статья из песочницы, о десятиугольной системе координат.
  17. «Не сломать, не потерять» — скучная статья про шар. Комментарии и то веселее.
  18. «Общая схема» — Статья у которой на обложке кот. Находится в хабе «чулан». Внутри очень неаккуратно поданная философия.




Вместо рекламы тут выражение благодарности всем кто задонатил за статью «скучные числа». Может, и эта статья кому-нибудь настолько понравится.

Комментарии (13)


  1. longclaps
    00.00.0000 00:00

    Много букв, внимательно почитаю позднее. Однако.

    У нас дискретная система, N коробок по 1024 конфет, 1024 сладкоежек. Есть устойчивое равновесие - когда по N конфет у каждого. Но даже если оно недостижимо - ввиду конечности числа состояний по принципу Дирихле система рано или поздно зациклится. При этом начальное состояние не обязательно будет содержаться в финальном цикле. Т.е. после достаточно большого числа итераций провернуть фарш назад не получится.

    У меня вышло мало букв, я что-то упустил?

    p.s. не рассчитывайте на мой быстрый ответ - мне карма не позволяет ????

    p.s.s. зато пока могу здесь добавить - я утверждаю, что открутить назад может не получиться при любом числе участников, нечетность не рулит.


    1. yurixi Автор
      00.00.0000 00:00

      Да, ниже говорится, что для возможности всё обратить важно чтобы количество количество участников было нечётным.


      1. ksbes
        00.00.0000 00:00

        И что? В этом случае не возможен цикл не включающий начальное состояние? Ну, если выражаться иначе, нет состояний в которое можно прийти двумя различными путями?
        Если это так, то это совсем не очевидно!


        1. yurixi Автор
          00.00.0000 00:00

          Циклы возможны, но откатив на столько же шагов получим точно то же состояние. А если количество нечётное, даже два, то даже первый шаг не обратить.


          1. ksbes
            00.00.0000 00:00

            Вы, может быть, не совсем поняли о чём идёт речь. Если у нас есть состояние В, непосредственным предшественником которого является как состояние А, так и состояние Б, то как вы выберете в какое возвращаться?
            Не все дискретные автоматы обратимы — та же игра Жизнь, например: вы в ней далеко не всегда сможете "мясорубку назад провернуть".
            Т.е. обратимость надо обосновывать отдельно.


            1. yurixi Автор
              00.00.0000 00:00

              Размытие напополам с соседом при нечётном количестве участников с зацикливанием по пространству участников обратимо. Двух предшественников быть не может, есть однозначный алгоритм вычисления предшественника. Их в статье даже несколько, с одинаковым результатом.


              1. ksbes
                00.00.0000 00:00

                Хорошо. Значит я не совсем понял о чём речь :) (но вообще рациональное количество конфет — это читерство!)


    1. yurixi Автор
      00.00.0000 00:00

      зато пока могу здесь добавить - я утверждаю, что открутить назад может не получиться при любом числе участников, нечетность не рулит.

      Не зря статья позиционирует себя как развитие интуиции.

      Вас ждёт забавное открытие. Ну, или меня, если вы хоть как-то примерно намекнёте на особые случаи, когда это не получается.

      Для уточнения: после деления пополам конфет может быть не целое число, это ограничение мной не учитывается.


  1. vvzvlad
    00.00.0000 00:00
    -1

    Получилась, на мой взгляд, и развлекательная и познавательная статья.

    Я: не понял ничего, не говоря уж о развлечении


  1. dprotopopov
    00.00.0000 00:00
    +2

    Когда-то давно было подобное на хабре

    https://habr.com/ru/post/147828/

    https://habr.com/ru/post/152885/


  1. uchitel
    00.00.0000 00:00

    Статья классная. Свертки еще используются для "арифметических" операций над распределениями плотности вероятности. Там тоже все очень интересно получается, настолько, что на интуицию даже не стоит полагаться.


    1. dprotopopov
      00.00.0000 00:00

      Мне тоже одно время интересовали свёртки - в том числе фурье - даже статейки накропал

      https://habr.com/ru/post/597715/

      https://habr.com/ru/post/266129/

      https://habr.com/ru/post/265781/


  1. Refridgerator
    00.00.0000 00:00

    Эта картинка однозначно имеет отношение к Chirp Z-transform:

    Я также слышал о Fractional Fourier transform, но не вникал в его суть для понимания того, как оно соотносится с содержанием вашей статьи.