Диссертация (1149346), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

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

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

После этого показан процесс изменения триангуляции и ее таблицы инциденций при проведенииукрупнения. Далее дается описание программы, реализующей рассмотренный впредыдущих главах алгоритм. В качестве языка программирования была выбрана Java; выбор обусловлен возможностями распараллеливания и переносимостьюна различные аппаратные платформы. В качестве входных данных необходимопередать таблицы инциденций обрабатываемой триангуляции. Для удобства тестирования рассматриваемого в работе метода была реализована возможность использовать в качестве входных данных программы графическое изображение влюбом из распространенных форматов (bmp, png, jpeg и другие), для которогоавтоматически выполняется построение триангуляции с необходимой топологией.Для чтения данных используется класс BufferedImage, входящий в компиляторJava от компании Oracle.

В качестве аппроксимируемых значений берутся уровнияркости компонент цвета соответствующего пикселя в представлении RGB3 , приэтом каждый из трех базовых цветов (красного, зеленого и синего) обрабатываетсянезависимо на отдельной сетке. В дальнейшем выполняется адаптивное локальное укрупнение построенных триангуляций, а затем построение курантовских аппроксимаций исходных значений. В последних разделах главы демонстрируютсярезультаты работы алгоритма на модельных примерах.В Заключении сформулированы основные результаты работы.3 RGB— аббревиатура английских слов Red, Green, Blue — красный, зелёный, синий соответственно, аддитивная модель представления цвета.10В Приложение вынесены таблицы результатов численных экспериментов, наборы тестовых изображений и соответствующие им аппроксимации, а также исходные коды комплекса компьютерных программ, реализующего предложенныеалгоритмы.11Глава 1О сплайн-всплесковых разложенияхОбзор главыВ этой главе будут рассмотрены сплайн-всплесковые разложения первого порядка в соответствиии с подходами, изложенным в [13], [19], [26], [8].

Даются основные определения и термины, используемые в дальнейшем, проводится обзорсуществующей теории сплайн-всплесковых разложений.1.1.Предварительные определенияНа интервале (α, β) вещественной оси R рассмотрим сеткуX:· · · < x−2 < x−1 < x0 < x1 < x2 < . . .Пустьlim xj = α,lim xj = β.j→−∞j→+∞defОпределение: Множество двумерных векторов A = {aj }j∈Z , удовлетворяющее соотношениюdet(aj , aj+1 ) 6= 0будем называть полной цепочкой векторов.12∀j ∈ Z,(1.1)defdefПусть Sj = (xj , xj+1 ) ∪ (xj+1 , xj+2 ), ϕ(t) = (1, t)T .

