Страница 3 из 4 Обратите внимание на то, что неотъемлемым свойством этого определения контекста формы является его инвариантность к операции переноса, поскольку все изменения выполняются по отношению к точкам в объекте. Для достижения инвариантности к операции масштабирования все радиальные расстояния нормализуются путем деления на среднее расстояние между парами точек. Контексты формы позволяют решить задачу установления соответствия между двумя аналогичными, но не идентичными формами, наподобие тех, которые показаны на рис. 24.20, а, б. Контексты формы являются разными для различных точек на одной и той же форме S, тогда как соответствующие (гомологичные) точки на подобных формах S и S', как правило, имеют одинаковые контексты формы. Таким образом, задача поиска соответствующих друг другу точек двух форм преобразована в задачу поиска партнеров, имеющих взаимно подобные контексты формы. Точнее, рассмотрим точкуна первой форме и точкуна второй форме. Допустим, что обозначает стоимость согласования этих двух точек. Поскольку контексты формы представляют собой распределения, выраженные в виде гистограмм, вполне обоснован подход, предусматривающий использование расстояния, следующим образом: где обозначают k-й сектор нормализованных гистограмм в точках и. Если дано множество стоимостейсогласования между всеми парами точек i на первой форме и точек j на второй форме, то может быть принято решение минимизировать общую стоимость согласования с учетом ограничения, что это согласование должно выполняться на основе взаимно-однозначного соответствия. Это — пример задачи поиска паросочетаний взвешенного двухдольного графа, которая может быть решена за время с использованием так называемого венгерского алгоритма (Hungarian algorithm).
|