Digital Image Mosaicing using Optimized KD-Tree Search

Digital Image Mosaicing using Optimized KD-Tree Search

Shubham Shukla

Computer Science and Engineering

Dr. B. R. Ambedkar National Institute of Technology Jalandhar, India

Dr. Renu Dhir 1, Ms. Rajneesh Rani 2

Computer Science and Engineering

Dr. B. R. Ambedkar National Institute of Technology Jalandhar, India

Abstract Field of view of an image capturing hardware is smaller than our own field of view due to limitations of hardware. For capturing field of view as human eye, concept of image mosaicing comes. Image mosaicing is referred to the process of combining multiple partially overlapped images, in order to generate a larger field of view. Feature based image mosaicing using KD-tree suffer from the backtracking issue of nearest neighbor search. In this proposed method, optimization of KD-tree is used to remove backtracking problem which also makes the execution faster.

KeywordsImage mosaicng; Scale Invariant Feature Transform (SIFT); KD-tree; RANSAC.

1. INTRODUCTION

   Image mosaicing is the process of stitching multiple partially overlapped images to generate a larger area image (panorama image) with seamless view. It is a process of combining small size images to produce a large size image with wide field of view. This process is about aligning multiple images according to the coordinate relations between the pair of images. Thereafter applying the appropriate transformation on coordinates, images can be easily merged. This is the basic fundamental concept behind image mosaicing. There are number of steps followed during image mosaicing, these are feature extraction, image registration, computing homo-graphy, and image warping and blending.

   Feature extraction minimizes the matching criteria over a limited extracted feature by removing the unnecessary information associated with the image that are not of use. It provides the unique feature of an image. Image registration is the second step involved in image mosaicing process; it is used to geometrically align set of images. In image registration, the geometrical correspondence between images is established so that various operations like comparison, transformation can take place. Homo-graphy computation is the third step in mosaicing. It is used to establish mapping between point of interests by removing the undesired points (or outliers). Image warping is the process of geometrically distorting the image either by rotating or scaling the image, in order to fit the reference image. Image blending is the final step of image mosaicing process; it is used to remove the seam effect from the mosaic image.

   KD-tree [1] is a multidimensional data structure used to store the extracted feature points and match them with the correspondence image to establish geometrical match between

   both the images in input pair. KD-search for nearest neighbor require it to search point to the leaf and if not found neighbor then move back to the upper level and search in other branch. Backtracking of nearest neighbor search takes a lot of time which is not quite efficient. So this paper removes the problem associated with the KD-tree and provides good speedup to the image mosaicing process.

2. LITERATURE SURVEY

   In 1997, S. Peleg et al. [2] proposed a method for generating mosaic image using planar, cylindrical and general manifold. Manifold projection helps in the fast creation of low distorted panorama mosaics under very slight camera motions. Manifold projection gives the computationally efficient result, because here only the image plane rotation and translation deformation takes place. In 1998, R. B. Inampudi [3] proposed a design of high performance software to perform geometrical and radio metrical corrections of two or more images without using any kind of special hardware. He used the concept of ground control points (GCP), geo- referencing and polynomial filing to mosaic images together. This method concentrates mosaicing over user specified cut lines. His work is on retina and kutub minar image. In 1998,

   1. Rousso et al. [4] proposed the pipe projection model which is used to define high quality mosaicing even for the most challenging cases of forward motion and zoom. The model also helps in removing parallax during complex motion. In 2000, HY Shum et al. [5] proposed a system based on the patch based alignment scheme to generate a mosaic image. It performs pairwise motion based on the block adjusted images generated by the patch alignment scheme. In 2001, M Uyttendaele et al. [6] proposed a method of eliminating ghosting effect occurred due to the motion of objects in the image pair. They used spline to get a spatially continuous exposure adjustment. In 2007, Bevilacqua et al. [7] proposed a fully automated real-time online mosaicing algorithm and were able to build high quality seem-free panoramic images. Moreover the whole algorithm does not exploit any prior information regarding scene geometry, acquisition devices or feedback signals. In 2008, Azzari et al. [8] proposed a quantitative evaluation methodology for image mosaicing algorithm. They performed tests over three well known algorithms, but the basis was dependent on the data set and the quality of mosaicing considered based on the seam and

      alignment. In 2010, L Li et al. [9] proposed a method based on SIFT following by KD-tree for the matching of points. This algorithm gives the reduced time span with the fidelity of resulting panoramic image is ensured. In 2012, Lin Zeng et al. [10] proposed a combined approach of SIFT and Dynamic programing to avoid the ghosting effect and mosaic failure due to huge exposer difference and big parallax between adjacent images. This method shows better feasibility and against most popular mosaic software (AutoStich, Microsoft ICE and Panorama Maker). In 2008, Silpa-Anan et al. [11] proposed various optimization techniques for KD-tree. The proposed techniques removed the limitations associated with the backtracking problem of nearest neighbor search in high dimensional space. They proposed various alternatives for optimization based on a multiple tree search scheme and PCA based search, combination of both work well and the result of search becomes two times faster than individual tree search.

