美赛重庆大学特等奖题名论文Word格式.docx
《美赛重庆大学特等奖题名论文Word格式.docx》由会员分享，可在线阅读，更多相关《美赛重庆大学特等奖题名论文Word格式.docx（30页珍藏版）》请在冰点文库上搜索。
F3
F4
Summary
Asisknowntoall,splicingofpaperscrapsisacomplexissue,whichexertsaimportantroleinjudicialevidencerecovery,restorationofhistoricaldocumentsandaccesstomilitaryintelligence.Thispaperfocusesonsplicingproblemofpaperscraps,establishingshreddingdistancemodelandrestorationTSPmodel.Atsametime,wedesignone-dimensionalandmulti-dimensionalpiecesrestorationalgorithmandthensolvesitbyusingMATLAB.
Forquestionone,weextractinformationfromtheAppendix1and2,designingtorecovertheone-dimensionalshreddingalgorithms,whichischaracterizedbyatextcharactersize,linespacingstructure.AndthenwecantransfortheshreddingproblemintorecoveryTSPproblem,thusobtainingthecorrectrecoverygraphicsandsequences.
Forquestiontwo,wefirstlystandardizeshreddingpicturesfromtheAppendix1and2,andthenextractthenormalizedimage-levelfeatures.Forthatpicturescannotbeclassifiedviamachine,weusethedevelopedprogramsofGUItoimprovetheefficiencyoflabor.
Forquestionthree,three-dimensionaldesignshreddingrestorationalgorithm,afirstsurfaceandthesurfaceofAnnex5bintegratepictures,get416piecesofshreddingpictures,thepicturealsostandardizedlevelfeatureextraction,classificationandotheroperations,willreduceddimensionsoftheone-dimensionalproblemandsolvedtoobtainthecorrectrecoveryimagesandsequencesofpositiveandnegativeAnnex5.Takingintoaccounttheproblemofquantitativeevaluationalgorithm,thispaperpresentsminimalinterventionmodeltoimprovethealgorithminplace,thatis,throughthecomputertorecognizetheorderandsequenceinreverseordertorecoverthenumberofmanualinterventiontoachieveaminimumnumberofadvantagesanddisadvantagesofthealgorithmisportrayed.
Keywords:
Reconstructdocuments；
TSP；
ShreddingDistanceModel；
ShreddingRestorationAlgorithm
Content
IIntroduction2
IISymbolDefinitions2
IIIAssumptionsandNotations2
ⅣForquestionone3
4.1ImagePreprocessing3
4.2ShreddingFeatureExtraction3
4.3RecognitionSequenceBasedonTextFeatures4
4.4TheDefinitionofShreddingDistance5
4.5RecoveryofTSP5
4.6SimulateAnneal（SA）Algorithm5
4.7One-DimensionalShreddingRestorationAlgorithm6
4.8TheSolutionofModel6
ⅤForquestiontwo7
5.1ShreddingStandardizationAndLevelFeatureExtraction7
5.2TheClassificationofLevelFeature8
5.3Two—DimensionalShreddingRestorationAlgorithm8
5.4TheSolutionofModel9
ⅥForquestionthree10
6.1DimensionalityReduction10
6.2Three—DimensionalShreddingRestorationAlgorithm11
6.3TheSolutionofModel11
ⅦStrengthsandWeaknesses12
7.1Strengths12
7.2Weaknesses12
ⅧTheRefinementofourModel13
8.1ImprovedApplyforColorfulImages13
8.2MinimalInterventionDegreeAlgorithm13
Reference13
AppendixⅠ15
AppendixⅡ16
AppendixⅢ17
Introduction
Traditionally,reconstructingshreddeddocumentscompletedbyhandiswithhigheraccuracy,butinefficiency,especiallywhenahugeamountofcomplicatedworktocompleteinashorttime.Withthedevelopmentofcomputertechnology,peopleistryingtodevelopautomaticsplicingtechniqueforreconstructingdocuments,astoimprovetherecoveryefficiencyofsplicing.
Inaddition,thisisakindofstaffwhichisrelatedtoourdailylife.Thefactorstobeconsideredinrealityfarmorethanthesubjectitself,andhowtomakethemodelmorerealisticandprovideeffectivesplicinginformationinthisarticleisamajorproblem.Facedbylotofinformationofferedandreasonableassumptionsforshreddingrecovery,weareabletoconducttheresearchforshreddingrecovery.
SymbolDefinitions
SymbolDefinitions
Pixelvaluesbeforebinarization
ThedistancebetweenshredAandshredB
Leftrecognitionsequence
Rightrecognitionsequence
Widthofcharacters
TotaldistanceofTSP
Thelengthofrecognitionsequence
AssumptionsandNotations
Forthesakeofconvenienceofthefollowingdiscussions,wefirstlyassumethat:
（1）Textdirectionishorizontal
（2）Positiveandnegativeprintmarginsareinthesameformat
（3）Ignoretheefficiencyoflaborproductivity
ⅣForquestionone
4.1Imagepreprocessing
Accordingtotherelevantknowledge，weneedtoprocessthepicturepixels.
Generally,theimagepixelvaluesarepositionedwithin[0,255],andthenaredistinguishedbetweenblankpositionandfontbysettingthethreshold.Asfornon-colorpictures,wejustneedtodistinguishblankandnon-blank.
Tomakethepicturecanclearlydescribetheemptyspaceandthecharacterposition,weuseMATLABforpreprocessingandputtheimageintoMATLABastoobtainthecorrespondingpixelmatrix.Atlast,wemakepixelmatrixbinarizationandthenhave
1,qij=255
Pij=
255,others
4.2Shreddingfeatureextraction
Generallyspeaking,shreddingfeatureextractionisdividedintotwocategories.Oneistoextractshreddingfeaturebysplicingshapefeatures,andtheotherischaracterizedbyextractingtextshreddingbasedonfeatures.Accordingtotheproblem,theshapeofthispaperbelongstothesecondcategory.
Figure1.One-dimensionalshredding
Figure2.Charactersfeatures
Insummary,thetextfeatureextractionasfollows:
Step1:
thepicture’sbinarization.textiswhite,blankisblack.
Step2:
findalllinespacingandemptyplaceofpictures,andmarkitasgray
Step3:
findoutallthekerning,andmarkitasgray
Step4:
calculatethecharacterwidthbyspacing,empty,kerningandotherfeatures.Accordingtotheproblem,thispaperextractstextfeaturebyimportingtheimagepixelsandusingMATLABprogram
4.3Recognitionsequencebasedontextfeatures
ThroughtheanalysisofChinesecharactersandEnglishletters,wesignthecharacterwidthofC.Thewidthisdividedintwoparts,respectivelyC—RandR,andfornotbeingcutcharacter,stillretainsthewidthC.
Figure3.Charactersegmentation
Accordingtothedefinitionofcharacter-basedsegmentation，weconstructrecognitionsequencesbasedonthecharacteristicsofthetext
LeftRight
Figure4.Recognitionsequences
FortherecognitionsequenceinFigure4,theplacewithnocharacterpositionis0,andtheothernodesrepresentthecorrespondingcharacterlength（forthefullCandtheincompleteisC—RorR）.
4.4Thedefinitionofshreddingdistance
Accordingtothedefinitionofrecognitionsequence,wedefinethedistancebetweenshreddingAandBandweget
X=0or1
Fromtheseequations,weknowthatthegreaterthedegreeofagreementofthetworecognitionsequences,thesmallerthedistancebetweentwokindsofrecognitionsequence.Undertheconditions,whenthetworecognitionsequencesarefullyconsistent,thedistancewillbe0.
4.5RecoveryofTSP
TSPisoneofthemostfamousproblemsingraphtheory.Ifweseeeachoftheshreddingasapoint,thereisadistancebetweenpoints.Inessence,weneedtofindthesmallesttotaldistancepath,whichistofindanoptimalTSPpath.So,therecoveryofshreddingcanbeabstractedintotherecoveryofTSP.
Therefore,wehavethejunction
S.t
where
DistotaldistanceofTSP
isdistancefromitoi+1
BysolvingTSPproblem,youcangetaccesstoeachpointinthesequence,andfinallyuseMATLABtogetoriginalpaper.
4.6SimulateAnneal（SA）algorithm
Simulatedannealing（SA）algorithmisaniterativesolutionstrategyontherandomsearchalgorithm,itisbasedonthephysicalannealingprocessofsolidmaterialandthegeneralsimilarityofcombinatorialoptimizationproblems.Thenameandinspirationcomefromannealinginmetallurgy,atechniqueinvolvingheatingandcontrolledcoolingofamaterialtoincreasethesizeofitscrystalsandreducetheirdefects.Theheatcausestheatomstobecomeunstuckfromtheirinitialpositionsandwanderrandomlythroughstatesofhigherenergy;
theslowcoolinggivesthemmorechancesoffindingconfigurationswithlowerinternalenergythantheinitialone.TheSAcanbedescribedasfollows:
Step1.Initialization.Giventhescopeofmodelforeachparameters,randomlyselectedaninitialsolution
andcalculatethecorrespondingtargetvalueE（
）;
settheinitialtemperature
finaltemperature
makearandomnumber∈（0,1）asaprobabilitythreshold,setthecoolingfunctionT（
+1）=γ•T（
）,inwhich,γisannealingcoefficient,
isthenumberofiterations.
Step2.AtacertainTtemperature,makeaperturbationΔx,thenanewsolutionis
=
+
produced,calculatethedifferenceΔE（
）=E（
）−E（
）.
Step3.IfΔE（x）<
0,xisaccepted;
ifΔE（
）>
0,
isacceptedaccordingtoprobabilityp=exp（−ΔE/
•T）,
isaconstantandusuallytakenthevalue1.Ifp>
ε,
isaccepted.When
accepted,
=
Step4.Inacertaintemperature,repeatsteps3.
Step5.ReducethetemperatureTbyslowcoolingfunction.
Step6.Repeatsteps2tostep5,untiltheconditionismeet.
ByusingSAtosolveTSP,wecanregardeachsequenceaseachsolution,astofindtheoptimalschedulingsequence.
4.7One-dimensionalshreddingrestorationalgorithm
Insummary,throughaone-dimensionalshreddingrecoveryalgorithm,itcanautomaticallyrecovertheone-dimensionalshredding.
Algorithmstepsisasfollows:
Extractingimagepixelmatrix
升级会员 