Patent US5909251A successfully refreshed from Google Patents.
US5909251A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Image frame fusion by velocity estimation using region merging
Assignee: Cognitech Inc
•
Filing: 1997-04-10
•
Granted: 1999-06-01
•
Expires: 2017-04-10
Abstract
Abstract A process for performing image frame fusion on a pixel-by-pixel basis by estimating velocities and occlusions between at least two image frames of a sequence of frames. For each pixel, the possible matchings are those that minimize changes in a selected parameter of the image (generally the grey-level). The process uses a region-growing procedure to reduce the number of possible matchings for each pixel. The output is a decomposition of the images into regions in which pixels move with the same model of velocity or are all occluded. The process includes a multi-scale description of velocities between two images, a multi-scale segmentation of the images into regions having different motion, a correcting term for sampling errors, sub-pixel motion errors and an occlusion estimation step. A preferred embodiment employs pyramidal calculations.
Inventors
- 👤 Frederic Guichard
- 👤 Leonid I. Rudin
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-10 02:21
CPC Classifications
H; H04; H04N; H04N19/00; H04N19/20; H04N19/23; G; G06; G06T; G06T7/00; G06T7/20; G06T7/215; G06V; G06V10/00; G06V10/20; G06V10/26; G06V10/267; H04N19/50; H04N19/503; H04N19/51; H04N19/537
Claims Analysis
Total Claims: 27
Claim 1
Independent Claim
262 words
A process for obtaining information from at least two image frames, each of said frames comprising an array of pixels, each pixel having an amplitude, one of said two frames being designated as a reference frame and the other being a non-reference frame, said process comprising: (1) defining a set of velocities with which the motion of pixels between said two frames may be modeled; (2) dividing each one of said two frames into plural regions; (3) determining an error for each one of at least some of said velocities by carrying out the following steps for each one of said regions and for each union of pairs of said regions: (A) mapping each pixel of said non-reference frame into said reference frame in accordance with the one velocity, (B) computing an error amount which is a function of a difference in pixel amplitude attributable to said mapping; (C) designating a minimum one of the error amounts computed for said velocities as the error for said one velocity, whereby a respective error is associated with each of said regions and with each union of pairs of said regions without regard to velocity; and (4) merging qualified ones of said regions by the following steps: (A) computing for each pair of regions a merging scale which depends upon a gain comprising a function of (a) the sum of the errors of each pair of regions and (b) the error of the union of said pair of regions; (B) merging each pair of said regions for which said merging scale meets a predetermined criteria.
Claim 2
Dependent Claim
262 words
A process for obtaining information from at least two image frames, each of said frames comprising an array of pixels, each pixel having an amplitude, one of said two frames being designated as a reference frame and the other being a non-reference frame, said process comprising: (1) defining a set of velocities with which the motion of pixels between said two frames may be modeled; (2) dividing each one of said two frames into plural regions; (3) determining an error for each one of at least some of said velocities by carrying out the following steps for each one of said regions and for each union of pairs of said regions: (A) mapping each pixel of said non-reference frame into said reference frame in accordance with the one velocity, (B) computing an error amount which is a function of a difference in pixel amplitude attributable to said mapping; (C) designating a minimum one of the error amounts computed for said velocities as the error for said one velocity, whereby a respective error is associated with each of said regions and with each union of pairs of said regions without regard to velocity; and (4) merging qualified ones of said regions by the following steps: (A) computing for each pair of regions a merging scale which depends upon a gain comprising a function of (a) the sum of the errors of each pair of regions and (b) the error of the union of said pair of regions; (B) merging each pair of said regions for which said merging scale meets a predetermined criteria.
Claim 3
Dependent Claim
47 words
The process of claim 1 wherein said merging scale further depends upon a cost comprising a function of (a) the sum of the lengths of the boundaries of each pair of regions and (b) the length of the boundary of the union of said pair of regions.
Claim 4
Dependent Claim
32 words
The process of claim 1 wherein the step of determining an error for each one of at least some of said velocities comprises determining an error for each one of said velocities.
Claim 5
Dependent Claim
74 words
The process of claim 1 further comprising, after the step of merging: erasing the individual pairs of regions which have been merged and defining their unions as individual regions; and repeating said steps of (a) computing an error for each one of at least some of said velocities, (b) computing a merging scale and merging each pair of regions for which the merging scale meets said criteria, whereby said process comprises plural repetitive iterations.
Claim 6
Dependent Claim
62 words
The process of claim 4 wherein the step of determining an error for each one of at least some of said velocities comprises determining said error for a limited set of said velocities, said limited set of said velocities corresponding to those velocities associated with the N smallest errors computed during a prior iteration of said process, wherein N is an integer.
Claim 7
Dependent Claim
113 words
The process of claim 5 wherein each limited set of velocites associated with the N smallest errors is different for different regions, and wherein said step of determining an error comprises: designating as the maximum error for a given region the largest error computed for that region in any prior iteration of said process; and wherein the step of computing said merging scale comprises determining for each pair of regions whether a velocity included in said limited velocity set of one of said regions is not included in the limited velocity set of the other of said pair of regions, and assigning as the corresponding error for said other region said maximum error.
Claim 8
Dependent Claim
58 words
The process of claim 1 wherein said mapping comprises computing a new pixel amplitude in accordance with a weighted average of pixel amplitudes mapped into said reference frame, wherein the weight of each pixel amplitude mapped into said reference frame is a decreasing function of the mapped pixel's distance from a given pixel location in said reference frame.
Claim 9
Dependent Claim
195 words
The process of claim 1 wherein said mapping step of mapping pixels from said non-reference frame to said reference frame is a forward mapping, said process further comprising determining which ones of said pixels are occluded by carrying out the following steps: (I) determining which pixels were not matched from said non-reference frame to said reference frame by said merging step following said forward mapping step and removing said pixels not matched from said reference frame; (II) performing said step of determining an error and said step of merging, except that said mapping step comprises a backward mapping of mapping from said reference frame to said non-reference frame, said backward mapping step employing a version of said reference frame in which said pixels not matched have been removed; (III) determining which pixels were not matched from said reference frame to said non-reference frame by said merging step following said backward mapping step and removing said pixels not matched from said non-reference frame; (IV) comparing the pixels remaining in said reference frame with the pixels remaining in said non-reference frame, and repeating steps I, II and III if there is a difference beyond a predetermined threshold.
Claim 10
Dependent Claim
48 words
The process of claim 8 further comprising: assigning a velocity to each remaining pixel in said non-reference frame; adding the remaining pixels of said non-reference frame to said reference frame in accordance with the velocity assigned to each pixel of said non-reference frame to produce an enhanced frame.
Claim 11
Dependent Claim
19 words
The process of claim 9 further comprising deblurring the image of said enhanced frame to produce a super frame.
Claim 12
Dependent Claim
20 words
The process of claim 1 wherein said dividing step initializes said regions so that each pixel is an individual region.
Claim 13
Dependent Claim
27 words
The process of claim 1 wherein said velocities comprise at least one of: the set of translational velocities, the set of rotational velocities, the set of zooms.
Claim 14
Dependent Claim
20 words
The process of claim 1 wherein said unions of pairs of regions constitute unions of pairs of adjacent regions only.
Claim 15
Dependent Claim
40 words
The process of claim 2 wherein said merging scale is computed as a ratio obtained by dividing said cost by said gain, and wherein said predetermined criteria comprises a maximum scalar value of said ratio above which merging is disallowed.
Claim 16
Dependent Claim
35 words
The process of claim 14 wherein said scalar value is selected in a range between an upper limit at which the entire image is merged and a lower limit at which no pixels are merged.
Claim 17
Dependent Claim
42 words
The process of claim 4 further comprising defining said set of velocities as a simple set during the first one of said iterations of said process, and supplementing said set of velocities with additional velocities as the size of said regions grows.
Claim 18
Dependent Claim
31 words
The process of claim 16 wherein said simple set comprises the set of translational velocities, and said additional velocities comprise the set of rotational velocities and the set of zoom velocities.
Claim 19
Dependent Claim
82 words
The process of claim 10 wherein said reference and non-reference frames lie in a moving sequence of frames depicting an image having motion, and said process further comprising designating one of said sequence of frames as said reference frame and successively designating others of said sequence of frames as said non-reference frame, and performing all of the foregoing steps for each one of the successive designations of said non-reference frame, whereby said superframe contains information from all the frames of said sequence.
Claim 20
Dependent Claim
48 words
The process of claim 18 further comprising designating successive ones of said sequence of frames as said reference frame and repeating all of said foregoing steps for each designation of said reference frame so that a super frame is constructed for each one of said sequence of frames.
Claim 21
Dependent Claim
30 words
The process of claim 9 wherein the step of assigning a velocity to each remaining pixel comprises selecting the velocity for the region of that pixel having the minimum error.
Claim 22
Independent Claim
199 words
A method of processing at least two image frames each divisible into similar sets of regions, wherein one of said frames is a reference frame and the other is a non-reference frame, said method of processing comprising: determining an error based upon discrepancy in pixel amplitude for each one of at least some of a set of velocities for modeling pixel motion between frames for each one of said regions and for each union of pairs of said regions, and wherein said determining an error further comprises: (A) mapping each pixel of said non-reference frame into said reference frame in accordance with the one velocity, (B) computing an error amount which is a function of a difference in pixel amplitude attributable to said mapping; (C) designating a minimum one of the error amounts computed for said velocities as the error for said one velocity, whereby a respective error is associated with each of said regions and with each union of pairs of said regions without regard to velocity; and, merging a pair of said regions whose union tends to have a smaller function of said error than the sum of similar functions of the separate regions of the pair.
Claim 23
Independent Claim
199 words
A method of processing at least two image frames each divisible into similar sets of regions, wherein one of said frames is a reference frame and the other is a non-reference frame, said method of processing comprising: determining an error based upon discrepancy in pixel amplitude for each one of at least some of a set of velocities for modeling pixel motion between frames for each one of said regions and for each union of pairs of said regions, and wherein said determining an error further comprises: (A) mapping each pixel of said non-reference frame into said reference frame in accordance with the one velocity, (B) computing an error amount which is a function of a difference in pixel amplitude attributable to said mapping; (C) designating a minimum one of the error amounts computed for said velocities as the error for said one velocity, whereby a respective error is associated with each of said regions and with each union of pairs of said regions without regard to velocity; and, merging a pair of said regions whose union tends to have a smaller function of said error than the sum of similar functions of the separate regions of the pair.
Claim 24
Independent Claim
154 words
A method of processing at least two image frames each divisible into similar sets of regions, comprising: determining an error based upon discrepancy in pixel amplitude for each one of at least some of a set of velocities for modeling pixel motion between frames for each one of said regions and for each union of pairs of said regions; and, merging a pair of said regions whose union tends to have a smaller function of said error that the sum of similar functions of the separate regions of the pair, and wherein said merging further comprises: (A) computing for each pair of regions a merging scale which depends upon a gain comprising a function of (a) the sum of the errors of each pair of regions and (b) the error of the union of said pair of regions; (B) merging each pair of said regions for which said merging scale meets a predetermined criteria.
Claim 25
Independent Claim
154 words
A method of processing at least two image frames each divisible into similar sets of regions, comprising: determining an error based upon discrepancy in pixel amplitude for each one of at least some of a set of velocities for modeling pixel motion between frames for each one of said regions and for each union of pairs of said regions; and, merging a pair of said regions whose union tends to have a smaller function of said error that the sum of similar functions of the separate regions of the pair, and wherein said merging further comprises: (A) computing for each pair of regions a merging scale which depends upon a gain comprising a function of (a) the sum of the errors of each pair of regions and (b) the error of the union of said pair of regions; (B) merging each pair of said regions for which said merging scale meets a predetermined criteria.
Claim 26
Independent Claim
292 words
A method of processing at least two image frames each divisible into similar sets of regions, comprising: determining an error based upon discrepancy in pixel amplitude for each one of at least some of a set of velocities for modeling pixel motion between frames for each one of said regions and for each union of pairs of said regions, and wherein the step of determining an error further includes: a forward mapping step of mapping pixels from a non-reference one of said frames to a reference one of said frames, said process further comprising determining which ones of said pixels are occluded by carrying out the following steps: (I) determining which pixels were not matched from said non-reference frame to said reference frame by said merging step following said forward mapping step and removing said pixels not matched from said reference frame; (II) performing said step of determining an error and said step of merging, except that said mapping step comprises a backward mapping of mapping from said reference frame to said non-reference frame, said backward mapping step employing a version of said reference frame in which said pixels not matched have been removed; (III) determining which pixels were not matched from said reference frame to said non-reference frame by said merging step following said backward mapping step and removing said pixels not matched from said non-reference frame; (IV) comparing the pixels remaining in said reference frame with the pixels remaining in said non-reference frame, and repeating steps I, II and III if there is a difference beyond a predetermined threshold; and merging a pair of said regions whose union tends to have a smaller function of said error than the sum of similar functions of the separate regions of the pair.
Claim 27
Independent Claim
292 words
A method of processing at least two image frames each divisible into similar sets of regions, comprising: determining an error based upon discrepancy in pixel amplitude for each one of at least some of a set of velocities for modeling pixel motion between frames for each one of said regions and for each union of pairs of said regions, and wherein the step of determining an error further includes: a forward mapping step of mapping pixels from a non-reference one of said frames to a reference one of said frames, said process further comprising determining which ones of said pixels are occluded by carrying out the following steps: (I) determining which pixels were not matched from said non-reference frame to said reference frame by said merging step following said forward mapping step and removing said pixels not matched from said reference frame; (II) performing said step of determining an error and said step of merging, except that said mapping step comprises a backward mapping of mapping from said reference frame to said non-reference frame, said backward mapping step employing a version of said reference frame in which said pixels not matched have been removed; (III) determining which pixels were not matched from said reference frame to said non-reference frame by said merging step following said backward mapping step and removing said pixels not matched from said non-reference frame; (IV) comparing the pixels remaining in said reference frame with the pixels remaining in said non-reference frame, and repeating steps I, II and III if there is a difference beyond a predetermined threshold; and merging a pair of said regions whose union tends to have a smaller function of said error than the sum of similar functions of the separate regions of the pair.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2002-05-31 | 2002-11-30 | 2003-06-01 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-05-31 | 2006-11-30 | 2007-06-01 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-05-31 | 2010-11-30 | 2011-06-01 | $7700.00 | Window Closed / Lapsed |