Data driven interpolation using geodesic affinity
AssigneeMicrosoft Corporation
InventorsYonatan Wexler, Eyal Ofek
Life of this patent
Estimating the term…
Abstract
Often, information regarding images and/or other data may be incomplete. For example, an image may have depth information associated with a portion of the image, but not the entire image. It may be advantageous to extrapolate the values from the known points to the entire image. Accordingly, a dimensional array representing an image (or other data) may be traversed one or more times to generate an interpolated table. The interpolated table may comprise pixels of unknown value, where a pixel of unknown value may be associated with a number of pixels with known values. In this way, values for pixels may be specified based upon values of pixels having known values.
Claims20
A method for interpolating values of non-seed objects based upon values of seed objects, comprising:
- interpolating a dimensional array comprising non-seed objects and seed objects into an interpolated table comprising non-seed objects, respective non-seed objects in the interpolated table associated with a predetermined number (k) of seed pairings, where respective seed pairings comprise a seed object and a seed cost, the interpolating comprising:
- for respective current objects within the interpolated table:
- adding a cost between a current object and a neighboring object to one or more seed costs within seed pairings of the neighboring object to obtain calculated seed pairings for the neighboring object, where respective calculated seed pairings for the neighboring object comprise a seed object and a calculated seed cost;
- comparing one or more seed costs within seed pairings of the current object with one or more calculated seed costs within the calculated seed pairings of the neighboring object;
- and
- updating the current object based upon the comparison so that the (k) seed pairings for the current object have a desired cumulative seed cost, where the updated (k) seed pairings do not comprise redundant seed objects;
- and
- for non-seed objects within the interpolated table:
- specifying a value for a non-seed object based upon values of seed objects within the updated (k) seed pairings of the non-seed object.
A system for interpolating values of non-seed objects based upon values of seed objects, comprising:
- a table generating component configured to:
- generate an interpolated table comprising non-seed objects based upon seed costs between non-seed objects and seed objects within a dimensional array, respective non-seed objects in the interpolated table associated with a predetermined number (k) of seed pairings comprising seed objects having a desired cumulative seed cost, where the seed pairings do not comprise redundant seed objects;
- and
- a value specifying component configured to:
- for non-seed objects within the interpolated table:
- specify a value for a non-seed object based upon values of seed objects within the seed pairings of the non-seed object.
A method for interpolating colors of unknown color pixels based upon colors of known color pixels, comprising:
- interpolating a dimensional array comprising unknown color pixels and known color pixels into an interpolated table comprising unknown color pixels, respective unknown color pixels in the interpolated table associated with a predetermined number (k) of pixel pairings, where respective pixel pairings comprise a known color pixel and a color cost, the interpolating comprising:
- for respective current pixels within the interpolated table:
- adding a cost between a current pixel and a neighboring pixel to one or more color costs within pixel pairings of the neighboring pixel to obtain calculated pixel pairings for the neighboring pixel, where respective calculated pixel pairings for the neighboring pixel comprise a known color pixel and a calculated color cost;
- comparing one or more color costs within pixel pairings of the current pixel with one or more calculated color costs within the calculated pixel pairings of the neighboring pixel;
- and
- updating the current pixel based upon the comparison so that the (k) pixel pairings for the current pixel have a desired cumulative color cost, where the updated (k) pixel pairings do not comprise redundant known color pixels;
- and
- for unknown color pixels within the interpolated table:
- specifying a color for an unknown color pixel based upon colors of known color pixels within the updated (k) pixel pairings of the unknown color pixel.
Dependencies are inferred from the claim text.