Comprehensive Study And Review Of Image Mosaicing Methods

Comprehensive Study And Review Of Image Mosaicing Methods

Mrs. Hetal M. Patel1, Asst. Prof. Pinal. J. Patel 2, Asst. Prof. Mr. Sandip G. Patel 3 1 C.S.E. Department, Government College of Engineering, Gandhinagar

Gujarat Technology University, Gujarat, India.

2 C.S.E. Department, Government College of Engineering, Gandhinagar Gujarat Technology University, Gujarat, India

3 Shrimad Rajchandra Institute of Management and Computer Application Uka Tarsadiya University,Gujarat, India.

Abstract

Image Mosaicing is the process of combining two or more images of the same scene into one image and generate panorama of high resolution image. In this paper, we have described the basic methods used to generate panorama image. Our objective is to provide different methods and algorithms used to generate panoramic image. This paper is mainly for the new comers who want to do work in the field of image mosaicing.

Keywords: Mosaicing, panorama, image blending

1. Introduction

   Image mosaicing in normal term also called image stitching where we stitch two or more images and generate one single image. Nowadays almost all digital cameras come with the feature of image panorama. Still it is not giving the very nice result and lots of improvement can be done. So this field of image processing also required efforts and still many new algorithm can be developed. Image mosaicing is used in many applications like video conferencing, from multiple node create 3D view, astronomy, telemedicine, cartoons, virtual museums, architectural Walkthroughs.

   Different steps required for doing image mosaicing are feature extraction, registration, stitching (merging images) and blending. Image registration is the process of aligning two or more images taken from one point or same thing is captured from different point which

   is shown in below figure. There are many different algorithms available to do image registration.

   Figure 1. Different image capturing methods[1]

   Main purpose of doing image registration is to create geometric correspondence between images so that we can compare images and apply other steps appropriately. Registration process can broadly divided into four categories.one in which consider pixel value of image directly [2], second is frequency domain based registration method [3], third is the algorithms which use edges and corners [4] and finally algorithms which consider objects and relation between features [4].

   After registration next is stitching. In stitching or image merging, all images are transformed according to registration parameter on single big canvas and final step

   is to do image blending which make the transition from one image to another image smoother so that joint between two images can be removed. So below diagram shows the basic steps needed in image mosaicing technique.

   respect to direction. Suppose two dimentinal gray scale image is used. Give it a name I. Assume image patch over the area (u,v) and shifting it by(x,y). The weighted SDD (sum of squared differences) between these two patches, S, is given by:

   (1)

   Input Image

   By using tailor expansion and partial derivatives, we can write above equation in matrix form as,

   Determine Correspondence point

   Here, A is the structure tensor,

   (2)

   (3)

   Determine Matching point

   Stitching and Blending

   Output mosaic

   Figure 2. Basic method of image mosaicing.

   Paper is organized as follows. in section 2 we have describe different point determining, point matching, feature detection and feature matching methods and blending methods. Section 3 contains different projective layouts, In Section 4 we have briefly described some of the recent work in image mosaicing. Finally section 5 contain conclusion and future work.

