Image Alignment Using Translation Invariant Feature Matching

• US 20110091065A1
• Filed: 12/08/2009
• Published: 04/21/2011
• Est. Priority Date: 10/21/2009
• Status: Active Grant

• Current Assignee: LTIMindtree Ltd. (Larsen & Toubro Limited)
• Original Assignee: Mindtree Limited (Larsen & Toubro Limited)
• Inventors: Sangappa, Hemanth Kumar, Chandrashekar, Puneeth Bilagunda, Kumaraswamy, Suresh Kirthi
• Granted Patent: US 8,385,689 B2
• Time in Patent Office: Days
• US Class Current: 382/100
• CPC Class Codes: G06T 2200/32 involving image mosaicing
• CPC Class Codes: G06T 2207/10016 Video; Image sequence
• CPC Class Codes: G06T 3/4038 Image mosaicing, e.g. composing plane images from plane sub-images
• CPC Class Codes: G06T 7/337 involving reference images or patches
• CPC Class Codes: G06T 7/35 using statistical methods
• CPC Class Codes: G06V 10/16 using multiple overlapping images; Image stitching
• CPC Class Codes: G06V 10/462 Salient features, e.g. scale invariant feature transforms [SIFT]

Abstract

A computer implemented method and system is provided for aligning multiple overlapping images in real time using translation invariant feature matching. A user captures overlapping images comprising a first image and a second image using one or more image capture devices. An image aligning application determines one or more local maxima pixel points and local minima pixel points in the first image and the second image based on predetermined statistical criteria. The image aligning application performs iterative intra image correlation in the first image for selecting a predetermined number of feature points. The image aligning application performs iterative inter image correlation for the selected feature points, for determining a predetermined number of best correlated feature point pairs, and selects a matching feature point pair from the best correlated feature point pairs. The image aligning application aligns the first image and the second image using the selected matching feature point pair.

Claims

1. A computer implemented method of aligning a plurality of overlapping images in real time using translation invariant feature matching, comprising the steps of:

capturing said overlapping images comprising a first image and a second image using one or more image capture devices, wherein each of said overlapping images overlaps an adjacent image of said overlapping images;

determining at least one of one or more local maxima pixel points and one or more local minima pixel points in a first region in said first image and a second region in said second image based on predetermined statistical criteria;

performing iterative intra image correlation for at least one of said determined one or more local maxima pixel points and said determined one or more local minima pixel points in said first image for selecting a predetermined number of feature points comprising at least one of one or more least correlated local maxima pixel points and one or more least correlated local minima pixel points, wherein said iterative intra image correlation is performed in one of a first mode and a second mode;

performing iterative inter image correlation for said selected feature points, for determining a predetermined number of best correlated feature point pairs, wherein each of said determined best correlated feature point pairs comprises one of said selected feature points in said first image and one of;

one of said determined one or more local maxima pixel points and one of said determined one or more local minima pixel points in said second image;

selecting a matching feature point pair from said determined best correlated feature point pairs; and

aligning said first image and said second image using said selected matching feature point pair.

2. The computer implemented method of claim 1, wherein said first mode of performing said iterative intra image correlation comprises the steps of:

defining one or more blocks in said first region in said first image, wherein said one or more blocks are of a plurality of predetermined sizes;

defining one of a plurality of areas of one of a plurality of predetermined sizes around each of said determined one or more local maxima pixel points and said determined one or more local minima pixel points within each of said defined one or more blocks;

correlating each of said defined areas around each of said determined one or more local maxima pixel points with said defined areas around said determined one or more local maxima pixel points, and correlating each of said defined areas around each of said determined one or more local minima pixel points with said defined areas around said determined one or more local minima pixel points, within each of said defined one or more blocks in said first region, wherein said correlation is iterated for said predetermined sizes of said defined areas, wherein number of said iterations of said correlation is determined by a threshold value;

