Jump to content
Compvision.ru
Sign in to follow this  
mrgloom

ICP(Iterative Closest Point)

Recommended Posts

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

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

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

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

Share this post


Link to post
Share on other sites

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

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

и еще тут

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

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

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

Share this post


Link to post
Share on other sites

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

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

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

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

Share this post


Link to post
Share on other sites

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

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

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);

}

Share this post


Link to post
Share on other sites

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

Share this post


Link to post
Share on other sites

по сути я понял ,что всё строится на понятии 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

Share this post


Link to post
Share on other sites

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

Share this post


Link to post
Share on other sites

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

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

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

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

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

Share this post


Link to post
Share on other sites

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

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

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

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

Share this post


Link to post
Share on other sites

<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>|

Share this post


Link to post
Share on other sites

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

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

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

Share this post


Link to post
Share on other sites

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

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

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

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

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

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

MaxFunEvals

Maximum number of function evaluations allowed

MaxIter

Maximum number of iterations allowed

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

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

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

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

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

Share this post


Link to post
Share on other sites

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

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

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

Share this post


Link to post
Share on other sites

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

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

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

Share this post


Link to post
Share on other sites

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

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

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

Share this post


Link to post
Share on other sites

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

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?

Share this post


Link to post
Share on other sites

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

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

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

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

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

а вот как определять само преобразование? если взять 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

Share this post


Link to post
Share on other sites

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

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

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

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

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

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

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

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

Share this post


Link to post
Share on other sites
Знаком интеграла без пределов обозначают неопределенный интеграл.

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

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

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

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

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

а вот еще

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

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

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

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

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

Share this post


Link to post
Share on other sites

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

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

Share this post


Link to post
Share on other sites

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

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

Share this post


Link to post
Share on other sites

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

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

Share this post


Link to post
Share on other sites

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

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

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

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

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

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

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this  

  • Recently Browsing   0 members

    No registered users viewing this page.

×