Optical flow estimation method and image synthesis method

Abstract

Optical flow is calculated for each patch on the basis of two images, and then a region having low confidence and a region having high confidence are separated depending on confidence of the optical flow, and the optical flow in the region having low confidence is interpolated using the optical flow in its surrounding regions.

What is claimed is:  
     
       1. An optical flow estimation method adapted to calculate optical flow for each patch on the basis of two Images, said method comprising the steps of: 
       separating a region having low confidence and a region having high confidence, depending on confidence of said optical flow; and  
       interpolating said optical flow in said region having low confidence using said optical flow in said low confidence region surrounding regions;  
       wherein confidence y is found, upon calculating from a 2×2 matrix of coefficients G in the following equation (a) having as elements the squares of differentials in the vertical and horizontal directions of an image region ω and its eigenvalues, by the following equation (b) from the smaller eigenvalue λ min  and a gray scale residual E between the regions after tracking:              G   =       ∑     p   ∈   ω              g        (   p   )                         g        (   p   )       T                 (   a   )               y   =         λ   min     E     .             (   b   )                         
     
     
       2. An image synthesis method for synthesizing a first image and a second image, comprising: 
       the first step of extracting from said first image a plurality of partial images which are effective for tracking by optical flow between said first image and said second image, as feature points;  
       the second step of tracking a point on said second image corresponding to each of said feature points on said first image, on the basis of said optical flow between said two images;  
       the third step of finding a transformation for finding, on the basis of each of said feature points on said first image and the corresponding point on said second image which is found in said second step, a position on said second image corresponding to each of points on said first image, or a position on said first image corresponding to each of points on said second image; and  
       the fourth step of synthesizing said first image and said second image such that the corresponding points on said first image and said second image coincide with each other on the basis of said obtained transformation.  
     
     
       3. The image synthesis method according to  claim 2 , wherein 
       said first step comprises the steps of  
       extracting an overlapped portion of said first image and said second image, and  
       extracting from said overlapped portion with said second image, on said first image, a plurality of said partial images which are effective for tracking by said optical flow between said two images, as said feature points.  
     
     
       4. The image synthesis method according to  claim 3 , wherein 
       in said step of extracting said overlapped portion of said first image and said second image, said overlapped portion of said first image and said second image is extracted on the basis of the Sum of Squared Differences method.  
     
     
       5. The image synthesis method according to  claim 2 , wherein 
       said second step comprises the steps of  
       finding said optical flow from said first image and said second image on the basis of an optical flow estimation method using the hierarchically structured Lucas-Kanade method for interpolating optical flow having low confidence out of optical flows obtained in the respective stages of said optical flow estimation method using optical flow in its surrounding regions, and  
       tracking the point on said second image corresponding to each of said feature points on said first image, on the basis of said obtained optical flow.  
     
     
       6. An image synthesis method in which from three or more images from a first image to a n-th image (n is an integer of not less than three), said first image and said n-th image are synthesized, with said first image as a reference image, comprising: 
       the first step of finding transformations for finding a position on an i-th image corresponding to each of points on an (i+1)-th image, taking i as each of integers from 1 to (n−1);  
       the second step of finding a transformation for finding a position on the first image corresponding to each of points on said n-th image, on the basis of all of said transformations found in said first step; and  
       the third step of synthesizing said first image and said n-th image such that the corresponding points of said first image and said n-th image coincide with each other;  
       wherein said first step repeats the following steps a to c, by updating i by 1 from i=1 up to i=(n−1):  
       step a of extracting from said i-th image a plurality of partial images which are effective for tracking by optical flow between said i-th image and said (i+1)-th image, as feature points;  
       step b of tracking a point on said (i+1)-th image corresponding to each of said feature points on said i-th image on the basis of said optical flow between said two images; and  
       step c of finding a transformation for finding a position on said i-th image corresponding to each of points on said (i+1)-th image on the basis of each of said feature points on said i-th image and the corresponding point on said (i+1)-th image found in said step b.  
     
     
       7. The image synthesis method according to  claim 6 , wherein 
       said step a comprises the steps of  
       extracting an overlapped portion of said i-th image and said (i+1)-th image, and  
       extracting from said overlapped portion with said (i+1)-th image on said i-th image a plurality of said partial images which are effective for tracking by said optical flow between said two images, as said feature points.  
     
     
       8. The image synthesis method according to  claim 7 , wherein 
       in said step of extracting said overlapped portion of said i-th image and said (i+1)-th image, said overlapped portion of said i-th image and said (i+1)-th image is extracted on the basis of the Sum of Squared Differences method.  
     
     
       9. The image synthesis method according to  claim 6 , wherein 
       said step b comprises the steps of  
       finding said optical flow from said i-th image and said (i+1)-th image on the basis of an optical flow estimation method using the hierarchically structured Lucas-Kanade method for interpolating optical flow having low confidence out of optical flows obtained in the respective stages of said optical flow estimation method using optical flow in its surrounding regions, and  
       tracking the point on said (i+1)-th image corresponding to each of said feature points on said i-th image, on the basis of said obtained optical flow.  
     
     
       10. An image synthesis method for synthesizing three or more images from a first image to a n-th image (n is an integer of not less than three), with said first image as a reference image, comprising: 
       the first step of finding transformations for finding a position on an i-th image corresponding to each of points on an (i+1)-th image, taking i as each of integers from 1 to (n−1);  
       the second step of finding, for each of images from a second image to said n-th image, a transformation for finding a position on said first image corresponding to each of points on each of said second to n-th images, on the basis of said transformations found in said first step; and  
       the third step of performing such processes as synthesizing said first image and said second image on the basis of said transformation for finding the position on said first image corresponding to each of the points on said second image and synthesizing said third image and the synthesized image of said first and second images on the basis of said transformation for finding the position on said first image corresponding to each of the points on said third image, and continuing such processes up until said n-th image and the synthesized image of said first to (n−1)-th images are synthesized on the basis of said transformation for finding the position on said first image corresponding to each of the points on said n-th image, thereby to obtain the synthesized image of said first to n-th images,  
       wherein said first step repeats the following steps a to c, by updating i by 1 from i=1 up to i=(n−1):  
       step a of extracting from said i-th image a plurality of partial images which are effective for tracking by optical flow between said i-th image and said (i+1)-th image, as feature points;  
       step b of tracking a point on said (i+1)-th image corresponding to each of said feature points on said i-th image on the basis of said optical flow between said two images; and  
       s step c of finding a transformation for finding a position on said i-th image corresponding to each of points on said (i+1)-th image on the basis of each of said feature points on said i-th image and the corresponding point on said (i+1)-th image found in said step b.  
     
     
       11. The image synthesis method according to  claim 10 , wherein 
       said step a comprises the steps of  
       extracting an overlapped portion of said i-th image and said (i+1)-th image, and  
       extracting from said overlapped portion with said (i+1)-th image on said i-th image a plurality of said partial images which are effective for tracking by said optical flow between said two images, as said feature points.  
     
     
       12. The image synthesis method according to  claim 11 , wherein 
       in said step of extracting said overlapped portion of said i-th image and said (i+1)-th image, said overlapped portion of said i-th image and said (i+1)-th image is extracted on the basis of the Sum of Squared Differences method.  
     
     
       13. The image synthesis method according to  claim 10 , wherein 
       said step b comprises the steps of  
       finding said optical flow from said i-th image and said (i+1)-th image on the basis of an optical flow estimation method using the hierarchically structured Lucas-Kanade method for interpolating optical flow having low confidence out of optical flows obtained in the respective stages of said optical flow estimation method using optical flow in its surrounding regions, and  
       tracking the point on said (i+1)-th image corresponding to each of said feature points on said i-th image, on the basis of said obtained optical flow.  
     
     
       14. An image synthesizer for synthesizing a first image and a second image, comprising: 
       first means for extracting from said first image a plurality of partial images which are effective for tracking by optical flow between said first image and said second image, as feature points;  
       second means for tracking a point on said second image corresponding to each of said feature points on said first image, on the basis of said optical flow between said two images;  
       third means for finding a transformation for finding, on the basis of each of said feature points on said first image and the corresponding point on said second image which is found by said second means, a position on said second image corresponding to each of points on said first image, or a position on said first image corresponding to each of points on said second image; and  
       fourth means for synthesizing said first image and said second image such that the corresponding points on said first image and said second image coincide with each other on the basis of said obtained transformation.  
     
     
       15. The image synthesizer according to  claim 14 , wherein 
       said first means comprises  
       means for extracting an overlapped portion of said first image and said second image, and  
       means for extracting from said overlapped portion with said second image, on said first image, a plurality of said partial images which are effective for tracking by said optical flow between said two images, as said feature points.  
     
     
       16. The image synthesizer according to  claim 15 , wherein 
       said means for extracting said overlapped portion of said first image and said second image extracts said overlapped portion of said first image and said second image on the basis of the Sum of Squared Differences method.  
     
     
       17. The image synthesizer according to  claim 14 , wherein 
       said second means comprises  
       means for finding said optical flow from said first image and said second image on the basis of an optical flow estimation method using the hierarchically structured Lucas-Kanade method for interpolating optical flow having low confidence out of optical flows obtained in the respective stages of said optical flow estimation method using optical flow in its surrounding regions, and  
       means for tracking the point on said second image corresponding to each of said feature points on said first image, on the basis of said obtained optical flow.  
     
     
       18. An image synthesizer in which from three or more images from a first image to a n-th image (n is an integer of not less than three), said first image and said n-th image are synthesized, with said first image as a reference image, comprising: 
       first means for finding transformations for finding a position on an i-th image corresponding to each of points on an (i+1)-th image, taking i as each of integers from 1 to (n−1);  
       second means for finding a transformation for finding a position on said first image corresponding to each of points on said n-th image, on the basis of all of said transformations found by said first means; and  
       third means for synthesizing said first image and said n-th image such that the corresponding points of said first image and said n-th image coincide with each other;  
       wherein said first means repeats the following steps a to c, by updating i by 1 from i=1 up to i=(n−1)  
       step a of extracting from said i-th image a plurality of partial images which are effective for tracking by optical flow between said i-th image and said (i+1)-th image, as feature points;  
       step b of tracking a point on said (i+1)-th image corresponding to each of said feature points on said i-th image on the basis of said optical flow between said two images; and  
       step c of finding a transformation for finding a position on said i-th image corresponding to each of points on said (i+1)-th image on the basis of each of said feature points on said i-th image and the corresponding point on said (i+1)-th image found in said step b.  
     
     
       19. The image synthesizer according to  claim 18 , wherein 
       said step a comprises the steps of  
       extracting an overlapped portion of said i-th image and said (i+1)-th image, and  
       extracting from said overlapped portion with said (i+1)-th image on said i-th image a plurality of said partial images which are effective for tracking by said optical flow between said two images, as said feature points.  
     
     
       20. The image synthesizer according to  claim 19 , wherein 
       in said step of extracting said overlapped portion of said i-th image and said (i+1)-th image, said overlapped portion of said i-th image and said (i+1)-th image is extracted on the basis of the Sum of Squared Differences method.  
     
     
       21. The image synthesizer according to  claim 18 , wherein 
       said step b comprises the steps of  
       finding said optical flow from said i-th image and said (i+1)-th image on the basis of an optical flow estimation method using the hierarchically structured Lucas-Kanade method for interpolating optical flow having low confidence out of optical flows obtained in the respective stages of said optical flow estimation method using optical flow in its surrounding regions, and  
       tracking the point on said (i+1)-th image corresponding to each of said feature points on said i-th image, on the basis of said obtained optical flow.  
     
     
       22. An image synthesizer for synthesizing three or more images from a first image to a n-th image (n is an integer of not less than three), with said first image as a reference image, comprising: 
       first means for finding transformations for finding a position on an i-th image corresponding to each of points on an (i+1)-th image, taking i as each of integers from 1 to (n−1);  
       second means for finding, for each of images from a second image to said n-th image, a transformation for finding a position on said first image corresponding to each of points on each of said second to n-th images, on the basis of said transformations found by said first means; and  
       third means for performing such processes as synthesizing said first image and said second image on the basis of said transformation for finding the position on said first image corresponding to each of the points on said second image and synthesizing said third image and the synthesized image of said first and second images on the basis of said transformation for finding the position on said first image corresponding to each of the points on said third image, and continuing such processes up until said n-th image and the synthesized image of said first to (n−1)-th images are synthesized on the basis of said transformation for finding the position on said first image corresponding to each of the points on said n-th image, thereby to obtain the synthesized image of said first to n-th images,  
       wherein said first means repeats the following steps a to c, by updating i by 1 from i=1 up to i=(n−1):  
       step a of extracting from said i-th image a plurality of partial images which are effective for tracking by optical flow between said i-th image and said (i+1)-th image, as feature points;  
       step b of tracking a point on said (i+1)-th image corresponding to each of said feature points on said i-th image on the basis of said optical flow between said two images; and  
       step c of finding a transformation for finding a position on said i-th image corresponding to each of points on said (i+1)-th image on the basis of each of said feature points on said i-th image and the c corresponding point on said (i+1)-th image found in said step b.  
     
     
       23. The image synthesizer according to  claim 22 , wherein 
       said step a comprises the steps of  
       extracting an overlapped portion of said i-th image and said (i+1)-th image, and  
       extracting from said overlapped portion with said (i+1)-th image on said i-th image a plurality of said partial images which are effective for tracking by said optical flow between said two images, as said feature points.  
     
     
       24. The image synthesizer according to  claim 23 , wherein 
       in said step of extracting said overlapped portion of said i-th image and said (i+1) image, said overlapped portion of said i-th image and said (i+1)-th image is extracted on the basis of the Sum of Squared Differences method.  
     
     
       25. The image synthesizer according to  claim 22 , wherein 
       said step b comprises the steps of  
       finding said optical flow from said i-th image and said (i+1)-th image on the basis of an optical flow estimation method using the hierarchically structured Lucas-Kanade method for interpolating optical flow having low confidence out of optical flows obtained in the respective stages of said optical flow estimation method using optical flow in its surrounding regions, and  
       tracking the point on said (i+1)-th image corresponding to each of said feature points on said i-th image, on the basis of said obtained optical flow.  
     
     
       26. A computer readable recording medium on which an image synthesis program for synthesizing a first image and a second image is recorded, wherein 
       said image synthesis program has a computer execute the following steps of  
       the first step of extracting from said first image a plurality of partial images which are effective for tracking by optical flow between said first image and said second image, as feature points;  
       the second step of tracking a point on said second image corresponding to each of said feature points on said first image, on the basis of said optical flow between said two images;  
       the third step of finding a transformation for finding, on the basis of each of said feature points on said first image and the corresponding point on said second image which is found in said second step, a position on said second image corresponding to each of points on said first image, or a position on said first image corresponding to each of points on said second image; and  
       the fourth step of synthesizing said first image and said second image such that the corresponding points on said first image and said second image coincide with each other on the basis of said obtained transformation.  
     
     
       27. The computer readable recording medium according to  claim 26 , wherein 
       said first step comprises the steps of  
       extracting an overlapped portion of said first image and said second image, and  
       extracting from said overlapped portion with said second image, on said first image, a plurality of said partial images which are effective for tracking by said optical flow between said two images, as said feature points.  
     
     
       28. The computer readable recording medium according to  claim 27 , wherein 
       in said step of extracting said overlapped portion of said first image and said second image, said overlapped portion of said first image and said second image is extracted on the basis of the Sum of Squared Differences method.  
     
     
       29. The computer readable recording medium according to  claim 26 , wherein 
       said second step comprises the steps of  
       finding said optical flow from said first image and said second image on the basis of an optical flow estimation method using the hierarchically structured Lucas-Kanade method for interpolating optical flow having low confidence out of optical flows obtained in the respective stages of said optical flow estimation method using optical flow in its surrounding regions, and  
       tracking the point on said second image corresponding to each of said feature points on said first image, on the basis of said obtained optical flow.  
     
     
       30. A computer readable recording medium on which an image synthesis program for synthesizing, from three or more images from a first image to a n-th image (n is an integer of not less than three), said first image and said n-th image, with said first image as a reference image, is recorded, wherein 
       said image synthesis program has a computer execute the following steps of  
       the first step of finding transformations for finding a position on an i-th image corresponding to each of points on an (i+1)-th image, taking i as each of integers from 1 to (n−1);  
       the second step of finding a transformation for finding a position on said first image corresponding to each of points on said n-th image, on the basis of all of said transformations found in said first step; and  
       the third step of synthesizing said first image and said n-th image such that the corresponding points of said first image and said n-th image coincide with each other, on the basis of said obtained transformation;  
       wherein said first step repeats the following steps a to c, by updating i by 1 from i=1 up to i=(n−1):  
       step a of extracting from said i-th image a plurality of partial images which are effective for tracking by optical flow between said i-th image and said (i+1)-th image, as feature points;  
       step b of tracking a point on said (i+1)-th image corresponding to each of said feature points on said i-th image on the basis of said optical flow between said two images; and  
       step c of finding a transformation for finding a position on said i-th image corresponding to each of points on said (i+1)-th image on the basis of each of said feature points on said i-th image and the corresponding point on said (i+1)-th image found in said step b.  
     
     
       31. The computer readable recording medium according to  claim 30 , wherein 
       said step a comprises the steps of  
       extracting an overlapped portion of said i-th image and said (i+1)-th image, and  
       extracting from said overlapped portion with said (i+1)-th image on said i-th image a plurality of said partial images which are effective for tracking by said optical flow between said two images, as said feature points.  
     
     
       32. The computer readable recording medium according to  claim 31  wherein 
       in said step of extracting said overlapped portion of said i-th image and said (i+1)-th image, said overlapped portion of said i-th image and said (i+1)-th image is extracted on the basis of the Sum of Squared Differences method.  
     
     
       33. The computer readable recording medium according to  claim 30 , wherein 
       said step b comprises the steps of  
       finding said optical flow from said i-th image and said (i+1)-th image on the basis of an optical flow estimation method using the hierarchically structured Lucas-Kanade method for interpolating optical flow having low confidence out of optical flows obtained in the respective stages of said optical flow estimation method using optical flow in its surrounding regions, and  
       tracking the point on said (i+1)-th image corresponding to each of said feature points on said i-th image, on the basis of said obtained optical flow.  
     
     
       34. A computer readable recording medium on which an image synthesis program for synthesizing, from three or more images from a first image to a n-th image (n is an integer of not less than three) said first image and said n-th image , with said first image as a reference image, is recorded, wherein 
       said image synthesis program has a computer execute the following steps of  
       the first step of finding transformations for finding a position on an i-th image corresponding to each of points on an (i+1)-th image, taking i as each of integers from 1 to (n−1);  
       the second step of finding, for each of images from said second image to said n-th image, a transformation for finding a position on said first image corresponding to each of points on each of said second to n-th images, on the basis of said transformations found in said first step; and  
       the third step of performing such processes as synthesizing said first image and said second image on the basis of said transformation for finding the position on said first image corresponding to each of the points on said second image and synthesizing said third image and the synthesized image of said first and second images on the basis of said transformation for finding the position on said first image corresponding to each of the points on said third image, and continuing such processes up until said n-th image and the synthesized image of said first to (n−1)-th images are synthesized on the basis of said transformation for finding the position on said first image corresponding to each of the points on said n-th image, thereby to obtain the synthesized image of said first to n-th images,  
       wherein said first step repeats the following steps a to c,by updating i by 1 from i=1 up to i=(n−1):  
       step a of extracting from said i-th image a plurality of partial images which are effective for tracking by optical flow between said i-th image and said (i+1)-th image, as feature points;  
       step b of tracking a point on said (i+1)-th image corresponding to each of said feature points on said i-th image on the basis of said optical flow between said two images; and  
       step c of finding a transformation for finding a position on said i-th image corresponding to each of points on said (i+1)-th image on the basis of each of said feature points on said i-th image and the corresponding point on said (i+1)-th image found in said step b.  
     
     
       35. The computer readable recording medium according to  claim 34 , wherein 
       said step a comprises the steps of  
       extracting an overlapped portion of said i-th image and said (i+1)-th image, and  
       extracting from said overlapped portion with said (i+1)-th image on said i-th image a plurality of said partial images which are effective for tracking by said optical flow between said two images, as said feature points.  
     
     
       36. The computer readable recording medium according to  claim 35 , wherein 
       in said step of extracting said overlapped portion of said i-th image and said (i+1)-th image, said overlapped portion of said i-th image and said (i+1)-th image is extracted on the basis of the Sum of Squared Differences method.  
     
     
       37. The computer readable recording medium according to  claim 34 , wherein 
       said step b comprises the steps of  
       finding said optical flow from said i-th image and said (i+1)-th image on the basis of an optical flow estimation method using the hierarchically structured Lucas-Kanade method for interpolating optical flow having low confidence out of optical flows obtained in the respective stages of said optical flow estimation method using optical flow in its surrounding regions, and  
       tracking the point on said (i+1)-th image corresponding to each of said feature points on said i-th image, on the basis of said obtained optical flow.  
     
     
       38. A digital camera with a function of synthesizing a first image and a second image, comprising: 
       first means for extracting from said first image a plurality of partial images which are effective for tracking by optical flow between said first image and said second image, as feature points;  
       second means for tracking a point on said second image corresponding to each of said feature points on said first image, on the basis of said optical flow between said two images;  
       third means for finding a transformation for finding, on the basis of each of said feature points on said first image and the corresponding point on said second image which is found by said second means, a position on said second image corresponding to each of points on said first image, or a position on said first image corresponding to each of points on said second image; and  
       fourth means for synthesizing said first image and said second image such that the corresponding points on said first image and said second image coincide with each other, on the basis of said obtained transformation.  
     
     
       39. A printer with a function of synthesizing a first image and a second image, comprising: 
       first means for extracting from said first image a plurality of partial images which are effective for tracking by optical flow between said first image and said second image, as feature points;  
       second means for tracking a point on said second image corresponding to each of said feature points on said first image, on the basis of said optical flow between said two images;  
       third means for finding a transformation for finding, on the basis of each of said feature points on said first image and the corresponding point on said second image which is found by said second means, a position on said second image corresponding to each of points on said first image, or a position on said first image corresponding to each of points on said second image; and  
       fourth means for synthesizing said first image and said second image such that the corresponding points on said first image and said second image coincide with each other, on the basis of said obtained transformation.