5.4. Логика признаков бесконечного порядка

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

В таком случае нецелесообразно пользоваться [I^D]_∞, в качестве восстановленного образа I, поскольку I^D - конечное точечное множество (в данном случае рассматривается ₁) и, следовательно, [I^D]_∞ = I^D. Вместо этого следует "вставить" в незаполненные части деформированного изображения небольшие множества положительных площадей.

Один из способов осуществления этого заключается в следующем. Обозначим через D(ρ) произвольный круг радиуса ρ и через D(z; ρ) - круг радиуса ρ с центром в точке z. Сформируем объединение

(5.4.1)

и пусть радиус ρ стремится к нулю при n → ∞. Мы покажем, что соотношение (5.4.1) обеспечивает при должном выборе радиуса ρ

Рис. 5.4.1

состоятельное восстановление (см. разд. 1.3). Все множества должны принадлежать некоторому ограниченному X₀⊂R² (см. разд. 5.1).

Обратимся к рис. 5.4.1, где с помощью соотношений

(5.4.2)

(сложение осуществляется по Минковскому) введены внутреннее Iⁱⁿ_ρ и внешнее I^out_ρ изображения (на рис. I^BХ_ρ и I^BЫХ_ρ). Будем предполагать, что граница ∂I является тонной в том смысле, что m(∂I) = 0. Тогда справедлива следующая теорема.

Теорема 5.4.1.Пусть I - ограниченное замкнутое множество с тонкой границей. Тогда восстановление в соответствии с (5.4.1) является состоятельным в области

(5.4.3)

если ρ → 0 и n² → +∞.

Доказательство. Известно, что

(5.4.4)

где I^* (z) - индикаторная функция I^*. Для z∈Iⁱⁿ_ρ, однако, получаем следующее:

(5.4.5)

(при nρ² → ∞, ρ → 0). Аналогично для z∈I^out_ρ получаем, что

(5.4.6)

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

(5.4.7)

Поскольку, однако, при р↓0 множества I + D(ρ) сокращаются до замыкания I, которое представляет собой само I, то A_ρ↓∅. Аналогично B_ρ↓∂I. Следовательно,

(5.4.8)

и доказательство закончено.

Для случая = ₂ необходимо, как может убедиться читатель, слегка изменить утверждение. При = ₃ интенсивности пуассоновского потока λ₁ (внутренняя) и λ₂ (внешняя) представляем в виде

(5.4.9)

где μ₁ и μ₂ постоянные, μ₁ > μ₂. Введем показатель N_ρ(z) - число точек z_i, находящихся внутри D (z; ρ).

Теорема 5.4.2.Восстановление

(5.4.10)

является состоятельным в области, если

(5.4.11)

Доказательство. Если z∈Iⁱⁿ_ρ, то

(5.4.12)

где N - случайная величина, подчиняющаяся распределению Пуассона с математическим ожиданием m:

(5.4.13)

Тогда из (5.4.11) следует, что m/t =(2μ₁)/(μ₁ + μ₂)- Однако хорошо известно, что для пуассоновской переменной N/m → 1 по вероятности и, следовательно,

(5.4.14)

по вероятности.

Таким образом,

(5.4.15)

Аналогично очевидно, что

(5.4.16)

Закончить доказательство данной теоремы можно так же, как это было сделано при доказательстве теоремы 5.4.1.

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

Если известно, что I - это просто s₀g, g = D(z; R), R задано, z неизвестна и s₀ принадлежит группе переносов, то как будто бы естественно восстанавливать I с помощью пересечения всех sg, содержащих I^D, где = ₁ (см. рис. 5.4.2). Тогда I^* ограничено круговыми дугами и имеет сплошную внутреннюю часть.

Множество же (5.4.1), наоборот, может иметь во внутренней части большое количество дыр, если ρ не является достаточно большим, и в таком случае I^* будет обнаруживать тенденцию стать слишком большим.

Можно рассмотреть также изображения типа (s⁰₁g₁) ∩ (∼ s⁰₂g₂), где g₁ и g₂ - заданные квадраты со сторонами, параллельными x и y. Преобразования подобия - те же, что и выше. Такое изображение может выглядеть, как множество с границей ∂I, представленное на рис. 5.4.3. В данном случае будет естественно использовать в качестве I^* пересечение всех sg₁ и ∼sg₂, содержащих (см. рисунок).

