Moving body recognition apparatus

• US 5,872,858 A
• Filed: 04/25/1995
• Issued: 02/16/1999
• Est. Priority Date: 09/17/1991
• Status: Expired due to Fees

• Current Assignee: Fujitsu Limited
• Original Assignee: Fujitsu Limited
• Inventors: Shiohara, Morito, Kamada, Hiroshi, Kubota, Takashi
• Primary Examiner(s): Mancuso, Joseph
• Assistant Examiner(s): Patel, Jayanti K.
• Application Number:
  US08/429,483
• Time in Patent Office: 1,393 Days
• Field of Search: 382/107, 382/190, 382/236, 382/297, 348/699, 348/700
• US Class Current: 382/107
• CPC Class Codes: G06T 7/246 using feature-based methods, e.g. the tracking of corners or segments
• CPC Class Codes: G06V 10/757 Matching configurations of points or features
• CPC Class Codes: G06V 40/20 Movements or behaviour, e.g. gesture recognition recognition of facial expressions G06V40/16

Abstract

A moving body recognition apparatus which recognizes a shape and movement of an object moving in relation to an image input unit by extracting feature points, e.g. a peak of the object and a boundary of color, each in said images captured at a plurality of instants in time for observation by the image input unit. The moving body recognition apparatus comprises an image input unit for capturing images of an object as a moving body having a rotation, a feature point extraction unit for extracting feature points from the images inputted by the image input unit, a feature point storage unit for storing known position data of the extracted feature points, and a shape/movement recognition unit for calculating the actual positions and movements of the feature points of the object in the images by using the known position data of the extracted feature points outputted from the feature point storage unit.

Claims

1. A moving body recognition apparatus for recognizing a movement of a moving object by positions of feature points in an image corresponding to said moving object, comprising:

image input means for capturing images of said moving object;

feature point extraction means for extracting feature points in said images captured by said image input means;

feature point position storage means for storing known position data corresponding to said extracted feature points; and

shape/movement recognition means for calculating actual positions of said extracted feature points and a movement of said object from said known position data of three of said extracted feature points forming a right angle of said object each in said images captured at any two instances in time from a direction perpendicular to an axis of rotation of said object moving on a single plane and said object having a rotation, two positions at said two instances of any one of said three feature points being on a plane parallel to said direction perpendicular to said axis of rotation.

2. The moving body recognition apparatus according to claim 1, wherein:

said shape/movement recognition means processes said images of said object captured from said direction perpendicular to said axis of rotation as orthogonally projected images of said object.

3. The moving body recognition apparatus according to claim 2, wherein said feature point extraction means comprises:

space filter means for extracting an outline image from said images captured by said image input means; and

edge point extraction means for extracting an edge point from said outline image and for storing it as feature point data in said feature point position storage means.

4. The moving body recognition apparatus according to claim 2, further comprising:

feature point position storage means for storing the actual positions of feature points outputted from said shape/movement recognition means; and

object movement storage means for storing the angle of rotation of an object outputted from said shape/movement recognition means.

5. The moving body recognition apparatus according to claim 4, configured as a computer system comprising:

a television camera in correspondence with said image input means;

image processing hardware including a space filter in correspondence with said feature point extraction means;

a first memory in correspondence with said feature point position storage means;

a central processing unit (CPU) in correspondence with said shape/movement recognition means;

a second memory in correspondence with said feature point position storage means and object movement storage means; and

a sensor for outputting to said CPU known position data regarding the shape and movement of said object.

6. The moving body recognition apparatus according to claim 4, wherein:

said image input means captures images of said object monitored by a visual device of an automatically running vehicle or an image of said object inspected in an inspection of factory automation (FA); and

said feature point position storage means and said object movement storage means store the results of recognizing the movements of said object being monitored or inspected.

7. The moving body recognition apparatus according to claim 4, wherein said shape/movement recognition means comprises:

known data input means for receiving from an external sensor known data regarding movements and positions of said feature points of said object;

feature point position normalization means for obtaining as normalized known position data the relative positions of the other two feature points when one of said three feature points of an object at the peak forming said right angle each in said images captured at any two instances in time for observation falls on the origin of a three-dimensional coordinate space;

