111111
`
`1111111111111111111111111111111111111111111111111111111111111
`US0071 06348B2
`
`c12) United States Patent
`Matsumoto et al.
`
`(10) Patent No.:
`(45) Date of Patent:
`
`US 7,106,348 B2
`Sep.12,2006
`
`(54) TEXTURE INFORMATION ASSIGNMENT
`METHOD, OBJECT EXTRACTION
`METHOD, THREE-DIMENSIONAL MODEL
`GENERATING METHOD, AND APPARATUS
`THEREOF
`
`(75)
`
`Inventors: Yukinori Matsumoto, Tsukuba (JP);
`Hajime Terasaki, Tsukuba (JP);
`Kazuhide Sugimoto, Tsukuba (JP);
`Tsutomu Arakawa, Ryugasaki (JP)
`
`(73) Assignee: Sanyo Electric Co., Ltd., Moriguchi
`(JP)
`
`( *) Notice:
`
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 473 days.
`
`(21) Appl. No.: 09/994,829
`
`(22) Filed:
`
`Nov. 28, 2001
`
`(65)
`
`Prior Publication Data
`
`US 2002/0060686 Al May 23, 2002
`
`Related U.S. Application Data
`
`( 62) Division of application No. 09/254,127, filed as appli(cid:173)
`cation No. PCT/JP97/02997 on Aug. 28, 1997.
`
`(30)
`
`Foreign Application Priority Data
`
`Aug. 29, 1996
`Aug. 30, 1996
`Aug. 30, 1996
`Jul. 23, 1997
`Aug. 12, 1997
`Aug. 12, 1997
`
`(JP)
`(JP)
`(JP)
`(JP)
`(JP)
`(JP)
`
`................................... 8-248739
`................................... 8-248946
`................................... 8-248958
`................................... 9-214104
`................................... 9-217486
`................................... 9-217550
`
`(51)
`
`Int. Cl.
`G09G 5100
`(2006.01)
`G06K 9100
`(2006.01)
`G06K 9120
`(2006.01)
`(52) U.S. Cl. ...................... 345/640; 345/643; 382/173;
`382/282
`
`(58) Field of Classification Search ................ 345/581,
`345/582,586,589,606,623-626,629-630,
`345/640, 643, 655, 682; 348/578, 580-581,
`348/584-585, 586-590; 382/173,282-283,
`382/284-286, 295; G09G 5/00; G06K 9/00,
`G06K 9/20
`See application file for complete search history.
`
`(56)
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`4,982,438 A
`5,475,507 A *
`5,483,066 A *
`5,687,249 A *
`5,724,493 A
`5,832,134 A *
`5,862,508 A *
`5,864,640 A
`5,892,853 A *
`6,118,552 A *
`6,151,424 A *
`6,215,914 B1 *
`6,229,578 B1 *
`6,246,804 B1 *
`6,356,272 B1 *
`6,445,833 B1 *
`6,556,210 B1 *
`200110005204 A1 *
`2002/0048399 A1 *
`
`111991 Usami eta!.
`12/1995 Suzuki et a!. ............... 358/500
`111996 Sadjadi eta!. ........... 250/338.1
`1111997 Kato .......................... 382/104
`3/1998 Hosoya et al.
`11/1998 Avinash et a!. ............. 382/257
`111999 Nagaya et al ............... 7011207
`111999 Miramonti eta!.
`4/1999 Hirani et a!.
`............... 382/280
`9/2000 Suzuki eta!. ............... 382/166
`1112000 Hsu ........................... 382/294
`4/2001 Nakamura et al ........... 382/284
`............ 348/607
`5/2001 Acharya et a!.
`6/2001 Sato eta!. .................. 382/284
`. ....... 345/582
`3/2002 Matsumoto et al.
`.............. 382/285
`9/2002 Murata et a!.
`4/2003 Yamamoto et al .......... 345/418
`6/2001 Matsumoto et al ......... 345/418
`4/2002 Lee eta!. ................... 382/165
`
`FOREIGN PATENT DOCUMENTS
`
`EP
`JP
`JP
`JP
`JP
`JP
`JP
`JP
`JP
`JP
`JP
`JP
`JP
`JP
`JP
`
`735 512 A2
`61-138377
`5-135155
`6-258048
`06-309023
`06-311405
`06-337998
`07-287756
`7-109626
`07-320035
`07-336694
`8-14858
`08-014858 A
`8-147494
`08147494 A
`
`10/1996
`6/1986
`6/1993
`9/1994
`1111994
`1111994
`12/1994
`10/1995
`1111995
`12/1995
`12/1995
`111996
`111996
`6/1996
`6/1996
`
`v22o
`
`I MAGE STORAGE
`UNIT
`
`/10
`
`r
`
`ARITHMETIC LOGIC
`UNIT
`
`INFORMATION
`REGION
`STORAGE UNIT
`
`/231
`
`EXTRACTED I MAGE
`STORAGE UNIT
`
`Align Ex. 1007
`U.S. Patent No. 9,962,244
`
`0001
`
`

