| (33) |
| (34) |
, 
,
.3. В соответствии с определением 
-диффузии
| (35) |
| (36) |
, 
,
, где
|
,4. С учетом неравенств (33) и (34) для любой дужки 
справедлива следующая цепочка равенств и неравенств.
|
.5. Для всех остальных дужек 
, не содержащих вершину справедливо неравенство
,
так как веса этих дужек в процессе 
-диффузии не меняются. Лемма доказана.
Лемма 10. Пусть 
- весовая функция, такая, что вес каждой дужки лежит в пределах
| (37) |
| (38) |
, 
, 
, 
, Пусть 
. В таком случае веса дужек лежат в пределах
| (39) |
| (40) |
, 
, Доказательство. 1. Для доказательства (39) достаточно доказать, что -диффузия не нарушает неравенства (37) при произвольном 
, 
. Выберем произвольно и и зафиксируем их для дальнейшего рассмотрения. Пусть и 
- две весовые функции, полученные до и после -диффузии, причем для весов выполняется неравенство (37).
2. В соответствии с -диффузией веса дужек определяются выражениями (35) и (36), откуда следует, что
|
.Отсюда, с учетом условия (37), следует, что неравенство
| (41) |
выполняется для всех дужек, содержащих вершину .
3. Веса дужек, не содержащих вершину , также удовлетворяет неравенство (41), так как веса этих дужек не меняются в процессе - диффузии.
4. Пусть - весовая функция, для которой выполняются условия (37), (38), а . Выберем произвольную дужку 
и произвольную разметку 
, такую, что 
, 
.
5. Поскольку диффузия 
выполняет эквивалентное преобразование весовой функции, равно как и преобразование 
, для разметки 
выполняется равенство
| (42) |
.6. В силу условия (38) справедливо неравенство
|
,из которого с учетом (42) следует неравенство
| (43) |
.7. Поскольку для функции 
доказано неравенство (41), то
| (44) |
.Вычитая (44) из (43), получаем
.
Лемма доказана.
Теорема. Для любой весовой функции
.
Доказательство. 1. В силу леммы 10 элементы последовательности 
, 
, принадлежат ограниченному множеству и поэтому содержит в себе подпоследовательность 
, имеющую предел 
. Покажем, что для любой такой подпоследовательности
| (45) |
.2. Выберем произвольно подпоследовательность 
, имеющую предел, и зафиксируем ее для дальнейшего рассмотрения. Обозначим
| (46) |
3. Для любого , и для любой разметки 
справедлива цепочка равенств и неравенств
| (47) |
,где
.
Равенство
в этой цепочке справедливо в силу леммы 1, а все остальные звенья этой цепочки очевидны.
4. В силу леммы 4 последовательность 
, , есть невозрастающая, а в силу (47) и ограниченная снизу последовательность. Следовательно, она имеет предел
.
Этот же предел имеет любая подпоследовательность последовательности , , в частности, подпоследовательность 
, 
, выбранная в п. 2, и подпоследовательность 
, где 
,
, 
.
Следовательно,
,
или, в другой записи
| (48) |
.5. Лемма 7 утверждает, что 
есть непрерывная функция весов , а лемма 9 утверждает, что 
есть непрерывное преобразование весов . Следовательно, величина 
есть непрерывная функция весов и поэтому
|
.Отсюда в силу леммы 6 следует
| (49) |
,что доказывает равенство (45).
6. В силу леммы 10 величина 
не может превосходить величину
|
и поэтому для каждого 
существует верхний предел
.
Последовательность 
есть монотонно невозрастающая последовательность неотрицательных чисел и поэтому имеет предел
.
7. В силу известной теоремы анализа [9] для любой такой последовательности существует подпоследовательность 
, 
, такая, что 
, и такая что
,
или, в другой записи,
| (50) |
.Равенство (50), естественно, справедливо и для любой подпоследовательности последовательности 
, , в частности такой подпоследовательности 
, , 
, для которой существует предел
,
или, в более краткой записи
,
где 
. Сходящаяся подпоследовательность , , гарантировано существует, потому что последовательность , , ограничена (лемма 10).
Таким образом, доказано существование последовательности , , имеющей предел
| (51) |
и такой, что
| (52) |
.8. Ранее доказанное равенство (45) справедливо для любой последовательности , , имеющей предел, в том числе и для последовательности, для которой выполняется (51) и (52). В силу леммы 8 из неравенства (45) следует 
, и с учетом (52),
| (53) |
.Для каждого выполняется
|
,и поэтому из (53) следует
.
Теорема доказана.
В печать
На перевод на английский язык согласен
АНАЛИЗ АЛГОРИТМОВ ДИФФУЗИИ ДЛЯ РЕШЕНИЯ
ОПТИМИЗАЦИОННЫХ ЗАДАЧ СТРУКТУРНОГО
РАСПОЗНАВАНИЯ
,
(Киев)
Аннотация
Выполнен формальный анализ алгоритма, известного под названием диффузии, который используется в структурном распознавании изображений, хотя мало исследован теоретически. Исследована пригодность алгоритма для оптимизации функции большого количества дискретных аргументов, представленной в виде суммы слагаемых, зависящих только от двух аргументов. Доказано, что при определенном условии останова алгоритма он обеспечивает приближенное решение определенных подклассов задач указанного формата с любой наперед заданной ненулевой погрешностью. Множество задач, приближенно решаемых алгоритмом, включает в себя все так называемые ациклические задачи и супермодулярные задачи, для которых сейчас известны алгоритмы решения, и некоторые другие задачи, алгоритмы решения которых до настоящее времени не были известны.
Ключевые слова: структурное распознавание, разметки, дискретная оптимизация, перестановочная супермодулярность.
АНАЛІЗ АЛГОРИТМІВ ДИФУЗІЇ ДЛЯ РОЗВ”ЯЗКУ
ОПТИМІЗАЦІЙНИХ ЗАДАЧ СТРУКТУРНОГО
РОЗПІЗНАВАННЯ
М. І.Шлезінгер,
(Київ)
Анотація
Виконано формальний аналіз алгоритму, відомого у структурному розпізнаванні як алгоритм дифузії, який мало досліджений теоретично. Досліджено придатність алгоритму для оптимізації функції від багатьох дискретних аргументів, поданої як сума доданків, залежних лише від двох аргументів. Доведено, що при певній умові зупинки алгоритм дає наближений розв’язок певних підкласів задач вказаного формату з довільною заздалегідь заданою ненульовою похибкою. Множина задач, що наближено розв’язується алгоритмом, містить у собі всі так звані ациклічні задачі і супермодулярні задачі, для яких зараз відомі алгоритми розв’язку, так і деякі інші задачі, для яких алгоритми розв’язку не були відомі.
Ключові слова: структурне розпізнавання, розмітки, дискретна оптимізація, перестановочна супермодулярність.
DIFFUSION ALGORITHMS AND STRUCTURAL RECOGNITION OPTIMIZATION PROBLEMS
М. І.Schlesinger, К.V.Antoniuk
(Кiev)
Summary
A formal analysis of so-called diffusion algorithms is performed, which are frequently used in structural recognition. However, they are rather poorly theoretically studied. The algorithms are analyzed from the viewpoint of their ability to optimize a function of many discrete variables, which is presented as a sum of many terms, each of them depending only of two variables. It is proved that at the certain stop condition the diffusion algorithm solves approximately certain subclasses of mentioned optimization problems with any pre-defined non-zero inexactness. A domain of problems, which are solvable with diffusion algorithms, includes all so-called acyclic or supermodular optimization problems as well as some other problems, which solution algorithms were not known for.
Key words: structural recognition, labeling, discrete optimization, permuted supermodularity.
|
Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 |
