As the end of my second year of studying software engineering comes to its end, I would like to reflect on what has been some of my most enjoyable work. The first part of this series, I will be talking about the latest piece of work I submitted – a panorama image stitching algorithm.
Throughout this year, the most consistently enjoyable module has, without a doubt, been Functional Programming. Where we used Matlab to solve various image-related issues. Across both semesters we were tasked with restoring distorted images as well as the aforementioned panorama image stitching. No doubt I’ll talk about my image restoration algorithm at some point, but for now I want to focus on my image stitching.
Before talking about the algorithm itself, I want to give context as to the requirements set forth by the specification. As I received high marks for my other coursework, again I wanted to achieve high marks with this algorithm. Hence to get the >70% I’d need to maintain throughout my studies for 1st class honors, the algorithm would need to do the following:
- Successfully stitch all 20 of the supplied images
- Be largely generic
- Not require manual selection of central/starting image
- Produce a visually plausible image
Taking all those requirements into consideration and after developing my algorithm, you can see the result at the top of the article. Obviously there are some problems with the stitching and it doesn’t crop borders. This wasn’t done for the coursework as it wasn’t required and I didn’t want to spend time on something that would have a negligible impact on marks.
My (Abandoned) Initial Approach
I had an idea before I created what would be my final coursework. I still think it could work, however I ran into problems when trying to get Matlab’s proprietary functional language to cooperate with my design. I should note this is a theory and mightn’t work.
To start, the algorithm would detect features from all of the images using the SURF feature detection algorithm. As this is done, the results are stored for later and features aren’t detected later for performance reasons. Then, using the extracted features and points, the algorithm will compare each image to every other image’s features.
Doing this, the algorithm would build a tree of image relationships. Using the amount of shared features between images, each image should have a parent which is the image it shares the most features with. Once this is done, the image with the most children should be taken, their parent relationship removed, and is now our central root image. Building a tree like this, for example.
Taking this relationship tree, the algorithm should then find the geometric transformations between each parent and child only. Using this, each child should know the required transformation it’d take to successfully be stitched onto its parent.
Starting with the root image and its children, the algorithm should move to the bottom of the tree and start with end child images, recursively add together all of its parents’ transformations, finally adding this current child’s transformation. This should result in the image being transformed to the correct location as it’d appear in the final image.
Eventually moving across all the images, this should hopefully result in a well stitched panorama image.
However, despite being a theory I still realise some of the potential limitations of the algorithm. The main one being that any flaws in an image’s estimated transformation would also be inherited by its children. Like I said, I never got round to fully implementing this but the results I did get were somewhat promising – with the experience I have now I feel like I could implement this.
If successful, this approach would have fulfilled the requirements set out by the algorithm. Perhaps even more so than the approach I did end up using.
The actual submitted algorithm, however, was much more simple and straightforward than the proposed algorithm above. At this point, it was a Tuesday evening. I had been grinding all day for the past 10 days on coursework – especially a group project in which nobody else in my group had done any work. I had to work on this for a Thursday deadline, realising I couldn’t get the other approach working I switched to a different algorithm which I could implement and should produce a great panorama.
Starting, it’s the same as the other method. Reading in all the images we want to stitch together and extract their features. However, unlike the other approach I alter the contrast of the image which results in a lot more shared points between matching images, as shown below in a comparison. As you can see, it resulted in a lot more matched features and results in a clear correlation that we can use to transform one image onto the other. The brickwork here proved to be a hard challenge for the default Matlab SURF feature detection but with some image manipulation we can get a much better result.
With this now done, I simply selected the first image which was read into the algorithm and use that at as our base starting image. After this, I looped around the remaining images to be added and compared their features to the overall panorama – which consists of just one image at this point.
As images are compared, to ensure the resulting panorama was highly accurate, I enforced a threshold to the number of shared points. Typically around 80 points. After meeting this threshold, only then would the image be transformed onto the panorama. Thus removing it from the pool of remaining images to add.
As images are being added to the panorama, two versions of it are kept. One is the result that will be displayed to the user and one is purely kept for feature detection. Whilst the transform estimation and feature detection is performed on one of the panoramas, both panoramas will have images transformed onto them. One being the raw unprocessed image and the grayscale contrast-adjusted image.
Once an image has been added to the panorama, the panorama’s features are detected again. I had considered finding a way to add the stitched image’s features vector to the already existing panorama features. However due to the image being warped and distorted, it resulted in major artifacts and I didn’t have time to find a solution. Solving this problem would result in a massive increase to the algorithm’s performance.
After looping around all the images till there are none left, the result is the image at the top of the article. This is assuming that all images are, infact, part of the panorama and can be stitched. Additionally, there’s a user-editing configuration file which is supplied to the algorithm. Which is mainly used to configure the estimation of geometric image transformations.
At the start of this, I listed the requirements of the algorithm. Saying that the solution had to be “largely generic” and having a configuration file makes it less generic. The genericness of the algorithm is largely related to the way images are stitched. For example, my solution versus manually stitching image A to B then B to C and so on. Developing an actual full generic solution is simply beyond the scope of a second year piece of coursework.
Having completed the algorithm, I tested it against various datasets. The coursework result was actually the worst result I obtained from the algorithm. With a maximum distortion of around 4 pixels between images, where you can see the seams of the panorama. Below are some other results using between 8 and 14 images that have been stitched together.
After submitting and receiving my mark, I got 97% for this piece of coursework. Losing marks for some discolouration in some of the images – I had highlighted this issue but not considered fixing it due to time constraints. Overall I am extremely pleased with my work and I think the results are exceptional. Especially considering I had to scrap most of my work and write the submitted algorithm in the best part of an afternoon through evening. If you want to download the program for MatLab and mess around with it yourself, the source code can be found here.