2. Basic methods for image mosaicing

   In this section we have briefly described some very basic methods and algorithms used in image mosaicing.

   1. Feature Extraction and Matching

      We start with corner detection algorithms where we have described Harris, SUSAN, forster and SIFT algorithms.

      1. Harris Corner Detector [10]

         Instead of using shifted patches, Harris and Stephens improved Moravec's corner detector by considering the differential of the corner score with

         Determine Point feature Extraction

         This matrix is a Harris matrix. and angle brackets denote averaging. Corner is characterized by a large variation of S in all directions of the vector ( x y ). By analyzing the eigenvalues of A, this characterization can be expressed in the following way: A should have two large eigenvalues for an interest point. Based on the magnitued of the eigenvalues, the following inferences can be made based on this argument:

         1. if 1 0 and 2 0 then this pixel ( x , y ) has no feature interest.

         2. if 1 0 and 2 has some large positive value, then an edge is found.

         3. if 1 and 2 have large positive values, then corner is found.

      2. SUSAN

         SUSAN is an acronym standing for Smallest Univalue Segment Assimilating Nucleus.SUSAN places a circular mask or called window over the pixel to be tested. The region of the mask is M. pixel in mask is reperesented by m. The nucleus is at m0. The brightness of pixel with in mask is compared with that of the nucleus. Every pixel is compared to the nucleus using following function :

         (4)

         Here, t represent radius. power of the exponent is determined empirically. The area of SUSAN is given by,

         (5)

         If c is rectangular function, then n is the number of pixels in the mask which are within t of the nucleues. The response of the SUSAN operator is given as:

         (6)

         For corner detection, two further steps are used. firstly, the centroid of the SUSAN is found. A proper corner will have the centroid far from the nucleues. The second is that all points on the line from the nuclues through the centroid out to the edge of the mask are in the SUSAN.

         To efficiently detect stable keypoint locations in scale space, David G. Low proposed using scale-space extrema in the difference of Gaussian function convolved with the image:

         D( x, y, ) = (G( x, y ,k ) G( x, y , )) * I( x, y ) (8)

         = L( x, y ,k ) L( x, y , )

         The difference-of-Gaussian function will have a strong response along edges, even is the location along the edge is poorly determined and therefore unstable to small amounts of noise.

         A 2X2 Hessian matrix computed at the location and scale of the keypoint is:

      3. Forstner Corner detector

         In some cases, one may wish to compute the location of a corner with subpixel accuracy. To achieve an approximate solution, the Förstner algorithm[11] solves for the point closest to all the tangent lines of the corner in a given window and is a least-square solution. The algorithm relies on the fact that for an ideal corner, tangent lines cross at a single point. Below diagram shows how algorithm detect corner using this algorithm.

         and then rejecting the keypoints for which,

         (9)

         (10)

         Figure 3. Corner detection using forstner method[12]

      4. SIFT Algorithm[8]

      Scale Invariant Feature Transform termed as SIFT is used to identify locations and scales that can be repeatably assigned under different views of the same object. Detecting locations that are invariant to scale changes of the image can be accomplished by searching for stable feature across all possible scales, using continuous function of scale known as scale spac. The scale space of an image is defined as a function, L( x, y ,

      ) , that is produced from the convolution of a variable – scale Gaussian, G( x, y , ), with the input image, I( x, y ):

      L( x, y , ) = G( x, y , ) * I( x, y ) (7)

   2. Homography Calculation using RANSAC

For deleting wrongly detected points RANSAC algorithm is used in image mosaicing. We have briefly explain this algorithm below.

RANSAC is an abbreviation for "RANdom SAmple Consensus". It is an iterative method to estimate parameters of a mathematical model from a set of observed data which contains outliers . It is a non- deterministic algorithm in the sense that it produces a reasonable result only with a certain probability, with this probability increasing as more iterations are allowed. The algorithm was first published by Fischler and Bolles at SRI international in 1981.[16]

A basic assumption is that the data consists of "inliers", i.e., data whose distribution can be explained by some set of model parameters, and "outliers" which are data that do not fit the model. In addition to this, the data can be subject to noise. The outliers can come, e.g., from extreme values of the noise or from erroneous measurements or incorrect hypotheses about the interpretation of data. RANSAC also assumes that, given a (usually small) set of inliers, there exists a procedure which can estimate the parameters of a model that optimally explains or fits this data.

The input to the RANSAC algorithm is a set of observed data values, a parameterized model which can explain or be fitted to the observations, and some confidence parameters.RANSAC achieves its goal

by iteratively selecting a random subset of the original data. These data are hypothetical inliers and this hypothesis is then tested as follows[17]:

1. A model is fitted to the hypothetical inliers, i.e. all free parameters of the model are reconstructed from the inliers.

2. All other data are then tested against the fitted model and, if a point fits well to the estimated model, also considered as a hypothetical inlier.

3. The estimated model is reasonably good if sufficiently many points have been classified as hypothetical inliers.

4. The model is re-estimated from all hypothetical inliers, because it has only been estimated from the initial set of hypothetical inliers.

5. Finally, the model is evaluated by estimating the error of the inliers relative to the model.

This procedure is repeated a fixed number of times, each time producing either a model which is rejected because too few points are classified as inliers or a refined model together with a corresponding error measure. In the latter case, we keep the refined model if its error is lower than the last saved model.

Possible variants of the RANSAC algorithm include[18],

• Break the main loop if a sufficiently good model has been found, that is, one with sufficiently small error. May save some computation time at the expense of an additional parameter.

• Compute this error directly from model without re- estimating a model from the consensus set. May save some time at the expense of comparing errors related to models which are estimated from a small number of points and therefore more sensitive to noise.