shape/movement determination means for determining an enablement or a disablement of recognizing said movements and positions of feature points of said object by using an output from said feature point position normalization means;

movement calculation means, activated by a determination by said shape/movement determination means of an enablement of recognizing said movements and positions of said feature points of said object, for calculating an angle of rotation of said object around said origin by using an output from said feature point position normalization means;

shape calculation means for obtaining unknown position data other than said known position data of said three feature points 0, 1 and 2 of said object by using outputs from said movement calculation means and said feature point position normalization means; and

feature point position reconstruction means for outputting a movement of said object by combining an angle of rotation around said origin outputted from said movement calculation means with said position data of said feature point falling on said origin in said images outputted from said feature point position normalization means, and for outputting positions of feature points by combining said unknown position data outputted from said shape calculation means with said position data of said three feature points 0, 1 and 2 in said images outputted from said feature point position normalization means.

8. The moving body recognition apparatus according to claim 7, wherein external memory means for temporarily storing known data outputted from said external sensor on an offline basis is provided before an input to said known data input means.

9. The moving body recognition apparatus according to claim 7, wherein the whole processes of said shape/movement recognition means comprise:

a first step of determining whether or not said known data input means has received at least one of expressions θ

=n π

(where n is an integer), α

+θ

=n π

-α

, and u₁₁ v₂₁ +u₂₁ v₁₁ =0, when the relations between two-dimensional vectors u_i and v_i are expressed as;

space="preserve" listing-type="equation">v.sub.i =R u.sub.i (where i=1,

     2)

and

space="preserve" listing-type="equation">u.sub.1 =d.sub.1 cos α

sin α

!.sup.t,

and

space="preserve" listing-type="equation">u.sub.2 =d.sub.2 cos (α

±

π

/2) sin (α

±

π

/2!.sup.t,

where the X axis is the direction of a parallel displacement of said feature points, the Z axis is the direction parallel to the axis of rotation of said object and, the Y axis is a direction perpendicular to an image plane, which is the XZ plane,

space="preserve" listing-type="equation">u.sub.i = u.sub.i1, u.sub.i2 !.sup.t, v.sub.i = v.sub.i1, v.sub.i2 !.sup.t

(where i=1,

     2) on the XY plane represent relative positions of a feature points i (where i=1, 2, i.e. two not falling on the origin of said three feature points 0, 1 and

     2) from the origin on which feature point 0 falls respectively at said first and second instants in time for observation and rotation matrix R ##EQU236## represents a two-dimensional rotation on the XY plane around the origin of an object from said first instant in time for observation to said second instant in time for observation, a set of recognition solutions <

1>

represents actual positions and movements of feature points 1 and 2 when vector u₂ is obtained by rotating vector u₁ by π

/2, and a set of recognition solutions <

2>

represents actual positions and movements of feature points 1 and 2 when vector u₂ is obtained by rotating vector u₁ by -π

/2;

a second step, invoked when said shape/movement recognition means determines positively in said first step, of executing recognition disablement process {1} after said known data input means outputs a deactivation signal to said feature point position normalization means and recognition disablement data to said movement calculation means;

a third step, invoked when said shape/movement recognition means determines negatively in said first step, of determining whether said feature point position storage means has stored positions of said three feature points 0, 1 and 2 in said images at two instants in time for observation, which is repeated until a positive determination is obtained;

a fourth step, invoked when said shape/movement recognition means determines positively in said third step, of having said feature point position storage means send an activation signal to said feature point position normalization means, thereby activating said feature point position normalization means;

a fifth step of having feature point position normalization means store positions of said three feature points 0, 1 and 2 each in said images stored in said feature point position storage means and obtain first components of vectors u_i and v_i (where i=1,

     2) as the X coordinate values by subtracting from the X coordinate values of feature points 1 and 2 in said images the X coordinate values of feature point 0 in said images, which falls on the origin of said XZ plane;

a sixth step of having said shape/movement determination means determine whether said first components of vectors u₁ and v₁ obtained by said feature point position normalization means satisfy next condition,

space="preserve" listing-type="equation">v.sub.11 ≠

±

u.sub.11 or v.sub.21 =±

u.sub.21 ;

a seventh step, invoked when said shape/movement determination means determines negatively in said sixth step, of having said shape/movement determination means output recognition disablement data to said movement calculation means, thereby executing a recognition disablement process {1};

an eighth step, invoked when said shape/movement determination means determines positively in said sixth step, of having said shape/movement determination means activate said movement calculation means for executing a process of said movement calculation means;

a ninth step of having shape calculation means execute its process;

a tenth step of having said feature point position reconstruction means obtain set of recognition solutions <

1>

representing actual positions and movements of feature points 1 and 2 when vector u₂ is obtained by rotating vector u₁ by π

/2 by using the second components of vectors u_i and v_i and rotation matrix R sent from said movement calculation means and shape calculation means;

an eleventh step of having said feature point position reconstruction means obtain set of recognition solutions <

2>

representing actual positions and movements of feature points 1 and 2 when vector u₂ is obtained by rotating vector u₁ by -π

/2 by using expressions ##EQU237## (where i=1,

     1) a twelfth step of having said feature point position reconstruction means determine whether or not either set of recognition solutions <

