Make your own free website on Tripod.com
  English
2.2.В. Особенности градиентной процедуры поиска локальных максимумов белл-сходства.

В ходе данной работы было опробовано несколько градиентных процедур поиска локальных экстремумов. Их главное средство заключалось в разворачивании системы координат, отвечающей смещению центральной точки аппроксимирующего отрезка, вдоль хребтов функции сходства. Характерный пример - процедура, описанная в [34]. Однако, использование таких универсальных, а потому довольно громоздких процедур не оправдывает себя в ситуации, когда возможен предварительный учет специфики переменных, упрощающий поиск экстремума. Специфика переменных заключается здесь в четко выраженной их иерархии. В первую очередь подстраиваются угол и поперечное положение прилегающего отрезка, за ними - параметры ветвей. И только затем осуществляется движение в продольном направлении.

Такая специфика переменных позволила на втором этапе экспериментов эффективно использовать градиентную процедуру, в которой движение по всем переменным восьмипараметрической меры сходства осуществляется одновременно и в принципе независимо. В процессе поиска возможны задержки (пропуски шагов по некоторым переменным), если параметры с более высоким приоритетом еще не подстроились. В окончательном варианте использовалась следующая система приоритетов: (+,A), (P1,P2), (D), (B1,B2,=), где - "+" и "=" обозначают движения в поперечном и продольном направлениях соответственно. Шаг по какой-либо переменной увеличивается наполовину (с учетом ограничения на максимальную величину - см. далее), если он исполняется в том же направлении, что и предыдущий, и уменьшается в противном случае. При этом считается, что подстроились те переменные, шаг по которым стал меньше, чем 1/4 от величины максимально допустимого по данной переменной.

Последние величины выбирались из самых общих соображений так, чтобы в результате каждого шага новый аппроксимирующий отрезок не слишком выходил за границы старого. Шаги в продольном направлении (и по длине ветвей) ограничивались величиной B/2, а в поперечном - D/2. Шаги по углу и кривизне не должны были колебать концы отрезка на величину большую чем D/2, т.е.  A*MAX(B1,B2)/0.7 и  P*(B/0.7)/2 не должны превышать D/2. Во избежание проявлений дискретности задания анализируемых контуров величина параметра D ограничивалась снизу величиной, изменяющейся в диапазоне 0.5 - 2.5 расстояний между соседними точками растра. Сверху параметр D ограничивался величиной B/2.

Конкретно такие ограничения организованы так, что при подходе к одному из них следующий шаг разрешается делать только на половину расстояния до этого ограничения. Этим достаточно просто обеспечивается возможность увеличения шага при необходимости продвижения в обратном направлении. Начальные шаги по отдельным компонентам выбирались равными половине их максимально возможных величин. При этом начальные значения параметров B и D принимались равными 10 и 4 соответственно, а максимально допустимая величина шага по D равной 0.5. Процедура поиска очередного максимума меры сходства останавливалась, когда шаги по всем переменным становились меньшими, чем 0.2 их максимально допустимых величин.

Как правило, поиск максимумов, отвечающих контурным отрезкам, требовал в среднем 60 - 80 шагов по углу наклона и положению в поперечном направлении при 8 - 12 шагах в продольном направлении.