IMAGE BLENDING USING MULTI-SPLINES

• US 20090263045A1
• Filed: 04/17/2008
• Published: 10/22/2009
• Est. Priority Date: 04/17/2008
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Uyttendaele, Matthew T., Szeliski, Richard
• Granted Patent: US 8,189,959 B2
• Time in Patent Office: Days
• US Class Current: 382/284
• CPC Class Codes: G06T 3/4038 Image mosaicing, e.g. composing plane images from plane sub-images

Abstract

Multi-spline image blending technique embodiments are presented which generally employ a separate low-resolution offset field for every image region being blended, rather than a single (piecewise smooth) offset field for all the regions to produce a visually consistent blended image. Each of the individual offset fields is smoothly varying, and so is represented using a low-dimensional spline. A resulting linear system can be rapidly solved because it involves many fewer variables than the number of pixels being blended.

Claims

1. A computer-implemented process for blending image regions, comprising using a computer to perform the following process actions:

associating a separate offset map with each image region being blended;

representing each offset map using a separate low-dimensional spline;

establishing an energy function comprising the summation of a set of terms comprising a separate term defining the difference in blended values of spline control points for each seam pixel and a separate term for each image region defining the blended values of the control points for each region, wherein a seam pixel is a pixel whose location corresponds to the boundary between two adjacent image regions;

solving the system of equation for the spline control point values that minimize the sum of all the terms;

computing a correction term for each pixel in each image region based on the spline control point values exhibited at spline control points and a prescribed 2D tensor product spline basis; and

applying the correction term associated with each pixel to that pixel to produce a blended image from the image regions.

2. The process of claim 1, wherein the image regions are color image regions, and wherein the actions of establishing the energy function, solving the system of equations, computing the correction terms, and applying the correction terms are performed separately for each color channel to produce separate blended color-channel images, and wherein the process further comprises an action of combining the separate blended images for each color channel to produce said blended image.

3. The process of claim 1, wherein the process action of applying the correction term, comprises adding the correction term to the intensity of its associated pixel.

4. The process of claim 1, further comprising the process actions of:

prior to performing the action of associating a separate offset map with each image region,

computing the logarithm of each pixel intensity value, and

assigning the logarithm as the intensity value for its associated pixel location; and

prior to performing the action of computing the correction terms,

exponentiating each spline control point value obtained from the solved equations, and

assigning the exponentiated value as the spline control point value for its associated spline control point grid location, and wherein

the process action of applying the correction term, comprises multiplying the correction term by the intensity of its associated pixel.

5. A computer-implemented process for blending image regions, comprising using a computer to perform the following process actions:

respectively superimposing onto each image region a spline grid comprising spline control points having a prescribed spacing;

identifying all seam pixels among the image regions, wherein a seam pixel is a pixel whose location corresponds to the boundary between two adjacent regions;

for each seam pixel,

computing a horizontal offset value representing the average of the intensity gradients between two adjacent image regions one of which is in the positive horizontal direction from the seam pixel under consideration,

computing a vertical offset value represents the average of the intensity gradients between two adjacent image regions one of which is in the positive vertical direction from the seam pixel under consideration,

computing a horizontal seam matching cost for the seam pixel under consideration which decreases as the horizontal offset value increases,

computing a vertical seam matching cost for the seam pixel under consideration which decreases as the vertical offset value increases;

computing a smoothness cost for each image region based on the variations in intensity between locations in the image region under consideration corresponding to a prescribed number of spline control points;

establishing a seam pixel zero decay cost for each seam pixel and an image region zero decay cost for each image region;

generating an energy function comprising,

for each seam pixel, generating a term wherein a horizontally seam matched intensity term, a vertically seam matched intensity term and a seam pixel zero decay intensity term are summed, and wherein the seam pixel terms are dependent on unknown spline control point intensity values associated with the image regions forming the seam that the seam pixel under consideration belongs to, and

for each image region, generating a term wherein a horizontally smoothed intensity term, a vertically smoothed intensity term and an image region zero decay intensity term are summed, and wherein the image region terms are dependent on unknown spline control point values associated with the image region under consideration;

solving the system of equation for the spline control point values that minimize the sum of all the equations;

computing a correction term for each pixel in each image region based on the spline control point values exhibited at spline control points and a prescribed 2D tensor product spline basis; and

applying the correction term associated with each pixel to that pixel to produce a blended image from the image regions.

6. The process of claim 5, wherein the process action of computing the horizontal offset value comprises an action of computing the average of the difference in intensity of the seam pixel under consideration between two image regions associated with that pixel and the difference in intensity of a pixel immediately adjacent the seam pixel under consideration in the positive horizontal direction between two image regions associated with that adjacent pixel.

