Help for MARSAUTOTIE2

PURPOSE:
-------

To automatically gather tiepoints for a set of overlapping images.
The resulting tiepoints are output in OUT for use by other programs such as 
MARSNAV, MARSNAV2 or for manual refinement via MARSTIE.

MARSAUTOTIE2 supports any mission, instrument, and camera model supported by the 
Planetary Image Geometry (Pig) software suite.  However, the parameters are 
likely to be camera-specific, so some tuning may be required.

The main difference between MARSAUTOTIE and MARSAUTOTIE2 is that MARSAUTOTIE 
core algorithm is based on image correlation to find tiepoints whereas 
MARSAUTOTIE2 is based on keypoints detection, description and matching using
the Affine SIFT (ASIFT) approach.



PATENT, LICENSE, OPEN SOURCE CODE:
------------------------------------

MARSAUTOTIE2 is based on open source code which implements the ASIFT method 
which is based on two techniques that are patented:
[1] SIFT. Scale Invariant Feature Transform:
    Method and apparatus for identifying scale invariant features in an image.
    David G. Lowe, US Patent 6,711,293 (March 23, 2004). Provisional application
    filed March 8, 1999. Assignee: The University of British Columbia.
[2] Method and device for the invariant-affine recognition of shapes.
    Jean-Michel Morel, Guoshen Yu, French Patent FR2931277 (September 20, 2009),
    (US 8687920 B2). Assignees: Ecole Polytechnique, Ecole Normale Superieure.

In essence [1] and [2] refer respectively to the "SIFT" and "Affine" parts of 
the "Affine SIFT" technique. 

At the time of this writing, informal authorizations (email/phone 
correspondances) have been obtained to use these techniques in the MVOR (Multi-
View Object Reconstruction) project (AMMOS-MGSS) - marsautotie2 is part of this
project.  The context of use is for ops and scientific research. More formal 
agreement is currently under consideration.


****************

The ASIFT technique that is implemented in VICAR is based on open source code
implementation that has been obtained from the following publication:

Guoshen Yu, and Jean-Michel Morel, ASIFT: An Algorithm for Fully Affine 
Invariant Comparison, Image Processing On Line, 1 (2011), pp. 11-38. 
https://doi.org/10.5201/ipol.2011.my-asift

with companion source code obtained from: 
http://www.ipol.im/pub/art/2011/my-asift/demo_ASIFT_src.tar.gz

Source code use is subject to BSD license and is replicated further below.


****************

The original (downloaded) source code is a full program, i.e., not just a 
library and has been modified in the following manner:
1 - All elements not directly related to the ASIFT technique have been removed.
  That is the readme.txt, Makefile, the main, the orsa technique, the eigen 
  library, the input/output reading/writing, and some unused functions.
2 - The SIFT-related functions and routines have been gathered and stored into
  a library, namely libSift which is stored under proprietary/. In addition to 
  this rearrangement, some functions inside the SIFT library have 
  been streamlined or optimized. No algorythmic changes, but code cleaning, 
  reformatting, or optimizing. The SIFT library is composed of:
     - demo_lib_sift.cc, demo_lib_sift.h
     - sift_library.cc, sift_library.h
  demo_lib_sift implements the SIFT technique, whereas sift_library contains a
  series of tools that the SIFT technique use.
  A simple Makefile has been created to compile the SIFT library and which is 
  located in the same directory as this file.
3 - The Affine part of the ASIFT technique has been integrated into marsautotie2
  by necessity. Affected source code of marsautotie2 program that contains some 
  code (or rewritten code) based on the original source code are:
     - marsautotie2.cc
     - compute_asift_keypoints.cc
     - compute_asift_matches.cc  
  As such, marsautotie2 contains coded method  that is subject to patent 
  restriction and specific care must be taken when running or distributing this
  program.






EXECUTION:
---------

There are two ways to present input images:

marsautotie2 inp=(a.img,b.img,c.img,...) out=tiepoints.tpt
or
marsautotie2 inp=ascii_listoffiles out_tpt=tiepoints.tpt

where ascii_listoffiles is a text file containing the list of filenames
to include in the mosaic, one per record.  Up to 200 input images can be
listed.



USAGE:
-----

It is important that all images be connected to each other via tiepoints.
If an image or block of images is not connected, the entire block can "drift"
as a unit out of alignment during the nav process.  The program will report
single unconnected images, but not blocks of them.  

