Identifying, matching and tracking multiple objects in a sequence of images

• US 9,087,384 B2
• Filed: 10/16/2012
• Issued: 07/21/2015
• Est. Priority Date: 10/19/2011
• Status: Active Grant

• Current Assignee: Crown Equipment Corporation
• Original Assignee: Crown Equipment Corporation
• Inventors: Holeva, Lee F., Elston, Edwin R., Jensen, Eric L., Seelinger, Michael J., Yoder, John-David S.
• Primary Examiner(s): Bhatnagar, Anand
• Assistant Examiner(s): Park, Soo
• Application Number:
  US13/652,649
• Publication Number:
  US 20130101167A1
• Time in Patent Office: 1,008 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: B66F 9/122 longitudinally movable
• CPC Class Codes: B66F 9/24 Electrical devices or systems
• CPC Class Codes: G06T 2207/10016 Video; Image sequence
• CPC Class Codes: G06T 7/13 Edge detection
• CPC Class Codes: G06T 7/20 Analysis of motion motion estimation for coding, decoding, compressing or decompressing digital video signals H04N19/43, H04N19/51

Abstract

A method of tracking scored candidate objects in a sequence of image frames acquired by a camera is provided. The scored candidate objects may comprise a set of existing scored candidate objects associated with a prior image frame and a set of new scored candidate objects associated with a next image frame.

Claims

1. A method of tracking scored candidate objects in a sequence of image frames acquired by a camera, the scored candidate objects comprising a set of existing scored candidate objects associated with a prior image frame and a set of new scored candidate objects associated with a next image frame, wherein each of the plurality of the scored candidate objects has a respective composite object score that represents a likelihood that the scored candidate object corresponds to an actual pallet structure in an image frame, the method comprising:

determining, by a computer, a respective location for each new scored candidate object in the next image frame; and

analyzing the new scored candidate objects, wherein said analyzing comprises;

for each particular existing scored candidate object;

identifying, by the computer, a respective first location of this particular existing scored candidate object in the prior image frame,

estimating, by the computer, a respective second location in the next image frame, wherein the respective second location is estimated based on movement of the camera between acquisition of the prior image frame and the next image frame,

calculating, by the computer, a respective prediction window, wherein the respective prediction window defines a set of pixel locations in the next image frame nearby the respective second location, and

for any new scored candidate object having a respective location within the respective prediction window, tentatively matching that new scored candidate object with this particular existing scored candidate object;

wherein the computer maintains a list of the existing scored candidate objects being tracked; and

said analyzing comprises;

adding any new scored candidate objects, whose respective location is not within the respective prediction window for any of the existing scored candidate objects, to the existing list of scored candidate objects being tracked.

2. The method of claim 1, wherein said analyzing comprises:

for each new scored candidate object that tentatively matches both a first existing scored candidate object and a second existing scored candidate object;

calculating a first value that comprises the absolute value of the difference between the respective composite object score of the new scored candidate object and the respective composite object score of the first existing scored candidate object;

calculating a second value that comprises the absolute value of the difference between the respective composite object score of the new scored candidate object and the respective composite object score of the second existing scored candidate object;

if the first value is less than, or equal to, the second value, then maintaining the tentative match between the first existing scored candidate object and the new scored candidate object, and ignoring the new scored candidate object with respect to the second existing scored candidate object; and

if the second value is less than the first value, then maintaining the tentative match between the second existing scored candidate object and the new scored candidate object, and ignoring the new scored candidate object with respect to the first existing scored candidate object.

3. The method of claim 1, wherein said analyzing comprises:

for each existing scored candidate object that tentatively matches both a first new scored candidate object and a second new scored candidate object;

calculating a first value that comprises the absolute value of the difference between the respective composite object score of the existing scored candidate object and the respective composite object score of the first new scored candidate object;

calculating a second value that comprises the absolute value of the difference between the respective composite object score of the existing scored candidate object and the respective composite object score of the second new scored candidate object;

if the first value is less than, or equal to, the second value, then maintaining the tentative match between the existing scored candidate object and the first new scored candidate object, and ignoring the second new scored candidate object with respect to the existing scored candidate object; and

if the second value is less than the first value, then maintaining the tentative match between the second new scored candidate object and the existing scored candidate object, and ignoring the first new scored candidate object with respect to the existing scored candidate object.