`

`US 7,106,348 B2
`Page 2
`
`JP
`JP
`
`8-331607
`09-231369
`
`12/1996
`9/1997
`
`OTHER PUBLICATIONS
`
`"Shape Measurement and Description of Curved Objects" by Yukio
`Sato and Hiroichi Fujita, Denshi Tsushin Gakkai, '79/1 vol. J62-D
`No.1.
`"Recovering 3D Models from Silhouette Sequence and Detecting
`Unexposed Regions" by Jiang Yu Zheng and Fumio Kishino,
`Denshi Joho Tsushin Gakkai, '93/6 vol. 176-D-11 No. 6.
`"Fundamental Study of Input Method of 3D digital Image" by
`Yoshiaki Usami and Misato NIO, Computer Vision 37-2, Jul. 18,
`1985.
`"Recent Tendency in Image Processing Algorithm" by Naokazu
`Yokoya, pp. 227-233, Shin Gijutsu Communications, 0 Plus E,
`Nov. 1986, edited by Takagi et a!.
`"3.4 Range Information From Geometry" pp. 88-93, Computer
`Vision edited by Dana H. Ballard and Christopher M. Brown.
`"An Iterative Procedure for the Polygonal Approximation of Plane
`Curves" by Urs Ramer, pp. 244-256, Computer Graphics and Image
`Processing (1972) I.
`"Estimation of Shape and Color from Bi-directional Voting Using a
`Sequence of Color Frames" by Hisayoshi Zaima and Tsuyoshi
`Yamamoti, Joho Shori Gakkai (1996).
`Photorealistic Scene Reconstruction by Voxel Coloring by Steven
`M. Seitz and Charles R. Dyer, pp. 1067-1073, 1997 IEEE.
`English translation of the Notice of Ground of Rejection received
`from the Japanese Patent Office dated Apr. 27, 2004 for the
`corresponding Japanese Patent Application No. 9-217550.
`English translation of the Notice of Ground of Rejection received
`from the Japanese Patent Office dated Jun. 22, 2004 for the
`corresponding Japanese Patent Application No. 09-232617.
`Takahiro Muraki et al. "Study on Virtual Viewpoint Image Genera(cid:173)
`tion Using Multi ViewPoint Image Selection Method" (in Japanese
`with English language translation), 1996 Proceedings of the Insti(cid:173)
`tute of Electronics, Information and Communication Engineers of
`Japan, Information-System 2, Aggregate Corporation Institute of
`Electronics, Information and Communication Engineers of Japan,
`Mar. 28, 1996, p. 228.
`English translation of the Notice of Ground of Rejection received
`from the Japanese Patent Office dated Aug. 3, 2004 for the corre(cid:173)
`sponding Japanese Patent Application No. 09-234829 (cited previ(cid:173)
`ously).
`English translation of the Notice of Ground of Rejection received
`from the Japanese Patent Office dated Aug. 3, 2004 for the corre(cid:173)
`sponding Japanese Patent Application No. 09-234829.
`
`English translation of the Notice of Ground of Rejection received
`from the Japanese Patent Office dated Aug. 3, 2004 for the corre(cid:173)
`sponding Japanese Application No. 09-217550.
`* cited by examiner
`Primary Examiner-Matthew C. Bella
`Assistant Examiner-Wesner Sajous
`(74) Attorney, Agent, or Firm-Westerman, Hattori, Daniels
`& Adrian, LLP
`
`(57)
`
`ABSTRACT
`
`The present method represents a three-dimensional shape
`model by polygons according to a plurality of object images
`information picked up by rotating a real object for every
`arbitrary angle to assign texture information on each poly(cid:173)
`gon from object image information having the largest pro(cid:173)
`jection area of the relevant polygon. In order to improve the
`color continuity between adjacent polygons, the object
`image information having correspondence between a poly(cid:173)
`gon of interest and an adjacent polygon thereof is selected so
`as to be the object image information approximating the
`shooting position and the shooting direction. An alternative
`method divides an object image into a plurality of regions,
`obtains difference between an object image and a back(cid:173)
`ground image in region level, outputs a mean value of the
`absolute value of difference in the region level, and detects
`the region having the mean value of absolute values of
`difference equal to or greater than a threshold value as the
`object portion. Another further method obtains a plurality of
`object images by shooting only a background of an object of
`interest and by shooting the object of interest during each
`rotation. A silhouette image is generated by carrying out a
`difference process between the object image and the back(cid:173)
`ground image. A voting process is carried out on the voxel
`space on the basis of the silhouette image. A polygon is
`generated according to the three-dimensional shape obtained
`by the voting process. The texture obtained from the object
`image is mapped to the polygon.
`
`27 Claims, 43 Drawing Sheets
`
`0002
`
`

`

`U.S. Patent
`
`Sep.12,2006
`
`Sheet 1 of 43
`
`US 7,106,348 B2
`
`FIG.1
`PRIOR ART
`
`AXIS OF ROTATION
`
`FIG.2
`
`SHOOTING PLANE
`
`CAMERA FOCUS
`POINT
`
`CONTOUR OF OBJECT OF INTEREST
`
`0003
`
`

`

`U.S. Patent
`
`Sep.12,2006
`
`Sheet 2 of 43
`
`US 7,106,348 B2
`
`FIG. 3
`
`1000
`
`~ D -150
`
`E
`
`n
`[6!
`
`130
`
`-'
`
`-) \
`I
`j.;;CJ-1
`I
`~
`
`t:=:!
`
`I
`
`FIG. 4
`
`140
`
`K
`
`200
`
`IMAGE STORAGE v-220
`UNIT
`
`~210
`
`ARITHMETIC
`LOGIC UNIT
`
`l
`
`230
`-...........
`
`SHAPE STORAGE
`UNIT
`
`1
`
`COLOR
`INFORMATION
`STORAGE UNIT
`
`240
`~
`
`0004
`
`

`

`U.S. Patent
`
`Sep. 12,2006
`
`Sheet 3 of 43
`
`US 7,106,348 B2
`
`FIG. 5
`
`IMAGE SHOOTING
`
`v- S10
`
`'
`
`SILHOUETTE IMAGE PRODUCTION
`
`'
`VOTING PROCESS
`
`~
`
`POLYGON REPRODUCTION
`
`~
`
`TEXTURE MAPPING
`
`v S12
`
`~ S14
`
`--- S16
`
`-- S18
`
`0005
`
`

`

`U.S. Patent
`
`Sep.12,2006
`
`Sheet 4 of 43
`
`US 7,106,348 B2
`
`F I G. 6 A
`
`IMAGE SHOOTING
`
`An
`
`FIG. 6 B
`SILHOUETTE
`IMAGE PRODUCTION
`
`Bn
`
`A3
`
`F I G. 6 C
`VOTING PROCESS
`
`Bn
`
`81
`
`FIG. 6 D
`POLYGON PRODUCTION
`
`F I G. 6 E
`TEXTURE MAPPING
`
`29
`
`27
`
`27
`
`0006
`
`

`

`U.S. Patent
`U.S. Patent
`
`Sep.12,2006
`Sep. 12,2006
`
`Sheet 5 of 43
`Sheet 5 0f 43
`
`US 7,106,348 B2
`US 7,106,348 B2
`
`
`
`FIG.7
`-I.J..
`
`0007
`
`0007
`
`

`

`U.S. Patent
`US. Patent
`
`Sep. 12,2006
`Sep. 12, 2006
`
`Sheet 6 of 43
`Sheet 6 0f 43
`
`U5 7,106,348 B2
`US 7,106,348 B2
`
`F 1 G. 8
`
`251
`
`
`
`51
`\MA.GE.
`
`OBJEC1
`
`0008
`
`0008
`
`

`

`U.S. Patent
`U.S. Patent
`
`Sep.12,2006
`Sep. 12, 2006
`
`Sheet 7 of 43
`Sheet 7 of 43
`
`US 7,106,348 B2
`US 7,106,348 B2
`
`UJ
`
`C.!:l < :E
`
`
`
`mo<§Swamo
`
`1-
`0 w
`J co
`0
`
`c
`Vi
`
`Wooafifo¢oco
`.‘WV6¢,\g,.a(1.9».va6..
`.I?w¢..n.
`co.co.
`wovafiwo.
`o.o,
`‘3.401;
`OCA.C.'4
`.v-I.Lgm..7
`
`.,..._
`m
`
`1-
`0 w
`J co
`0
`
`w
`C.!:l < ::;:
`
`1-
`0 w
`J co
`0
`
`U')
`
`co
`
`vm
`
`
`
`mag.5”.“me
`
`1-
`0 w
`J co
`0
`
`C"') co
`mm
`
`(j)
`
`m.OHh.
`CJ -LL
`
`C'-J m
`
`0009
`
`0009
`
`
`
`
`

