Dynamic method for recognizing objects and image processing system therefor

• US 5,063,603 A
• Filed: 11/06/1989
• Issued: 11/05/1991
• Est. Priority Date: 11/06/1989
• Status: Expired due to Term

• Current Assignee: Sarnoff Corporation (SRI International, Inc.)
• Original Assignee: David Sarnoff Research Center, Inc.
• Inventors: Burt, Peter J.
• Primary Examiner(s): Boudreau, Leo H.
• Assistant Examiner(s): Fox, David
• Application Number:
  US07/432,013
• Time in Patent Office: 729 Days
• Field of Search: 382/2, 382/37, 382/38, 382/41, 382/39, 358/84
• US Class Current: 382/115
• CPC Class Codes: G06V 10/25 Determination of region of interest [ROI] or a volume of interest [VOI]
• CPC Class Codes: G06V 30/2504 Coarse or fine approaches, e.g. resolution of ambiguities or multiscale approaches
• CPC Class Codes: G06V 40/166 using acquisition arrangements

Abstract

A time series of successive relatively high-resolution frames of image data, any frame of which may or may not include a graphical representation of one or more predetermined specific members (e.g., particular known persons) of a given generic class (e.g. human beings), is examined in order to recognize the identity of a specific member if that member'"'"'s image is included in the time series. The frames of image data may be examined in real time at various resolutions, starting with a relatively low resolution, to detect whether some earlier-occurring frame includes any of a group of image features possessed by an image of a member of the given class. The image location of a detected image feature is stored and then used in a later-occurring, higher resolution frame to direct the examination only to the image region of the stored location in order to (1) verify the detection of the aforesaid image feature, and (2) detect one or more other of the group of image features, if any is present in that image region of the frame being examined. By repeating this type of examination for later and later occurring frames, the accumulated detected features can first reliably recognize the detected image region to be an image of a generic object of the given class, and later can reliably recognize the detected image region to be an image of a certain specific member of the given class.

Claims

1. A dynamic image-processing method for recognizing objects of a given class graphically represented in a time series of successive relatively high-resolution frames of image data;

said method being responsive to (A) a stored program for controlling said image-processing and for specifying a set of decision criteria, and (B) stored data;

wherein objects of said given class all possess a group of known generic attributes which, taken as a whole, distinguish objects of said given class from objects not of said given class; and

wherein said stored data initially defines a limited number of separate features related to said group of generic attributes, any of which initially stored features is likely to be present in a sequence of one or more successive frames of image data if an object of said given class is graphically represented in that sequence;

said method comprising the steps of;

a) under the control of said stored program and in response to at least a first one of said separate features initially defined by said stored data, making a first determination in accordance with said decision criteria as to a first probability that one or more relatively early-occurring frames of said time series may include as part of said image data thereof at least said first one of said separate features of objects of said given class;

b) in response to said first probability being at least equal to a first predetermined threshold value, adding data defining at least the relative location of said part within the relatively early-occurring frames of said sequence to said stored data, thereby enhancing said stored data;

c) under the control of said stored program and in response to said enhanced stored data, making a second determination in accordance with said decision criteria as to a second probability that one or more relatively later-occurring frames of said time series verifies said part as including at least a second one of said separate features in addition to said first feature;

d) in response to said second probability being above a second predetermined threshold, recognizing said part as being a graphical representation of an object of said given class;

e) in response to said second probability being below a third predetermined threshold which third predetermined threshold is significantly below said second predetermined threshold, recognizing said part as not being a graphical representation of an object of said given class;

f) in response to said second probability being in a range between said second and third probabilities, adding further data defined by the verification of step c) to said stored data, thereby further enhancing said stored data; and

g) if said second probability is in said range, recursively repeating steps c) and f) for relatively later and later occurring sequences of one or more frames of said time series until the probability determined by such repeated step d) either rises above said second predetermined threshold or falls below said third predetermined threshold.

2. The method defined in claim 1, wherein said method further comprises the step of:

analyzing each of said successive relatively high-resolution frames of image data into a multi-resolution pyramid comprised of at least one level that exhibits a lower resolution than that of said high-resolution frames prior to step (a);

wherein in step (a) the first probability is the probability with which any of the lower-resolution levels of the multi-resolution pyramid of a sequence of one or more relatively early-occuring frames of said time series may include as part of said image data thereof at least said first one of said separate features of objects of said given class; and

wherein in step (c) the second probability is the probability that any of the levels of the multi-resolution pyramid of a sequence of one or more relatively later-ocurring frames of said time series verifies said part as including at least a second one of said separate features in addition to said first feature;

3. The method defined in claim 2, wherein said graphic representation of objects of said given class comprises a two-dimensional representation of a movable three-dimensional object, whereby the location, size and/or shape of said two-dimensional representation in a frame of said movable object may vary from one frame to another.

4. The method defined in claim 3, wherein said time series of sucessive frames are comprised of two-dimensional representations of actual three-dimensional objects viewed by a camera, at least one of said viewed actual three-dimensional objects being movable.

