United States Patent [191
`Hashima et al.
`
`1|||||m|||||mumlllllggwgyttylln|||||m|||||n||||||||
`
`[11] Patent Number:
`[45] Date of Patent:
`
`5,521,843
`May 28, 1996
`
`[54] SYSTEM FOR AND METHOD OF
`RECOGNIZING AND TRACKING TARGET
`MARK
`
`[75] Inventors: Masayoshi Hashima; Fumi Hasegawa;
`Keiju Okabayashi; Ichiro Watanabe;
`Shinji Kanda; Naoyuki Sawasaki;
`Yuichi Murase, all of Kawasaki, Japan
`
`[73] Assignee: Fujitsu Limited, Kawasaki, Japan
`[21] Appl. No.:
`119,228
`[22] PCT Filed:
`Jan. 29, 1993
`
`[86] PCT No.:
`PCT/JP93I00107
`§ 371 Date:
`Sep. 28, 1993
`§ 102(6) Date: Sep. 28, 1993
`[87] PCT Pub. No.: WO93/15376
`
`PCT Pub. Date: Aug. 5, 1993
`Foreign Application Priority Data
`
`[30]
`
`Jan. 30, 1992
`
`[JP]
`
`Japan .................................. .. 4-015557
`
`Jun. 26, 1992
`
`[JP]
`
`Japan . . . . . .
`
`Aug. 18, 1992
`
`[JP]
`
`Japan . . . . . .
`
`. . . .. 4-193457
`
`. . . .. 4-219029
`
`Oct. 29, 1992
`Nov. 17, 1992
`
`[JP]
`[JP]
`
`Japan . . . . . .
`. . . .. 4-291628
`Japan .................................. .. 4-307015
`
`[51] Int. Cl? .................................................... .. G01S 15/06
`[52] U.S. Cl. .................... .. 364/516; 340/815.54; 382/103
`[58] Field of Search ............................. .. 364/167.01, 559,
`364/516; 340/815.54, 815.57, 815.68; 382/10,
`14, 18, 25, 51, 65; 250/203 CT; 33/293;
`348/94
`
`[56]
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`5,008,804
`5,207,003
`
`4/1991 Gordon et al. ................... .. 364/167.01
`5/1993 Yamada et al. ......................... .. 33/293
`
`Japan .
`Japan .
`
`FOREIGN PATENT DOCUMENTS
`61-126406 6/1986
`62-54107
`3/ 1987
`62-54108
`3/1987
`62185106 8/1987
`62-185105
`8/1987
`63-75508 4/1988
`3-131710 6/1991
`4-119481
`4/1992
`
`Japan .
`Japan .
`Japan .
`Japan .
`Japan .
`Japan .
`
`Primary Examiner-—Emanuel T. Voeltz
`Assistant Examiner~Thomas Peeso
`Attorney, Agent, or Firm—Armstrong, Westerman, Hattori,
`McLeland & Naughton
`
`[57]
`
`ABSTRACT
`
`A system for and a method of recognizing and tracking a
`target mark with a video camera is disclosed. The system
`includes a target mark (10) disposed on an object (1) and
`composed of a black circle and a white triangle mounted
`centrally on the black circle and three-dimensionally shifted
`from the black circle, a video camera (20) for imaging the
`target mark (10), a robot (30) supporting the video camera
`(20) and movable in directions with six degrees of freedom,
`an image processor (40) for processing image data of the
`target mark which is produced by the video camera (20), a
`shift calculating unit (50) for detecting a shift of the target
`mark (10) from projected histogram information of the
`target mark (10) which is produced by the image processor
`(40), and a robot controller (60) for controlling movement of
`the robot depending on the shift to enable the video camera
`(20) to track the target mark (10). The system is capable of
`tracking the target mark (20) attached to the object (1) on a
`real-time basis. Mark recognizing apparatus capable of
`accurately recognizing target marks of other shapes is also
`disclosed.
`
`7/1981 Ueda et a1. ............................. .. 348/94
`4,281,342
`4,297,725 10/1981 Shimizu et a1. ................ .. 250/203 CT
`
`14 Claims, 47 Drawing Sheets
`
`I0
`
`20
`
`IH
`
`30
`
`__
`
`IMAGE
`PROCESSOR
`
`\fo
`
`ROBOT
`CONTROLLER
`
`m5”
`
`§3fFI7tw~AL
`CALCULATING
`umr
`
`Page 1 of 68
`
`SAMSUNG EXHIBIT 1006
`Samsung v. Image Processing Techs.
`
`

`

`US. Patent
`
`May 28, 1996
`
`Sheet 1 of 47
`
`5,521,843
`
`.Ptmm
`
`av
`
`mcmmmuomm
`
`mu 3:
`
`cm
`
`on
`
`5
`
`GE
`
`
`
`@22. <30 .36
`
`.22:
`
`qqzoiacm
`532229“ s got
`/s
`
`SAMSUNG EXHIBIT 1006
`Page 2 of 68
`
`

`

`US. Patent
`
`May 28, 1996
`
`Sheet 2 of 47
`
`5,521,843
`
`FIG.2
`
`'2
`
`f '"n
`
`ma
`
`PM
`
`'2
`
`FIG.4
`
`SAMSUNG EXHIBIT 1006
`Page 3 of 68
`
`

`

`US. Patent
`
`May
`28, 1996
`
`Sheet 3 0f 47
`
`5,521,843
`
`S!
`
`@ READ ORIGINAL IMAGE
`
`l
`32 _\-|CONVERT T0 BINARY IMAGE J
`I
`LABEL BINARY IMAGE
`
`S3
`
`84¢
`
`85
`
`SII
`
`N0
`
`SI2
`
`YES
`SEPARATE IMAGE 0F
`(\- GROUP NUMBER n
`
`MARK DETECTION
`FAILED
`
`AREA OF
`IMAGE 0F
`GROUP
`NUMBER n
`
`<
`
`<
`
`AREA
`
`DETERMINE X- AND Y-PRDJECTED HISTDGRAMS
`
`DE TE C T PEAKS
`
`SID
`
`IS NUMBER OF PEAKS IN X- AND
`Y-PROJE C TED HISTDGRAMS 2?
`
`PRESENT GROUP
`NUMBER n
`I
`5'4 \(MARK osrscnou SUCCESSFUL
`
`3
`
`FIG.5
`
`SAMSUNG EXHIBIT 1006
`Page 4 of 68
`
`

`

`US. Patent
`
`May 28, 1996
`
`Sheet 4 of 47
`
`5,521,843
`
`
`
`
`
`Y-PROJE C TED HIS TOGRAM
`
`X-PROJEC TED HISTOGRAM
`
`FIG.6
`
`SAMSUNG EXHIBIT 1006
`Page 5 of 68
`
`

`

`US. Patent '
`
`May 28,1996
`
`Sheet 5 of 47
`
`5,521,843
`
`FIG.7
`
`GROUP 3
`
`GROUP 2
`
`GROUP 4 l;
`
`moi/Pi
`
`GROUP 6'\®
`
`GROUP 7%)
`
`GROUP 8
`
`FIG.8
`
`SAMSUNG EXHIBIT 1006
`Page 6 of 68
`
`

`

`US. Patent
`
`May 28, 1996
`
`Sheet 6 of 47
`
`5,521,843
`
`FIG.9
`
`SAMSUNG EXHIBIT 1006
`Page 7 of 68
`
`

`

`US. Patent
`
`May-28, 1996
`
`Sheet 7 of 47
`
`5,521,843
`
`SAMSUNG EXHIBIT 1006
`Page 8 of 68
`
`

`

`US. Patent
`
`May 28, 1996
`
`Sheet 8 of 47
`
`5,521,843
`
`
`
`33322: P": umsmmi
`
`
`
`2352.2: cm: 056mm-»
`
`FIG.”
`
`X-PROJEC TED HISTOGRAM
`
`FIGJZ
`
`X-PROJEC TED HISTOGRAM
`
`SAMSUNG EXHIBIT 1006
`Page 9 of 68
`
`

`

`US. Patent
`
`May 28, 1996
`
`Sheet 9 of 47
`
`5,521,843
`
`M2.’ AUXILIARY ORIGIN MARK
`
`M4
`
`512 PIXELS
`
`4!
`_
`\J
`
`(22
`y e-(f
`X
`
`42
`
`i
`I _
`
`Y
`
`‘2.
`g
`
`l
`s
`In
`
`V
`
`SAMSUNG EXHIBIT 1006
`Page 10 of 68
`
`

`

`US. Patent
`
`May 28, 1996
`
`Sheet 10 of 47
`
`5,521,843
`
`Yb2
`
`FIG.I5
`
`42
`
`X
`
`512 PIXELS
`
`‘
`
`y M
`
`-
`
`10B
`
`22
`
`_
`
`<3
`\
`y e? 15
`X m E
`‘W
`CAMERA
`%
`'OA
`COORDINATE
`SYSTEM
`
`FIGJS
`
`if
`
`SAMSUNG EXHIBIT 1006
`Page 11 of 68
`
`

`

`US. Patent
`
`May 28, 1996
`
`Sheet 11 of 47
`
`5,521,843
`
`@267.‘
`
`2156C
`
`SAMSUNG EXHIBIT 1006
`Page 12 of 68
`
`

`

`US. Patent
`
`May 28, 1996
`
`Sheet 12 of 47
`
`5,521,843
`
`FIG.I8
`
`Xbl Xpl K KXpZ Xb2
`XPc
`Xbc
`
`SAMSUNG EXHIBIT 1006
`Page 13 of 68
`
`

`

`US. Patent
`
`May 28, 1996
`
`Sheet 13 0f 47
`
`5,521,843
`
`F 16.20
`
`FIG.22
`
`FIG.2I
`
`F 16.23
`
`SAMSUNG EXHIBIT 1006
`Page 14 of 68
`
`

`

`US. Patent
`
`May 28, 1996
`
`Sheet 14 of 47
`
`5,521,843
`
`120
`
`100
`
`
`
`120
`
`’30
`
`no
`
`_,
`
`FIG.24(AI
`
`FIG.24(B)
`
`/ I0!
`
`[2!
`
`I
`
`IA
`
`I8
`
`20
`
`g
`VIA
`
`,0,
`
`SAMSUNG EXHIBIT 1006
`
`Page 15 of 68
`
`F1626
`
`SAMSUNG EXHIBIT 1006
`Page 15 of 68
`
`

`

`US. Patent
`
`May 28', 1996
`
`Sheet 15 0f 47
`
`5,521,843
`
`( sTART
`
`)
`
`RECOGNIZE MARK
`._I
`"w
`SET wmoow
`
`\921
`
`\szz
`
`READ ORIGINAL IMAGE
`
`\sza
`
`CONVERT T0 BINARY IMAGE \sz“
`i
`DETERMINE x- AND Y-
`PROJECTED HISTOGRAMS
`*
`CONFIRM MARK
`
`\j25
`
`S26
`
`3”
`
`DOES
`MARK EXIST?
`
`$28
`as
`DETECT POSITIONAL SHIFT \
`
`GENERA TE SPEED c0MMAM0 VALUE \ 829
`
`s30
`i'
`OUTPUT SPEED coMMAMo VALUE '\
`
`DETERMINE wmnow POSITION
`AND SIZE FOR NEXT MEAsuREMEMT
`
`\S3I
`
`832
`
`OBJECT GEIPPED
`
`F1627
`
`SAMSUNG EXHIBIT 1006
`Page 16 of 68
`
`

`

`US. Patent
`
`May 28, 1996
`
`Sheet 16 0f 47
`
`5,521,843
`
`
`
`FIG 281A) y
`
`F I 6 28(8)
`
`SAMSUNG EXHIBIT 1006
`Page 17 of 68
`
`

`

`US. Patent
`
`May 28, 1996
`
`Sheet 17 of 47
`
`' 5,521,843
`
`Z
`[UNI T.‘ mm]
`
`0
`
`E2 IUNIT: PIXEL]
`
`FIG.3I
`
`SAMSUNG EXHIBIT 1006
`Page 18 of 68
`
`

`

`US. Patent
`
`May 28, 1996
`
`Sheet 18 of 47
`
`5,521,843
`
`Ex [UNI T: PIXEL]
`
`Dx lumr: mm]
`
`F1632
`
`Ax [UNI T.‘ PIXEL/mm]
`
`0
`
`ZIUN! T: mm]
`
`SAMSUNG EXHIBIT 1006
`Page 19 of 68
`
`

`

