Рис.19a,b

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

Очевидно, что в центре образуется многократное (по числу сторон) наложение эталонного треугольника (рис.19c), которое и определяет, в данном случае, искомое решение задачи позиционного обнаружения.

Рис.19c

Это наложение можно регистрировать без какого-либо непосредственного сопоставления самих контуров. Достаточно нарисовать на эталонном треугольнике некоторый единичный базисный вектор(см. рис.19a), и регистрировать взаимоналожение этого вектора (см. рис.19c).

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

Рис.19d

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

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

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

Рис.20

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

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

Таким образом, задача позиционного обнаружения плоских объектов сводится к поиску пересечений подобных кривых, отвечающих отдельным аппроксимирующим отрезкам. Пример для двух отрезков показан на рис.21. Здесь xOy - система координат изображения. По вертикальной оси откладывается угол между базисным вектором и горизонтальной осью Ox.

Рис.21

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

Следует отметить, что рассматриваемый алгоритм не предполагает обязательной непрерывной гладкости контурных границ искомых объектов. Для работоспособности алгоритма необходимо, чтобы число особых точек этих границ (углов) было конечным. Объекты не должны напоминать ежа или облако. Требуется только наличие отдельных гладких участков. Это, как правило, обеспечивается самой технологией операций по формированию объектов: резанием, строганием, точением, протягиванием, ковкой и т.п., а также самой физикой природы: силами инерции, поверхностного натяжения; закономерностями процессов скалывания, растрескивания и т.д. и т.п. Эталонная кривая строится по таким гладким участкам и представляет собой совокупность отдельных кривых (пространства искомых параметров), отвечающих этим участкам.

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

Пусть имеется множество гипотез H о некотором физическом явлении и множество фактов T, которые могут быть зарегистрированы при исследовании этого явления. При этом известно, что каждая гипотеза h H подтверждается определенным подмножеством фактов T(h) T. В дальнейшем каждое такое подмножество будем называть фактограммой (фактографом) данной гипотезы.

Обычно, задача выбора гипотезы h_o H, соответствующей некоторой совокупности фактов T_o T, далее называемой множеством реализовавшихся фактов, ставится и решается как задача поиска гипотезы, фактограмма которой имеет максимальное сходство с этим множеством:

где

S - функция, определяющая сходство между совокупностями фактов.

В простейшем случае сходство определяется числом элементов, одновременно принадлежащих обеим сравниваемым совокупностям:

где

E(t,T(h)) =

1, если t T(h); 0, если t T(h).

Можно сказать, что в данном случае производится поиск гипотезы, ПОДТВЕРЖДАЕМОЙ максимальным количеством реализовавшихся фактов.

Теперь заметим, что ту же задачу поиска гипотезы, соответствующей реализовавшимся фактам, можно ставить как задачу поиска гипотезы, ПОРОЖДАЕМОЙ одновременно наибольшим количеством этих фактов:

где

H(t) =	{h|h H, t T(h)} - подмножество гипотез, порождаемых отдельным фактом, т.е. подтверждаемых этим фактом. Далее каждое такое подмножество будет называться гипограммой (гипографом) конкретного факта. Рис.22 образно иллюстрирует суть введенных понятий.
E^(h,T(t)) =	1, если h H(t); 0, если h H(t).

Рис.22

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

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

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

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

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

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

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

Содержательный подход к задаче позиционного обнаружения как задаче поиска наложения модельных изображений искомых объектов, порождаемых независимо отдельными фрагментами (признаками) этих объектов [19], непосредственно подсказывает технику параметризации. Очевидно, в качестве искомых параметров следует использовать параметры простейших конфигураций структурных элементов, жестко связанных с эталоном искомого объекта и позволяющих полностью определить его положение и ориентацию. При этом суть задачи обнаружения сводится к поиску наложения таких конфигураций. В случае плоских объектов базисной конфигурацией является любой единичный вектор, приписанный вначале эталону объекта. Если меняется масштаб, то этому вектору можно приписать соответствующее изменение длины. В случае объемных тел базисной структурой могут быть два единичных вектора, исходящих из одной точки. Положение такой конструкции определяется шестью параметрами: три задают координаты точки приложения, два - ориентацию главного вектора этой конструкции, и один - вращение вспомогательного вектора вокруг главного. Можно использовать и углы Эйлера. В этом случае базисная конструкция будет представлять собой тройку взаимно перпендикулярных векторов, исходящих из одной точки. Во всех этих случаях отдельная гипограмма будет определяться по совокупности положений базисной структуры, которые она может занимать относительно данного первичного признака (фрагмента) искомого объекта.