7. The process of claim 5, wherein the process action of computing the vertical offset value comprises an action of computing the average of the difference in intensity of the seam pixel under consideration between two image regions associated with that pixel and the difference in intensity of a pixel immediately adjacent the seam pixel under consideration in the positive vertical direction between two image regions associated with that adjacent pixel.

8. The process of claim 5, wherein the process action of computing the horizontal seam matching cost for the seam pixel under consideration comprises an action of computing the reciprocal of one plus the quotient of the horizontal offset value divided by a prescribed factor

9. The process of claim 5, wherein the process action of computing the vertical seam matching cost for the seam pixel under consideration comprises an action of computing the reciprocal of one plus the quotient of the vertical offset value divided by a prescribed factor

10. The process of claim 5, wherein the process action of computing the smoothness cost for each image region, comprises the process action of computing a smoothness cost representative of all the non-seam pixel within an image region under consideration, said per-region smoothness cost being based on the variation in intensity between representative locations in the image region corresponding to four mutually adjacent spline control points.

11. The process of claim 10, wherein the process action of computing said smoothness cost for an image region under consideration comprises an action of computing the sum of the squares of the differences between the intensities associated with said four spline control points.

12. The process of claim 5, wherein the horizontally seam matched intensity term comprises the product of the horizontal seam matching cost and the square of a seam pixel spline control point intensity term, wherein the seam pixel spline control point intensity term comprises the sum of a horizontal intensity term for each spline control point, said horizontal intensity term being a first fraction of the intensity associated with the spline control point under consideration assuming the spline control point is part of a first image region associated with the seam pixel under consideration subtracted from a second fraction of the intensity associated with the spline control point under consideration assuming the spline control point is part of an image region laying immediately adjacent the first image region in the positive horizontal direction, all less the horizontal offset value associated with the seam pixel under consideration.

13. The process of claim 12, wherein the vertically seam matched intensity term comprises the product of the vertical seam matching cost and the square of a seam pixel spline control point intensity term, wherein the seam pixel spline control point intensity term comprises the sum of a vertical intensity term for each spline control point, said vertical intensity term being said first fraction of the intensity associated with the spline control point under consideration assuming the spline control point is part of the first image region associated with the seam pixel under consideration subtracted from a third fraction of the intensity associated with the spline control point under consideration assuming the spline control point is part of an image region laying immediately adjacent the first image region in the positive vertical direction, all less the vertical offset value associated with the seam pixel under consideration.

14. The process of claim 13, wherein the seam pixel zero decay intensity term comprises the product of the seam pixel zero decay cost and the square of a spline control point intensity term, wherein the spline control point intensity term comprises the sum of an intensity term associated with each spline control point, said intensity term being said first fraction of the spline control point under consideration assuming the spline control point is part of the first image region associated with the seam pixel under consideration.

15. The process of claim 14, wherein the first fraction decreases with the distance the spline control point under consideration is from the seam pixel under consideration until it is zero and is computed using a prescribed 2D tensor product spline basis, the second fraction decreases with the distance the spline control point under consideration is from the next pixel located in the positive horizontal direction from the seam pixel under consideration until it is zero and is computed using said prescribed 2D tensor product spline basis, and the third fraction decreases with the distance the spline control point under consideration is from the next pixel located in the positive vertical direction from the seam pixel under consideration until it is zero and is computed using said prescribed 2D tensor product spline basis.

16. The process of claim 5, wherein the horizontal smoothed intensity term comprises the product of the per-region smoothness cost and the square of an image region spline control point horizontal intensity term associated with the spline control point under consideration, wherein the image region spline control point horizontal intensity term comprises the intensity associated with the next spline control point located in the positive horizontal direction from the spline control point under consideration less the intensity associated with the spline control point under consideration.

17. The process of claim 5, wherein the vertical smoothed intensity term comprises the product of the per-region smoothness cost and the square of an image region spline control point vertical intensity term associated with the spline control point under consideration, wherein the image region spline control point vertical intensity term comprises the intensity associated with next spline control point located in the positive vertical direction from the spline control point under consideration less the intensity associated with the spline control point under consideration.

18. The process of claim 5, wherein the image region zero decay intensity value term comprises the product of the image region zero decay cost, the square of the intensity associated with the spline control point under consideration and the square of said prescribed spacing.

19. The process of claim 5, wherein the process action of superimposing a spline grid onto each image region, comprises an action of aligning the spline grids with each other.