5. The method defined in claim 4, wherein said given class of objects is comprised of human beings, and said group of known attributes includes attributes of the human face.

6. The method defined in claim 4, comprising the further steps of:

h) continually measuring the distance between the television camera viewing said movable object and said movable object to obtain current measurement data of said distance; and

i) utilizing said current measurement data together with said enhanced stored data in the performance of step c) to make said second determination.

7. The method defined in claim 2, wherein:

said given class of objects is comprised of a plurality of preselected members, each of which preselected members of said given class is individually defined by possessing a unique set of known species of each of at least a sub-group of said known generic attributes; and

for each species of each one of said generic attributes of said sub-group, said stored data includes a separate species-feature related to a graphical representation of that species of that one generic attribute in a particular pyramid level of said successive frames,

said method comprising the further steps of;

h) under the control of said stored program, and in response to said part being recognized as a graphical representation of an object of said given class, comparing, in turn, each separate stored species-feature related to each different species of a first given one of said generic attributes of said sub-group at a particular pyramid level with said part to determine which of said compared species corresponds to said part with a highest probability that is greater than a predetermined threshold probability; and

i) repeating step h), in turn, for each separate stored species-feature related to each different species of each other given one of said generic attributes of said sub-group at a particular pyramid level, thereby determining the unique set of known species graphically represented by said part and the preselected individual member, if any, defined by that unique set.

8. The method defined in claim 7, wherein said graphic representation of objects of said given class comprises a two-dimensional representation of a movable three-dimensional object, whereby the location, size and/or shape of said two-dimensional representation in a frame of said movable object may vary from one frame to another.

9. The method defined in claim 8, wherein said time series of successive frames comprise television frames of actual three-dimensional objects viewed by a television camera, at least one of said viewed actual three-dimensional objects being movable.

10. The method defined in claim 9, wherein said given class of objects is comprised of human beings, and said group of known attributes includes attributes of the human face, whereby said preselected individual members of said given class are comprised of preselected persons.

11. An image-processing system for dynamically recognizing objects of a given class graphically represented in a time series of successive relatively high-resolution frames of image data;

wherein objects of said given class all possess a first group of known generic attributes which, taken as a whole, distinguish objects of said given class from objects not of said given class and each known member of said given class possesses a second group of known specific attributes which, taken as a whole, distinguish that known member from other members of said given class;

said system comprising;

first means for storing a stored program for controlling said image-processing and for specifying a set of decision criteria,

second means for storing data which includes a set of initial data, said initial data defining a limited number of separate features related to at least said first group of generic attributes, any of which initially stored features is likely to be present in a sequence of one or more successive frames of image data if an object of said given class is graphically represented in that sequence;

third means coupled to said first and second means for (1) making a first determination in accordance with said decision criteria as to a first probability that one or more relatively early-occurring frames of said time series may include as part of said image data thereof at least said first one of said separate features of objects of said given class;

(2) in response to said first probability being at least equal to a first predetermined threshold value, storing additional data in said second means that defines at least the relative location of said part within the relatively early-occurring frames of said sequence, thereby enhancing the data stored in said second means;

(3) making a second determination in accordance with said decision criteria as to a second probability that one or more relatively later-occurring frames of said time series verifies said part as including at least a second one of said separate features in addition to said first feature;

(4) in response to said second probability being above a second predetermined threshold, recognizing said part as being a graphical representation of an object of said given class;

(5) in response to said second probability being below a third predetermined threshold which third predetermined threshold is significantly below said second predetermined threshold, recognizing said part as not being a graphical representation of an object of said given class;

(6) in response to said second probability being in a range between said second and third probabilies, storing in said second means further additional data that is defined by said second determination, thereby further enhancing the data stored in said second means; and

(7) if said second probability is in said range, recursively making additional determinations for relatively later and later occurring sequences of one or more frames of said time series until the probability determined by the final additional determination either rises above said second predetermined threshold or falls below said third predetermined threshold.

12. The system defined in claim 11 further comprising:

means for analyzing each of said successive relatively high-resolution frames of image data into a multi-resolution pyramid comprised of at least one level that exhibits a lower resolution than that of said high-resolution frames; and

wherein third means are coupled to said first, second and analyzing means for (1) making a first determination in accordance with said decision criteria as to a first probability with which any of the lower-resolution levels of the multi-resolution pyramid of a sequence of one or more relatively early-occurring frames of said time series may include as part of said image data thereof at least said first one of said separate features of objects of said given class;

(2) in response to said first probability being at least equal to a first predetermined threshold value, storing additional data in said second means that defines at least the relative location of said part within the relatively early-occurring frames of said sequence, thereby enhancing the data stored in said second means;

(3) making a second determination in accordance with said decision criteria as to a second probability that any of the levels of the multi-resolution pyramid of a sequence of one or more relatively later-occurring frames of said time series verifies said part as including at least a second one of said separate features in addition to said first feature;

