| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > сравнить 2 набора точек |
| Автор: mrgloom 31.10.2012, 10:19 |
| вообщем задача такая. есть 2 набора точек и надо по метрике евклидову расстоянию указать какие точки из 2-х множеств не покрыты, т.е. например если для точки первого множества есть хотя бы 1 точка второго множества отстоящая от неё менее чем на threshold, то значит точка покрыта. и так надо для всех точек первого и второго множества. хотелось бы не решать полным перебором точек. возможно knnsearch который в opencv с этим справится?(только я не уверен там помоему приближённый алгоритм) или надо строить quad tree чтобы быстрее отсекать? + потом еще надо точки которые непокрыты как то обвести баунд боксами, скажем делим все непокрытые точки опять же по расстоянию на группы, проверяем кол-во в группе если больше N, то обводим рамкой. |
| Автор: maxdiver 31.10.2012, 12:54 |
| http://en.wikipedia.org/wiki/Nearest_neighbor_search ? |
| Автор: mrgloom 31.10.2012, 16:08 |
| ну да, но у меня получается, что когда я для точки первого сета ищу пары во втором сете, то я потом эти точки могу выкинуть из второго сета(т.к. уже найдена хотя бы 1 точка пара), чтобы уменьшить их кол-во, что при линейном поиске ускоряет поиск, но когда мы используем что то типа kdtree индекс то уже построен и как я понимаю уже ничего не выкинешь, хотя наверно всё равно быстрее будет. |
| Автор: maxdiver 1.11.2012, 14:58 |
| Перестроение пространственного индекса (kd-дерева или чего-нибудь на основе диаграммы Вороного) вперемешку с поиском скорее всего только замедлит работу. |
| Автор: mrgloom 2.11.2012, 12:34 | ||
не понял. индекс то мы строим 1 раз для 1 сета точек(видимо большего), а потом для каждой точки второго меньшего сета осуществляем поиск. у меня точек примерно десятки тысяч, не знаю достаточно ли это для ускорения. |
| Автор: mrgloom 14.11.2012, 09:18 |
| Еще такой вопрос про PCA. Допустим у нас есть выборка из 1000 сэмплов(каждый вектор длиной N) и для 1001 надо найти скажем K ближайших соседей, можно было бы перебрать все по порядку используя например просто евклидову метрику для вектора длиной N и потом отсортировать и взять K ближайших сэмплов. Но вроде бы такой подход никуда не годится, ибо при больших N это плохо работает. (в математическом обосновании я не очень уверен). Значит применяем PCA потом проецируем 1000 сэмлов на новый базис и 1001 тоже и так же ищем K ближайших только для размерности векторов например 100, а не N. Можно так же применить не просто линейный поиск, а сделать дерево из 1000 элементов и всё будет искаться быстрее. Но тут возникает проблема, по мере наполнения сэмплов в базу, получается что при каждом добавлении нового элемента в базу требуется перестраивать индекс дерева, а так же если мы используем PCA пересчитывать базис. Какое решение такой проблемы можно предложить? мне пока только пришло в голову делать это не для каждого элемента, а для группы элементов или вообще ничего не делать до того как не наберем полную базу. Возможно можно сформировать какой то критерий насыщения базы, т.е. добавление новых сэмплов в базу уже мало повлияет на нашу текущую "популяцию"? т.е. для новых приходящих элементов чтобы получить K ближайших соседей и посмотреть на что они похожи можно использовать уже этот состоявшийся базис. |