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

    п.с. RANSAC,ICP не предлагать, интересно как это можно решить на графах.

Это сообщение отредактировал(а) mrgloom - 30.1.2012, 17:19

mrgloom, 
Читай про максимальное паросочетание.

Очень неясная и нечеткая постановка задачи.
Как математик могу сказать, что оптимальное решение в той постановке которая дана - все точки шум. Тогда расстояние 0.
Четко сформулируйте условия.

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


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

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

а потом мы должны наилучшим образом "наложить" эти 2 набора точек ( в реальности должны определить поворот и смещение по х у), а так же определить какие точки шум, а какие нет.

Это сообщение отредактировал(а) mrgloom - 9.2.2012, 15:34

mrgloom, 
Теорию можно прочитать здесь:
http://habrahabr.ru/blogs/algorithm/63982/

  80-99%


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


Mirkes, По поводу формулировки задачи. mrgloom плохо её сформулировал.
Это и понятно задача чисто инженерная нежели математическая. Многие факторы не учитываются.

Есть набор точек в 3D пространстве положение их не известно. Есть 2 проекции этих точек на разные плоскости.  Координаты известны.
Плюс есть шум. Шум двух видов:
1) Если сравнивать второй набор с первым, то некоторые точки исчезли другие появились. 
2) Плюс каждая точка имеет некоторый аддитивный шум в своих координатах.

По поводу проецирования, оно обычное. Но само по себе имеет ряд особенностей:
При проецировании координаты одних точек на первой проекции отличаются от второй. 
а) смещены.
б) смещены и повёрнуты
с) смещены и повёрнуты плюс прочие искажения.
mrgloom, не уточнил что за задача, так что я исхожу из случая б) 

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

Задача как раз и найти максимальное паросочетание. То есть имеем предположение что таких пар более 2.
Но вот смещение и поворот надо будет искать либо интерационно, либо придумать некоторую ивристику.

вроде бы нашел в литературе это называется bipartite graph matching
но там рассматривается случай если кол-во точек одинаковое, т.е. без шумов.