Рис. 5.4.2

Рис. 5.4.3

Рис. 5.4.4

И если, наконец, известно, что I имеет вид (∼ s⁰₁g₁) ∩ (s⁰₂g₂), где g₁ и g₂ - два круга с известными радиусами R₁ и R₂, R₁ < R₂, то мы получаем области, имеющие форму круговых колец, как это показано на рис. 5.4.4. В этом случае можно попытаться восстановить I^*, строя пересечение всех ∼s₁g₁ и s₂g₂, содержащих I (I^* на рисунке не показано).

Остановимся более подробно на мощности тех алгоритмов восстановления, которые в большей степени, чем алгоритмы (5.4.1) и (5.4.10), используют структуру образа. Пусть G = G¹∪G², причем G¹ включает некоторые множества с границами, построенными из конечного числа ограниченных аналитических дуг. Пусть арность в G¹ задана так: ω_in(g) = 0, ω_out(g) = 1. Множество G² представляет собой совокупность булевых функций множества; здесь ω_in(g) равна числу переменных, a ω_out(g) = 1. Следовательно, элементы, входящие в G², могут представлять собой композиции объединения, пересечения и дополнения. Кроме того, β(g) = α, g∈G^α, α = 1, 2; S - перенос, как и выше, для G₁, а для g∈G² sg = g.

Воспользовавшись типом соединения Σ - древовидный, при соединении всех входных связей ρ(1, 1) или ρ(2, 1) = ЛОЖЬ и ρ(2, 2) = ρ(1, 2) - ИСТИНА получаем некоторое пространство конфигураций, являющееся обобщением евклидовых образов из случая 2.3.3 т.1. В данном случае индекс класса образующих α = 1, 2 используется только для того, чтобы различать множества и функции множеств. Обратившись к более тонкому делению пространства а, можно было бы получить на результирующей алгебре изображений более жесткие структуры образов, однако здесь мы не будем этим заниматься.

Мы будем идентифицировать две конфигурации c₁ и c₂, оценивая множества, вычислимые по схеме конфигурации, начиная с нижних узлов и далее вверх. Если два полученные в результате такого вычисления множества согласуются, то мы отождествляем c₁ и c₂, т. е. c₁Rc₂.

Рассмотрим теперь принадлежащий этой алгебре изображений некоторый класс образов ₀ с ограниченными изображениями I. Другими словами, мы имеем дело с некоторым классом ограниченных множеств, характеризуемых определенными структурными описаниями - примером можно считать один из трех рассмотренных выше случаев. Как же можно, располагая этими сведениями, восстановить I₀∈₀ по наблюдаемым I = ₁I₀?

Как и раньше, I^D⊂I₀ и мы хотели бы окружить I^D границами, связанными с теми, которые возникают в множестве образующих G₁. Мы хотим, чтобы восстановленное изображение I^* сходилось по мере к I₀ при n → ∞.

Попробуем воспользоваться следующим алгоритмом.

Алгоритм. I^* вычисляется как пересечение всех тех изображений I, принадлежащих ₀, которые содержат I^D. Интуитивно кажется, что этот алгоритм использует структуру образов и можно рассчитывать на благоприятный результат восстановления. Ситуация, однако, не так проста, и необходимо заранее принять меры против тех возможных последствий, которые могут не быть очевидными с первого взгляда. Может оказаться, что ₀ включает изображение I, дополнение которого снабжено длинными и тонкими "иглами", направленными внутрь I. Если это действительно так, то, комбинируя (посредством объединения) иглы ряда изображений sI из мы можем исключить из I^* значительную часть I, и при n → ∞ сходимость к идеальному изображению может не иметь места.

Чтобы избежать этого, необходимо обеспечить выполнение определенных условий, и мы предложим один способ преодоления этого затруднения. Пусть задан некоторый ограниченный треугольник T, одна из вершин которого обозначена Р и угол при ней равен υ; рассмотрим класс подобразов ₁⊂₀, для которого существует такой поворот φ, что при z∈I^c повернутый треугольник Т (z, φ) также содержится в I^c.

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

Теорема 5.4.3. Модифицированный алгоритм сходится в области.