(4) in response to said second probability being above a second predetermined threshold, recognizing said part as being a graphical representation of an object of said given class;

(5) in response to said second probability being below a third predetermined threshold which third predetermined threshold is significantly below said second predetermined threshold, recognizing said part as not being a graphical representation of an object of a said given class;

(6) in response to said second probability being in a range between said second and third probabilities, storing in said second means further additional data that is defined by said second determination, thereby further enhancing the data stored in said second means; and

(7) if said second probability is in said range, recursively making additional determinations for relatively later and later occurring sequences of one or more frames of said time series until the probability determined by the final additional determination either rises above said second predetermined threshold or falls below said third predetermined threshold.

13. The system defined in claim 11, wherein said graphic representation of objects of said given class comprises a two-dimensional representation of a movable object, whereby the location of said two-dimensional representation in a frame of said movable object may vary from one frame to another;

and wherein said system further includes;

moving-object means responsive to said successive frames of image data for deriving the respective pixel locations in a frame of those pixels that define the graphical representation of moving objects; and

wherein said third means is coupled to said moving-object means for employing said respective pixel locations of said moving objects as an additional feature in making said probability determinations and, in response to the probability being determined to be in said range, storing them as additional data in said second means.

14. The system defined in claim 11, wherein said graphic representation of objects of said given class comprises a two-dimensional representation of an object having predetermined color hue characteristics;

and wherein said system includes;

color-detecting means responsive to said successive frames of image data for deriving the respective pixel locations in a frame of those pixels that define the graphical representation of objects having said predetermined color hue characteristics; and

wherein said third means is coupled to said color-detecting means for employing said respective pixel locations of said objects having said predetermined color hue characteristics as an additional feature in making said probability determinations and, in response to the probability being determined to be in said range, storing them as additional data in said second means.

15. The system defined in claim 11, wherein among the features defined by the initial data stored in said second means are predetermined pattern shapes associated with the two-dimensional graphical representation of said objects of said given class;

and wherein said third means includes;

matching means for correlating pattern shapes defined by the pixels constituting each successive frame of image data at a certain resolution against each of said predetermined pattern shapes, and for employing the correlation values derived thereby in the making of said probability determinations; and

means responsive to the probability being determined to be in said range for storing the locations of the correlated pixels in said second means.

16. The system defined in claim 15, wherein said time series of successive frames is comprised of two-dimensional representations of actual three-dimensional objects viewed by imaging means including a camera and distance-measuring means, at least one of said viewed actual three-dimensional objects being movable, whereby the size of a two-dimensional representation of an actual three-dimensional movable object varies in accordance with the distance of said actual three-dimensional movable object from said camera, and said image data for each frame includes distance data corresponding to each of the two-dimensional pixel locations of that frame;

and wherein said third means further includes;

size-adjusting means responsive to said distance data for scaling the size of said predetermined pattern shapes that are correlated by said correlation means in accordance with said distance data, whereby the number of scaled sizes of each predetermined pattern shape that is required to be initially stored is minimumized.

17. The system defined in claim 15, wherein said time series of successive frames is comprised of two-dimensional representations of actual three-dimensional objects viewed by imaging means including a camera, at least one of said viewed actual three-dimensional objects being movable, whereby the pattern shape of a two-dimensional representation of an actual three-dimensional movable object varies in accordance with the orientation of said actual three-dimensional movable object with respect to said camera;

and wherein said third means further includes;

orientation-transformation means responsive to the correlation value derived by said matching means for continually varying the orientation of at least one of the two pattern shapes then being correlated against each other until the correlation value is maximized.

18. The system defined in claim 17, wherein said initially-stored pattern shapes include a plurality of stored pattern shapes each of which corresponds to a two-dimensional representation of the same three-dimensional object of said given class in a different predetermined orintation thereof;

and wherein said orientation-transformation means includes;

pattern-shape-orientation transformation means for deriving a computed pattern shape from said plurality of stored pattern shapes which has an orientation which is a variable mix of the respective different orientations of said plurality of stored pattern shapes and said pattern-shape-orientation transformation means being responsive to the correlation value derived by correlating said computer pattern shape against a pattern shape derived from said image data for continually varying the mix of said plurality of stored pattern shapes until the correlation value of the two pattern shapes then being correlated against each other is maximized.

19. The system defined in claim 15, wherein said time series of successive frames is comprised of two-dimensional representations of actual three-dimensional stationary and movable objects of a scene viewed by imaging means including a camera;

wherein all objects of said given class in said scene are movable;

wherein said second means stores the respective pixel locations of the pattern shape of the two-dimensional representation of each stationary object in said scene as viewed by said camera; and

wherein;

said matching means is responsive to the stored respective pixel locations of the pattern shape of the two-dimensional representation of each stationary object for excluding that stationary-object pattern shape present in each frame of image data from being correlated against each of said predetermined pattern shapes.