Image Processing

ВНИМАНИЕ, ЭТО НЕДОПИСАННАЯ СТАТЬЯ. Она мо­жет со­дер­жать ка­кие-угод­но не­точ­но­сти.

Край­гинг (kriging) был при­ду­ман в [та­ком-то] го­ду [та­ким-то] че­ло­ве­ком, от­сю­да и на­зва­ние ме­то­да. Ин­те­рес­ны­ми осо­бен­но­стя­ми дан­но­го ме­то­да яв­ля­ют­ся [осо­бен­но­сти]. До край­гин­га ис­поль­зо­ва­лись [та­кие-то] ме­то­ды. Край­гинг вы­год­но от­ли­чал­ся от них [тем-то], по­это­му стал очень по­пу­ля­рен вско­ре по­сле сво­е­го изоб­ре­те­ния.

Жир­ным шриф­том бу­ду обо­зна­чать точ­ки и век­то­ры, что­бы не пу­тать их с чис­ла­ми.

Опре­де­ле­ние ме­то­да

До­пу­стим, нам да­ны точ­ки , , ... , в ев­кли­до­вом про­стран­стве  лю­бой раз­мер­но­сти, и в этих точ­ках из­ве­ст­ны зна­че­ния не­ко­то­рой функ­ции: , , ... , , при­чём са­ма функ­ция  нам не­из­ве­ст­на. Тре­бу­ет­ся по­стро­ить ин­тер­по­ля­ци­он­ную функ­цию , яв­ля­ю­щу­ю­ся «хо­ро­шей» оцен­кой не­из­вест­ной функ­ции : .

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

(1)

Край­гинг — ли­ней­ный ме­тод. Это озна­ча­ет, что для вы­чис­ле­ния ко­эф­фи­ци­ен­тов , ... , зна­че­ния , ... , не ис­поль­зу­ют­ся; ис­поль­зу­ет­ся по­ло­же­ние то­чек , , ... , , и мо­дель слу­чай­но­го про­цес­са (ва­рио­грам­ма, о ней поз­же). Од­на­ко, ес­ли для по­строе­ния ва­рио­грам­мы вы поль­зу­е­тесь ве­ли­чи­на­ми , ... , , то ре­зуль­тат ин­тер­по­ля­ции бу­дет не­ли­ней­но за­ви­сеть от этих ве­ли­чин.

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

(2)

Та­кой под­ход был на­зван оп­ти­маль­ным ли­ней­ным пред­ска­за­ни­ем.

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

(3)

Функ­ция на­зы­ва­ет­ся ва­рио­грам­мой слу­чай­но­го про­цес­са. По­ка мы её не зна­ем (и вряд ли узна­ем, так как функ­ция нам не­из­ве­ст­на и, во­об­ще го­во­ря, мо­жет не яв­лять­ся слу­чай­ным про­цес­сом).

Пред­по­ло­жим, что ва­рио­грам­ма из­ве­ст­на. То­гда зна­че­ния ве­сов опре­де­ля­ют­ся сле­дую­щим об­ра­зом:

(4)

где

(5)

По­лу­чен­ные ве­са мож­но под­ста­вить в фор­му­лу (1) и по­лу­чить тре­бу­е­мое зна­че­ние . Ве­ли­чи­на вспо­мо­га­тель­ная (это мно­жи­тель Лагран­жа); она мо­жет при­го­дить­ся для по­сле­дую­щей оцен­ки по­греш­но­сти ме­то­да.

Важ­но, что ес­ли нуж­но вы­чис­лить зна­че­ния ин­тер­по­ля­ци­он­ной функ­ции во мно­гих точ­ках, то мат­ри­цу A до­ста­точ­но раз­ло­жить один раз, так как она не за­ви­сит от те­ку­щей точ­ки . Об­ра­ти­те вни­ма­ние, что при прак­ти­че­ской реа­ли­за­ции мат­ри­цу нуж­но имен­но раз­ло­жить, а не об­ра­тить (ра­зум­ные лю­ди ни­ко­гда не об­ра­ща­ют мат­ри­цы). Мож­но, на­при­мер, ис­поль­зо­вать LU-раз­ло­же­ние. С раз­ло­жен­ной мат­ри­цей си­сте­ма урав­не­ний (4) бу­дет ре­шать­ся для каж­дой вы­чис­ля­е­мой точ­ки со ско­ро­стью умно­же­ния мат­ри­цы на век­тор (то есть вы не те­ря­е­те в ско­ро­сти по срав­не­нию с од­но­крат­ным об­ра­ще­ни­ем мат­ри­цы), од­на­ко точ­ность ре­ше­ния бу­дет вы­ше, чем при об­ра­ще­нии мат­ри­цы.

Край­гинг поз­во­ля­ет оце­нить по­греш­ность са­мо­го се­бя. По­греш­ность вы­чис­ля­ет­ся в ви­де дис­пер­сии от­кло­не­ния вы­чис­лен­но­го зна­че­ния от ис­тин­но­го не­из­вест­но­го:

(6)

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

Слу­чай ста­ци­о­нар­но­го изо­троп­но­го про­цес­са

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

Ва­рио­грам­ма ста­ци­о­нар­но­го и изо­троп­но­го слу­чай­но­го про­цес­са яв­ля­ет­ся функ­ци­ей од­ной пе­ре­мен­ной — рас­стоя­ния меж­ду точ­ка­ми:

(7)

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

(8)

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

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

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

Те­перь стро­им по этим точ­кам плав­ную кри­вую (есть мно­го ме­то­дов сде­лать это):

Эту кри­вую и ис­поль­зу­ем в ка­че­стве функ­ции  в фор­му­лах (4)–(5).

Кста­ти, ме­тод поз­во­ля­ет учесть по­греш­ность ис­ход­ных дан­ных: есть ни что иное, как удво­ен­ная дис­пер­сия из­ме­ря­е­мой ве­ли­чи­ны. Ес­ли тре­бу­ет­ся, что­бы по­верх­ность про­шла точ­но по имею­щим­ся точ­кам, то долж­но быть рав­но ну­лю (кри­вая на ри­сун­ке 2 долж­на вы­хо­дить из на­ча­ла ко­ор­ди­нат). Ес­ли же ис­ход­ные дан­ные не­точ­ны, и име­ют дис­пер­сию d, то долж­но быть .

Ещё од­но за­ме­ча­ние. Глад­кость ре­зуль­ти­рую­щей ин­тер­по­ля­ци­он­ной функ­ции  сов­па­да­ет с глад­ко­стью функ­ции . Ес­ли нам нуж­но, что­бы  бы­ла не­пре­рыв­но диф­фе­рен­ци­ру­е­ма (не име­ла «из­ло­мов»), то долж­на быть то­же не­пре­рыв­но диф­фе­рен­ци­ру­е­мой. Не­труд­но ви­деть, что ес­ли не­пре­рыв­но диф­фе­рен­ци­ру­е­ма, и , то функ­ция  бу­дет то­же не­пре­рыв­но диф­фе­рен­ци­ру­е­мой. В свя­зи с этим ва­рио­грам­му ча­сто ищут в сле­дую­щем ви­де:

(9)

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

При­мер

[Здесь бу­дет при­мер для не­сколь­ких то­чек]

Про­грамм­ная реа­ли­за­ция

[Здесь бу­дет бу­дет при­мер про­грам­мы с опи­са­ни­ем]

Ма­те­ри­а­лы по те­ме

[Здесь бу­дут ссыл­ки]