Рис.7

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

где

b_i, d_i -	параметры, определяющие положение контурной точки в собственной системе координат аппроксимирующего отрезка (рис.8); эти параметры определяются по координатам точки x_i, y_i с помощью преобразований
	b_i = (x_i - X)*cos(A) + (y_i - Y)*sin(A),
	d_i = -(x_i - X)*sin(A) + (y_i - Y)*cos(A);

Рис.8

X,Y -	координаты центра отрезка;
A -	угол наклона отрезка;
P =	P1, если b_i >= 0 (кривизна правой ветви), P2, если b_i < 0 (кривизна левой ветви);
B =	B1, если b_i >= 0 (длина правой ветви), B2, если b_i < 0 (длина левой ветви);
D -	полуширина функции принадлежности.

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

Контурное изображение, на котором проверялась принципиальная работоспособность этой процедуры, показано на рис.10a.

Рис.10a

Размер исходного полутонового изображения равен - 290 * 196 точек. Для выделения контурных границ использовался известный оператор Хюккеля [5,6]. Всего было выделено приблизительно 800 контурных точек. Начальные позиции прилегающих отрезков определялись узлами регулярной сетки с шагом в 12 точек растра (соображения, на основе которых задавался этот шаг, излагаются в Приложении_2.2.A). Значения остальных параметров принимались следующими: B1 = B2 = 5, D = 2.5, A = 0, P1 = P2 = 0.

Начальные приближения имели самые различные позиции относительно аппроксимируемых участков. Тем не менее, в подавляющем большинстве, из 384-х имевших здесь место запусков, процедура градиентной "подстройки" находила максимум белл-сходства, определяющий реальный прилегающий отрезок (рис.10b).

Рис.10b

Не более 10 пусков привело к ошибочной аппроксимации: либо к захвату случайного скопления контурных точек, не похожего на отрезок линий (пятну), либо к захвату нескольких близко расположенных отрезков. Такие случаи определялись по явному нарушению процесса поиска - чрезмерному увеличению длины (ширины) получаемого отрезка или числа шагов, либо по критерию заполненности результирующего отрезка контурными точками [ссылка ниже].

Проведенные таким образом эксперименты показали, что максимумы, отвечающие искомым отрезкам, имеют чистые склоны. Действительно, на этих склонах нет каких-либо выбросов (они поглощаются основными экстремумами), в которых могла бы "заблудиться" градиентная процедура. Эти эксперименты доказали принципиальную возможность получения описания контурных фигур в терминах прилегающих (касательных) отрезков, соответствующих нашим интуитивным представлениям.

Вместе с тем, анализ поведения градиентной процедуры, первоначально используемой для поиска локальных максимумов белл-сходства [2], показал, что в окрестностях своих максимумов (т.е. на заключительных этапах поиска) функция сходства имеет вид длинных, узких хребтов, вытянутых вдоль осевых линий контурных границ. При этом аппроксимирующие отрезки могут долго колебаться в направлении, поперечном к этим линиям, с очень медленным продвижением в продольном направлении. Для быстрого прохождения этих хребтов в [3] было предложено смещать в процессе поиска центральную точку аппроксимирующего отрезка не по осям системы координат изображения, а вдоль и поперек текущего направления его осевой линии. Так как осевая линия аппроксимирующего отрезка постепенно подстраивается под осевую линию представляемого участка контурной границы, продольное движение отрезка осуществляется непосредственно вдоль осевой линии упомянутых хребтов. Такая организация процедуры поиска локальных максимумов меры сходства позволила довольно быстро и четко проходить вышеупомянутые хребты этой меры. Подробнее о выборе величины шагов сказано в Приложении_2.2.B.

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

В соответствии с прореженным представлением был модифицирован и критерий заполненности прилегающих отрезков [Приложение 2.2.C].

