Back to results
US 9,435,888 B1Granted
Shape matching automatic recognition methods, systems and articles of manufacturing
AssigneeThe United States of America as represented by the Secretary of the Navy
InventorJeffrey Jay Hilde
Life of this patent
Estimating the term…
Abstract
Systems, methods, and articles of manufacture for automatic target recognition. A hypothesis about a target's classification, position and orientation relative to a LADAR sensor that generates range image data of a scene including the target is simulated and a synthetic range image is generated. The range image and synthetic range image are then electronically processed to determine whether the hypothesized model and position and orientation are correct. If the score is sufficiently high then the hypothesis is declared correct, otherwise a new hypothesis is formed according to a search strategy.
Claims17
A method of identifying a target in a range image of a scene, comprising:
- receiving target parameter values for a plurality of target parameters for a target hypothesis, wherein said plurality of target parameters are selected from the group of parameters describing location and orientation of said target, wherein said range image R is mathematically defined as R={(rij),i=1, . . . b,j=1 . . . c}, where b represents the number of columns of pixels in said sensor range image, c represents the number of rows of pixels in said sensor range image, and rij represents the range between an object at point ij in said sensor range image and said sensor;
- electronically generating a synthetic range image of said scene for said target hypothesis by rendering a 3-D wire grid model of a plurality of 3-D wire models of targets to be identified at said target parameter values;
- wherein one of said plurality of 3-D models has a surface which is a match to a surface of said target, where said synthetic range image Rs is mathematically defined as Rs={rijs,i=1, . . . b,j=1 . . . c}, where b represents the number of columns of pixels in said sensor range image, c represents the number of rows of pixels in said sensor range image, and rijs represents the range between an object at point ij in said synthetic range image and said sensor, wherein said generating a synthetic range image is performed using a graphics processing unit;
- electronically computing a matching score C for said target hypothesis, where said matching score C is mathematically defined as
- C
- =
- ∑
- v
- =
- 0
- k
-
- ∑
- i
- =
- 0
- b
-
- ∑
- j
- =
- 0
- c
-
- {
- var
-
-
- 2
- d
- i
-
-
- j
- <
- T
- var
-
-
- 3
- d
- i
-
-
- j
- ≥
- T
- ,
- where
- T
- =
- L
-
- (
- 1
- 2
- )
- v
- ,
- where L is a first pre-determined value, where var2 is a second pre-determined value, where var3 is a third pre-determined value, where said second pre-determined value is greater than said third pre-determined value, where k is a fourth pre-determined value, where dij is a discrepancy between said sensor range image and said synthetic range image at location ij of said synthetic range image and is mathematically defined as
- d
- ij
- =
- {
- Minimum
-
- (
- (
- r
- ij
- S
- -
- N
- ij
- )
- 2
- )
- if
-
-
- f
- i
- ,
- j
- S
- =
- true
- var
-
-
- 1
- if
-
-
- f
- i
- ,
- j
- S
- =
- false
- ,
- where var1 is a fifth pre-determined value, where said fifth pre-determined value is greater than or equal said first pre-determined value, where Nij is mathematically defined as Nij={(rmn,m),m=(i−h), . . . (i+h),n=(j−w), . . . (j+w)}, where h is a sixth pre-determined value and w is a seventh pre-determined value;
- electronically determining whether said matching score C exceeds a pre-determined threshold score;
- and
- electronically identifying said target model located and positioned according to said target parameter values to be a match to said target when said matching score C exceeds said pre-determined threshold score.
103 more elements
A method of electronically identifying a target in a range image of a scene, comprising:
- receiving target parameter values for a plurality of target parameters for a target hypothesis, wherein said plurality of target parameters are selected from the group of parameters describing location and orientation of said target, wherein said range image R is mathematically defined as R={(rij),i=1, . . . b,j=1 . . . c}, where b represents the number of columns of pixels in said sensor range image, c represents the number of rows of pixels in said sensor range image, and rij represents the range between an object at point ij in said sensor range image and said sensor;
- electronically generating a synthetic range image of said scene for said target hypothesis by rendering a 3-D wire grid model of a plurality of 3-D wire models of targets to be identified at said target parameter values;
- wherein one of said plurality of 3-D models has a surface which is a match to a surface of said target, where said synthetic range image Rs is mathematically defined as Rs={rijs,i=1, . . . b,j=1 . . . c}, where b represents the number of columns of pixels in said sensor range image, c represents the number of rows of pixels in said sensor range image, and rijs represents the range between an object at point ij in said synthetic range image and said sensor;
- electronically computing an average range difference a between said sensor range image and said synthetic range image Rs, where said average range difference a is mathematically defined as:
- a
- =
- ∑
- i
- =
- 1
- b
-
- ∑
- j
- =
- 1
- c
-
- r
- ij
- S
- -
- r
- ij
- if
-
-
- f
- ij
- S
- =
- true
- 0
- if
-
-
- f
- ij
- S
- =
- true
- ∑
- i
- =
- 1
- b
-
- ∑
- j
- =
- 1
- c
-
- 1
- if
-
-
- f
- ij
- S
- =
- true
- 0
- if
-
-
- f
- ij
- S
- =
- false
- ,
- where fijs=true for all pixel locations ij of said synthetic range image Rs that lie on said rendered 3-D wire-grid model Rs in said synthetic range image, and where fijs=false for all pixel locations ij of said synthetic range image Rs that do not lie on said rendered 3-D wire-grid model in said synthetic range image Rs;
- electronically range-syncing said synthetic range image, resulting in a range-synced synthetic range image RsyncS for said target hypothesis, where said range-synced synthetic range image RsyncS is mathematically defined as RsyncS={(rijs−ad),i=1, . . . b,j=1 . . . c};
- electronically computing a matching score C for said target hypothesis, where said matching score C is mathematically defined as
- C
- =
- ∑
- v
- =
- 0
- k
-
- ∑
- i
- =
- 0
- b
-
- ∑
- j
- =
- 0
- c
-
- {
- var
-
-
- 2
- d
- ij
- <
- T
- var
-
-
- 3
- d
- ij
- ≥
- T
- ,
- where
- T
- =
- L
-
- (
- 1
- 2
- )
- v
- ,
- where L is equal to a first pre-determined value, where var2 is a second pre-determined value, where var3 is a third pre-determined value, where said second pre-determined value is greater than said third pre-determined value, where k is a fourth pre-determined value, where dij is a discrepancy between said sensor range image and said synthetic range image at location ij of said synthetic range image and is mathematically defined as
- d
- ij
- =
- {
- Minimum
-
- (
- (
- (
- r
- ij
- S
- -
- ad
- )
- -
- N
- ij
- )
- 2
- )
- if
-
-
- f
- i
- ,
- j
- S
- =
- true
- var
-
-
- 1
- if
-
-
- f
- i
- ,
- j
- S
- =
- false
- ,
- where var1 is a fifth pre-determined value, where said fifth pre-determined value is greater than or equal said first pre-determined value, where Nij is mathematically defined as Nij={(rmn,m),m=(i−h), . . . (i+h),n=(j−w), . . . (j+w)}, where h is a sixth pre-determined value and w is a seventh pre-determined value;
- electronically determining whether said matching score C exceeds a pre-determined threshold score;
- and
- electronically identifying declaring said target model located and positioned according to said target parameter values to be a match to said target when said matching score C exceeds said pre-determined threshold score.
172 more elements
A non-transitory computer readable medium having stored thereon a plurality of computer executable instructions that, when executed by a computer including a graphics processing unit, cause the computer to:
- receive target parameter values for a plurality of target parameters for a target hypothesis, wherein said plurality of target parameters are selected from the group of parameters describing location and orientation of said target, wherein a range image R of a scene including a target is mathematically defined as R={(rij),i=1, . . . b,j=1 . . . c}, where b represents the number of columns of pixels in said range image, c represents the number of rows of pixels in said range image, and rij represents the range between an object at point ij in said range image and said sensor;
- generate a synthetic range image of said scene for said target hypothesis by rendering a 3-D wire grid model of a plurality of 3-D wire models of targets to be identified at said target parameter values using said graphics processing unit;
- wherein one of said plurality of 3-D models has a surface which is a match to a surface of said target, where said synthetic range image Rs is mathematically defined as Rs={rijs,i=1, . . . b,j=1 . . . c}, where b represents the number of columns of pixels in said range image, c represents the number of rows of pixels in said range image, and rijs represents the range between an object at point ij in said synthetic range image and said sensor;
- compute an average range difference a between said range image and said synthetic range image Rs, where said average range difference a is mathematically defined as:
- a
- =
- ∑
- i
- =
- 1
- b
-
- ∑
- j
- =
- 1
- c
-
- r
- ij
- S
- -
- r
- ij
- if
-
-
- f
- ij
- S
- =
- true
- 0
- if
-
-
- f
- ij
- S
- =
- true
- ∑
- i
- =
- 1
- b
-
- ∑
- j
- =
- 1
- c
-
- 1
- if
-
-
- f
- ij
- S
- =
- true
- 0
- if
-
-
- f
- ij
- S
- =
- false
- ,
- where fijs=true for all pixel locations ij of said synthetic range image Rs that lie on said rendered 3-D wire-grid model Rs in said synthetic range image, and where fijs=false for all pixel locations ij of said synthetic range image Rs that do not lie on said rendered 3-D wire-grid model in said synthetic range image Rs;
- range-sync said synthetic range image, resulting in a range-synced synthetic range image RsyncS for said target hypothesis, where said range-synced synthetic range image RsyncS is mathematically defined as RsyncS={(rijs−ad),i=1, . . . b,j=1 . . . c};
- compute a matching score C for said target hypothesis, where said matching score C is mathematically defined as
- C
- =
- ∑
- v
- =
- 0
- k
-
- ∑
- i
- =
- 0
- b
-
- ∑
- j
- =
- 0
- c
-
- {
- var
-
-
- 2
- d
- ij
- <
- T
- var
-
-
- 3
- d
- ij
- ≥
- T
- ,
- where
- T
- =
- L
-
- (
- 1
- 2
- )
- v
- ,
- where L is equal to a first pre-determined value, where var2 is a second pre-determined value, where var3 is a third pre-determined value, where said second pre-determined value is greater than said third pre-determined value, where k is a fourth pre-determined value, where dij is a discrepancy between said range image and said synthetic range image at location ij of said synthetic range image and is mathematically defined as
- d
- ij
- =
- {
- Minimum
-
- (
- (
- (
- r
- ij
- S
- -
- ad
- )
- -
- N
- ij
- )
- 2
- )
- if
-
-
- f
- i
- ,
- j
- S
- =
- true
- var
-
-
- 1
- if
-
-
- f
- i
- ,
- j
- S
- =
- false
- ,
- where var1 is a fifth pre-determined value, where said fifth pre-determined value is greater than or equal said first pre-determined value, where Nij is mathematically defined as Nij={(rmn,m),m=(i−h), . . . (i+h),n=(j−w), . . . (j+w)}, where h is a sixth pre-determined value and w is a seventh pre-determined value;
- determine whether said matching score C exceeds a pre-determined threshold score;
- and
- identify said target model located and positioned according to said target parameter values to be a match to said target when said matching score C exceeds said pre-determined threshold score.
172 more elements
A non-transitory computer readable medium having stored thereon a plurality of computer executable instructions that, when executed by a computer including a graphics processing unit, cause the computer to:
- receive target parameter values for a plurality of target parameters for a target hypothesis, wherein said plurality of target parameters are selected from the group of parameters describing location and orientation of said target, wherein a range image R of a scene including a target is mathematically defined as R={(rij),i=1, . . . b,j=1 . . . c}, where b represents the number of columns of pixels in said range image, c represents the number of rows of pixels in said range image, and rij represents the range between an object at point ij in said range image and said sensor;
- generate a synthetic range image of said scene for said target hypothesis by rendering a 3-D wire grid model of a plurality of 3-D wire models of targets to be identified at said target parameter values;
- wherein one of said plurality of 3-D models has a surface which is a match to a surface of said target, where said synthetic range image Rs is mathematically defined as Rs={rijs,i=1, . . . b,j=1 . . . c}, where b represents the number of columns of pixels in said range image, c represents the number of rows of pixels in said range image, and rijs represents the range between an object at point ij in said synthetic range image and said sensor;
- compute a matching score C for said target hypothesis, where said matching score C is mathematically defined as
- C
- =
- ∑
- v
- =
- 0
- k
-
- ∑
- i
- =
- 0
- b
-
- ∑
- j
- =
- 0
- c
-
- {
- var
-
-
- 2
- d
- ij
- <
- T
- var
-
-
- 3
- d
- ij
- ≥
- T
- ,
- where
- T
- =
- L
-
- (
- 1
- 2
- )
- v
- ,
- where L is a first pre-determined value, where var2 is a second pre-determined value, where var3 is a third pre-determined value, where said second pre-determined value is greater than said third pre-determined value, where k is a fourth pre-determined value, where dij is a discrepancy between said range image and said synthetic range image at location ij of said synthetic range image and is mathematically defined as
- d
- ij
- =
- {
- Minimum
-
- (
- (
- r
- ij
- S
- -
- N
- ij
- )
- 2
- )
- if
-
-
- f
- i
- ,
- j
- S
- =
- true
- var
-
-
- 1
- if
-
-
- f
- i
- ,
- j
- S
- =
- false
- ,
- where var1 is a fifth pre-determined value, where said fifth pre-determined value is greater than or equal said first pre-determined value, where Nij is mathematically defined as Nij={(rmn,m),m=(i−h), . . . (i+h),n=(j−w), . . . (j+w)}, where h is a sixth pre-determined value and w is a seventh pre-determined value;
- determine whether said matching score C exceeds a pre-determined threshold score;
- and
- identify said target model located and positioned according to said target parameter values to be a match to said target when said matching score C exceeds said pre-determined threshold score.
97 more elements
Dependencies are inferred from the claim text.