`US. Patent
`
`May 28, 1996
`
`Sheet 19 0f 47
`
`5,521,843
`
`DETERMINE DISTANCE DETwEEN MARK
`AND CAMERA FRDM AREA OF MARK: \ S4 ,
`z=f IE2)
`I
`‘DETERMINE SHIFT FROM GIVEN
`PDsITIDN IN 2 DIREcTIDN
`
`"\842
`
`I
`
`DETERMINE INCLINATIONS A IN X, Y, ROLL,
`PITCH, YAW DIRECTIONS:
`
`’\_S43
`
`I
`DETERMINE ACTUAL SHIFTS IN x, Y, ROLL,
`PITCH, YAW DIRECTIONS:
`
`\844
`
`SAMSUNG EXHIBIT 1006
`Page 20 of 68
`
`

`

`US. Patent
`
`May 28, 1996
`
`Sheet 20 of 47
`
`5,521,843
`
`
`
`z/mm]
`
`300
`
`200
`
`I00
`
`F I 6.36
`
`0 0
`
`[0000
`
`20000
`
`30000
`
`40000
`
`50000
`
`El [PIXEL]
`
`SAMSUNG EXHIBIT 1006
`
`Page 21 0f 68
`
`SAMSUNG EXHIBIT 1006
`Page 21 of 68
`
`

`

`US. Patent
`
`May 28, 1996
`
`Sheet 21 of 47
`
`5,521,843
`
`200
`
`Ey [PIXEL]
`
`100
`
`FIG.37 m
`
`-IOO
`
`F1638
`
`I00
`
`200
`
`I’mm’
`
`300
`
`SAMSUNG EXHIBIT 1006
`
`Page 22 0f 68
`
`SAMSUNG EXHIBIT 1006
`Page 22 of 68
`
`

`

`US. Patent
`
`May 28, 1996
`
`Sheet 22 of 47
`
`5,521,843
`
`START
`
`INPUT MARK IMAGE
`
`DETECT SHIFT 0N SCREEN
`
`CONVERT T0 SHIFT m
`
`ACTUAL comm TES
`
`85’
`
`$52
`
`853
`
`GENERA TE SPEED COMMAND VALUE
`
`IN NEW COORDINATE SYSTEM
`
`OUTPUT SPEED COMMAND VALUE
`
`854
`
`955
`
`
`
`OBJECT GRIPPED .7
`
`YES
`
`FIG.39
`
`S56
`
`SAMSUNG EXHIBIT 1006
`
`Page 23 0f 68
`
`SAMSUNG EXHIBIT 1006
`Page 23 of 68
`
`

`

`US. Patent
`
`May 28, 1996
`
`Sheet 23 of 47
`
`5,521,843
`
`V.
`
` EN
`
`2 L
`
`I.
`
`I...
`
`I
`9.
`
`0 “
`
`SAMSUNG EXHIBIT 1006
`
`Page 24 0f 68
`
`SAMSUNG EXHIBIT 1006
`Page 24 of 68
`
`

`

`US. Patent
`
`May 28, 1996
`
`Sheet 24 of 47
`
`5,521,843
`
`START
`
`
`
`$6 7
`
`OBJECT GRIPPED .7
`
`YES
`
`END
`
`FIG.4I
`
`SAMSUNG EXHIBIT 1006
`
`Page 25 0f 68
`
`INPUT MARK IMAGE
`
`DETECT SHIFT ON SCREEN
`
`CONVERT T0 SHIFT IN ACTUAL
`COORDINA TES
`
`CONVERT TO SHIFT IN CAMERA
`COORDINATE SYSTEM
`
`GENERA TE SPEED COMMAND VALUE
`IN CAMERA COORDINA TE SYSTEM
`
`OUTPUT SPEED COMMAND VALUE
`
`$6I
`
`3‘52
`
`$63
`
`554
`
`365
`
`566
`
`SAMSUNG EXHIBIT 1006
`Page 25 of 68
`
`

`

`US. Patent
`
`May “28, 1996
`
`Sheet 25 of 47
`
`5,521,843
`
`Wm
`
`V.w.
`m.
`
`SAMSUNG EXHIBIT 1006
`
`Page 26 0f 68
`
`SAMSUNG EXHIBIT 1006
`Page 26 of 68
`
`

`

`US. Patent
`
`May 28, 1996
`
`Sheet 26 of 47
`
`5,521,843
`
`M X
`
`cg
`
`FIG.45(A)
`
`-
`
`‘ X
`
`cg
`
`FIG.45(BI
`
`FIG.45(CI
`
`A
`
`SAMSUNG EXHIBIT 1006
`
`Page 27 0f 68
`
`SAMSUNG EXHIBIT 1006
`Page 27 of 68
`
`

`

`US. Patent
`
`May 28, 1996
`
`Sheet 27 of 47
`
`5,521,843
`
`FIG.47
`
`FIG.46
`
`
`
`SAMSUNG EXHIBIT 1006
`
`Page 28 0f 68
`
`SAMSUNG EXHIBIT 1006
`Page 28 of 68
`
`

`

`US. Patent
`
`May 28, 1996
`
`Sheet 28 of 47
`
`5,521,843
`
`
`
`
`
` ammNmmmmaaoE23EE8-N\§EE3EEmvdlgmvdlSEvdIGEde35deEmvdl
`
`qa<u<u
`
`01F1!.I”<qa<v.<
`
`EE23.x.3Ea:.5-.gEN\7mE
`
`35$:23:33.2}:36:$36:$55:A‘Ft,IJ.I
`a<<<<u<,.Maaa«a<9mmmmm‘mma
`
`
`
`
`
`
`
`SAMSUNG EXHIBIT 1006
`
`Page 29 0f 68
`
`SAMSUNG EXHIBIT 1006
`Page 29 of 68
`
`

`

`US. Patent
`
`May 28, 1996
`
`Sheet 29 of 47
`
`5,521,843
`
`
`
`
`
`EmvdtGE,deSEVGEGEVQI\vadl232‘.ka
`
`
`
`
`
`
`
`B:o?nu¢t:a:o¢-N\uMuaR:\v:u"fin:
`
`mma4mamm
`
`J1.J,,J9av.o<be.<<Hugh<<oamm
`
`SAMSUNG EXHIBIT 1006
`
`Page 30 0f 68
`
`SAMSUNG EXHIBIT 1006
`Page 30 of 68
`
`

`

`US. Patent
`
`May 28, 1996
`
`Sheet 30 of 47
`
`5,521,843
`
`
`
`35de$3de2.5deEmle$5leG$vdl
`
`\i8.8~3Eumag.uEEBa«x:"aa:
`
`uq
`
`maamamammm
`
`mmu<u<o<
`
`
`
`
`
`1.fl4«u<<I!la.—II.
`
`SAMSUNG EXHIBIT 1006
`
`Page 31 0f 68
`
`SAMSUNG EXHIBIT 1006
`Page 31 of 68
`
`

`

`U
`
`tnem.
`
`69m8,2yaM
`
`74f013mhS
`
`3489125,5
`
`S..7I
`
`3:333:xm3:63.40
`
`
`
`Rama:«mm
`
`\Samt‘mmfio
`
`2&9:<1
`
`E.$2.”:35:33:
`
`
`
`S<<zot‘momIsuzmd
`
`
`
`mimic:5mm
`
`
`
`x5;<muioéEzmu
`
`22..Rom
`
`859$:
`
`«Sandi
`
`SAMSUNG EXHIBIT 1006
`
`Page 32 0f 68
`
`SAMSUNG EXHIBIT 1006
`Page 32 of 68
`
`

`

`US. Patent
`
`May 28, 1996
`
`Sheet 32 of 47
`
`5,521,843
`
`3%
`
`>~B3m33562m5
`
`3358.2:
`
`EE§28
`
`$3.23E325::
`
`3::Etta
`
`$223.3
`
`$3338
`
`$33399
`
`
`
`$3338$3338
`
`$3338
`
`vow
`
`mam
`
`NonSm.
`
`
`
`35:53.2:+$3.33$2.232Pfizgzg
`
`
`
`+mzfikmm30%;*92$on
`
`PB
`
`9335:
`
`xzo3m3
`
`$522:ozszsm
`
`use:
`
`no»
`
`$3338_
`
`_
`
`_._
`
`ezqaas__M
`$336:
`
`SAMSUNG EXHIBIT 1006
`
`Page 33 0f 68
`
`_____
`
`x~83m3
`
`m35:
`
`»~83m3
`
`m3SE
`
`x«93.3
`
`m33:
`
`SE33
`
`3336C
`
`SAMSUNG EXHIBIT 1006
`Page 33 of 68
`
`
`
`
`
`
`
`

`

`US. Patent
`
`May 28, 1996
`
`Sheet 33 of 47
`
`5,521,843
`
`
`
`FIG.52 '
`
`SAMSUNG EXHIBIT 1006
`
`Page 34 0f 68
`
`SAMSUNG EXHIBIT 1006
`Page 34 of 68
`
`

`

`US. Patent
`
`May 28, 1996
`
`Sheet 34 of 47
`
`5,521,843
`
`2m.
`
`2:3:56wait;@«23%:mBe;
`
`Inmom.
`
`V
`
`
`
`
`2m$322::82;$522:qu.3:§8».
`
`$832:$5.533«2qua”
`
`5‘2:zem‘mc‘n‘SQU
`
`.22:
`
`Algemaa
`
`<\a
`
`
`
`
`
`Eas33522:«:5action:25;figSP3moZm
`
`.36:
`
`SAMSUNG EXHIBIT 1006
`
`Page 35 0f 68
`
`SAMSUNG EXHIBIT 1006
`Page 35 of 68
`
`
`

`

`US. Patent
`
`May 28, 1996
`
`Sheet 35 of 47
`
`5,521,843
`
`m2.5
`
`.mqu
`
`
`
`
`
`8.3.5.;#358
`
`59:8
`
`:2Eszg
`2:36:
`
`.325;E.3398
`vadl
`
`hissEv6Q5,
`Evndl
`
`.353.an;
`
`\Svndt
`
`x8.5soc
`
`Bind:
`
`Qvndi
`
`
`
`wENEomtuzxmqfichEot
`
`.3sz
`
`322%
`
`uSNEQtIQEm#253:—
`
`EFndE
`
`SAMSUNG EXHIBIT 1006
`
`Page 36 0f 68
`
`SAMSUNG EXHIBIT 1006
`Page 36 of 68
`
`

`

`US. Patent
`
`May 28, 1996
`
`Sheet 36 of 47
`
`5,521,843
`
`FIG.55
`
`MAINMEMORY
`
`PROCESSOR
`
`I
`
`
`
`
`IMAGEMEMORY
`
` INTERFACE
`CAMERA
`
`SAMSUNG EXHIBIT 1006
`
`Page 37 0f 68
`
`SAMSUNG EXHIBIT 1006
`Page 37 of 68
`
`

`

`US. Patent
`
`May 28, 1996
`
`Sheet 37 of 47
`
`5,521,843
`
`FIG.56
`
`SAMSUNG EXHIBIT 1006
`
`Page 38 0f 68
`
`SAMSUNG EXHIBIT 1006
`Page 38 of 68
`
`

`

`US. Patent
`
`May 28, 1996
`
`Sheet 38 of 47
`
`5,521,843
`
`0
`
`f
`
`1 F
`
`IG.58
`
`SAMSUNG EXHIBIT 1006
`
`Page 39 0f 68
`
`SAMSUNG EXHIBIT 1006
`Page 39 of 68
`
`

`

`US. Patent
`
`May 28, 1996
`
`Sheet 39 of 47
`
`5,521,843
`
`
`
`FIG.60
`
`SAMSUNG EXHIBIT 1006
`
`Page 40 0f 68
`
`SAMSUNG EXHIBIT 1006
`Page 40 of 68
`
`

`

`US. Patent
`
`May 28, 1996
`
`Sheet 40 of 47
`
`5,521,843
`
`FIG.61
`
` FIG.62
`
`233
`
`SAMSUNG EXHIBIT 1006
`
`Page 41 0f 68
`
`SAMSUNG EXHIBIT 1006
`Page 41 of 68
`
`

`

`US. Patent
`
`May 28, 1996
`
`Sheet 41 of 47
`
`5,521,843
`
`0
`
`INPUT IMAGE
`
`37’
`
`BAND-CONVERT T0
`BINARY IMAGE
`
`372
`
`LABEL BINARY IMAGE AND LABEL
`
`HISTOGRAM
`
`S73
`
`SELECT MARK
`
`S74
`
`PRODUCE x- AND Y-
`PROJECTED HISTOGRAMS
`
`575
`
`
`
`
`
`CALCULATE x AND Y ADDRESSES (WEIGHTED
`MEANS OF X- AND Y- PROJECTED
`
`HISTOGRAMS}
`
`
`
`376
`
`
`
` FOUR
`POINTS
`EX TRAC TED ?
`
`
`
`
`
`YES
`
`CALCULATE DISTANCE
`AND ATTITUDE
`
`378
`
`O
`
`FIG.63
`
`SAMSUNG EXHIBIT 1006
`
`Page 42 0f 68
`
`SAMSUNG EXHIBIT 1006
`Page 42 of 68
`
`