Доказательство. Рассмотрим некоторую точку z∈I₀ - ∂I₀ (см. рис. 5.4.5). Все изображение I₀ состоит из конечного числа связанных элементов и z - один из них. Пусть ρ(z) - расстояние от z до I₀^c, поэтому ρ(z) > 0. Рассмотрим круг D (z, ρ), ρ < ρ(z), содержащийся в I₀. Чтобы обеспечить I^*(z) ≠ I₀(z) = 1, необходимо располагать некоторым I∈₁ дополнение которого I^c покрывает z. Если I^c покрывает z, то существует некоторый треугольник T(z, φ)⊂I^c, обладающий определенной ориентацией φ. Принцип действия алгоритма, однако, исключает наличие в I^c точки z_υ из I^D. Следовательно, в множестве А = Т (z, φ) ∩ D (z, ρ) не может быть точек z_υ. С другой стороны, условное распределение вероятностей на D(z, ρ) является равномерным, и m (Т) = πρ² > 0. Следовательно, вероятность по крайней мере для k точек в D(z, φ) стремится к единице при n → ∞. Для заданного числа точек в D(z, ρ) их условное распределение на D(z, ρ) является равномерным. Вероятность же того, что углы между z и теми z_υ для которых выполняется z_υ∈D(z, ρ), не покрывают угол υ, стремится, однако, к нулю при стремлении n к бесконечности, так что

(5.4.17)

и

(5.4.18)

отсюда следует, что теорема доказана, см. доказательство теоремы 5.4.1.

Рис. 5.4.5

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

Чтобы несколько прояснить эту ситуацию, обратимся к конкретному случаю, а именно к случаю, о котором шла речь в теореме 5.3.1. Пусть изображение соответствует указанной постановке; сформируем восстановленное изображение

(5.4.19)

где SQ(z, s) - квадрат с центром в точке г и со стороной 2s. Причина использования квадратов, а не кругов, как в (5.4.1), несомненно, состоит в том, что квадрат- более естественная фигура с точки зрения формы границы (см., например, рис. 5.3.1). Отметим, однако, что I^**, вообще говоря, не принадлежит ; мы не пользуемся алгоритмом восстановления, обеспечивающим сохранение структуры.

Определим теперь математическое ожидание площади множества ошибок:

(5.4.20)

(обозначения здесь те же, что и выше). Чтобы обеспечить восстановление, состоятельное по площади, необходимо, конечно, считать, что s↓O при n → ∞. За счет некоторой потери общности будем полагать, что при n → ∞ s ∼ n^-a, a > 0. Но довод, аналогичный использованному при доказательстве теоремы 5.4.1, указывает, что необходимо потребовать, чтобы ns² → +∞, и, следовательно, a < (1/2).

Для этого необходим асимптотический прием того же типа, что использовался для доказательства теоремы 5.3.1, конечно, в некоторых деталях они будут различаться. Мы не будем приводить здесь довольно трудоемкое доказательство и сформулируем лишь результат (доказательство можно найти в отчете Гренандера и Лавина (1973)).

Теорема 5.4.4.Алгоритм восстановления (5.4.19) имеет при s ∼ n^-a, 0 < a < (1/2), ошибку восстановления

(5.4.21)

где р - периметр I.

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

Теорема свидетельствует о том, что алгоритм (5.4.19) имеет асимптотическую ошибку восстановления порядка n^-1/2+ε, ε > 0; сопоставив эту оценку с величиной (ln n)/n, что соответствует алгоритму, обеспечивающему сохранение структуры, убеждаемся, что последний лучше.

Это хорошо, но следует помнить, что данный результат доказан лишь для частного случая. Следующий пример позволяет убедиться в том, что он не обладает общностью в полном смысле этого слова. Пусть алгебра изображений состоит изо всех тех множеств, которые замкнуты относительно логики признаков р-го порядка при р = 1 или 2, или 3 ..., и все g - полуплоскости. Тогда пределом [I^D]_р при р → ∞ является само №% и при n → ∞ мы не получим состоятельного по площади восстановления. Несомненно, этот пример -скорее крайний случай, и, вероятно, можно было бы найти лучшие примеры.

К этому следует добавить, что восстановленные изображения типа (5.4.1) или (5.4.19) неудобны в обращении, поскольку в них используется столько же информации, сколько содержит само №. И наоборот, восстановление типа того, которое применяется для выпуклой оболочки I^d в среднем требует много меньше информации.