1>

or <

2>

satisfies known data of said object received by said known data input means;

a thirteenth step, invoked when said feature point position recognition means determines negatively in said twelfth step, of having feature point position reconstruction means execute a recognition disablement process {2};

a fourteenth step, invoked when said feature point position reconstruction means determines negatively in said twelfth step, of having said feature point position reconstruction means store in said object movement storage means rotation matrix R in the set of recognition solutions satisfying said known data and the coordinate values of feature point 0 in said images outputted from said feature point position normalization means; and

a fifteenth step of having said feature point position reconstruction means store in said feature point position storage means second components u_i and v_i (where i=1,

     2) in said set of recognition solutions satisfying said known data and coordinate values of feature points 0, 1 and 2 in said images outputted from said feature point position normalization means, thereby ending the whole processes.

10. The moving body recognition apparatus according to claim 9, wherein said movement calculation means:

obtains an integer n (=0, 1, 2, or

     3) defining the value range of angle α

formed between one of said two-dimensional vectors u₁ and the X axis, such that

space="preserve" listing-type="equation">(π

/2)n≦

α

≦

(π

/2)(n+1)

in accordance with the sign of the values of first components u₁₁ and u₂₁ of two of said two-dimensional vectors u₁ and u₂, by a next table

space="preserve" listing-type="tabular">______________________________________ 0 <

α

<

π

/2 <

π

<

α

<

3π

/2 <

α

0 π

/2 π

/2 α

<

π

π

3π

/2 3π

/2 α

<

2π

2π

______________________________________u.sub.11 + + 0 - - - 0 + N.A.u.sub.21 0 - - - 0 + + + N.A.______________________________________

obtains an integer m (=0, 1, 2 or

     3) defining the value range of angle β

formed between one of said two-dimensional vectors v₁ and the X axis, such that

space="preserve" listing-type="equation">(π

/2)m≦

β

≦

(π

/2) (m+1)

in accordance with the sign of the values of first components v₁₁ and v₂₁ of two of said two-dimensional vectors v₁ and v₂, by a next table

space="preserve" listing-type="tabular">______________________________________ 0 <

β

<

π

/2 <

π

<

β

<

3π

/2 <

β

0 π

/2 π

/2 β

<

π

π

3π

/2 3π

/2 β

<

2π

2π

______________________________________v.sub.11 + + 0 - - - 0 + N.A.v.sub.21 0 - - - 0 + + + N.A.______________________________________

determines the signs of sinθ

by using the values of integers n and m defining the value ranges of angles α and

β

;

calculates said rotation matrix R by using expressions

space="preserve" listing-type="equation">cos θ

=(u.sub.11 u.sub.21 +v.sub.11 v.sub.21)/(u.sub.11 v.sub.21 +u.sub.21 v.sub.11)

space="preserve" listing-type="equation">sin θ

=±

(1-cos.sup.2 θ

).sup.1/2 ;

determines whether or not said rotation matrix R thus calculated or its inverse rotation matrix R^-1 satisfies said known data of said object received by said known data input means;

invokes said recognition disablement process {1} when neither said rotation matrix R nor said inverse rotation matrix R^-1 satisfies said known data; and

sends the values of angle α and

