LINUX.ORG.RU

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

 ,


0

1

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

Вопрос - как понять, какие размеры у сетки (в узлах) по всем осям? Т.е. мы скажем имеем двумерную сетку, смотрим на нее вдоль оси Y - имеем по Х сколько то групп точек. Нужно посчитать число групп. Автоматически естественно;-)

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

★★★★★

что значить группа точек?

dikiy ★★☆☆☆ ()
Ответ на: комментарий от AIv

То есть тебе надо определить понятие кучки точек?

dikiy ★★☆☆☆ ()
Ответ на: комментарий от dikiy

как вариант - примени «математическое» размытие на пространство с точками. Полученные связные области и будут твоими группами. Если групп слишком много - увеличиваешь радиус размытия.

dikiy ★★☆☆☆ ()
Ответ на: комментарий от dikiy

А можно от балды выбирать радиус и от каждой точки искать соседей.

dikiy ★★☆☆☆ ()
Ответ на: комментарий от dikiy

Это называется полным перебором. Очевидное такого очевидного решения тут не искали бы.

FeyFre ★★★★ ()
Ответ на: комментарий от FeyFre

Это называется полным перебором. Очевидное такого очевидного решения тут не искали бы.

это не проблема. Всего-то n^2 шагов. А-то и меньше, если отсортировать.

dikiy ★★☆☆☆ ()

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

FeyFre ★★★★ ()
Последнее исправление: FeyFre (всего исправлений: 1)
Ответ на: комментарий от FeyFre

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

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

AIv ★★★★★ ()

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

anonymous ()

но могут и вообще хрен знает как шаги прыгать - тут уж ничего не поделаешь...

Если именно прыгать хрен знает как, то только перебором.

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

peregrine ★★★★★ ()
Последнее исправление: peregrine (всего исправлений: 1)
Ответ на: комментарий от anonymous

Задано вдоль главных осей естественно.

AIv ★★★★★ ()

Я ничего не понял. У тебя есть неупорядоченный набор точек, заданных своими координатами, коих число D, и известно, что эти точки образуют в D-мерном пространстве сетку в виде прямоугольного параллелепипеда? И надо найти его «размер», измеряемый в ячейках/узлах, с учётот того, что есть небольшая погрешность в координатах?

Sahas ★★★★★ ()

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

Правда если множество повернуто как-то в пространстве, то наверное надо будет сделать ортонормирование ещё.

ebantrop ()

Преобразования Хафа пробовал?

С их помощью легко восстанавливается сетка у датчиков Шака-Гартманна даже если экран будет немного повернут.

anonymous ()
Ответ на: комментарий от anonymous

Да, для обработки «классических» гартманнограмм (там 256 пятен образуют структуру из восьми колец по 32 радиуса + два маркера) я, как тут и предлагали, тупо сортировку использовал. Сначала вычислил центр тяжести, затем сделал сортировку по R и по углу. Дальше по расстоянию между координатами в сортированных массивах проводил кластеризацию. Задача нерешаема, если вариации координат могут превышать половину минимального порога между ними.

Но у тебя задача вполне проста, т.к. априорно шаг сетки значительно превышает погрешности. Если ты уверен, что сетка строго параллельна координатным осям, тупо набирай 2 массива, отсортированных по x и по y! Если же может быть поворот, преобразование Хафа поможет тебе определить основные симметрии (на углах, равных повороту и поворот+180° в образе Хафа вдоль координаты R будут максимумы). Думаю, шага где-нибудь в полградуса по углу тебе хватит, по R же можно вообще одномерное преобразование сделать (т.к. нам нужен лишь угол поворота).

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

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

anonymous ()

Я не специалист, конечно, но что если просто отфильтровать распределение точек на каждой оси через какую-нибудь свёртку и найти локальные максимумы? Или это тоже самое, что Дикий предложил?

anonymous ()
Ответ на: комментарий от AIv

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

anonymous ()

Определить число кластеров «автоматически» позволяет library(mclust). По любой оси отдельно загружаешь и она считает оптимальное число кластеров. Алгоритм там внутри описан.

Проблема с «крайними точками» на осях (если там мало данных).

psv1967 ★★★★★ ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.