3.2.5Выделение корневой структуры

Рис. 3.8: Этап 2 - Выделение корневой структуры

На данном этапе большой массив дифракционных паттернов был проанализирован и отложен в сторону. Почти сразу ему на смену пришли таблицы значений (look-up tables) координат общих дуг для каждого паттерна и профилей интенсивностей вдоль каждой из дуг для всех паттернов. На основе этого был построен полносвязный граф корреляционных соотноешний между паттернами для всех рассматриваемых значений углов { , , }, а также стало возможным тривиальное вычисление корреляционной величины путем интерполирования между элементами этого графа (который также является равномерным массивом).

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

34

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

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

≈ ( Φ Θ Ψ)

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

Первый и самый тривиальный метод поиска абсолютных ориентаций состоит в следующем:

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

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

3.Для всех последующих паттернов проделать аналогичные действия.

4.Использовать полученные значения ориентаций как искомые.

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

≈

35

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

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

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

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

2.Качественная подвыборка ядра будущей пространственной системы (корневой структуры), - фиксированное число паттернов.

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

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

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

1.Метод “Наращивания” - итеративное добавление очередного паттерна в общуюю структуру с учетом всех предыдущих паттернов.

2.Метод “Опорного множества” - выборка набора опорных изображений с лучшими попарными ориентациями

36

3.Метод “Клика” - поиск максимального полносвязного подграфа (представлен впервые)

4.Метод “Триплеты” - использование элементарных связок более высокой размерности (представлен впервые)

Рассмотрим каждый из них более подробно.

Метод “Опорного множества”.

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

Алгоритм поиска ядра:

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

Критерий выбора:

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

Формула итерационной сложности:

	+ ( − ) ,
=

где - сложность полного перебора между двумя паттернами, обратно зависимая от шагов углового перебора { , , }, а - сложность сравнения паттерна с корневой структурой.

Вывод:

возросшие затраты на определение корневой структуры и определение оптимальной ориентации каждого элемента относительно корневой структу-

37

ры. Однако такой метод существенно более правдоподобен в условиях присутствия шумов.

Метод “Клики”.

Данный метод предлагается впервые. Алгоритм поиска ядра:

Для поиска корневой структуры в этом методе предлагается установить

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

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

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

Критерий выбора:

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

38

Формула итерационной сложности:

≈		∏
		_ ( ) + ( − ) ,
		=2

где _ ( ) - сложность нахождения нового элемента клики, в зависимости от ее размера.

Вывод:

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

Метод “Триплеты”.

Данный метод предлагается впервые. Алгоритм поиска ядра:

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

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

всебе самосвязную и самосогласованную пространственную ориентацию

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

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

39

Критерии выбора:

∙первый триплет выбирается случайно, его ориентация берется за начальную.

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

Формула итерационной сложности:

≈ + ( − 1) ,

2

где - число триплетов, а вторая половина уравнения соответствует сложности метода “наращивания”.

Вывод:

Данный метод реализует в себе пространственные свойства связности данных с достаточно вычислительно быстрым алгоритмом восстановления пространственных ориентаций.

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

40