Parallelized generation of substantially seamless image mosaics

• US 8,970,619 B2
• Filed: 11/24/2009
• Issued: 03/03/2015
• Est. Priority Date: 11/24/2009
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Lepikhin, Maksim
• Primary Examiner(s): McDowell, Jr., Maurice L
• Assistant Examiner(s): Zhai, Kyle
• Application Number:
  US12/625,260
• Publication Number:
  US 20110122145A1
• Time in Patent Office: 1,925 Days
• Field of Search: 345/589, 345/643, 345/423, 345/629
• US Class Current: 345/629
• CPC Class Codes: G06T 11/60 Editing figures and text; Combining figures or text
• CPC Class Codes: G06T 2200/32 involving image mosaicing
• CPC Class Codes: G09G 2340/12 Overlay of images, i.e. displayed pixel being the result of switching between the corresponding input pixels
• CPC Class Codes: G09G 2360/16 Calculation or use of calculated indices related to luminance levels in display data
• CPC Class Codes: G09G 5/02 characterised by the way in which colour is displayed details of colour display specific for CRTs G09G1/28; specific for flat matrix panels other than liquid crystal displays G09G3/2003; specific for liquid crystal displays G09G3/3607
• CPC Class Codes: G09G 5/14 Display of multiple viewports

Abstract

Many computing services incorporate large mosaics of geo-located images. For example, a user may access and interact with a digital image map comprising thousands of digital images mosaiced together. It may be advantageous to parallelize mosaic creation by splitting the mosaic into tiles, and processing the tiles independently from one another. Unfortunately, visual artifacts between image boundaries may result because of the independent processing. Accordingly, one or more systems and/or techniques for generating a substantially seamless mosaic tile are disclosed herein. A mosaic tile comprising one or more intersecting images may be received. Pair-wise image segmentation may be executed upon pairs of intersecting images within the mosaic tile to generate seam lines between the pair of intersecting images. The seam lines are used to compose the mosaic tile. A constrained alpha-expansion algorithm is executed upon hole regions within the composed mosaic to generate a substantially seamless mosaic.

Claims

1. A method for generating a substantially seamless mosaic tile, comprising:

receiving a mosaic tile comprising one or more images intersecting the mosaic tile;

composing the mosaic tile, comprising;

for pairs of intersecting images, executing pair-wise image segmentation upon a pair of intersecting images to generate a seam line between the pair of intersecting images based upon a node to pixel location assignment, the executing pair-wise image segmentation comprising;

generating a graph comprising;

assigning nodes within the graph to respective pixel locations of an intersection area of the pair of intersecting images; and

for respective adjacent node pairings within the graph, generating an edge comprising a cost between a first node and a second node of a node pairing; and

cutting the graph to generate seam lines comprising;

for respective nodes, assigning a node to either a first image node or a second image node based upon a maxflow/mincut algorithm; and

generating seam lines between respective pairs of intersecting images based upon node to pixel location assignments; and

composing the mosaic tile to generate a composed mosaic tile based upon seam lines of respective pairs of intersecting images; and

executing an alpha-expansion algorithm upon hole regions within the composed mosaic tile to generate a substantially seamless mosaic tile, comprising;

for unassigned nodes within a hole region of the composed mosaic tile, assigning an unassigned node to either a first image adjacent the unassigned node, where the first image is within the composed mosaic tile, or a second image adjacent the unassigned node, where the second image is within the composed mosaic tile, based upon one or more costs to mitigate hole regions, where, prior to the executing an alpha-expansion algorithm, the unassigned nodes are not assigned to any images,

at least some of the method implemented at least in part via a processing unit.

2. The method of claim 1, comprising:

constraining the alpha-expansion algorithm based upon the node to pixel location assignments.

3. The method of claim 1, comprising:

generating multiple substantially seamless mosaic tiles concurrently.

4. The method of claim 1, comprising:

generating a mosaic image based upon one or more substantially seamless mosaic tiles.

5. The method of claim 4, comprising:

presenting the mosaic image to a user.

6. The method of claim 1, the mosaic tile comprising a digital elevation model.

7. The method of claim 1, the cost corresponding at least one of:

a pixel color difference;

or

an intensity gradient.

8. The method of claim 1, the composing the mosaic tile comprising:

for respective images within the mosaic tile, intersecting one or more image regions overlapping at least a portion of a particular image based upon respective seam lines of the one or more image regions.

9. The method of claim 8, the intersecting comprising:

retaining node to pixel location assignments of a subset of nodes within the mosaic tile, where respective nodes within the subset of nodes belong to no more than one image region; and

