shape matching

[mrgloom 242]

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

надо найти похожесть этих контуров -> вычислить какую то метрику.

вопрос как это сделать быстрее?

все что пришло в голову это отскейлить (или даже пропустить этот шаг),

повернуть вертикально\горизонтально - зная оси описывающего элипса.

(+сделать так чтобы более легкая половина контура смотрела вверх)

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

(через методы оптимизации)

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

[Smorodov 579]

Может в сторону fourier descriptors посмотреть? Они и сгладить до необходимой степени помогут. И сохранять контуры в компактном виде.

Еще скорее всего пригодится понятие Procrustes distance.

ЗЫ: Я видел документы, в которых перед сравнением контуров, их представляли в полярных координатах, при этом они становились похожи на обычные графики. Похожие фигуры, повернутые друг относительно друга представлялись похожими графиками, сдвинутыми друг относительно друга.

ЗЫЗЫ: ну и книжку поищите Фурман Я.А. "Введение в контурный анализ"

[mrgloom 242]

а какие у fourier descriptors недостатки?

п.с. shape marching->shape matching ошибка в названии.

[Smorodov 579]

По поводу недостатков не задумывался, с критикой Фурье-разложения не сталкивался.

Вот еще ссылка, думаю будет интересна: http://habrahabr.ru/blogs/image_processing/118486/#habracut

[mrgloom 242]

я скорее не про критику фурье разложения, а про область применимости.

т.е. фурье дескрипторы подходят только для сравнения объект-объект? (хотелось бы сравнивать объект - несколько перекрывающихся объектов)

как обстоит дело с деформациями? частичным отсутствием частей? шумом?

вот пример где пробуют сопоставить 2 набора точек (только тут нет деформаций)

http://rcvlab.ece.queensu.ca/~qridb/lsdPage.html

вот тут обзор многих подходов

http://igitur-archive.library.uu.nl/math/2007-0118-201351/hagedoorn_99_state-of-the-art.pdf

http://www.cs.duke.edu/courses/spring07/cps296.2/course_projects/nihshanka_proj.pdf

хотелось бы найти наиболее общий.

[mrgloom 242]

вот вроде бы даже, то что нужно

Partial shape matching http://longbin.org/ShapeMatching.aspx

и

shape matching with partial occlusion

http://www.mit.edu/~jglov/rss08-jg.pdf

в деформациях пока не разобрался.