111111
`
`1111111111111111111111111111111111111111111111111111111111111
`US007558420B2
`
`c12) United States Patent
`Era
`
`(10) Patent No.:
`(45) Date of Patent:
`
`US 7,558,420 B2
`Jul. 7, 2009
`
`(54) METHOD AND APPARATUS FOR
`GENERATING A STEREOGRAPHIC IMAGE
`
`(76)
`
`Inventor: Kazunari Era, 4-1-11-201,
`Matsuba-cho, Kashiwa-shi, Chiba,
`277-0827 (JP)
`
`( *) Notice:
`
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 394 days.
`
`(21) Appl. No.:
`
`10/525,033
`
`(22) PCT Filed:
`
`Aug. 20, 2003
`
`(86) PCT No.:
`
`PCT/JP03/10499
`
`§ 371 (c)(l),
`(2), ( 4) Date:
`
`Feb. 17, 2005
`
`(87) PCT Pub. No.: W02004/019621
`
`PCT Pub. Date: Mar. 4, 2004
`
`(65)
`
`Prior Publication Data
`
`US 2005/0254702 Al
`
`Nov. 17, 2005
`
`(56)
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`6,445,833 B1 * 9/2002 Murata et al ................ 382/285
`
`FOREIGN PATENT DOCUMENTS
`
`EP
`EP
`JP
`JP
`JP
`JP
`JP
`wo
`wo
`
`0 918 439 A1
`1 235 438 A1
`A 05-091545
`A 8-29734
`A 10-051812
`A 2001-298753
`A-2002-123842
`WO 02/13141 A1
`WO-A-02/13141
`
`5/1999
`8/2002
`4/1993
`2/1996
`2/1998
`10/2001
`4/2002
`212002
`212002
`
`OTHER PUBLICATIONS
`
`Japanese Office Action, mailed on Sep. 4, 2007; with English Trans(cid:173)
`lation.
`Canadian Office Action, mailed on Oct. 30, 2007.
`Office Action of Canadian Corresponding Application No. 2,496,353
`issued Jul. 30, 2008.
`* cited by examiner
`Primary Examiner-Wesley Tucker
`(74) Attorney, Agent, or Firm---Oiiff & Berridge, PLC
`
`(30)
`
`Foreign Application Priority Data
`
`(57)
`
`ABSTRACT
`
`Aug. 20, 2002
`Aug. 20, 2002
`
`(JP)
`(JP)
`
`............................. 2002-238709
`............................. 2002-238710
`
`(51)
`
`Int. Cl.
`G06K 9100
`(2006.01)
`G06K 9136
`(2006.01)
`(52) U.S. Cl. ....................................... 382/154; 382/285
`(58) Field of Classification Search ................. 382/154,
`382/285
`See application file for complete search history.
`
`In a 3D image generating apparatus 1 depth values (Z-value)
`of pixels are calculated on the basis of grayscale values of2D
`image data. Next, a reverse determination, smoothing, distri(cid:173)
`bution adjustment, local adjustment, and the like are per(cid:173)
`formed on the Z-values. Next, parallaxes of pixels are deter(cid:173)
`mined on the basis of the Z-values of the pixels finally
`obtained, and the pixels are displaced acceding to the paral(cid:173)
`laxes, so as to generate data of a stereographic image.
`
`10 Claims, 43 Drawing Sheets
`
`

`
`11
`
`12
`
`13
`
`14
`
`15
`
`CPU
`
`ROM
`
`RAM
`
`CHARACTER
`GENERATOR
`
`TIME CIRCUIT
`
`TRANSMISSION
`CONTROL UNIT
`
`INTERFACE
`
`(TO I NET)
`
`~1
`
`~GNETIC1-J8
`----
`DISK DRIVE
`
`•
`
`I
`
`CD-ROM DRIVE
`
`22
`
`DISPLAY
`
`WcoJr1R~L~\nl= •I
`I
`
`FIG. 1
`
`21
`
`I
`
`I 23
`
`..) KEYBOARD
`
`25 c..
`INPUT
`~
`· 1CONTROL UNITh
`
`26
`
`I I .
`
`POINTING I
`
`DEVICE
`
`24
`
`~
`00
`•
`~
`~
`~
`
`~ = ~
`
`~ = :-
`
`~-....l
`N
`0
`0
`\0
`
`('D
`('D
`
`rFJ =-
`......
`.....
`0 .....
`
`.j;o.
`(.H
`
`d
`rJl
`-....l u.
`u.
`00
`~
`
`N = = N
`
`

`
`U.S. Patent
`
`Jul. 7, 2009
`
`Sheet 2 of 43
`
`US 7,558,420 B2
`
`FIG. 2
`16
`MI7 MIS Mig Ml10
`
`Ml4 MISM
`
`[Moving Images Selected By A User Are Displayed
`In This Area (2D mode)]
`
`MD
`
`Ml6
`MIS Ml7 MIS Mig Ml10
`
`[Moving Images Selected By A User Are Displayed
`In This Area (3D mode)]
`
`MD
`
`

`
`U.S. Patent
`
`Jul. 7, 2009
`
`Sheet 3 of 43
`
`US 7,558,420 B2
`
`FIG. 3
`
`BR
`
`BC
`
`SETTINGS
`
`lr
`:2
`IIPROJECTED
`.
`182
`<
`
`r DEPTH
`INTERFACE
`L
`
`_
`
`I 11
`
`rUNOUlATION
`L
`......_ __ _ 18_3 _
`RANGE
`UPPER r--"""-~
`LIMIT ....____.
`
`181
`FIRST LINE
`9
`I---RECESSED X ODD L I NE
`182 °
`111111 Itt I 185
`EVEN LINE
`~
`I 11 "'II SHAllOW -v~--- DEEP 186
`
`_.._
`
`184 1 I I I I I I I ~~1 BM~--O-K-----.1
`·
`-
`BM~CANCELI
`
`LOWER .....--"'-.....,
`LIMIT "---.......
`
`DEFAULT
`
`FIG. 4
`
`SLO
`y-
`SL2
`SL4
`·....r
`SL6
`v
`
`--v: SL1
`SL3
`SL5
`SL7
`"'v"
`
`•
`•
`•
`t-++~~~~~~~~~~~-++-~-++-~-€1_ FL 1
`~~~~~~~~~~~~~~~~""'- FL3
`t++~~~++-~++-~-++-H-f-++-~-++-~~H+ofl..... FL5
`~~~~~~~~~~~~~~~~~ FL7
`
`•
`•
`•
`
`

`
`U.S. Patent
`
`Jul. 7, 2009
`
`Sheet 4 of 43
`
`US 7,558,420 B2
`
`FIG. 5
`
`•
`•
`•
`
`FL 1
`FL3
`FLS
`FL7
`
`I,
`
`I I
`
`I I
`:I
`
`I'
`
`·(POLARIZING STRIPE FILTER )j
`.
`i
`AVAILABLE RANGE OF STEREOPSIS
`~·I
`
`I
`
`1 ...
`
`FIG. 6
`
`Flett
`
`

`
`U.S. Patent
`
`Jul. 7, 2009
`
`Sheet 5 of 43
`
`US 7,558,420 B2
`
`FIG. 7
`
`YES
`
`READ DATA OF A FRAME
`
`S101
`
`CONVERSION TO RGB
`
`GRAYSCALE VALUE ADJUSTMENT
`
`S104
`
`REVERSE DETERMINATION
`
`SMOOTHING
`
`DISTRIBUTION ADJUSTMENT
`
`LOCAL ADJUSTMENT
`
`INPLANE Z-VALUE ADJUSTMENT
`
`DISPLACEMENT OF PIXELS
`
`S106
`
`S107
`
`S109
`
`S110
`
`

`
`(MSB)
`
`(LSB)
`__,
`
`FIG. 8
`
`I
`I
`: R DATA(Sbits)
`R DATA(Sbits) : G DATA(6bits)
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`1 15
`~ ]"' ..,.] l - ]""""
`
`l
`
`.-
`
`X
`
`-..
`
`X
`
`j
`
`-
`
`...
`
`-
`
`-
`
`(FOR COLOR DEPTH OF 16 bits )
`
`(MSB)
`
`I
`I B DATA
`I G DATA
`I R DATA
`r- 8 bits + 8 bits + 8 bits -J
`
`(LSB)
`
`(FOR COLOR DEPTH OF 24 bits)
`
`(MSB)
`
`I
`I B DATA
`I G DATA
`I DUMMY DATA I R DATA
`r- 8 bits + 8 bits + 8 bits + 8 bits -J
`
`(LSB)
`
`(FOR COLOR DEPTH OF 32 bits)
`
`~
`00
`•
`~
`~
`~
`
`~ = ~
`
`2' :-
`
`~-....l
`N
`0
`0
`\0
`
`('D
`('D
`
`rFJ =(cid:173)
`.....
`0\
`0 .....
`
`.j;o.
`(.H
`
`d
`rJl
`"'--...1 u. u.
`N = = N
`
`00
`~
`
`

`
`U.S. Patent
`
`Jul. 7, 2009
`
`Sheet 7 of 43
`
`US 7,558,420 B2
`
`FIG. 9
`
`DECLARATION OF unsigned short *srcp
`
`CONVERSION OF src TO unsigned short
`
`srcp~(unsigned short) src
`
`CC+-0
`
`NO
`
`NO
`
`S207
`
`R+-(int)((*srcp & OxF800)>>11 )*30
`
`END
`
`G~(int)((*srcp & Ox07E0)>>5)*59
`
`B~(int)(*srcp & Ox001 F)*11
`
`*zinfo~(BYTE)((R+G+B)/1 00)
`
`srcp~ srcp + 1
`zinfo ~ zinfo + 1
`cc~cc+1
`
`S211
`
`

`
`U.S. Patent
`
`Jul. 7, 2009
`
`Sheet 8 of 43
`
`US 7,558,420 B2
`
`FIG. 10
`
`YES
`
`cc.-o
`
`------------....~8217
`~:..N:...!.O~----.
`CC<WD*HT?
`
`YES
`
`s.-(int)(*src )*11
`
`8218
`
`END
`
`G~(int)(*(src+1 )*59)
`
`R~(int)(*src+2)*30)
`
`*zinfo~(BYTE)((R+G+B)/1 00)
`
`srcp~ srcp + 1
`zinfo ~ zinfo + 1
`cc~ cc+ 1
`
`8220
`
`8222
`
`

`
`U.S. Patent
`
`Jul. 7, 2009
`
`Sheet 9 of 43
`
`US 7,558,420 B2
`
`FIG. 11
`
`DECLARATION OF unsigned long *srcp
`
`lf
`•
`DECLARATION OF unsigned long *srcp
`+
`srcp<E-(unsigned long) src
`t
`CC<E--0
`. .. :.t
`
`---
`,.
`R<E-(int)((*srcp & OxOOFF0000)>>16)*30 c END
`t
`G<E-(int)((*srcp & OxOOOOFF00)>>8)*59
`t
`8-E--(int)(*srcp & OxOOOOOOFF)*11
`
`S225
`,....f-1
`
`S226
`,...f-./
`
`S227
`~
`
`~228
`
`NO
`
`8230
`
`8231
`l.-J
`
`8232
`l.-J
`
`8233
`l.-J
`
`8234
`l.-J
`
`8229
`
`-=:::::::::::::
`
`CC<WD*HT?
`..__
`
`YES
`
`•
`
`*zinfo<E-(BYTE)( (R+G+B)/1 00)
`t
`srcp<E- srcp + 1
`zinfo <E- zinfo + 1
`cc <E- cc + 1
`
`

`
`U.S. Patent
`
`Jul. 7, 2009
`
`Sheet 10 of 43
`
`US 7,558,420 B2
`
`FIG. 12
`
`~SS1
`
`~SS2 SS3~
`
`~SS4
`
`~SS5 SS6~
`
`~SS7
`
`~ssa ssg~
`
`

`
`U.S. Patent
`
`Jul. 7, 2009
`
`Sheet 11 of 43
`
`US 7,558,420 B2
`
`FIG. 13
`
`START
`
`CALCULATE AVERAGE MZ
`
`8301
`
`8302
`
`8303
`
`NO
`
`S1+-S1+WEIGHT OF
`CTth SS
`
`S2~S2+WEIGHT OF
`CTth SS
`
`S306
`
`CT~CT+1
`
`8307
`
`

`
`FIG. 14
`
`NO
`
`8310
`
`REVERSE
`
`MAINTAIN
`
`8314
`
`REVERSE
`
`F2 MODE?
`"""YEs
`REVERSE
`
`8316
`
`~
`00
`•
`~
`~
`~
`
`~ = ~
`
`2' :-
`
`~-....l
`N
`0
`0
`\0
`
`('D
`('D
`
`rFJ =(cid:173)
`.....
`....
`N
`0 .....
`
`.j;o.
`(.H
`
`d
`rJl
`"'--...1 u. u.
`N = = N
`
`00
`~
`
`

`
`U.S. Patent
`
`Jul. 7, 2009
`
`Sheet 13 of 43
`
`US 7,558,420 B2
`
`FIG. 15
`
`I
`
`Mx
`...
`..;
`.....
`.,. \,/MM
`My ,h ~ I
`-
`
`Px
`
`..
`I
`~
`I
`MM
`
`'t\-
`
`Px
`
`f-.-
`Ill
`lllr My
`
`~---------------------------------------~---
`I
`~--~MM
`:
`L~_!
`Px
`
`I
`
`"""
`
`""
`
`I Mx
`
`

`
`U.S. Patent
`
`Jul. 7, 2009
`
`Sheet 14 of 43
`
`US 7,558,420 B2
`
`FIG. 16
`
`MTh~HT-CLN
`
`CALCULATE SM 1
`
`outinfo~SM 1/
`(MTh*MTw)
`
`cwo~cwo+1
`
`

`
`U.S. Patent
`
`Jul. 7, 2009
`
`Sheet 15 of 43
`
`US 7,558,420 B2
`
`FIG. 17
`
`Cl)
`UJ
`:::::>
`_J
`
`< > I
`
`N
`LL...
`0
`2:
`0
`1--
`:::::> co
`a:::
`1--
`Cl)
`
`0
`
`0
`
`255 Z-VALUE
`
`0
`
`Cl)
`UJ
`:::::>
`_J
`
`< > I
`
`N
`LL...
`0
`2:
`0
`1--
`
`:::::> co
`
`0:::
`1--
`
`Cl) -c
`
`0
`
`255 Z-VALUE
`
`

`
`U.S. Patent
`
`Jul. 7, 2009
`
`Sheet 16 of 43
`
`US 7,558,420 B2
`
`FIG. 18
`
`CALCULATE MAX Z, MIN Z,
`ANDAVE-Z
`-
`
`max_span.;-max_z-ave_z
`min_span~min_z-ave_z
`S503
`NO
`
`502
`
`max~31
`
`CLN~O
`pz _image.;-z _image
`
`----_.S,.--507 NO
`S508 -......L...-.....
`
`z~(z-ave_z)/
`max_span*(max-ave_z)
`
`z~(z-ave_z)/(ave_z­
`min_z)*min_span)
`
`

`
`U.S. Patent
`
`Jul. 7, 2009
`
`Sheet 17 of 43
`
`US 7,558,420 B2
`
`FIG. 19
`
`- - - - - - " ' - - - - - - - - - . 8516
`*adjust_z_imageE-*pz_image+z
`
`pz_imageE-pz_image+1
`adjust_ z _imageE-adjust_z _image+ 1
`CLNE-CLN+1
`
`S517
`
`FIG. 20
`
`081- .,.,...-
`
`GG
`
`I
`
`VL'
`
`PP5
`
`

`
`U.S. Patent
`
`Jul. 7, 2009
`
`Sheet 18 of 43
`
`US 7,558,420 B2
`
`FIG. 21
`
`START
`,,
`ADJUSTMENT OF STEP SIZE
`,,
`CALCULATION OF CONTOUR
`LINES
`,,
`DETERMINATION OF OBJECT'S
`CENTER
`
`u
`DETERMINATION OF
`INTERSECTIONS
`
`700 ~
`
`701 ~
`
`702 ~
`
`703 ~
`
`u
`s
`704
`I NPLANE Z -VALUE CALCULAT I ON ~
`
`705 ~
`
`706 ~
`
`lr
`INPLANE
`CALCULATION OF
`MODIFICATION Z-VALUE
`,,
`INPLANE
`CALCULATION OF
`MODIFICATION Z-VALUE
`,,
`END
`
`

`
`U.S. Patent
`
`Jul. 7, 2009
`
`Sheet 19 of 43
`
`US 7,558,420 B2
`
`FIG. 22
`
`max~255/MK
`Target_z~o
`
`CLN~O
`
`cwo~o
`P1~-1
`P2~-1
`fnd~o
`
`arget_z~ Target_z+1
`
`8721
`
`0 CLN~CLN+1
`
`~::;.....,
`
`P1~cwo
`
`P2+-CWD
`fnd+-fnd+1
`
`cwo~cwo+1
`
`8720
`
`

`
`U.S. Patent
`
`Jul. 7, 2009
`
`Sheet 20 of 43
`
`US 7,558,420 B2
`
`FIG. 23
`
`YES
`
`YES
`
`YES
`
`YES
`
`YES
`
`YES
`
`® ® CD
`P1
`® ® 0
`
`

`
`U.S. Patent
`
`Jul. 7, 2009
`
`Sheet 21 of 43
`
`US 7,558,420 B2
`
`FIG. 24
`
`9
`
`YES
`
`S737
`
`STORE FOUND COORDINATE IS
`cord->point->x
`and cord->point y
`
`IN
`
`END
`
`.---------~......-----..... S738
`cord->point+-cord->point+ 1
`
`-------~-------. S739
`cord->npoint+-cord->npoint+1
`
`-------~-------. S740
`FOUND PIXEL IS SET AS Pl
`
`8
`
`

`
`U.S. Patent
`
`FIG. 25
`
`Jul. 7, 2009
`
`Sheet 22 of 43
`
`US 7,558,420 B2
`
`SELECT CONTOUR LINE
`
`g_ min_ x+-999999
`g_max_x+-0
`g_min_y+-999999
`g_max_y+-0
`
`S752
`
`CNT+-0
`
`min x+-999999
`maxx+-0
`min_y+-999999
`max_y+-0
`
`p1.x+-PNT ->x
`p1.y+-PNT->y
`min_x+-p1.x
`
`p2.x+-PNT->x
`p2. y+-PNT ->y
`max_x-p2.x
`
`NO
`
`NO
`
`S759
`
`NO
`
`S761
`
`

`
`U.S. Patent
`
`Jul. 7, 2009
`
`Sheet 23 of 43
`
`US 7,558,420 B2
`
`FIG. 26
`
`10
`
`p3.x-E-PNT ->x
`p3.y-E-PNT->y
`~in_y-E-p3.y
`
`p4.x-E-PNT ->x
`p4.y-E-PNT->y
`max_y<E-p4. y
`
`CNT~CNT+1
`PNT~PNT+1
`
`12
`
`8762
`
`NO
`
`S764
`NO
`
`S765
`
`S766
`
`

`
`U.S. Patent
`
`Jul. 7, 2009
`
`Sheet 24 of 43
`
`US 7,558,420 B2
`
`FIG. 27
`
`STORE cordp IN cent_ cord
`
`g_min_x~p1.x
`
`CALCULATE xAND y
`COORDINATES OF
`INTERSECTIONS AND STORE IT
`
`STORE corp IN side_cord
`
`g_max_x~p2.x
`
`cordp~cordp+1
`
`8768
`
`8769
`
`8770
`
`8772
`
`8773
`
`8774
`
`

`
`U.S. Patent
`
`Jul. 7, 2009
`
`Sheet 25 of 43
`
`US 7,558,420 B2
`
`START
`
`SELECT CONTOUR LINE
`
`cordp~cord
`fnd~o
`
`FIG. 28
`
`8781
`
`S784
`
`PNT ~cordp->point
`CNT~O
`
`NO
`
`NO
`
`p[find].x~PNT.x
`p[find].y~PNT.y
`
`CNT~CNT+1
`PNT~PNT+1
`
`find~find+1
`
`p[find].x~-1
`p[find].y~-1
`
`cordp~cordp+1
`
`

`
`U.S. Patent
`
`Jul. 7, 2009
`
`Sheet 26 of 43
`
`US 7,558,420 B2
`
`FIG. 29
`
`START
`
`SELECT PLANE OF EQUIVALENT
`LEVEL
`
`CNT~O
`
`cent_h~HT -center. y
`object_h~dist/focus*cent_h
`
`8795
`
`S796
`
`S797
`
`NO
`
`S799
`
`NO
`
`New_ z[CNT]E-object_ h *focus/
`p[CNT]. y-center. y)-dist
`
`CNT~CNT+1
`
`END
`
`

`
`U.S. Patent
`
`Jul. 7, 2009
`
`Sheet 27 of 43
`
`US 7,558,420 B2
`
`FIG. 30
`
`SELECT INTERSECTION
`
`CNT+---1
`
`S809
`
`YES
`oz1 +---(p[CNT-1 ].x,
`p[CNT-1].y-1)
`
`sub1 +-oz2-oz1
`
`--su_b_2_+-_n-ew~.....-z_[C_N_T_]_--.. 8812
`new_z[CNT-1]
`
`S813
`NO
`
`S814
`
`S815
`
`adjust_ outline[CNT]+---0
`
`adjust_ outline[CNT]
`+-sub2-sub1
`
`CNT+-CNT+1
`
`S816
`
`

`
`U.S. Patent
`
`Jul. 7, 2009
`
`Sheet 28 of 43
`
`US 7,558,420 B2
`
`CLN-E---0
`
`FIG. 31
`
`8902
`NO
`
`8903
`
`NO
`
`S905
`
`OBTAIN adjust_z_image
`
`8906
`
`z_image-E-
`z _image+adjust_z_image
`,.--------1..----....... 8907
`CWD+-CWD+1
`
`8908
`
`

`
`U.S. Patent
`
`Jul. 7, 2009
`
`Sheet 29 of 43
`
`US 7,558,420 B2
`
`FIG. 32
`
`END
`
`81004
`,-J NO
`
`CALCULATE ZZ
`
`MOVE src TO THE TOP OF
`THE NEXT LINE
`
`81 006.-------"-----,
`CALCULATE PARALLAX SS
`
`NO
`
`STORE DATA OF
`PIXEL src+MV IN
`image3d
`
`image3d ~image3d+1
`outinfo~outinfo+ 1
`cwo~cwo+1
`
`

`
`U.S. Patent
`
`Jul. 7, 2009
`
`Sheet 30 of 43
`
`US 7,558,420 B2
`
`MK~256/0b
`
`zz~z_image/MK
`
`ZZ ~ (LOWER LIMIT)
`
`FIG. 33
`
`NO
`
`NO
`
`FIG. 34
`
`NO
`
`zz~2ss-zz
`
`- - - - - ' - - - - - - - . 81032
`SS+-ZZ+INTERFACE DEPTH
`
`

`
`U.S. Patent
`U.S. Patent
`
`Jul. 7, 2009
`Jul. 7, 2009
`
`34f013teehS
`Sheet 31 of 43
`
`US 7,558,420 B2
`US 7,558,420 B2
`
`FIG. 35
`
`

`
`U.S. Patent
`
`Jul. 7, 2009
`
`Sheet 32 of 43
`
`US 7,558,420 B2
`
`FIG. 36
`
`READ DATA OF A FRAME
`
`YES
`
`CONVERSION TO RGB
`
`GRAYSCALE VALUE ADJUSTMENT
`
`REVERSE DETERMINATION
`
`105
`
`SMOOTHING
`
`DISTRIBUTION ADJUSTMENT
`
`LOCAL ADJUSTMENT
`
`INPLANE Z-VALUE ADJUSTMENT
`
`ENHANCEMENT
`
`DISPLACEMENT OF PIXELS
`
`

`
`U.S. Patent
`
`Jul. 7, 2009
`
`Sheet 33 of 43
`
`US 7,558,420 B2
`
`FIG. 37
`
`S1120
`
`NO
`
`81131
`
`DRAW HALF LINE STARTING AT
`POINT
`(CWD, CLN)
`
`DETERMINE INTERSECTIONS OF 81125
`HALF LINE AND CONTOUR LINES
`
`NO
`
`pz_imageE(cid:173)
`z_image+cLN*WD+CWD
`
`*pz_imageE(cid:173)
`pz_iamge+offset_z
`
`CWDE-CDW+1
`
`

`
`U.S. Patent
`
`Jul. 7, 2009
`
`Sheet 34 of 43
`
`US 7,558,420 B2
`
`FIG. 38
`
`IMAGE DATA FOR THE
`LEFT EYE
`
`IMAGE DATA FOR THE
`RIGHT EYE
`
`READ EVEN(cid:173)
`NUMBERED LINES
`I
`-
`
`READ ODD-NUMBERED
`LINES
`
`..
`
`(FRAME BUFFER)
`
`FIG. 39
`
`IMAGE DATA FOR THE
`LEFT EYE
`
`IMAGE DATA FOR THE
`RIGHT EYE
`
`I
`READ DATA OF PIXELS OF
`EVEN-NUMBERED ROWS
`
`I
`READ DATA OF PIXELS OF
`ODD-NUMBERED ROWS
`
`(FRAME BUFFER)
`
`

`
`U.S. Patent
`
`Jul. 7, 2009
`
`Sheet 35 of 43
`
`US 7,558,420 B2
`
`FIG. 40
`
`IMAGE DATA FOR THE
`LEFT EYE
`
`IMAGE DATA FOR THE
`RIGHT EYE
`
`EVEN-NUMBERED FRAME ODD-NUMBERED FRAME
`BUFFER
`BUFFER
`
`FIG. 41
`
`IMAGE DATA FOR THE
`LEFT EYE
`
`IMAGE DATA FOR THE
`RIGHT EYE
`
`DATA FILE FOR
`STORING
`IMAGE DATA
`FOR THE LEFT EYE
`
`DATA FILE FOR
`STORING
`IMAGE DATA
`FOR THE RIGHT EYE
`
`

`
`U.S. Patent
`
`Jul. 7, 2009
`
`Sheet 36 of 43
`
`US 7,558,420 B2
`
`FIG. 42
`
`81051
`
`cwD~o
`
`CALCULATE ZZ
`
`81054
`
`NO
`
`81055
`
`81056
`
`81061
`
`MOVE src TO THE TOP OF
`THE NEXT LINE
`
`CALCULATE PARALLAX
`
`CLN~CLN+1
`
`MV1~CN+SS
`MV2~CN-SS
`
`S1057
`
`STORE PIXEL DATA OF
`src+MV1 IN Limage3d
`
`STORE PIXEL DATA OF 81059
`src+MV2 IN Rimage3d
`
`Limage3d~Li mage3d+ 1
`Rimage3d~Rimaged3d+1
`cwD~cwo+1
`
`81060
`
`

`
`U.S. Patent
`
`Jul. 7, 2009
`
`Sheet 37 of 43
`
`US 7,558,420 B2
`
`11
`
`12
`
`13
`
`14
`
`15
`
`FIG. 43
`
`CPU
`
`ROM
`
`RAM
`
`CHARACTER
`GENERATOR
`
`Tl ME CIRCUIT
`
`FIG. 44
`
`I
`
`I
`
`I
`
`28
`
`DISPLAY
`CONTROL UNIT
`
`21a
`22a
`--------- ---1
`I I
`I I I I
`
`DISPLAY
`
`25
`
`30
`
`OPERATION
`UNIT
`
`DK
`
`7 8 9
`* 0 #
`
`

`
`U.S. Patent
`
`Jul. 7, 2009
`
`Sheet 38 of 43
`
`US 7,558,420 B2
`
`FIG. 45
`
`211
`
`L1
`R1
`
`FIG. 46
`
`214
`
`LEFT EYE
`
`RIGHT EYE
`
`~~L2
`~ R2
`L3
`R3
`~:::::::~~~~ L4
`~~:===:s:Sj R4
`L5
`R5
`
`

`
`U.S. Patent
`
`Jul. 7, 2009
`
`Sheet 39 of 43
`
`US 7,558,420 B2
`
`FIG. 47
`
`,.......----.r------, 82000
`SELECT
`IMAGE
`
`ENABLE 2D MODE
`
`....----......1..-------, 82002
`OUTPUT 2D
`IMAGE DATA
`
`ENABLE 3D MODE
`L.....---.....,.----.182007
`
`GENERATE 3D
`
`IMAGE
`
`TERMINATE DISPLAYING
`
`_ __ _..__ __ ___, 82008
`OUTPUT 3D
`IMAGE
`
`NO
`
`NO
`
`TERMINATE DISPLAYING
`
`

`
`U.S. Patent
`
`Jul. 7, 2009
`
`Sheet 40 of 43
`
`US 7,558,420 B2
`
`FIG. 48
`
`RECEIVE MOVING
`
`IMAGE
`
`ENABLE 20 MODE
`
`OUTPUT A FRAME OF
`IMAGE DATA
`
`ENABLE 3D MODE
`
`IMAGE DATA
`TRANSFER
`OF A FRAME TO DATA
`BUFFER
`
`GENERATE 3D
`
`IMAGE
`
`OUTPUT 3D
`
`IMAGE
`
`NO
`
`NO
`
`

`
`INTERFACE
`
`(TO I NET)
`
`18
`y
`
`TRANSMISSION
`CONTROL UNIT
`
`MAGNET I C L--J-
`DISK DRIVE
`
`rl FIRST DATA F1 l 33
`_ _ _ -r
`
`BUFFER
`
`32
`
`1
`:
`...
`
`I
`I
`
`21b
`
`DISPLAY
`
`34
`.. -~-----,
`
`'PDl'
`
`-
`
`I
`
`:
`
`I
`I
`L--------1
`
`11
`
`12
`
`13
`
`14
`
`15
`
`CPU
`
`ROM
`
`- - -
`
`RAM
`
`CHARACTER
`GENERATOR
`
`TIME CIRCUIT ____
`
`I
`
`CD-ROM
`DRIVE
`
`I~
`
`DISPLAY
`CONTROL UNIT
`
`25
`
`SECOND DATA
`BUFFER
`
`FIG. 49
`
`~~ INPUT ~
`CONTROL UNIT
`
`I KEYBOARD ~3
`
`24
`
`INPUT
`CONTROL UNIT
`
`~
`00
`•
`~
`~
`~
`~
`
`=
`
`~
`
`2'
`:-
`~-....l
`N
`0
`0
`\0
`
`rFJ
`
`('D
`('D
`
`=-
`.....
`....
`0 .....
`
`.j;o.
`
`.j;o.
`(.H
`
`d
`rJl
`"'--...1 u.
`u.
`00
`~
`N
`
`= = N
`
`

`
`U.S. Patent
`
`Jul. 7, 2009
`
`Sheet 42 of 43
`
`US 7,558,420 B2
`
`FIG. 50
`
`83001
`
`RECEIVE MOVING
`
`IMAGE
`
`ENABLE 2D MODE
`
`IMAGE DATA OF A
`OUTPUT
`FRAME TO 1st DATA BUFFER
`
`ENABLE 3D MODE
`
`IMAGE DATA
`TRANSFER
`OF A FRAME TO DATA
`BUFFER
`
`GENERATE 3D
`
`IMAGE
`
`IMAGE DATA TO 1st
`OUTPUT 3D
`AND 2nd BUFFERS
`
`NO
`
`NO
`
`

`
`FIG. 51
`
`40
`
`~
`00
`•
`~
`~
`~
`
`~ = ~
`
`2' :-
`
`~-....l
`N
`0
`0
`\0
`
`41
`)
`
`OPERATIONS
`UNIT
`
`..
`....
`
`~
`SIMULATION
`PROCESSING
`UNIT
`
`~
`
`__....
`
`..
`
`FRAME BUFFER
`
`..
`...
`
`~~
`
`18
`S_
`STEREOGRAPHIC
`IMAGE
`GENERATING
`UNIT
`
`rFJ =(cid:173)
`.....
`
`('D
`('D
`
`.j;o.
`(.H
`
`0 .....
`
`.j;o.
`(.H
`
`d
`rJl
`-....l u. u.
`N = = N
`
`00
`~
`
`

`
`US 7,558,420 B2
`
`1
`METHOD AND APPARATUS FOR
`GENERATING A STEREOGRAPHIC IMAGE
`
`TECHNICAL FIELD
`
`The present invention relates to a method and apparatus for
`generating three-dimensional image data by means of two(cid:173)
`dimensional image data.
`
`BACKGROUND ART
`
`Humans are able to visually perceive three-dimensional
`objects in three-dimensional space. This ability is known as
`stereopsis. Stereopsis occurs when a human brain recognizes
`an object in three-dimensions on the basis of two images,
`received by the right and the left eyes, respectively. In other
`words, it is necessary for each of the right and the left eyes to
`receive an image for stereopsis to occur.
`A technique called stereography has been developed, in
`which image processing is performed on a two-dimensional
`image so that a viewer can perceive the processed two-dimen(cid:173)
`sional planar image as a three-dimensional image. Stereog(cid:173)
`raphy involves an image processing technique of revising
`image data of a single two-dimensional planar image to gen(cid:173)
`erate image data for each of the right and left eyes. Specifi(cid:173)
`cally, the image data for each of the right and left eyes is
`generated by calculating a binocular parallax with regard to
`an object (subject) depicted in an image and displacing,
`according to the parallax, positions of pixels (dots) of the
`image in right and left directions, respectively.
`For example, the parallax is determined by a value repre(cid:173)
`sentative of the degree of a famess (or nearness) of an object
`(hereinafter referred to as a Z-value), which is calculated on
`the basis of at least one of saturation, brightness, and hue of
`the object. For example, Japanese patent JP2002-123842A 35
`discloses a method for determining a Z-value on the basis of
`saturation and brightness of the original 2D image. Specifi(cid:173)
`cally, the method includes: (a) a step of determining Z-values
`for each pixel on the basis of saturation of the image data; (b)
`a step of determining a contour line(s) of the object(s) 40
`included in the image; (c) a step of calculating an average of
`the Z-values of all pixels within the object, and (d) a step of
`determining that the average is a Z-value of the object. A
`parallax with respect to the object is determined on the basis
`of the Z-value of the object.
`In addition, to improve perception of the generated 3D
`image, saturation of pixels near the object is changed so as to
`"blur" an edge of the object. It is to be noted that such a
`blurring process depends on an empirical rule, that is, the fact
`the farther away an object is located in an image, the fainter its 50
`image is (namely, the lower its saturation is), and the nearer
`the object is located, the sharper its image is (namely, the
`higher its saturation is). This is because edges of distant
`objects tend to be fine due to dust in the air and the like,
`blurring the object. Nearby objects increase in number and in 55
`saturation, and edges of the objects are thicker and thus look
`sharper.
`However, there are images that do not follow the above
`rule, such as an image in which a bright sky is depicted at a far
`distance and a dark-colored forest at a near distance. In such 60
`a case, the rule on which a Z-value is calculated does not
`represent a true depth of objects. As a result, it is not possible
`to reproduce a correct parallax with the generated stereo(cid:173)
`graphic image, and a viewer is thus given an unnatural
`impression.
`Further, in a case where a shadow or a highlight hangs over
`a certain portion of an object, in other words in a case where
`
`2
`a variation of saturation within the object is considerable, it is
`not possible to calculate a true Z-value of the object. As a
`result, a generated stereographic image gives a viewer an
`impression that only the overhanging portion is projected (or
`recessed) locally. In this case, since it is not possible to deter(cid:173)
`mine an edge of objects precisely, the blurring process cannot
`contribute to improvement of plasticity of the 3D image.
`Still further, in a highlighted portion of an object in which
`a Z-value becomes larger, a parallax of that portion is over-
`10 estimated accordingly. As a result, a phenomenon will occur
`in which adjacent pixels in an original2D image are displaced
`in opposite horizontal directions when generating a stereo(cid:173)
`graphic image. This phenomenon is called a pixel crossing,
`generating a distorted portion in the generated stereo graphic
`15 image. As a result, a quality of a generated stereographic
`image is reduced to such an extent that it cannot be appreci(cid:173)
`ated by a viewer. Occurrence of this phenomenon is espe(cid:173)
`cially serious at a position where a number of objects overlap.
`At such a position, distortion of the image can occur easily;
`20 thus it becomes significantly difficult to achieve natural per(cid:173)
`ception of a stereographic image for a viewer.
`As is described above, since it is not possible in the prior art
`to calculate a correct Z-value from an original image data to
`generate a stereographic image, generation of a realistic ste-
`25 reographic image is difficult.
`
`SUMMARY OF THE INVENTION
`
`The present invention has been made, taking into account
`30 the above background art, to provide a method for generating
`stereographic image data that gives a viewer an impression of
`natural plasticity, and an apparatus for generating stereo(cid:173)
`graphic image data adapted to the method. The present inven-
`tion is a result of the applicant's continuing studies on nec(cid:173)
`essary conditions for giving a human a strong impression of
`plasticity.
`A method for generating a stereo graphic image according
`to the present invention is characterized by comprising: a
`calculating step of calculating Z-values of pixels on the basis
`of image data of pixels, the pixels forming an image, each
`Z-value being assigned to a pixel, and each Z-value repre-
`senting a depth of an object corresponding to the pixel; an
`adjusting step of adjusting a Z-value of a target pixel obtained
`in the calculating step using a Z-value of a pixel other than the
`45 target pixel; and a generating step of determining an amount
`of displacement of a target pixel on the basis of an adjusted
`Z-value of the target pixel, and displacing the target pixel
`horizontally by the determined amount, to generate images
`for the right and the left eyes. By adjusting Z-values, a ste(cid:173)
`reographic image which provides a viewer with natural plas(cid:173)
`ticity is generated.
`In a preferred embodiment, in the calculating step the
`weights are determined based on the ratio of cone cells sen(cid:173)
`sitive of R, G, and B, respectively, which cones exist in a
`retina of a human eye.
`It is possible that in the adjustment step Z-values of pixels
`are adjusted so that a single step available for a Z-value of a
`pixel corresponding to an object located backward in an origi(cid:173)
`nal image express deeper depth than a single step available for
`a Z-value of a pixel corresponding to an object located for(cid:173)
`ward in the original image.
`It is possible that in the adjusting step an average of Z-val(cid:173)
`ues of pixels within an area which includes a target pixel is
`obtained and a Z-value of the target pixel is replaced by the
`65 obtained average.
`Further, it is possible that in the adjusting step a distribution
`of the Z-values of all pixels in the image and an average of all
`
`

`
`US 7,558,420 B2
`
`3
`pixels in the image are obtained and deviation of the distri(cid:173)
`bution is corrected using the obtained average.
`Still further, it is possible that in the adjusting step at least
`one object in the image represented by the image data is
`identified referring to Z-values of pixels calculated in the
`calculating step and a Z-value of the target pixel is adjusted on
`the basis of a Z-value of a pixel located within an area corre(cid:173)
`sponding to the identified object.
`Still further, it is possible that in the adjusting step any one
`of a step size of quantization of the Z-value, and an upper limit 10
`and a lower limit of the calculated Z-value is determined
`based on a value of a parameter specified by a user.
`Still further, it is possible that in said adjustment step
`tendency of Z-values of pixels in the image is analyzed by
`comparing a Z-value of a pixel within an area with a Z-value 15
`of a pixel within another area, and when a result of the
`analysis agrees with a predetermined condition, a quantitative
`relation between the amount of displacement of the target
`pixel and the Z-value of the target pixel is reversed in the
`generating step.
`In a preferred embodiment, it is possible that the stereo(cid:173)
`graphic image generating apparatus further comprises a step
`of obtaining moving images comprised of a plurality of
`images, and wherein a stereo graphic image is generated from
`each image, to generate stereo graphic images corresponding 25
`to the moving images in real time.
`A stereo graphic image generating apparatus for generating
`a stereographic image according to the present invention is
`characterized in comprising: a calculating means for calcu(cid:173)
`lating Z-values of pixels on the basis of image data of pixels, 30
`the pixels forming an image, each Z-value being assigned to
`a pixel, and each Z-value representing a depth of an object
`corresponding to the pixel; an adjusting means for adjusting a
`Z-value of a target pixel obtained in the calculating means
`using a Z-value of a pixel other than the target pixel; and a 35
`generating means for determining an amount of displacement
`of a target pixel on the basis of an adjusted Z-value of the
`target pixel, and displacing the target pixel horizontally by the
`determined amount, to generate images for the right and the
`left eyes. It is possible that the apparatus further comprises an 40
`obtaining means foro btaining from a user a parameter used in
`said adjusting means.
`The present invention also provides a computer program
`for functioning a computer as the stereographic image gen(cid:173)
`erating apparatus. It is possible that the program is stored in a 45
`various types of storage media and is download via a network,
`so as to be installed in the computer.
`
`4
`FIG. 8 is a schematic diagram illustrating a format of data
`of an image.
`FIG. 9 is a flowchart showing a grayscale value adjustment.
`FIG. 10 is a flowchart showing the grayscale value adjust(cid:173)
`ment (cont'd).
`FIG. 11 is a flowchart showing the grayscale adjustment
`(cont'd).
`FIG. 12 is a diagram illustrating sampling areas and corre(cid:173)
`sponding weight coefficients used in a reverse determination.
`FIG. 13 is a flowchart showing the reverse determination.
`FIG. 14 is a flowchart showing the reverse determination
`(cont'd).
`FIG. 15 is a diagram illustrating matrix areas MMs used in
`smoothing.
`FIG. 16 is a flowchart showing the smoothing.
`FIG. 17 is a conceptual diagram illustrating a distribution
`adjustment.
`FIG. 18 is a flowchart showing the distribution adjustment.
`FIG. 19 is also a flowchart showing the distribution adjust-
`20 ment (cont'd).
`FIG. 20 illustrates a distribution of Z-values with regard to
`an object adapted to a local adjustment.
`FIG. 21 is a flowchart showing the local adjustment.
`FIG. 22 is a flowchart showing a contour determination
`included in the local adjustment.
`FIG. 23 is a flowchart showing the contour determination
`(cont'd).
`FIG. 24 is a flowchart showing the contour determination
`(cont'd).
`FIG. 25 is a flowchart showing an object center determi(cid:173)
`nation included in the local adjustment.
`FIG. 26 is a flowchart showing the object center determi(cid:173)
`nation (cont'd).
`FIG. 27 is a flowchart showing the object center determi(cid:173)
`nation (cont'd).
`FIG. 28 is a flowchart showing an intersection determina(cid:173)
`tion included in the local adjustment.
`FIG. 29 is a flowchart showing an inplane Z-value calcu(cid:173)
`lation included in the local adjustment.
`FIG. 30 is a flowchart showing an inplane Z-value correc(cid:173)
`tion.
`FIG. 31 is a flowchart showing a Z-value adjustment.
`FIG. 32 is a flowchart showing a pixel displacement.
`FIG. 33 is a flowchart showing the pixel displacement
`(cont'd).
`FIG. 34 is a flowchart showing the pixel displacement
`(cont'd).
`FIG. 35 illustrates an enhancement according to a modified
`embodiment of the present invention.
`FIG. 36 is a flowchart showing an overview of image
`processing according to the modified embodiment.
`FIG. 37 is a flowchart showing an enhancement according
`to the modified embodiment.
`FIG. 38 is a conceptual diagram illustrating a scheme of
`55 displaying a stereographic image according to the modified
`embodiment.
`FIG. 39 is also a conceptual diagram illustrating a scheme
`of displaying a stereographic image according to the modified
`embodiment.
`FIG. 40 is also a conceptual diagram illustrating a scheme
`of displaying a stereographic image according to the modified
`embodiment.
`FIG. 41 is also a conceptual diagram illustrating a scheme
`of displaying a stereographic image according to the modified
`65 embodiment.
`FIG. 42 is a flowchart showing a pixel displacement
`according to the modified embodiment.
`
`50
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`FIG. 1 is a block diagram illustrating an example of a 3D
`image generation apparatus according to the first embodi(cid:173)
`ment of the present invention.
`FIG. 2 is a schematic diagram illustrating an example of a
`screen displayed by a 3D image drawing application.
`FIG. 3 is a schematic diagram illustrating an example of a
`configuration of a setting dialogue panel.
`FIG. 4 is a schematic diagram illustrating a mechanism of
`displaying a 3D image according to the first embodiment of 60
`the present invention
`FIG. 5 is also a schematic diagram illustrating a mecha(cid:173)
`nism of displaying a 3D image according to the first embodi(cid:173)
`ment of the present invention.
`FIG. 6 illustrates anaglyph glasses.
`FIG. 7 is a flowchart showing image processing performed
`when a 3D mode is selected.
`
`

`
`US 7,558,420 B2
`
`5
`FIG. 43 is a block diagram illustrating a functional con(cid:173)
`figuration of a Mobile terminallA of the second embodiment
`of the present invention.
`FIG. 44 is an external view of Mobile terminallA.
`FIG. 45 is a schematic diagram illustrating a configuration
`of a display 21b.
`FIG. 46 illustrates a principle of exciting stereopsis when
`an image is viewed by the naked eye.
`FIG. 47 is a flowchart showing a process for displaying a
`static image preformed by Mobile terminallA.
`FIG. 4S is a flowchart showing a process for displaying
`moving images preformed by Mobile terminallA.
`FIG. 49 is a block diagram illustrating an example of a
`functional configuration of a 3D image generating apparatus
`lB according to the third embodiment of the present inven(cid:173)
`tion.
`FIG. 50 is a flowchart showing a process for displaying
`moving images preformed by 3D image generating apparatus
`lB.
`FIG. 51 is a block diagram illustrating a functional con(cid:173)
`figuration of a train simulator 40 according to an application
`of the present invention.
`
`BEST MODE FOR CARRYING OUT THE
`INVENTION
`
`Detailed description of the preferred embodiments of the
`present invention will now be described with reference to the
`accompanying drawings.
`
`FIRST EMBODIMENT
`
`<A. Configuration of the Apparatus>
`FIG. 1 shows a 3D image generating apparatus 1 of the first
`embodiment of the present invention. In FIG.l, a CPU (cen(cid:173)
`tral processing unit) 11 controls all units of 3D image gen(cid:173)
`eration apparatus 1 to perform processing including genera(cid:173)
`tion of stereo graphic image data. A ROM (read only memory)
`12 is employed to store programs, one of which is executed
`when the apparatus is turned on, and related data. A RAM
`(random access memory) 13 is employed as a work area of
`CPU11.
`A Character generator 14 generates font data to be dis(cid:173)
`played on a display. A Time circuit 15 outputs a current t