Предлагаемая онтологическая схема представляет собой обобщение и попытку более глубокого выяснения сути подобных алгоритмов. Прежде всего, эта схема непосредственно показывает эквивалентность результатов, получаемых с помощью той или иной методики позиционного ообнаружения объектов. Ярким примером этого является работа матричного дешифратора, которую можно рассматривать и как параллельное сравнение с эталоном (заданным на адресном регистре) и как поиск пересечения (ячейки сгущения) гипограмм, задаваемых адресными шинами. Следует отметить, что первоначальным толчком в направлении идеи накопления гипотез послужили идеи Гузмана [30] о выдвижении глобальных гипотез на основе локальных данных, а для идеи наложения моделей - идея Уолтца о поиске непротиворечивой (совместимой) пометки контурных ребер [31].

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

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

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

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

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

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

Если определять эти направления по коротким отрезкам (для того чтобы обеспечить общую универсальность алгоритма, независимо от формы объектов), то в реальных условиях случайные колебания этих отрезков будут приводить к существенным колебаниям базисного вектора. Например, если использовать элементы контура получаемые непосредственно с помощью оператора Хюккеля [5, 6] (как это предлагалось в [23]). В этом случае, колебания концов получаемых элементарных контуров с амплитудой плюс или минус одна точка, при диаметре входного участка в 7 точек растра, на расстоянии в 50 точек (что соответствует среднему расстоянию до центра фигуры диаметром в 100 точек), приводят к колебаниям базисного вектора с размахом в 15 точек растра (50/(7/2)).

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

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

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

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

Размер зон по оси, определяющей наклон базисного вектора, выбирается согласно условию приблизительной эквивалентности сдвига ( L)и поворота ( A) эталонной фигуры: A= L/R, где R - радиус объекта. Эта величина вычисляется как среднеарифметическое длин радиусов-векторов, направленных из центра тяжести к каждой из точек контурной границы.

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

Гипограммы задаются поточечно с шагом, соизмеримым с линейными размерами зон. Поэтому, маркировка, в области пересечения нескольких гипограмм, может не дать одной зоны, которую одновременно пометили бы все эти гипограммы. Для преодоления подобных случайностей дискретной пометки, в программе, реализующей алгоритм, производится усреднение получаемых картин в пределах соседних зон. Для каждой помеченной зоны вычисляется ее вес - арифметическая сумма содержимого соседних зон. Содержимое зоны - это число пометивших ее гипограмм. Соседними считаются - 27=3х3х3 зон, включая центральную. Отдельное сгущение регистрируется как зона, вес которой превосходит веса своих соседей. Центральная точка такой зоны принимаются в качестве точки сгущения. В целом, такая операция названа сглаживанием.

В программе, реализующей алгоритм, запоминается информация только о помеченных зонах. Для этого отводится некоторый массив. Запись исполняется с помощью хеширования [Приложение_3.5.A].

Эталонные гипограммы распознаваемых предметов - стельки, утюга и футляра от очков (см. рис.13) - строились по их отдельным изображениям. Размер зон пространства искомых параметров по осям, определяющим положение точки приложения ( L) равнялся восьми (8) точкам растра. По оси, определяющей наклон базисного вектора ( A), равнялся 0.1 радиана. Линейный размер зон выбирался приблизительно равным минимальному расстоянию на котором различимы два параллельных контура. В данном случае это расстояние - разрешение - определялось диаметром входного района оператора Хюккеля, с помощью которого выделялись элементы контурных границ. Диаметр этого района составлял 7 точек растра [2.2.]. Конкретное значение "8" было выбрано как ближайшая степень двойки, что существенно ускоряет операцию определения номера зоны (вместо деления - сдвиг...). Размер зон по углу выбирался согласно выше указанному критерию эквивалентности сдвига и поворота для фигур со средним радиусом в 50 точек растра (средний радиус объектов в данном случае).

При таких размерах зон эталонные гипограммы искомых объектов содержали соответственно 85, 60 и 45 точек.

В процессе накопления гипотез о положении стельки (на рис.13) было помечено 1784 зоны. Из них: четырехкратно - 1, трехкратно - 3, двукратно - 47, однократно - 1733 (время накопления гипотез 1,5 с; производительность ЭВМ - 1 миллион операций с плавающей запятой). Среди этих зон после операции сглаживания было зарегистрировано 18 отдельных сгущений (время сглаживания 1,0 с). На рис.23 показано соотношение весов этих сгущений.

Рис.23

Гистограммы зон максимального веса наиболее мощных сгущений представлены на рис.24.

Рис.24

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

Рис.25

На рис.25 жирными штрихами показано положение эталона искомого объекта, определяемое центральной зоной (центральной точкой этой зоны) наиболее мощного сгущения (рис.24a). На этом же рисунке тонкими штрихами показаны положения эталона, определяемые двумя наиболее мощными ложными сгущениями (см. рис.24b,c).

В [Приложении_3.5.B] рассматривается вопрос общей целесообразности операции сглаживания.

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

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

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

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

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

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

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