Image Stitching Algorithm Based On Feature Extraction ProjectReport Submittedinpartialfulfillmentoftherequirementsforthedegreeof Bachelor of Engineering by Ansari Mohd Manzoor Maqsood Rehana (12CO65) Supervisor Prof. Khan Mubbashir Co-Supervisor Prof. Sameer Panwala Department of Computer Engineering, SchoolofEngineeringandTechnology Anjuman-I-Islam’sKalsekarTechnicalCampus PlotNo. 2 3,Sector-16,NearThanaNaka,KhandaGaon, NewPanvel,NaviMumbai. 410206 AcademicYear: 2014-2015 CERTIFICATE Department of Computer Engineering, SchoolofEngineeringandTechnology, Anjuman-I-Islam’sKalsekarTechnicalCampus KhandaGaon,NewPanvel,NaviMumbai. 410206 This is to certify that the project entitled Image Stitching Algorithm Based On Feature Ex- tractionisabonafideworkofAnsariMohdManzoorMaqsoodRehana(12CO65)submitted totheUniversityofMumbaiinpartialfulfillmentoftherequirementfortheawardofthedegree of“BachelorofEngineering”inDepartmentofComputerEngineering. Prof. KhanMubbashir Prof. SameerPanwala Supervisor/Guide Co-Supervisor/Guide Prof. TabrezKhan Dr. AbdulRazakHonnutagi HeadofDepartment Director Project Approval for Bachelor of Engineering ThisprojectentitledImageStitchingAlgorithmBasedOnFeatureExtractionbyAnsari MohdManzoorMaqsoodRehana isapprovedforthedegreeofBachelorofEngineeringin DepartmentofComputerEngineering. Examiners 1. .............................. 2. .............................. Supervisors 1. .............................. 2. .............................. Chairman ............................. Declaration I declare that this written submission represents my ideas in my own words and where others ideasorwordshavebeenincluded,Ihaveadequatelycitedandreferencedtheoriginalsources. I also declare that I have adhered to all principles of academic honesty and integrity and have not misrepresented or fabricated or falsified any idea/data/fact/source in my submission. I un- derstandthatanyviolationoftheabovewillbecausefordisciplinaryactionbytheInstituteand can also evoke penal action from the sources which have thus not been properly cited or from whomproperpermissionhasnotbeentakenwhenneeded. AnsariMohdManzoorMaqsoodRehana(12CO65) Abstract Tittle: ImageStitchingAlgorithmBasedOnFeatureExtraction This paper proposes a novel edge-based stitching method to detect moving objects and con- struct mosaics from images. The method is a coarse-to-fine scheme which first estimates a good initialization of camera parameters with two complementary methods and then refines the solution through an optimization process. The two complementary methods are the edge alignment and correspondence-based approaches, respectively. The edge alignment method estimates desired image translations by checking the consistencies of edge positions between images. Thismethodhasbettercapabilitiestoovercomelargerdisplacementsandlightingvari- ationsbetweenimages. Thecorrespondence-basedapproachestimatesdesiredparametersfrom a set of correspondences by using a new feature extraction scheme and a new correspondence building method. The method can solve more general camera motions than the edge alignment method. Since these two methods are complementary to each other, the desired initial estimate can be obtained more robustly. After that, a Monte-Carlo style method is then proposed for integratingthesetwomethodstogether. Inthisapproach,agridpartitionschemeisproposedto increase the accuracy of each try for finding the correct parameters. After that, an optimization processisthenappliedtorefinetheaboveinitialparameters. Differentfromotheroptimization methodsminimizingerrorsonthewholeimages,theproposedschememinimizeserrorsonlyon positionsoffeaturespoints. Sincethefoundinitializationisveryclosetotheexactsolutionand only errors on feature positions are considered, the optimization process can be achieved very quickly. Experimentalresultsareprovidedtoverifythesuperiorityoftheproposedmethod. AnsariMohdManzoorMaqsoodRehana(12CO65) B.E.(ComputerEngineering) UniversityofMumbai. iv Contents ProjectApprovalforBachelorofEngineering . . . . . . . . . . . . . . . . . . . . . ii Declaration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iii Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iv TableofContents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vii ListofFigures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viii ListofTables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ix KeywordsAndGlossary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . x 1 ProjectOverview 1 1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.1.2 AdvantagesOverCurrentSystem . . . . . . . . . . . . . . . . . . . . 3 1.2 ProposedSystemArchitecture . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.2.1 FormulationofProblemWithusingTechnology . . . . . . . . . . . . . 4 1.3 OrganizationoftheProject . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2 ReviewOfLiterature 6 2.1 TheImplementofanImageStitchingAlgorithmbasedonFeatureExtraction . 6 2.1.1 Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.1.2 Pros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.1.3 Cons . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.1.4 HowweovercomeThoseprobleminProject . . . . . . . . . . . . . . 8 2.2 SeamlessImageStitchingintheGradientDomain . . . . . . . . . . . . . . . . 9 2.2.1 Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.2.2 Pros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.2.3 Cons . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.2.4 HowweovercomeThoseprobleminProject . . . . . . . . . . . . . . 10 2.3 TowardsOptimalImageStitchingforVirtualMicroscopy . . . . . . . . . . . . 10 2.3.1 Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.3.2 Pros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.3.3 Cons . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.3.4 HowweovercomeThoseprobleminProject . . . . . . . . . . . . . . 12 2.4 ImageMosaickingandProducingaPanoramicVisibility . . . . . . . . . . . . 12 2.4.1 Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.4.2 Pros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.4.3 Cons . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.4.4 HowweovercomeThoseprobleminProject . . . . . . . . . . . . . . 14 2.5 ImageStitchingbasedonFeatureExtractionTechniques . . . . . . . . . . . . 14 2.5.1 Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.5.2 Pros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 v 2.5.3 Cons . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2.5.4 HowweovercomeThoseprobleminProject . . . . . . . . . . . . . . 17 2.6 TechnologicalReview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2.6.1 MATLAB/SCILAB . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 3 RequirementAnalysis 19 3.1 PlatformRequirement: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 3.1.1 SupportiveOperatingSystems: . . . . . . . . . . . . . . . . . . . . . 19 3.2 SoftwareRequirement: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 3.2.1 FrontEndSoftwareRequirement: . . . . . . . . . . . . . . . . . . . . 19 3.3 HardwareRequirement: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 3.3.1 BasicHardwareRequiredforDevelopment: . . . . . . . . . . . . . . 20 3.3.2 HardwareRequiredForProjectDevelopment: . . . . . . . . . . . . . . 20 4 ProjectDesign 21 4.1 DesignApproach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 4.1.1 FrontEndDesigns . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 4.2 SoftwareArchitecturalDesigns . . . . . . . . . . . . . . . . . . . . . . . . . . 22 4.2.1 ComponentDiagram . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 4.2.2 DeploymentDiagram . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 4.3 Work-flowDesign . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 4.3.1 FlowDiagram . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 4.3.2 DFDLevels . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 5 ImplementationDetails 27 5.1 AssumptionsAndDependencies . . . . . . . . . . . . . . . . . . . . . . . . . 27 5.1.1 Assumptions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 5.1.2 Dependencies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 5.2 ImplementationMethodologies . . . . . . . . . . . . . . . . . . . . . . . . . . 28 5.2.1 ModularDescriptionofProject . . . . . . . . . . . . . . . . . . . . . 28 5.3 DetailedAnalysisandDescriptionofProject . . . . . . . . . . . . . . . . . . . 28 5.4 UseCaseDiagram . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 5.4.1 UsecaseReport . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 5.5 ClassDiagram . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 5.5.1 ClassDiagramReport . . . . . . . . . . . . . . . . . . . . . . . . . . 42 5.6 SequenceDaigram . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 5.7 ActivityDaigram . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 6 ResultsandDiscussion 45 6.1 TestCases . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 6.2 Results Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 7 ProjectTimeLine 49 7.1 ProjectTimeLineMatrix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 7.2 ProjectTimeLineChart . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 8 TaskDistribution 51 8.1 DistributionofWorkload . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 8.1.1 ScheduledWorkingActivities . . . . . . . . . . . . . . . . . . . . . . 51 8.1.2 Membersactivitiesortask . . . . . . . . . . . . . . . . . . . . . . . . 53 vi 9 ConclusionandFutureScope 54 9.1 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 9.2 FutureScope . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 References 56 10 PublishedPapers 58 PublishedPapers 58 AppendixI 59 Acknowledgment 65 vii List of Figures 1.1 SystemArchitecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2.1 ExampleofEdgeDetection . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.2 controlpointselectiontool . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2.3 mosaicimage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 4.1 GraphicalUserInterface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 4.2 SoftwareArchitecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 4.3 ComponentDiagram . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 4.4 DeploymentDiagram . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 4.5 FlowDiagramofimagestitchingalgorithmbasedonfeatureextraction . . . . . 25 4.6 Level0DFDofimagestitchingalgorithmbasedonfeatureextraction . . . . . 26 4.7 Level1DFDofimagestitchingalgorithmbasedonfeatureextraction . . . . . 26 5.1 exampleofa5x5Gaussianfilter. . . . . . . . . . . . . . . . . . . . . . . . . . 29 5.2 ExamplesofFeatureExtractionOutput. . . . . . . . . . . . . . . . . . . . . . 32 5.3 StitchedImages. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 5.4 Projection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 5.5 Finalimage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 5.6 RansacDisplay. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 5.7 UseCaseDiagram . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 5.8 ClassDiagram . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 5.9 SequenceDaigram . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 5.10 ActivityDaigram . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 6.1 TestCase1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 6.2 TestCase2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 6.3 StitchedImage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 6.4 Histogram . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 7.1 ProjectTimeLineMatrix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 7.2 ProjectTimeLineChart . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 7.3 ProjectTimeLineChart . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 10.1 GraphicalUserInterface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 10.2 SelectedImage1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 10.3 SelectedImage2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 10.4 Histogramforthesourceimage1 . . . . . . . . . . . . . . . . . . . . . . . . . 62 10.5 Histogramforthesourceimage2 . . . . . . . . . . . . . . . . . . . . . . . . . 63 10.6 Finalstitchedimageanditshistogram . . . . . . . . . . . . . . . . . . . . . . 64 viii List of Tables 5.1 UsecaseReport . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 5.2 ClassDiagramReport . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 8.1 ScheduledWorkingActivities . . . . . . . . . . . . . . . . . . . . . . . . . . 51 8.2 ScheduledWorkingActivities . . . . . . . . . . . . . . . . . . . . . . . . . . 52 8.3 ScheduledMemberActivities . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 ix