4. The method of claim 1, wherein said analyzing comprises:

deleting any unmatched existing scored candidate objects from the list of scored candidate objects being tracked, wherein an unmatched existing scored candidate object has no matching new scored candidate object.

5. The method of claim 4, wherein the sequence of image frames comprises a plurality of image frames in sequential order starting at a first image frame and ending at a last image frame, wherein acquisition of the first image frame occurs prior to acquisition of the last image frame, whereby each particular image frame, other than the first image frame and the last image frame, has a role as both:

a current next image frame in the sequence, when this particular image frame is acquired after the acquisition of its immediate predecessor image frame in the sequence, and

a current prior image frame in the sequence, when the immediate successor image frame in the sequence is acquired after acquisition of this particular image frame.

6. The method of claim 5, wherein deleting any unmatched existing scored candidate objects from the list of scored candidate objects being tracked, comprises:

for each of a subset of image frames in the sequence immediately preceding the prior image frame, determining whether the unmatched existing scored candidate object was also unmatched when that image frame of the subset was the current prior image in the sequence;

if the unmatched existing scored candidate object was also unmatched in each of the subset of image frames, then deleting the unmatched existing scored candidate object; and

if the unmatched existing scored candidate object was not unmatched in each of the subset of image frames, then maintaining the unmatched existing scored candidate object in the list of scored candidate objects being tracked.

7. The method of claim 6, wherein the subset of image frames comprises 3 image frames.

8. The method of claim 1, wherein the sequence of image frames comprises a plurality of image frames in sequential order starting at a first image frame and ending at a last image frame, wherein acquisition of the first image frame occurs prior to acquisition of the last image frame, whereby each particular image frame, other than the first image frame and the last image frame, has a role as both:

a current next image frame in the sequence, when this particular image frame is acquired after the acquisition of its immediate predecessor image frame in the sequence, and

a current prior image frame in the sequence, when the immediate successor image frame in the sequence is acquired after acquisition of this particular image frame.

9. The method of claim 8, further comprising:

acquiring a new successor image frame relative to the current next image frame;

changing the role of the current next image frame to be that of the current prior image frame; and

updating the list of scored candidate objects being tracked based on said analyzing.

10. A system of tracking scored candidate objects in a sequence of image frames acquired by a camera, the scored candidate objects comprising a set of existing scored candidate objects associated with a prior image frame and a set of new scored candidate objects associated with a next image frame, wherein each of the plurality of the scored candidate objects has a respective composite object score that represents a likelihood that the scored candidate object corresponds to an actual pallet structure in an image frame, the system comprising:

a computer configured to execute instructions in an accessible memory, said accessible memory storing a list of the existing scored candidate objects being tracked;

the computer when executing instructions stored in the accessible memory;

determines a respective location for each new scored candidate object in the next image frame;

performs analysis of the new scored candidate objects, wherein said analysis comprises;

for each particular existing scored candidate object;

identifying a respective first location of this particular existing scored candidate object in the prior image frame,

estimating a respective second location in the next image frame, wherein the respective second location is estimated based on movement of the camera between acquisition of the prior image frame and the next image frame,

calculating a respective prediction window, wherein the respective prediction window defines a set of pixel locations in the next image frame nearby the respective second location, and

for any new scored candidate object having a respective location within the respective prediction window, tentatively matching that new scored candidate object with this particular existing scored candidate object; and

adding any new scored candidate objects, whose respective location is not within the respective prediction window for any of the existing scored candidate objects, to the existing list of scored candidate objects being tracked.

11. The system of claim 10, wherein said analysis further comprises:

for each new scored candidate object that tentatively matches both a first existing scored candidate object and a second existing scored candidate object;

calculating a first value that comprises the absolute value of the difference between the respective composite object score of the new scored candidate object and the respective composite object score of the first existing scored candidate object;

calculating a second value that comprises the absolute value of the difference between the respective composite object score of the new scored candidate object and the respective composite object score of the second existing scored candidate object;

if the first value is less than, or equal to, the second value, then maintaining the tentative match between the first existing scored candidate object and the new scored candidate object, and ignoring the new scored candidate object with respect to the second existing scored candidate object; and

if the second value is less than the first value, then maintaining the tentative match between the second existing scored candidate object and the new scored candidate object, and ignoring the new scored candidate object with respect to the first existing scored candidate object.