Контурное изображение, на котором проверялась работоспособность усовершенствованной процедуры представления контурных границ прилегающими отрезками показано на рис.13. Размер исходного полутонового изображения - 216 х 216. В данном случае, диаметр входного участка оператора Хюккеля равнялся семи (7) точкам растра. Перекрытие при отслеживании контуров равнялось половине диаметра этого участка. Следовательно, шаг между "прореженными" контурными точками - 3.5. Контуры приведенного изображения содержат 215 точек.

Рис.13

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

Предложенная организация процедуры градиентного поиска, прореживание контурных точек и выбор начальных приближений, определяемых по наилучшим участкам контурных границ, позволили существенно повысить устойчивость процесса описания этих границ в терминах прилегающих отрезков. Резко сократилось и необходимое счетное время. Представление контурной картины, показанной на рис.13, прилегающими отрезками потребовало 50 с счетного времени, а картины того же порядка сложности, показанной на рис.10 (первая серия экспериментов [2]), с помощью первоначального варианта этой процедуры - свыше 20 мин.

Проведенные эксперименты подтвердили возможность практической реализации концепции прилегающих отрезков - отрезков с нечеткими концами.

В Приложении_2.2.D рассматриваются некоторые тактические вопросы организации процесса поиска локальных максимумов нечеткой меры совпадения.

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

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

Примененный способ предварительного выбора контурных точек рассчитан на работу в условиях полного отсутствия информации о топологических связях между отдельными элементарными контурами. Однако, как показывает опыт работы с реальными изображениями, контурные границы отслеживаются с помощью локальных операторов на довольно протяженных участках. В связи с этим представляется перспективным рассмотрение связанных участков контурных границ взамен изолированных точек из некоторой области. Кстати, это могло бы облегчить и аппроксимацию близко расположенных контуров.

Использование оператора Хюккеля для нахождения контурных границ анализируемых изображений обусловлено необходимостью упрощения экспериментов. По всей видимости, предлагаемый метод аппроксимации будет работоспособен и при использовании более простых операторов, например при использовании упрощенного оператора Хюккеля [18], оператора Собела, а возможно, и простейшего оператора Робертса [7]. Кроме того, просматривается возможность построения оператора, аналогичного по качеству результатов (и по сути, лежащей в основе функционирования) оператору Хюккеля, но гораздо более быстродействующего.

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

Все вычисления проводились в формате чисел с плавающей запятой. Нет принципиальных трудностей в их переводе в целочисленный вид. При этом байтного (или чуть большего) представления было бы достаточно в большинстве случаев. Резко сократить счетное время здесь позволит очевидная замена непосредственных аналитических вычислений на табличное задание колоколообразных (одномерных) функций и их производных. Необходимые при этом произведения также можно определять таблично. Объем таких таблиц, хотя и велик, но не превышает технических возможностей используемых вычислительных средств (для хранения этих таблиц требуется память порядка нескольких десятков килобайт).

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

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

Рис.14

Причем такой наезд обусловлен не шириной функции принадлежности, как это было в случае среднеквадратичной аппроксимации контурных границ прямолинейными отрезками. Во избежание возможного проявления тонкостей структуры функции сходства, вызванного прореживанием контурных границ, минимальная ширина функции принадлежности ограничивался размером, приблизительно равным шагу между прореженными контурными точками (D = 1.5). Эксперименты показали некритичность получаемых результатов к выбору этого размера (пробные эксперименты проводились при D_min = 0.5 - 2.5).

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

В работе [3] для ограничения наезжающей тенденции парабол было предложено двигаться в сторону ветви меньшей кривизны. Однако, как оказалось, при этом требуется противодействие сползанию прилегающих отрезков к концам представляемых участков при нечетко выраженных максимумах прямолинейности (рис.15). Корректно решить эту задачу не удалось, - не удалось однозначно подобрать какую-либо стратегию переключения продольной движущей силы, которая позволяла бы одновременно избежать сползания аппроксимирующих отрезков и наездов на плавные перегибы.

Рис.15

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

где

d_i -	отклонение контурной точки от прямой линии, касающейся прилегающего отрезка в его центральной точке, т.е. от продольной оси его собственной системы координат;
U -	полуширина прямолинейного коридора занимаемого отрезком (рис.16).

