張裕泰碩士論文.PDF

Size: px

Start display at page:

Download "張裕泰碩士論文.PDF"

绿劳
4 years ago
Views:

1 Delaunay

3 Delaunay x,y,z x y z Delaunay Spatal Redundances and Temporal Redundances - 1 -

4 [1] 480pxels 640pxels 8bts 640x480=307,200 byte [2] (Codng Redundancy ) (Interpxel Redundancy ) - 2 -

5 (Psychovsual Redundancy ) 480pxels 640pxels 8bts x480x30=9,216,000bytes nter-frame redundancy (Spatal Redundances) 1-3 -

6 1 (Temporal Redundances) 2 (a) (b) 2 (a)(b) (low pass flter) spatal temporal - 4 -

7 30-5 -

8 RGB ), ( ), ( ), ( ), ( B w w G w R Y + + = w w w = ), ( ), ( ), ( ), ( ), ( ), ( B G R Q I Y

9 - - 7 = ), ( ), ( ), ( ), ( ), ( ), ( Q I Y B G R PSNRpeak sgnal-to-nose rato MPEG = = N Msg Msg N RMSE 1 2 )] 2( ) 1( [ 1 N N = = = N N Msg Msg N RMSE )], 2( ), 1( [ 1 = = N u u N ) ( 1 σ

10 σ 2 u = 1 N N 2 N = 1 = 1 u 2 (, ) 2 σ msg1 10Log10( ) 2 σ 2 Q 10Log10( ) 2 σ R R - 8 -

11 3. MPEG - 9 -

12 - - 10

13 Delaunay Delaunay Vorono Dagram Vorono Vorono 1644 Le Monde de Mr Descartes ou Le Traté de la Lumére Prncpa Phlosophae (Descartes) Vorono Drchlet Vorono Vorono Vorono n Drchlet m m Vorono

14 Vorono 2(2 m -1) m (m-1) Vorono Drchlet Vorono Vorono Thessen Vorono [5] Horton [6] Whtney Thessen s method Thessen s polygon [7] 1909 Boldyrev(Popoff) Davs Hardng [8,9]Vorono nfluence polygons [7] Wgner Setz [10] Vorono Vorono Wgner-Setz regons Vorono Frank Kasper [11] Vorono

15 Vorono polyhedra Doman of an atom Vorono Brown [12] Vorono area potentally avalable(apa) Mead [13] Vorono plant regon Jack Vorono [14] Hoofd et al. Vorono [15] capllary domans Vorono Bogue[16] Vorono Sheh [17] Weghted Vorono Snyder dacey [18,19] Evans Vorono(Delaunay) [20,21] 1960 Vorono

16 Vorono 1970 Vorono [22] Vorono (mnmum spannng tree) convex hull k Vorono Vorono Delaunay Vorono Delaunay Whtney [7]Smth [23] Smplcal graph Smth Delaunay Delaunay smplces[24] Rogers [25] Chrst et al.radom lattce feld theory [26] Vonoro

17 B-ISDN(broadband ntegrated servces dgtal) Mark R. Pckerng VBR [27] B-ISDN moton compensated predctondctdscrete cosne transform VBR quantzer step sze Mark R. Pckerng quantzer VBR CBR [28]VBR CBR constant bt rate VBR CBR Ch Chang Kuo H.263 CBR [29]

18 [29]1 MBmacroblockGOBgroup of blocks GOPgroup of pctures 2 Ch Chang Kuo INTRA MB JNDust notceable dstorton zg-zag DCT Lagrange Lagrange multpler MB MB quantzaton parameter Thao Chang dstorton functon [30] dstorton measure close form 20%-65% RM8 SM3 [31,32] [33-35]

19 Chh-Feng Chang Ja-Shung Wang [36] MPEG CBR TM5 TM5 MPEG MPEG Hufang Sun [37]

20 Delaunay [39]Delaunay 4 Delaunay Delaunay [40] (a) (b) (c) (d) 4. Delaunay (a) (b) (c) 45 (d)

21 Delaunay Drchlet [43-45]Drchlet Delaunay [41,42] Drchlet Delaunay Delaunay Delaunay crcumcrcle property [39]Delaunay Drchlet n terrtores Drchlet 8 Drchlet

22 Delaunay 5 5. Drchlet ( )Delaunay ( ) Delaunay P P P non-cocrcularty assumpton Delaunay Non-collnearty assumpton m P= { p 1,..., pn} R ( n 2) p 1,..., pn 6a Non-cocrcularty assumpton

23 2 P= { p,..., pn } R (4 n ) C p,..., p P, k 4, 1 1 k C, P { p,..., p } C 6b \ 1 k 6. a b m R 4 m+2 Non-cocrcularty assumpton Delaunay Vorono Vorono Dagram Vorono V1 Vorono V2 Vorono Vorono Vorono Vorono Vorono V3 V4 Vorono m

24 1 Vorono 2 Vorono 7. Vorono Eucldean plane p P 1 P 3 P 1 P 3 tessellaton Vorono ordnary Vorono dagram Vorono

25 Vorono dagram V1 Vorono Eucldean plane 2 Vorono Vorono V1 n n 2 n < n p 1,..., p n x 1,..., x n n x x,,, I = n {1,..., n} p x, ) ( 1 x2 x p p 2 d p, p ) = x x = ( x x ) + ( x x ) ( 2 [ ] p p p p x x x, x, I n p p V1 V2 ( Vorono ) P = p,..., p } 2 n < x x,,, I = n {1,..., n}. { 1 n V ( p ) = { x x x x x for I }, n p Vorono

26 = V ( p ),..., V ( p )} { 1 n P Vorono ) V p ( p Vorono P = p,..., p } Vorono { 1 n V2 V ( p ) = { x x x x x, I }, n < Vorono Vorono V p ) Vorono ( Vorono e Vorono = V ( p ) = { x x x x x, I }, n Vorono Vorono V ( p ) V ( p ) Φ V p ) V ( p ) Vorono ( ) ( Vorono Vorono Vorono vertexvorono Vorono Vorono V Vorono Vorono Vorono Vorono Vorono Vorono

27 Vorono Vorono Vorono V1 V2 Vorono S V S = { V ( p1) S,..., V ( pn ) S}. Vorono S Vorono Vorono V p ) S V ( p ) S Vorono ( 8. Vorono Vorono 8 p p p p p p p p b( p, p ) b( p, p )

28 p p b ( p, p ) b( p, p ) = { x x x = x x },. H ( p, p ) = { x x x x x },. H ( p, p ) p p 2 V3 ( Vorono ) P = { p,..., pn R 2 n < x x,, I n 1 } V ( p ) = I I n \{ } H( p, p ) p Vorono (P) = V( p ),..., V( p )} P Vorono { 1 n V3 V2 x x x x x H p, p ) m ( V4 (R m Vorono ) P x x,,, I n m { p 1,..., p n R 2 n < = } V ( p ) = { x x x x x for I }, n = I I n \{ } H( p, p ) p m Vorono (P) = V( p ),..., V( p )} { 1 n P m Vorono H ( p, p ) = { x x x x x, }

29 V2 V p ) = { x x x x x } V p ) ( ( Vorono V3 convex set Vorono Vorono V1 2 R V (P) Vorono 2 R V3 V p ) H( p, p ) ( V p ) H( p, p ) H( p, p ) \ H ( p, p )] [ H( p, p ) \ H ( p, p )] = Φ ( [ Vorono Vorono Vorono 1 1 P = p,..., p } ( 2 n < ) { 1 n V ( p ) = { x x x x x, I }, n V p ) non-empty convex polygon ( V P) = { V ( P ),..., V ( P )} ( 1 n U n = 1 2 V ( p ) = R, [ V ( p ) \ V ( p )] [ V ( p ) \ V ( p )] = Φ,,, I. n P Vorono dagram V (P) tessellaton m 2 V1 R R R m

30 Vorono Vorono Vorono polytope Vorono Vorono n 2 Vorono Vorono Vorono 2 2 P = p,..., p } ( 2 n < ) { 1 n Vorono Vorono ) V p p CH(P) CH(P) P convex hull ( non-collonearty3 n < Vorono Delaunay Vorono Vorono Vorono Vorono Delaunay Vorono Vorono Vorono Vorono Vorono Vorono [7,8]4 m m Vorono

31 m Vorono (m-1)vorono (m-1)vorono (m-2)vorono 3 Vorono 2 Vorono Vorono 2 Vorono 1 Vorono 1 Vorono Vorono Vorono 9. Vorono (a) Delaunay (b) Delaunay (c) (b) Delaunay (d) (b) Delaunay

32 Vorono Vorono Delaunay D Vorono Delaunay Delaunay D2 Delaunay D3 Delaunay m p p p1, p2, p 3, p p 1 p 2 p 3 p 4 p1p3 p 2 p

33 Vorono V(P) P = p,..., p } ( 3 n < ) { 1 n non-collnearty assumpton Vorono q V p ),..., V ( p k ) ( 1 Vorono q Vorono p 1,..., p k q p p+ 1, = 1,..., k V(P) Vorono PCH(P) CH(P)Delaunay

34 D2 (Delaunay ) V(P) n P n 2 = { p1,..., p } R ( 3 n < ) Vorono P Q = q,..., q n } V(P) Vorono x 1,..., x k { 1 v Vorono q T = { x x = λ, λ = 1, λ 0, I } x = 1 k k = 1 D = T,..., } { 1 T n v I nv k = 3 DP Delaunay k 4 DP Delaunay Delaunay pretrangulaton T 2 k k 4 T,... 1 T k 2 k k 2 = T 1 T k = 3 T = D = { T11,..., T1k 2,..., 1,...,,..., 2} 1 Tn Tn Tn k v D P Delaunay D Delaunay v v n v T = { x x = λ, λ = 1, λ 0, I } x = 1 k k = 1 k Delaunay Delaunay Vorono Delaunay DDelaunay Vorono Vorono

35 Delaunay Delaunay Delaunay Delaunay (P) DDelaunay P Delaunay 2 R D2 m D3 D3 (m Delaunay ) V(P) n Vorono P = } m { p 1,..., p n R ( 3 n < ) Q = { q 1,..., q n } V(P)Vorono V ( p ),..., ( ) v 1 V p k q (m-1)voronot p 1,..., m p k I nv, = m + 1 D(P)= T,..., } k { 1 T n v m smplces D(P) P mdelaunay k m + 2 D(P)m Delaunay m + 2 k T m k smplces T (hyperplanes) T,... T smplces( 1 k m Tk m = T = T, 1 = m + 1 ) D( P) = { T11,..., T1 k,..., 1,..., } 1 m Tn v Tn v D(P)m Delaunay k m n v k D(P) smplex mdelaunay smplex[41] D1D2 Delaunay Delaunay Delaunay Delaunay P

36 Vorono Delaunay, n log n n [44] 10. Delaunay

37 AC

38 Delaunay Delaunay Delaunay Delaunay Delaunay 3.2 T ' 2 P x, y P x, y, P x, y = ( ) ( ) ( ) T ( ) ( ) ( ) ( ) P x, y ' x,y P y x,y

39 Delaunay 2.4 Delaunay Delaunay Delaunay

40 11 12 Delaunay Delaunay x,y,z x y z

41 Delaunay Delaunay Delaunay Spatal Redundances and Temporal Redundances H, ' 2 = P ( x,y,z) P ( x, y, z ), P ( x, y z ) H ( ) ( ) ( ) ( ) x,y,z ' x,y,z P z x,y,z P

42 Delaunay 2.4 Delaunay 14 G(A)G(P)G(B) A PB GAGB G P

43 AP BP G AB AB ( P) = G( B) + G( A) AB AP BP A B A P B P BP P A AB AP P A P B G AB A GB GP GA AP BP + = 1 GP GAGB AB AB ABC P ABP ACP BCPP G ABP ACP BCP ( P) = G( C) + G( B) + G( A) ABC ABC ABC

44 GP P GA A GB B GC C P A BCP ACP ABP BCP ABC ABC ABC P A P B C GA GBGC GP GA P A BC ABP ACP BCP + + = 1 GP ABC ABC ABC GAGBGB

45 ABCD P ABPCACPDBCDP ABDPP ABCP ABDP ACDP G + ABCD ABCD ABCD BCDP ( P) = G( D) + G( C ) + G( B) G( A) ABCD GP P GA A GB B GC C GD D BCDP P A BCDP ABCD ABCP ABDP ACDP ABCD ABCD P A ABCD P B C D GA GBGC GD GP GA P A BCD 1 Q={, } Q T={P 1,P 2,P 3,P 4, }

46 1. 2. Delaunay Delaunay 6. Delaunay

47 17 Delaunay

48 3.2 2 Delaunay 1. N 2. N Delaunay

49 Delaunay Delaunay

50 Delaunay bt bt 32 5 bt 8 bt 30 bt

51 queue

52 Football Garden Football MPEG PSNR MPEG 0.7 Bt Rate MPEG (1) Garden

53 Garden

54 (2)Football FootBall PSNR (db) Bt Rate (bts/pxel) MPEG

55 FootBall

56 Delaunay x,y,z x y z Delaunay Delaunay Delaunay Spatal Redundances and Temporal Redundances

57 - - 55

58 [1] Rafael C. Gonzalez, Rchard E. Woods(1992), Dgtal Image Processng, Addson-Wesley Publshng Company, 4-6. [2] (1996),,, [3] (1996),,, [4] (1996),,, [5] Thessen, A.H. (1911) Precptaton averages for large areas Monthly Weather Revew, vol. 39, [6] Horton, R.E. (1917) Ratonal study of ranfall data makes possble better estmates of water yeld Engneerng News-Record, vol. 79, [7] Whtney, E.N. (1929) Areal ranfall estmates Monthly Weather Revew,vol. 57, [8] Popoff, C.C. (1966) Computng reserves of mneral deposts: prncples and conventonal methods U.S. Department of the Interor, Bureau of Mnes, Informaton Crcular, [9] Haynes, K.E. and A.S. Fotherngham (1984) Gravty and Spatal Interacton Models, Sage Scentfc Geography Seres, Volume 2 Beverly Hlls, Calf.: Sage Publcatons

59 [10] Wgner, E. and F. Setz (1933) On the consttuton of metallc sodum Physcal Revew,vol. 43, [11] Frank, F.C. and J.S. Kasper (1958) complex alloy structures regarded as sphere packngs. I. Defntons and basc prncples Acta Crystallographca,vol. 11, [12] Brown, G.S. (1965) Pont densty n stems per acre New Zealand Forestry Servce Research Notes,vol. 38, [13] Mead, R. (1966) A relatonshp between ndvdual plant-spacng and yeld Annals of Botany, N.S.,vol. 30, [14] Jack, W.H. (1967) Sngle tree samplng n even-aged plantatons for survey and expermentaton Internatonal Unon of Forestry Research Organsatons, XIV. IUFRO-Kongress, Muchen, Papers VI, Secton 25, [15] Hoodf, L., Z. Turek, K. Kubat, B.E.M. Rngnalda and S. Kazda (1985) Varablty of ntercapllary dstance estmated on hstologcal sectons of rat heart Advances n Expermental Medcne and Bology,vol. 191, [16] Bougue, D.J. (1949) The Structure of the Metropoltan Communty: A Study of Domnance and Subdomnance Ann Arbor: Horace M. Rackham School of Graduate Studes, Unversty of Mchgan. [17] Sheh, Y-N. (1985) K.H. Rau and the economc law of market areas Journal of

60 Regonal Scence, vol. 25(2), [18] Snyder, D.E. (1962) Urban places n Uruguay and the concept of a herarchy Festschrft: C.F. Jones, Northwestern Unversty, Studes n Geography,vol. 6, [19] Dacey, M.F. (1965) The geometry of central place theory Geografska Annaler, vol. 47B, [20] Evans, I.S. (1967) The propertes of patterns of ponts, measured by apace fllng and angular relatonshps Geographcal Artcles (Cambrdge), vol. 8, [21] Boots, B.N. (1974) Delaunay trangles: an alternatve approach to pont pattern analyss Proceedngs, Assocaton of Amercan Geographers, vol. 6, [22] Shamos, M.I. and D. Hoey (1975) Closest-pont problems Proceedngs of the 16 th Annual IEEE Symposum on Foundatons of Computer Scence, [23] Smth, F.W. (1964) The structure of aggregates and the molecular knematcs of the vscosty of a Bernal lqud Canadan Journal of Physcs, vol. 42, [24] Smth, F.W. (1965) The structure of aggregates a class of 20-sded space-fllng polyhedra Canadan Journal of Physcs, vol. 43, [25] Rogers, C.A. (1964) Packng and Coverng Cambrdge Tracts n Mathematcs and Mathematcal Physcs No.54. Cambrdge: Cambrdge Unversty Press. [26] Chrst, N.H., R. Fredberg and T.D. Lee (1982) Random lattce feld theory:

61 general formulaton Nuclear Physcs, vol. 202, [27] Mark R. Pckerng, John F. Arnold(1994) A Perceptually Effcent VBR Rate Control Algorthm, IEEE Transactons On Image Processng, vol.3, no.5, [28] J. L. Mtchell, W.B. Pennebaker, C. E. Fogg, and D. J. LeGall, MPEG Vdeo Compresson Standard. New York:Chapman & Hall, [29] Ch Chang Kuo, Jn Jang Leou(1998) A New Rate Control Scheme for H.263 Images, 1998 Internatonal Computer Symposum Workshop on Image Processng and Character Recognton, [30] Thao Chang, Ya On Zhang,(1997) A New Rate Control Scheme Usng Quadratc Rate Dstorton Model, IEEE Trans. Crcuts Syst. Vdeo Technol., vol.7, no.1, [31] Specal group on codng for vsual telephony, Descrpton of reference model 8 (RM8), CCITT SGXV Workng Party XV/4, document 525, June [32] MPEG Vdeo Sm Edtoral Group, MPEG vdeo smulaton model three, ISO/IEC JTC1/SC29 WG11, July [33] M. Kawashma, C.-T. Chen, F.-C. Jeng, and S. Snghal, A new rate control strategy for the MPEG vdeo codng algorthm, J. Vsual Commun. Image Represent., vol. 4, no. 3, ,

62 [34] C.-T. Chen and A. Wong, A self-governng rate buffer control strategy for pseudoconstant bt rate vdeo codng, IEEE Trans. Image Processng, vol. 2, no. 1, 50-59, [35] C. Horne and A. Pur, Vdeo codng wth adaptve quantzaton and rate control, n Proc. SPIE Conf. Vsual Communcaton and Image Processng, 1992, [36] Chh-Feng Chang, Ja-Shung Wang, A stable buffer control strategy for MPEG codng, IEEE Trans. Crcuts Syst. Vdeo Technol., vol. 4, , [37] Hufang Sun, Wlson Kwok, Joel W. Zdepsk, Archtectures for MPEG compressed btstream scalng, IEEE Trans. Crcuts Syst. Vdeo Technol., vol. 6, no. 2, , [38] Arnold, D.B., Mlne, W.J. (1984) The Ues of Vorono Tessellatons n Processng Sol Survey Results IEEE CG&A, vol. 3,22-28 [39] A. Okabe, B. Boots, and K. Sughara (1995) Spatal Tessellatons, Wley, England. [40] A. M. Fnch, R. C. Wlson, and E. R. Hancock (1997), Matchng Delaunay Graphs, Pattern Recognton, vol. 30, no. 1, [41] D. J. Mavrpls (1990), Adaptve Mesh Generaton for Vscous Flows Usng Delaunay Trangulaton, J. Comput. Phys., vol. 90,

63 [42] D. G.. Holmes and S. H. Lamson (1986), Adaptve Trangular Meshes for Compressble Flow Solutons, n Proceedngs, Internatonal Conference on Numercal Grd Generaton n Computatonal Flud Dynamcs, Karlsruhe, West Germany, edted by J. Hauser and C. Taylor Pnerdge, Swansea, UK. [43] Ash, P.F. and E.D. Bolker (1985), Recognzng Drchlet tessellaton, Grometrae Dedcata, vol. 19, [44] Ash, P.F. and E.D. Bolker (1986), Generalzed Drchlet tessellaton, Grometrae Dedcata, vol. 20, [45] Green, P.J. and R. Sbson (1978), Computng Drchlet tessellaton n the plane, The Computer Journal, vol. 21, [46] N. A. Golax, R. W. Dutton (1997), Delaunay trangulaton and 3D adaptve mesh generaton, Fnte Elements n Analyss and Desgn, vol. 25, [47] N. A. Golas, T. D. Tsbouks (1994) An approach to refngn three-dmnsonal tetrahedral meshes based on Delaunay transformatons, Internatonal ournal of numercal methods n engneerng, vol. 37,

作为市场化的人口流动

作为市场化的人口流动 Workng Paper Seres No.30 2003 6 1 Lews 1954 Harrs et al. 1970; Felds 1974 50 1949 1957 70% 80% 1958 50 1949 1986 50 20.7% 60 17.0% 70 32.9% 1980 1986 29.4% 45.23% 1988 6 1978 2 Meng 2000 pp. 26-28 Cook