12. The system of claim 10, wherein said analysis further comprises:

for each existing scored candidate object that tentatively matches both a first new scored candidate object and a second new scored candidate object;

calculating a first value that comprises the absolute value of the difference between the respective composite object score of the existing scored candidate object and the respective composite object score of the first new scored candidate object;

calculating a second value that comprises the absolute value of the difference between the respective composite object score of the existing scored candidate object and the respective composite object score of the second new scored candidate object;

if the first value is less than, or equal to, the second value, then maintaining the tentative match between the existing scored candidate object and the first new scored candidate object, and ignoring the second new scored candidate object with respect to the existing scored candidate object; and

if the second value is less than the first value, then maintaining the tentative match between the second new scored candidate object and the existing scored candidate object, and ignoring the first new scored candidate object with respect to the existing scored candidate object.

13. The system of claim 10, wherein the computer when executing instructions stored in the accessible memory:

deletes any unmatched existing scored candidate objects from the list of scored candidate objects being tracked, wherein an unmatched existing scored candidate object has no matching new scored candidate object.

14. The system of claim 13, wherein the sequence of image frames comprises a plurality of image frames in sequential order starting at a first image frame and ending at a last image frame, wherein acquisition of the first image frame occurs prior to acquisition of the last image frame, whereby each particular image frame, other than the first image frame and the last image frame, has a role as both:

a current next image frame in the sequence, when this particular image frame is acquired after the acquisition of its immediate predecessor image frame in the sequence, and a current prior image frame in the sequence, when the immediate successor image frame in the sequence is acquired after acquisition of this particular image frame.

15. The system of claim 14, wherein the computer, when executing instructions stored in the accessible memory, deletes any unmatched existing scored candidate objects from the list of scored candidate objects being tracked, according to:

for each of a subset of image frames in the sequence immediately preceding the prior image frame, determining whether the unmatched existing scored candidate object was also unmatched when that image frame of the subset was the current prior image in the sequence;

if the unmatched existing scored candidate object was also unmatched in each of the subset of image frames, then deleting the unmatched existing scored candidate object; and

if the unmatched existing scored candidate object was not unmatched in each of the subset of image frames, then maintaining the unmatched existing scored candidate object in the list of scored candidate objects being tracked.

16. The system of claim 15, wherein the subset of image frames comprises 3 image frames.

17. The system of claim 10, wherein the sequence of image frames comprises a plurality of image frames in sequential order starting at a first image frame and ending at a last image frame, wherein acquisition of the first image frame occurs prior to acquisition of the last image frame, whereby each particular image frame, other than the first image frame and the last image frame, has a role as both:

a current next image frame in the sequence, when this particular image frame is acquired after the acquisition of its immediate predecessor image frame in the sequence, and

a current prior image frame in the sequence, when the immediate successor image frame in the sequence is acquired after acquisition of this particular image frame.

18. The system of claim 17, wherein the computer when executing instructions stored in the accessible memory:

acquires a new successor image frame relative to the current next image frame;

changes the role of the current next image frame to be that of the current prior image frame; and

updates the list of scored candidate objects being tracked based on said analysis.

19. A computer program product of tracking scored candidate objects in a sequence of image frames acquired by a camera, the scored candidate objects comprising a set of existing scored candidate objects associated with a prior image frame and a set of new scored candidate objects associated with a next image frame, wherein each of the plurality of the second candidate objects has a respective composite object score that represents a likelihood that the scored candidate object corresponds to an actual pallet structure in an image frame, the computer program product comprising:

a non-transitory computer readable storage medium having computer readable program code embodied therewith, the computer readable program code comprising;

computer readable program code configured to determine a respective location for each new scored candidate object in the next image frame;

computer readable program code configured to perform analysis of the new scored candidate objects, wherein said analysis comprises;

for each particular existing scored candidate object;

identifying a respective first location of this particular existing scored candidate object in the prior image frame,

estimating a respective second location in the next image frame, wherein the respective second location is estimated based on movement of the camera between acquisition of the prior image frame and the next image frame,

calculating a respective prediction window, wherein the respective prediction window defines a set of pixel locations in the next image frame nearby the respective second location, and