20. A computer-implemented process for blending image regions, comprising using a computer to perform the following process actions:

respectively superimposing onto each image region a spline grid comprising spline control points having a prescribed spacing S;

identifying all seam pixels among the image regions, wherein a seam pixel is a pixel whose location corresponds to the boundary between two adjacent regions;

for each seam pixel,

computing a horizontal offset value g_i,j<sup>−

x</sup> representing the average of the intensity gradients between two adjacent image regions one of which is in the positive horizontal direction from the seam pixel under consideration, where i,j refer to coordinates of the seam pixel,

computing a vertical offset value g_i,j<sup>−

y</sup> represents the average of the intensity gradients between two adjacent image regions one of which is in the positive vertical direction from the seam pixel under consideration,

computing a horizontal seam matching cost s_i,j^x for the seam pixel under consideration which decreases as the horizontal offset value increases,

computing a vertical seam matching cost s_i,j^y for the seam pixel under consideration which decreases as the vertical offset value increases;

computing a smoothness cost s for each image region based on the variations in intensity between locations in the image region under consideration corresponding to a prescribed number of spline control points;

establishing a seam pixel zero decay cost w_i,j for each seam pixel and an image region zero decay cost w for each image region;

generating a sum of squared terms comprising,

a separate term for each seam pixel in the form of,

${s_{i,j}^x<br><br>\left[\begin{array}{c}\underset{k,m}{\sum <br><br>}<br><br>B<br><br>\left(i+1-\mathrm{kS},j-\mathrm{mS}\right)<br><br>c_{k,m}^{l_{i+1,j}}-\\ B<br><br>\left(i-\mathrm{kS},j-\mathrm{mS}\right)<br><br>c_{k,m}^{l_{i,j}}-g_{i,j}^{~x}\end{array}\right]}^2+{s_{i,j}^x<br><br>\left[\begin{array}{c}\underset{k,m}{\sum <br><br>}<br><br>B<br><br>\left(i-\mathrm{kS},j+1-\mathrm{mS}\right)<br><br>c_{k,m}^{l_{i,j+1}}-\\ B<br><br>\left(i-\mathrm{kS},j-\mathrm{mS}\right)<br><br>c_{k,m}^{l_{i,j}}-g_{i,j}^{~y}\end{array}\right]}^2+{w_{i,j}\left[\underset{k,m}{\sum <br><br>}<br><br>B<br><br>\left(i-\mathrm{kS},j-\mathrm{mS}\right)<br><br>c_{k,m}^{l_{i,j}}\right]}^2$

where B(i+1−

kS,j−

mS), B(i−

kS,j−

mS) and B(i−

kS,j+1−

mS) represent various values of a 2D tensor product spline basis, k and m refer to the horizontal and vertical coordinates of the spline control points, c_k,m^li,j is the intensity exhibited at a spline control point having coordinates k,m if the point is assumed part of a first image region associated with the pixel at coordinates i,j, c_k,m^li+1,j is the intensity exhibited at a spline control point having coordinates k,m if the point is assumed part of an image region laying immediately adjacent the first image region in the positive horizontal direction, c_k,m^li,j+1 is the intensity exhibited at a spline control point having coordinates k,m if the point is assumed part of an image region laying immediately adjacent the first image region in the positive vertical direction, and

a single term for each image region in the form of,

$\underset{k,m}{\sum <br><br>}<br><br>{s<br><br>\left[c_{k+1,m}-c_{k,m}\right]}^2+{s<br><br>\left[c_{k,m+1}-c_{k,m}\right]}^2+S^2<br><br>{w<br><br>\left[c_{k,m}\right]}^2,$

where c_k,m is the intensity exhibited by a spline control point overlying the image region under consideration and having coordinates k,m, c_k+1,m is the intensity exhibited by a spline control point overlying the image region under consideration and having coordinates k+1,m, and c_k,m+1 is the intensity exhibited by a spline control point overlying the image region under consideration and having coordinates k,m+1;

solving the system of equation for the spline control point values that minimize the sum of all these terms;

computing a correction term h_i,j^l for each pixel ij in each image region l based on the spline control point values c_k,m^l exhibited at spline control points having coordinates k,m and the a 2D tensor product spline basis B(i−

kS,j−

mS) using the equation

$h_{i,j}^l=\underset{k<br><br><br><br>m}{\sum <br><br>}<br><br>B<br><br>\left(i-\mathrm{kS},j-\mathrm{mS}\right)<br><br>c_{k,m}^l;<br><br>\mathrm{and}$

applying the correction term associated with each pixel to that pixel to produce a blended image from the image regions.