then 
one 
cuss 
ects 
rre- 
y » 
|]. 
] as 
lere 
ode 
«B 
> Pin 
the 
art 
ent 
Pn S 
if 7 
3d yt p ds * 
i anti Az 
0 
Gm — 22) p(z)dz 
3.2 The expected number P(B) of objects which inter- 
sect with a quad block B . 
Suppose a quad block B with size 1/2" x 1/2" corre- 
spondences the node nd, . The objects which intersect with 
B are stored at the sub tree of QO whose root is nd, ,or at 
one of the ancestors of nd, . Suppose that the ancestors of 
nd, are nd, ,nda ,. .. ,nd,—, , Where ndo is the root of QO, 
and pis the expected number of objects stored at nd; , and 
gn is the expected number of objects stored at the subtree 
whose root is nd, ,then 
m—1 
PO» s En + Gm 
m-—1 
To estimate z Pi + qm , We estimate pis , Which is the 
expected number of objects stored at the subtree whose 
root is nd; but not at the tree whose root is ndi+1 , and we 
have: 
yz" : 
m >3[, (1/2 — Dh 
then 
P(B) 
m—1 
S Ep +m 
m-—1 
ic ER 
m—1 
Ja: ; 
ei HE * Q/2* — ay 
i 
3.3 A example of p(x) 
Now using a example of p(z) , we further estimate pm 
and P(B) , to show the effectiveness of QO. 
Let 3x) = eV / (ge /207?), its shape shown on 
Figure 1. 
  
Fig. 1 The shape of p(x) 
The reason of letting p (x) be this special function is 
listed below; (1)the number of objects with size x con- 
taining in the unit square potition with 1/2 ; (2)for a 
given class of images, the objects which is two smaller is 
85 
: . 1 
always noise, so we set a decreasing factor e»: , 
p(x) reach its maximum value at point x— ,So o shows 
the maximum feature of the probability density function 
of the size of objects. 
1. The estimate of P(B) 
We obtain the estimate below: 
P(B) 
<7 
3 1 
420-72) 
6 42 
T[——Àma- d£ 
(4 — 42) da 2 
2. The estimate ofp. For pa , we obtain ; 
1,4—42) 
Ju S. os 20 T 
2 
Wer Je 
§ 4 Conclusion 
The vector data has a well —organized logical structure 
, but has no natural spatial index. In this paper , a spa- 
tial index for vector data , called QO, is presented . 
Analysing the querying effectiveness on the vector data 
with QO structure , it is shown that the time consume of 
queries in the position — based class is much smaller than 
that on "pure" vector data. 
This structure also can be used in other systems, such 
as CAD/CAM systems or vision systems. 
References 
[1] A. Rosenfeld and A. Kak, Digital Picture Process- 
ing, 2nd Ed. , Academic Press, New York, 1982. 
[2] S. K. Chang, Principles of Pictorial Information 
System Design, Prentice — Hall , Inc. , 1989. 
[3] M. J. B. Duff, "Intermediate —1level Image Pro- 
cessing” , London Academic Press, 1986. 
[4] H. Samet, "The Quadtree and Related Hierarchical 
Data Structures” , Computing Survey, Vol. 16, No. 2, 
1984, 187—260. 
[5] E. Kawaguchi and T. Endo, et al, "Depth — first 
Expression Viewed from Digital Picture Processing " 
IEEE Trans. Vol. PAMI—5, 1983, pp373— 384. 
[6] Q. Y. Shi , "Image Processing Operations Using CD 
Representations" , Proc. of 8th ICPR, 1986, pp320 — 
322. 
[7] S. X. Li and M. H. Leow, "The Quadcode and its 
Applications" , Proc of 7th ICPR 1984, pp227 —229. 
[8] H. Samet and M. Tamminen, Computing Geometric 
Properties of Images Represented by Linear Quadtree" ,