711 
ON THE GRAPH-BASED PANORAMA CONSTRUCTION FOR 2D LARGE-SCALE 
MICROSCOPE IMAGES 
Yu-Bo. Xie a,d , Ping.Yang b , Yong-Xi. Gong c 
a State Key Lab of Information Engineering in Surveying Mapping and Remote Sensing,Wuhan University,Wuhan 
430079, China - E-mail:thanks2l@163.com 
b Real Estate Surveying and Mapping Office of Guangzhou, Guangzhou 510030, China E-mail: ypworm@163.com 
institute of RS & GIS, Peking University, Beijing 100871, China - E-mail: yongxi_gong@163.com 
d North China Institute of Computing Technology, Beijing 100083, China - E-mail:thanks2l@163.com 
KEY WORDS: mosaicing graph, panoramic image, spanning tree, spatial cluster 
ABSTRACT: 
On analysis of existing images mosaicing methods, the conception of mosaicing graph is introduced and some principles to construct 
high quality panorama are presented in the paper. Image registration algorithm based on spatial relationship is applied to calculate 
the registration position and evaluate the registration error of a pair of images. Then three images mosaicing approaches based on 
spanning trees, including minimum cost spanning tree, shortest path spanning tree with media as root and minimum rouging cost 
spanning tree are proposed to calculate global optimum position of every images and to create the panorama. In the experiments, 
results of four methods are compared and the approaches based on shortest path spanning tree with media as rot and minimum 
routing cost spanning tree are proved to be appropriate to construct panorama with high quality and great efficiency. 
1. INTRODUCE 
Image mosaicing has already been an important subject in 
image processing and the technology has been applied widely in 
robotics, computer vision, virtual reality, surveillance, 
interactive TV, virtual tourism, medicine, remote sensing and so 
on(Brown, 1992, Chen, 1995, Gledhill et al., 2003, Zitova et al., 
2003). Image mosaicing is the most difficult problem of 
panoramic image construction(Gledhill et al., 2003). 
Image mosaicing is based on image registration. Existing 
methods of registration can be classed into area-based and 
feature-based approaches(Brown, 1992, Zitova et al., 2003,), 
which evaluate the similarity of images with several 
measurements to obtain the correct registration position(Skerl, 
2006).Pyramid-based algorithm(Thevenaz, 1998), 
wavelet-based algorithm(Manjunath, 1996, Meijering et al., 
1999), SSDA(Bamea et al., 1972) or combined algorithm(Xu et 
al., 1999) were proposed to fasten the image registration. While 
getting the registration in general, those methods could neither 
evaluate the quality of the registration result nor compare the 
results of different pairs of images. 
Most of the mosaicing methods deal with 1-D sequence images, 
in which each image is only adjacent to its previous and 
following image and there is no cycle of the adjacent 
relationships. In 1-D sequence images mosaicing, global 
position of each image is calculated by transform parameter of 
two neighboring images. In order to construct high quality 
panoramic image, errors of neighboring images are reduced by 
recovering the camera focal length(Kang et al., 1999, Davis , 
1998) or adjusting transform parameter(Kim et al., 2003, 
McLauchlan et al., 2002). In 2-D image mosaicing, each image 
not only has overlay area with its previous or following images, 
but also has neighbor relationships with some other images. In 
2-D image mosaicing, some registration failures or errors of 
pairs of images may transfer to other images and accumulate 
more and more, which will induce gaps or overlaps of the 
panoramic image. 
In order to reduce errors accumulated in 2-D image mosaicing, 
many improved methods, including topological relations among 
images(Hsu et al., 2002), gap closure of images 
sequence(Szeliski et al., 1997), least square method(Park et al., 
2000) or integrated method(Shum et al., 2000) are proposed to 
adjust local registration errors or select global optimization 
solution to create high quality panoramic image. 
According to the work above, a new type of mosaicing method 
based on graph theory was proposed, of which a vertex 
indicates an image and an edge indicates the registration 
relationships of pairs of images. For each edge, a weight by 
some criterion is attached. Registration graph are introduced to 
replace failed registered pairs by registering other pairs and 
reduce the registration error globally(Zhou, 2006). In(Nikolaidis 
et al., 2005), a object function is proposed to select the spanning 
tree of the graph, in which sub-graph spanning tree mosaicing is 
introduced to reduce the computation complexity. More 
approaches adopt shortest path spanning tree algorithm to 
calculate the global positions of each image and to build high 
quality panoramic image (Zhou et al., 2006, Kang et al., 2000, 
Marzotto et al., 2004). To avoid randomicity of reference frame, 
an improvement method, which take median as the root of the 
shortest path spanning tree(median is the root vertex with 
minimum routing cost from the root to other vertexes(Wu et al., 
2003)), is provided to adjust local registration and confirm 
global position of all images(Choe et al., 2006). 
Above method of image mosaicing is mainly used to construct 
panoramic image of natural scene for browse, and the amount of 
images is most about decade or several decades. In order to 
build panoramic image with high precision, the overlap rate 
between pair images is about 70%-80%( Zhang et al., 2004). If 
the panoramic image is constructed from large scale images, for 
instance, hundreds of or thousands of images, registration 
failure or accumulate errors will lead to obvious gaps or 
overlaps though image registration error of pair images is little.