rotation matrix R or said rotation matrix R or said rotation matrix R^-1 satisfying said known data to said shape calculation means and said feature point position reconstruction means.

11. The moving body recognition apparatus according to claim 10, wherein said movement calculation means determines the sign of sinθ

by a method comprising;

a step 1 of determining whether the value of an integer (m-n) is odd or even;

a step 2, invoked when the value of integer (m-n) is determined to be odd in said step 1, of determining whether the value of an integer p is odd or even, where p=(m-n-1)/2

a step 3, invoked when the value of integer p is determined to be odd in said step 2, of determining that the sign of sinθ

is positive;

a step 4, invoked when the value of integer p is determined to be even in said step 2, of determining that the sign of sinθ

is positive;

a step 5, invoked when the value of integer (m-n) is determined to be even in said step 1, of determining the sign of sinθ

by a next table through a comparison between the values of u₁₁ and v₁₁.

space="preserve" listing-type="tabular">______________________________________m n conditions sin⊖

______________________________________0 0 u.sub.11 <

v.sub.11 -1 1 u.sub.11 >

v.sub.11 +2 2 u.sub.11 <

v.sub.11 +3 3 u.sub.11 >

v.sub.11 -0 2 |u.sub.11 | <

|v.sub.11 | +2 0 |u.sub.11 | >

|v.sub.11 | -1 3 |u.sub.11 | <

|v.sub.11 | -3 1 |u.sub.11 | >

|v.sub.11 | +______________________________________

12. The moving body recognition apparatus according to claim 9, wherein said recognition disablement process {1} comprises:

a step of having said movement calculation means send to said feature point position reconstruction means recognition disablement data; and

a step of having said feature point position reconstruction means store said recognition disablement data in said object movement storage means and said feature point position storage means, for a process completion.

13. The moving body recognition apparatus according to claim 9, wherein said shape calculation means:

determines whether the first components u₁₁ and u₂₁ of two of said two-dimensional vectors u₁ and u₂ are zero;

executes a shape calculation process {1} on determining that neither one of the first components u₁₁ and u₂₁ of two of said two-dimensional vectors u₁ and u₂ is zero,

calculates the second components u₁₂ and u₂₂ of two of said vectors u₁ and u₂ by using expressions

space="preserve" listing-type="equation">u.sub.12 =d.sub.1 sin α and

u.sub.22 =d.sub.2 cos α

obtains the second components v₁₂ and v₂₂ of two of said two-dimensional vectors v₁ and v₂ by using expressions

space="preserve" listing-type="equation">v.sub.12 =R.sub.2 u.sub.1 and v.sub.22 =R.sub.2 u.sub.2, and

sends to said feature point position reconstruction means the second components u₁₂, u₂₂, v₁₂ and v₂₂ of said two-dimensional vectors u₁, u₂, v₁ and v₂ ;

executes a shape calculation process {2} on determining that the first component u₁₁ of one of said two-dimensional vectors u₁ is zero,

calculates the second components u₁₂ and u₂₂ of two of said vectors u₁ and u₂ by using expressions

space="preserve" listing-type="equation">u.sub.12 =d.sub.1 sin α and

u.sub.22 =d.sub.2 cos α

obtains the second components v₁₂ and v₂₂ of two of said two-dimensional vectors v₁ and v₂ by using expressions

space="preserve" listing-type="equation">v.sub.12 =R.sub.2 u.sub.1 and v.sub.22 =R.sub.2 u.sub.2, and

sends to said feature point position reconstruction means the second components u₁₂, u₂₂, v₁₂ and v₂₂ of said two-dimensional vectors u₁, u₂, v₁ and v₂ ; and

executes a shape calculation process {3} on determining that the first components u₁₁ and u₂₁ of two of said two-dimensional vectors u₁ and u₂ are respectively non-zero and zero,

calculates the second components u₁₂ and u₂₂ of two of said vectors u₁ and u₂ by using expressions

space="preserve" listing-type="equation">u.sub.12 =d.sub.1 sin α and

u.sub.22 =d.sub.2 cos α

obtains the second components v₁₂ and v₂₂ of two of said two-dimensional vectors v₁ and v₂ by using expressions

space="preserve" listing-type="equation">v.sub.12 =R.sub.2 u.sub.1 and v.sub.22 =R.sub.2 u.sub.2, and