The program does not depends on having some initial pointing parameters in the
images to find tiepoints, except if geometric constraint is applied (see below).
The Affine SIFT (ASIFT) will find and match features that are scale, rotation, 
translation and affine invariant. This means that, locally at least, ground 
features are assumed planar. This, of course, is not necessarily reality, but 
experience shows that in most cases, the techniques works on real images. 
Too "unplanar" or "parallax distorted" features will not be matched correctly 
or at all.  



METHOD:
------

The process is composed of three main steps. The outline is as follow:

For each input (each image): *****************

1: Find keypoints
A keypoint is a location in the image that shows "interesting" features. That 
is, a location which could a priori be quite uniquely defined by its direct
surrounding. This seach for keypoints is carried out at different "octave", 
that is at different image size (the image size is iteratively reduced by a 
factor of 2), and at different "scale" (different levels of blur applied at 
each given octave). This allows to find keypoints at different level of 
resolution and zoom.

2: Describe keypoints
Once keypoints are identified, their "signature" is computed. A set of 
statistics that describe the keypoints are defined from the keypoint 
surrounding. The goal is to describe as precisely as possible the keypoints so
that its signature uniquely identify it. 

For each image pairs that are tiepointed: ******************

3: Match keypoints
Each keypoints (detected in the previous step) of the "left" image are compared 
to each keypoints of the "right" image. If they match, then the two keypoints
form a tiepoint. The comparison is based on the description of the keypoints.
The euclidean distance between the two descriptions is computed. If the 
distance is small, that indicates that the two keypoints "look" similar. 



There are a number of parameters to fine tune each of these steps and to 
add additional constraints to improve the number and quality of the tiepoints.
The main parameters are now explained.


Keypoints detections
---------------------
The ASIFT detects keypoints that are scale, rotation, translation and affine
invariant. Rotation and translation invariance are obtained through 
normalization whereas scale and affine invariance are obtained through
simulation. Translation invariance is reached simply by removing the pixel
location from the keypoint description. Rotation invariance is reached by 
computing the main direction (gradient) of the patch surrounding the keypoint 
and centering the description with respect to this main direction. Scale and
affine invariance cannot be obtained from normalization and are simulated. The
image is transformed through a series of scale and affine transformations and
keypoint detection and description are carried out on each of these simulations.

A set of parameters allows to control the actual keypoint detection and 
simulations, i.e., how many scales and affine transforms are going to be 
simulated. See NUMTILTS, OCTAVE, SCALES, UPSAMPLE, INITSIGMA, DOGGTHRESHOLD, 
EDGETHRESHOLD, and BORDER.
There is a tradeoff between extensive number of simulations and computing time. 
See NBESTMATCHES for an optimized approach.


Keypoints descriptions
----------------------
Once keypoints are identified, they are "described". Statistics on the keypoint
surrounding are computed and an (oriented) histogram of the pixels distribution
around the keypoints is formed to "describe" the keypoint. An histogram of 128
bins is used traditionally. No parameters are made available for now as they 
are seldomly changed.


Keypoints matchings
-------------------
Once the keypoints are identified and described for all images, they are 
matched. 
By default, all input images are matched to all others. An alternative is to
match images sequentially  depending on the input list order. This can be
tuned with PAIR_MATCH.
When two images are matched, all keypoints of the left images are matched to 
all keypoints of the right image. In practice, a loop over the left keypoints
is involved, where each left keypoint is matched to all right keypoints 
(1 "left" vs all "right"). The euclidean distances between the left keypoint 
descriptor and the right keypoints descriptors are computed. The distance ratio
between the smallest and second-to-smallest distances is computed. If the ratio 
is below a threshold then the matched is deemed valid: the left keypoint and
the right keypoint with the smallest distance are paired as tiepoint. 
A small ratio means that the keypoint is much more similar to the left keypoint 
than all the other ones which add confidence on the matching. On the contrary, 
a large ratio (close to 1) indicates that the descriptions of the smallest and 
second-to-smallest keypoints are similar and cannot confidently discriminate one
from the other. Note that the natural alternatives for matching which would 
consist of simply selecting the smallest distance keypoint or setting up a 
threshold on the distance itself either don't work or are difficult to adjust. 
Simply selecting the smallest distance is not reliable as there will always be a 
"smallest" even if the two images are completely unrelated. Adjusting a hard 
threshold on the distance is not trivial to do. 
Adjusting the matching ratio is done through MATCHRATIO parameter.  

