Перейти к содержимому
Compvision.ru
mrgloom

ICP(Iterative Closest Point)

Recommended Posts

Все параметры HMM представляются как один вектор.

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

Куда двигать параметры определяется по градиенту (если точно то в сторону, противоположную градиенту).

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

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

http://www.cs.cmu.edu/~ytsin/KCReg/

тут еще есть некий альтернативный вариант, но только матлаб.

и еще тут

http://research.microsoft.com/en-us/um/people/awf/lmicp/

в пейпере о gmmreg еще написано что всё таки они считают некое discrete gauss transform.

как раз вроде делается через перемножение матриц.

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

читаю про реализацию метода

http://www.cs.cmu.edu/~ytsin/KCReg/KCReg.pdf

там Kernel Correlation почему это определяется как интеграл от произведения kernel function ? и как это реализовывать когда имеем дискретный случай?(хотя вроде по формуле (3) )

из какого раздела математики это всё?

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

еще про вычисление градиента от функции для минимизатора.

допустим имеем функцию что то типа гауссианы

f= exp(-((x(i)-x(j))/(scale))^2)

тогда градиент

grad= (-2*((x(i)-x(j))/(scale)^2)*exp(-((x(i)-x(j))/(scale))^2)/(m*n)

вот непонятно почему мы делим на m*n ? m,n - это кол-во точек в матрице точек которые x(i),x(j).

по идее должна быть просто производная? причем производная получается по dx= x(i)-x(j)

double GaussTransform(const double* A, const double* B,

    int m, int n, int dim, double scale, double* grad)

{

  double cross_term = 0;

  for (int i = 0; i < m * dim; ++i)

  {

    grad[i] = 0;

  }


  scale = SQR(scale);

  for (int i = 0; i < m; ++i)

  {

    for (int j = 0; j < n; ++j)

	{

      double dist_ij = 0;

      for (int d = 0; d < dim; ++d)

	  {

		dist_ij +=  SQR(A[i * dim + d] - B[j * dim + d]);

      }

      double cost_ij = exp(-1.0 * dist_ij / scale);


      for (int d = 0; d < dim; ++d)

	  {

        grad[i * dim + d] -= cost_ij * 2.0 * (A[i * dim + d] - B[j * dim + d]);

      }

      cross_term += cost_ij;

    }

    /* printf("cross_term = %.3f\n", cross_term);  */

  }

  scale *= m * n;

  for (int i = 0; i < m * dim; ++i)

  {

    grad[i] /= scale;

  }

  return cross_term / (m * n);

}

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

Из раздела статистики и машинного обучения, см. kernel methods.

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

по сути я понял ,что всё строится на понятии inner product http://mathworld.wolfram.com/InnerProduct.html

и в нашел случае похоже там формула 3 с интегралом.

и вроде как при переходе к другому пространству(space) kernel function как раз и заменяет inner product.

слайд 14

http://www.kernel-methods.net/tutorials/KMtalk.pdf

но как то всё равно всё это мутно.

а что тогда на слайде 15 <x,z>^2 ? если <x,z> и так inner product

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

Евклидова метрика и Евклидова метрика в квадрате :)

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

вообще то евклидолва метрика

(x1-z1)^2+(x2-x2)^2 и обозначается как модуль или еще вроде называют нормой.

а тут именно квадрат inner product, только к чему тут этот квадрат.

и там показывается, что квадрат inner product можно заменить на inner product от более сложной (было двухмерное пространство стало трёхмерное)функции - которая и является kernel function?

но тогда почему существуют разные kernel function?

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

(z1-z2)^2+(x1-x2)^2 - это и есть квадрат inner produc-та, здесь просто корень не взят.

upd: торможу малость, не нужен тут корень.

Тут в первой и четвертой лекциях по этой теме кое-что есть:

http://www.compvision.ru/forum/index.php?showtopic=864

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

<x,z>= x1*z1+x2*z2

|<x,z>|= sqrt((z1-z2)^2+(x1-x2)^2)

так?

(<x,z>)^2 =(x1*z1+x2*z2)^2 и далее по тексту ,т.е. я всё еще н епонимаю какое отношение это имеет к метрике |<x,z>|

http://en.wikipedia.org/wiki/Euclidean_space

тут вообще нету про |<x,z>|

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

Похоже это и есть ядро.

Ядро это некая новая метрика, вводимая для удобства.

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

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

вообщем я решил пока оставить gmmreg и посмотреть KCReg

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

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

а только ограничение на кол-во итераций.

используют fminsearch возможно есть что то побыстрее?

и я честно говоря не понял чем отличается

MaxFunEvals

Maximum number of function evaluations allowed

MaxIter

Maximum number of iterations allowed

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

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

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

еще вроде хорошая книжка Численные методы. Использование MATLAB Автор: Мэтьюз Дж. Г. и др.

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

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

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

Сохранять графики в матлабе можно командой print

http://www.mathworks.com/help/matlab/ref/print.html

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

