ѧ
Journal of Software
2000 Vol.11 No.1 P.110-115



һֻ״ͼϢ
ʷֲ
ժҪİһͼ񿴳һЩ򹹳ɵ,Щڲɫȷ,ͼ״Щı߽߼ռϵ.Ҫͼ򳡾״м,ؼ״ԵĶռϵıʾƥ.Ӧñģƥ似,˽Ϊļ״Լ㷽,Щ״֮Ŀռϵɶάϴʾ.»˿ռϵƥ㷨,ڼ,̷Ϊռϵƥ3׶.ʵ,˷нϸߵļٶ,нϸߵļ.
ؼʡ,άϴ,״ļ,ͼ.
ͼšTP311
A Shape-Based Image Information Retrieval Method
LIU Ji-minSHI Zhong-zhi
(Institute of Computing TechnologyThe Chinese Academy of SciencesBeijing100080)
AbstractAn image can be considered as a combination of regions, which have some intrinsic homogeneities in color or texture, etc. The shapes in an image are described by the boundaries of these regions and their spatial relations. To retrieve image by shape, it is a key problem to measure the similarity among shapes and match their spatial relations. Adopting template-matching technique, the authors present a computation method for simple shape similarity. Based on the two-dimensional set string representation of the spatial relation of these simple shapes, a spatial relation match algorithm is also presented. The whole retrieval process is divided in three stages, i.e., the rough stage, the refining stage and the spatial relation matching stage. The experiment shows this method is rapid and accurate.
Key wordsSimilarity, 2D set string, shape-based retrieval, image database.
״ͼϢǻݵͼϢһʮҪķ.Ŀǰ,вٻݽмʵϵͳ,QBIC,Photobook,VisualSeek.ЩϵͳڸɫϢмʱ,õļڴĽΪӽ.ڸ״Ϣмʱ,״е,ܳز״,ɴ˽,м.ף1,2ҲǲƵķ.ָмķ,ٶȿ.,״һĳ̶Ƕ״ĸ֪,˸оȫͬ״ͬ,,ַļûҪõĽܴ.,ʵ,ȡв̶ͬȵ,ƱؽһӰ쵽ľ.
෴,ף3,4,Ӧ˱ģ弼,ûṩ״ģ,ͼе״ƥ.һֱӰ״бȽ,ǱȽ,нϸߵľ.ڼʱ,ǽģÿһͼƥ,ÿһƥ䶼кܴļ,,һļٶ.
Ϊ˼߼ٶ,ֱ֤ϸߵļ,ǵǣÿ洢ͼοеͼ,ȡ״,ÿıԵһ״,ɼ״(,״ָƽϵļ򵥱),ͼ״Щı߽߼ռϵ,ͼ1ʾ.


Simple shape 1, 2, 3 are boundaries of the regions that have notable features. The shape of the original image is represented with the three simple shapes and their relationship.
״1,2,3Ǵԭʼͼȡľ״ı߽,3״ռϵԭʼͼе״.
Fig.1Shape representation
ͼ1״
ǽЩ״,ͬʱܳ״.ڽмʱ,ûֱӻһ򼸸״,ΪѯҪ,ͼ2ʾ.


In order to retrieve the original image in Fig.1, the user can directly draw one or more simple shapes which he concerns as research query, e.g.
Ϊ˴ͼмͼ1еԭʼͼ,ûֻҪֱӻĵ1򼸸״,ΪѯҪ,(a),(b),(c).
Fig.2The submission of the research query
ͼ2ѯҪύ
ϵͳݸ״,гμ,Щ״ͼ,ñģƥ似5ݽм,ųƶȽСͼ,,ûύǶ״,ҪĿռϵ,Լͼνпռϵƥ,ųռϵƥͼ,ʣµͼƶȴӴСظû.ϵͳͼͼ3ʾ.

Fig.3System flow chatr
ͼ3ϵͳͼ
ĵ1״ԵĶ.2ۿռϵıʾƥ,öάϴʾ״֮ռϵķ,˿ռϵƥ㷨.3ۻ״ͼ㷨.4ھй˽һ̽. 
1״ԵĶ
ܼ״nf1,f2,...,fn,Щܳص,㷽Ĳ,ɲοͨͼ,ף6.X=fX1,fXn,...,fXnʾ״XnΪfX1,fXn,...,fXn.A=fA1,fAn,...,fAnB=fB1,fBn,...,fBn,ǿµdisf(A,B)̻ƶSimilarf(A,B)