In the matching strategy described above, each and every keypoints in left are
matched to all keypoints in right. The more keypoints are to be compared, the 
more chance you could match two keypoints that satisfy the matching ratio 
criteria but are two different ground point locations. As a matter of fact, 
SIFT and ASIFT generates a lot of these outliers. One way to reduce them is to
restrict the pool of right keypoints that are matched to a left keypoint by 
bringing in additional constraints. There are two options available.
- If the camera geometries are available, the epipolar constraint can be used. 
That is, for a keypoint in left, a subset of the right keypoints is selected 
based on the distance of these keypoints from the epipolar line of the left
keypoint in the right image. This constrains the match to satisfy a closeness to
the epipolar line (where it is supposed to be). See EPIMAXDIST for applying 
this constraint.
- The subset of right keypoints can be reduced based on their position relative
to the left keypoint position. For instance, if left keypoint is at position
(100,100) (pixel coordinates) in the left image, then the subset of right
keypoints that are compared to the left keypoints could be limited to the 
keypoints that are within 10 pixels of (100,100) in right image. This assumes 
that features in left images are expected to be found within the same location 
in right image. See POSMAXDIST for that approach.
In both case, i.e., EPIMAXDIST and POSMAXDIST, if the subset of keypoints only
contains one keypoint, no matching is done as there is no second-to-smallest to
compare against. The drawback of such approach is that potentially we could 
delete a good match.

In addition to the geometric constraint, a set of filtering is applied by
default (non parameter) to the tiepoint list which will filter out 
non-unique tiepoints, one-to-multiple or multiple-to-one tiepoints. 
Non-uniqueness happens because of the various affine simulations,
and one-to-multiple (i.e., more than one tiepoints have the same left pix
coordinates but different right coordinates) and multiple-to-one are 
natural artefact of the matching step.

A post-processing filtering step based on a local graph is available (See GTM).
Once the tiepoints are found, a local analysis is carried on to find and
remove outliers. The approach is based on the assumption that, locally, the
parallax effect is smooth and a set of close points in one image should 
corresponds to the associated (tiepoint-wise) points in the other image.
This method is an implementation of the paper:
"A robust Graph Transformation Matching for non-rigid registration"
Image and Vision Computing 27(7):897-910. June 2009



The program output a tiepoint file in XML format.


IMAGE PAIRING STRATEGIES
The input is a list of images that need to be tiepointed. There are different
strategies available to "pair" image together. Strategies are set through
PAIR_MATCH, REFIMAGE, IGNORE and IGNORE_INTRA.
The default strategy is to tiepoints all images against all the others.
PAIR_MATCH offers three kind of strategies that are related to the order of the
images in the input list (see PAIR_AMTCH for more details).
- PAIR_MATCH=0: all-vs-all (the default)
- PAIR_MATCH > 0: "sliding window" with overlap. The value of PAIR_MATCH
indicates the number of images before and after the current image that will be
tiepointed together. For instance PAIR_MATCH=1, means that each group of images
composed of the a given image, the one before and the after in the list will be 
tiepointed together (i.e., (1,2), (1,2,3), (2,3,4), (3,4,5), etc...). If 
PAIR_MATCH=2, then each group of images composed of the a given image, the two 
before and the two after in the list will be tiepointed together (i.e., (1,2,3), 
(1,2,3,4), (1,2,3,4,5), (2,3,4,5,6), etc...). 
- PAIR_MATCH < 0: "sliding window" with NO overlap. The (absolute) value of 
PAIR_MATCH indicates the number of images that will be tiepointed together. 
For instance PAIR_MATCH=-1, means that a (1,2), (2,3), (3,4), (4,5), etc... will 
be tiepointed. If PAIR_MATCH=-2, then
(1,2,3), (3,4,5), (6,7,8) etc...

Once the pair list is defined, it can be further refined using REFIMAGE, IGNORE
and IGNORE_INTRA. It is likely that these parameters will be used with 
PAIR_MATCH=0, but that is not a requirement.
See definition of these parameters for further details. Here are a couple of
use-cases that involves subgroup of images:
Assume we have a list of input images 1,2,3,4,5,6,7,8,9,10: 
PAIR_MATCH=0 REFIMAGE=9,10 will cause to tie point images 1,2,3,4,5,6,7,8 
between each other and with 9 and with 10. But 9 and 10 won't be tiepointed
between each other.

