Äîêóìåíò âçÿò èç êýøà ïîèñêîâîé ìàøèíû. Àäðåñ îðèãèíàëüíîãî äîêóìåíòà : http://imaging.cs.msu.ru/pub/2005.icpt.Yurin_Sveshnikova.ar.ru.pdf Äàòà èçìåíåíèÿ: Tue May 17 23:00:00 2005 Äàòà èíäåêñèðîâàíèÿ: Mon Oct 1 19:46:34 2012 Êîäèðîâêà:

: .
.. *, .. **. * - ** sveshnikova_n@list.ru, yurin_d@inbox.ru


. , . : ) , , , ; ) , .


[1-10]. . , . , , . . , , . [11], (ground truth), . , , , : , . , (), . , , , , . , , , ­ ? , , , , , ( ~20) , , [16,17]. , , , , [13,14]. , . , , . , . , , , , , , ( ), , [4,7,10]. , : () [1] () [2]. , . ­ , , ,

1


[1], . , , , , , . , , , , . .

1. .







, , , , , . (. 1). f = 1..F () .





...

f



...
j
f

...

i
j

f

k

c

i

s
c

p

c

Cj

f +1

... ...
k

f +2

...



f +1

i
j

f +1

f +2

i

f



...
... (u fp , v

f +2

f +1

i

j



...

f +2

(u

(u
(

fp

)
(
f +1 ) p

(

f +1 ) p

,v
(

)

f +2) p

,v

f +2)p

)...

. 1. . . , , , [16, 17]. . 1 u fp , v fp

(u

(

f +1) p

, v(

f +1) p

), (u

(

f + 2) p

, v(

f + 2) p

)

(

)

.. .

, , (. 1, ). , , , . . ,

2


, (. .1 ). , . . , , , , . . , .

2. .
(xp , yp , zp )


j








f

(xp , y p )

k

s

f

p

~~ u fp , v

fp

z
k

p

j
c

c

t

f

i
l
f

i

c

f

. 2. . , [1-3].

f = 1..F , , t f ().
,

~~ u fp , v fp - () . ,
(. . 2) :

p = 1..P s p ,

u

fp

=g

i f (s p - t f )
f

k f (s p - t f )

,v

fp

=g

j f (s p - t f )
f

k f (s p - t f )

,

(1)

l 1 g f = ~ ef = u f N 2 tg max

(

f

2

)

,

~ u fp u fp = ~ e , uf N

~ v fp v fp = ~ e , uf N

i f , j f , k f - , ,

f - (), k f , i f , j f ~e ; l f - . u f -

; N - , . gf, u fp , v [1]:
fp



max f

-

[-1 2 ,1 2]

~~ l f , u fp , v fp . z f = -k f t f , z ' f = z f / g f , k f s / z f << 1 ,

3


u fp = m f s p + t Xf u fp = i f (s p - t f ) / z ' f m = i , f v fp = j f (s p - t f ) / z ' f n f = j v fp = n f s p + tYf
(2) :

f f

z z

' f

' f

;

t Xf = - i f t tYf = - j f t

f f

z z

' f ' f

,

(2)

W = MS+ T ,

W' = W - T ,


(2')

W=
T = (t
X1

u11 v11 M uF v
1

u12 v12 M u v
1

F2 F2

F1

L u1P L v1P L M L u FP L vFP

(3)

tY

1

... t

XF

tYF ) , S = s
T

(

... s P , M = m

)

(

1

n

1

... m

F

n

F

)

T

W' , . , rank M = 3 , , , , [3].

1 - 1D = rank W = rank S = 2 - 2 D 3 - 3D

(4)

W' . W':

)) W ' = UV T = (U )( V T ) = MS , rank (W ' )

(5)

U, V - , = diag(1,...,n), n = min(2F, P), 1,...,n - W. , , , x . U V , , ) ) W. , , M S Q 3, [1]:

) ) )) ) ) W ' = MS = M (QQ -1 ) S = ( MQ)(Q -1S ) = MS ,
S . , MMT=MQQTMT, , , , Q:

) ) ) ) m f QQT mTf - n f QQT nTf = 0,

) ) m f QQT nTf = 0,

) )T m1 QQT m1 = 1.

(6)

, (6) . Q = QQ . (6) () SVD [12].
T

~

Q Q . , (6) Q , Q diag ( ± 1 ± 1 ± 1) . , , , [1]:

