5.5. Один результат, относящийся к аппроксимации изображения

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

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

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

Как бы то ни было, воспользуемся правилом идентификации, согласно которому из и (как множества) следует кроме того, это отождествляет дополнения где

Пусть — некоторое фиксированное инвариантное относительно подмножество образующих; определим отображение как

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

(iii) определения 3.1.1 (т.1, гл. 3),

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

Это доказывает, что отображение определяется однозначно.

Для доказательства свойства определения 3.1.2 (т. 1, гл. 3) обратим внимание на то, что

Можно доказать также и свойство этого определения, поскольку если то

Итак, мы доказали, что представляет собой гомоморфное отображение

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

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

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

аппроксимацией Асимптотическая нижняя грань для ошибки аппроксимации была получена в работе Маклура и Вайтала (1975):

Теорема 5.5.1. Если изображение представляет собой компактное выпуклое множество в пространстве имеющее гладкую границу с непрерывным радиусом кривизны то

где описанный многоугольник с сторонами.

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

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

где — направления нормалей к сторонам Тогда

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

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

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