Week #13

I have completed correlator — Detection feature points and searching corresponding points on different images.
This week I finished documentation for my code, performed refactoring and cleaning up.
I implemeted in GDALCorrelator file 2 main external methods for searching and matching feature points. Methods provide simple and seamless usage of my internal classes.
My mentor is going to implement GCP producing based on my realization, adapt and migrate correlator to GDAL.
I'll devote my remaining time to refining documentation and helping in porting correlator.

I participate in GSoC program for the first time, and it's an unforgettable and priceless experience for me :)

Week #12

This week I've sucessfully ported code for searching corresponding points to C/C++, so it's possible to use algorithm in GDAL now.
https://github.com/migal-drew/GDAL-correlator
Method uses RGB values to prepare grayscale image as 2-dimensional array of pixels brightness, than finds feature points and matches their. User should provide threshold values and octave numbers. Octave affects on the size of detected points. So, for small images you should use small octave numbers, and vice versa. For example, octaves 2-3 are good for 640x480 and 1024x768 images.

I recommend to use the small number of octave ranges (one-two), for instance numbers 2-2, 4-4, 2-3, but not 1-6 or 2-8, besause it slows down computation speed in several times. Also I don't recommend use high resolution photos. In future I'm going to fix this computation issues. In this project I concentrated on reliable results more than speed.
Another important thing that algorithm is scale and rotation sensitive. The images should have similar size and angle (difference up to 10-15 degrees).
The results are better than shown in my previous post, because I implemented simple false matching detection, and algorithm tends to find more robust matches.

I'm planning to spend remaining time cleaning up code (improving readability) and working on documentation, and I need to discuss with my mentor about current situation and specify completed goals.

*UPDATED 
Actually algorithm is scale invariant. I perfomed a test using images with different resolutions. Octave range - 1-3 for both images. Left picture - 512x512, right - 300x300.

 

 

Right - 640x480, left - 400x300

Here you can see how many robust matches algorithm is able to find. It's near perfect, wrong detections are possible very rarely (I was planning to implement good technique for false detetions pruning - RANSAC, but project has lagged because of his complexity, so I decided to make another simple, but still admissible method. I'm very excited of that I implemented, and it works as I've planned in the begin.

Week #11

This week I implemented descriptors and method for matching points (based on euclidean distance and bruteforce comparison). Matching requires value of threshold. If threshold is low - number of coressponding points is small, but results are robust, and conversely.
https://github.com/migal-drew/SimpleSURF_csharp

Next week I'm planning to port my code in GDAL, test algorithm and work on documentation.

Examples:

 

Here is result in case if threshold is too high (false detections intersect other "true" matches)

 Test with "sunflower field" image

And test with "standard" image in computer vision ("lenna image")

Week #10

