The International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences. Vol. XXXVII. Part B5. Beijing 2008 
Large-scale microscope images are gathered by microscope 
apparatus, which cover the whole area of target. Each image has 
overlap area between conjoint images. In general, panorama of 
large-scale microscope images is applied in medicine, LSI etc. 
Mosaicing of Large-scale microscope images is different from 
general image mosaicing in: (1) Microscope images are 
gathered by special apparatus so that errors including distortion 
and rotation can be neglected. (2) The amount of images is large, 
commonly several hundred, for example, under 40 multiple 
magnifier an organization slice has several hundreds or several 
thousands images with 1600*1200 pixels. Therefore, local 
mosaicing error will accumulate and lead to gaps or overlaps of 
the panoramic image. (3) On the field such as medicine and LSI, 
panoramic image is build for further analysis, so the quality of 
the panoramic image is vital. Those panoramas with low quality 
will lead to unpredictable bad result. 
In this paper, several mosaicing approaches based on mosaicing 
graph are presented and compared, e.g. minimum cost spanning 
tree, shortest path spanning tree and minimum routing cost 
spanning tree from the quality and efficiency point of view, and 
the most proper method to be selected under different situation 
is discussed. 
The main contents of this paper is arranged as following: in 
section 2, the conception of mosaicing graph and some 
principles to construct optimal panoramic are provided; In 
section 3, method and algorithm to compute the weight of 
mosaicing graph, and methods based on three types of spanning 
tree of mosaicing graph are presented and compared to build 
panorama with high quality and great efficiency. In Section 4, 
experimental results of several methods are presented and 
compared. Finally, a conclusion is drawn in 5. 
2. CONCEPTS AND PRINCIPLES 
Mosaicing graph of image mosaicing is an undirected weighted 
graph, marked as G(V,E,w), in which V represents image set, E 
represents registration relation set among images and w is 
weight of edge. Microscope images arrange much regular, like 
M rows and N columns(M*N) matrix, and only neighboring 
images have registration relationship. 
A micrograph mosaicing graph of 2 row 3 arrange is shown in 
Figure 1(a). In the mosaicing graph, each vertex denotes an 
image, each edge denotes registration relation between two 
neighboring images, and each edge owns non-negative weight. 
Among mosaicing graph, there always are some registration 
failures or errors, while one spanning tree of mosaicing graph 
may determine global positions of all images. If cycle existing 
in the graph, global position of some of the images may 
calculate by more than one route and conflicts emerge. Then, 
the most important problem to build a panoramic image is to 
select a proper spanning tree to minimize the global errors of 
the mosaicing graph. 
Let mosaicing graph be G(V,E,w) where w>0, one of its 
spanning tree be T, weight of edge be radio scaling. The 
approaches to construct panoramic image based on spanning 
tree can be classified into two types: on the external errors and 
on the internal errors. 
First we will discuss the approach based on the external errors. 
Let vertex i and j be pair of conjoint vertexes, (xi,yi),(xj,yj) be 
registration coordinate of vertex i and j of conjoint images, 
(xi ’ ,yi ’),(xj ’ ,yj ’ ) be global coordinate of vertex i and j by 
spanning tree T respectively. As to spanning tree T of 
mosaicing graph G, the total errors of conjoint vertexes is 
marked as external errors summation, that is 
Y. fa,fafa.fa) 2 +(0-,fa)-tv,fa)) 1 (1) 
i,jcV(GX 
(i,y)e£(G) 
According to equation (1), the panoramic image will be in 
highest quality when E is smallest. If weight of pair image 
registration is considered, registration with high quality should 
take more rates in Eout. Let aij be the measurement of 
registration quality of image pair i and j. Spanning tree to build 
panoramic image with best quality should satisfy: 
4», =«mjsW(6>- -A)f -KOj -yfaiy, -yjf j (2) 
Although it is a good method to construct high quality 
panoramic image, unfortunately, to get all of the spanning trees 
of mosaicing graph imposes prohibitive computational 
requirements when the amount of the vertexes is 
large(Nikolaidis, 2005). Then we should consider from 
another point of view and discuss the method based on internal 
errors. 
Supposed shortest path SP(u,v)=(u=rl,r2,...,m=v)of vertex u,v 
of spanning tree T, thereinto ri V(T), routing cost dT(u,v) of 
SP(u,v) can be denoted as weight summation of all edges in the 
path on T: 
n—1 
d T {u,v)= I w(r t ,r t+ 1) (3) 
/=1 
For each pairs of neighboring images u and v, the result is best 
while the routing cost is minimized; for the mosaicing graph, 
the panoramic image is in highest quality while the routing 
cost’s summation of all the adjacent vertexes in graph is 
minimized. This spanning tree is marked as Adjacent-Vertex 
-in-Graph Minimum Routing Cost Spanning Tree (AVGMRST), 
and the cost of AVGMRST is called Adjacent-Vertex-in-Graph 
Minimum Routing Cost(AVGMRC) of mosaicing graph: 
A VGMRC(G) = min j £ dj(u,v)> (4) 
[w,veF (G),e(u,v)eE(G) 
So, the AVGMRST is the spanning tree of mosaicing graph to 
build high quality panoramic image; if it is difficult to build 
AVGMRST, the spanning tree which is closer to AVGMRST is 
preferred. For example, Figure 1(a) is a mosaicing graph and its 
optimize spanning tree should make summation of route cost 
between vertexes (1,2),(2,3),(1,6),(2,5),(3,4),(5,6) and (4,5) 
minimized, and its AVGMRC is 32, as Figurel(b) shown. 
Figurel(c), Figurel(d), Figurel(e) and Figurel(f) shows