for any new scored candidate object having a respective location within the respective prediction window, tentatively matching that new scored candidate object with this particular existing scored candidate object

computer readable program code configured to maintain a list of the existing scored candidate objects being tracked; and

computer readable program code configured to add any new scored candidate objects, whose respective location is not within the respective prediction window for any of the existing scored candidate objects, to the existing list of scored candidate objects being tracked.

20. The computer program product of claim 19, wherein said analysis further comprises:

for each new scored candidate object that tentatively matches both a first existing scored candidate object and a second existing scored candidate object;

calculating a first value that comprises the absolute value of the difference between the respective composite object score of the new scored candidate object and the respective composite object score of the first existing scored candidate object;

calculating a second value that comprises the absolute value of the difference between the respective composite object score of the new scored candidate object and the respective composite object score of the second existing scored candidate object;

if the first value is less than, or equal to, the second value, then maintaining the tentative match between the first existing scored candidate object and the new scored candidate object, and ignoring the new scored candidate object with respect to the second existing scored candidate object; and

if the second value is less than the first value, then maintaining the tentative match between the second existing scored candidate object and the new scored candidate object, and ignoring the new scored candidate object with respect to the first existing scored candidate object.

21. The computer program product of claim 19, wherein said analysis further comprises:

for each existing scored candidate object that tentatively matches both a first new scored candidate object and a second new scored candidate object;

calculating a first value that comprises the absolute value of the difference between the respective composite object score of the existing scored candidate object and the respective composite object score of the first new scored candidate object;

calculating a second value that comprises the absolute value of the difference between the respective composite object score of the existing scored candidate object and the respective composite object score of the second new scored candidate object;

if the first value is less than, or equal to, the second value, then maintaining the tentative match between the existing scored candidate object and the first new scored candidate object, and ignoring the second new scored candidate object with respect to the existing scored candidate object; and

if the second value is less than the first value, then maintaining the tentative match between the second new scored candidate object and the existing scored candidate object, and ignoring the first new scored candidate object with respect to the existing scored candidate object.

22. The computer program product of claim 19, further comprising:

computer readable program code configured to delete any unmatched existing scored candidate objects from the list of scored candidate objects being tracked, wherein an unmatched existing scored candidate object has no matching new scored candidate object.

23. The computer program product of claim 22, wherein the sequence of image frames comprises a plurality of image frames in sequential order starting at a first image frame and ending at a last image frame, wherein acquisition of the first image frame occurs prior to acquisition of the last image frame, whereby each particular image frame, other than the first image frame and the last image frame, has a role as both:

a current next image frame in the sequence, when this particular image frame is acquired after the acquisition of its immediate predecessor image frame in the sequence, and

a current prior image frame in the sequence, when the immediate successor image frame in the sequence is acquired after acquisition of this particular image frame.

24. The computer program product of claim 23, further comprising:

computer readable program code configured to delete any unmatched existing scored candidate objects from the list of scored candidate objects being tracked, according to;

for each of a subset of image frames in the sequence immediately preceding the prior image frame, determining whether the unmatched existing scored candidate object was also unmatched when that image frame of the subset was the current prior image in the sequence;

if the unmatched existing scored candidate object was also unmatched in each of the subset of image frames, then deleting the unmatched existing scored candidate object; and

if the unmatched existing scored candidate object was not unmatched in each of the subset of image frames, then maintaining the unmatched existing scored candidate object in the list of scored candidate objects being tracked.

25. The computer program product of claim 24, wherein the subset of image frames comprises 3 image frames.

26. The computer program product of claim 19, wherein the sequence of image frames comprises a plurality of image frames in sequential order starting at a first image frame and ending at a last image frame, wherein acquisition of the first image frame occurs prior to acquisition of the last image frame, whereby each particular image frame, other than the first image frame and the last image frame, has a role as both:

a current next image frame in the sequence, when this particular image frame is acquired after the acquisition of its immediate predecessor image frame in the sequence, and

a current prior image frame in the sequence, when the immediate successor image frame in the sequence is acquired after acquisition of this particular image frame.

27. The computer program product of claim 26, further comprising:

computer readable program code configured to acquire a new successor image frame relative to the current next image frame;

computer readable program code configured to change the role of the current next image frame to be that of the current prior image frame; and

computer readable program code configured to update the list of scored candidate objects being tracked based on said analysis.