`

`U.S. Patent
`
`Sep.12,2006
`
`Sheet 8 of 43
`
`US 7,106,348 B2
`
`FIG. 10A
`
`F I G. 1 0 B
`
`e 1 PLANE
`
`L81
`
`\
`
`L82
`(
`
`L81
`
`I
`--"1
`-
`
`lOB· .... -
`
`F I G. 1 1
`
`/300
`
`27
`
`0010
`
`

`

`U.S. Patent
`U.S. Patent
`
`Sep.12,2006
`Sep. 12, 2006
`
`Sheet 9 of 43
`Sheet 9 0f 43
`
`US 7,106,348 B2
`US 7,106,348 B2
`
`[]J
`C\1
`
`128
`
`.
`
`(.!} -lL
`FIG.
`
`LD
`
`/~7
`
`r - - - - - - - - - . ID \
`
`\
`
`
`\
`<(
`12A
`C\1
`,.....
`.
`(.!} -lL
`FIG. Q
`
`2]
`
`co .........
`c--.1
`
`0011
`
`0011
`
`

`

`U.S. Patent
`
`Sep. 12, 2006
`
`Sheet 10 of 43
`
`US 7,106,348 B2
`
`F I G. 1 3
`
`IMAGE SHOOTING
`
`SHAPE MODEL PRODUCTION
`
`v S20
`
`v S22
`
`~
`
`CORRESPONDENCE BETWEEN 30 SHAPE
`CONSTITUENT ELEMENT AND
`IMAGE
`
`v S24
`
`INTO COLOR
`DATA INPUT
`STORAGE UNIT
`
`INFORMATION v S26
`
`0012
`
`

`

`U.S. Patent
`
`Sep.12,2006
`
`Sheet 11 of 43
`
`US 7,106,348 B2
`
`F I G. 1 4
`
`IMAGE SHOOTING
`+
`SHAPE MODEL PRODUCTION
`~
`E max <= NUMBER OF 3D SHAPE
`CONSTITUENT ELEMENTS
`I max <= NUMBER OF SHOT I MAGES
`I cnt <= 0
`Prod [i=O- Emax-1] <= 0
`Id [i=O-Emax-1] <=-1
`
`S20
`
`S22
`
`vS2402
`
`~-!.
`
`Ecnt <= 0
`
`S2403
`
`S2406
`No
`VS2408
`
`S2410
`
`S2412
`
`-.J,
`V tmp <= INNER PRODUCT BETWEEN NORMAL ~S2404
`VECTOR OF lcnt-th IMAGE
`SHOOTING PLANE AND NORMAL
`VECTOR OF Ecnt-th 3D SHAPE
`CONSTITUENT ELEMENT
`~
`Prod [Ecnt] < Vtmp?
`lYes
`Prod [Ecnt] <= Vtmp
`I d [Ecnt] <=
`I cnt
`I
`.f
`Ecnt <= Ecnt+1
`~
`E cnt > Ernax ?
`~Yes
`I cnt <= I cnt+l
`,L
`I max ?
`I cnt >
`l Yes
`INFORMATION
`INTO COLOR
`DATA INPUT
`STORAGE UNIT
`(DATA OF i-th 3D SHAPE
`CONSTITUENT ELEMENT IS INPUT FROM
`ld [i]th IMAGE)
`
`S2414
`
`S2416
`
`S2418
`
`No
`
`No
`
`0013
`
`