designating nodes outside of the subset of nodes as unassigned nodes.

10. A system, implemented at least in part via a processing unit, configured to generate a substantially seamless mosaic tile, comprising:

one or more processing units; and

memory comprising instructions that when executed by at least one of the one or more processing units implement at least some of;

a segmentation component configured to;

receive a mosaic tile comprising one or more images intersecting the mosaic tile;

for pairs of intersecting images, execute a pair-wise image segmentation upon a pair of intersecting images to generate a seam line between the pair of intersecting images based upon a node to pixel location assignment, the pair-wise segmentation configured to;

generate a graph by;

 

assigning nodes within the graph to respective pixel locations of an intersection area of the pair of intersecting images; and

 

for respective adjacent node pairings within the graph, generating an edge comprising a cost between a first node and a second node of a node pairing; and

cut the graph to generate seam lines by;

 

for respective nodes, assigning a node to either a first image node or a second image node based upon a maxflow/mincut algorithm; and

 

generating seam lines between respective pairs of intersecting images based upon node to pixel location assignments; and

compose the mosaic tile to generate a composed mosaic tile based upon seam lines of respective pairs of intersecting images; and

a node assignment component configured to;

execute an alpha-expansion algorithm upon hole regions within the composed mosaic tile to generate a substantially seamless mosaic tile, the alpha-expansion algorithm configured to, for unassigned nodes within a hole region of the composed mosaic tile, assign an unassigned node to either a first image adjacent the unassigned node, where the first image is within the composed mosaic tile, or a second image adjacent the unassigned node, where the second image is within the composed mosaic tile, based upon one or more costs to mitigate hole regions, where, prior to the executing an alpha-expansion algorithm, the unassigned nodes are not assigned to any images.

11. The system of claim 10, the node assignment component configured to:

constrain the alpha-expansion algorithm based upon the node to pixel location assignments.

12. The system of claim 10, the segmentation component configured to compose multiple mosaic tiles concurrently.

13. The system of claim 10, the segmentation component configured to:

intersect one or more image regions overlapping at least a portion of a particular image based upon respective seam lines of the one or more image regions.

14. The system of claim 13, the segmentation component configured to:

retain node to pixel location assignments of a subset of nodes within the mosaic tile, where respective nodes within the subset of nodes belong to no more than one image region; and

designate nodes outside of the subset of nodes as unassigned nodes.

15. The system of claim 10, the cost corresponding to at least one of:

a pixel color difference;

or

an intensity gradient.

16. The system of claim 10, comprising:

a presentation component configured to;

generate a mosaic image based upon one or more substantially seamless mosaic tiles.

17. The system of claim 16, the presentation component configured to:

present the mosaic image to a user.

18. A computer readable device comprising instructions that when executed perform operations for generating a substantially seamless mosaic tile, comprising:

receiving a mosaic tile comprising one or more images intersecting the mosaic tile;

composing the mosaic tile, comprising;

for pairs of intersecting images, executing pair-wise image segmentation upon a pair of intersecting images to generate a seam line between the pair of intersecting images based upon a node to pixel location assignment, the executing pair-wise image segmentation comprising;

generating a graph comprising;

assigning nodes within the graph to respective pixel locations of an intersection area of the pair of intersecting images; and

for respective adjacent node pairings within the graph, generating an edge comprising a cost between a first node and a second node of a node pairing; and

cutting the graph to generate seam lines comprising;

for respective nodes, assigning a node to either a first image node or a second image node based upon a maxflow/mincut algorithm; and

generating seam lines between respective pairs of intersecting images based upon node to pixel location assignments; and

composing the mosaic tile to generate a composed mosaic tile based upon seam lines of respective pairs of intersecting images; and

executing an alpha-expansion algorithm upon hole regions within the composed mosaic tile to generate a substantially seamless mosaic tile, comprising;

for unassigned nodes within a hole region of the composed mosaic tile, assigning an unassigned node to either a first image adjacent the unassigned node, where the first image is within the composed mosaic tile, or a second image adjacent the unassigned node, where the second image is within the composed mosaic tile, based upon one or more costs to mitigate hole regions, where, prior to the executing an alpha-expansion algorithm, the unassigned nodes are not assigned to any images.

19. The computer readable device of claim 18, the operations comprising:

constraining the alpha-expansion algorithm based upon the node to pixel location assignments.

20. The computer readable device of claim 18, the operations comprising:

generating a mosaic image based upon one or more substantially seamless mosaic tiles.