支持隐私保护的图像内容检测技术研究

目录TOC\o"1-3"\h\u1.绪论 第一章绪论1.1研究背景及意义随着成像传感器和互联网技术的飞速发展，图像数据的种类和数量与日俱增，如何从海量的图像库中快速且准确的找到满足用户需求的图像成为当前研究的热点[[]XiaZ,XiongNN,VasilakosAV,etal.EPCBIR:Anefficientandprivacy-preservingcontent-basedimageretrievalschemeincloudcomputing[J].InformationSciences,2017,387:195-204][]XiaZ,XiongNN,VasilakosAV,etal.EPCBIR:Anefficientandprivacy-preservingcontent-basedimageretrievalschemeincloudcomputing[J].InformationSciences,2017,387:195-204图像检索可以从检索方法上分为两类：基于文本的图像检索（Text-basedImageRetrieval，简称TBIR）和基于内容的图像检索（Content-basedImageRetrieval，简称CBIR）。在图像存储量还不是很大的时候，主要采用方法的是基于文本的图像检索。基于文本的图像检索算法通过手动注释来表示图像的内容，并通过搜索表示图像的关键字来查询与关键字相似的图像实现检索功能。它将图像的内容用注释关键词的方式表达出来，图像的内容采用人工的方式进行注释[[]PutriRD,PrabawaHW,WihardiY.Colorandtexturefeaturesextractiononcontent-basedimageretrieval[C]//InternationalConferenceonScienceinInformationtechnology.2017:711-715]。虽然通过关键字查找的查准率较高，但如果图像数据库中存在海量的图像数据时，使用人工的方式注释这些图像的关键字很难，而且图像的概念高于描述图像的系列文本单词，无法用文本实现对图像完全准确的描述，手动索引的方式既耗时又耗人力。基于内容的图像检索由机器自动提取包含图像内容的颜色[[]JainAK,VailayaA.ImageRetrievalUsingColorandShape[J].PatternRecognition,1997,29(8):1233-1244.]、纹理[[]MaWY,ZhangHJ.BenchmarkingofImageFeaturesforContent-basedRetrieval[C]//The32AsilomarConferenceonSignals,Systems&Computers.LosAlamitos:IEEE,1998:253-257.]、形状[[[]PutriRD,PrabawaHW,WihardiY.Colorandtexturefeaturesextractiononcontent-basedimageretrieval[C]//InternationalConferenceonScienceinInformationtechnology.2017:711-715[]JainAK,VailayaA.ImageRetrievalUsingColorandShape[J].PatternRecognition,1997,29(8):1233-1244.[]MaWY,ZhangHJ.BenchmarkingofImageFeaturesforContent-basedRetrieval[C]//The32AsilomarConferenceonSignals,Systems&Computers.LosAlamitos:IEEE,1998:253-257.[]LoncaricS.ASurveyofShapeAnalysisTechniques[J].PatternRecognition,1998,31(8):983-1001.随着云计算技术的快速发展，数据外包服务已经成为一种新兴的服务模式，数据外包服务能够利用服务提供商专业的技术和资源对海量数据提供存储、计算及使用等服务。数据拥有者（DataOwner，简称DO）将自身的图像数据外包给服务提供商（ServiceProvider，简称SP）(例如：Google，百度云等服务提供商)进行专业、高效的存储管理，这使得图像拥有者从繁重的数据管理任务中解脱出来，同时由于SP专业高效的管理机制，也降低了数据拥有者的数据管理成本。在图像检索时必定存在图像传输的过程，攻击者很容易在图像在存储和检索过程中窃取到图像信息，导致图像的隐私泄露。当图像拥有者在云服务器中存储大量图像时，图像拥有者就会失去对图像的直接控制权，导致图像信息的泄露，如何确保图像的完整性和安全性成为了现在研究的难点和重点[[]HuangRW,GuiXL,YuS,etal.StudyofPrivacy-preservingFrameworkforCloudStorage[J].ComputerScienceand[]HuangRW,GuiXL,YuS,etal.StudyofPrivacy-preservingFrameworkforCloudStorage[J].ComputerScienceandInformationSystems,2011,8(3):801-819.对于数据外包而言，数据拥有者最关心的是服务质量和数据安全即数据的隐私问题，因为自身的数据内容交由并不完全可信的SP运营，因此，数据拥有者的数据不能直接暴露给云平台，而用户发送的查询和查询结果因为有可能泄露用户隐私，也不能暴露给云平台。在各种图像数据包含了各种各样的用户个人隐私信息，这些个人隐私的泄露可能会给用户带来无法估量的负面影响。存储在服务器端的用户隐私数据也存在着被窃取、泄露和篡改的巨大风险。由于内外部的利益驱动，会发生一些数据泄露的问题，这使云服务器面临信任危机，也成为制约云计算技术进一步发展和实施的关键因素。加密是保护图像内容安全的一个有效手段，现有的图像检索技术却无法对加密后的图像直接进行检索，简单的做法是数据拥有者将图像上传给云服务器之前对图像进行加密，在需要进行查询时，用户需要下载全部的加密数据并解密之后进一步使用，当存储在云端的加密数据形成一定规模时，这种方式的效率非常低。因此，密文高效检索成为需要解决的问题。本文在隐私保护这一需求上，开展了隐私保护海量图像检索关键技术的研究。有些局部特征虽然能够较好的处理局部特征点，得到较为满意的匹配结果。但是也存在运算速度慢、特征点数量和感兴趣区域存在较大相关性、不同图像特征点数量出入较大的问题。在基于隐私保护的基础中，提出一种获得较好的检索性能的图像检索算法。如何设计出一种安全有效的检索机制，即在保证不泄露用户隐私的前提下，准确、快速地检索出用户感兴趣的图像就成为目前图像搜索技术领域内需要重点解决的一个问题。因为每幅图像都包含大量的特征描述符，而这些特征描述符往往都是高维向量的形式，比如SIFT特征描述符是128维的向量，为图像安全检索带来了困难。本课题拟解决现有的解决方案存在的问题，比如，不支持数据及索引结构更新、计算复杂度大等，为外包数据库健康、快速地实施提供安全保障，促进云计算服务的进一步发展。用户喜欢能够同时提供智能和安全的图像检索这两种功能的系统，将图像检索外包到云上让云知道有关图像内容的任何信息。近年来，复杂的神经网络[[]ChiraagJuvekar,VinodVaikuntanathan,AnanthaChandrakasan.Gazelle:ALowLatencyFrameworkforSecureNeuralNetworkInference.In27thUSENIXSecuritySymposium,USENIXSecurity2018,Baltimore,MD,USA,August15--17,2018.1651--1669]（ConvolutionalNeuralNetworks，简称CNN）作为一类复杂而强大的机器学习模型，在许多图像检索任务中都表现出比人类更高的精度，如作为近似最近邻（ApproximateNearestNeighbor,简称ANN）搜索。一个预先训练的CNN可以作为一个特征提取器，用于智能和安全的图像检索，这要求两者都是安全的加法和乘法运算。完全同态加密技术，如基于格的方案可以有可能处理此类问题，但由于计算复杂度大。另一种方法是支持安全性的安全多方计算（[]ChiraagJuvekar,VinodVaikuntanathan,AnanthaChandrakasan.Gazelle:ALowLatencyFrameworkforSecureNeuralNetworkInference.In27thUSENIXSecuritySymposium,USENIXSecurity2018,Baltimore,MD,USA,August15--17,2018.1651--16691.2国内外研究现状1.2.1图像检索技术图像检索的发展历程包含了两个阶段：基于文本的图像检索和基于内容的图像检索。从20世纪70年代开始，有关图像检索的研究就已开始，当时主要是基于文本的图像检索技术，利用文本描述的方式描述图像的特征，如绘画作品的作者、年代、流派、尺寸等。到90年代以后，出现了对图像的内容语义，如图像的颜色、纹理、布局等进行分析和检索的图像检索技术，即基于内容的图像检索技术。在早期的图像检索中，由于成像设备的不完善，图像数量也不是很多，人们通过使用手动注释内容表示图像的内容，主要依靠关键字或文本描述图像，然后利用文本匹配进行查询。基于文本的图像检索方法事先需要对图像进行人工标注，但是，图像的概念要高于描述图像的一系列单词，人工标注的文本具有不充分、主观、费时费力等缺点，而随着时代的发展以及科技的进步，相机、摄像机等设备的增多，图像的数量也在呈倍数增加，此方案就会增加大量的人力物力，无法满足需求。基于内容的图像检索[[]MohamadzadehS,FarsiH.Content-basedimageretrievalsystemviasparserepresentation[J].IetComputerVision,2016,10(1):95-102]是当今社会一种主流的图像检索技术，是目前国内外研究者广泛关注的研究热点。CBIR检索技术的核心是描述图像内容的可视特征[[]Z.BrakerskiandV.Vaikuntanathan,"Fullyhomomorphicencryptionfromring-lweandsecurityforkeydependentmessages,"inProceedingsofthe31stAnnualConferenceonAdvancesinCryptology,ser.CRYPTO’11.Berlin,Heidelberg:Springer-Verlag,2011,pp.505–524.]提取，融合了图像理解和识别模式等技术，克服了传统基于文本检索方法的缺陷，具有很好的前景和应用价值。为了不断地完善图像检索技术，就需要对图像的特征进行更深入的研究，使得提取的特征既能够更加真实地反映人的主观认识，又方便表达和索引。2011年，吴建波等人[[]吴建波，赵建民，朱信忠，等.基于一种SIFT优化算法的图像检索[J].微型电脑应用，2011,27(5):4-7]提出了一种通过SIFT特征来进行图像检索的方法；2013年，Sulochana等人[[]SulochanaS,VidhyaR.TextureBasedImageRetrievalUsingFrameletTransform-GrayLevelCo-occurrenceMatrix(CLCM)[J].InternationalJournalofAdvancedResearchinArtificialIntelligence,2013,2(2)]通过采用提取纹理特征的方法称为灰度共生矩阵对图像进行检索；2017年，Rani[]MohamadzadehS,FarsiH.Content-basedimageretrievalsystemviasparserepresentation[J].IetComputerVision,2016,10(1):95-102[]Z.BrakerskiandV.Vaikuntanathan,"Fullyhomomorphicencryptionfromring-lweandsecurityforkeydependentmessages,"inProceedingsofthe31stAnnualConferenceonAdvancesinCryptology,ser.CRYPTO’11.Berlin,Heidelberg:Springer-Verlag,2011,pp.505–524.[]吴建波，赵建民，朱信忠，等.基于一种SIFT优化算法的图像检索[J].微型电脑应用，2011,27(5):4-7[]SulochanaS,VidhyaR.TextureBasedImageRetrievalUsingFrameletTransform-GrayLevelCo-occurrenceMatrix(CLCM)[J].InternationalJournalofAdvancedResearchinArtificialIntelligence,2013,2(2)[]RaniM,MishraPK.AnIMPROVEDCONTENTBASEDIMAGERETRIEVALAPPROACHUSINGLOCALBINARYPATTERN(LBP)[J].InternationalEducationalScientificResearchJournal,2017,3(4)[]LiuQing,XULuping,MAYiDe,al.ImageNMIFfeatureExtractionandRetrivalMethodBasedonPulseCoupledNeutralNetworks[J].ActaAutomaticaSinica,2010,36(7):931-938[]LiuP,GuoJM,ChamnongthaiK,etal.FusionofcolorhistogramandLBP-basedfeaturesfortextureimageretrievalandclassification[J].InformationSciences,2017,390:95-111基于内容的图像检索方法可以用来检索图像具有较大储存量的情况，它将图像如颜色，纹理，形状等特征提取出来进行分析，然后检索具有相似特征的图像。经过试验证明，CBIR有更高的检索准确率及效率。它的传统框图如下图1所示，数据所有者将自身的图像存储到数据库中，并建立图像本身的特征数据库。用户想要搜索与查询图像相似的图像，首先给数据库发送请求并将查询图像的特征作为搜索陷门，当数据库接收到请求后，根据请求采用相似性匹配算法计算关键图像特征与特征库中图像特征的相似度，然后按照相似度从大到小的顺序将匹配图像的检索结果反馈给用户，检索过程结束。图像特征库图像数据库查询图像预处理查询图像检索结果检索相似性匹配特征提取图1：CBIR基本框图图像特征库图像数据库查询图像预处理查询图像检索结果检索相似性匹配特征提取1.2.2图像加密技术伴随着云计算技术的发展，越来越多的研究者开始关注外包环境下安全的CBIR，他们也提出了一些安全的CBIR方案。这些方案可以分为：基于可搜索加密（SearchableSearchEncryption,SSE）的方案[[]Z.BrakerskiandV.Vaikuntanathan,"Fullyhomomorphicencryptionfromring-lweandsecurityforkeydependentmessages,"inProceedingsofthe31stAnnualConferenceonAdvancesinCryptology,ser.CRYPTO’11.Berlin,Heidelberg:Springer-Verlag,2011,pp.505–524]、基于同态加密的方案[[]Z.BrakerskiandV.Vaikuntanathan,"Fullyhomomorphicencryptionfromring-lweandsecurityforkeydependentmessages,"inProceedingsofthe31stAnnualConferenceonAdvancesinCryptology,ser.CRYPTO’11.Berlin,Heidelberg:Springer-Verlag,2011,pp.505–524[]P.ZhengandJ.Huang,"Anefficientimagehomomorphicencryptionschemewithsmallciphertextexpansion,"inProceedingsofthe21stACMInternationalConferenceonMultimedia,ser.MM’13.NewYork,NY,USA:ACM,2013,pp.803–812.[]Hyeong-IlKim,Hyeong-JinKimandJae-WooChang,"APrivacy-PreservingTop-kQueryProcessingAlgorithmintheCloudComputing,"inEconomicsofGrids,Clouds,Systems,andServices:13thInternationalConference,GECON2016,Athens,Greece,September20-22,2016,pp.277-292在文本检索中，可搜索加密技术是实现云存储安全的一项重要技术手段。在基于可搜索加密的解决方案下，DO建立一个安全的索引结构，并且把这个安全索引上传给云服务器，以此来实现安全并且高效的查询。2000年，Song等人[[]D.X.Song,D.Wagner,A.Perrig.Practicaltechniquesforsearchesonencrypteddata[C].IEEESymposiumonSecurityandPrivacy,2000:44–55.]最先引入了SSE方案，他们提出的方案允许通过关键词在加密的文档上进行查询。Wang[[]C.Wang,N.Cao,J.Li,K.Ren,andW.Lou,"Securerankedkeywordsearchoverencryptedclouddata,"inProceedingsofthe2010IEEE30thInternationalConferenceonDistributedComputingSystems,ser.ICDCS’10.Washington,DC,USA:IEEEComputerSociety,2010,pp.253–262.]、Curtmola[[]R.Curtmola,J.Garay,S.Kamara,andR.Ostrovsky,"Searchablesymmetricencryption:Improveddefinitionsandefficientconstructions,"JournalofComputerSecurity,vol.19,no.5,pp.895–934,Sep.2011.]以及Chase[[]M.ChaseandS.Kamara,"Structuredencryptionandcontrolleddisclosure,"inAdvancesinCryptology-ASIACRYPT2010,M.Abe,Ed.Berlin,Heidelberg:SpringerBerlinHeidelberg,2010,pp.577–594.]等人利用多种索引构建机制提高了搜索效率。随后，Cash[[]D.Cash,S.Jarecki,C.Jutla,H.Krawczyk,M.C.Ros¸u,andM.Steiner,"Highly-ScalableSearchableSymmetricEncryptionwithSupportforBooleanQueries,"SpringerBerlinHeidelberg,2013.]、Fisch[[]B.A.Fisch,B.Vo,F.Krell,A.Kumarasubramanian,V.Kolesnikov,T.Malkin,andS.M.Bellovin,"Malicious-clientsecurityinblindseer:Ascalableprivatedbms,"in2015IEEESymposiumonSecurityandPrivacy,May2015,pp.395–410.]等人的工作扩展了SSE方案，扩展的方案实现支持多个关键字的精确搜索和复杂的布尔运算。在实际搜索过程中可能会遇到的查询关键词拼写错误的问题，Li等人[[]J.Li,Q.Wang,C.Wang,N.Cao,K.Ren,andW.Lou,"Fuzzykeywordsearchoverencrypteddataincloudcomputing,"in2010ProceedingsIEEEINFOCOM,March2010,pp.1–5.]的工作提出的SSE方案支持模糊的关键字搜索，它可以解决上述问题。尽管可搜索加密技术可以直接扩展到TBIR中，但基于内容的图像检索与文本检索不同的，它没有预定义的范围，可搜索加密技术扩展到CBIR方案中具有一定的困难性。2009年，Lu等人[[[]D.X.Song,D.Wagner,A.Perrig.Practicaltechniquesforsearchesonencrypteddata[C].IEEESymposiumonSecurityandPrivacy,2000:44–55.[]C.Wang,N.Cao,J.Li,K.Ren,andW.Lou,"Securerankedkeywordsearchoverencryptedclouddata,"inProceedingsofthe2010IEEE30thInternationalConferenceonDistributedComputingSystems,ser.ICDCS’10.Washington,DC,USA:IEEEComputerSociety,2010,pp.253–262.[]R.Curtmola,J.Garay,S.Kamara,andR.Ostrovsky,"Searchablesymmetricencryption:Improveddefinitionsandefficientconstructions,"JournalofComputerSecurity,vol.19,no.5,pp.895–934,Sep.2011.[]M.ChaseandS.Kamara,"Structuredencryptionandcontrolleddisclosure,"inAdvancesinCryptology-ASIACRYPT2010,M.Abe,Ed.Berlin,Heidelberg:SpringerBerlinHeidelberg,2010,pp.577–594.[]D.Cash,S.Jarecki,C.Jutla,H.Krawczyk,M.C.Ros¸u,andM.Steiner,"Highly-ScalableSearchableSymmetricEncryptionwithSupportforBooleanQueries,"SpringerBerlinHeidelberg,2013.[]B.A.Fisch,B.Vo,F.Krell,A.Kumarasubramanian,V.Kolesnikov,T.Malkin,andS.M.Bellovin,"Malicious-clientsecurityinblindseer:Ascalableprivatedbms,"in2015IEEESymposiumonSecurityandPrivacy,May2015,pp.395–410.[]J.Li,Q.Wang,C.Wang,N.Cao,K.Ren,andW.Lou,"Fuzzykeywordsearchoverencrypteddataincloudcomputing,"in2010ProceedingsIEEEINFOCOM,March2010,pp.1–5.[]W.Lu,A.Swaminathan,A.L.Varna,andM.Wu,"Enablingsearchoverencryptedmultimediadatabases,"inProceedingsoftheSPIEmediaforensicsandsecurity:IS&T/SPIEelectronicimaging,vol.7254,SanJose,CA,January2009,pp.7254–7254–11.[]S.Wang,M.Nassar,M.Atallah,andQ.Malluhi,"Secureandprivateoutsourcingofshape-basedfeatureextraction,"inProc.ofICICS’13.Springer,2013,pp.90–99.[]B.Cheng,L.Zhuo,Y.Bai,Y.Peng,andJ.Zhang,"Secureindexconstructionforprivacy-preservinglarge-scaleimageretrieval,"in2014IEEEFourthInternationalConferenceonBigDataandCloudComputing,Dec2014,pp.116–120.[]KAPTHIKK,KASHYAPS.Transparenthashingintheencrypteddomainforpreservingimageretrieval[J].Signal,ImageandVideoProcessing,2013,7(4):647-664[]CHENGB,ZHOUL,BAIY,etal.Secureindexconstructionforprivacy-preservinglarge-scaleimageretrival[C]//ProcedingsofIEEEFourthInternationalConferenceonBigDataandCloud.Piscataway:IEEE,2014:116-120近年来，同态加密在检索方案中越来越通用，基于同态加密（HE）的方案[[]LUW,VARNAA,WUM.Confidentiality-preservingimagesearch:acomparativestudybetweenhomomorphicencryptionanddistance-preservingrandomization[J].IEEEAccess,2014,2:125–141.]是SSE的替代方案。在基于同态加密的方案中，用户通过利用同态密码系统（例如Paillier密码系统[[]P.Paillier,"Public-keycryptosystemsbasedoncompositedegreeresiduosityclasses,"inINADVANCESINCRYPTOLOGY–EUROCRYPT1999.Springer-Verlag,1999,pp.223–238.]、ElGammal密码系统[[]T.Elgamal.Apublickeycryptosystemandasignatureschemebasedondiscretelogarithms.IEEETransactionsonInformationTheory,1985,469–472.]或者基于格的密码系统[[]I.Chillotti,N.Gama,M.Georgieva,andM.Izabachene,"Fasterfullyhomomorphicencryption:Bootstrappinginlessthan0.1seconds,"inAdvancesinCryptology_x0016_ASIACRYPT,J.H.CheonandT.Takagi,Eds.Berlin,Germany:Springer,2016,pp.3-33.]）加密图像，利用同态加密的同态加法或者同态乘法性质，云服务器能够在密文上进行图像处理并建立索引结构。2012年，Hsu等人[[]HSUC,LuC,andPeiS.Imagefeatureextractioninencrypteddomainwithprivacy-preservingsift[J].IEEETransactionsonImageProcessing,2012,21(11):4593–4607.]提出安全的SIFT问题，它的所有操作都可以在密文状态下进行，但是这需要大量的计算开销并且需要用户频繁的参与到检索过程中。2014[]LUW,VARNAA,WUM.Confidentiality-preservingimagesearch:acomparativestudybetweenhomomorphicencryptionanddistance-preservingrandomization[J].IEEEAccess,2014,2:125–141.[]P.Paillier,"Public-keycryptosystemsbasedoncompositedegreeresiduosityclasses,"inINADVANCESINCRYPTOLOGY–EUROCRYPT1999.Springer-Verlag,1999,pp.223–238.[]T.Elgamal.Apublickeycryptosystemandasignatureschemebasedondiscretelogarithms.IEEETransactionsonInformationTheory,1985,469–472.[]I.Chillotti,N.Gama,M.Georgieva,andM.Izabachene,"Fasterfullyhomomorphicencryption:Bootstrappinginlessthan0.1seconds,"inAdvancesinCryptology_x0016_ASIACRYPT,J.H.CheonandT.Takagi,Eds.Berlin,Germany:Springer,2016,pp.3-33.[]HSUC,LuC,andPeiS.Imagefeatureextractioninencrypteddomainwithprivacy-preservingsift[J].IEEETransactionsonImageProcessing,2012,21(11):4593–4607.[]ZHANGY,ZHUOL,PENGY,etal.Asecureimageretrievalmethodbasedonhomomorphicencryptionforcloudcomputing[C]//Procedingsof201419thInternationalConferenceonDigitalSignalProcessing.Piscataway:IEEE,2014:26–274.[]ZHANGL,JUNGT,FENGP,etal.Cloud-basedprivacypreservingimagestorage,sharingandsearch[J].arXivpreprintarXiv:1410.6593,2014[]YUANJ,YUS,GUOL.SEISA:Secureandefficientencryptedimagesearchwithaccesscontrol[C]//Procedingsof2015IEEEConferenceonComputerCommunications.Piscataway:IEEE,2015:2083–2091.[]ZOUQ,WANGJ,YEJ,etal.Efficientandsecureencryptedimagesearchinmobilecloudcomputing[J].SoftComputing,2017,21(11):2959–2969.[]HUANGY,ZHANGJ,PANL,etal.PrivacyProtectioninInteractiveContentBasedImageRetrieval[J].IEEETransactionsonDependableandSecureComputing,20高维数据索引技术在基于内容的图像检索中，现有的索引技术分为三类，它们分别是哈希索引、倒排索引和树形索引。基于哈希函数的索引结构主要是以局部敏感哈希（Locality-SensitiveHashing,LSH）函数为代表。2007年，Sadowski等人[[]SADOWSKIC,LEVING.SimHash:Hash-basedSimilarityDetection./sun/trunk/paper/SimHashwithBib.pdf,2007.][]SADOWSKIC,LEVING.SimHash:Hash-basedSimilarityDetection./sun/trunk/paper/SimHashwithBib.pdf,2007.图像检索中的倒排索引是基于视觉词袋的图像索引方法。不同于基于关键词创建的传统倒排索引结构，在基于内容的图像检索中，需要事先对图像内容训练进行训练，将其训练成视觉单词，然后通过索引文件对图像数据集中的所有视觉单词进行索引。2003年，Sivic等人[[]SIVICJ,ZISSERMANA.VideoGoogle:Atextretrievalapproachtoobjectmatchinginvideos[C]//null.Piscataway:IEEE,2003:1470.]首次提出基于视觉词袋模型的倒排索引，该方案利用文本描述实现视频中的目标物的匹配。2011年，Jegou等人[[]JEGOUH,DOUZEM,SCHMIDC.Productquantizationfornearestneighborsearch[J].IEEEtransactionsonpatternanalysisandmachineintelligence,2011,33(1):117–128.]基于非对称距离计算提出用户最近邻搜索的倒排索引的方法。2012年，Babenko[]SIVICJ,ZISSERMANA.VideoGoogle:Atextretrievalapproachtoobjectmatchinginvideos[C]//null.Piscataway:IEEE,2003:1470.[]JEGOUH,DOUZEM,SCHMIDC.Productquantizationfornearestneighborsearch[J].IEEEtransactionsonpatternanalysisandmachineintelligence,2011,33(1):117–128.[]BABENKOA,LEMPITSKYV.Theinvertedmulti-index[C]//ComputerVisionandPatternRecognition(CVPR),2012IEEEConferenceon.Piscataway:IEEE,2012:3069–3076.树形结构数据这类存储方式非常便于面向检索的索引结构，具有数据组织有序、检索效率高等优势。在基于树形的索引结构中，如红黑树、B树等索引结构这些传统的索引树形，它们都是针对低维数据进行创建的。对于高维数据来说，最常用的索引树形是KD树和R树，其中KD树索引结构在不高于20维的数据检索中效率比较高。Beis等人[[]BEISJS,LOWEDG.Shapeindexingusingapproximatenearest-neighboursearchinhighdimensionalspaces[C]//ComputerVisionandPatternRecognition,1997.Proceedings.1997IEEEComputerSocietyConferenceon.Piscataway:IEEE,1997:1000–1006.]提出类似的基于KD树的检索方法来提高检索性能。Slipa[]BEISJS,LOWEDG.Shapeindexingusingapproximatenearest-neighboursearchinhighdimensionalspaces[C]//ComputerVisionandPatternRecognition,1997.Proceedings.1997IEEEComputerSocietyConferenceon.Piscataway:IEEE,1997:1000–1006.[]SILPA-ANANC,HARTLEYR.OptimisedKD-treesforfastimagedescriptormatching[C]//ComputerVisionandPatternRecognition,2008.CVPR2008.IEEEConferenceon.Piscataway:IEEE,2008:1–81.3本文的主要内容和章节安排1.3.1本文的主要内容本文研究的主要目的是图像在进行特征检索时，使得隐私信息不被泄露并完成准确检索的要求。研究的主要内容如下：本文提出了一种支持隐私保护的图像检索方案。为了防止图像隐私信息泄露，用户在图像上传前先对图像进行加密操作，在基于隐私保护的基础中，设计出一种安全有效的检索机制，获得较好的检索性能的图像检索算法。即在保证不泄露用户隐私的前提下，准确、快速地检索出用户感兴趣的图像。该方案支持提取安全的SIFT特征，安全索引SKDTree构建，在保护图像及其特征向量隐私的情况下，实现密文状态下的图像检索。线性检索需要根据相似性对所有数据进行排序，计算复杂度高。与线性检索方案相比，我们基于BOW特征构建SKDTree树形索引，在保证检索精度的前提下提高了检索的效率。本文提出了安全的特征提取及索引构建协议，包括基于同态加密的安全乘法协议、基于混淆电路的安全比较协议、欧氏距离安全计算协议等等，从而实现数据的安全共享。本文给出了详细的协议安全性分析，证明了协议对数据隐私安全的保障。1.3.2本文的章节安排本文一共分为六章，每一章的内容简介如下：第一章绪论：本章首先对该研究方向的背景详细的介绍，然后说明了隐私保护在先进大环境下的研究意义。其次介绍了国内外的研究现状。最后对本文的主要内容和结构的部署安排做了描述。第二章基础知识：为了便于读者对方案的理解，本章主要介绍了方案构建过程中使用的工具，对方案构建过程中所涉及的相关知识作了阐述，介绍了SIFT特征提取、同态加密、BOW词袋模型、安全多方计算等相关技术。第三章安全SIFT特征提取方法：本章主要介绍了隐私保护下SIFT特征的提取，本章利用了同态加密和多方安全计算来实现SIFT特征提取中的安全乘法协议和安全比较协议。第四章安全的索引构建方法：本章主要介绍了隐私保护下索引的构建。第五章基于隐私保护的图像检索方案：本章利用。。。，提出隐私保护的图像检索方案。对方案具体构造和算法进行了详细描述，最后对方案进行安全性和效率的分析。第六章总结与展望：本章对本文工作做了高度概括，总结了本文研究的工作，总结方案中的优缺点并对以后的研究方向进行了展望。

第二章基础知识2.1基于内容的图像检索特征提取基于内容的图像检索的基础是特征提取，特征要能反映出图像的性质，较为通用的特征一般有颜色、纹理等。（1）颜色特征颜色特征是图像中最常见的特征。图像的各种形变比如说平移、改变大小尺寸和对图像进行旋转等，这些操作对图像的颜色基本没有影响。我们可以使用直方图、颜色矩和颜色一致性来描述图像的颜色特征，从而对图像进行检索。基于颜色特征的检索主要采用颜色直方图的方法。常用的颜色空间有RGB，HSI和HSV等。颜色直方图描述全局的颜色分布，对旋转以及位置变化不敏感。颜色直方图是将图像中得所有色彩在直方图中统计出来，能够反应图像的平均颜色信息，但缺乏图像的空间位置信息。颜色直方图只是统计了整幅图像上所有颜色占的比例，如果有两幅图像颜色比例相同，直方图就会认为他们是同一类图像。因此采用纯粹的基于颜色直方图的检索，并不能很好地区分这些图像。同时，要把每幅图像的颜色直方图信息存储下来，需要较大的空间。人类肉眼一般对图像的主色调比较敏感，因此有人提出了基于主色调的检索方法，即通过系统提供的调色板选择颜色，指定某主色调进行检索。然而，肉眼的分辨率毕竟有限，一定范围内的相近的颜色往往无法区分，并且颜色在按色彩量化时会产生误差，从而使得非常相似的颜色被量化到了不同范围内，导致图像匹配时的错漏。通过正态分布拟合法来获取指定颜色的扩展值，对主色调进行扩展，可以弥补因为选择的随机性和量化等引起的误差。（2）纹理特征纹理是指图像像素灰度集和颜色的某种规律性变化。纹理特征显示出了图像表面的结构，主要包括粗糙度、方向性、对比度以及规则性。颜色特征是统计每一个像素点将所有的颜色做统计，而纹理特征则是寻找图像的某个区域内的排列规律[[][]严宇，宋威.颜色和纹理混合描述符图像检索方法[J].计算机科学与探索，2017（11）：120-129基于纹理特征的检索适用于水波、布匹、建材等类型的图像。通常采用统计方法、结构方法以及频谱分析方法进行。统计方法是利用统计的方法需找规律，是为了得到纹理区域内的统计特性。统计方法是根据图像像素间灰度的统计性质规定出纹理特征以及特征与参数间的关系，主要用于分析像沙地、木纹、草坪等细致而不规则的物体。结构方法即使寻找纹理特征的排列规律，主要描述的是由元素以一定的规律排列而成的纹理。结构方法是根据纹理基元及其排列规则来描述纹理特征，适用于像砖瓦、布料这种由一类元素组成的纹理以及排列比较规则的东西。频谱分析方法则是根据图像的不同频率来提取纹理特征。（3）形状特征许多相似的物体具有不同的颜色，但其形状总是类似的，因此形状也属于图像的一个显著特征。形状包括面积、主轴方向、连通性等特征，形状的表征方法很多，包括几何常量、力矩、本征工程等等，可以通过基于边缘和基于区域来描述形状特征。基于边缘的形状特征适用于边缘比较清晰的图像，主要是提取物体的边缘信息，通过图像的整体来提取形状特征。基于区域的检测则是将整幅图像分割成大小相同的区域，在区域内提取特征。国防科大多媒体实验室提出了根据颜色特征进行形状检索的方法，该方法简单实用，非常适合于背景相对简单的图像形状检索。一般情况下，彩色图像中的对象与背景之间必然存在颜色上的差异。如果利用这种颜色差异提取物体的形状边缘信息，相对而言比直接提取边缘更为容易。通过将图像分块，每一子块分别计算直方图，选择有差异的比较对，形成颜色特征差值表，比较时进行差值表的比较。（4）空间关系特征空间关系特征是图像中各对象的基本关系。利用图像中对象的空间关系来区别图像，符合人们识别图像的习惯，直角坐标系是其最直接的表示法。空间关系主要包括方向、度量、拓扑三大类关系。空间关系特征可以分为两类：一类方法首先对图像进行自动分割，划分出其中所含的对象或颜色区域，然后根据这些区域对图像索引，主要包括二维符号串、空间四叉树和符号图像；另一类方法是将图像均匀划分若干子块，对每个图像子块提取特征建立索引。在检索中，首先根据特征计算图像的相应子块之间的相似度，然后通过加权计算总得相似性。这类方法的分块并不能精确的给出局部色彩的信息，而且计算和存储的代价都比较昂贵，因此，在实际中应用较少，从而给基于对象空间关系的图像检索带来了困难。2.2SIFT特征提取DavidG.Lowe提出一种称之为SIFT的图像局部特征描述算子，并通过实验证实了该算子对图像的尺度缩放、平移、旋转变换保持不变，对图像的亮度变化以及仿射变换也具有相当的鲁棒性。SIFT算法具有如下一些特点：1.SIFT特征是图像的局部特征，其对旋转、尺度缩放、亮度变化保持不变性，对仿射变换、视角变化、噪声也保持一定程度的稳定性；2.区分性好，信息量丰富，适用于在海量特征数据库中进行快速、准确的匹配；3.多量性，即使少数的几个物体也可以产生大量的SIFT特征向量；4.高速性，经优化的SIFT匹配算法甚至可以达到实时的要求；5.可扩展性，可以很方便的与其他形式的特征向量进行联合。SIFT算法的本质就是从图像中提取SIFT关键点的过程。SIFT特征检测主要包括以下4个基本步骤：1.尺度空间极值检测：搜索所有尺度上的图像位置。通过高斯微分函数来识别潜在的对于尺度和旋转不变的兴趣点。二维高斯滤波函数，其中σ表示高斯函数的方差（1）一幅N×N的图像I(x,y)，在不同尺度空间下的表示可以由图像与高斯核卷积得到Gaussian图像：（2）其中σ称之为尺度空间，其值越小表示图像被平滑地越少。大尺度对应图像的概貌，小尺度对应图像的细节。（3）采用DoG算子建立的尺度空间如图2所示。图2DoG算子建立的尺度空间高斯金字塔分为n阶（octave），每一阶分为s层。为了这s层上检测特征点，需要产生s+2幅DoG图像，对应s+3幅Gaussian图像。这s+3幅Gaussian图像的尺度参数为σ，则下一层的Gaussian图像的尺度参数为kσ。为了要让一阶之间有s层，规定k=21/s。将同一阶中的s+3层Gaussian图像，相邻的图像相减就产生了对应的s+2层DoG图像。为了产生下一阶的Gaussian图像，对上一阶产生的最后一幅N×N的图像进行亚采样，生成N/2×N/2的图像的图像。在亚采样图像基础上重复上述建立s+3层Gaussian图像的过程。为了检测D(x,y,σ)的局部极值点，需要比较DoG图像中每个像素与其同一层及上下两层共计26个近邻像素的值。若像素(x,y)是一个可能的SIFT关键点，则它必须在它周围的26个近邻像素（上一个尺度的9个点＋同尺度的8个点＋下一个尺度的9个点）中是极值点，如图3所示。所有这样的局部极值点，就构成了一个SIFT候选关键点的集合。图3DoG尺度空间局部极值检测2.关键点定位在每个候选的位置上，通过一个拟合精细的模型来确定位置和尺度。关键点的选择依据于它们的稳定程度。极值检测得到的所有候选关键点，还必须通过两步检验才能确定是关键点：一是它必须与周围的像素有明显的差异，也就是说低对比度的点不要；二是它不能是边缘点。1）低对比度的点通过拟合三维二次方程，可以找出低对比度的点。对D（x，y，σ）进行泰勒展开到二次项：（4）其中：D是DoG计算的结果；x是候选关键点之一。由D和x，可以找到一个偏移量：（5）将式（5）代入（4）中，如果计算得到的｜｜＜0.03，则该点是低对比度的点。2）边缘处的点类似Harris边缘检测的方法，计算Hessian矩阵：（6）获取特征点处的Hessian矩阵，假设H的特征值为α和β（α、β代表x和y方向的梯度）且α>β。令α=rβ则有：（7）其中Tr(H)求取H的对角元素和；Det(H)为求H的行列式值。（8）则公式（8）的值在两个特征值相等时最小，随着r的增大而增大。r值越大，说明两个特征值的比值越大，即在某一个方向的梯度值越大，而在另一个方向的梯度值越小，而边缘点恰恰就是这种情况。所以为了剔除边缘响应点，需要让该比值小于一定的阈值，若大于阈值，则该点可能是边缘的点，可以将它剔除。3.关键点方向分配基于图像局部的梯度方向，分配给每个关键点位置一个或多个方向。所有后面的对图像数据的操作都相对于关键点的方向、尺度和位置进行变换，从而提供对于这些变换的不变性。为了使算子具备旋转不变性，采用梯度直方图来确定关键点的主方向，如图4所示。对于每一个关键点，考虑他的邻近的一个邻域窗口内的梯度方向，最多人投票的方向就当做该点的主方向。而每个邻近的点对中央这个点的权重由高斯分布再乘上该点的梯度的大小来决定。图4使用直方图统计邻域内像素的梯度和方向图5将坐标轴旋转为特征点的主方向为了保证特征矢量的旋转不变性，要以特征点为中心，在附近邻域内将坐标轴旋转θ角度，即将坐标轴旋转为特征点的主方向，如图5所示。如果梯度直方图中存在另一个相当于主峰值80%的峰值时，则将整个方向认为是该关键点的辅方向。一个关键点可能被指定多个方向（一个主方向，一个以上的辅方向）。这种情况下，就可复制同一个关键点，使它们分别朝向不同的方向。4.特征点描述符在每个关键点周围的邻域内，在选定的尺度上测量图像局部的梯度。这些梯度被变换成一种表示，这种表示允许比较大的局部形状的变形和光照变化。为了确保旋转不变性，首先将坐标轴旋转为关键点的方向。以一个关键点为中心，取8×8的窗口，将该窗口切成2×2的子窗口，统计每个子窗口中的方向直方图，如图6所示。图6关键点邻域梯度信息生成的特征向量每一个子窗口的方向由其上4×4的小块的方向用之前的方法来决定。图中的每个关键点方向由2×2共4个种子点的方向决定，一个种子点有8个方向的信息，则每个关键点就有4×8=32维。图7SIFT特征向量计算在实际计算过程中，为了增强匹配的稳健性，通常采用4×4共16个种子点来描述，这样一个关键点就有16×8=128维的数据，形成128维的SIFT特征向量，如图7所示。2.3同态加密一般加密方案关注的都是数据存储安全，即我要给其他人发送某数据，或者要在计算机或者其他服务器上存储某数据，需要先对数据进行加密然后再发送或者存储。数据加密之后，对于没有密钥的用户，不可能从加密结果中得到有关原始数据的任何信息。只有拥有密钥的用户才能够实现解密，得到正确的原始信息。在这个过程中用户不能对加密结果做任何操作，只能进行存储或者传输。对加密结果做其他操作将会导致错误的解密，甚至解密失败。同态加密的概念是Rivest等人在20世纪70年代首先提出的，与一般加密算法相比，同态加密除了能实现基本的加密操作之外，还能实现密文间的多种计算，即先计算后解密可等价于先解密后计算。同态加密方案关注的是数据处理安全。同态加密提供了一种对加密数据进行处理的功能。也就是说，其他人可以对加密数据进行处理，但是处理过程不会泄露任何原始内容。同时，拥有密钥的用户对处理过的数据进行解密后，得到的正好是处理后的结果。这个特性对于保护信息的安全具有重要意义，利用同态加密技术可以先对多个密文进行计算之后再解密，不必对每一个密文解密而花费高昂的计算代价；利用同态加密技术可以实现无密钥方对密文的计算，密文计算无须经过密钥方，既可以减少通信代价，又可以转移计算任务，由此可平衡各方的计算代价；利用同态加密技术可以实现让解密方只能获知最后的结果，而无法获得每一个密文的消息，可以提高信息的安全性。正是由于同态加密技术在计算复杂性、通信复杂性与安全性上的优势，越来越多的研究力量投入到其理论和应用的探索中。近年来，云计算受到广泛关注，而它在实现中遇到的问题之一即是如何保证数据的私密性，同态加密可以在一定程度上解决这个技术难题。本质上，同态加密是指这样一种加密函数，对明文进行环上的加法和乘法运算再加密，与加密后对密文进行相应的运算，结果是等价的。由于这个良好的性质，人们可以委托第三方对数据进行处理而不泄露信息。具有同态性质的加密函数是指两个明文a、b满足Dec(Enc(a)⊙Enc(b))=a⊕b的加密函数，其中Enc是加密运算，Dec是解密运算，⊙、⊕分别对应明文和密文域上的运算。当⊕代表加法时，称该加密为加同态加密：当⊕代表乘法时，称该加密为乘同态加密。同态加密方案实际上分为了两类。它们之间的主要区别归结为可以对其密文执行的数学运算的类型和频率。两种同态加密分别是：1.部分同态加密（SomewhatHomomorphicEncryption,SWHE）：部分同态加密可实现有限次的加、乘同态运算，它是完全同态加密的先驱。在2009年GraigGentry给出FHE的构造前，很多加密方案都具有SomewhatHomomorphism的性质。实际上，经典的RSA加密对于乘法运算就具有同态性。Elgamal加密方案同样对乘法具有同态性。Paillier在1999年提出的加密方案也具有同态性，而且是可证明安全的加密方案。2.全同态加密（FullyHomomorphicEncryption,FHE）：全同态加密方案[[]C.Gentry,S.Halevi,andN.P.Smart,"Fullyhomomorphicencryptionwithpolylogoverhead,"inAdvancesinCryptologyEUROCRYPT,D.PointchevalandT.Johansson,Eds.Berlin,Germany:Springer,2012:46-482.]与其他形式的同态加密不同，它可以处理密文的任意计算。全同态加密是指同时满足加同态和乘同态性质，可以进行任意多次加和乘运算的加密函数，用数学公式表示同态加密，可以写成Dec(f(En(m1),En(m2),...,En(mk)))=f(m1,m2,...,mk)，或写成：f(En(m1),En(m2),...,En(mk))=En(f(m1[]C.Gentry,S.Halevi,andN.P.Smart,"Fullyhomomorphicencryptionwithpolylogoverhead,"inAdvancesinCryptologyEUROCRYPT,D.PointchevalandT.Johansson,Eds.Berlin,Germany:Springer,2012:46-482.全同态加密的目标是允许任何人使用加密数据执行有用的操作而无需访问加密密钥。该概念具有改善云计算安全性的应用，如果您在云中存储加密的敏感数据，但不信任云提供商，全同态加密为您提供一种操作和搜索数据方法而无需允许云提供商访问您要访问的数据。在基于HE的CBIR方案中，用户利用同态密码系统逐像素对图像进行加密，它允许云在加密域中处理和索引它们的图像。Hsu等人在文献[34]中提出了一种采用Paillier密码系统加密图像的高精度CBIR算法。这种方法受到有意义密文表达式的影响，导致加密和解密速度慢的问题。Hu等人[[]S.Hu,Q.Wang,J.Wang,Z.Qin,andK.Ren.SecuringSIFT:Privacypreservingoutsourcingcomputationoffeatureextractionsoverencryptedimagedata.IEEETrans.ImageProcess,2016:341-3425.]在Hsu的基础上进一步提出了一种利用带误差环学习（r-LWE）同态密码系统进行SIFT特征提取的有效方案。与Hsu等人提出的方案不同，它们的批处理安全乘法协议基于部分同态加密（[]S.Hu,Q.Wang,J.Wang,Z.Qin,andK.Ren.SecuringSIFT:Privacypreservingoutsourcingcomputationoffeatureextractionsoverencryptedimagedata.IEEETrans.ImageProcess,2016:341-3425.[]P.Li,T.Li,Z.-A.Yao,C.-M.Tang,andJ.Li,"Privacy-preservingoutsourcingofimagefeatureextractionincloudcomputing,"SoftComputing,vol.21,no.15,pp.43494359,Aug.2017.尽管基于HE的方案允许云服务器处理和索引加密的图像，这在语义上是安全。不幸的是，他们需要更高的时间和空间复杂度。更重要的是，这些方案不可避免的面临密文扩展和噪声增长问题。这些都对可伸缩性和准确性的有负面影响。2.3词袋模型Bag-of-words，也叫做“词袋”，Bag-of-words词袋模型最初被用在信息检索领域，对于一篇文档来说，假定不考虑文档内的词的顺序关系和语法，只考虑该文档是否出现过这个单词。假设有5类主题，我们的任务是来了一篇文档，判断它属于哪个主题。在训练集中，我们有若干篇文档，它们的主题类型是已知的。我们从中选出一些文档，每篇文档内有一些词，我们利用这些词来构建词袋。我们的词袋可以是这种形式：{‘watch’,'sports','phone','like','roman',……}，然后每篇文档都可以转化为以各个单词作为横坐标，以单词出现的次数为纵坐标的直方图，如下图所示，之后再进行归一化，将每个词出现的频数作为文档的特征。近几年，在图像领域，使用Bag-of-words方法也是取得了较好的结果。如果说文档对应一幅图像的话，那么文档内的词就是一个图像块的特征向量。一篇文档有若干个词构成，同样的，一幅图像由若干个图像块构成，而特征向量是图像块的一种表达方式。我们求得N幅图像中的若干个图像块的特征向量，然后用K-Means算法把它们聚成k类，这样我们的词袋里就有k个词，然后来了一幅图像，看它包含哪些词，包含单词A，就把单词A的频数加1。最后归一化，得到这幅图像的BoW表示，假如k=4,每幅图像有8个小块(patch)，那么结果可能是这样的：[2,0,4,2]，归一化之后为[0.25,0,0.5,0.25]。（1）特征提取通过分割、密集或随机采集、关键点或稳定区域、显著区域等方式使图像形成不同的图像块，并获得各图像块处的特征。特征必须具有较高的区分度，而且要满足旋转不变性以及尺寸不变性等，通常采用SIFT特征。SIFT会从图片上提取出很多特征点，每个特征点都是128维的向量，如果图片足够多的话，我们会提取出一个巨大的特征向量库。（2）构建视觉词典提取完特征后，采取聚类算法对这些特征向量进行聚类。聚类是实现视觉词典即码本的关键，通常采用K-Means聚类算法。K-Means算法流程：1.随机初始化K个聚类中心；2.重复下述步骤直至算法收敛：①对应每个特征，根据距离关系赋值给某个中心/类别；②对每个类别，根据其对应的特征集重新计算聚类中心。聚类完成后，由聚类中心代表的视觉词汇形成视觉词典，得到k个向量组成的字典。视觉单词数量即K一般取3000-10000，即图像整体描述的直方图维度为3000-10000。（3）生成码本，即构造Bag-of-Features，也就是局部特征投影过程判断图像的每个特征点与哪个类心最近，最近则放入该类心，最后将生成一列频数表。对于输入特征，量化的过程是将该特征映射到距离其最接近的视觉单词，并实现计数。Bag-of-words在CV中的应用首先出现在AndrewZisserman[6]中为解决对视频场景的搜索，其提出了使用Bag-of-words关键点投影的方法来表示图像信息。后续更多的研究者归结此方法为Bag-of-Features，并用于图像分类、目标识别和图像检索。在Bag-of-Features方法的基础上，AndrewZisserman进一步借鉴文本检索中TF-IDF模型(TermFrequency-InverseDocumentFrequency)来计算Bag-of-Features特征向量。接下来便可以使用文本搜索引擎中的反向索引技术对图像建立索引，高效的进行图像检索。TF-IDF是一种用于信息检索的常用加权技术，在文本检索中，用以评估词语对于一个文件数据库中的其中一份文件的重要程度。词语的重要性随着它在文件中出现的频率成正比增加，但同时会随着它在文件数据库中出现的频率成