`

`U.S. Patent
`
`Sep.12,2006
`
`Sheet 12 of 43
`
`US 7,106,348 B2
`
`FIG. 1 5
`
`/
`
`/
`
`/
`
`/
`
`/
`
`/
`
`/
`
`/
`
`/
`
`/
`
`260
`
`/
`
`/
`
`/
`
`/
`
`/
`
`@
`
`//~==============================~
`START
`-..
`Emax <= NUIMJER OF 3D SHAPE
`Cll!STI TUENT ELEMENTS
`I max <= NUI.IlER OF SHOT I MAGES
`lent<= 0
`Prod [i=O- Emax-1] <= 0
`Id [i=O-Emax-1] <= -1
`
`S240
`2
`
`•
`
`V- <= INNER PROOUCT BETl'IEEN NORMAL S2404
`VECTOO Cf !cnt-th IMAGE
`SHOOTING PLANE AND NOOWL
`VECTOO Cf Ecnt-th 30 SHAPE
`CONSTITUENT ELEIICNT
`.J..
`S2406
`Prod [Ecntl ;;;! Vtmp ?~
`S2408
`.J..Yes
`Prod [Ecnt] <= Vtmp
`Id (Ecntl <=lent
`.Ji'
`
`Ecnt <= Ecnt+l
`+
`~
`Ecnt ;;:;:; Emax ?
`.;Yes
`I cnt <= I cnt+l
`"'
`I cnt ?;, I max ?
`Hes
`INTO COLOR INFORMATION
`DATA INPUT
`STORAGE UNIT
`(DATA OF i-th 30 SHAPE
`CONSTITUENT ELEMENT IS INPUT FROM
`ld [i]th IMAGE)
`
`No
`
`SZ41 0
`
`S241
`2
`
`SZ41 4
`
`SZ41
`6
`
`SZ41 8
`
`'
`
`' ' ' ' ' ' ' '
`
`'
`
`' ' ' ' '
`' ' '
`
`' ' '
`
`140
`
`0014
`
`

`

`U.S. Patent
`
`Sep.12,2006
`
`Sheet 13 of 43
`
`US 7,106,348 B2
`
`F I G. 1 6
`
`IMAGE SHOOTING
`J,
`SHAPE MODEL PRODUCTION
`!
`Emax <= NUMBER OF 3D SHAPE
`CONSTITUENT ELEMENTS
`I max <= NUMBER OF SHOT
`IMAGES
`I cnt <= 0
`Area [i=O- Emax-1] <= 0
`I d [i=O- Emax-1] <= -1
`'1
`Ecnt <= 0
`
`"1
`A tmp <= AREA OF Ecnt-th 3D SHAPE
`CONSTITUENT ELEMENT PROJECTED
`ON lcnt-th IMAGE
`r
`Area [Ecnt] < A tmp ?
`~Yes
`Area [Ecnt] <= Atmp
`I d [Ecnt] <=
`I cnt
`-L
`.J;
`Ecnt <= Ecnt+1
`!
`Ecnt > Emax ?
`~Yes
`I cnt <=
`I cnt+1
`!
`I cnt >
`I max ?
`! Yes
`INTO COLOR INFORMATION
`DATA INPUT
`(DATA OF i-th 3D SHAPE
`STORAGE UNIT
`CONSTITUENT ELEMENT IS INPUT FROM
`ld [i]th IMAGE)
`
`No
`
`No
`
`S20
`
`S22
`
`I--S2422
`
`S2423
`
`~..--S2424
`
`S2426
`No
`VS2428
`
`S2430
`
`S2432
`
`S2434
`
`S2436
`
`~..--S2438
`
`0015
`
`

`

`U.S. Patent
`
`Sep.12,2006
`
`Sheet 14 of 43
`
`US 7,106,348 B2
`
`F I G. 1 7
`
`PROVISIONAL CORRESPONDENCE BETWEEN 3D ~.--S2440
`SHAPE CONSTITUENT ELEMENT AND
`IMAGE
`
`N
`
`J
`~
`<= NUMBER OF 3D SHAPE
`CONSTITUENT ELEMENTS
`Cnt <= 0
`F lg <=OFF
`
`J
`"l
`Pre_lbl <=NUMBER OF IMAGE
`CORRESPONDING TO Cnt-th 3D
`SHAPE CONSTITUENT ELEMENT
`!
`COMPUTE
`IMAGE OBTAINING OPTIMUM
`EVALUATION VALUE FOR Cnt-th 30 SHAPE
`CONSTITUENT ELEMENT
`!
`New_ I b I <= NUMBER OF NEW
`CORRESPONDING IMAGE
`OBTAI NED BY COMPUTATION
`.t.
`New_lbl ::f:. Pre_lbl ?
`! No
`F lg <=ON
`.-
`Cnt <= Cnt+1
`i
`Cnt > N ?
`~Yes
`F lg = OFF ?
`~Yes
`
`~ END ~S2460
`
`~S2442
`
`~.--S2444
`
`~S2446
`
`~S2448
`
`S2450
`Yes
`
`S2452
`v
`
`~.--S2454
`
`S2456
`
`S2458
`
`No
`
`No
`
`0016
`
`

`

`U.S. Patent
`US. Patent
`
`Sep. 12, 2006
`Sep.12,2006
`
`Sheet 15 of 43
`Sheet 15 0f 43
`
`US 7,106,348 B2
`US 7,106,348 B2
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`-
`
`
`
`>-
`N ><
`.........
`
`II III-IlllllllnzaZQZNIIlIll-lllllllllll
`
`III-IIIIIIIIII-IQZQZQZIIlIII-III-III-III
`
`IIIIIIIIIIIIIIIHZQZQZQBIIIII-IIIIIIIIIII
`
`
`I‘ll-III-IIIIIIZQZEZQZ?RIIIIIIIIIIIII-II
`Ills-IIIIIIIllnazazazaansIIIIIlIll-lllll
`
`Instill-Illlllmzazazazmanll-ll-IIIIIIII-
`
`
`Il-II-IlIIllllzazgmezzazanrllulIsl-III.-
`sluts-IlllllluamzazzzazazanllillllllIII-
`IIIIIIIIIIIllflz2£2Z26262626IIIIIIIIIIIII
`
`lint-IIIIII-mazmzaznzazazagain-Ilium...-
`Initial-Illlmnazzz52525202gag-IIIIIIIIII
`
`lllllllll lizazazazazazazazazullllllllnl
`llllllllllluazazazazazazazaznallllllllll
`
`Insulin-Inluzazazazazazazazezna-llnlllll
`
`
`Inning-Illmzazazazazazazazmagmas-lull..-
`Install-InmazazazazazazazzzaanazulIl-III
`III-IlullgazazazazazazaznznznmzaMI-Illll
`
`
`llllllllIbZflZflZflZflZflZflZflZflZflflflazfix
`....--..
`
`Illilllilzazazazazazazezaznzgagazg
`,.....
`II
`Inmazazazazazazaznzzaues-nll
`
`>-
`.-
`IIMZEZQZQZflZflZQZflZLilI-IIII
`.- CD IIZflZflZflZgZfllfil III-II-IIIII
`
`0
`
`-
`II
`IHQZQZfiZZ‘IIIII III-III...-
`>-
`,_
`F-
`III-IIIIIII
`IWZ£HIIIIIIIIII
`~
`><
`..........
`0
`X ..........
`
`
`
`
`
`DATAINCOLORINFORMATIONSTORAGEUNlT
`
`\
`
`-C"J »
`
`C'.i
`X
`.........
`
`
`
`w
`<.!:J < ::E
`z
`0
`0 w
`1-
`0
`UJ
`J
`0
`0:::: a...
`z
`0
`<.!:J
`CX) >--I
`,... 0...
`
`
`
`18POLYGONPROJECTEDONIMAGE
`
`(.!) -LL
`FIG.
`
`0 ~~~
`
`0
`X
`..........
`
`.,....
`>.
`-.,....
`X
`.........
`
`0017
`
`0017
`
`

`

`U.S. Patent
`
`Sep.12,2006
`
`Sheet 16 of 43
`
`US 7,106,348 B2
`
`F I G. 1 9
`
`Emax <= NUMBER OF 3D SHAPE
`CONSTITUENT ELEMENTS
`I max <= NUMBER Of SHOT I MAGES
`Ecnt <= 0
`_, -.
`I cnt <= 0, wacc <= 0
`
`~.
`
`_s2soo
`
`S2501
`
`S2502
`No
`
`I
`I
`
`~S2504
`
`lcnt-th IMAGE IS INPUT
`SUBJECT OF COLOR OF
`Ecnt-th 30 SHAPE
`CONSTITUENT ELEMENT ?
`~Yes
`wght <= AREA OF Ecnt-th 30 SHAPE
`CONSTITUENT ELEMENT PROJECTED
`ON lcnt-th IMAGE
`~
`INFORMATION OF Ecnt-th 3D _szso6
`AS COLOR
`SHAPE CONSTITUENT ELEMENT, APPLY
`WEIGHT OF INFORMATION OF lent IMAGE
`BY wght. AND ACCUMULATE INTO COLOR
`INFORMATION STORAGE UNIT
`.1-
`wacc == wacc+wght
`I +
`I cnt <=
`I cnt+1
`t
`I max ?
`I cnt >
`~Yes
`INFORMATION ACCUMULATED .-S2512
`DIVIDE COLOR
`IN COLOR
`INFORMATION STORAGE UNIT BY
`wacc
`
`S2508
`
`S2509
`
`S2510
`
`S2514
`
`S2516
`
`No
`
`No
`
`t
`Ecnt <= Ecnt+1
`+
`Ecnt > Emax ?
`.1- Yes
`~ END
`
`/szs1a
`
`0018
`
`

`

`U.S. Patent
`
`Sep.12,2006
`
`Sheet 17 of 43
`
`US 7,106,348 B2
`
`F I G. 2 0
`
`F I G. 2 1
`
`v S20
`
`IMAGE SHOOTING
`1
`SHAPE MODEL PRODUCTION
`l
`CORRESPONDENCE BETWEEN 3D SHAPE CONSTITUENT 1-- S30
`ELEMENTS AND PLURALITY OF
`IMAGES
`
`I-- S22
`
`l
`
`INTO COLOR INFORMATION STORAGE
`
`....- S32
`
`DATA INPUT
`UNIT
`
`0019
`
`

`

`FIG. 2 2
`
`301
`
`/
`
`/
`
`/
`
`/
`
`/
`
`/
`
`/
`
`/
`
`/
`
`/
`/ /
`
`260
`
`/
`- /
`
`/
`
`@
`
`\.
`'\
`'\
`\.
`'\
`\.
`
`',
`
`\.
`\.
`\.
`'\
`\.
`\.
`'\
`
`D
`
`S1
`
`REGION SEGMENTATION PROCESS OF ~
`OBJECT
`IMAGE
`STORING PROCESS OF REGION
`INFORMATION
`DIFFERENCE PROCESS BETWEEN
`OBJECT
`IMAGE OF EACH REGION AND
`BACKGROUND
`IMAGE
`
`VALUES OF DIFFERENCE IN EACH
`REGION
`DETECTION PROCESS OF OBJECT
`MEAN VALUE OF ABSOLUTE VALUES
`OF DIFFERENCE AND THRESHOLD
`VALUE
`
`-- S2
`-- S3
`COMPUTE MEAN VALUE OF ABSOLUTE -- S4
`PORTION BY COMPARISON BETWEEN -- S5
`EXTRACTION OF DETECTED OBJECT --
`
`I
`
`I iJnRrtnN
`PORTION
`
`I I-S6
`
`e •
`
`00
`•
`~
`~
`~
`
`~ = ~
`
`rFJ
`('D
`
`'? ....
`
`N
`
`~
`
`N
`0
`0
`0\
`
`('D
`
`rFJ =-('D
`.....
`....
`0 .....
`
`QO
`
`.j;o.
`(.H
`
`d
`rJl
`
`"'--...1
`
`~
`
`""""' = 0'1 w
`00 = N
`
`0020
`
`

`

`U.S. Patent
`
`Sep.12,2006
`
`Sheet 19 of 43
`
`US 7,106,348 B2
`
`F I G. 2 3
`
`IMAGE STORAGE
`UNIT
`
`v22o
`
`210
`I
`ARITHMETIC LOGIC
`UNIT
`
`r-
`
`v231
`
`IMAGE
`EXTRACTED
`STORAGE UNIT
`
`r
`
`INFORMATION
`REGION
`STORAGE UNIT
`
`0021
`
`

`

`U.S. Patent
`
`Sep.12,2006
`
`Sheet 20 of 43
`
`US 7,106,348 B2
`
`vB
`
`I
`
`F I G. 2 4
`
`OBJECT IMAGE VA
`
`9
`
`/
`
`/
`DETECTION PROCESS OF OBJECT PORTION BY COMPARISON
`BETWEEN MEAN VALUE OF ABSOLUTE VALUES OF DIFFERENCE
`AND THRESHOLD VALUE
`
`15
`
`EXTRACTION OF DETECTED OBJECT PORTION
`
`16
`
`/
`(OUTPUT)
`
`L-----------------------------------------1
`
`BACKGROUND
`110
`IMAGE
`I
`I
`r------- -------------~
`L 11
`I
`I
`I
`I
`I
`I
`I
`I
`
`REGION
`SEGMENTATION
`OF OBJECT IMAGE
`---------------
`I
`MEAN VALUE COMPUTATION OF ABSOLUTE VALUES OF
`DIFFERENCE IN EACH REGION
`
`SIMPLE DIFFERENCE
`... PROCESS BETWEEN OBJECT
`IMAGE AND BACKGROUND
`IMAGE
`
`13
`
`I
`I
`I
`I
`I
`I
`I
`I
`I
`1
`I
`I
`I
`I
`I
`I
`I
`l
`I
`l
`I
`l
`I
`I
`I
`I
`I
`I
`l
`I
`I
`I
`I
`I
`
`r--
`l
`I
`l
`1
`I
`l
`I
`I
`I
`l
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`
`0022
`
`

`

`U.S. Patent
`
`Sep.12,2006
`
`Sheet 21 of 43
`
`US 7,106,348 B2
`
`{)
`LO
`('I
`
`.
`
`(!J -
`
`LL
`
`(])
`LO
`('I
`.
`
`(.!J -
`
`LL
`
`<{
`LO
`C\J
`
`(!J
`
`-
`
`LL
`
`0')
`
`,_.
`
`II
`
`\f-o
`tr~
`~ro
`
`I
`
`0 z
`::>M
`ON
`0:::
`C!:J w
`::.::::~
`0< (
`<:.::liE
`co-
`
`......
`or-
`w ......
`""':)
`co 1-
`0 Cl) w
`LJ.._ 0::::
`ow
`1-wz
`c.!:S-
`<(
`:::iiE LJ._ -o
`
`c;
`«!
`
`.,....
`ctl
`
`0') C'..J
`.,....
`ro
`
`0023
`
`

`

`U.S. Patent
`
`Sep.12,2006
`
`Sheet 22 of 43
`
`US 7,106,348 B2
`
`F I G. 2 6
`
`OBJECT IMAGE SHOOTING
`(SET VALUE OF EACH PIXEL TO
`v(i,j))
`
`S111
`
`COMPUTATION OF DEPTH
`INFORMATION dp(i, j)
`BY STEREO METHOD
`
`S112
`
`REGION SEGMENTATION
`OF OBJECT
`IMAGE
`(EACH REGION IS R)
`
`S113
`
`COMPUTATION OF MEAN VALUE
`mdp \R) =I Rdp ( i, j) /n OF DEPTH
`INFORMATION FOR EACH REGION
`2 R IS TOTAL SUM
`IN R, n IS
`NUMBER OF PIXELS
`IN REGION R
`
`S114
`
`Yes
`
`No
`
`S116
`
`v (i' j): = 1
`
`S117
`
`0024
`
`

`

`U.S. Patent
`U.S. Patent
`
`Sep.12,2006
`Sep.12,2006
`
`Sheet 23 of 43
`Sheet23 0f43
`
`US 7,106,348 B2
`US 7,106,348 B2
`
`
`
`mw<E.So:5
`
`~
`::;)
`0
`
`~
`::;)
`Q
`
`meg:2o_szmzwmm2o_mum <hN.OHL
`
`:t:
`
`~ c... w
`
`Ohm.OHL
`-l..L.
`
`a:l
`r-....
`C\J
`
`th.GHL
`(!J -LJ...
`
`<l:
`r-....
`(\J
`
`(!J -LJ...
`
`w
`<!j < ::E
`z
`0
`~ < ::E a::
`0 u.. z
`
`
`
`waif2c_.2583Emma
`
`Q
`
`UJ
`
`<!j < ==
`
`z
`0
`1-<
`1-z w
`:::=
`C,!j w
`C/.)
`z
`0
`
`{!j
`
`UJ a::
`
`0025
`
`0025
`
`

`

`U.S. Patent
`
`Sep.12,2006
`
`Sheet 24 of 43
`
`US 7,106,348 B2
`
`F I G. 2 8
`
`SHOOT A PLURALITY OF BACKGROUND IMAGES
`
`S221
`
`COMPUTE MEAN VAlUE m(i,j), STANDARD
`DEVIATION a (i, j) FOR EACH PIXEl
`
`IMAGE (SET VAlUE OF
`SHOOTING OF OBJECT
`EACH PIXEL TO v(i,j))
`
`S222
`
`S223
`
`I v c i. j) -m < i. j) I <
`No
`
`S224
`Yes
`
`v (i. j): = 0
`
`S225
`
`v(i,j):= 1
`
`S226
`
`COMPLETED FOR ALL PIXELS ?
`No
`
`S227
`Yes
`
`0026
`
`

`

`U.S. Patent
`
`Sep.12,2006
`
`Sheet 25 of 43
`
`US 7,106,348 B2
`
`F I G. 2 9
`
`SHOOT A PLURALITY OF BACKGROUND IMAGES
`
`COMPUTE MEAN VALUE m(i, j), STANDARD
`DEV I AT I ON a ( i. j) FOR EACH PIXEL
`
`SHOOT PLURALITY OF OBJECT IMAGES
`
`COMPUTE MEAN VALUE mv(i, j) FOR EACH
`PIXEL OF OBJECT
`IMAGE
`
`S221
`
`S222
`
`S333A
`
`S333B
`
`lmv (i. j) -m (i, j) I <
`No
`
`S334
`Yes
`
`S335
`I
`
`mv (i, j) : = 0 J
`
`mv(i, j) := 1
`
`S336
`
`COMPLETED FOR ALL PIXELS ?
`No
`
`S227
`Yes
`
`0027
`
`

`

`U.S. Patent
`
`Sep.12,2006
`
`Sheet 26 of 43
`
`US 7,106,348 B2
`
`F I G. 3 0
`
`~
`
`SHOOT A PLURALITY OF BACKGROUND IMAGES
`
`S221
`
`COMPUTE MEAN VALUE m(i, j), STANDARD
`DEVIATION a (i, j) FOR EACH PIXEL
`
`~S222
`
`IMAGE (SET VALUE OF ~S223
`SHOOTING OF OBJECT
`EACH PIXEL TO v(i, j))
`!
`REGION SEGMENTATION OF OBJECT
`(SET EACH REGION AS R)
`
`IMAGE
`
`~S441
`
`COMPUTE md(R)=O::Riv(i, j)-m(i, j) 1)/n
`FOR EACH REGION
`IR IS TOTAL SUM
`
`IN R, n IS THE NUMBER OF
`
`f.-- S442
`
`PIXELS WITHIN REGION R r
`
`COMPUTE m a- (R) =IRa- ( i. j) /n FOR EACH
`REGION
`
`_l -!
`md(R) < kma (R) ?
`No
`
`I v(i,j):=1, ((i, j) eR)
`
`~.--S443
`
`S444
`Yes
`
`~4 45
`( (i. j) ER) J
`
`I v (i' j): =0 ...
`S446
`
`COMPLETED FOR ALL REGIONS ?
`No
`
`S447
`Yes
`
`~~
`
`0028
`
`

`

`U.S. Patent
`
`Sep.12,2006
`
`Sheet 27 of 43
`
`US 7,106,348 B2
`
`FIG. 3 1
`
`~
`
`SHOOT A PLURALITY OF BACKGROUND IMAGES
`
`S221
`
`COMPUTE MEAN VALUE m(i,j), STANDARD
`DEVIATION a (i. j) FOR EACH PIXEL
`
`SHOOT PLURALITY OF OBJECT IMAGES
`!
`COMPUTE MEAN VALUE mv(i, j) FOR EACH
`IMAGE
`PIXEL IN OBJECT
`
`REGION SEGMENTATION OF AVERAGED OBJECT
`IMAGE (SET EACH REGION AS R)
`!
`COMPUTE md(R)=(IR!mv(i, j)-m(i. j) D/n
`FOR EACH REGION
`IR IS TOTAL SUM
`IN R. n IS THE NUMBER OF
`PIXELS WITHIN REGION R
`
`f-- S222
`
`S333A
`
`f--S333B
`
`~s551
`
`f.- S442
`
`COMPUTE rna (R)=IRa (i, j)/n FOR EACH REGION
`I
`-~
`
`S443
`
`S444
`Yes
`
`md(R) < kma (R) ?
`No
`
`I mv ( i, j) : = 1.. ( (i, j) eR)
`
`S55
`5
`I
`I mv (i. j) : =0, ( ( i' j) ER) I
`S556
`
`COMPLETED FOR ALL REGIONS ?
`No
`
`S447
`Yes
`
`~~
`
`0029
`
`

`

`U.S. Patent
`
`Sep.12,2006
`
`Sheet 28 of 43
`
`US 7,106,348 B2
`
`F I G. 3 2
`
`109
`I
`
`SHOOTING DEVICE
`
`v-220
`
`IMAGE STORAGE UNIT
`
`v 113
`
`ARITHMETIC LOGIC/
`CONTROL UNIT
`
`240
`I
`COLOR INFORMATION
`STORAGE UNIT
`
`SHAPE STORAGE UNIT
`
`\
`230
`
`0030
`
`

`

`U.S. Patent
`
`Sep. 12,2006
`
`Sheet 29 of 43
`
`US 7,106,348 B2
`
`F I G. 3 3
`
`CALIBRATION
`
`v S8
`
`11f
`
`SHOOTING OF OBJECT OF
`INTEREST & BACKGROUND
`
`!,
`
`SILHOUETTE
`PRODUCTION
`
`IMAGE
`
`~
`
`VOTING PROCESS
`
`S10
`
`S12
`
`S14
`
`dt
`
`POLYGON PRODUCTION
`
`v S16
`
`,!I
`
`TEXTURE MAPPING
`
`v S18
`
`0031
`
`

`

`sep.12,2006
`
`sneet 30 of 43
`
`U.S. -patent
`
`US '7 ,106,348 B2
`
`
`
`Illli1111’eullllll‘l'lll.!!!!!!
`
`\ \~--~~--~--------~~--~~------J:
`
`\
`l
`\
`\
`
`' \
`
`l
`\
`
`' \
`
`•
`'
`
`' ' \
`
`\
`\
`I
`i
`\
`
`' \
`
`\
`I
`\
`\
`\
`I
`\
`
`liilll‘illiilltlfllilVliilIlilfll
`
`I
`I
`
`\
`\
`
`\
`~
`I
`\
`
`\
`\
`
`' \
`
`\ I
`
`0032
`
`u..
`
`0032
`
`

`

`U.S. Patent
`U.S. Patent
`
`Sep. 12, 2006
`Sep.12,2006
`
`Sheet 31 0f 43
`Sheet 31 of 43
`
`US 7,106,348 B2
`US 7,106,348 B2
`
`FIG. 3 5 A
`
`'
`
`120
`
`35>--~--:l
`
`z
`
`110
`
`X
`
`F I G. 358
`
`120
`
`35:----~-
`
`
`
`z
`
`' ...
`
`... ...
`
`... ...
`
`.........
`
`/3
`... ...
`
`y
`
`,
`,'(r
`
`y
`
`
`
`X
`
`F I G. 35C
`FIG. 35C
`
`120
`
`,
`
`.&----
`
`,
`
`\
`
`,"'
`' ' 35
`
`0033
`
`0033
`
`

`

`U.S. Patent
`
`Sep.12,2006
`
`Sheet 32 of 43
`
`US 7,106,348 B2
`
`FIG. 36
`
`40
`
`251
`
`I 't------
`'II, I 'r---(cid:173)
`I 'r-----
`
`... ,_ __ .,...
`
`...
`r- '~----~
`1.. .....
`.... ...
`l
`,.. ...
`f• ....
`I' ..... ,__ __ _.
`J'....,l
`I
`......
`(,.
`j' .... ,
`...... ,
`t'-.._ __ _
`I ' I ,-.,,
`t..
`...... ..._
`1 ..........
`'I.._
`1 .......
`I
`1..
`'1.._
`I "'I-.
`I
`'t,.
`'L..
`I
`1
`I
`'1..
`I "'l,.
`I
`J,.
`'1...
`I
`1
`.. L...
`.. I..
`l
`t..
`f
`'I..
`'t..
`l
`1
`.... I..
`I "'t..
`J
`...
`.. ..._ __ __
`........... '
`......... '
`f
`r- .,.I
`,... ,I
`........ ...,_ __ ~
`to- ._I
`I
`f'o .,.I
`f"
`I
`....
`I
`,...
`f...._ I" .._I
`.... ,.. ,I
`'1.,.
`r" ._1
`I
`,... .,_
`I
`
`............ ___ __
`'I.... I ' , I t-----
`.... ,
`...
`
`"1.,.
`
`r
`
`0034
`
`

`

`U.S. Patent
`U.S. Patent
`
`Sep. 12,2006
`Sep.12,2006
`
`Sheet 33 of 43
`Sheet 33 of 43
`
`US 7,106,348 B2
`US 7,106,348 B2
`
`N(
`
`:0
`
`42
`
`
`
`FIG.37
`-lL
`
`0035
`
`0035
`
`

`

`U.S. Patent
`U.S. Patent
`
`Sep.12,2006
`Sep.12,2006
`
`Sheet 34 of 43
`Sheet34 of43
`
`US 7,106,348 B2
`US 7,106,348 B2
`
`F I G. 3 8
`FIG.
`38
`
`z
`
`~
`
`..\..
`
`L}J; ....» dz
`
`r
`
`---251
`
`4“ww%
`_kw”;
`w.b
`MnN,Ixah.....F9..$31
`«Mme,myéfié
`bin.33}
`few$55.?mm
`
`39%4‘
`
`m“
`
`633%....wiumefia
`
`0036
`
`0036
`
`

`

`U.S. Patent
`
`Sep.12,2006
`
`Sheet 35 of 43
`
`US 7,106,348 B2
`
`FIG. 39A
`
`43a
`44a
`43b
`
`39B--
`
`44b
`41a
`
`43c
`
`41c
`
`44c
`
`F I G. 3 9 B
`
`41b
`
`398
`
`0037
`
`

`

`U.S. Patent
`
`Sep.12,2006
`
`Sheet 36 of 43
`
`US 7,106,348 B2
`
`F I G. 4 0
`
`CUT 30 SHAPE AT PLURALITY OF PLANES,
`OBTAIN CONTOUR LINE OF EACH CUT PLANE
`
`POLYGONAL APPROXIMATION OF EACH CONTOUR LINE,
`OBTAIN VERTEX COORDINATE OF THAT POLYGON
`
`PRODUCE POLYGON BY CONNECTING VERTICES
`CORRESPONDING TO ADJACENT CUT PLANES
`
`.......- SA1
`
`v SA2
`
`......-- SA3
`
`0038
`
`

`

`U.S. Patent
`U.S. Patent
`
`Sep. 12, 2006
`Sep.12,2006
`
`Sheet 37 0f 43
`Sheet 37 of 43
`
`US 7,106,348 B2
`US 7,106,348 B2
`
`F I G. 4 1
`
`c
`
`e
`
`
`
`B
`
`F
`
`0039
`
`0039
`
`

`

`U.S. Patent
`
`Sep.12,2006
`
`Sheet 38 of 43
`
`US 7,106,348 B2
`
`F I G. 4 2
`
`VERTEX OF CUT PLANE Sent
`c
`d
`
`b
`
`a
`
`e
`
`f
`
`A o ---------------cv-----0-----cv-----cv
`-----0-----0-----0-----0
`
`B
`
`c 0-----
`D 0-----
`
`VERTEX OF
`CUT PLANE
`Scnt+1
`
`I
`I
`I
`
`-----~-----@-----~-----~
`
`-----0-----~
`
`I
`
`'
`
`E 0-----~-----@-----
`
`F 0-----0-----0-----0-----(~)
`
`J
`
`•
`
`I
`
`•
`
`I
`
`I
`
`I
`
`.._
`
`G ~-----0-----0-----0---------------- O
`
`0040
`
`

`

`U.S. Patent
`U.S. Patent
`
`Sep. 12, 2006
`Sep.12,2006
`
`Sheet 39 0f 43
`Sheet 39 of 43
`
`US 7,106,348 B2
`US 7,106,348 B2
`
`F I G. 4 3
`FIG. 43
`
`27
`
`
`
`27
`
`F
`
`0041
`
`0041
`
`

`

`U.S. Patent
`
`Sep.12,2006
`
`Sheet 40 of 43
`
`US 7,106,348 B2
`
`F I G. 4 4
`
`s max <= NUMBER OF CUT PLANES
`Sent <= 0
`
`-- SB1
`
`I
`-4-
`\/max <= NUMBER OF VERTICES AT Scnt-th ~ SB2
`CUT PLANE
`Vent <= 0
`
`J
`-4-
`CONNECT Vcnt-th VERTEX OF Sent PLANE AND ~ SB3
`Vcnt+1 (th) VERTEX
`
`No
`
`No
`
`-- SB4
`
`SB5
`
`_.... SB6
`
`SB7
`
`Vent <= Vcnt+1
`
`Vent> Vrnax-1 ?
`Yes
`Sent <= Scnt+1
`
`Sent > Smax?
`
`Yes
`-----TO SB8
`
`0042
`
`

`

`U.S. Patent
`
`Sep.12,2006
`
`Sheet 41 of 43
`
`US 7,106,348 B2
`
`F I G. 4 5
`
`FROM SB7
`
`Sent<= 0
`
`j max <= NUMBER OF VERTICES OF Sent PLANE
`j max <= NUMBER OF VERTICES OF (Scnt+1)th
`PLANE
`
`CONNECT lth VERTICES TOGETHER OF Sent PLANE
`AND Scnt+1 PLANE
`i <= 1,
`j <= 1
`
`i_n <= i+1. j_n <= j+1
`
`SB8
`
`SB9
`
`SB10
`
`SB11
`
`d i st ([S cnt: i]. [Scnt+1: j_n])
`< dist([Scnt: i_n],
`[Scnt+1 :j])
`
`SB13
`.---..~--.--~------ - - - - - - -....J....., Y..-es ___ --L.------. SB14
`CONNECT i-th VERTEX OF
`CONNECT (i_n)th VERTEX OF
`Sent PLANE AND (j_n)th
`Sent PLANE AND j-th
`VERTEX OF Scnt+l PLANE
`VERTEX OF Scnt+1 PLANE
`j <= Ln
`i <=
`i_n
`
`SB17
`
`CONNECT i-th VERTEX OF
`Sent PLANE AND EACH OF
`(j~jmax-1th) VERTICES
`OF Scnt+l PLANE
`
`j ~ jmax-1 ?
`Yes
`CONNECT j-th VERTEX OF
`Scnt+1 PLANE AND EACH OF
`(i~imax-1)th VERTICES
`OF Sent PLANE
`
`S cnt <= S cnt+ 1
`
`SB19
`
`No
`
`Sent > Smax ?
`
`0043
`
`

`

`U.S. Patent
`
`Sep.12,2006
`
`Sheet 42 of 43
`
`US 7,106,348 B2
`
`F I G. 4 6
`
`s max <= NUMBER OF GUT PLANES
`Sent <= 0
`
`\/max <= NUMBER OF VERTICES AT Scnt-th CUT
`PLANE
`Vent <= 0
`
`CONNECT Vent-1 (th) VERTEX OF Sent PLANE
`
`No
`
`No
`
`Vent <= Vcnt+l
`
`V cnt > Vmax-1 ?
`Yes
`Sent <= S cnt+1
`
`Sent > Smax?
`Yes
`Sent <= 0
`
`SB5
`
`SB7
`
`CONNECT VERTEX OF Sent PLANE AND VERTEX OF
`Scnt+l PLANE SO THAT CONNECTED DISTANCE IS
`SHORTEST
`
`S cnt <= S cnt+ 1
`
`No
`
`Sent > Smax ?
`
`SB1
`
`SB2
`
`S83
`
`SB4
`
`SB6
`
`S88
`
`SC9
`
`SC10
`
`0044
`
`

`

`U.S. Patent
`U.S. Patent
`
`Sep.12,2006
`
`ea
`
`Sheet 43 of 43
`34a%m
`
`US 7,106,348 B2
`US 7,106,348 B2
`
`\
`\
`
`\
`\
`
`\
`\
`
`I
`
`I
`
`z
`0 -I -
`
`- 0
`
`1-
`1-
`L1J
`::::l
`:I:
`
`...J -Cl)
`
`z
`-
`0
`I -
`0
`::::l
`0
`0
`c:::
`c...
`z
`0
`C!)
`>-
`...J
`0
`0...
`
`<:.!::' z -0...
`0... < ==
`
`UJ
`0::
`:::l
`1-><
`I..U
`1-
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`0
`::::l
`Q
`Cl)
`0
`Cl)
`c:::
`u...r
`c...
`0
`0
`UJ
`0::
`C!)
`c...
`<
`==
`-
`C!)
`UJ -
`z
`1-
`0
`>
`
`622538528:8m8”m,5”$8.:2::
`
`
`sa;czééMae?
`nN22528:mag.E585;
`
`s8N Sm
` h?.GHu
`
`\
`\
`\
`\
`\
`
`\
`\
`
`' \
`
`\
`
`-lL
`
`0045
`
`0045
`
`

`

`US 7,106,348 B2
`
`1
`TEXTURE INFORMATION ASSIGNMENT
`METHOD, OBJECT EXTRACTION
`METHOD, THREE-DIMENSIONAL MODEL
`GENERATING METHOD, AND APPARATUS
`THEREOF
`
`This application is a division of prior application Ser. No.
`09/254,127, filed Nov. 1, 1999, which is a 371 ofPCT/JP97/
`02997 filed Aug. 28, 1997.
`
`TECHNICAL FIELD
`
`The present invention relates to a texture information
`assignment method of assigning texture information to a
`shape model of a real object of interest according to an
`object image obtained by shooting that real object of inter(cid:173)
`est, an object extraction method of extracting an object
`portion by removing an undesired portion such as the
`background from the object image, a three-dimensional
`model generation method of generating a three-dimensional 20
`model of an object of interest, and apparatus of these
`methods.
`
`BACKGROUND ART
`
`40
`
`2
`FIG. 1 is a diagram representing the concept of assigning
`texture information to the three-dimensional model gener(cid:173)
`ated as described above according to the image information
`continuously picked up by a camera.
`Japanese Patent Laying-Open No. 5-135155 discloses the
`case of obtaining image information by continuously rotat(cid:173)
`ing an object of interest and shooting the same, i.e., obtain(cid:173)
`ing image information in the resolution level of shape
`recognition with respect to a three-dimensional model of a
`10 human figure. More specifically, an image is picked up for
`every 1 o of rotation to obtain 360 images with respect to the
`object of interest.
`For the sake of simplifying the description, the case of
`shooting an image for every larger stepped angle will be
`15 described hereinafter. However, the essence is identical.
`Consider the case of picking up a total of n images by
`rotating an object of interest for every predetermined angle
`of rotation, as shown in FIG. 1. In this case, each image
`information corresponds to the label number of 1, 2, 3 ... , n.
`The object of interest is represented as a shape model
`(wire frame model) 300 using a polygon (triangular patch).
`When texture information is to be assigned to shape model
`300, color information (texture information) of the image
`information of a corresponding label number is assigned for
`25 each triangular patch according to the direction of the
`camera shooting the object of interest.
`More specifically, based upon the vector towards the
`target triangular patch from the axis of rotation of shape
`model 300, the texture information with respect to the
`triangular patch is captured from the image that has the
`direction of the shooting direction vector and this vector
`most closely matched. Alternatively, from the standpoint of
`intuition, a plurality of lines such as the circles of longitude
`of a terrestrial globe can be assumed with respect to the
`surface of the model. Texture information can be captured
`from the first image information for the triangular patch in
`the range of 0° to 1x360/n°, from the second image infor(cid:173)
`mation for the triangular patch in the range of 1x360/n° to
`2x360/n°, and so on. This method of capturing texture
`information will be referred to as the central projection
`system hereinafter.
`The central projection system is advantageous in that
`image information can be provided in a one-to-one corre-
`45 spondence with respect to each triangular patch or the
`constituent element forming the shape model (referred to as
`"three-dimensional shape constituent element" hereinafter),
`and that this correspondence can be determined easily.
`However, the central projection system is disadvanta-
`50 geous in that the joint of the texture is noticeable when the
`gloss or the texture of the color information is slightly
`different due to the illumination and the like since the texture
`information is assigned from different image information
`(image information of a different label number) to a three-
`55 dimensional shape constituent element that is not present
`within the same range of rotation angle when viewed from
`the axis of rotation.
`Furthermore, a correspon