Methods and machine-readable mediums are disclosed for warping overlapping images. In one embodiment, the method comprises selecting a first set of points in a first image that are located in an overlap region of the first image and the second image, determining a set of tie points in the second image, each tie point correlating to a point in the first set, determining a second set of points, each point in the second set located at a position in the overlap region between a point in the first set and a tie point correlated to the point in the first set, and warping the first image and the second image by applying an algorithm using the second set of points, the algorithm to reposition at least a portion of the points in the first image and at least a portion of the points in the second image.
1. A method comprising:
selecting a first set of points in a first image, the first set of points being located in an overlap region of the first image and a second image;
determining a set of tie points in the second image, each tie point correlating to a point in the first set;
determining a second set of points, each point in the second set being located at a position in the overlap region between a point in the first set and a tie point correlated to the point in the first set; and
warping the first image and the second image by applying an algorithm using the second set of points, the algorithm to reposition at least a portion of points in the first image and at least a portion of points in the second image, and wherein applying an algorithm comprises calculating a Delaunay triangulation of the second set of points.
2. The method of claim 1 , wherein applying an algorithm further comprises using the Delaunay triangulation to calculate a linear polynomial warp for the first image and a linear polynomial warp for the second image.
3. The method of claim 1 , further comprising before calculating the Delaunay triangulation, adding first outlying points and second outlying points to the second set of points, the first outlying points located in a non-overlap region of the first image and the second outlying points located in a non-overlap region of the second image.
4. A method comprising:
selecting a first set of points in a first image the first set of points being located in an overlap region of the first image and a second image;
determining a set of tie points in the second image, each tie point correlating to a point in the first set, and wherein determining the set of tie points comprises, for each point in the first set:
selecting a patch comprising the point and a set of neighboring points located within a first predetermined distance from the point;
selecting a first potential tie point in the second image corresponding to the same location as the point;
determining a set of potential tie points in the second image, the set of potential tie points including the first potential tie point and one or more additional potential tie points located within a second predetermined distance surrounding the first potential tie point;
for each potential tie point, calculating a correlation between points in the patch and the potential tie point and neighboring points located in the second image within the first predetermined distance from the potential tie point; and
if a good correlation exists, selecting a tie point corresponding to a potential tie point with a best correlation; and
after calculating the correlation:
analyzing the correlations for the potential tie points; and
if a plurality of similar correlations exceed a predefined threshold for a plurality of potential tie points, determining the good correlation does not exist; and
determining a second set of points, each point in the second set being located at a position in the overlap region between a point in the first set and a tie point correlated to the point in the first set; and
warping the first image and the second image by applying an algorithm using the second set of points, the algorithm to reposition at least a portion of points in the first image and at least a portion of points in the second image.
5. The method of claim 4 , wherein the plurality of potential tie points are positioned linearly to each other.
6. The method of claim 4 , wherein the plurality of potential tie points are randomly distributed.
7. A method comprising:
selecting a first set of points in a first image, the first set of points being located in an overlap region of the first image and a second image;
determining a set of tie points in the second image, each tie point correlating to a point in the first set, wherein determining the set of tie points comprises, for each point in the first set:
selecting a patch comprising the point and a set of neighboring points located within a first predetermined distance from the point;
before selecting a first potential tie point:
creating a histogram of frequencies of point intensities in the patch;
calculating a bimodal coefficient for the histogram; and
if the bimodal coefficient indicates a bimodal distribution of the histogram calculating a mean point intensity value for the patch, and removing the point from the first set if the mean point intensity value is within a predefined shadow range; and
selecting the first potential tie point in the second image corresponding to the same location as the point;
determining a set of potential tie points in the second image, the set of potential tie points including the first potential tie point and one or more additional potential tie points located within a second predetermined distance surrounding the first potential tie point;
for each potential tie point, calculating a correlation between points in the patch and the potential tie point and neighboring points located in the second image within the first predetermined distance from the potential tie point; and
if a good correlation exists selecting a tie point corresponding to a potential tie point with a best correlation; and
determining a second set of points, each point in the second set being located at a position in the overlap region between a point in the first set and a tie point correlated to the point in the first set; and
warping the first image and the second image by a applying an algorithm using the second set of points, the algorithm to reposition at least a portion of points in the first image and at least a portion of points in the second image.
8. A method comprising:
selecting a first set of points in a first image, the first set of points being located in an overlap region of the first image and a second image;
determining a set of tie points in the second image, each tie point correlating to a point in the first set, wherein, determining the set of ties points comprising, for each point in the first set:
selecting a patch comprising the point and a set of neighboring points located within a first predetermined distance from the point;
before selecting a first potential tie point, reducing a resolution of the patch b a resolution parameter and reducing a resolution of at least a portion of the second image h the resolution parameter;
selecting the first potential tie point in the second image corresponding to the same location as the point;
determining a set of potential tie points in the second image, the set of potential tie points including the first potential tie point and one or more additional potential tie points located within a second predetermined distance surrounding the first potential tie point;
for each potential tie point, calculating a correlation between points in the patch and the potential tie point and neighboring points located in the second image within the first predetermined distance from the potential tie point; and
if a good correlation exists:
selecting a tie point corresponding to a potential tie point with the best correlation, and then;
restoring the resolution of the patch;
restoring the resolution of the second image;
setting the second predetermined distance equal to two times the size of the reduced resolution parameter; and
repeating determining the set of potential tie points, calculating the correlation, and selecting the tie point; and
determining a second set of points, each point in the second set being located at a position in the overlap region between a point in the first set and a tie point correlated to the point in the first set; and
warping the first image and the second image by applying an algorithm using the second set of points the algorithm to reposition at least a portion of points in the first image and at least a portion of points in the second image.
9. A method comprising:
selecting a first set of points in a first image, the first set of points being located in an overlap region of the first image and a second image;
determining a set of tie points in the second image, each tie point correlating to a point in the first set;
before determining a second set of points:
analyzing a plurality of neighboring tie points wherein the analyzing comprises:
calculating an average vertical displacement and an average horizontal displacement between the neighboring tie points and points in the first set correlated to the neighboring tie points;
determining the tie point is not similar to the neighboring tie points if the difference between the average horizontal displacement and the horizontal displacement between the tie point and a point in the first set correlated to the tie point exceeds a predetermined threshold; and
determining the tie point is not similar to the neighboring tie points if the difference between the average vertical displacement and the point in the first set correlated to the tie point exceeds the predetermined threshold; and
if the tie point is not similar to the neighboring tie points, removing the tie point from the set of tie points and removing the point in the first set correlated to the tie point from the first set; and
determining the second set of points, each point in the second set being located at a position in the overlap region between a point in the first set and a tie point correlated to the point in the first set; and
warping the first image and the second image by applying an algorithm using the second set of points, the algorithm to reposition at least a portion of points in the first image and at least a portion of points in the second image.
10. A method comprising:
selecting a first set of points in a first image, the first set of points being located in an overlap region of the first image and a second image;
determining a set of tie points in the second image, each tie point correlating to a point in the first set;
before determining a second set of points:
analyzing a plurality of neighboring tie points wherein the analyzing comprises:
calculating an average angular variance between the neighboring tie points and points in the first set correlated to the neighboring tie points;
calculating a magnitude of the displacement between the tie point and a point in the first set correlated to the tie point;
using the average angular variance and the magnitude to compare the tie point to the neighboring tie points; and
if the tie point is not similar to the neighboring tie points, removing the tie point from the set of tie points and removing the point in the first set correlated to the tie point from the first set; and
determining the second set of points, each point in the second set being located at a position in the overlap region between a point in the first set and a tie point correlated to the point in the first set; and
warping the first image and the second image by applying an algorithm using the second set of points, the algorithm to reposition at least a portion of points in the first image and at least a portion of points in the second image.
11. A method comprising:
selecting a first set of points in a first image, the first set of points located in an overlap region of the first image and the second image;
determining a set of tie points in the second image, each tie point correlating to a point in the first set;
determining a second set of points, each point in the second set located at a position in the overlap region halfway between the point in the first set and a tie point correlated to the point in the first set;
adding first outlying points located in the non-overlap region of the first image to the second set of points, the first outlying points located within a predetermined distance from the overlap region;
adding second outlying points located in the non-overlap region of the second image to the second set of points, the second outlying points located within the predetermined distance from the overlap region;
calculating a Delaunay triangulation of the second set of points;
using the Delaunay triangulation to calculate a warp for the first image and a warp for the second image;
using the warp to reposition points in the first image located in the overlap region and within the predetermined distance from the overlap region; and
using the warp to reposition points in the second image located in the overlap region and within the predetermined distance from the overlap region.
12. The method of claim 11 , wherein the warps comprises linear polynomial warps.
13. The method of claim 11 , wherein determining the set of tie points comprises, for each point in the first set:
selecting a patch comprising the point and a set of neighboring points located within a first predetermined distance from the point;
selecting a first potential tie point in the second image corresponding to the same location as the point;
determining a set of potential tie points in the second image, the set of potential tie points including the first potential tie point and one or more additional potential tie points located within a second predetermined distance surrounding the potential tie point; for each potential tie point, calculating a correlation between points in the patch and the potential tie point and neighboring points located in the second image within the first predetermined distance from the potential tie point; and
if a good correlation exists, selecting a tie point corresponding to a potential tie point with the best correlation.
14. The method of claim 13 , further comprising before selecting a first potential tie point, reducing the resolution of the patch by a resolution parameter and reducing the resolution of at least a portion of the second image by the resolution parameter.
15. The method of claim 14 , further comprising if a good correlation exists, after selecting the tie point:
restoring the resolution of the patch;
restoring the resolution of the second image;
setting the second predetermined distance equal to two times the size of the reduced resolution parameter; and
repeating determining the set of potential tie points, calculating the correlation, and selecting the tie point.
16. A method comprising the steps of:
a step for selecting a first set of points in a first image, the first set of points being located in an overlap region of the first image and a second image;
for each point in the first set:
a step for selecting a patch comprising the point and a set neighboring points located within a first predetermined distance from the point;
before a step for selecting a first potential tie point, a step for reducing a resolution of the patch by a resolution parameter and a step for reducing a resolution of at least a portion of the second image by the resolution parameter;
the step for selecting the first potential tie point in the second image corresponding to the same location as the point;
a step for determining a set of potential tie points in the second image, the set of potential tie points including the first potential tie point and one or more additional potential tie points located within a second predetermined distance surrounding the first potential tie point;
for each potential tie point, a step for calculating a correlation between points in the patch and the potential tie point and neighboring points located in the second image within the first predetermined distance from the potential tie point; and
if a good correlation exists, a step for selecting a tie point corresponding to a potential tie point with a best correlation, and then
a step for restoring the resolution of the patch;
a step for restoring the resolution of the second image;
a step for setting the second predetermined distance equal to two times the size of the reduced resolution parameter; and
a step for repeating the steps for determining the set of potential tie points, calculating the correlation, and selecting the tie point; and
a step for determining a set of tie points in the second image, each tie point correlating to a point in the first set;
a step for determining a second set of points, each point in the second set being located at a position in the overlap region between a point in the first set and a tie point correlated to the point in the first set; and
a step for warping the first image and the second image by applying an algorithm using the second set of points, the algorithm to reposition at least a portion of points in the first image and at least a portion of points in the second image.
17. One or more machine-readable mediums having stored thereon sequences of instructions, which, when executed by a machine, cause the machine to perform the actions of:
selecting a first set of points in a first image, the first set of points being located in an overlap region of the first image and a second image;
determining a set of tie points in the second image, each tie point correlating to a point in the first set;
determining a second set of points, each point in the second set being located at a position in the overlap region between a point in the first set and a tie point correlated to the point in the first set; and
warping the first image and the second image by applying an algorithm using the second set of points, the algorithm to reposition at least a portion of points in the first image and at least a portion of points in the second image, wherein applying an algorithm comprises instructions, which when executed by the machine, cause the machine to perform the actions of calculating a Delaunay triangulation of the second set of points and using the Delaunay triangulation to calculate a linear polynomial warp for the first image and a linear polynomial warp for the second image.
18. One or more machine-readable mediums having stored thereon sequences of instructions, which, when executed by a machine, cause the machine to perform the actions of:
selecting a first set of points in a first image, the first set of points being located in an overlap region of the first image and a second image;
determining a set of tie points in the second image, each tie point correlated to a point in the first set;
selecting a patch comprising the point and a set of neighboring points located within a first predetermined distance from the point;
before selecting a first potential tie point, reducing a resolution of the patch by a resolution parameter and reducing a resolution of at least a portion of the second image by the resolution parameter;
selecting the first potential tie point in the second image, corresponding to the same location as the point;
determining a set of potential tie points in the second image, the set of potential tie points include the first potential tie point and one or more additional potential tie points located within a second predetermined distance surrounding the potential tie point;
for each potential tie point, calculating a correlation between points in the patch and thy potential tie point and neighboring points located in the second image within the first predetermined distance from the potential tie point; and
if good correlation exists selecting a tie point corresponding to a potential tie point with a best correlation;
after selecting the tie point, restoring the resolution of the patch;
restoring the resolution of the second image;
setting the second predetermined distance equal to two times the size of the reduced resolution parameter; and
using the original resolution and the second predetermined distance to repeat determining the set of potential tie points, calculating the correlation, and selecting the tie point; and
determining a second set of points, each point in the second set being located at a position in the overlap region between a point in the first set and a tie point correlated to the point in the first set; and
warping the first image and the second image by applying an algorithm using the second set of points, the algorithm to reposition at least a portion of points in the first image and at least a portion of points in the second image.