determining one or more resultant correlation coefficients based on said correlation, wherein each of said determined one or more resultant correlation coefficients represents one of a pair of local maxima pixel points whose defined areas are correlated and a pair of local minima pixel points whose defined areas are correlated;

determining one or more best resultant correlation coefficients from said determined one or more resultant correlation coefficients, wherein each of said determined one or more best resultant correlation coefficients represents one of;

one of said determined one or more local maxima pixel points and one of said determined one or more local minima pixel points;

determining a best resultant correlation coefficient from said determined one or more best resultant correlation coefficients within each of said defined one or more blocks, wherein said determined best resultant correlation coefficient represents one of said defined one or more blocks;

determining a predetermined number of least correlated blocks from said defined one or more blocks using said determined best resultant correlation coefficient of each of said defined one or more blocks; and

selecting said predetermined number of feature points comprising at least one of;

one or more least correlated local maxima pixel points and one or more least correlated local minima pixel points from said determined least correlated blocks.

3. The computer implemented method of claim 1, wherein said second mode of performing said iterative intra image correlation, comprises the steps of:

defining one of a plurality of areas of one of a plurality of predetermined sizes around each of said determined one or more local maxima pixel points and said determined one or more local minima pixel points in said first region in said first image;

correlating each of said defined areas around each of said determined one or more local maxima pixel points with said defined areas around said determined one or more local maxima pixel points in said first region, and correlating each of said defined areas around each of said determined one or more local minima pixel points with said defined areas around said determined one or more local minima pixel points in said first region, wherein said correlation is iterated for said predetermined sizes of said defined areas, wherein number of said iterations of said correlation is determined by a threshold value;

determining one or more resultant correlation coefficients based on said correlation, wherein each of said determined one or more resultant correlation coefficients represents one of a pair of local maxima pixel points whose defined areas are correlated and a pair of local minima pixel points whose defined areas are correlated;

determining one or more best resultant correlation coefficients from said determined one or more resultant correlation coefficients, wherein each of said determined one or more best resultant correlation coefficients represents one of;

one of said determined one or more local maxima pixel points and one of said determined one or more local minima pixel points; and

selecting said predetermined number of feature points comprising at least one of;

one or more least correlated local maxima pixel points and one or more least correlated local minima pixel points, using said determined one or more best resultant correlation coefficients.

4. The computer implemented method of claim 1, wherein the step of performing said iterative inter image correlation comprises the steps of:

defining a cell in said second region in said second image corresponding to spatial coordinates of each of said selected feature points in said first region in said first image;

defining one of a plurality of first areas of one of a plurality of predetermined sizes around each of said selected feature points in said first region;

defining one of a plurality of second areas of said one of said predetermined sizes around each of one of said determined one or more local maxima pixel points and said determined one or more local minima pixel points within each said defined cell in said second region in said second image;

correlating each of said defined first areas in said first region with one or more of said defined second areas within each said defined cell in said second region based on spatial coordinates of each of said selected feature points, wherein said correlation is iterated for said predetermined sizes, wherein number of said iterations of said correlation is determined by a threshold value;

determining one or more resultant correlation coefficients based on said correlation, wherein each of said determined one or more resultant correlation coefficients represents one of said selected feature points and one of;

one of said determined one or more local maxima pixel points and one of said determined one or more local minima pixel points in said second image;

determining one or more best resultant correlation coefficients from said determined one or more resultant correlation coefficients, wherein each of said determined one or more best resultant correlation coefficients represents one of said selected feature points and one of;

one of said determined one or more local maxima pixel points and one of said determined one or more local minima pixel points in said second image; and

determining a predetermined number of best correlated feature point pairs using said determined one or more best resultant correlation coefficients.

5. The computer implemented method of claim 4, wherein each of said defined first areas is coincided with one of said defined second areas based on said spatial coordinates of said selected feature points prior to the step of said correlation during performing said iterative inter image correlation, wherein said coinciding compensates for translation between said first image and said second image.

6. The computer implemented method of claim 1, wherein the step of selecting said matching feature point pair comprises the steps of:

calculating probability of occurrence of one of a vertical offset value and a horizontal offset value, of each of said determined best correlated feature point pairs;

grouping said determined best correlated feature point pairs into one or more groups based on said calculated probability;

selecting a group comprising a maximum number of said best correlated feature point pairs from among said one or more groups; and

selecting said matching feature point pair from said selected group.

7. The computer implemented method of claim 1, wherein said predetermined statistical criteria comprise an absolute surrounding mean deviation of said determined one or more local maxima pixel points and said determined one or more local minima pixel points.

8. The computer implemented method of claim 1, wherein said one or more image capture devices are positioned relative to one another in positions restraining rotation between said first image and said second image.

9. The computer implemented method of claim 1, wherein each of said iterative intra image correlation and said iterative inter image correlation is a zero offset correlation.

10. The computer implemented method of claim 1, further comprising the step of modifying said first image and said second image prior to said determination of one or more local maxima pixel points and said one or more local minima pixel points in said first image and said second image for minimizing effects of at least one of barrel distortion and noise on said first image and said second image.

11. The computer implemented method of claim 1, wherein said first image and said second image are aligned for creating a panoramic image, wherein said first region and said second region for determining said one or more local maxima pixel points and said one or more local minima pixel points are a first region of maximum overlap in said first image and a second region of maximum overlap in said second image respectively, and wherein the step of creating said panoramic image comprises the steps of:

superimposing said first image and said second image by concurrently positioning said selected matching feature point pair for obtaining a superimposed image;

computing a width of an overlapping region in said superimposed image;

defining a sigmoid function for said second image for said computed width;

defining a reverse sigmoid function for said first image for said computed width; and

applying said sigmoid function and said reverse sigmoid function to said second image and said first image respectively at said overlapping region for creating said panoramic image.

12. The computer implemented method of claim 1, wherein said first image and said second image are aligned for creating a stabilized image, wherein said first image and said second image are captured using one of said one or more image capture devices, wherein said first image and said second image comprise inter image jitter, and wherein said first region in said first image and said second region in said second image for determining said one or more local maxima pixel points and said one or more local minima pixel points are entire region of said first image and entire region of said second image respectively, and wherein said step of creating said stabilized image comprises the step of displacing said second image with respect to said first image using said selected matching feature point pair for compensating for said inter image jitter.

13. A computer implemented system for aligning a plurality of overlapping images in real time using translation invariant feature matching, comprising:

one or more image capture devices for capturing said overlapping images comprising a first image and a second image; and

an image aligning application for aligning said captured overlapping images comprising;

an input module for accepting said captured overlapping images from said one or more image capture devices via a network;

a pixel point determination module for determining at least one of one or more local maxima pixel points and one or more local minima pixel points in a first region in said first image and a second region in said second image based on predetermined statistical criteria;

an intra image correlation module for performing iterative intra image correlation for at least one of said determined one or more local maxima pixel points and said determined one or more local minima pixel points in said first image for selecting a predetermined number of feature points comprising at least one of one or more least correlated local maxima pixel points and one or more least correlated local minima pixel points;

an inter image correlation module for performing iterative inter image correlation for said selected feature points, for determining a predetermined number of best correlated feature point pairs, wherein each of said determined best correlated feature point pairs comprises one of said selected feature points in said first image and one of;

one of said determined one or more local maxima pixel points and one of said determined one or more local minima pixel points in said second image;

a feature point pair selection module for selecting a matching feature point pair from said determined best correlated feature point pairs; and

an aligning module for aligning said first image and said second image using said selected matching feature point pair.

14. The computer implemented system of claim 13, wherein said intra image correlation module performs the steps of:

defining one or more blocks in said first region in said first image, wherein said one or more blocks are of a plurality of predetermined sizes;

defining one of a plurality of areas of one of a plurality of predetermined sizes around each of said determined one or more local maxima pixel points and said determined one or more local minima pixel points within each of said defined one or more blocks;