`

`US. Patent
`
`May 28, 1996
`
`Sheet 42 of 47
`
`5,521,843
`
`FIG.64(A)
`
`230
`
`233
`
`234
`
`FIG.64(BI
`
`
`
`SAMSUNG EXHIBIT 1006
`
`Page 43 0f 68
`
`SAMSUNG EXHIBIT 1006
`Page 43 of 68
`
`

`

`US. Patent
`
`May 28, 1996
`
`Sheet 43 of 47
`
`5,521,843
`
`247
`
`FIG.68(B)
`
`FIG.68(A)
`
`FIG.66(AI
`
`244
`
`243
`
`/\240
`
`246
`
`246
`
`FIG.66(B)
`
`SAMSUNG EXHIBIT 1006
`
`Page 44 0f 68
`
`SAMSUNG EXHIBIT 1006
`Page 44 of 68
`
`

`

`US. Patent
`
`May 28, 1996
`
`Sheet 44 of 47
`
`5,521,843
`
`$87
`
`388
`
`$89
`
`EXTRACT TWO PEAKS 0F X-
`
`AND Y- PROJECTED HISTOGRAMS
`
`SET MASK AROUND SMALL CIRCLE
`
`
`
`CALCULATE DISTRIBUTED
`
`
`WEIGHTS B 0F X- AND Y-
`
`PROJECTED HISTOGRAMS
`0F REVERSED SMALL CIRCLE
`
`
`
`38 I
`
`532
`
`$83
`
`384
`
`INPUT IMAGE
`
`
`BAND-CONVERT T0
`BINARY IMAGE
`
`LABEL BINARY IMAGE
`
`SELECT MARK
`
`
`
`
`
`
`CALCULATE WEIGHT MEAN
`OF SMALL CIRCLE
`
`USING A + B
`PRODUCE X— AND Y-
`
`PROJECTED HISTOGRAMS
`CALCULATE WEIGHT MEAN
`
`986
`or SMALL CIRCLE
`
`
`
`CALCULATED DISTRIBUTED
`WEIGHTS A or x. AND Y-
`
`890
`
`89/
`
`592
`
`
`
`$93
`
`usma B
`
`
`Two
`
`PROJECTED HISTOGRAMS
`
`
`
`
`
`
`CIRCLES EXTRACTED
`.7
`
`YES
`
`CALCULATE WEIGHT AND
`A TTI TUDE
`
`FIG.67.
`
`SAMSUNG EXHIBIT 1006
`
`Page 45 0f 68
`
`SAMSUNG EXHIBIT 1006
`Page 45 of 68
`
`

`

`US. Patent
`
`May 28, 1996
`
`Sheet 45 of 47
`
`5,521,843
`
`F1669
`
`265
`
`266
`
`263 '
`
`26!
`
`V
`
`262
`
`SAMSUNG EXHIBIT 1006
`
`Page 46 0f 68
`
`SAMSUNG EXHIBIT 1006
`Page 46 of 68
`
`

`

`US. Patent
`
`May 28, 1996
`
`Sheet 46'of 47
`
`5,521,843
`
`INPUT IMAGE
`
`3"”
`
`BAND-CONVERT T0
`BINARY IMAGE
`
`3’02
`
`LABEL BINARY IMAGE
`
`3103
`
`SELECT TWO MARKS WITH IST AND
`2ND LARGEST NUMBERS 0F PIXELS
`
`$104
`
`APPLY THREE-DIMENSIONAL MARK
`
`DE TEC TING PROCESS
`
`SIOS
`
`SIOC
`
`
`
`NO
`
`SELECT FOUR MARKS
`
`APPL Y FOUR-C IRCLE
`
`DETECTING PROCESS
`
`SI09
`
`CALCULATE DISTANCE AND ATTITUDE
`
`FIG.7O
`
`SAMSUNG EXHIBIT 1006
`
`Page 47 0f 68
`
`SAMSUNG EXHIBIT 1006
`Page 47 of 68
`
`

`

`US. Patent
`
`May 28, 1996
`
`Sheet 47 of 47
`
`5,521,843
`
`«KN
`
`SNLQ‘CX
`
` SNSSS
`
`[III
`III
`
`III”
`
`I
`
`I.
`IllI
`
`'
`
`SNQEB
`
`mN
`
`8.2.25
`
`Swag:
`
`8N???
`
`Rat
`
`SAMSUNG EXHIBIT 1006
`
`Page 48 0f 68
`
`SAMSUNG EXHIBIT 1006
`Page 48 of 68
`
`
`
`

`

`1
`SYSTEM FOR AND METHOD OF
`RECOGNIZING AND TRACKING TARGET
`MARK
`
`TECHNICAL FIELD
`
`The present invention relates to a system for and a method
`of recognizing and tracking a target mark using a video
`camera, and more particularly to a system for and a method
`of recognizing and tracking a target mark for detecting the
`position and attitude of the target mark by processing an
`image of the target mark produced by a video camera,
`detecting a shift of the position of the target mark from a
`predetermined position, and controlling the position and
`attitude of a processing mechanism based on the detected
`shift.
`
`BACKGROUND ART
`
`To have a robot grip a moving object by itself or clock a
`spacecraft with another spacecraft, it is necessary to recog-
`nize and track a target mark on the moving object or the
`spacecraft using a video camera.
`There has heretofore been known a process of measuring
`the position and attitude of an object by producing an image
`of a target mark on the object with a video camera, and
`processing the data of the produced image to determine the
`position and attitude of the object. The process may be used
`in an application for gripping the object with a robot hand.
`In such an application, the video camera is mounted on a
`robot, which tracks the target mark based on position and
`attitude data of the target mark which are produced by the
`video camera, for gripping the object with the robot hand.
`The conventional process takes its time until the position
`and attitude of the object are recognized by processing the
`image data of the target mark. It has been impossible for the
`prior process to effect a real-time data feedback to the robot
`and also diflicult to track the object.
`Another process which effects pattern matching on
`images to track an object is time-consuming as it requires
`lots of calculations in a two-dimensional space.
`According to still another process of tracking an object,
`movement of the object is grasped, and the position of the
`moving object is predicted. This process cannot simply be
`applied to movement of an ordinary object because the
`process is based on the fact that the object makes regular
`movements.
`
`Before a target mark is recognized, it is necessary to
`extract a desired mark from an image which either contains
`another object or objects or has a lot of noises. To meet such
`a requirement, the conventional processes compare the area
`of the mark or extracts features by way of pattern matching.
`The area comparison procedure determines as a desired
`mark an extracted image having substantially the same area
`as the desired mark. It is virtually impossible, however, to
`extract a desired mark from an image which either contains
`an object of almost the same size around the mark or has a
`lot of noises. The area comparison procedure thus finds use
`in a limited range of applications.
`The feature extraction procedure based on pattern match-
`ing needs a large expenditure of time for searching an image
`memory, and hence it processing time is long.
`To measure the position and attitude of an object in a
`three-dimensional space, there is employed a triangular or
`rectangular target mark representing the positional relation-
`ship between three or four points. If such a target mark is
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`4O
`
`45
`
`50
`
`55
`
`60
`
`65
`
`5,521,843
`
`2
`
`attached to a certain plane of an object, then the position and
`attitude of the object can be measured from the positional
`relationship of the image of the target mark in an image
`space. In the measurement, calculations based on projective
`geometry are effected on the coordinates of image points that
`are projected from the object space of the target mark onto
`the image plane of a camera. When the position or attitude
`of the object changes, the relationship between image points
`on the target mark also changes. Therefore, it is possible to
`calculate the position and attitude of the object in the
`three-dimensional space based on the change in the rela-
`tionship between image points on the target mark.
`Since a conventional measuring system using target
`marks calculates the position and attitude of an object based
`on the coordinates of image points that are extracted from a
`triangular or rectangular target mark image, the measuring
`accuracy tends to vary depending on the attitude of the target
`mark with respect to the camera. Specifically, when image
`data containing a directional component is obtained from
`each image point on an image plane to describe a certain
`plane of the object to which a target mark is attached, a
`reference distance with respect to each image point varies,
`resulting in a lack of stability with respect to the measuring
`accuracy for the position and attitude.
`Conventional calculations of a position using a target
`mark require that the plane of the target mark be at a certain
`angle to the plane of an image, and hence need much more
`calculation parameters than if the camera faces the target
`mark head on. Therefore, the calculations in measuring the
`position are complex, and the measuring accuracy is low—
`ered.
`
`When a mark in the form of four points is converted into
`an image by an imaging means, the four points are shown as
`having a certain area on the image, making it impossible to
`accurately determine the positions of the points in the image
`data. Accordingly, the positions of the points on the image
`cannot be determined in terms of subpixels. Since the
`distance up to the object and the attitude of the object are
`calculated based on the inaccurate positions of the points in
`the image data, the distance up to the object and the attitude
`of the object cannot be measured with accuracy.
`
`DISCLOSURE OF THE INVENTION
`
`In view of the above problems of the conventional sys-
`tems and processes, it is a first object of the present invention
`to provide a system for and a method of recognizing and
`tracking a target mark on a real-time basis using a video
`camera.
`
`A second object of the present invention is to provide a
`system for and a method of recognizing and tracking a target
`mark so as to be capable of extracting a desired target mark
`quickly and reliably.
`A third object of the present invention is to provide a
`system for and a method of recognizing and tracking a target
`mark while eliminating measuring error variations due to the
`positional relationship between the target mark and a cam-
`era.
`
`A fourth object of the present invention is to provide a
`system for and a method of recognizing and tracking a target
`mark to measure the distance up to and the attitude of an
`object simply with high accuracy.
`To achieve the above objects, there is provided in accor—
`dance with the present invention a target mark tracking
`system for tracking a target mark with a video camera,
`comprising a target mark disposed on an object and com-
`
`SAMSUNG EXHIBIT 1006
`
`Page 49 of 68
`
`SAMSUNG EXHIBIT 1006
`Page 49 of 68
`
`

`

`3
`
`4
`
`5,521,843
`
`posed of a black circle and a white triangle mounted
`centrally on the black circle and three-dimensionally shifted
`from the black circle, a video camera for imaging the target
`mark, a moving mechanism supporting the video camera
`and movable in directions with six degrees of freedom,
`image processing means for processing image data of the
`target mark which is produced by the video camera, shift
`detecting means for detecting a shift of the target mark from
`projected histogram information of the target mark which is
`produced by the image processing means, and moving
`mechanism control means for controlling movement of the
`moving mechanism depending on the shift to enable the
`video camera to track the target mark.
`The target mark is composed of the black circle and the
`White triangle mounted centrally on the black circle and
`three-dimensionally shifted from the black circle, and is
`mounted on the object. The video camera is mounted on the
`moving mechanism which is movable in the directions with
`six degrees of freedom and images the target mark. The
`image processing means processes the image data of the
`target mark which is produced by the video camera. The
`shift detecting means detects a shift of the target mark from
`projected histogram information thereof. The moving
`mechanism control means controls movement of the moving
`mechanism depending on the shift
`to enable the video
`camera to track the target mark.
`As described above, the target mark composed of the
`three-dimensionally shifted white triangle disposed centrally
`on the black circle is imaged by the video camera, and a shift
`in each of the coordinate axis directions of the target mark
`is determined from the image data. The shifts can be
`determined from projected histograms of the image data,
`which are calculated in a one-dimensional domain. There»
`
`fore, the calculations of the projected histograms are very
`simple and small in amount. Therefore, the shifts of the
`target mark can be determined by a high-speed processing.
`As a consequence, real—time data can be fed back to the
`moving mechanism depending on the determined shifts,
`making it possible to enable the video camera to track the
`target mark on a real-time basis.
`According to the present invention, there is also provided
`a visual target mark tracking control system for imaging a
`target mark with a video camera and processing image data
`of the target mark produced by the video camera to hold the
`video camera in a predetermined positional relationship to
`the target mark at all
`times, comprising image change
`detecting means for detecting a change from a target position
`and attitude for the target mark in an image of the target
`mark produced by the video camera, actual change detecting
`means for detecting a relative actual change from the pre-
`determined positional relationship between the video carn—
`era and the target mark, and relating means for experimen-
`tally shifting the predetermined positional
`relationship
`between the video camera and the target mark, and relating
`values which are detected by the image change detecting
`means and the actual change detecting means when the
`predetermined positional
`relationship is experimentally
`shifted, to each other.
`
`The relating means experimentally shifts the predeter-
`mined positional relationship between the video camera and
`the target mark, and relates a value which is detected by the
`image change detecting means, i.e., a change from a target
`position and attitude for the target mark on its image, and a
`value which is detected by the actual change detecting
`means, i.e., a relative actual change from the predetermined
`relationship between the video camera and the target mark,
`to each other.
`
`10
`
`15
`
`20
`
`25
`
`3O
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`By thus relating the changes, the change in the image of
`the target mark can quickly be converted into the relative
`actual change from the predetermined relationship between
`the video camera and the target mark. Thus, even when the
`distance between the target mark and the Video camera is
`greatly varied,
`the moving object can stably be tracked
`without a reduction in the response.
`According to the present invention, there is also provided
`a target mark attitude detecting method of detecting the
`attitude of a target mark to detect the attitude of an object
`about the direction of a camera based on an image produced
`by the camera of a target mark which is composed of at least
`a triangle of a particular shape, comprising the steps of
`determining projected histograms in X and Y directions of
`the image of the triangle of the target mark, determining the
`positions of the centers of gravity in the X and Y directions
`of the image of the triangle of the target mark in the
`projected histograms, determining maximum histogram val-
`ues and X- and Y—axis values in the projected histograms,
`determining which of classified and preset attitude patterns
`the attitude of the triangle of the target mark belongs to
`based on the positions of the centers of gravity, the maxi-
`mum histogram values, the X- and Y-axis values, and known
`geometrical data of the target mark, and calculating the
`attitude of the triangle of the target mark in the determined
`attitude pattern about the direction of the camera.
`Attitudes for the triangle of the target mark are classified
`into attitude patterns. Then, it is determined which of the
`classified and preset attitude patterns the attitude of the
`triangle of the target mark belongs to based on the positions
`of the centers of gravity, the maximum histogram values, the
`X— and Y—axis values, and known geometrical data of the
`target mark. The attitude of the triangle of the target mark in
`the determined attitude pattern about the direction of the
`camera is then calculated. The rolling interval of the target
`mark can properly and simply be grasped.
`According to the present invention, there is further pro-
`vided a method of detecting a target mark, comprising the
`steps of converting an original image to binary images,
`grouping the binary images into images with joined pixels,
`determining X— and Y—projected histograms of the grouped
`images, counting extreme values of the X- and Y-projected
`histograms of the grouped images, and comparing the
`counted extreme values with predetermined extreme values
`of X- and Y-histograms of a target mark to determine
`whether the grouped images represent the target mark.
`According to the present invention, there is also provided
`an apparatus for measuring the position and attitude of an
`object based on an image of a target mark, comprising a
`target mark disposed on a particular flat surface of an object
`and composed of a circle and a central point thereof, a
`camera for imaging the target mark to generate an image of
`the circle and the central point thereof, feature extracting
`means for extracting feature points required to measure the
`position and attitude of the object, from the image of the
`target mark, and calculating means for calculating the posi-
`tion and attitude of the target mark in an object space
`according to projective geometrical calculations on the
`feature points.
`According to the present invention, there is also provided
`a distance and attitude measuring apparatus for measuring
`the distance up to and the attitude of an object, comprising
`four disk-shaped marks disposed on an object and having
`respective centers of gravity positioned in one plane, at least
`one of the disk-shaped marks having a radius different from
`the radii of the other disk-shaped marks, imaging means for
`
`SAMSUNG EXHIBIT 1006
`
`Page 50 of 68
`
`SAMSUNG EXHIBIT 1006
`Page 50 of 68
`
`

`

`5
`
`6
`
`5,521,843
`
`imaging the disk-shaped marks, center-of-gravity calculat-
`ing means for calculating the positions of the centers of
`gravity of the respective disk-shaped marks based on image
`data of the four disk—shaped marks which are outputted by
`the imaging means, and calculating means for solving a
`four-point perspective problem to calculate the distance up
`to and the attitude of the object based on the positions of the
`centers of gravity calculated by the center-of—gravity calcu-
`lating means.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`FIG. 1 is a view showing an overall arrangement of a
`target mark tracking system;
`FIG. 2 is a perspective view of a target mark;
`FIG. 3 is a plan view of the target mark;
`FIG. 4 is a side elevational view of the target mark;
`FIG. 5 is a flowchart of a sequence for detecting the target
`mark;
`
`FIG. 6 is a diagram showing X- and Y-histograms of the
`target mark;
`FIG. 7 is a diagram showing a binary image converted
`from a projected image;
`FIG. 8 is a diagram illustrative of the labeling of the
`binary image;
`FIG. 9 is a diagram showing an example in which an
`object having a group number 3 is separated;
`FIG. 10 is a diagram showing X- and Y-projected histo~
`grams of the separated object having a group number 3;
`FIG. 11 is a diagram showing a target mark of other form
`and its X- and Y—projected histograms;
`FIG. 12 is a diagram showing a target mark of still other
`form and its X- and Y—projected histograms;
`FIG. 13 is a diagram showing a four-circle target mark for
`measuring a position and attitude;
`FIG. 14 is a diagram illustrative of the manner in which
`shifts in X- and Y-directions of a target mark are determined;
`FIG. 15 is a diagram illustrative of the manner in which
`the central position Pm of the target mark is determined;
`FIG. 16 is a diagram illustrative of the manner in which
`a shift in a Z direction of the target mark is determined;
`FIG. 17(A) is a perspective view of the target mark,
`showing thevattitude of a camera;
`FIG. 17(B) is a view showing a target mark image;
`FIG. 18 is a diagram showing X- and Y—projected histo-
`grams of the target mark image;
`FIG. 19 is a diagram illustrating the manner in which a
`shift in a yaw direction is determined;
`FIG. 20 is a diagram illustrating the manner in which a
`shift in a pitch direction is determined;
`FIG. 21 is a diagram showing the target mark image as it
`is rotated in a roll direction and its X-projected histogram;
`FIG. 22 is a diagram illustrating the manner in which a
`shift in the yaw direction is determined;
`FIG. 23 is a diagram showing the manner in which a
`window is established;
`
`FIGS. 24(A) and 24(B) are views of another target mark;
`FIG. 25 is a view of still another target mark;
`FIG. 26 is a view showing an example in which the target
`mark shown in FIG. 25 is used;
`FIG. 27 is a flowchart of a sequence of detection of a
`positional shift and gripping an object;
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`FIGS. 28(A) and 28(B) are diagrams showing the posi-
`tional relationship between a video camera and a target
`mark;
`FIGS. 29(A) and 29(B) are views showing movement of
`the video camera when a shift is actually measured;
`FIG. 30 is a diagram