`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
`
`
`
`U.S. Patent
`
`May 28, 1996
`
`Sheet 14 of 47
`
`5,521,843
`
`
`
`I20
`
`I30
`
`V
`
`no
`
`_,
`
`FIG.24(AI
`
`FIG.24(B)
`
`FlG.25
`
`I0!
`
`I21 /
`
`I
`
`20
`
`§
`VIA
`
`SAMSUNG EXHIBIT 1006
`
`Page 15 of 68
`
`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
`
`
`
`U.S. Patent
`
`May 28, 1996
`
`Sheet 20 of 47
`
`5,521,843
`
`1/mm]
`
`300
`
`200
`
`I00
`
`F I (5.36
`
`0 0
`
`[0000
`
`20000
`
`30000
`
`40000
`
`50000
`
`El [PIXEL]
`
`SAMSUNG EXHIBIT 1006
`
`Page 21 of 68
`
`SAMSUNG EXHIBIT 1006
`Page 21 of 68
`
`
`
`U.S. Patent
`
`May 28, 1996
`
`Sheet 21 of 47
`
`5,521,843
`
`Ey [PIXEL]
`
`200
`
`I 00
`
`-I00
`
`FIG.37 W
`
`FIG.38
`
`I00
`
`200
`
`W’
`
`300
`
`SAMSUNG EXHIBIT 1006
`
`Page 22 of 68
`
`SAMSUNG EXHIBIT 1006
`Page 22 of 68
`
`
`
`U.S. Patent
`
`May 28, 1996
`
`Sheet 22 of 47
`
`5,521,843
`
`START
`
`INPUT MARK IMAGE
`
`DETECT SHIFT ON SCREEN
`
`couvsnr T0 smrr m
`
`ACTUAL COORDINA res
`
`85’
`
`353
`
`s53
`
`GENERA TE SPEED coummo VALUE
`
`IN NEW COORDINATE srsrsu
`
`ourpur SPEED couu/ma VALUE
`
`954
`
`855
`
`
`
`OBJECT GRIPPED .7
`
`YES
`
`FIG.39
`
`S56
`
`SAMSUNG EXHIBIT 1006
`
`Page 23 of 68
`
`SAMSUNG EXHIBIT 1006
`Page 23 of 68
`
`
`
`U.S. Patent
`
`May 23, 1996
`
`Sheet 23 of 47
`
`5,521,843
`
`FIG.42
`
`FIG.40
`
`SAMSUNG EXHIBIT 1006
`
`Page 24 of 68
`
`SAMSUNG EXHIBIT 1006
`Page 24 of 68
`
`
`
`U.S. Patent
`
`May 28, 1996
`
`Sheet 24 of 47
`
`5,521,843
`
`START
`
`
`
`S6 7
`
`OBJECT GRIPPED .7
`
`YES
`
`END
`
`FlG.4I
`
`SAMSUNG EXHIBIT 1006
`
`Page 25 of 68
`
`INPUT MARK IMAGE
`
`DETECT smrr on SCREEN
`
`CONVERT To sum in ACTUAL
`COORDINA res
`
`couvmr T0 smrr m CAMERA
`coonomn rs srsmu
`
`GENERA rs SPEED comumo VALUE
`m CAMERA COORDINA rs srsrsu
`
`ourpur SPEED comma VALUE
`
`$6I
`
`352
`
`$63
`
`354
`
`355
`
`5“
`
`SAMSUNG EXHIBIT 1006
`Page 25 of 68
`
`
`
`U.S. Patent
`
`May “zs, 1996
`
`Sheet 25 of 47
`
`5,521,843
`
`SAMSUNG EXHIBIT 1006
`
`Page 26 of 68
`
`SAMSUNG EXHIBIT 1006
`Page 26 of 68
`
`
`
`U.S. Patent
`
`May 23, 1996
`
`Sheet 26 of 47
`
`5,521,843
`
`FIG.45(A)
`
`FIG.45lBI
`
`FlG.45(CI
`
`Xcg
`
`SAMSUNG EXHIBIT 1006
`
`Page 27 of 68
`
`SAMSUNG EXHIBIT 1006
`Page 27 of 68
`
`
`
`U.S. Patent
`
`May 23, 1996
`
`Sheet 27 of 47
`
`5,521,843
`
`FIG.47
`
`FIG.46
`
`SAMSUNG EXHIBIT 1006
`
`Page 28 of 68
`
`SAMSUNG EXHIBIT 1006
`Page 28 of 68
`
`
`
`U.S. Patent
`
`9
`May 28 1996
`
`Sheet 28 of 47
`
`5,521,843
`
`
`
`
`
` <u<u<umMMW..NH.§84.EE8-N\§EAEone3ESmi§$.2._.3.9%:3.3.2;3.3.2;32%:
`
`
`
`
`
`
`
`
`
` «N:$+w\uu¢ta3:3-~u¢‘QB‘mxfiats#J41*.1!J<qu<<<
`
`
`35$:2m_§:32%:2.2%:$§$:§$...EJVJ4..
`a<J1|<<<c}Qa<u<c<omm.m_.mmm&.m‘
`
`
`
`
`
`
`
`SAMSUNG EXHIBIT 1006
`
`Page 29 of 68
`
`SAMSUNG EXHIBIT 1006
`Page 29 of 68
`
`
`
`U.S. Patent
`
`May 28, 1996
`
`Sheet 29 of 47
`
`5,521,843
`
`
`
`
`
`$28:m§V.u:.e$.§.CEVQI55$:E25:
`
`
`
`
`
`mma.mamm
`
`B:3.n4.R:G:c¢-N\uE.R:butuin:
`
`
`
`
`
`J..x_.3_9cc.3.‘ac.<<\<nu..2c
`
`._mm
`
`SAMSUNG EXHIBIT 1006
`
`Page 30 of 68
`
`SAMSUNG EXHIBIT 1006
`Page 30 of 68
`
`
`
`U.S. Patent
`
`May 28, 1996
`
`Sheet 30 of 47
`
`5,521,843
`
`
`
`
`
`3.2%:23.2.4.321$32%:.:§$:35$:
`
`
`
`
`
`
`
`
`
`
`
`?N\o¢+N\a3RN‘\mw\8.SawEN‘EN‘N\Sua3.:
`
`..<
`
`ma.mam..mmm
`
`mm..q..<2
`
`
`
`1._JV....2.I1Ia._I!j
`
`
`
`
`
`SAMSUNG EXHIBIT 1006
`
`Page 31 of 68
`
`SAMSUNG EXHIBIT 1006
`Page 31 of 68
`
`
`
`U
`
`tHeM.
`
`PHE S..7I
`
`3%:En.
`2%:<1
`E.3335:33.:E8:32:
`3:233:S$282.5
`
`$<<29:58E25
`
`.=:mzo:Em:
`
`
`
`>5;<$-%-$:E...
`
`
`
`22...8...
`
`69Hcos2V.aM
`
`74f013mhS
`
`348:125,5
`
`3.3.2;
`
`:33:
`
`SAMSUNG EXHIBIT 1006
`
`Page 32 of 68
`
`SAMSUNG EXHIBIT 1006
`Page 32 of 68
`
`
`
`U.S. Patent
`
`May 28, 1996
`
`Sheet 32 of 47
`
`5,521,843
`
`$3.38
`
`$3.58
`
`
`
`Q2358932:8
`
`225228
`
`3»
`
`8»NS.an
`
`
`
`:§8§:...$§=>2<22mE9.5.958
`
`+3:5»>822?‘.$52»
`
`2%
`
`2338.2:
`
`3&222
`
`>223:
`
`_____
`
`E5528
`
`>2<2EE2822:
`
`
`
`NEE925%
`
`»29$:
`
`m:<2...
`
`22932
`
`ms.SE
`
`uziem
`
`2292.22
`
`m:52...
`
`«E33
`
`E:n.oC
`
`PB
`
`@2352
`
`22952
`
`=s..§:m$uszzém
`
`.335
`
`a2<228_
`
`8»
`
`_
`
`___
`
`223.38__M
`8:3:
`
`SAMSUNG EXHIBIT 1006
`
`Page 33 of 68
`
`SAMSUNG EXHIBIT 1006
`Page 33 of 68
`
`
`
`
`
`
`
`
`U.S. Patent
`
`May 28, 1996
`
`Sheet 33 of 47
`
`5,521,843
`
`SAMSUNG EXHIBIT 1006
`
`Page 34 of 68
`
`SAMSUNG EXHIBIT 1006
`Page 34 of 68
`
`
`
`U.S. Patent
`
`May 28, 1996
`
`Sheet 34 of 47
`
`5,521,843
`
`2»
`
`2»8»
`
`
`
`:2:xEmma.=x2m:mw2~l¥c1U@SE22:m89>
`
`
`
`esszfiba«E§§..a
`
`
`
`
`
`
`2»mmw.wwu%m.mEazi$528536.$3§2.»
`
`t2:z8E§=8
`
`HH
`
`<\a
`
`'1.A.
`
`.22:
`
`
`
`
`
`
`
`E«S3522:«.3522:8...:82;E.<e.G>m..3%
`
`mndl
`
`SAMSUNG EXHIBIT 1006
`
`Page 35 of 68
`
`SAMSUNG EXHIBIT 1006
`Page 35 of 68
`
`
`
`
`U.S. Patent
`
`May 28, 1996
`
`Sheet 35 of 47
`
`5,521,843
`
`we.5
`
`$3
`
`gem9.3;
`
`33,2...
`
`%§3.361
`
`§§.§§u_2..§..*
`
`
`$558538.=.G:..<..§
`:5;$3.26
`
`
`ai2..
`
`E2;2:5;Q36E
`
`:33:
`
`SAMSUNG EXHIBIT 1006
`
`Page 36 of 68
`
`SAMSUNG EXHIBIT 1006
`Page 36 of 68
`
`
`
`U.S. Patent
`
`May 28, 1996
`
`Sheet 36 of 47
`
`5,521,843
`
`FIG.55
`
`MAINMEMORY
`
`I
`
`
`
`IMAGEMEMORY
` PROCESSOR
`INTERFACE
`CAMERA
`
`SAMSUNG EXHIBIT 1006
`
`Page 37 of 68
`
`SAMSUNG EXHIBIT 1006
`Page 37 of 68
`
`
`
`U.S. Patent
`
`May 28, 1996
`
`Sheet 37 of 47
`
`5,521,843
`
`FIG.56
`
`SAMSUNG EXHIBIT 1006
`
`Page 38 of 68
`
`SAMSUNG EXHIBIT 1006
`Page 38 of 68
`
`
`
`U.S. Patent
`
`May 28, 1996
`
`Sheet 38 of 47
`
`5,521,843
`
`FIG.58
`
`SAMSUNG EXHIBIT 1006
`
`Page 39 of 68
`
`SAMSUNG EXHIBIT 1006
`Page 39 of 68
`
`
`
`U.S. Patent
`
`May 28, 1996
`
`Sheet 39 of 47
`
`5,521,843
`
`FlG.60
`
`SAMSUNG EXHIBIT 1006
`
`Page 40 of 68
`
`SAMSUNG EXHIBIT 1006
`Page 40 of 68
`
`
`
`U.S. Patent
`
`May 28, 1996
`
`Sheet 40 of 47
`
`5,521,843
`
`FlG.6l
`
`FIG. 62
`
`23 I
`
`230
`
`232
`
`234
`
`233
`
`SAMSUNG EXHIBIT 1006
`
`Page 41 of 68
`
`SAMSUNG EXHIBIT 1006
`Page 41 of 68
`
`
`
`U.S. Patent
`
`May 28, 1996
`
`Sheet 41 of 47
`
`5,521,843
`
`C
`
`INPUT IMAGE
`
`37!
`
`BAND-CONVERT T0
`BINARY IMAGE
`
`S72
`
`LABEL BINARY IMAGE AND LABEL
`
`HISTOGRAM
`
`S74
`
`SELECT MARK
`
`PRODUCE x- AND Y-
`PROJECTED HISTOGRAMS
`
`575
`
`
`
`S73
`
`375
`
`
`
`CALCULATE x zmo Y ADDRESSES (WEIGHTED
`MEANS OF X- AND Y- PROJECTED
`
`HISTOGRAMSI
`
`
`
`
`
` FOUR
`POINTS
`EX TRAC TED ?
`
`
`
`
`
`YES
`
`CALCULATE DISTANCE
`AND ATTITUDE
`
`373
`
`O
`
`FIG.63
`
`SAMSUNG EXHIBIT 1006
`
`Page 42 of 68
`
`SAMSUNG EXHIBIT 1006
`Page 42 of 68
`
`
`
`U.S. Patent
`
`May 28, 1996
`
`Sheet 42 of 47
`
`5,521,843
`
`
`
`230
`
`233
`
`234
`
`F I 6.6 4M}
`
`F I G.6 4(8)
`
`234
`
`Y
`
`236
`
`X
`
`FIG. 65
`
`235
`
`X0
`
`SAMSUNG EXHIBIT 1006
`
`Page 43 of 68
`
`SAMSUNG EXHIBIT 1006
`Page 43 of 68
`
`
`
`U.S. Patent
`
`May 28, 1996
`
`Sheet 43 of 47
`
`5,521,843
`
`mew
`
`SN
`
`New
`
`::mm.Em
`
`5:.
`
`E$.,.E
`
`3x
`
`ME
`
`SN
`
`§m.§:
`
`a.$.¢:
`
`SAMSUNG EXHIBIT 1006
`
`Page 44 of 68
`
`SAMSUNG EXHIBIT 1006
`Page 44 of 68
`
`
`
`
`U.S. Patent
`
`May 28, 1996
`
`Sheet 44 of 47
`
`5,521,843
`
`$8 I
`
`533
`
`S83
`
`S84
`
`BAND-CONVERT T0
`BINARY IMAGE
`
`LABEL BINARY IMAGE
`
`SELECT MARK
`
`INPUT IMAGE
`
`
`
`
`
`CALCULATE WEIGHT MEAN
`OF SMALL CIRCLE
`
`USING A + B
`PRODUCE X- AND Y-
`
`PROJECTED H'ST°GR’mS
`
`
`CALCULATED o/srmaureo
`WEIGHTS A or x. AND Y-
`
`PROJECTED HISTOGRAMS
`Two
`
`890
`
`39/
`
`393
`
`s93
`
`
`
`386
`
`CALCULATE WEIGHT MEAN
`or SMALL cmcus
`
`
`
`usma 3
`
`
`
`
`cmcuzs EXTRACTED
`.7
`
`YES
`
`CALCULATE WEIGHT AND
`A TTI TUDE
`
`FIG.6'7
`
`SAMSUNG EXHIBIT 1006
`
`Page 45 of 68
`
`S87
`
`S88
`
`S89
`
`EXTRACT TWO PEAKS OF X-
`
`AND Y- PROJECTED HISTOGRAMS
`
`SET MASK AROUND SMALL CIRCLE
`
`
`
`
`WEIGHTS B OF X- AND Y-
`
`PROJECTED HISTOGRAMS
`OF REVERSED SMALL CIRCLE
`
`CALCULATE DISTRIBUTED
`
`
`
`SAMSUNG EXHIBIT 1006
`Page 45 of 68
`
`
`
`U.S. Patent
`
`May 28, 1996
`
`Sheet 45 of 47
`
`5,521,843
`
`FIG.69
`
`265
`
`266'
`
`263 %
`
`251
`
`
`
`262
`
`SAMSUNG EXHIBIT 1006
`
`Page 46 of 68
`
`SAMSUNG EXHIBIT 1006
`Page 46 of 68
`
`
`
`U.S. Patent
`
`May 28, 1996
`
`Sheet 46'of 47
`
`5,521,843
`
`mpur IMAGE
`
`5"”
`
`BAND-CONVERT T0
`BINARY IMAGE
`
`3'02
`
`LABEL BINARY IMAGE
`
`3103
`
`SELECT rwo mmvs WITH IST AND
`2ND LARGEST NUMBERS or PIXELS
`
`5'04
`
`APPLY THREE-DIMENSIONAL MARK
`DETECTING PROCESS
`
`SI05
`
`SI06
`
` "Es
`
`N0
`
`
`
`SELECT FOUR MARKS
`
`APPL Y FOUR-C IRCLE
`
`DE TEC TING PROCESS
`
`SI09
`
`CALCULATE DISTANCE AND ATTITUDE
`
`FIG.70
`
`SAMSUNG EXHIBIT 1006
`
`Page 47 of 68
`
`SAMSUNG EXHIBIT 1006
`Page 47 of 68
`
`
`
`U.S. Patent
`
`May 23, 1996
`
`Sheet 47 of 47
`
`5,521,843
`
`«KN
`
`[‘I'|l
`
`III
`lllualllt
`lnllllllul
`
`III!
`
`ulllanlvnllll
`
`8.Na.:.:.
`
`8.Nu.§<
`
`Rdl
`
`SAMSUNG EXHIBIT 1006
`
`Page 48 of 68
`
`8.mo.BB
`
`1
`
`3.2.25
`
`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
`
`20
`
`25
`
`30
`
`35
`
`40
`
`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 cam-
`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.
`
`20
`
`25
`
`30
`
`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 pattem 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-histograrns 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;
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`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 showing the shift that is actually
`measured;
`
`FIG. 31 is a graph showing a z-Ez relationship;
`FIG. 32 is a graph showing an Ex-Dx relationship;
`FI