Real time image registration, motion detection and background replacement using discrete local motion estimation

• US 6,798,897 B1
• Filed: 09/05/2000
• Issued: 09/28/2004
• Est. Priority Date: 09/05/1999
• Status: Active Grant

• Current Assignee: Protrack Limited
• Original Assignee: Protrack Limited
• Inventors: Rosenberg, Yoav
• Primary Examiner(s): Mehta, Bhavesh M.
• Assistant Examiner(s): AZARIAN, SEYED H
• Application Number:
  US09/654,679
• Time in Patent Office: 1,484 Days
• Field of Search: 382/100, 382/154, 382/107, 382/181, 382/151, 382/109, 382/103, 382/106, 382/284, 382/276, 382/309, 382/254, 382/232, 382/294, 348/586, 348/552, 348/44, 348/38, 348/51, 348/558, 348/559, 348/565, 348/154, 348/587, 356/27, 356/28, 356/29, 356/34, 352/46, 600/532
• US Class Current: 382/107
• CPC Class Codes: G06T 7/33 using feature-based methods
• CPC Class Codes: G06T 7/35 using statistical methods

Abstract

A method for registration between first and second images, the method including defining, for each individual location from among a plurality of locations sparsely distributed over the first image, a local probability matrix in which each element represents the probability of a possible displacement between the individual location in the first image and its corresponding location within the second image, defining a combined probability matrix by combining corresponding elements over the plurality of probability matrices, and computing an alignment of the first and second images in accordance with a combination of at least one of the largest of the elements of the combined probability matrix; and further, a method for detecting motion within a scene including at least one moving objects by comparing first and second time-separated images of the scene, the method comprising defining, for each individual location from among a plurality of locations distributed over the first image, a local probability matrix in which each element represents the probability of a possible displacement between said individual location in the first image, representing an individual portion of the scene in the first image, and its corresponding location within the second image, and ranking the local probability matrices into a plurality of ranks of matrices, differing in the probability that the individual location corresponding to a matrix belonging to a rank was displaced between the first and second images, relative to what is known regarding camera motion between the first and second images.

Claims

1. A method for registration between first and second images, the method comprising:

for each individual location from among a plurality of locations sparsely distributed over the first image, defining a local probability matrix in which each element represents the probability of a possible displacement between said individual location in the first image and its corresponding location within the second image;

defining a combined probability matrix by combining corresponding elements over the plurality of probability matrices; and

computing an alignment of the first and second images in accordance with a combination of at least one of the largest of the elements of the combined probability matrix.

2. A method according to claim 1 wherein the corresponding elements which are combined in said combined probability matrix defining step comprise elements within the local probability matrices which are similarly positioned if each individual local probability matrix is shifted to represent the effect on the individual location corresponding to the individual matrix, of a particular non-translational transformation between the first and second images.

3. A method according to claim 2 and also comprising repeating said combined probability matrix defining step for each of a plurality of possible non-translational transformations between the first and second images;

and

selecting at least one most likely non-translational transformation from among said plurality of possible non-translational transformations; and

wherein said step of computing an alignment comprises

computing a relative non-translational transformation of the first and second images by computing a combination of said at least one most likely non-translational transformation; and

computing a relative translation of the first and second images by computing a combination of at least one of the largest of the elements of the at least one combined probability matrices of the at least one most likely non-translational transformations.

4. A method according to claim 3 wherein said step of selecting at least one most likely non-translational transformations from among said plurality of possible non-translational transformations includes:

comparing a set of at least one of the largest of the elements in each of the combined probability matrices of each of the plurality of possible non-translational transformations;

selecting at least one set from among the compared sets whose members are largest; and

selecting as most likely non-translational transformations, the at least one non-translational transformation corresponding to said at least one set whose members are largest.

5. A method according to claim 1 wherein the probability matrix is characterized in that each i,j element therewithin represents the probabilities that the individual point corresponds to an individual point in the second image, which is displaced correspondingly to the displacement of the i,j element from the center of the probability matrix.

6. A method according to claim 1 wherein the corresponding elements which are combined comprise similarly positioned elements within the local probability matrices.

7. A method according to claim 1 and also comprising executing said alignment.

8. A method according to claim 3 and also comprising executing said alignment by effecting said relative non-translational transformation and said relative translation of the first and second images.