Цi(i=1,...,n)ΪԤȷĳ,ӳÿҪ̶.disf(A,B)ԽС,ʾSimilarf(A,B)Խ.
Ϊ,״֮Զ״ԶĹؼ.֮ƶ.ļ,һ㶼Ƶķ.,Ǻҵ̻״ʵ,ѡȡ,ɱػֲͬ״мȵ,ʱнϴ.ΪõΪȷSimilarf(A,B),ģαķ,÷Ƕף5еķļ,䲽£
(1) ״Aʾ,ѡȡʵʽ.һ򵥵ķ,AȾ
,ָΪߵĿƵ.ٶƵΪck(k=1,2,...,l),C=(c1,c2,...,ck),CԻSĲ̱ʾΪ(C,S),䳤ΪL(C).ߦ(C,S)Ϊģ,Ϊ

Ц,ΪȨֵ,ΪBend;E1E2ģ;Ext(C,S)dSΪ.,ȡExt(C,S)=e-Kd2(C,S)d(C,S)Ϊ(C,S)ϵĵ㵽״Bľ,KΪԤȷĳ.ʽǶף7еʽ˺ܴĸĽ֮õ.,μף8.
(2) Aƽʵת,ѡȡʹE3λΪAʼαĳʼλ.
(3) ڲC,Aα,ʹE(C)ﵽС.
(4) E3/L(C)Ϊƥƶ.ϸ㷨йʵμף5.
2ռϵıʾƥ
Ϊ״Ϧ=A1,A2,...,AnĿռϵ,ǽ״XYͶӰ,XYϷֱõϴX1X2...XsY1Y2...Yt,ͼ4ʾ.
X1X2...Xsʣ
(1),˵,Xi(i=1,2,...,s)ǼϣA1,A2,...,Anһ.
(2) (A1x-Ajx,AiXp,AjXq,XpXq,УAixʾAiXϵͶӰX,Ԥȷĳ.һʱ,״ͶӰʱ,ӦΪͬһ,Ҫǿǵ,ʵʼʱ,Ĵ.
(3) AkXi,AlXj,ij,AkxAlx.
Y1Y2YtҲƵ.
ϴ,ǿԷ״ϸԪ֮Կռϵ.
״Ϧ1A1,A2,,An릸2B1,B2,,Bn,ڶӦ,ʹFX1iX2i,FY1iY2i,Ʀ1릸2ͬԿռϵ.ʱ,ǻԶǵĽṹΪdisF1,2dAi,AjʾAiAj֮ľ.disF1,2ԿǶԦ1릸2ľԿռϵƶȵһֶʽ,disF1,2ԽС,1릸2ĿռṹԽ.
,ռϵƥ,Ϊȷ,ʵ˵.
ûƽϻA,B,C,D4״,ͼ4ʾ,ͼеĳͼļ״ͼ5ʾ,,ͨ״Լ,ȷƥϵA1,B2,3,C4,6,D5,ǵǣͼ5Ƿ״Ӽa,b,c,d1,2,3,4,5,6,ʹAa,Bb,Cc,Dd,ңa,b,c,dA,B,C,DͬԿռϵͼ5ɼ,һĴa=1,b=2,c=4,d=5.

Fig.4Representation of spatial relationship
ͼ4ռϵıʾ

Fig.5Example for spatial relation matching
ͼ5ռϵƥ
һ,ǵ.
֪: 1A1,A2,...,An,2B1,B2,...,Bm,AiSi(i=1,2,...,n,Si2),
: ai(i=1,2,...,n),ʹaiSi(i=1,2,...,n),ӳAiai֮,a1,a2,...,anA1,A2,...,AnͬԿռϵ.
һ,Ǹ㷨.


Ȼ,ʵͼռϵ,ķ,һĹϵͼƥ䷽.
3״㷨
ڹϵݿṩһЩܺõļ,,ǽ⡢״⡢ͼֱùϵݿ,ṹֱǣ
Feature database١Shape databaseڡImage database
Shape no.Feature 1...Feature n Shape no.Shape dataImage no.Image no.Image data
,״,ͼ,״,,״,ͼ,ͼ.
йֶ˵£ǰдͼȡļ״ͳһ,ÿ״һΨһ״ţΪ˼ӿٶ,ÿ״״ݱֿ,״ݿ״BMPͼΣͼҲͳһ,ÿͼһΨһͼţÿ״,ҪһͼűǴһͼȡ.
ûṩ״Ϊ1A1,A2,...,An,¼㷨.
Step 0. ״1A1,A2,...,An,ȷ01.
Step 1. ÿһAi(i=1,2,...,n):
Step 1.1. ȡAi.
Step 1.2. ShapeNoiAidisfСڦ0ļ¼״.
Step 1.3. ImageNoiΪռ.
Step 1.4. ShapeNoiеÿ״Sj:
Step 1.4.1. ģαķȷAiƶSimilarf.
Step 1.4.2. Similarfڦ1,ͼѡȡ״ΪSjͼ,䲢뼯ImageNoi,,ShapeNoiȥSj.
Step 1.5. ʶӳAiShapeNoi.
Step 2. .
Step 3. ImageNoImageNoA1,A2,...,AnͬԿռϵͼ.
Step 4. ImageNoΪռ,ʵ0٦1,תStep 1.
Step 5. ImageNoеÿͼ,A1,A2,...,AnĽṹ,ṹС˳һͼ.
һڻ״вҩͼʵϵͳ,ϵͳ400ͼ,Ӧʱ2.̷Ϊ3׶ΣStep 1.2ǻĳStep 1.4Ǽ,Step 3ǿռϵƥ.ͼ,ֻӰStep 1.2,һ׶Ǹм,Ӧʱ䲻̫Ӱ.
4ᡡ
ʵ,ǵķнϸߵļٶ.ͬʱ,ڲģƥ䷽,Ҳ֤˽ϸߵļ.
ڻ״ļ,Чشͼȡ״,ЩǾ״ǻ״.Լ,һʮѵ.,ضӦ,ǿȽһڼı׼״,һµͼͼʱ,ñԵȡ9ݻָ10ݵȷȡ,Ȼ,ѱ׼״е״ģ,Ӧģƥ䷽5,ҳĿڼļ״.õķ.
ͬʱ,Ϊ,ÿһͼ񶼿û״ķм.һЩ״Եͼ,Ͳû״ķм.ҪһʵõĻ״ͼϢϵͳϵͳ,뽫֪ѧӾݿ⼼лؽ,⽫һѶ11,12.
оõȻѧ(No.69790080)͹863߿ƼĿ(No.863-317-9604-05)
йѧԺ㼼о100080
ʷֲйѧԺ㼼о100080
ο
1Grosky W I, Mehrotra R. Index-Based object recognition in pictorial data management. Computer Vision, Graphics, and Image Processing, 1990,52(3):416436
2Mehrotra R, Gary J. Similar shape retrieval in shape data management. IEEE Computer, 1995,28(9):5762
3Alberto Del Bimbo, Pietro Pala. Visual image retrieval by elastic matching of user sketches. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1997,19(2):121132
4Jain A K, Yu Zhong, Scridhar Lakshmanan. Object matching using deformable templates. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1996,18(3):267278
5Liu Ji-min, Wang Wei, Shi Zhong-zhi. A new deformable template matching method. Chinese Journal of Computers, 1999,22(4):1519
(,ΰ,ʷֲ.һµıģƥ䷽.ѧ,1999,22(4):1519)
6Xu Jian-hua. Image Processing and Analysis. Beijing: Science Press, 1992
(콨.ͼ.:ѧ,1992)
7Michael Kass. Snake: an active contour models. In: Proceedings of the International Conference on Computer Vision. London, 1987. 259268
8Cohen F S, Wang Jin-yinn. Part : modeling image curves using invariant 3-D object curve modelsa path to 3-D recognition and shape estimation from image contours. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1994,16(1):112
9Canny J. A computational approach to edge detection. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1986,8(6):679698
10Zhu S C, Yuille A. Region competition: unifying snakes, region growing, and bayes/MDL for multiband image segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1996,18(9):884900
11Forsyth D, Malik J, Wilensky R. Digital image retrieval. Sciences, 1997,(10):4954
(Forsyth D, Malik J, Wilensky R.ͼ.ѧ,1997,(10):4954)
12Strix C. Image retrieval on the Web. Sciences, 1997,(7):1416
(Stix C.άѰͼ.ѧ,1997,(7):1416)
1998-10-12ո
1999-02-09޸