sends to said feature point position reconstruction means the second components u₁₂, u₂₂, v₁₂ and v₂₂ of said two-dimensional vectors u₁, u₂, v₁ and v₂.

14. The moving body recognition apparatus according to claim 13, wherein said shape calculation process {1} comprises:

a step of obtaining said angle α

formed between one of said two-dimensional vectors u₁ and the X axis by using an expression

space="preserve" listing-type="equation">tan α

=(u.sub.11 cos θ

-v.sub.11)/u.sub.11 sin θ

; and

a step of obtaining lengths d₁ and d₂ of two of said two-dimensional vectors u₁ and u₂ by expressions d₁ =u₁₁ /cosα and

d₂ =-u₂₁ /sinα

.

15. The moving body recognition apparatus according to claim 13, wherein said shape calculation process {2} comprises:

a step 6 of determining whether or not the value of the first component u₂₁ of one of said two-dimensional vectors u₂ is less than zero,

a step 7, invoked when the value of u₂₁ is determined to be less than zero in step 6, of equalizing the value of angle α

to π

/2 and obtaining lengths d₁ and d₂ of two of said two-dimensional vectors u₁ and u₂ by using expressions

space="preserve" listing-type="equation">d.sub.1 =|v.sub.11 /sin θ

| and d.sub.2 =|u.sub.21 |;

and

a step 8, invoked when the value of u₂₁ is not determined to be less than zero in step 6, of equalizing the value of angle α

to 3 π

/2 and obtaining lengths d₁ and d₂ of two of said two-dimensional vectors u₁ and u₂ by using expressions

space="preserve" listing-type="equation">d.sub.1 =|v.sub.11 /sin θ

| and d.sub.2 =|u.sub.21 |.

16. The moving body recognition apparatus according to claim 13, wherein said shape calculation process {3} comprises:

a step 9 of determining whether or not the value of the first component u₁₁ of one of said two-dimensional vectors u₁ is greater than zero,

a step 10, invoked when the value of u₁₁ is determined to be greater than zero in step 9, of equalizing the value of angle α

to zero and obtaining lengths d₁ and d₂ of two of said two-dimensional vectors u₁ and u₂ by expressions

space="preserve" listing-type="equation">d.sub.1 =|u.sub.11 | and d.sub.2 =|v.sub.21 /sin θ

|;

and

a step 11, invoked when the value of u₁₁ is not determined to be greater than zero in step 6, of equalizing the value of angle α

to π and

obtaining lengths d₁ and d₂ of two of said two-dimensional vectors u₁ and u₂ by expressions

space="preserve" listing-type="equation">d.sub.1 =|u.sub.11 | and d.sub.2 =|v.sub.2 /sin θ

|.

17. The moving body recognition apparatus according to claim 9, wherein said recognition disablement process {2} comprises:

a step of having said feature point position reconstruction means store recognition disablement data in said object movement storage means and said feature point position storage means, for a process completion.

18. The moving body recognition apparatus according to claim 9, wherein the whole processes of said shape/movement recognition means comprise:

a first step of determining whether or not said known data input means has received at least one of θ

=n π

(where n is an integer), α

+θ

=n π

-α

, and

space="preserve" listing-type="equation">u.sub.11 v.sub.21 +u+u.sub.21 v.sub.11 =0,

when the relations between two-dimensional vectors u_i and v_i are expressed as;

v_i =R u_i (where i=1,

     2),

u₁ =d₁ cosα

sinα

!^t, and

u₂ =d₁ cos(α

±

π

/2) sin(α

±

π

/2)!^t,

where the X axis is the direction of a parallel displacement of said feature points, the Z axis is the direction parallel to the axis of rotation of said object and, the Y axis is a direction perpendicular to an image plane, which is the XZ plane,

space="preserve" listing-type="equation">u.sub.i = u.sub.i1, u.sub.i2 !.sup.t, v.sub.i = v.sub.i1, v.sub.i2 !.sup.t (where i=1,

     2)

on the XY plane represent relative positions of a feature points i (where i=1, 2, i.e. two of three feature points not falling on the origin) from the origin on which feature point 0 falls respectively at said first and second instances in time for observation and rotation matrix R ##EQU238## represents a two-dimensional rotation on the XY plane around the origin of an object from said first instance in time for observation to said second instance in time for observation, a set of recognition solutions <

