Aligning images

• US 8,699,821 B2
• Filed: 09/03/2010
• Issued: 04/15/2014
• Est. Priority Date: 07/05/2010
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Orr, James Edmund IV, Johnson, Garrett M., Cote, Guy
• Primary Examiner(s): Koziol, Stephen R
• Assistant Examiner(s): CONNER, SEAN M
• Application Number:
  US12/876,097
• Publication Number:
  US 20120002899A1
• Time in Patent Office: 1,320 Days
• Field of Search: None
• US Class Current: 382/294
• CPC Class Codes: G06T 2207/10144 Varying exposure
• CPC Class Codes: G06T 2207/10152 Varying illumination
• CPC Class Codes: G06T 2207/20016 Hierarchical, coarse-to-fine, multiscale or multiresolution image processing; Pyramid transform
• CPC Class Codes: G06T 2207/20021 Dividing image into blocks, subimages or windows
• CPC Class Codes: G06T 2207/20208 High dynamic range [HDR] image processing
• CPC Class Codes: G06T 5/50 using two or more images, e.g. averaging or subtraction
• CPC Class Codes: G06T 7/32 using correlation-based methods
• CPC Class Codes: H04N 23/12 with one sensor only
• CPC Class Codes: H04N 23/62 Control of parameters via user interfaces
• CPC Class Codes: H04N 23/667 Camera operation mode switching, e.g. between still and video, sport and normal or high- and low-resolution modes
• CPC Class Codes: H04N 23/6811 based on the image signal
• CPC Class Codes: H04N 23/6812 based on additional sensors, e.g. acceleration sensors
• CPC Class Codes: H04N 23/71 Circuitry for evaluating the brightness variation
• CPC Class Codes: H04N 23/72 Combination of two or more compensation controls
• CPC Class Codes: H04N 23/741 by increasing the dynamic range of the image compared to the dynamic range of the electronic image sensors
• CPC Class Codes: H04N 23/743 Bracketing, i.e. taking a series of images with varying exposure conditions
• CPC Class Codes: H04N 23/951 by using two or more images to influence resolution, frame rate or aspect ratio

Abstract

Some embodiments provide a method of aligning a pair of images. The method defines multiple different pairs of images at multiple different resolutions. The method hierarchically aligns the original pair of images by first aligning the pair of images at the lowest resolution and then aligning each pair of images at each higher resolution based on the alignments of the pair of images at the lower resolutions. For some of the resolutions, to perform the hierarchically alignment, the method identifies, for at least one image at each resolution, portions that are suitable for performing the alignment and portions that are not suitable for performing the alignment. The method compares each pair of images at a particular resolution by using the suitable portions while excluding the unsuitable portions from the comparison.

Claims

1. A method of aligning a pair of original images, the method comprising:

defining a plurality of different pairs of images at a plurality of different resolutions, wherein the plurality of different pairs of images is associated with a plurality of different pairs of bitmaps, and each particular bitmap is a bitmap of a particular original image at a particular resolution; and

hierarchically aligning the pair of original images by first aligning the pair of images at the lowest resolution and then aligning each pair of images at each higher resolution based on the alignments of the pair of images at the lower resolutions,

the hierarchical aligning comprising, for each particular resolution in a subset of resolutions;

for at least one particular image at the particular resolution, dividing the particular image into a plurality of tiles for use in identifying corresponding portions in the other image in the pair at the particular resolution; and

comparing the pair of images by using tiles that are suitable for the comparison while discarding tiles that are unsuitable from the comparison;

wherein identifying suitable and unsuitable tiles in a particular image at a particular resolution comprises identifying tiles that have more than a threshold level of black pixels or tiles that have more than a threshold level of white pixels as unsuitable.

2. The method of claim 1, wherein comparing the pair of images at at least one resolution comprises finding an offset that aligns the pair of images at the particular resolution using the portions suitable for performing the alignment and an offset that aligns the images at a lower resolution.

3. The method of claim 2, wherein the finding the offset at the particular resolution comprises:

resizing the found offset that aligns the images at the lower resolution to account for the difference in the resolution between the lower resolution and the particular resolution; and

using the resized offset as a starting offset for finding the offset that aligns the images at the particular resolution.

4. The method of claim 2, wherein finding an offset comprises determining which particular offset of a limited number of candidate offsets provides the closest alignment of the images.

5. The method of claim 4, wherein the limited number of candidate offsets comprises all offsets within one pixel horizontally and one pixel vertically of a starting offset.

6. The method of claim 4, wherein the limited number of candidate offsets does not comprise any offsets more than one pixel horizontally or more than one pixel vertically from the starting offset.

7. The method of claim 1, wherein defining a plurality of different pairs of images at a plurality of different resolutions comprises generating a plurality of versions of each original image at a plurality of resolutions, wherein generating each version of each image at a particular resolution comprises decimating a higher resolution version of the image.

8. The method of claim 7, wherein the decimating a higher resolution version comprises generating the version at a particular resolution by sub-sampling the higher resolution version.

9. The method of claim 1, wherein the subset of resolutions do not include a plurality of lower resolutions but comprise a plurality of higher resolutions.

10. A non-transitory machine readable medium of a mobile device, the machine readable medium storing a program that when executed by at least one processing unit aligns and composites a plurality of images, the program comprising sets of instructions for:

at each particular resolution of a plurality of resolutions;