3. METHODOLOGY

   The main objective of this paper is to improve the execution performance of mosaic system by removing the time consuming task associated with the KD-tree. Feature extraction of both images is done using SIFT [12]. SIFT follows mainly four steps

   1. Scale-space extrema detection: It represents the scale space associated with the unique key points.

   2. Key point localization: This step only considers those key point that represent either minima or maxima.

   3. Orientation assignment: Here, every key point is having one or more orientation depending on the local image gradient directions. This step helps in achieving invariance to rotation because the key point descriptor can be presented relative to this orientation and thus invariance to image rotation achieved.

   4. Key point descriptor generation: This step insures invariance to image location, scale and rotation. A descriptor vector of size (128) for every key point calculated such that the descriptor is highly distinctive and partially invariant to the variations such as accuracy, illumination, 3D viewpoint, stability, etc.

      Second step in the mosaicing process is to register both the images. Here we use optimized KD-search [11] for finding the nearest neighbors of the key points. Algorithm for finding the nearest neighor involves five steps.

      1. Create m different KD-trees in such a manner that each tree possesses a different structure and be highly independent on each other.

      2. With the limit of n nodes to be searched, break the search into m different trees in simultaneous searches.

      3. The average of searching of nodes in each tree will be limited to n/m.

      4. Search multiple trees in the form of a concurrent search with a pooled priority queue.

      5. Stop when found the exact nearest neighbor.

   Third step in image mosaicing is finding homo-graphy between the images for mapping between the image pair. RANSAC [13] algorithm is used for removing the mismatches between both images. Final step is image warping and blending. In image warping we distort one image with reference to the other, to match their coordinates and put both images in a larger canvas, so as to create a mosaiced image. Finally image blending is used to remove the seam effect from the output mosaic image.

4. RESULT

   To compare the performance of the scheme, it is tested against normal KD-tree mosaic scheme on MATLAB tool with Dual-core CPU and 2GB RAM on Windows-7 over standard dataset provided by The Artificial Intelligence Research Institute (IIIA) [14]. IIIA has built a dataset of approximate 19 sequence scenes along with 12000 cylindrical images taken from different viewpoints and with some difference of distance.

   Fig. 1(a): Left Scene Fig. 1(b): Right Scene

   The whole dataset contains cylindrical images taken in difference of 20 cm in a straight path with the size of 479×480 each. Fig. 1(a) shows the left part of a scene, Fig. 1(b) shows the right part of the scene containing some common or overlapping region (Door is common). Fig. 1(c) shows the key point correspondence between both the images. Finally Fig. 1(d) shows the final output mosaic image of input pair. The performance of the system gives the speedup of 12% over the normal KD-tree system when tested over the dataset of IIIA.

   Fig 1(c): Mapping of Key

   Fig 1(d): Output Mosaic Image

   1. Inampudi, Ramesh B. "Image mosaicing." Geoscience and Remote Sensing Symposium Proceedings, 1998. IGARSS'98. 1998 IEEE International. Vol. 5. IEEE, 1998.

   2. Rousso, Benny, et al. "Universal mosaicing using pipe projection." Computer Vision, 1998. Sixth International Conference on. IEEE, 1998.

   3. Shum, Heung-Yeung, and Richard Szeliski. "Image mosaic construction system and apparatus with patch-based alignment, global block adjustment and pair-wise motion-based local warping." U.S. Patent No. 6,097,854. 1 Aug. 2000.

   4. Uyttendaele, Matthew, Ashley Eden, and R. Skeliski. "Eliminating ghosting and exposure artifacts in image mosaics." Computer Vision and Pattern Recognition, 2001. CVPR 2001. Proceedings of the 2001 IEEE Computer Society Conference on. Vol. 2. IEEE, 2001.

   5. Bevilacqua, Alessandro, and Pietro Azzari. "A fast and reliable image mosaicing technique with application to wide area motion detection." Image Analysis and Recognition. Springer Berlin Heidelberg, 2007. 501-512.

   6. Azzari, Pietro, Luigi Di Stefano, and Stefano Mattoccia. "An evaluation methodology for image mosaicing algorithms." Advanced Concepts for Intelligent Vision Systems. Springer Berlin Heidelberg, 2008

   7. Li, Lin-na, and Nan Geng. "Algorithm for sequence image automatic mosaic based on SIFT feature." Information Engineering (ICIE), 2010 WASE International Conference on. Vol. 1. IEEE, 2010.

   8. Zeng, Lin, et al. "Dynamic image mosaic via SIFT and dynamic programming."Machine Vision and Applications (2013): 1-12.

   9. Silpa-Anan, Chanop, and Richard Hartley. "Optimised KD-trees for fast image descriptor matching." Computer Vision and Pattern Recognition, 2008. CVPR 2008. IEEE Conference on. IEEE, 2008.

   10. Lowe, David G. "Distinctive image features from scale-invariant keypoints."International journal of computer vision 60.2 (2004): 91- 110.

   11. Fischler, Martin A., and Robert C. Bolles. "Random sample consensus: a paradigm for model fitting with applications to image analysis and automated cartography." Communications of the ACM 24.6 (1981): 381-395.

   12. http://www.iiia.csic.es/~aramisa/datasets/iiiapanos.html

5. CONCLUSION

The work presented in this paper is based on the search criteria for KD-tree by dividing search over multiple trees. Here, multiple independent KD-trees are created using different strategies in order to make trees more independent of each other. In this work, search of traversing n elements is divided over the number of trees and searching on trees is done in concurrently. Ranking of first candidate and a second candidate is maintained over the pooled queue and the candidate with the least distance from the origin is selected. Through this approach, we have reduced the backtracking time taken by the individual tree in the search of best nearest neighbor. This work provides a considerable speedup over normal KD-tree enabled mosaic approach.

REFERENCES

1. Beis, Jeffrey S., and David G. Lowe. "Shape indexing using approximate nearest-neighbour search in high-dimensional spaces." Computer Vision and Pattern Recognition, 1997. Proceedings., 1997 IEEE Computer Society Conference on. IEEE, 1997.

2. Peleg, Shmuel, and Joshua Herman. "Panoramic mosaics by manifold projection." Computer Vision and Pattern Recognition, 1997.

Proceedings., 1997 IEEE Computer Society Conference on. IEEE, 1997.