Рис.16

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

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

Вместе с тем, и здесь четкого решения задачи продольной фиксации аппроксимирующих отрезков получить не удалось. При использовании ограничивающих прямолинейных коридоров отдельный аппроксимирующий отрезок может потерять чувствительность к концам представляемой контурной линии. Это может случиться, если эта линия имеет достаточную протяженность и кривизну, и потому может выйти за продольные границы ограничивающего коридора. Увеличивать же ширину коридора нельзя, - начнет сказываться тенденция параболы наезжать на плавные перегибы. Примером таких контурных линий являются контурные границы отвечающие пятке стельки (рис.13), а также боковым сторонам утюга, когда контуры этого объекта представлены достаточно полно (рис.17).

Рис.17

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

Следует обратить внимание на то, что ограничение ширины прямолинейных коридоров занимаемых аппроксимирующими отрезками приводит и к соответственному обрыву этих отрезков (на поперечных границах коридора). В результате контурная линия, которая без поперечных ограничений могла быть представлена одним отрезком, будет представлена несколькими (см., например, отрезки 4, 15 на рис.13).

Вероятно, разрешить проблемы продольной фиксации аппроксимирующих отрезков могло бы использование таких кривых (в качестве эталонов простейших отрезков), кривизна которых возрастает к их концам и минимальна в центре (например, кривых эллиптического типа). По-видимому, аппроксимация такого типа способна дать объективное (в нашем интуитивном понимании) разбиение контурных границ на участки минимальной кривизны, но этот вопрос требует дальнейших исследований.

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

Несмотря на определенные успехи, окончательного решения задачи продольной фиксации аппроксимирующих отрезков, получить не удалось. Не удалось, например, зафиксировать эти отрезки на боковых сторонах утюга, а также на пятке стельки (см. рис.13). Конечно можно рассматривать, что эти примеры относятся к некоторому вырожденному случаю - слишком плавных кривых. Тем не менее в приведенных примерах демонстрируется принципиальная зыбкость грани, позволяющей четко отличать случай, когда контур должен представляться целостной дугой, а когда - составной (а именно, как аппроксимирующие отрезки должны в истинном случае располагаться на контуре). В зависимости от начальных приближений, случайных помех, а также неидеальности формы самих объектов можно получать различные представления - разбиения - контурных линий, отвечающих тождественным элементам наблюдаемых объектов.

Эта ситуация усугубляется и тем, что на практике полное выделение контурных границ встречается сравнительно редко. Выделяются обрывки линий. Плохо отражаются затемненные участки (или сверхосвещенные). Некоторые участки могут в принципе отсутствовать, - по причине возможного частичного перекрытия другими объектами. Последнее обстоятельство представляет собой одну из характернейших особенностей решения задачи распознавания объектов в реальных условиях. В общем случае, аппроксимирующие отрезки не фиксируются на определенных местах в принципе.

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

Рис.18 иллюстрирует это положение для простейших случаев, в частности, - неполного выделения прямолинейных контуров (рис.18a).

Рис.18a,b,c,d

Здесь выделенные отрезки отвечают углу некоторой фигуры. Этот угол может скользить относительно каждого из выделенных отрезков (рис.18b,c), и только сочетание таких отрезков ловит этот угол четко (рис.18d). Аналогичный пример для криволинейного угла (утюга), который, например, фиксируется, по крайней мере двумя аппроксимирующими (прилегающими) отрезками (и тем самым определяет эти отрезки как определенные части контура искомого объекта), представлен на рис.18e.

Рис.18e

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

Решению этой задачи и был посвящен следующий этап данной работы. На этом этапе был разработан метод [19], интерпретирующий задачу позиционного обнаружения как накопление гипотез [3], который в случае объектов определенной - фиксированной - формы позволяет конструктивно решать задачу позиционного обнаружения в условиях скользящего первично-элементарного сопоставления контуров.