wiki:Correlator

Correlator in GDAL

Short description

Producing a single seamless mosaic from single frames (remote sensing data from aircrafts and UAVs)

Introduction

Today gathering of a large number of remote sensing data from aircrafts and UAVs is carried out. In most cases data contains single frames, so there is a task to create single seamless mosaic from several mutually overlapping images by finding tie points (“feature points”) and optimal correct transformations. Due to lots of photos, which should be processed, we need to have fast, robust, convenient and simple tool for handling images in automatic mode without close human participation. At present, GDAL doesn’t have such algorithm and even more there isn’t suitable specific third-party applications. Many geospatial open source projects use GDAL, such as Quantum GIS and GRASS, so existing a tool for stitching photos in GDAL can be useful and irreplaceable for images processing in the all dependant programs, can make usage of these software easier, more general and comprehensive.

Main idea

I propose to implement in GDAL correlator, which will carry out process of creation mosaic and simple geographical orientation using telemetry. According to my investigations, I’ll compare one of existing methods and my idea. First and foremost, this is the ordinary algorithm of creation mosaic images:

  1. Segmentation - initial photos are divided on many small square areas(patches) with similar parameters. Then algorithm transforms raster patches into smooth approximate vectorized figures.
  2. Correlation - finding the most corresponding patches, computing correlation coefficients between pairs of patches and initial orientation of images with affine transformation.
  3. Area correlation - this step is necessary because we need to clarify orientation (initial results are general due to approximate vectorization and smoothing)

But this approach is slow, because we need to compute vectorized contours (but this step unnecessary and too complicated in my opinion), and due to simplifying figures algorithm isn’t reliable. So, I’m going to implement another approach. The key point - speeded up and robust algorithms which underlie at the heart of algorithm. SURF algorithm - for fast and robust feature detection and FLANN algorithm as correlator for matching feature points. These methods are basis which should perform image processing quickly.

We suppose that photos have telemetry and can initially place photos in the right order using extracted GPS information (positions and maybe angles). This way we already have simple geographical binding. Ideally, user should provide images, telemetry and get seamless bound mosaic in the end. Images need to be without camera distortion, so user before start should execute optical correction of photos, Often data doesn’t contain DEM, and DEM is very approximate, so we’ll use essentially GPS information from telemetry. Another key point is that photos should be without camera’s distortion, i. e. before stitching need to perform images correction. Detailed steps of algorithm’s work:

  1. Load photos and telemetry. Extract GPS data, compute global orientation (maybe with angles).
  2. Find feature points in photos with SURF algorithm.
  3. Match points with FLANN algorithm. Steps 2 and 3 should be sufficiently fast.
  4. Compute averaged points. Provide points as GCP into GDAL GCP based polynomial transformer and get equalized points, images will be more like a orthogonal projection. Photos usually have approximate ortho projection and 2 neighbouring overlapping images should be very similar. This step is necessary for improvement of our mosaic, because after this we’ll get images which are closer to true ortho view.
  5. Computation of optimal affine transformation parameters. Optimization performed by gradient descent method.
  6. Apply transformations which we got at previous step. For ultimate mosaic we use GDAL images merge algorithm to fuse all images in one (requires images in one coordinate system).

Plan & Timeline

  1. Check and test all necessary methods/functions from OpenCV and GDAL for correlator implementation (20-25 days). At this moment, I should be able to have all necessary knowledge about transformations, image processing, according algorithms and able to develop my code.
  2. Get used to work with GDAL library, learn principles of development, find dependant functions and use them for utility. (7-15 days)
  3. Implement SURF-algorithm for searching points in image(“feature points”). (5-6 days)
  4. Implement correlator - match feature points on images and create pairs of points (“tie points”). Realization of FLANN algorithm (6-9 days)
  5. Test algorithms in GDAL. (2-3 days)
  6. Apply gradient descent method in GDAL for optimization - finding the best affine transformations, carry out tests (4-8 days).
  7. Create QuantumGIS user-friendly plugin for easy usage.(4-7 days)
  8. Test the whole implementation. (1-2 days)

Future ideas

Make acceptable to handle raw photos without telemetry and any additional data. I think that is quite possible because in my first research I didn’t rely on additional information about relief, GPS and camera parameters and tried to make universal algorithm. Maybe implement another optimization method instead of gradient descent. I’m interested in this project and in the algorithms which used here, my university study corresponds with this GSoC work, so definitely I won’t end up with mentioned here methods and ideas.

Project Progress

Github: https://github.com/migal-drew/GDAL-correlator

Blog: http://correlatorgsoc2012.blogspot.com/

GDAL Commits: r24868

Last modified 5 years ago Last modified on Aug 26, 2012 8:51:18 PM