The International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences. Vol. XXXVII. Part B5. Beijing 2008 
minimum cost spanning tree, shortest path spanning tree of 
vertex 2, shortest path spanning tree of vertex 6 and minimum 
routing cost spanning tree of mosaicing graph in Figure 1(a) 
respectively. From Figure 1, we can see that not all of the 
shortest path spanning trees can reduce the global errors of the 
mosaicing graph effectively. Minimum cost spanning tree, one 
of the shortest path spanning trees and minimum routing cost 
spanning tree, especially the second and the third ones, are close 
to the optimal solution to create high quality panoramic image. 
The second problem to be considered is how to select weight of 
edge in mosaicing graph. According to measure scale, data can 
be classified as nominal scale, ordinal scale, interval scale and 
radio scale. To construct spanning trees of graph, if only 
comparison weights of different edges is needed, data of 
interval scale or ordinal scale is enough. If the spanning tree is 
based on route, then the weight should be a type of radio scale. 
It is the second principle of image mosaicing based on 
mosaicing graph. For example, while constructing minimum 
spanning tree of mosaicing graph, the weight of the edge should 
be a type of ordinal scale, interval scale or radio scale. While 
constructing the shortest path spanning tree or minimum routing 
cost spanning tree of mosaicing graph, the weight of the edge 
should be radio scale 
Q- 
1.8 
-T-® 
1 
T 2 
© 
©- 
b 
- L2 -© 
o- 
1.8 
—9 
1 
T 2 
1.5 
© 
© 
d 
© 
Q- 
1.8 
dry 
-r-9 
1 
T 2 
1.5 
© 
© 
f 
© 
(a) Mosaicing Graph; (b) Adjacent-Vertex-in-Graph Minimum Routing 
Cost Spanning Tree (AVGMRC=32); (c) Minimum Cost Spanning Tree 
(AVGMRC=35.4); (d) Shortest Path Spanning Tree of Vertex 2 
(AVGMRC= 33.2); (e) Shortest Path Spanning Tree of Vertex 6 
(AVGMRC=49.6); (f) Minimum Routing Cost Spanning Tree 
(AVGMRC=33.2) 
Figure 1. AVGMRC and Four Typical Spanning Trees 
of Mosaicing Graph. 
cases in the microscope images mosaicing, much time are 
consumed and a balance between the quality of the panorama 
and the efficiency should be made. 
3. METHOD AND ALGORITHM 
3.1 Local Registration Based on Spatial Relationships and 
Evaluation of the Registration 
Image registration is a procedure to search the same image of 
standard image in the reference image. Existing image 
registration algorithm can not distinguish the registration 
precision of different pairs of images through the correlation 
coefficient. 
We adapted a registration approach based spatial relationships, 
in which the standard image is divided into several block 
images to register with the reference image respectively and 
then the registration position is calculated by the spatial 
relationship of the block image registration positions through 
spatial clustering algorithm. Details of this method can be 
viewed in []. 
In this method, the standard image is divided into n blocks 
denoted by Bfi-1,2...n). Registrations of these blocks are 
carried out in reference image to get n coordinates of standard 
image in the reference image, marked as L(BJ. Under ideal 
condition with non-distortion and non-circumvolve, each one in 
L(Bj) will be same. However, in practice elements in L(Bi) are 
different because of distortion and circumvolve. But in most 
cases, elements of the L(Bj distribute around a point and 
concentrate in a small region , while few points distribute 
irregularly. Therefore we can compute the position of the 
standard image in the reference image from those concentrated 
points. 
Adopting image registration algorithm based on spatial 
relationships, not only the registration position can be calculated, 
but also the reliability of the image registration is computed. 
Suppose N is the amount of blocks divided from standard image, 
M is the amount of points in C max , the class has more object than 
others, and the reliability P of registration is: 
(5) 
3.2 Weights of the Edges in Mosaicing Graph 
Before constructing panoramic graph based on spanning tree of 
mosaicing graph, the weight of the edge should be calculated. 
Weight of edge should satisfy the principle 2 and 3 provided in 
section 2. 
In large scale mosaicing, error accumulation is a relative 
severity problem. Weight of edge is uncertainly and error is 
unavoidable. If routing cost of two routes is similar, the route 
with more edges will accumulate more errors. Therefore, the 
third principle is, in the spanning tree of mosaicing graph, the 
number of edge in the route should be reduced. 
The final principle is that, a balance should be made between 
the quality of the panorama and the efficiency. For those with 
several images to be mosaiced, a more precise method can be 
considered to construct a panorama in high quality; but for those 
with hundreds of or thousands of images which are the most 
It is reasonable to take average error of the registration as the 
weight of the edge. As to registration result of a pair of images, 
let l(x,y) be the registration position, (xi,yi)(i=l,2...M) be the 
points in Cmax. The average error of the registration is: 
(6) 
713