9. A method according to claim 3 wherein said plurality of possible non-translational transformations between the first and second images includes at least one relative rotation between the first and second images.

10. A method according to claim 3 wherein said plurality of possible non-translational transformations between the first and second images includes at least one relative zoom between the first and second images.

11. A method according to claim 3 wherein said plurality of possible non-translational transformations between the first and second images includes at least one transformation which comprises a combination of zoom and rotation between the first and second images.

12. A method according to claim 3 wherein said plurality of possible non-translational transformations between the first and second images includes at least one non-translational affine transformation between the first and second images.

13. A method for detecting motion within a scene by comparing first and second time-separated images of the scene, the method comprising:

for each individual location from among a plurality of locations distributed over the first image, defining a local probability matrix in which each element represents the probability of a possible displacement between said individual location in the first image, representing an individual portion of the scene in the first image, and its corresponding location within the second image; and

ranking the local probability matrices into a plurality of ranks of matrices, differing in the probability that the individual location corresponding to a matrix belonging to a rank was displaced between the first and second images, relative to what is known regarding camera motion between the first and second images.

14. A method according to claim 13 wherein said ranking step comprises comparing the center region of each local probability matrix to the peripheral regions thereof.

15. A method according to claim 13 wherein said ranking step comprises:

constructing a combined probability matrix in which each element represents the probability of a possible camera motion-caused displacement between said first image and said second image; and

ranking the local probability matrices in accordance with the degree to which they respectively resemble said combined probability matrix.

16. A method according to claim 13 and also comprising deriving the second image from a third image of the scene, separated in time from the first image of the scene, including:

selecting a transformation which, when applied to the third image, results in an image similar to said first image; and

applying the transformation to the third image, thereby to derive the second image.

17. A method according to claim 16 wherein said transformation has a non-translational component.

18. A method according to claim 16 wherein said transformation having a non-translational component comprises a non-translational transformation.

19. A system for registration between first and second images, the system comprising:

a local probability matrix generator operative to define, for each individual location from among a plurality of locations sparsely distributed over the first image, a local probability matrix in which each element represents the probability of a possible displacement between said individual location in the first image and its corresponding location within the second image;

a combined probability matrix generator defining a combined probability matrix by combining corresponding elements over the plurality of probability matrices; and

an image aligner computing an alignment of the first and second images in accordance with a combination of at least one of the largest of the elements of the combined probability matrix.

20. A system for detecting motion within a scene by comparing first and second time-separated images of the scene, the system comprising:

a local probability matrix generator defining, for each individual location from among a plurality of locations distributed over the first image, a local probability matrix in which each element represents the probability of a possible displacement between said individual location in the first image, representing an individual portion of the scene in the first image, and its corresponding location within the second image; and

a location displacement evaluation unit operative to rank the local probability matrices into a plurality of ranks of matrices, differing in the probability that the individual location corresponding to a matrix belonging to a rank was displaced between the first and second images, relative to what is known regarding camera motion between the first and second images.

21. A method for registration between first and second images, the method comprising:

for each individual location from among a plurality of locations sparsely distributed over the first image, defining a local displacement score matrix in which each element'"'"'s position within the matrix corresponds to a possible displacement between the first and second images, relative to an apriori model of registration between the first and second images and wherein each element in the matrix comprises a score representing the extent to which the individual location in the first image resembles a corresponding location within the second image to which the individual location in the first image is translated under the possible displacement;

defining a combined displacement score matrix by combining corresponding elements over the plurality of local displacement score matrices; and

computing an alignment of the first and second images in accordance with a combination of at least one of the largest of the elements of the combined displacement score matrix.

22. A system for registration between first and second images, the system comprising:

a local displacement score matrix generator operative to define, for each individual location from among a plurality of locations sparsely distributed over the first image, a local displacement score matrix in which each element'"'"'s position within the matrix corresponds to a possible displacement between the first and second images, relative to an apriori model of registration between the first and second images and wherein each element in the matrix comprises a score representing the extent to which the individual location in the first image resembles a corresponding location within the second image to which the individual location in the first image is translated under the possible displacement;

a combined displacement score matrix generator operative to combine corresponding elements over the plurality of local displacement score matrices; and

an aligner operative to compute an alignment of the first and second images in accordance with a combination of at least one of the largest of the elements of the combined displacement score matrix.