Рассмотрим функции ωj (t), t ∈(α, β), j ∈ Z, такие, чтоPj 0 ∈Z aj 0ωj 0 (t) = ϕ(t),∀t ∈ (α, β) \ X,(1.2)ωj (t) ≡ 0 ∀t ∈/ Sj,supp ωj = Sj .Определение: Соотношения вида (1.2) будем называть аппроксимационными соотношениями.При t ∈ (xk , xk+1 )ak−1 ωk−1 (t) + ak ωk (t) = ϕ(t),(1.3)с учетом (1.1) имеемωk−1 (t) =det(ϕ(t), ak ),det(ak−1 , ak )ωk (t) =det(ak−1 , ϕ(t)).det(ak−1 , ak )Для фиксированного j ∈ Z, k = j и k = j + 1, получим:det(aj−1 ,ϕ(t))t ∈ (xj , xj+1 ) det(aj−1 ,aj )aj+1 )ωj (t) = det(ϕ(t),t ∈ (xj+1 , xj+2 )det(aj ,aj+1 )0t∈/ [xj , xj+2 ](1.4)supp ωj ⊂ [xj , xj+2 ].Определение: Функции ωj (t), полученные из аппроксимационных соотношений, называются координатными сплайнами.Обозначим l-ю компоненту вектора ai через [aj ]l , так чтоdefai = ([aj ]0 , [aj ]1 ).Тогда функцию ωj (t) можно записать в следующем виде:t·[aj−1 ]0 −[aj−1 ]1t ∈ (xj , xj+1 )[a j−1 ]0 [aj ]1 −[aj−1 ]1 [aj ]0j+1 ]1 −t·[aj+1 ]0ωj (t) = [a ] [at ∈ (xj+1 , xj+2 ) .·[aj 0j+1 ]1 −[aj ]1 ·[aj+1 ]00t∈/ [xj , xj+2 ]13Можно заметить, что ωj (t) – кусочно-линейная функция.Рассмотримdefe(t) =uXt ∈ (α, β)\Xcj ωj (t),j— линейную комбинацию функций ωj при j ∈ Ze(t) будетПо определению функции ωj (t) для каждого t ∈ (xi , xi+1 ) функция uиметь вид:e(t) = ci−1 ωi−1 (t) + ci ωi (t).uОпределение: Замыкание S1 (X, A, ϕ) линейной оболочки функций {ωj }j∈Z втопологии поточечной сходимости называется пространством сплайнов первойстепени:defS1 (X, A, ϕ) = Clp {u | u =Xcj ωj∀cj ∈ R1 }.(1.5)jЭлементы этого пространства назовем сплайнами первой степени.1.2.О непрерывности координатных функцийОпределим di ∈ R2 через следующее тождество:dTi x = det(ai−1 , x)∀x ∈ R2 ∀i ∈ Z;def(2.1)тогдаdTi = (−[ai−1 ]1 , [ai−1 ]0 ).(2.2)Лемма 1: Если цепочка {aj }j∈Z полная, то справедливы соотношения:dTi ai 6= 0,dTi ai−1 = 0,dTi ai−2 6= 0,∀i ∈ Z.Доказательство:Первые 2 соотношения очевидны с учетом (2.1).Для доказательства третьего тождества будем рассуждать от противного.14(2.3)Пусть dTi ai−2 = 0.

Составим систему уравнений относительно неизвестных [di ]0 ,[di ]1dT ai−2 = 0,idT a = 0.i i−1Определитель системы det(ai−2 , ai−1 ) отличен от нуля по условию полноты цепочки ai , следовательно, di = 0, что противоречит первому тождеству (2.3). Лемма доказана.defОбозначение: ϕi = ϕ(xi ).Теорема 1:Для непрерывности функции ωj (x) на (α, β) необходимо и до-статочно, чтобыdTi ϕi = 0∀i ∈ Z.(2.4)Доказательство:Достаточность:Докажем непрерывность ωj в точках xj , xj+1 и xj+2 .В соответствии с (1.4) получаем:ωj (xj + 0) =det(aj−1 , ϕj ),det(aj−1 , aj )ωj (xj+2 − 0) = −det(aj+1 , ϕj+2 ).det(aj , aj+1 )(2.5)По (2.1), (2.4) числитель первого равенства равен нулю при i = j. Числительво втором равенстве равен dTj+2 ϕj+2 и также равен нулю с учетом формулы (2.4)при i = j + 2.Таким образом, функция ωj непрерывна в точках xj и xj+2 .Покажем непрерывность ωj в точке xj+1 . При t ∈ (xj , xj+1 ) из (1.2) находимaj−1 ωj−1 (t) + aj ωj (t) = ϕ(t),(2.6)а при t ∈ (xj+1 , xj+2 ) из (1.2) получаемaj ωj (t) + aj+1 ωj+1 (t) = ϕ(t).15(2.7)Перейдем к пределу в (2.6) и в (2.7) при t → xj+1 − 0 и t → xj+1 + 0 соответственно.

Ввиду того, что ωj−1 (xj+1 − 0) = 0 и ωj+1 (xj+1 + 0) = 0, приходим ксоотношениямaj ωj (xj+1 − 0) = ϕ(xj+1 ),aj ωj (xj+1 + 0) = ϕ(xj+1 ).Отсюда ωj (xj+1 − 0) = ωj (xj+1 + 0).Достаточность доказана.Необходимость: По непрерывности ωj (t) имеем ωj (xj + 0) = 0, с учетом формулы (2.6) получаем det(aj−1 , ϕj ) = 0; следовательно, по формуле 2.1, dTj ϕj = 0.Необходимость доказана.Обозначение:a?j = ϕj+1 = (1, xj+1 )T ,defd?i = (−xi , 1)Tdef∀i, j ∈ Z;(2.8)defОчевидно, что A? = {a?j } — полная цепочка векторов; решение соответствующейсистемы аппроксимационных соотношений обозначим ωj∗ (t).defПо аналогии с пространством сплайнов S1 (X) = S1 (X, A) построим пространствоdefсплайнов S?1 (X) = S1 (X, A? ).Следствие 1: Функция ωj? непрерывна на отрезке (α, β) ∀j ∈ Z.Доказательство: В обозначениях (2.8) второе из соотношений в (2.3) принимает вид (d?i )T a?i−1 = (d?i )T ϕi = 0, что совпадает с условием (2.4); теперь утверждение, сформулированное в следствии, вытекает из теоремы 1.Теорема 2: Во множестве {S1 (X, A) | A ∈ A} пространств (X, A)-сплайнов1-й степени существует и единственно пространство непрерывных сплайнов;оно определяется цепочкой A? и совпадает с пространством S?1 (X).Доказательство: Существование пространства непрерывных (X, A)-сплайновследует из теоремы 3 (см.

также следствие 1); таковым является пространствоS∗1 (X).16Осталось установить, что во множестве всех пространств сплайнов первой степени на сетке X существует лишь одно пространство непрерывных сплайнов.Пусть по некоторой полной цепочке векторов A = {ai }i∈Z построено пространствоS1 (X, A),в котором координатные функции ωj ∀j ∈ Z лежат в пространстве C(α, β). Пустьпо этой цепочке построена цепочка {di }i∈Z согласно формулам (2.1).В соответствии с теоремой 1 соотношения ωj ∈ C(α, β) ∀j ∈ Z эквивалентнысоотношениям dTi ϕi = 0 ∀i ∈ Z; значит, векторы di и ϕi ортогональны. Вспоминая,что по построению вектора di (см.

(2.1)) он ортогонален также вектору ai−1 , приходим к выводу о коллинеарности векторов ai−1 и ϕi ; таким образом, существуют(благодаря полноте цепочек {aj } и {ϕj }) отличные от нуля константы ci ∈ R1 такие, что ai−1 = ci−1 ϕi , или (что то же самое) ai = ci a?i . Получаемые в этом случаепо формулам (1.4) функции обозначим ωj . Очевидно, что они равны функциям ωjс точностью до умножения на константу:ωj =1 ?ω ,cj jпоэтому линейные оболочки множеств {ωj | ∀j ∈ Z} и {ωj? | ∀j ∈ Z} совпадают.Единственность пространства непрерывных (X, A)-сплайнов доказана.Определение: Пространство S?1 (X) называется пространством непрерывных (X)-сплайнов первой степени, а сплайны этого пространства — непрерывными сплайнами первой степени на сетке X.Замечание: Из формулы (1.4) получаем:(t − xj )/(xj+1 − xj )t ∈ [xj , xj+1 ),ωj? (t) = (xj+2 − t)/(xj+2 − xj+1 ) t ∈ [xj+1 , xj+2 ),0t∈/ [xj , xj+2 ].(2.9)Построенный таким образом сплайн ωj? (t) можно рассматривать как одномернуюфункцию Куранта.171.3.Нелинейные координатные функцииПусть ϕ — двухкомпонентная вектор-функция класса C S на (α, β).

Построимфункции ϕj (t) по формулам (1.3)—(1.4) и введем обозначения(S) def (S)= ϕ (xk ).defϕk = ϕ(xk ),ϕkТеорема 3 (О гладкости): Пустьϕ ∈ C S (α, β),(S)dTk ϕk = 0 ∀k ∈ Z.(S)Тогда ωj(3.1)∈ C(α, β).Доказательство: Заметим прежде всего, что достаточно доказать непрерыв(S)ность функции ωjв точках xj , xj+1 и xj+2 , так как непрерывность ее в остальныхточках интервала (α, β) очевидна.В соответствии с формулой (1.4) легко получить предельные значения функции(S)ωj :(S)(S)ωj (xj(S)det(aj−1 , ϕj )+ 0) =,det(aj−1 , aj )(S)ωj (xj+2det(aj+1 , ϕj+2 )− 0) = −.det(aj , aj+1 )(S)Согласно формуле (2.1) числитель первого из этих равенств совпадает с dTj ϕj ,и потому равен нулю по условию (3.1) при k = j; числитель во втором равенстве(S)совпадает с выражением dTj+2 ϕj+2 и также равен нулю по условию (3.1), если в(S)этом условии положить k = j + 2.

Характеристики

Список файлов диссертации