• An advantage of RANSAC is its ability to do robust estimation of the model parameters, i.e., it can estimate the parameters with a high degree of accuracy even when a significant number of outliers are present in the data set. A disadvantage of RANSAC is that there is no upper bound on the time it takes to compute these parameters. When the number of iterations computed is limited the solution obtained may not be optimal, and it may not even be one that fits the data in a good way. In this way RANSAC offers a trade-off; by computing a greater number of iterations the probability of a reasonable model being produced is increased. Another disadvantage of RANSAC is that it requires the setting of problem- specific thresholds.

• RANSAC can only estimate one model for a particular data set. As for any one-model approach when two (or more) model instances exist, RANSAC may fail to find either one. The Hough transform an alternative robust estimation technique that may be useful when more than one model instance is present.

2.3 Image Blending[19]

Blending is applied to make seamless stitching. Two popular methods of blending the images are, One is called alpha blending, which takes weighted average of two images. and another is Gaussian pyramid.

In alpha blending ,the weighting function is usually a ramp. At the stitching line, the weight is half and half, while away from the stitching line one image is given more weights than the other. The cases that alpha blending works extremely well is when image pixels are well aligned to each other and the only difference between two images is the overall intensity shift. Alpha blending will merge two images seamlessly. However, if the images are not aligned well, the disagreements will show in the blended image.

Gaussian pyramid approch, essentially merges the images at different frequency bands and filters them accordingly. The lower the frequency band, the more it blurs the boundary. Gaussian pyramid blurs the boundary while preserving the pixels away from the boundary. It does not work well, however, if the two images are at significantly different intensity levels. The transition is not as smooth as alpha blending for this case.

1. Projective layouts

   In this section we have decscribe different projective layouts on which image mosaicing can be used.

   1. Rectilinear

      Rectalinear projection, where the stitched image is viewed on a two-dimensional plane intersecting the panosphere in a single point. Lines that are straight in reality are shown as straight regardless of their directions on the image. Wide views – around 120° or so – start to exhibit severe distortion near the image borders. One case of rectilinear projection is the use of cube faces with cubic mapping for panorama viewing. Panorama is mapped to six squares, each cube face showing 90 by 90 degree area of the panorama.

   2. Cylindrical

      Cylinderical projection , where the stitched image shows a 360° horizontal field of view and a limited vertical field of view. Panoramas in this projection are meant to be viewed as though the image is wrapped into a cylinder and viewed from within. When viewed on a 2D plane, horizontal lines appear curved while vertical lines remain straight[13]Vertical distortion increases rapidly when nearing the top of the panosphere. There are various other cylindrical formats, such as Mercator and Miller cylindrical which have less distortion near the poles of the panosphere.

   3. Spherical

      Spherical projection , which is strictly speaking another cylindrical projection , where the stitched image shows a 360° horizontal by 180° vertical field of view i.e. the whole sphere. Panoramas in this projection are meant to be viewed as though the image is wrapped into a sphere and viewed from within. When viewed on a 2D plane, horizontal lines appear curved as in a cylindrical projection, while vertical lines remain vertical[13].

   4. Panini

      Since a panorama is basically map of a sphere, various other mapping projections from cartographer can also be used if so desired. Additionally there are specialized projections which may have more aesthetically pleasing advantages over normal cartography projections such as Hugin's Panini projection[14] – named after Italian vedutismopainter Giovanni Paolo Pannini[15].

   5. Stereographic

   Stereographic projection or fisheye projection can be used to form a little planet panorama by pointing the virtual camera straight down and setting the field of view large enough to show the whole ground and some of te areas above it; pointing the virtual camera upwards creates a tunnel effect. Conformality of the stereographic projection may produce more visually pleasing result than equal area fisheye projection as discussed in the stereographic projection's article.