1>

represents actual positions and movements of feature points 1 and 2 when vector u₂ is obtained by rotating vector u₁ by π

/2, and a set of recognition solutions <

2>

represents actual positions and movements of feature points 1 and 2 when vector u₂ is obtained by rotating vector u₁ by -π

/2;

a second step, invoked when said shape/movement recognition means determines positively in said first step, of executing recognition disablement process {1} after said known data input means outputs a deactivation signal to said feature point position normalization means and recognition disablement data to said movement calculation means;

a third step, invoked when said shape/movement recognition means determines negatively in said first step, of determining whether said feature point position storage means has stored positions of said three feature points 0, 1 and 2 each in said images at two instances in time for observation, which is repeated until a positive determination is obtained;

a fourth step, invoked when said shape/movement recognition means determines positively in said third step, of having said feature point position storage means send an activation signal to said feature point position normalization means, thereby activating said feature point position normalization means;

a fifth step of having feature point position normalization means store positions of said three feature points 0, 1 and 2 each in said images stored in said feature point position storage means and obtain first components of vectors u_i and v_i (where i=1,

     2) as the X coordinate values obtained by subtracting from the X coordinate values of feature points 1 and 2 in said images the X coordinate values of feature point 0 in said images, which falls on the origin of said XZ plane;

a sixth step of having said shape/movement determination means determine whether said first and second components of vectors u_i and v_i (where i=1,

     2) obtained by said feature point position normalization means satisfy next condition,

space="preserve" listing-type="equation">v.sub.11 ≠

±

u.sub.11 or v.sub.21 =±

.sub.21 ;

a seventh step, invoked when said shape/movement determination means determines negatively in said sixth step, of having said shape/movement determination means output recognition disablement data to said movement calculation means, thereby executing a recognition disablement process {1};

an eighth step, invoked when said shape/movement determination means determines positively in said sixth step, of having said shape/movement determination means activate said movement calculation means for executing a process of said movement calculation means;

a ninth step of having shape calculation means execute its process;

a tenth step of having said feature point position reconstruction means obtain set of recognition solutions <

2>

representing actual positions and movements of feature points 1 and 2 when vector u₂ is obtained by rotating vector u₁ by -π

/2 by using the second components of vectors u_i2 and v_i and rotation matrix R sent from said movement calculation means and shape calculation means;

an eleventh step of having said feature point position reconstruction means obtain set of recognition solutions <

1>

representing actual positions and movements of feature points 1 and 2 when vector u₂ is obtained by rotating vector u₁ by π

/2 by using expressions ##EQU239## a twelfth step of having said feature point position reconstruction means determine whether or not either set of recognition solutions <

1>

or <

2>

satisfies known data of said object received by said known data input means;

a thirteenth step, invoked when said feature point position recognition means determines negatively in said twelfth step, of having feature point position reconstruction means execute a recognition disablement process {2};

a fourteenth step, invoked when said feature point position reconstruction means determines negatively in said twelfth step, of having said feature point position reconstruction means store in said object movement storage means rotation matrix R in the set of recognition solutions satisfying said known data and the coordinate values of feature point 0 in said images outputted from said feature point position normalization means; and

a fifteenth step of having said feature point position reconstruction means store in said feature point position storage means second components of u_i and v_i (where i=1,

     2) in said set of recognition solutions satisfying said known data and coordinate values of feature points 0, 1 and 2 in said images outputted from said feature point position normalization means, thereby ending the whole processes.

19. A moving body recognition apparatus for recognizing a movement of a moving object by positions of feature points in images of said moving object, comprising:

image input means for capturing images of said moving object from a direction perpendicular to an axis of rotation of said object moving on a single plane and said object having a rotation;

feature point extraction means for extracting three feature points in said images captured at two instances in time by said image input means, two positions at said two instances of any one of said three feature points being on a plane parallel to said direction perpendicular to said axis of rotation;

feature point position storage means for storing known position data of said extracted three feature points; and

movement recognition means for calculating a movement of said object from said known position data of said extracted three feature points forming a right angle of said object each in said images captured by said image input means.