generating a bitmap at the particular resolution for each image in the pair of images;

tiling one of the pair of bitmaps if when the particular resolution is one of a subset of the resolutions;

discarding any tile that is not suitable for comparison with portions of the other bitmap, wherein identifying tiles that are not suitable at the particular resolution comprises identifying tiles that have more than a threshold level of black pixels or tiles that have more than a threshold level of white pixels as unsuitable; and

finding an offset that aligns the pair of images at that the particular resolution (i) by using any non-discarded tiles, and (ii) when the particular resolution is not the lowest resolution, by using an offset that aligns the images at a lower resolution.

11. The machine readable medium of claim 10, wherein the program further comprises sets of instructions for:

rescaling a found offset that aligns the images at the lower resolution; and

using the rescaled offset as a starting offset for finding an offset of the particular resolution.

12. The machine readable medium of claim 11, wherein the set of instructions for finding an offset comprises a set of instructions for determining which particular offset of a limited number of candidate offsets provides the closest alignment of the images.

13. The machine readable medium of claim 10, wherein the program further comprises a set of instructions for generating a plurality of versions of each image of the pair of images at a plurality of resolutions, wherein the set of instructions for generating a version at a particular resolution comprises a set of instructions for decimating a higher resolution version of the image.

14. The machine readable medium of claim 13, wherein the set of instructions for decimating a higher resolution version comprises a set of instructions for generating the version at a particular resolution as a copy of the higher resolution version, wherein the copy has half the number of pixels vertically and half the number of pixels horizontally as the higher resolution version of the pair of images.

15. The machine readable medium of claim 14, wherein the copy is generated by sub-sampling the higher resolution version.

16. The computer readable medium of claim 10, wherein the set of instructions for generating a bitmap comprises a set of instructions for creating a 1-bit bitmap with pixels that correspond to the pixels of the image, wherein a first value of pixels in the bitmap correspond to pixels in the image comprising all pixels in the image that are above the median brightness of pixels in the image and a second value of pixels in the bitmap correspond to pixels in the image comprising all pixels in the image that are below the median brightness.

17. The method of claim 10, wherein the subset of resolutions do not include a plurality of lower resolutions but comprise a plurality of higher resolutions.

18. A mobile device, comprising:

a) a camera for capturing a plurality of images;

b) at least one processing unit;

c) a machine readable medium storing an alignment module that when executed by the at least one processing unit aligns the plurality of images, the alignment module comprising sets of instructions for;

defining a plurality of different pairs of images at a plurality of different resolutions, wherein the plurality of different pairs of images is associated with a plurality of different pairs of bitmaps, and each particular bitmap is a bitmap of a particular original image at a particular resolution; and

hierarchically aligning the pair of original images by first aligning the pair of images at the lowest resolution and then aligning each pair of images at each higher resolution based on the alignments at the pair of images at the lower resolutions,

the hierarchically aligning comprising, for each particular resolution in a subset of resolutions;

for at least one particular image at the particular resolution, dividing the particular image into a plurality of tiles for use in identifying corresponding portions in the other image in the pair at the particular resolution; and

comparing the pair of images by using tiles that are suitable for the comparison while discarding tiles that are unsuitable from the comparison;

wherein identifying suitable and unsuitable tiles in a particular image at a particular resolution comprises identifying tiles that have more than a threshold level of black pixels or tiles that have more than a threshold level of white pixels as unsuitable; and

compositing the aligned pair of original images to produce a high dynamic range image.

19. The mobile device of claim 18, wherein the set of instructions for comparing the pair of images at at least one resolution comprises a set of instructions for finding an offset that aligns the pair of images at the particular resolution using the portions suitable for performing the alignment and an offset that aligns the images at a lower resolution.

20. The mobile device of claim 19, wherein the set of instructions for finding the offset at the particular resolution comprises sets of instructions for:

resizing the found offset that aligns the images at the lower resolution to account for the difference in the resolution between the lower resolution and particular resolution; and

using the resized offset as a starting offset for finding the offset that aligns the images at the particular resolution.

21. The mobile device of claim 19, wherein the set of instructions for finding an offset comprises a set of instructions for determining which particular offset of a limited number of candidate offsets provides the closest alignment of the images.

22. The mobile device of claim 21, wherein the limited number of candidate offsets comprises all offsets within one pixel horizontally and one pixel vertically from the initial offset.

23. The mobile device of claim 21, wherein the limited number of candidate offsets does not comprise any offsets more than one pixel horizontally or more than one pixel vertically from the initial offset.

24. The mobile device of claim 18, wherein the set of instructions for defining a plurality of different pairs of images at a plurality of different resolutions comprises a set of instructions for generating a plurality of versions of each original image at a plurality of resolutions, wherein the set of instructions for generating each version of each image at a particular resolution comprises a set of instructions for decimating a higher resolution version of the image.

25. The mobile device of claim 24, wherein the set of instructions for decimating a higher resolution version comprises a set of instructions for generating the version at a particular resolution by sub-sampling the higher resolution version.

26. The mobile device of claim 18, wherein the exclusion discarding of the unsuitable portions from the comparison decreases a number of operations performed by the processor to execute the sets of instructions of the alignment module in order to align the plurality of images.

27. The method of claim 18, wherein the subset of resolutions do not include a plurality of lower resolutions but comprise a plurality of higher resolutions.