This week I implemented working version of algorithm for searching feature points in image (based on SURF algorithm, but I omitted some tricky details - original is faster, I'll improve computation speed later).
Code:  https://github.com/migal-drew/SimpleSURF_csharp

Next week I'm planning to write code for finding descriptors and matching of identical points. If I don't come across problems, I'll begin to port methods in GDAL.

Week #9

This week I didn't have enough free time, so results aren't great.
I tried to improve intial orientation of photos using GPS, but task turned up slightly more complicated than I expected, and I couldn't finish in time for weekly report.
Next week I'm planning continue my previous week goals and achieve more progress.

Week #8

This week I tried to apply code for initial positioning of photos based on GPS information

https://github.com/migal-drew/GPS_assembling

Program creates .jgw and .prj files for every input image.

(I use this sample of telemetric information -

ftp://www.aerialrobotics.eu/winter-high-overlap/trace.txt.TRIG1-001.pix4d.dat )

But for now I couldn't figure out appropriate camera parameters, so photos aren't aligned properly.

Next week I'm planning solve this ussue and continue work on searching feature points.

 This is current results. As you can see, positions and angles look good, but images don't match with each other (I think that is due to wrong scaling - wrong pixel size).

P.S. In this year I with my friends participate in ICFP contest for the second time. I hope we will reach some good results :)

Week #7

This week I started to work on SURF algorithm

https://github.com/migal-drew/SimpleSURF_csharp

Also I started to implement initial orientation and geographical positioning using GPS information (C++ with GDAL library). Unfortunately, I've encountered some problems with with GDAL functions and with my programming environment - CodeBlocks and Eclipse CDT.

 I made another example of stitching. The photos are from my proposal, but now with my optimization code (in proposal - Opencv built-in transformer). 

Before and after

For more details read my previous posts.

Working on correlator

I started to work on simplified version of SURF algorithm. It's more complicated than I expected, and I decided to start with C sharp implementation (I hope to quickly port code to C++ using GDAL API).
Also I will need to test algorithm.

For the moment I made computation of integral image:
https://github.com/migal-drew/SimpleSURF_csharp

Next day I'm planning to add wavelets and Hessian computation. Also I have some ideas and I'll verify their. My official weekly report and last results will be in the next post.

Problems and current results

Recently I added calculation of initial parameters (reverse affine transformation using 3 points). Now algorithm works with parameters which are near to optimum. As I expected, optimization process (gradient descent method) became faster (in previous solution, initial parameters was zeros).

But I still didn't solve problems with my LMA implementation. LMA can't improve initial parameters. It seems to me that I made some difficult to detect mistakes.

I think that I should take a break from optimization and implement simplified version of SURF. I hope that I'll have some code for midterm.

What I have today (in all examples I used gradient descent):

 Example #1

 Initial images

 

Result after initial orientation (using 3 points)

(white dots are feature points, white lines - gaps between similar points)

Result after 900 iterations

Example #2

Initial images  

 

 

 Result after initial orientation (using 3 points)

 

Result

Example #3

Initial images

 

Result

 

So, gradient descent is Ok for 2 images. Of course, it's very slow, nevertheless it works. But I don't know what happens if I apply this approach to several images (more than 2). There is only one way to check out - make implementation. If I have a time, I'll try to code this.

Week #6

 This week I passed my exams and finally I'm able to spend more time on project. I think that on next week I'll make progress and write a real code (not for testing purposes).

But today I'm stuck. I solved problem with singular matrix using approximate computation (least squares method from numpy = lstsq (http://docs.scipy.org/doc/numpy/reference/generated/numpy.linalg.lstsq.html)), but my implementation of LMA method converges very poorly. I fixed some errors and tried to tune parameters, but it wasn't successful. In some cases, I get admissible results (mosaic is good and time of solving is small), in others algorithm stuck and can't overcome strange minimum. I didn't figure out why it happens.

So, previous oprimization based on Gradient descent algorithm looks better, and if I can't apply LMA, I'll try gradient. But I really hope to solve my problems with LMA.

I corrected my code and tuned parameters, all links from my weekly report #5.

https://github.com/migal-drew/OpencvTransform/blob/master/src/mosaicing_lma.py
https://github.com/migal-drew/OpencvTransform/blob/master/src/levenberg_marquardt.py
https://github.com/migal-drew/OpencvTransform/blob/master/src/utilities.py

Brief results:

1 picture - LMA,  error:

before - 20516, after - 4669 and requires only one (!) iteration (its'really fast!)

I got also error about 4161 with 43 iterations (then algoritm totally converges) 

2 picture - also LMA, but here, as you can see, algorithm fails (despite of number of iterations or values of thresholds, method stucks)

Interesting results with non aerial photos

LMA method (the best mosaic as I could get)

The same photos, but Gradient descent algorithm (it looks much better than previous with LMA)

It's all for this week!

Week #5

On this week I tried to implement Levenberg-Marquardt algorithm (LMA http://en.wikipedia.org/wiki/Levenberg-Marquardt_algorithm), but I encountered some problems. The Hessian matrix, which I've computed, is non-invertible (singular), so method doesn't work.
Therefore I should find another solution or modify algorithm.

This code finds feature points and invokes LMA
https://github.com/migal-drew/OpencvTransform/blob/master/src/mosaicing_lma.py
Main LMA code
https://github.com/migal-drew/OpencvTransform/blob/master/src/levenberg_marquardt.py
And I made some minor changes in
https://github.com/migal-drew/OpencvTransform/blob/master/src/utilities.py

Week #4

This week was unsuccessful because of my university exams and I was unable to follow my shedule.
I only started to figure out how SURF algorithm works, and I'm planning to understand Levenberg-Marquardt method. Also I'll try gdalwarp and/or gdaltransform utilities and decide will it be useful or not. It looks like my project is frozen, but I hope to catch up.

Previous similar approach

Recently I've discovered this paper http://www.gmat.unsw.edu.au/snap/publications/xing_etal2010c.pdf
The main algorithm and crucial parts of mosaicing process described here almost exactly match with my ideas. Of course proposed in this publication method is much more sophisticated and includes additional optimization steps as applying of Kalman filter and Levenberg-Marquardt algorithm. But thr main idea is the same - matching corresponding points and minimization of square function.

Week #3

I have exams in my university, so I didn't make any sufficient progress in  GSoC work. Probably I'll spent another week on my study. But my current goals stay the same and I hope to return to project soon as I'll have any free time.

Week #2

It was a busy week, so I didn't reach my goal to get more familiar with algorithm of searching feature points, but I have some new ideas.
Feature searching algorithms are versatile and they can give diverse results on photos. Some methods detect more points than others on the one photo, and a little amount of points on another. It happens due to quality of the landscape and number of well-marked objects as single trees and buildings. That's why we need to select the most stable and robust algorithm which can provide enough points in almost all cases.
FAST Corner Detector algorithm is extemely speedy and simple, but SURF is more robust and tends to search more points. I think that it would be interesting to compare these and others algorithms and pick the best. Today many feature searching approaches exist and they are being developed and improved, so I need to briefly investigate their advantages and disadvantages.
I think that the primary task is to enhance optimization and try a Levenberg-Marquardt method. I hope that the stitching process will work significantly faster.
http://en.wikipedia.org/wiki/Levenberg-Marquardt_algorithm

First week

1. I compiled GDAL and implemented simple prototype of gradient descent method for searching
   and optimization of transformation parameters for 2 photos. Of course, it's far away from perfect,
   but it looks promising.
2. I think that I'll start to learn SURF algorithm, how it works, maybe I'll begin to code prototype to verify my awareness. It's a very sufficient part of stitching processing.
3. Usually it's very hard to start something. You have to dive into details and get used to work
   with many new things. I have lots of homeworks in my university study and exams are coming.
   So for now it's extremely exausting task to mix SoC coding and study.

Cool example of stitching results at this moment.
Here are 3 iterations - initial, intermediate and final. White lines are distances between corresponding points on both images. With every step, algorithm moves points (images) closer to each other, so distances (errors) become extremely small.

Few days ago I worked on gradinet descent method for optimized stitching. I wrote the dirty implementation on python + numpy. I've done some primitive tests and verified in C# little program, which I made for viewing points before and after optimization. I've discovered that algorithm converges, and even it requiers sometimes lots of time (but still admissible), it seems to me that I'm on right way.

Recently I have been working on an optimization method - gradient descent
Here is a Google doc