基于形状上下文的现场足迹比对算法研究
|
摘要
犯罪现场留下的足迹图像,为法庭提供了有价值的证据,是公安部门侦破过程的一个重要环节。现场足迹的模糊性、残缺性以及光照不均等特点给快速、准确地进行足迹图像的分析与匹配提出了很大的挑战。足迹识别算法大都需要进行调整或者分类,影响了识别的速度与精度。刑事案件侦破需要足迹识别算法针对足迹图像的特点,能够快速而且准确地识别出待比对图像。
针对现场足迹的特点,本文提出并实现了基于Canny的足迹边缘检测算法以及基于形状上下文的足迹比对算法。首先对原始的足迹图像进行灰度转换;然后以Canny算子为基础,使用高斯平滑抑制噪声,在二维高斯偏导卷积得到梯度边缘方向后由非极大值抑制和动态阈值边缘连接实现足迹边缘检测;最后对边缘进行采样后建立极坐标系得到现场足迹每个点的形状表达,并进行归一化处理,通过计算检索足迹和待比对足迹的形状上下文距离获取其相似度,实现足迹图像的比对与识别。基于形状上下文的足迹比对算法满足平移,旋转,缩放的不变性,提高了现场足迹比对的准确度、效率。
通过实验及实验结果的分析,验证了基于Canny的现场足迹边缘检测算法不仅能够抑制噪声,而且能有效地保持边缘。
Shoeprints found at crime scenes provide valuable forensic evidence, and is also an important part in judicial investigations. Due to the characteristics of vagueness, incompleteness and uneven brightness, it is a great challenge to analyze and match among shoeprints. The speed and precision of recognition are affected because previous shoeprints recognition algorithms are mostly needed to be classified or to be adjusted. The detection of criminal cases requires that recognition algorithm must aim to the characteristics of shoeprints and be able to quickly and accurately identify the matched shoeprints.
In the light of the characteristics of shoeprints, edge detection based on canny operator and matching algorithm based on shape context are proposed in this paper. Firstly make a gray-scale conversion to original shoeprint; then on the basis of canny operator, suppressing noise using Gaussian mask, calculating gradient and edge direction with convolution of derivative of two-dimensional Gaussian, non-maximum suppression and dynamic threshold and linking edge, implement edge detection of shoeprints; finally establishing polar coordinate system to obtain shape representation of every sample point which are sampled from the detected edge, normalizing, the measurement of similarity is got by computing the distance between the shape context of query shoeprint and that of matched one, achieve matching and identification of shoeprints. The proposed matching algorithm based on shape context not only satisfies the invariance to translation, scale and rotation, but also improves accuracy and efficiency of shoeprints matching on the scene.
A large number of experiences were carried out and experimental results were analyzed, edge detection based on canny operator can not only to eliminate noise, but also preserves the edges and details of images effectively.
针对现场足迹的特点,本文提出并实现了基于Canny的足迹边缘检测算法以及基于形状上下文的足迹比对算法。首先对原始的足迹图像进行灰度转换;然后以Canny算子为基础,使用高斯平滑抑制噪声,在二维高斯偏导卷积得到梯度边缘方向后由非极大值抑制和动态阈值边缘连接实现足迹边缘检测;最后对边缘进行采样后建立极坐标系得到现场足迹每个点的形状表达,并进行归一化处理,通过计算检索足迹和待比对足迹的形状上下文距离获取其相似度,实现足迹图像的比对与识别。基于形状上下文的足迹比对算法满足平移,旋转,缩放的不变性,提高了现场足迹比对的准确度、效率。
通过实验及实验结果的分析,验证了基于Canny的现场足迹边缘检测算法不仅能够抑制噪声,而且能有效地保持边缘。
Shoeprints found at crime scenes provide valuable forensic evidence, and is also an important part in judicial investigations. Due to the characteristics of vagueness, incompleteness and uneven brightness, it is a great challenge to analyze and match among shoeprints. The speed and precision of recognition are affected because previous shoeprints recognition algorithms are mostly needed to be classified or to be adjusted. The detection of criminal cases requires that recognition algorithm must aim to the characteristics of shoeprints and be able to quickly and accurately identify the matched shoeprints.
In the light of the characteristics of shoeprints, edge detection based on canny operator and matching algorithm based on shape context are proposed in this paper. Firstly make a gray-scale conversion to original shoeprint; then on the basis of canny operator, suppressing noise using Gaussian mask, calculating gradient and edge direction with convolution of derivative of two-dimensional Gaussian, non-maximum suppression and dynamic threshold and linking edge, implement edge detection of shoeprints; finally establishing polar coordinate system to obtain shape representation of every sample point which are sampled from the detected edge, normalizing, the measurement of similarity is got by computing the distance between the shape context of query shoeprint and that of matched one, achieve matching and identification of shoeprints. The proposed matching algorithm based on shape context not only satisfies the invariance to translation, scale and rotation, but also improves accuracy and efficiency of shoeprints matching on the scene.
A large number of experiences were carried out and experimental results were analyzed, edge detection based on canny operator can not only to eliminate noise, but also preserves the edges and details of images effectively.
引文
1.闫旭琴.自动足迹分析与比对系统中的关键技术的研究与实现[D].青岛:山东科技大学,2007:1-3.
2.牛瑞娟.足迹特征提取与分类[D].青岛:山东科技大学,2007:1-3.
3.吴志军.鞋底花纹比对与分析系统的设计与实现[D].大连:大连海事大学,2004:1-6,17-20.
4.G.Alexandre,"Computerized classification of the shoeprints of burglar soles",Forensic Science International,Volume 82,1996:59-65.
5.N.Sawyer,SHOE-FIT A computerised shoeprint database,Proc.European Convention on Security and Detection,1995,p86-89.
6.W.Ashley,What shoe was that? The use of computerised image database to assist in identification,Forensic Science Int.,82(1),1996,p7-20.
7.Z.Geradts and J.Keijzer,The image-database REBEZO for shoeprints with developments on automatic classification of shoe outsole designs,Forensic Science Int.,82,1996,p21-31.
8.A.Bouridane,A.Alexander,M.Nibouche and D.Crookes,Application of fractals to the detection and classification of shoeprints,Proc.2000 Int.Conf.Image Processing,1,2000,p474-477.
9.A.Alexander,A.Bouridane and D.Crookes,Automatic classification and recognition of shoeprints,Proc.Seventh Int.Conf.Image Processing and Its Applications,2,1999,p638-641.
10.P.de Chazal,J.Flynn and R.B.Reilly,Automated processing of shoeprint images based on the Fourier Transform for use in forensic science,IEEE Trans.Pattern Analysis &Machine Intelligence,27(3),2005:341-350.
11.L.Zhang and N.Allinson,Automatic shoeprint retrieval system for use in forensic investigations,UK Workshop On Computational Intelligence(UKCI05),2005.
12.柯少卿.足迹分块分类的研究[D].大连:大连海事大学,2006:1,11-16.
13.刘健康.足迹图像处理方法研究[D].大连:大连海事大学,2006:1-7.
14.Swain M.J.,Ballard D.H.Color indexing[J].International Journal of Computer Vision,1991,7(1):11-32.
15.管燕.基于形状特征的平面足迹图像检索的研究[D].扬州:扬州大学,2008:7-10.
16.庄越挺,潘云鹤,吴飞编著.网上多媒体信息分析与检索[M].北京:清华大学出版社,2002.
17.章毓晋著.基于内容的视觉信息检索[M].北京:科学出版社,2003.
18.崔屹编著.图像处理与分析.数学形态学方法及应用[M].北京:科学出版社,2000.
19.Milan Sonka,Vaclay Hlavac,Roger Boyle著.艾海舟,武勃等译.图像处理、分析与机器视觉[M].北京:人民邮电出版社.2003.
20.Nikolaoua N.,Papammarkos N.Color Image Retrieval Using a Fractal Signature Extraction Technique[J].Engineering Applications of Artificial Intelligence,2002,15:81-96.
21.Miroslaw Bober.MPEG-7 Visual Shape Descriptors[J].IEEE Transaction on Circuits and Systems for Video Technology,2001,11(6).
22.Kaushik Chakrabarti,Michael Ortega-Binderberger,Kriengkrai Porkaew,Peng Zuo,Sharad Mehrotra.Similar Shape Retrieval in MARS[A].In IEEE Int.Conf.on Multimedia and expo(ICMEII)[C],New York,NY,USA.pages 709-712,2000.
23.Del Bimbo A.,Pala P.Shape Indexing by Multi-scale Representation[J].Image and Vision Computing 1999,17:245-261.
24.Mokhtarian F.,Abbasi S.and Kittler J.Efficient and Robust Retrieval by Shape content through Curvature Scale Space[A].Int.Workshop on Image Databases and Multimedia Search[C],Amsterdam,The Netherlands,1996:35-42.
25.Ahmet Latif Ametl.Texture Defect Detection Using Subband Domain Co-Occurrence Matrices[J].Image Analysis and Interpretation,Apr 1998,4:205-210.
26.Dorin Comanieiu,Peter Meer,David Tyler.Dissimilarity computation through low rank corrections[J].Pattern Recognition Letters,2003,24:227-236.
27.阮秋琦编著.数字图像处理学[M].北京:电子工业出版社,2000.
28.陈十金,汤漾平,邓勇.基于链码的轮廓跟踪技术在二值图像中的应用[J].华中理工大学学报,1998,26(12):25-28.
29.Yang L.,Algregtsen F.Fast computation of invariant geometric moments:A new method giving current results[A].In:Proc IEEE Int Conf on Image Processing[C],1994,21(6):131-142.
30.Deepak Kapur,Lakshman Y.N.,Tushar Saxena.Computing invariants using elimination methods[A].In:Proc IEEE Int Confon Image roc[C],1995,23(1):23-42.
31.David Copper,Zhibin Lei.On representation and invariant recognition of complexobje series:Hebert M,Jponce,Boult T,Gross A eds.3D Object Representation for Computer Vision[C],New York,1995,139-153.cts based on patches and parts[A].In:Springer Lecture Notes in Computer Science
32.Chen C.C.Improved moment invariants for shape discrimination[J].Pattern Recognition,1993,26(5):683-686.
33.何斌,马天予,王运坚.VisualC++数字图像处理[M].北京:人民邮电出版社,2002:7-8.
34.庄越挺,潘云鹤,吴飞编著.网上多媒体信息分析与检索[M].北京:清华大学出版社,2002.
35.Dorin Comaniciu,Peter Meer,David Tyler.Dissimilarity Computation Through Low Rank Corrections[J].Pattern Recognition Letters,2003,24:227-236.
36.Horst Eidenberger.Distance Measures for MPEG-7-based Retrieval.http://www.ims.tuwien.ac.at/medialdocuments/publications/mir2003.pdf.
37.Minh N.Doy and Martin Vetterli.Texture Similarity Measurement Using Kullback-Leibler Distance on Wavelet Subbands.http://lcavwww.epfl.ch/～minhdo/publications/1CIP2000_texture.pdf.
38.Vittorio Castelli.Multidimensional Indexing Structures for Content-based Retrieval[R].IBM Research Report,2001,2.
39.Stefano Berretti,Alberto Del Bimbo,and Pietro Pala.Retrieval by Shape Similarity with Perceptual Distance and Effective Indexing[J].IEEE Transactions Multmedia,2000,2(4).
40.Arnold W.M.,Marcel W.,Simone S.,et al.Content-based Image Retrieval at the end of the Early Years[J].IEEE Trans.On PAMI,2000,22(12):1349-1379,
41.Manjunath B.S.,Ohm J.R.,Vasudenvan V.V.,et al.Color and Texture Descriptors[J].IEEE Trans.On CSVT.,2001,11(6):703-715.
42.Mehtre B.M.,Kankallllalli M.S.,Narasimhalu A.D.,Color Matching for Image Retrieval[J].Pattern Recognition Letters,1995,16:325-331.
43.Hsieh I.S.,Fan K C.,Multiple Classifiers for Color Flag and Trademark Image Retrieval[J].IEEE Trans.On Image Processing,2001,10(6):938-950.
44.Jain A.K.,Vailaya A.,Shape-based Retrieval:a case study with trademark image databases[J].Pattern Recognition,1998:31(9):1369-1390.
45.李向阳,庄越挺,潘云鹤.基于内容的图像检索技术与系统[J].计算机研究与发展,2001,3(38).
46.章毓晋著.基于内容的视觉信息检索[M].北京:科学出版社,2003.
47.甘勇,马芳,熊坤等.基于遗传算法和梯度算子的图像边缘检测[J].微计算机信息,2007,32(2):306-308.
48.薛文格,邝天福.图像边缘检测方法研究[J].电脑知识与技术,2007(24):246-248.
49.冈萨雷斯,伍兹,艾丁斯.数字图像处理:MATLAB版[M].北京:电子工业出版社,2005:289-296
50.MORA Marco,Sbaro Danie.A Robust Footprint Detection Using Color Images and Neural Networks Lecture Notes in Computer Science,2005(3773):311-318
51.白雪。足迹比对算法的研究与实现[D],中国农业大学硕士论文,2007.
52.杨姝,史力民,王彩荣,高立群.基于二维阈值向量分割的足迹边缘提取方法[J].东北大学学报(自然科学版).2005,25(3):216-218.
53.葛雯,高立群.基于非张量积小波变换的足迹边缘提取算法[J].计算机安全,2008,7(3):5-9.
54.Canny John.A Computational Approach to Edge Detection[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,1986,PAMI-8(6):679-698.
55.Worthington,P.L.Enhanced Canny edge detection using curvature consistency[C].2002Proceedings.16th International Conference on Pattern Recognition,2002,1(11):596-599.
56.王植,贺赛先.一种基于Canny理论的自适应边缘检测方法[J].中国图像图形学报,2004,9(8):957-961.
57.王娜,李霞.一种新的改进Canny边缘检测算法[J].深圳大学学报,2005,22(2):149-153.
58. .Belongie, S., Malik, J., J.Puzicha: Shape matching and object recognition using shape contexts. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2002,24(24),p509-522.
2.牛瑞娟.足迹特征提取与分类[D].青岛:山东科技大学,2007:1-3.
3.吴志军.鞋底花纹比对与分析系统的设计与实现[D].大连:大连海事大学,2004:1-6,17-20.
4.G.Alexandre,"Computerized classification of the shoeprints of burglar soles",Forensic Science International,Volume 82,1996:59-65.
5.N.Sawyer,SHOE-FIT A computerised shoeprint database,Proc.European Convention on Security and Detection,1995,p86-89.
6.W.Ashley,What shoe was that? The use of computerised image database to assist in identification,Forensic Science Int.,82(1),1996,p7-20.
7.Z.Geradts and J.Keijzer,The image-database REBEZO for shoeprints with developments on automatic classification of shoe outsole designs,Forensic Science Int.,82,1996,p21-31.
8.A.Bouridane,A.Alexander,M.Nibouche and D.Crookes,Application of fractals to the detection and classification of shoeprints,Proc.2000 Int.Conf.Image Processing,1,2000,p474-477.
9.A.Alexander,A.Bouridane and D.Crookes,Automatic classification and recognition of shoeprints,Proc.Seventh Int.Conf.Image Processing and Its Applications,2,1999,p638-641.
10.P.de Chazal,J.Flynn and R.B.Reilly,Automated processing of shoeprint images based on the Fourier Transform for use in forensic science,IEEE Trans.Pattern Analysis &Machine Intelligence,27(3),2005:341-350.
11.L.Zhang and N.Allinson,Automatic shoeprint retrieval system for use in forensic investigations,UK Workshop On Computational Intelligence(UKCI05),2005.
12.柯少卿.足迹分块分类的研究[D].大连:大连海事大学,2006:1,11-16.
13.刘健康.足迹图像处理方法研究[D].大连:大连海事大学,2006:1-7.
14.Swain M.J.,Ballard D.H.Color indexing[J].International Journal of Computer Vision,1991,7(1):11-32.
15.管燕.基于形状特征的平面足迹图像检索的研究[D].扬州:扬州大学,2008:7-10.
16.庄越挺,潘云鹤,吴飞编著.网上多媒体信息分析与检索[M].北京:清华大学出版社,2002.
17.章毓晋著.基于内容的视觉信息检索[M].北京:科学出版社,2003.
18.崔屹编著.图像处理与分析.数学形态学方法及应用[M].北京:科学出版社,2000.
19.Milan Sonka,Vaclay Hlavac,Roger Boyle著.艾海舟,武勃等译.图像处理、分析与机器视觉[M].北京:人民邮电出版社.2003.
20.Nikolaoua N.,Papammarkos N.Color Image Retrieval Using a Fractal Signature Extraction Technique[J].Engineering Applications of Artificial Intelligence,2002,15:81-96.
21.Miroslaw Bober.MPEG-7 Visual Shape Descriptors[J].IEEE Transaction on Circuits and Systems for Video Technology,2001,11(6).
22.Kaushik Chakrabarti,Michael Ortega-Binderberger,Kriengkrai Porkaew,Peng Zuo,Sharad Mehrotra.Similar Shape Retrieval in MARS[A].In IEEE Int.Conf.on Multimedia and expo(ICMEII)[C],New York,NY,USA.pages 709-712,2000.
23.Del Bimbo A.,Pala P.Shape Indexing by Multi-scale Representation[J].Image and Vision Computing 1999,17:245-261.
24.Mokhtarian F.,Abbasi S.and Kittler J.Efficient and Robust Retrieval by Shape content through Curvature Scale Space[A].Int.Workshop on Image Databases and Multimedia Search[C],Amsterdam,The Netherlands,1996:35-42.
25.Ahmet Latif Ametl.Texture Defect Detection Using Subband Domain Co-Occurrence Matrices[J].Image Analysis and Interpretation,Apr 1998,4:205-210.
26.Dorin Comanieiu,Peter Meer,David Tyler.Dissimilarity computation through low rank corrections[J].Pattern Recognition Letters,2003,24:227-236.
27.阮秋琦编著.数字图像处理学[M].北京:电子工业出版社,2000.
28.陈十金,汤漾平,邓勇.基于链码的轮廓跟踪技术在二值图像中的应用[J].华中理工大学学报,1998,26(12):25-28.
29.Yang L.,Algregtsen F.Fast computation of invariant geometric moments:A new method giving current results[A].In:Proc IEEE Int Conf on Image Processing[C],1994,21(6):131-142.
30.Deepak Kapur,Lakshman Y.N.,Tushar Saxena.Computing invariants using elimination methods[A].In:Proc IEEE Int Confon Image roc[C],1995,23(1):23-42.
31.David Copper,Zhibin Lei.On representation and invariant recognition of complexobje series:Hebert M,Jponce,Boult T,Gross A eds.3D Object Representation for Computer Vision[C],New York,1995,139-153.cts based on patches and parts[A].In:Springer Lecture Notes in Computer Science
32.Chen C.C.Improved moment invariants for shape discrimination[J].Pattern Recognition,1993,26(5):683-686.
33.何斌,马天予,王运坚.VisualC++数字图像处理[M].北京:人民邮电出版社,2002:7-8.
34.庄越挺,潘云鹤,吴飞编著.网上多媒体信息分析与检索[M].北京:清华大学出版社,2002.
35.Dorin Comaniciu,Peter Meer,David Tyler.Dissimilarity Computation Through Low Rank Corrections[J].Pattern Recognition Letters,2003,24:227-236.
36.Horst Eidenberger.Distance Measures for MPEG-7-based Retrieval.http://www.ims.tuwien.ac.at/medialdocuments/publications/mir2003.pdf.
37.Minh N.Doy and Martin Vetterli.Texture Similarity Measurement Using Kullback-Leibler Distance on Wavelet Subbands.http://lcavwww.epfl.ch/～minhdo/publications/1CIP2000_texture.pdf.
38.Vittorio Castelli.Multidimensional Indexing Structures for Content-based Retrieval[R].IBM Research Report,2001,2.
39.Stefano Berretti,Alberto Del Bimbo,and Pietro Pala.Retrieval by Shape Similarity with Perceptual Distance and Effective Indexing[J].IEEE Transactions Multmedia,2000,2(4).
40.Arnold W.M.,Marcel W.,Simone S.,et al.Content-based Image Retrieval at the end of the Early Years[J].IEEE Trans.On PAMI,2000,22(12):1349-1379,
41.Manjunath B.S.,Ohm J.R.,Vasudenvan V.V.,et al.Color and Texture Descriptors[J].IEEE Trans.On CSVT.,2001,11(6):703-715.
42.Mehtre B.M.,Kankallllalli M.S.,Narasimhalu A.D.,Color Matching for Image Retrieval[J].Pattern Recognition Letters,1995,16:325-331.
43.Hsieh I.S.,Fan K C.,Multiple Classifiers for Color Flag and Trademark Image Retrieval[J].IEEE Trans.On Image Processing,2001,10(6):938-950.
44.Jain A.K.,Vailaya A.,Shape-based Retrieval:a case study with trademark image databases[J].Pattern Recognition,1998:31(9):1369-1390.
45.李向阳,庄越挺,潘云鹤.基于内容的图像检索技术与系统[J].计算机研究与发展,2001,3(38).
46.章毓晋著.基于内容的视觉信息检索[M].北京:科学出版社,2003.
47.甘勇,马芳,熊坤等.基于遗传算法和梯度算子的图像边缘检测[J].微计算机信息,2007,32(2):306-308.
48.薛文格,邝天福.图像边缘检测方法研究[J].电脑知识与技术,2007(24):246-248.
49.冈萨雷斯,伍兹,艾丁斯.数字图像处理:MATLAB版[M].北京:电子工业出版社,2005:289-296
50.MORA Marco,Sbaro Danie.A Robust Footprint Detection Using Color Images and Neural Networks Lecture Notes in Computer Science,2005(3773):311-318
51.白雪。足迹比对算法的研究与实现[D],中国农业大学硕士论文,2007.
52.杨姝,史力民,王彩荣,高立群.基于二维阈值向量分割的足迹边缘提取方法[J].东北大学学报(自然科学版).2005,25(3):216-218.
53.葛雯,高立群.基于非张量积小波变换的足迹边缘提取算法[J].计算机安全,2008,7(3):5-9.
54.Canny John.A Computational Approach to Edge Detection[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,1986,PAMI-8(6):679-698.
55.Worthington,P.L.Enhanced Canny edge detection using curvature consistency[C].2002Proceedings.16th International Conference on Pattern Recognition,2002,1(11):596-599.
56.王植,贺赛先.一种基于Canny理论的自适应边缘检测方法[J].中国图像图形学报,2004,9(8):957-961.
57.王娜,李霞.一种新的改进Canny边缘检测算法[J].深圳大学学报,2005,22(2):149-153.
58. .Belongie, S., Malik, J., J.Puzicha: Shape matching and object recognition using shape contexts. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2002,24(24),p509-522.