~

4


( M = MR0 ,

( T S = R0 S ,

R0 = [i f 0 , j f 0 , k f 0 ], k

f

0

= i f0 â j f0 ,

(7)

f 0 1..F. [1], (), . , S ( , ) M. , [2]. (1). , f, .. gf = g, (1) , zf (2) zf' t f i f , j f , k f , ,

(

)

(t xf , t yf , t zf ) : (1 + 1 (k f s p ) )u g zf '
fp

=

1 ((i f , s p ) + t xf ), zf '

(1 +

1 (k f s p ) )v g zf '

fp

=

1 (( j f , s p ) + t yf ). zf '

(8)

, (2), . : W'=W1 + W2,

= 1/ g
u12 v12 u v

, W1 = W (3),

W2 =

k 1s1 z1 ' k 1s1 z1 ' M k F s1 zF ' k F s1 zF '

u11 v11 u v

F1

F1

k 1s 2 z1 ' k 1s 2 z1 ' M k F s2 zF ' k F s2 zF '

L L L L L

F2

F2

k 1s P z1 ' k 1s P z1 ' M k FsP zF ' k FsP zF '

u1P v1P . u FP v FP

(9)

.. W , , W1, , , W2, W1, sp, kf, : W2 [2] , s p , k f , z ' f , ,



,





+1

/ , (5). (8)

, . . W2 (9) s p , k f , z ' f , . W', (6) s p , k f , z' f .

= arg min (


+1

/ ) ,

+1

, - W' (9).

FMIN [12], . - . 3 . , , . .

5


W 1

1.

3D ( ) [1]. , .. , . ( (2'), (5), (6) ) s p , k f , z ' f . q = 0,



(0)

=0.

2 3 4
`N o'

2.

. 2.1. W2, (9),

s p , k f , z'
2.2. 2.3.

f



(q)

= arg min (


+1

/ ) .

W', (9). W' (5)-(6).
(q) ( q -1)

5
3.

2.4.

6
4.

- |< : | q - , - .



,

M, S, T
. 3 - .

z- ( ). > 0. , S M.

5. x y ( f- , (7)). 6. (20), (30).

. () , , . . 4 P ~~ u fp , v fp .

(

)

P'

P



j


f

(xp , y p )

~~ u fp , v
~ ~ u ' fp , v '
fp

fp

k

f

C

dz

p

z

i
cp

f

l

f

. 4. . , [1]. . 4 , P' P ~~ , u ' fp , v ' fp ­ , , P' ,

(

)

. ++. W ( gf). , . VRML- [14].

6


3. ().
. ­ , . : L1: L2: Ax + By + z + D ­ h = 0; Ax + By + z + D + h = 0; (10)

h .

. , h .

. 5. . . 5 . : ­ , f ­ f - , r f ­ f - . , W', (4):

W ' = MS ,
f = 1..F ­ , p = 1..P ­ .

(11)

W' min(2F,P). W' : W' = W0 + , (12) = [ij] ­ 2F x P , , :



2

=

1 2 FP


i =1 j =1

2F

P

2 ij = 2 ;

=

1 2 FP


i =1 j =1

2F

P

ij = 0.

(13)

, (12), , . , , min(2F, P) , n. W'. ( ) . [1]. h , , (.. (10) z x y, S 2). V (. (5)), [3]. , n, . : 3 > n. (14) W' . , z .

7


z p = -( Ax p + By p + D m h) = -( Ax p + By p + D) ± h = z
,

(1) p

± h.

(15)

s

(1) p

= ( x p , y p , z (p1) )T ,
S1 = s

s
(1) P

( 2) p

= (0, 0, ± 1)
, S2 = s

T

S = S1 + h S 2 ,

(

(1) 1

... s

)

(

( 2) 1

... s

( 2) P

),

.

W' (, z): W'=MS1+h*MS2 = W1'+W2' (16) .. h = 0 : rank S1 = 2 rankW = 2 , , W' : h , . , rank S2 = 1 rank W'2 = 1, .. W', h, W'2 3.. [15] ( 1 ). ( ) . :

|| A || 2 =|| A ||2 = F
2F


P

2 aij =





2 i

;

, (13) :
2 n || ||2 =


f =1 p =1

w 2 = 2 FP 2 ; fp

(17)

W'2. .. rank W'2 = 1, , h 3 W'.

1 =|| W '2 || = FPh J , J = F
2 3 2 2


f =1

F



gf 2 i +j z zf cf

2

(

2 zf

)



(18)

(18) , . , a priori. , , F , . (18) r . r - -, . , , , , , r r r r r i z = i z (r ), j z = j z (r ), g = g (r ), z =| r | . = (r ) . (18), :

r g (r ) J = r |r | -
+

r rr 2r i z (r ) + j z2 (r ) (r )dr

2

(

)

(19)

.

4. .
, ( W ' ) . ,

hmin

, hmin ~ h .



h

8


. . 3 ~ h , hmin ~ h

3 =

n

, :

h
h

=



n 3

(20)

, : (5) W ' - . W ' = W +
0



, M S

W

0





. ­ (21)

.

min W 's - M S
M ,S

, W = M S .
0

M S . , ( ) ( S ) ( M ).

0



M S .

M .

S

, (22)

W ' = ( M + M ) ( S + S ) = M S + M S + M S + M S M S + M S + M S


(20) (21), , || M S |||| M S ||

M



S

;

«



». ,

, :

M M

S
S

(23)

W ' , , , , ±90° , . , . , , . . , z , S = [0,0, S z ] , . ,
T

(23) M m

z

- - M :

M m z
. .

|| S || S

S
S

- , (20):

9


S
S

=



n
3

M m z



n 3

(23')

. , , , ..

g = 1 i z 1

1

g1 j1 z1

...

gF i zF

F

gF i F , zF



g = 1 i z 1

1

g1 j1 z1

...

gF i zF

F

gF i F zF



(24)



, , , , :

|| M || =
2
2 i zf 0, i


f =1
2 0

F

gf 2 i zf + j z f

2

(

2 zf

)
(
f

(25)

[

2 0

]

2 j zf 0, j

[

]
2 z

, , g f / z

)

2

, ,

,

i

2 z



j

2 z

,

|| M || = i
2

(

+ j

2 z

)
F f =1

gf z f

2

(26)

/ , , . ,

, .

i

2 z

j

2 z

(26) :

|| M || = 2 j
2

2 z


f =1

F

gf z f

2



j

2 z

,

j

2 z

,
F

j =

j

2 z

. (27)

|| M || =


f =1



2 gf 2 i f + j2f = 2 z cf

(

)


f =1

F



2 gf z cf

|| M || j || M ||
(28) (23'), :

(28)

j || M ||= m z




n 3

(29)



j

(29), :

j =

|| M ||
m
z



n

(30)

3

10


5.

.

. «» , , , R+H, R ­ , H ­ , H~1000 , a â a , z = 0 , h. XY . , (0,0,-R). YZ F 90° . , N . . 6 .

. 6. «».

: 1. MatLab . 2. ( ) W' . 3. [2] [1] ++. 4. :



Shape

=

1 a

1 P


p =1

P

T (s p - s 0 ) 2 ; S = [s1 p

s

T 2

... sT ] ; S 0 = [s P

0T 1

s

0T 2

... s 0T ] . P

(31)


R = [i

Rotation

=

1 3F
F


f =1

F

(i f - i 0f ) 2 + ( j f - j0f ) 2 + (k f - k 0f ) 2 ;

(32)

1

j1 k

1

... i

j

F

kF ];

R 0 = [i

0 1

0 j1

k

0 1

... i

0 F

j0 F

kF ].

0

, ­ ; ­ . 5. (20), (30). 7-10 . : 60 o , h = 0.05 , 2 2 , 1000 0.1 [16]. , . . «1» , W' (2'). «2» , W' , [2] . , , .. . «3» , (17), (18) ,

11


. . 7, 9



3

.

, 15%. . 8, 10 n , n . , (17). 50%.

. 7.



. 8.

3

W' h .



n

W' h.

. 9.



. 10.

3

W' N.



n

W' N.

. 11-14 (31), (32) . . 11-14 «1» «2» , , . «4» «3» (20), (30), W' . «3» W (2'), . «4» W' , [2] . «5» (20), (30) (17) (18).

12


. 11. h .

. 12. h.

. 13. N.

. 14. N.

, (17), (18) (20), (30) . , . , . (20),(30) (17)-(19) , . / , , , , , . , . () µ. , 3 , 4



n

, . ,

. , (20),(30) , 3 4 . , , .

13


.
, , . ( ), , ( W). , . . , , 0.1 % 1 % , . / , , 0.1 % 1 % . . , (30) 2 . (20) 50%. ( ) , .. , . (20, 30) , , , , . , , , , . , .. .

.
1. Conrad I. Poelman, Takeo Kanade. A Paraperspective Factorization Method for Shape and Motion Recovery: //Technical Report CMU-CS-93-219 / School of Computer Science, Carnegie Mellon University. -- 11 December 1993. http://www.ri.cmu.edu/pubs/pub_1189.html, http://www.ri.cmu.edu/people/person_136_pubs.html . . , .. . , , . ­ . . 12- '2002 ­ . 123-129. , 2002. http://www.graphicon.ru/2002/pdf/Yanova_Re.pdf Joao Paulo Salgado, Arriscado Costeira. A multi-body Factorization method for motion analysis: //Tese para obtencao do grau de doutor em Engenharia Electrotecnica e de Computadores. /Universitade Technica de Lisboa Instituto Superior Rechnico. Lisboa, Maio de 1995. http://omni.isr.ist.utl.pt/~jpc/pubs.html Yuri Boykov, Olga Veksler, Ramin Zabih. Fast Approximate Energy Minimization via Graph Cuts: /Cornell University, 1999. http://www.csd.uwo.ca/faculty/yuri/ , http://research.microsoft.com/~vnk/, http://www.cs.cornell.edu/~rdz/index.htm. M. Watanabe S. K. Nayar and M. Noguchi. Real-time focus range sensor. Proc. of Intl. Conf. on Computer Vision, pages 995--1001, New York, USA, September 1995. ftp://ftp.cs.columbia.edu/pub/CAVE/papers/nayar/nayar\-nabe\-noguchi\-sensor\_iccv\-95.ps.gz. Ali Azarbayejani Tony Jebara and Alex Pentland. 3d structure from 2d motion. Technical report, MIT Media Laboratory, May 1999. Perceptual Computing Tech. Rep. #523. http://cgi.media.mit.edu/vismod/tr_pagemaker.cgi. http://vismod.media.mit.edu/. Vladimir Kolmogorov and Ramin Zabih. Computing Visual Correspondence with Occlusions using Graph Cuts. In: International Conference on Computer Vision, July 2001. http://www.cs.cornell.edu/rdz/Papers/KZ-ICCV01-tr.pdf Ruo Zhang, Ping-Sing Tsai, James Edwin Cryer, and Mubarak Shah. Analysis of shape from shading techniques. In IEEE CVPR - 94, pages 377--384, Seattle, Washington, June 1994. http://www.cs.ucf.edu/~vision/papers/cvpr943.pdf . University of Central Florida, Orlando,

2.

3. 4. 5. 6. 7. 8.

14


9.
10.

11. 12. 13. 14.

15. 16.

17.

Computer Science Department, Technical Report, 1993, http://www.cs.ucf.edu/~vision/papers/analysisOfShapeFromShadingTechniques.pdf Eric Krotkov Fabio Cozman. Depth from scattering. Technical report, Robotics Institute, Carnegie Mellon University, Pittsburgh, http://www.ri.cmu.edu/pub\_files/pub2/cozman\_fabio\_1997\_1/cozman\_fabio\_1997\_1.pdf. Michael H. Lin, Carlo Tomasi: Surfaces with Occlusions from Layered Stereo. In: IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 2003. D. Scharstein and R. Szeliski. A taxonomy and evaluation of dense two-frame stereo correspondence algorithms. IJCV, 47:7­42, 2002. http://www.middlebury.edu/stereo/. . ., . ., . . . . -.:,1980. 280 . . . , . . . . // 2004, .30, 5, . 48-68. . . , . . . . ­ . . 14- '2004 ­ . 200-207. , 2004. http://www.graphicon.ru/2004/Proceedings/Technical_ru/1[1].pdf. . . . ­ .: , 2001. Carlo Tomasi, Takeo Kanade. Shape and Motion from Image Streams: a Factorization Method, Part 3, Detection and Tracking of Point Features //Technical Report CMU-CS-91-132 / School of Computer Science, Carnegie Mellon University. -- April 1991. http://www.ri.cmu.edu/pubs/pub_2543.html Anton Shokurov, Andrey Khropov, Denis Ivanov. Feature Tracking in Images and Video. ­ . . 13- '2003 ­ . 177-179. , 2003.

15