PAIR_MATCH=0 REFIMAGE=9,10 -IGNORE_INTRA will cause to tie point images 
1,2,3,4,5,6,7,8 with 9 and with 10 only. 




Execution:
---------

$MARSLIB/marsautotie2 inputImagelist.lis outputTiePoints.tie
Will launch the process using standard SIFT (not ASIFT) where all left keypoints
will be matched to all right keypoints.

$MARSLIB/marsautotie2 inputImagelist.lis outputTiePoints.tie NUMTILTS=3 
EPIMAXDIST=20
Will launch the process using ASIFT with 9 affine simulations (nb of 
simulations is defined from numtilts, but is not equal to numtilts) and 
epipolar constraint is to be enforced.


Parallel Processing
-------------------
This program has been parallelized using Open MP (OMP), which is built in to the
g++ compiler. By default the number of threads used equals the number of cores 
on the machine where the program is being run. 

There are two locations where the parallelization occurs:
- During the keypoint detection and description. Parallelization happen on the 
number of affine simulations to carry. If no affine simulation is set up in the
parameters, this step is not parallelelized.
- During the matching of the keypoints. Again, the parallization is done on the
number of affine simulations.

In essence, the more affine transforms, the more parallelization. If the input 
consists in only two images with no affine (i.e., regular SIFT), the process is
essentially not parallelized.

of threads can be controlled by setting the OMP_NUM_THREADS environment
variable before running the program.  There are numerous other OMP variables
that can be set; see the OMP documentation.  However, the number of threads
is the only one that is likely to be useful in most cases.



LICENSE:
--------

As mentionned earlier, this program uses third party open source implementation
of 2 techniques that are patented. The following display the license and 
disclaimer of the program used.

**************************************************************

Copyright (c) 2011, Guoshen Yu and Jean-Michel Morel
All rights reserved.

The source code files in this directory implement as tightly as 
possible algorithms described in this IPOL article. They are made 
available to the exclusive aim of serving as scientific tools enabling 
the verification of the soundness and completeness of the algorithmic 
descriptions.

These source codes implement an algorithm possibly linked to the patent 
[1][2]. Compiling or running this code may violate patents in certain 
countries. For this reason, the use of the source files 
- demo_ASIFT.cpp
- compute_asift_keypoints.cpp
- compute_asift_matches.cpp
- demo_lib_sift.cpp
may be restricted in certain countries to non profit research and non profit 
educational purposes. In certain countries, redistribution or commercial 
use of these source files may require the  consent of the patent owner. 

[1] Jean-Michel Morel and Guoshen Yu,  Method and device for the invariant 
affine recognition recognition of shapes (WO/2009/150361), patent pending.

[2] David Lowe  "Method and apparatus for identifying scale invariant 
features in an image and use of same for locating an object in an 
image",  U.S. Patent 6,711,293.

In short, be careful before you download, compile, use, modify, or 
redistribute these source codes. The situation being different for every 
country and changing over time, it is your responsibility to check that 
you are not infringing a patent by using this source code. IPOL therefore 
invites potential users to consult a patent lawyer. If and only if you are
free from any patent restriction, then you can enjoy the BSD license terms.

The source code in the subdirectory third_party comes from the Eigen 
library, which is LGPL-licensed.
(see http://www.gnu.org/copyleft/lesser.html)

fproj.cpp, frot.cpp, orsa.cpp, libMatch, libNumerics
copyright (C) 2007-2010, Lionel Moisan <Lionel.Moisan@parisdescartes.fr>,
Universite Paris Descartes, distributed under the BSD license.

With the exception of the files mentioned above, redistribution and use 
in source and binary forms, with or without modification, are permitted
provided that the following conditions are met: the rest of usual BSD 
license follows.

BSD LICENSE

Redistribution and use in source and binary forms, with or without
modification, are permitted provided that the following conditions are
  * Redistributions of source code must retain the above copyright
    notice, this list of conditions and the following disclaimer.
  * Redistributions in binary form must reproduce the above
    copyright notice, this list of conditions and the following
    disclaimer in the documentation and/or other materials provided
    with the distribution.

THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
HOLDER BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

This license file must be retained with all copies of the software,
including any modified or derivative versions.


**************************************************************






HISTORY:
-------

02-02-18  Initial marsautotie2. 

COGNIZANT PROGRAMMER:  Francois Ayoub

PARAMETERS: