Критерий попадания точек на целочисленную сетку с поворотом

[ilghiz]

Добрый день,

Пусть у меня имеется на плоскости $N$ точек $a_i = (x_i, y_i), i=1, \dots, N$, и мне известно, что если я применю к этим точкам преобразование $\alpha B a_i + t$, где $t \in {\matbb R}^2$ - произвольный вектор, $\alpha \in {\matbb R}$ - произвольное число и $B \in {\matbb R}^{2 \times 2}$ - унитарная матрица, то полученные точки расположатся с некоторой точностью на квадратной сетке с целыми координатами. Более того, они будут занимать существенно меньшее число ячеек по каждому направлению, чем $N$.

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

Точек в реальности будет не много, не меньше 7, и, не больше 100.

Пока видится наивный метод - перебирать все углы поворота от 0 до 90 с маленьким шагом, а далее после поворота делать параллельный перенос, чтобы все это множество центрировалось на начало координат, и счиать проекции всех точек на оси. Далее пытаться угадать шаг, но как-то все это не строго получается.

Скажите, пожалуйста. возможно есть какой-то детерминистический метод решения? Или Есть какой-то критерий, (желательно дифференцируемый), чтобы по нему можно было одномерную минимизацию по углу поворота запустить.

Спасибо!

[slavav]

Чувствую что считать вам какое-то преобразование Фурье, максимум которого укажет угол поворота и масштабный множитель. Параллельный перенос после этого считается аналитически.

[mihaild]

А позволяют ли параметры задачи надеяться, что попадутся две точки на одной горизонтали или вертикали? Если да - то при таких параметрах перебираем все пары точек, перебираем число узлов между ними (от 1 до $N$) и дальше легко проверяем.

[svv]

ilghiz, при правильном преобразовании Ваши точки расположатся в узлах сетки "плотно" (как красные на картинке), или не обязательно плотно (как зелёные)?

[Евгений Машеров]

Находим углы направлений i-той точки на j-тую, приводим к $(0;\frac \pi 2)$, ищем медиану значений углов. Если точки лежат на сетке, она должна дать искомый угол поворота.

[Aritaborian]

Может, моду, а не медиану? Хотя нет, точки ведь расположены с плюс-минус точностью.

[Евгений Машеров]

Если бы были точно целочисленные, то моду. Но мода не очень хороша в смысле устойчивости. Надо что-то не сильно зависящее от "заведомо не в ту сторону", но всё же находящее нечто среднее (просто среднее зависело бы от значений углов на точки, лежащие не на тех же линиях сетки). Причём надо какие-то статистики для углов, вроде описанных у Мардиа, чтобы понималось - между $1^o$ и $359^o$ лежит $0^o$, а не $180^o$
Примерно так:
Для проверки данного метода попробуем рассмотреть неповёрнутую решётку. Если для неё получится нулевой поворот - можно попробовать вычислительный эксперимент со случайным поворотом.
Если у нас n точек, а вертикалей и горизонталей по m, $n\gg m$и попадание случайно, то для наудачу выбранной точки будет в среднем $\frac {n-1} m$ точек на той же горизонтали и столько же на той же вертикали. И по $\frac {n(1-n/m)} 2$ точек "Левее" и "правее" и "выше" и "ниже". И после отбрасывания этих последних остаются лишь "наши вертикалы и горизонталы". Вроде получается. Как вариант - среднее, но после усечения, но надо для границ усечения заранее знать не только n, но и m.

ilghiz в сообщении #1562412 писал(а):

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

Скорее всего невозможно. Условие "целочисленности" сильно всё портит.

[sup]

Пусть у нас возникла следующая задача.
Дан набор точек (пока одномерный случай)

$$ x_n = X + k_n \cdot d + e_n, \quad n = \overline{1, N}. $$

1. $x_n$ - наблюдаемый набор координат
2. величины $X, d$ фиксированы и неизвестны (смещение и шаг решетки)
3. $k_n$ - неизвестные целочисленные координаты (на решетке)
4. $e_n$ - неизвестная ошибка (предполагается малой)

Требуется найти $X, d$.
Ясно, что задача поставлена не вполне корректно, т.к. величина ошибки никак не контролируется. Но с этим ничего не поделать.
Для решения этой задачи предлагается использовать аппарат цепных дробей.
Прежде всего, избавимся от сдвига $X$. Для этого сортируем $x_n$ и берем разности между соседними точками. Да, ошибка увеличится (в 1.5 раза), но теперь можно считать, что $X =0$. Снова сортируем. После этого можно считать, что последовательность $k_n$ неубывает. Вот теперь рассматриваем дроби вида

$$ f_n = \frac{x_n}{x_{n+1}}. $$

В идеальном мире это были бы рациональные дроби. Но ошибки $e_n$ портят картинку. Ну и ладно. Рассматриваем цепные дроби для наилучшего приближения и следим за знаменателями. Как только знаменатель СКАКНУЛ - все, нашли хорошего кандидата для рациональной дроби.
На практике этот метод работает прекрасно, но есть нюансы.

1. дробь $f_n$ надо "парсить" руками. Попытка использовать простое деление данных типа "double" моментально заваливается. Так что надо использовать целочисленную арифметику с самого начала. Разбор экспоненты, мантиссы итд.
2. Метод ловит лишь взаимно простые величины и не различает дроби вида 1/2 и 3/6. Так что надо это учитывать.
3. Скачок в знаменателе - та еще вещь. Их может быть несколько. Какой лучше? Это и есть выбор размера решетки.
4. Как всегда, много чего еще по мелочам. Все это всплывает в процессе использования.

(Оффтоп)

Между прочим, такой подход можно эффективно использовать для сжатия геометрии, если есть серьезные подозрения насчет существования такой решетки. Отдельно сжимаем целочисленные координаты (относительно простая задача) и отдельно вычисленные ошибки $e_n$ (если вообще нужно). Для сжатия ошибок используем их "малость". Таким образом можно иногда получить сжатие без потерь с коэффициентом 4-5)

Ну, а теперь двумерные данные. Они еще и повернуты, но это ничего не меняет. Просто шаг решетки будет $\cos \varphi$. Дальше изучаем координаты $x, y$ по-отдельности.

[svv]

sup в сообщении #1562676 писал(а):

Они еще и повернуты, но это ничего не меняет. Просто шаг решетки будет $\cos \varphi$.

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

[sup]

Я и не утверждал, что это готовый алгоритм. После удаления сдвига получаем набор "дельт" по иксам. После этого надо убрать "слишком маленькие". Это действительно может быть дребезг. Если же они все слишком маленькие, то следует использовать игреки. Да и "слишком большие" тоже неприятно. Тут, скорее, важно отношение соседних величин. Та самая дробь $f_n$ не должна быть слишком маленькой.

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

[svv]

Я понял, но всё-таки приведу картинку.

И это ещё без учёта ошибок.

[sup]

Аааааааааа, я понял. Да, с поворотом я, похоже, промахнулся. Там же будет другая формула

$$ x = k\cos \varphi + l \sin \varphi. $$

Точно. Надо подумать, можно ли тут как-нибудь приспособиться.

-- Вс авг 14, 2022 21:56:30 --

Можно использовать проекции одного вектора на другой.
Тогда проекция выглядит так

$$ (u - \lambda v, v) = 0, \quad \lambda = \frac{(u, v)}{(v, v)}. $$

А скалярные произведения инвариантны относительно поворотов. Значит $\lambda$ рациональное число.
Вроде не проврался. Знаменатель тогда сумма квадратов. Дальше надо думать.
А лучше спецов по теории чисел спросить. Они быстрее придумают

[ilghiz]

Спасибо огромное всем за интересные советы!

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

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

Пока додумался существенно упростить свою задачу до того, чтобы гарантировать хотя бы две точки, отстоящие на одну целую единицу на дискретной сетке. Такая задача тогда решается просто - ищем минимальное расстояние, и соответствующий отрезок трансформируем в (0,0)-(1,0), а норму определяем в виде невязки попадания остальных точек на целочисленную сетку.

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

[svv]

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

[ilghiz]

svv в сообщении #1562746 писал(а):

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

Спасибо! Так тоже интересно получается!!!

Я может и не прав, но, ИМХО численно через углы и умножение на циркулянт (то есть через Фурье) будет проще. На дискретной сетке при нулевых ошибках все углы у какой-то ограниченной области имеют только несколько дискретных значений, тангенсы которых равны $1/1, 1/2, 1/3, 2/3, \dots$. Если мы не знаем на сколько у нас картинка повернута, нам надо дискретизовать набор таких углов и набор наблюдаемых углов и найти сдвиг в виде умножения на Теплицеву. Очевидно, что в силу того, что углы зациклены на 360 градусов, эта Теплицева превращается в циркулянт и нам не надо окаймлять все в два раза. Я именно так делал по первости. Основная проблема которая у меня имеется - набор точек приходит от минимизации другой задачи и мне нужен критерий не только попадания на сетку, но и на сколько "хорошо" мы попадаем сейчас на эту сетку.

svv в сообщении #1562746 писал(а):

Тут не требуется, чтобы среди точек нашлись два соседних узла сетки.

Я набор точек на сетке делаю сам, другое дело, что не весь этот набор всегда виден. Раньше я не требовал того, чтобы обязательно находились два узла сетки, но, как оказалось, во всем наборе из около 500 точек было только 5 маленьких районов, где этот критерий не соблюдался, поэтому я решил перегенерить набор точек, чтобы этот критерий соблюдался бы всегда.