2. Recent work

   We have studied many recent papers on image mosaicing. Here we have briefly describe the idea of algorithms presented in these papers.

   In [5], robust image mosaicing algorithm presented where they have used SUSAN corner detector is used to extract feature point, and the phase correlation technique is used to roughly estimate translational parameters of two images. The wrongly matched points are deleted with RANSAC algorithm after the initial matching. At the same time, fundamental matrix and homography matrix are estimated robustly based on the epipolar and homography constraints. The linear weighted transition method is employed in the process of image fusion.

   Corner technique based image mosaicing algorithm presented in[6]. Here they have used three step method. In first step they take two images and find corner of both these images. In second step, remove false corner from both images and finally using homography, find matched corner and get mosaic image.

   Image stitching algorithm based on feature extraction is presented in [7]. Here they extracted the edge feature pixels of images based on Canny operator edge detection algorithm and then matched the image with

   edge feature pixels in images. This algorithm is corresponding accurate and effective; it provides a new solution to calculate the edge feature pixels in image stitching algorithm.

   In [8], one SIFT based algorithm is presented. In this paper an automatic image mosaic technique based on SIFT (Scale Invariant Feature Transform) was proposed by using the rotation and scale invariant property of SIFT. Keypoints are first extracted by searching over all scales and image locations, then the descriptors defined on the keypoint neighborhood are computed, through to compare the Euclidean distance of their descriptors to extract the initial feature points pair, then eliminate spurious feature points pair by applying RANSAC, finally transform the input image with the correct mapping model for image fusion and complete image stitching.

3. Conclusion and future work

   Due to the wide range of applications, image mosaicing is one of the important research area in the field of image processing. Here we have presented some of the very fundamental and basic techniques used in image mosaicing. By doing the combination of different algorithms and according to the application we can make new and better image mosaicing algorithms. SUSAN, Harris and SIFT are popular feature extraction algorithms.

   In future we would like to implement research paper we have studied. We want to compare all algorithms and we would like to modified algorithms so that we can get better results. We would also like to present our own image mosaicing algorithm based on combination of SIFT and other algorithms.

4. References

1. S. C. Park, M. K. Park, and M. G. Kang, Super-resolution image reconstruction: A technical review, IEEE Signal Processing Mag., vol. 20, pp. 2136, May 2003.

2. D.I. Barnea, H.F. Silverman, A class of algorithms for fast digital registration, IEEE trans.comput., vol c-12.

3. C.D. Kuglin, D.C. hines, The phase correlation image alignment method, Proc IEEE 1975,pp.163-165.

4. Lisa, A survey of image registration techniques, ACM, 1992.

5. Yanli Wan, Zhenjiang Miao, Jing Chen, A Robust Image Mosaic Algorithm, 2008 Congress on Image and Signal Processing.

6. Deepak Jain, Gaurav Saxena, Vineet singh, Image Mosaicing using corner techniques, 2012 International Conference on Communication Systems and Network Technologies.

7. Yi Zhuang, Xinrong Hu, Jianchun Wang, The Implement of an Image Stitching Algorithm based on Feature Extraction, 2009 Second International Conference on Education Technology and Training.

8. Yang zhan-long Guo bao-long, IMAGE MOSAIC BASED ON SIFT, International Conference on Intelligent Information Hiding and Multimedia Signal Processing, IEEE 2008.

9. S. M. Smith and J. M. Brady. "SUSAN – a new approach to low level image processing". International Journal of Computer Vision 1997, 23 (1): 4578.

10. C. Harris and M. Stephens, "A combined corner and edge detector". Proceedings of the 4th Alvey Vision Conference. pp. 147151,1988.

11. Förstner, W; Gülch, "A Fast Operator for Detection and Precise Location of Distinct Points, Corners and Centres of Circular Features". ISPRS,1987

12. http://en.wikipedia.org/wiki/Corner_detection#The_F.C3.B 6rstner_corner_detector.

13. Wells, Sarah et al,. IATH Best Practices Guide to Digital Panoramic Photography. Retrieved 2008-06-01.2007.

14. Hugin.sourceforge.net, hugin manual: Panini.

15. Groups.google.com, hugin-ptx mailing list, December 29, 2008.

16. Martin A. Fischler and Robert C. Bolles (June 1981). "Random Sample Consensus: A Paradigm for Model Fitting with Applications to Image Analysis and Automated Cartography". Comm. of the ACM 24 (6): 381 395. doi:10.1145/358669.358692

17. David A. Forsyth and Jean Ponce (2003). Computer Vision, a modern approach. Prentice Hall. ISBN 0-13-085198-1.

18. P.H.S. Torr and D.W. Murray (1997). "The Development and Comparison of Robust Methods for Estimating the Fundamental Matrix". International Journal of Computer Vision 24 (3): 271300.doi:10.1023/A:1007927408552.

19. Yining Deng* and Tong Zhang."Generating Panorama Photos".SPIE Digital library doi:10.1117/12.513119