correlating each of said defined areas around each of said determined one or more local maxima pixel points with said defined areas around said determined one or more local maxima pixel points, and correlating each of said defined areas around each of said determined one or more local minima pixel points with said defined areas around said determined one or more local minima pixel points, within each of said defined one or more blocks in said first region, wherein said correlation is iterated for said predetermined sizes of said defined areas, wherein number of said iterations of said correlation is determined by a threshold value;

determining one or more resultant correlation coefficients based on said correlation, wherein each of said determined one or more resultant correlation coefficients represents one of a pair of local maxima pixel points whose defined areas are correlated and a pair of local minima pixel points whose defined areas are correlated;

determining one or more best resultant correlation coefficients from said determined one or more resultant correlation coefficients, wherein each of said determined one or more best resultant correlation coefficients represents one of;

one of said determined one or more local maxima pixel points and one of said determined one or more local minima pixel points;

determining a best resultant correlation coefficient from said determined one or more best resultant correlation coefficients within each of said defined one or more blocks, wherein said determined best resultant correlation coefficient represents one of said defined one or more blocks;

determining a predetermined number of least correlated blocks from said defined one or more blocks using said determined best resultant correlation coefficient of each of said defined one or more blocks; and

selecting said predetermined number of feature points comprising at least one of;

one or more least correlated local maxima pixel points and one or more least correlated local minima pixel points from said determined least correlated blocks.

15. The computer implemented system of claim 13, wherein said intra image correlation module performs the steps of:

defining one of a plurality of areas of one of a plurality of predetermined sizes around each of said determined one or more local maxima pixel points and said determined one or more local minima pixel points in said first region in said first image;

correlating each of said defined areas around each of said determined one or more local maxima pixel points with said defined areas around said determined one or more local maxima pixel points in said first region, and correlating each of said defined areas around each of said determined one or more local minima pixel points with said defined areas around said determined one or more local minima pixel points in said first region, wherein said correlation is iterated for said predetermined sizes of said defined areas, wherein number of said iterations of said correlation is determined by a threshold value;

determining one or more resultant correlation coefficients based on said correlation, wherein each of said determined one or more resultant correlation coefficients represents one of a pair of local maxima pixel points whose defined areas are correlated and a pair of local minima pixel points whose defined areas are correlated;

determining one or more best resultant correlation coefficients from said determined one or more resultant correlation coefficients, wherein each of said determined one or more best resultant correlation coefficients represents one of;

one of said determined one or more local maxima pixel points and one of said determined one or more local minima pixel points; and

selecting said predetermined number of feature points comprising at least one of;

one or more least correlated local maxima pixel points and one or more least correlated local minima pixel points, using said determined one or more best resultant correlation coefficients.

16. The computer implemented system of claim 13, wherein said inter image correlation module performs the steps of:

defining a cell in said second region in said second image corresponding to spatial coordinates of each of said selected feature points in said first region in said first image;

defining one of a plurality of first areas of one of a plurality of predetermined sizes around each of said selected feature points in said first region;

defining one of a plurality of second areas of said one of said predetermined sizes around each of one of said determined one or more local maxima pixel points and said determined one or more local minima pixel points within each said defined cell in said second region in said second image;

correlating each of said defined first areas in said first region with one or more of said defined second areas within each said defined cell in said second region based on spatial coordinates of each of said selected feature points, wherein said correlation is iterated for said predetermined sizes, wherein number of said iterations of said correlation is determined by a threshold value;

determining one or more resultant correlation coefficients based on said correlation, wherein each of said determined one or more resultant correlation coefficients represents one of said selected feature points and one of;

one of said determined one or more local maxima pixel points and one of said determined one or more local minima pixel points in said second image;

determining one or more best resultant correlation coefficients from said determined one or more resultant correlation coefficients, wherein each of said determined one or more best resultant correlation coefficients represents one of said selected feature points and one of;

one of said determined one or more local maxima pixel points and one of said determined one or more local minima pixel points in said second image; and

determining a predetermined number of best correlated feature point pairs using said determined one or more best resultant correlation coefficients.