http://home.hiroshima-u.ac.jp/tamaki/study/cuda_softassign_emicp/softassign_and_emicp_on_gpu.pdf

интересный метод нахождения матрицы поворота и смещения на слайде 9, интересно расширяется ли он на перспективные преобразования?

похоже метод называется horn's method (quaternion)

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

http://www.mathworks.com/matlabcentral/fileexchange/26186-absolute-orientation-horns-method/content/oldstuff/absorientParams2D_nobsxfun.m

вообще говоря, кто мешает поставить вместо min. sum_i ||s*R*A(:,i) + t - B(:,i)||^2

те же перспективные преобразования?

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

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

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

http://ru.wikipedia.org/wiki/%D0%A1%D0%B2%D1%91%D1%80%D1%82%D0%BA%D0%B0_(%D0%BC%D0%B0%D1%82%D0%B5%D0%BC%D0%B0%D1%82%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B8%D0%B9_%D0%B0%D0%BD%D0%B0%D0%BB%D0%B8%D0%B7)

еще непонятно как они реализуют дискретный случай- там еще у них в документе интеграл без значков это значит от -inf до inf?

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

кстати еще возникла идея, что то типа брутфорсного перебора.

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

есть объект - небольшой набор точек.

делаем что то типа ранзака, берем рэндомно из сцены точки и из образца делаем преобразование, накладываем, смотрим метрику.

метрика допустим евклидова или как в документах выше.

а вот как определять само преобразование? если взять 4 точки например для перспективного, то т.к. мы работаем не с идеальными образцами, то даже если мы взяли нужные пары точек, то получим матрицу гомографии с ошибкой и остальная часть точек плохо наложится и мы даже и не сможем получить хорошего наложения если переберем все точки(такой метод я уже пробовал ничего хорошего не получится для реальных ситуаций), значит надо брать переопределенную систему через МНК(но я так и не понял как его реализовать для точек, причем похоже, что и МНК и horn's method работают только для аффинных, т.к. в этом случае мы имеет линейную систему, а мне надо чтобы поддерживало и перспективные).

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

п.с. про МНК еще тут нашел

http://courses.graphicon.ru/files/courses/vision/2011/lectures/cv2011_06_fitting.pdf

Least squares and the singular value decomposition

http://users.ecs.soton.ac.uk/im/bari08/svd.pdf

еще полезное

http://www.slideserve.com/luella/random-sample-consensus-a-paradigm-for-model-fitting-with-application-to-image-analysis-and-automated-cartography

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

Знаком интеграла без пределов обозначают неопределенный интеграл.

По поводу свертки, не зря же матрица коэффициентов называется "ядро свертки".

Только "ядро" понятие значительно более широкое.

Чистым брутфорсом не получится, слишком много точек.

RANSAC и прочие -SAC годятся при малых отклонениях конфигурации объектов.

МНК - при известном взаимном соответствии точек и линейной трансформации.

Разные минимизаторы тоже требуют известного взаимного соответствия точек.

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

Поделиться сообщением


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

ну это то понятно, но чтобы его вычислить ведь надо что то туда подставить.

Чистым брутфорсом не получится, слишком много точек.

RANSAC и прочие -SAC годятся при малых отклонениях конфигурации объектов.

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

Не понял, что значит при малых отклонениях.

а вот еще

http://www.cs.ubc.ca/~lowe/papers/pami91/pamilatex.html

а что тогда остается глобальная оптимизация?

в матлабе попробовал globalsearch с ограничениями, работает лучше чем fminsearch без ограничений(т.к. вроде их задать нельзя)

единственное, что напрягает, что работает всего 1 ядро. вроде там есть что то типа запускаем N локальных солверов из рэндомных точек(multiplestart как то так) и они работают параллельно, но у меня ядра не были загружены почему то.

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

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

Я не пробовал распараллеливать матлабовские скрипты, но похоже что это можно делать при помощи parfor вместо for и task objects, ну и GPU поддерживается.

http://www.mathworks.com/products/parallel-computing/description4.html

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

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

если брать только сдвиг и поворот то работает прилично, но вот globalsearch почему то не всегда даёт глобальный минимум.

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

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

http://www.ri.cmu.edu/pub_files/pub4/tsin_yanghai_2003_2/tsin_yanghai_2003_2.pdf

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

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

с шейп контекстом наверно сработает.

а по поводу использования минимизатора с ксрег, получается, что всё упирается в кол-во точек.(если ничего не делать, то для картинки 3к х 4к получается ~1-3кк точек)

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

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

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

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

Создайте учётную запись или войдите для комментирования

Вы должны быть пользователем, чтобы оставить комментарий

Создать учётную запись

Зарегистрируйтесь для создания учётной записи. Это просто!

Зарегистрировать учётную запись

Войти

Уже зарегистрированы? Войдите здесь.

Войти сейчас


  • Сейчас на странице   0 пользователей

    Нет пользователей, просматривающих эту страницу

×