Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.intsys.msu.ru/magazine/archive/v6(1-4)/zhivot.pdf Дата изменения: Tue Oct 29 14:39:04 2002 Дата индексирования: Mon Oct 1 23:20:41 2012 Кодировка: Поисковые слова: m 44

T -

.

.

.

,

.

.

1.

f(i j ) i = 1 n j = 1 mg! R ,
1

g g

1 mg. {

g

gij i =1 : : : m, j =1 : : : n. g f{
,

g

(i j )

g: gij 2 R1 , f(i j ) i = 1 n j = m n, (i j ) ,

g

2R

1

: ( g)ij = gij , (f + g)ij = fij + gij , i = 1 n j = 1 m. nm XX f g : (f g ) = fij gij . ,
i
=1

j

=1

R N , N = m n,
,

N,

.

gij , i = 1 n j = 1 m,
, 44/99{ .

-


64 ,

.

.

,

.

.

,

, . {f
k ij

f f

()

k

= ff = 1,

k ij

()

i = 1 n j = 1 mg 2 R , k = 0 9,
()

k ij

()

f, = f ij i = 1 n j = 1 mg2 RN
()

, = 0. g,

N

,

, , (1)

,

k

g = f (k) + :
1.1.
1, 4]

, pr( ) { ij , 8i j ,

, , (1), pr(gj k ) = , , pr ( ).

f

()

k

,

g = fgij g2 R
nm YY i
=1 =1 ( pr(gij ; fijk)):

N

-

k

j

ij

,i=1nj=1m

-

pr(gj k ) = pr (g ; f (k) ): Pr( k ) { , ,

k , k = 0 9. k, -

g

k,


65 pr Pr( k jg)= P (gj k ) Pr( k ) 9 pr(gj l ) Pr( l )
l
=0

k =0 ::: 9

k
k
=0 9

: Pr( k ) = 1=10, k = 0 9. pr(gj k ) max , k g,

k = k (g)= arg max Pr( k jg) g 2 RN :
Pr( k jg) max k , , , (2) (3)

k,
k
=0 9

k = arg max pr(gj k ) = arg max pr (g ; f (k) ) g 2 RN :
ij

2
k

k=0 RN ,

9

i = 1 n j = 1 m,
c
()

k = arg max
, 9,

=0 9

0n m 1 YY @ pr(gij ; fijk )A :
i
=1 =1

pr( ),

j

(g ) 2 = ( ()

(

( ) = ( 0( ) : : : (g) , 10 R:
0

9

. ( )) : RN !

g2R

N

-

:::

9

):

X
9

k

k

=1 k > 0 8k = 0 9

)

g 2 RN :
(4) -

=0

:

k

k

(g), k = 0 9.

g 2 RN ,


66

.

.

,

.

.

()

, (1 ; kl )

R( l
kl { Pr( l ), l = 0 9,

( )) =

X
9

Z

l,
k

-

k

=0

RN

(g)p(gj l )dg -

. ()

R( ( )) =

X
9

l

Pr( l )

X
9

=0

k

(1 ; kl )

Z

=0

RN

k

(g)p(gj l )dg:

(5)

R( ( ))

9 9 9 1 X X Z (g)p(gj l )dg; 1 X Z (g)p(gj l )dg min R( ( )) = 10 k l 10 l=0 () l=0 k=0RN RN

min, (5) () , Pr( l ) = 1=10, l = 0 9:

XZ
9

9 9 1 X X Z (g)p(gj l )dg = 1: k 10 l=0 k=0 RN max p(gj k ) k=0 9 (2)

l=0 RN

l

(g)p(gj l )dg max
()

(6) , () -

k. g 2 RN :

l (g)=

8 <1 :0

p(gj l ) = max p(gj k )
k
=0 9


67 ( )=( 0 ( ) : : : (6) . , ,
9

( ))

. .

, ,

(6) -

8g 2 RN :
(7),
L

X
9

l

l

(g)p(gj l ) max
()

=0

g

(7) () , -

. (6),
1

(6).

,
L

()
10

'( ) : RN ! R1 ,

( ),

(6) , 2]). (2).

,

( ., ( ), , . -

,

,
1.2.

, Pr( k ), k = 0 9.

() 2
1 2

kq

=f

kq ij
()

i = 1 n j = 1 mg {
A
. (

5].

-

f (k), k =

,

A

ij

)

A

=

f

,

A ij

i

=1

nj

=1

mg2


68 0 9. 1,
1.

.

.

,

.

.

q k
,
Vf (k) =

, (k ) (k ) 0 (k ) 1 f =0 +1 , k = 0 9.
N

,

0 -

R

Vf (k

f

()

k

)

(

(

)
N

f = ffij g2 R j f =
()

X
q

c

q

()

kq

c0 6 c1

)

, (8)

{

Pf

k

:
()

Vf (k) ,

Pf k g =

X
q

c

q

()

kq

g2R

N

(9) :

8g 2 R

c0 = c0 (g), c1 = c1 (g) {
N

nm XX i=1 j
=1

gij ;

X
q

c

kq q ij
()

!

2

= cmin 6c
0

nm XX i
=1

1

j

gij ;

X
q

c

=1

kq q ij
()

!

2

k = 0 9: (10)
5]. (11)

,

(10)

f=
RN
,

s X i=1

cf i
A A

i f

()

A ij

(
=

1 0

( (

ij ij

) )

2 62

i

=1

nj

=1

m:


69
i f cf i
()

2 RN { 2R
1

0

1,

R, ci 2 R , i = 1 s
N
1

f, i = 1 s

(1)

f

:::

s f

()

{

C

0 6 cf s X i=1

Rs {

(12)

Vf

f (11)
(i f )

g 2 RN , c =(c1 : : : cs ) 2 C
Vf ,

g= Pf

ci

Pf g =

s X i
=1

c

(i if

)

g2R

N

R

N

c =(c1 : : : cs ) 2 C { g;
Lf
2.

: 8g 2
s X i=1

s X i
=1

ci fi

2

()

=miC g ; n c2 . ,

c

i if

2

()

:

(13) -

f

R,
N

Vf ,

L( f

(1)

:::

s f

()

){

,

,

s,

Lf

f.


70 (13)

.

.

,

.

.

g

Lf

,

g g= e
s X i=1

6],

g e

ci e

i f

()

ci = e
2

(g (i) ) f i =1 ::: s (i) 2

kfk

8e 2 R c

s

:
2

kc ; ekHf = min kc ; ek c c c2C
(1) 2 2

kxkHf =(x Hf x), x 2 Rs , Hf =
k,

0 0 ::: Bk f k B 0 k f k ::: B B: : : @
(2) 2

Hf

0 0
f

0

0

::: k

() 2

1 C C. C :C A s
k
g
-

k = arg min kg ; Pf k gk2 : k
()

(14)

k,

,

, , ,

g

k.

(14), , E ij = 0 9], ,
()

(1)

ij

i = 1 n j = 1 m. k k2 = 2 N =m n
.

E
,

ij

2

=

2

< 1,
2

N
()

-

g=f + , N rank Pf
()

l

,

()

k

= kg ; Pf k gk2 = 2 . (k ) = kf (l) + ; Pf k (f (l) + ))k= 2 . (k ) N , k = 0 9, 3 2 N ; rank Pf k
k
() ()

-

3

N

s

N


71 , , k = l, t2 = kf (l) ; Pf k f (l) k > 0, k 4 f (k).
()

k 6= l
(0) 2

f
(9)

()

l

-

,

10

:::

,

, tk =0,
2

t2 : : : t2 . 0 9 y
()

k

{

,

(

k
2

)

,
2

,
()

k

y

(0)

::: y

(9)

tk , k = 0 9.
. , ,
k

, pr ( t2 ) { k ( N)
2
2

(15)

(0)

:::
,

(9)

, ,, ,

3, 4],

yk ,
2

k = arg max p (y k
,
1.

()

t2 )= arg mkin y(k) : k
(14).
,

(15)
, .

(1)

1, i = 1 n j = 1 m
(14)

E

ij

=0

ij

E

ij

2

=

2

<

N !1

.
,

, rank
4

Pf N s

(k )

, (12),
(k )

Pf

(k)

=

Vf

6].

g

.

s

,

Pf

(k)

rank

Pf
,

6s
g

f

2


72
2.

.

.

,

.

.

-

-

, , ,

. 8]. .

, -

2.1.

-

-

( , f (k) = ffijk) g2 Rm n { k , i = 1 m, j = 1 n , f (k) =0 (k ) q m n , q =0 1 { 2R (0 1) f (k) , k = 0 9.

,

( )0

k

+1

( )1

k

-

f

()

{

. ).
( )0

2 RN ,
,

{

,

g2R

N

{{
,

,

,

{ , 0 9( ,

P ({ = k) = 1 8k = 0 9,

, -

Vf (k
k

)

k

( )1

, : h=

R,
N

f

()

k

Vf (k) =

h2R

mn

X
1

q

cq

()

kq

;1 0 1

=0


73

P

f (k
()

)

{

Pf k g = g c(k) (g)= (k q
k q) (k ) q k2
()

X
1

Vf (k) :

q

=0

c(k) (g) q

()

kq

g2R

N

, k = 0 9, q =0 1.

(k ) 0 2 : e = 1 2 R2 , H (k) = k 0 k k (k0) 1 k2 . 1

(k ) c(k) (g) = c0k) (g) 2 R2 . c( (g ) 1

!

-

(c (g) H e).
() ()

k

k

,

c (g) ; c(k) (g) 0 Pf k g.
() 1

k

,

g

V
,

f (k

)

(

,

()

g k.
, :

)

, ,

g g
=g

k,
-

-

k,

(k ) P ({ = kj = g)= F ((kc) (g) (bk)) (c (g) H e)

!
0 , 1

(16)

F( )
,

, b =(;1 1) 2 R2 . , 8],

k,

,

k = arg kmax9 P ({ = kj = g): =0:::

(17)


74
2.2.

.

.

,

.

.

-

{

f

()

{

{

, ,

g
,

-

' ij ( ) = '( )

{ 2 f0 : : : 9g.

, i = 1 m, j = 1 n, , 8]. {=k , k,
n

( ' j{ (gjk)= min min '(gij ; fijk))

i

=1

mj

=1

g2R

N

k =0 ::: 9:
=g ,

{ = k.

' j{ (gjk)

8]

P ({ = k = g)= min(' j{ (gjk) P ({ = k)) P ({ = k)= 1, 8k = 0 9,
( P ({ = k = g)= min min '(gij ; fijk) ):

i

=1

nj

=1

m

,

g

,

k = k (g)

(18)

k (g) = arg mkax P ({ = k = g):
2.

(1)
.

{

f

()

{

,

, 8].

(18)

k

,

f

{ -


75
3. -

2.2 . , : ?
3.1.

-

.

. , .

-

-

, = f!1 !2 : : : !N , Pr( ) P ( ) { , F 0 1]. ( F Pr) ( F P) . 3. ( F P) ( F Pr), 8A B 2 F : Pr(A) > Pr(B ) ) P (A) > P (B ). ( F P ), ( F Pr), , , P ( ): 8A 2 F A 6= ? : P (A) = 1, P (?) = 0, ( F Pr) . 4. ( F P) ( F Pr), ( F P) ( F Pr), ( F P 0 ), ( F Pr) -

::: g, F = P ( ) { -

{

8A B 2 F : P 0(A) >P 0 (B ) ) P (A) >P (B ):


76

.

.

,

.

.

3.1, 3.1 ( F P ), , ( F Pr). . 8]

8],

. 5, x1. (19) .

Pr(f!1 g) > Pr(f!2 g) > ::: > Pr(f!N g) > ::: > 0 (19)
k X j
=1

. prj , k =1 2 : : : , F
0

pk =

P (f!k g), prk =Pr(f!k g) Fk =
1.

0.
( ( ,

, ,

)

( F P) ( F Pr),
):

pk > pk+1 (pk >pk+1 )
.

p1 =1 pk = pk+1 , prk 6 1 ; Fk , k =1 2 ::: .
,

( F Pr). ( F P) p1 = 1 1= P ( ) = P

( F P) ,
1
k
=1

-

( F Pr).

f!k g = sup p
k=1:::1

!

(19)
k

f!k

+1

1= p1 > p2 > ::: > pN > ::: : (20) prk 6 1 ; Fk , pk > pk+1. A= !k+2 ::: g B = f!k g. Pr(A) = 1 ; Fk , Pr(B ) = prk , Pr(A) > Pr(B ). ,

P (A)= sup pi = p
i=k+1:::1

k

+1



77 . , prk 6 1 ; Fk , , ,

pk 6 pk+1 ,

(20)

pk = pk+1.
.

. ? : 9kA : prkA 6 Pr(A) 6 1 ; FkA ;1. 1 A = (A \f!i g),

8A 2

F

A2F kA :

A 6=

i : A \f!i g 6= ?

i

A 6= ?,
.

=1

kA = i=1:::1fi j i =1 2 : : : !i 2 Ag: min
prkA 6 Pr(A)=
1 X
i=1

Pr(A\f!i g)=

1 X
i=kA

Pr(A\f!i g) 6

1 X
i=kA

pri =1;FkA ;1 :

A B 2 F,Pr(A) > Pr(B ) > 0.
Pr(A)= prkA + Pr(B )= prkB + Pr(A) > Pr(B ) prkA +
1 X
i=kA
+1

1 X

i=kA

Pr(A \f!i g) Pr(B \f!i g)

1 X

+1

1 ; FkA ;1 > prkB , 1 ; FkA ;1 > 1 X Pr(A \f!i g) > prkB + Pr(B \f!i g) > prkB .
i=kB
+1

i=kB

+1

, P (A) = pkA , P (B ) = pkB . kA 6 kB , P (A) > P (B ). kA > kB , , prkB 6 1 ; FkA ;1 , prkA 6 prkA ;1 6 ::: 6 prkB 6 1 ; FkA ;1 6 ::: 6 1 ; FkB 8j = kB : : : kA ; 1 : prj 6 1 ; Fj . , , 8j = kB : : : kA ; 1: pj = pj +1 , , P (A)= pkA = pkB = P (B ).


78

.

.

,

.

.

prk > 1 ; Fk , P 0 ( ), 0 (f!k g) > P 0 (f P P 0 (A) >P 0(B ), .

, ( F P 0) !k+1 g). A = f!k g P (A)= P (B ), ( F P) , , ( F Pr). , ,

pk = pk+1 .

( F P ) ( F Pr).

-

( F Pr) B = f!k+1g -

( F P ) ( F Pr). ( ( F Pr). ( F P 0) F: P 0 (A) > P 0 (B ). kA
F

P)

( F Pr), P 0 (A) = P 0 (f kA 6 j 6 kB ; 1: pj >pj +1, ,

A B2 0 (B ) = P 0 (f!k g), !kA g) > P B prj > 1 ; Fj . , P (A)= pkA > pj >pj +1 >
. ( F P ), (21) ( F P) , . , -

P 0 ( ),

,

1= p1 > p2 > ::: > pN > ::: > 0

pk = P (f!k g), k = 1 2 : : : ,
( )

( F Pr), . (21).

(21)

pk , k = 1 2 ::: , ::: 6 1.
, (21) ,

,

k > 1, pk < pk+1 < pk+2 <


79 ( F P ), P (f!ig) = pi, i = 1 2 : : :
2.

1.

,

,

P

Fs =

s X k
=1

,

(21) ( F Pr),
,

, -

prk , s =1 2 : : : (19)
,

,

prk = Pr(f!k g), k =1 2 : : :
s X

-

8 < Q = :Fs
5

E=

n

1 =1 ; 2s + 2s1 2j "j s =1 2 ::: f"1 "2 ::: g2 E +1 j =1

9 =

N 1 ;2 ; 2j " + " s = 2 3 : : : , lim 1 ;2 ; X 2s " = j s;1 s N !1 2N +1 2s s=1 j =1 o 0 "s > 0 ps >ps+1 s =1 2 : : : .

s;1 X

f" " : : : g : j"s j < 21s 2 ;
1 2

;

s; X
1

j

2j "j s = 1 2 ::: "s 6

=1

( F P)

2.

,

( F Pr)

, 1 , . 2.

3.

Q

"s : "s 6 0,
.

ps = p

1,

s+1

,

s =1 2 : : :

1.

"s =prs ;(1 ; Fs ):
(22)

( F Pr).

( F P) (22) (23)

Fs = Fs:

s X k
=1

prk

5

2Fs =1 + Fs;1 + "s s =1 2 : : : F0 =0 k Xj
,

k

=0

j

2

"j

= 0.

=1


80 ,

.

.

,

.

.

,
s 1 + 1 X 2j " s =1 2 ::: Fs =1 ; 2s 2s+1 j j =1 s;1 Xj 1 prs = 2s + "2s ; 2s1 2 "j s =1 2 ::: : +1 j =1

(24) (25) -

, ,

,

(24), (25) (26)

prs , s = 1 2 : : : , (19),

Fs;1 1 ; 2;s+1 +2;s , ,
s; X
1

prk > prk+1 > 0 k =1 2 : : : : (26) (24),
1

j

2j "j < 1 ; 2;s +2;s;

s X j
=1

2j "j < 1:

=1

s;1 X j"s j < 21s @2 ; 2j "j j =1

0

1 As

=1 2 : : : : (26) (25),

(27) (28)

1 "s 6 2s 2 ;

s; ; X 2j " j
1

j

+ "s;

1

s =2 3 : : : :

=1

FN

lim F N !1 N (24)

=1 (29)

N ;X lim 2N1+1 2 ; 2s "s =0: N !1 s=1


81 , ps > ps+1, prs ;(1 ; Fs ) > 0. 1 . 1 , , ,
s

1, "s = (22),
+1

"s > 0 , ps >p
1 ( F Pr) 2.

( F P) ( F Pr).

, ( F P)

-

"s > 0 , ps >ps+1 "s 6 0 , ps 6 ps+1:
1 3. , 2. 1

(30) ,

(27), (28), (29) (30). , s =1 (27) . , s =1 2 : : : k.

"s , s =1 2 : : : ,

j" j < 1,
1

j"k j + = 21k
s = k +1
(27)

0 k; 1 @2 ; X 2j "j A
1

j

> 0:

=1

1 j"k+1 j < 2 21k

0 k; 1 @2 ; X 2j "j A ; 1 "k : 2
1

j

(31)

=1


82

.

.

,

.

.

11 2 2k

= 22

0 k; @2 ; X 2j "j 0j k; 1 1 @2 ; X k
1 =1 1

,

j

=1

1 0 A ; 1 "k > 1 1k @2 2 22 1 00 2j "j A ; 1 @ 1k @2
22 (31) 0, ).

1 1 ; 2j "j A ; 2 j"k j = j 11 k; Xj A A ; 2 "j ; = 2 >
k; X
1 =1 1

j

0 -

=1

, (27) . (28)

( ,

"

s

(30) ,

0, (27) (29)

"s = 0,
, , ,
.

ps = ps;1,

"s;1 > 0.

"s , "s > 0, s X 0 6 2s "s < 2, 8s =1 2 : : : .
j
=1

,

2

.

N
(27).
1

"

k

"N = 21 N FN =1.
3.2.

0 N; 1 @2 ; X 2j "j A
j
=1

,

"k , k (32)

-

,

N-

'( )


83 { . ,
N

N
F( N )
1

( N F( N ) PN ) = ::: {N) { F( PN ( ) { , : , , -

PN (f!k g ::: f!kN g)= i=1:::N '(!ki ): min P ( k = !l ) = '(!l ) = pl , = ( 1 2 : : : N) 2 N c ' (x) = PN (fxg), x 2 N . ( N F( N ) PrN ),
. pr ( ) : pr (x) = PrN (fxg), x 2 N .
1 2

:::

N

,

N
,
2

'( )

, ,

.
1

= f1 2 3 4g P ( i = j ) = pj , i = 1 2 j = 1 4, 1 = p1 > p2 > p3 > p4 > 0. , 2 =( 1 2 ), , ( i 2 j f!ig f!j g , i j = 1 4): 1234 1 p1 p2 p3 p4 2 p2 p2 p3 p4 3 p3 p3 p3 p4 4 p4 p4 p4 p4 ,

2

2

=


84 (
1 2

.

.

,

.

.

)2 ,

2

, (

f!i g f!j g
1 2 3 4 1 pr1 pr2 pr3 pr4 2 pr2 pr2 pr3 pr4

2

,i 3 pr3 pr3 pr3 pr4

i

j = 1 4):
4 pr4 pr4 pr4 pr4

j

,

-

1 < pr 1 2 1 ; pr1 < pr 2 4 1 ; pr1 ;3pr2 < pr 3 6 pr4 = 1 ; pr1 ; , , , ,

3pr2 ;5pr3 : 7

< 1 ;3pr1 < 1 ; pr15;3pr2
. , -

<1

( ). A = f!2 g f!2 g = f!2 g2 B = ( ) n ((f!1 g f!1 g) (f!2 g f!1 g) (f!1 g f!2 g) (f!2 g f!2 g)) = 2 nf!1 !2 g2 . P2 (A) = p2 > p3 = P2 (B ), Pr2 (A) > Pr2 (B ). Pr2 (A) = pr2 , Pr2 (B ) = 1 ; pr1 ;3pr2 , . A 2 , f!1 !2g , B{ , 2 nf!1 !2g2 , . , pr1 pr2 prk > 0, k =3 4 Pr2 (f!1 !2 g2 )=pr1 +3 pr2 < 1. -


85 .

X
4

1

2

Pr( k = i) =
2

j

=1

min(pri prj ), i 2 , k = 1 2,
1

Pr( 2 = ij ,

1

= j )=

X
4

min(prj pri ) min(prk prj )
1

i j=1 4
, -

k

=1

,

.
3.

,

-

1 = p1 > ::: > pm > 0 k , k =1 : : : N , Pr( k = !j )=
m X i
1 =1

, ,

N k k = 1 ::: N , = f!1 !2 : : : !m g N
, -

m X iN ;1
=1

min(prj pri : : : pri
1

N;

1

)

j =1 : : : m

Pr( k+1 = !jk j 1 = !j ::: k = !jk )=
m X
+1

=

ik

:::

m X

1

+2 =1

m X

iN

ik

:::

m X
=1

=1

min(prj ::: prj
1 1

k

+1

pri
k

k

+2

::: priN ) ::: priN )

+1 =1

iN

min(prj ::: prjk pri

+1

k =1 : : : N ; 1 jk =1 : : : m


86
k; X; N r ; (r ;
1

.

.

,

.

.

1;

r

k ; (k ; 1) +1
N N

=1

1)N prr

< prk <

1;

k; X; N r ; (r ;
1

r

=1

1)N prr
N
:

kN ; (k ; 1)

k =1 : : : m ; 1, prm

;mN ; (m ;
(

1)N prm =1 ;

m;1 X r
=1

;rN ; (r ;
(

1)N prr :
1

:::

N

)

1

:::
4.

N

).
-

, 60 (. . 1,

. ).
2 22

100 , ( : )

N (0

2

)

-

x pr(x) = p 1 e; , ;1 2 p U (; = 2 p jxj 6 = 2, pr(x) ,

=0

< x < 1), ) p = 2) (
). )( . . 1,

p pr(x) = ( 2 );1 , )) , -


87

. 1. )

),

9, 7, 5, 2: ), , ) ( ( ( 2. , , : 4.0 { 1

( ).

(

-

7 , 8.0 { ,

5 , 14.0 {

9 , 6.0 { ,

N N-

N (0
3, ,

2

).


88

.

.

,

.

.

. 2. 10000 , , . { .

. { -

-

. 3. 10000 { , . ,

. { , .

-

.

2


89 (18). ( . 2, 3). . , . . ) , . , . ( , , , . , . ( , . , ) ( , , , 1). (17),

. (3). (14). ,

,


90

.

.

,

.

.

1] 2] 3] 4] 5] 6]

. .: .

.. .. .

. .: , 1974.

, 1984.

-

.. . 1983. . 269. 5. . 1061{1064. ..

. .: , 1975. . M.: , 1979. . // -

. .: , 1984. . 41{82. 7] Pyt'ev Yu.P. Morphological Image Analysis // Pattern Recognition and Image Analysis. 1993. Vol. 3. No. 1. Pp. 19{28. 8] .. . . .: , 2000. 9] . . .: , 1967.