17. The computer implemented system of claim 13, wherein said feature point pair selection module performs the steps of:

calculating probability of occurrence of one of a vertical offset value and a horizontal offset value, of each of said determined best correlated feature point pairs;

grouping said determined best correlated feature point pairs into one or more groups based on said calculated probability;

selecting a group comprising a maximum number of said best correlated feature point pairs from among said one or more groups; and

selecting said matching feature point pair from said selected group.

18. The computer implemented system of claim 13, wherein said aligning module creates a panoramic image using said first image and said second image captured using said one or more image capture devices, wherein said first region and said second region for determining said one or more local maxima pixel points and said one or more local minima pixel points are a first region of maximum overlap in said first image and a second region of maximum overlap in said second image respectively.

19. The computer implemented system of claim 18, wherein said aligning module creates said panoramic image by performing the steps of:

superimposing said first image and said second image by concurrently positioning said selected matching feature point pair for obtaining a superimposed image;

computing a width of an overlapping region in said superimposed image;

defining a sigmoid function for said second image for said computed width;

defining a reverse sigmoid function for said first image for said computed width; and

applying said sigmoid function and said reverse sigmoid function to said second image and said first image respectively at said overlapping region for creating said panoramic image.

20. The computer implemented system of claim 13, wherein said aligning module creates a stabilized image from said first image and said second image captured using one of said one or more image capture devices, wherein said first image and said second image comprises an inter image jitter, and wherein said first region in said first image and said second region in said second image for determining said one or more local maxima pixel points and said one or more local minima pixel points are entire region of said first image and entire region of said second image respectively.

21. The computer implemented system of claim 20, wherein said aligning module creates said stabilized image by displacing said second image with respect to said first image using said selected matching feature point pair for compensating for said inter image jitter.

22. The computer implemented system of claim 13, wherein said image aligning application further comprises an image modification module for modifying said first image and said second image prior to said determination of one or more local maxima pixel points and said one or more local minima pixel points in said first image and said second image for minimizing effects of at least one of barrel distortion and noise on said first image and said second image.

23. A computer program product comprising computer executable instructions embodied in a computer-readable medium, wherein said computer program product comprises:

a first computer parsable program code for accepting a plurality of overlapping images comprising a first image and a second image captured using one or more image capture devices via a network;

a second computer parsable program code for determining at least one of one or more local maxima pixel points and one or more local minima pixel points in a first region in said first image and a second region in said second image based on predetermined statistical criteria;

a third computer parsable program code for performing iterative intra image correlation for at least one of said determined one or more local maxima pixel points and said determined one or more local minima pixel points in said first image for selecting a predetermined number of feature points comprising at least one of one or more least correlated local maxima pixel points and one or more least correlated local minima pixel points;

a fourth computer parsable program code for performing iterative inter image correlation for said selected feature points, for determining a predetermined number of best correlated feature point pairs, wherein each of said determined best correlated feature point pairs comprises one of said selected feature points in said first image and one of;

one of said determined one or more local maxima pixel points and one of said determined one or more local minima pixel points in said second image;

a fifth computer parsable program code for selecting a matching feature point pair from said determined best correlated feature point pairs; and

a sixth computer parsable program code for aligning said first image and said second image using said selected matching feature point pair.

24. The computer program product of claim 23, further comprising a seventh computer parsable program code for creating a panoramic image using said first image and said second image captured using said one or more image capture devices, wherein said first region and said second region for determining said one or more local maxima pixel points and said one or more local minima pixel points is a first region of maximum overlap in said first image and a second region of maximum overlap in said second image respectively.

25. The computer program product of claim 23, further comprising an eighth computer parsable program code for creating a stabilized image from said first image and said second image captured using one of said one or more image capture devices, wherein said first image and said second image comprises inter image jitter, and wherein said first region in said first image and said second region in said second image for determining said one or more local maxima pixel points and said one or more local minima pixel points are entire region of said first image and entire region of said second image respectively.