www.pudn.com > bsiftC_.rar > MatchKeys.cs

/* MatchKeys.cs
 *
 * Keypoint file correlation functionality.
 *
 * (C) Copyright 2004 -- Sebastian Nowozin (nowozin@cs.tu-berlin.de)
 *
 * "This software is provided for non-commercial use only. The University of
 * British Columbia has applied for a patent on the SIFT algorithm in the
 * United States. Commercial applications of this software may require a
 * license from the University of British Columbia."
 * For more information, see the LICENSE file supplied with the distribution.
 */

using System;
using System.IO;
using System.Text;
using System.Collections;
using System.Runtime.Serialization;
using System.Runtime.Serialization.Formatters.Binary;


public class MatchKeys
{
	public ArrayList FindMatchesBBF (KeypointN[] keys1, KeypointN[] keys2)
	{
		// TODO: swap so smaller list is searched.

		ArrayList al = new ArrayList ();
		foreach (KeypointN kp in keys2)
			al.Add (kp);
		KDTree kd = KDTree.CreateKDTree (al);

		ArrayList matches = new ArrayList ();
		foreach (KeypointN kp in keys1) {
			ArrayList kpNNList = kd.NearestNeighbourListBBF (kp, 2, 40);

			if (kpNNList.Count < 2)
				throw (new Exception ("BUG: less than two neighbours!"));

			KDTree.BestEntry be1 = (KDTree.BestEntry) kpNNList[0];
			KDTree.BestEntry be2 = (KDTree.BestEntry) kpNNList[1];

			if ((be1.Distance / be2.Distance) > 0.6)
				continue;

			KeypointN kpN = (KeypointN) be1.Neighbour;

			matches.Add (new Match (kp, kpN, be1.Distance, be2.Distance));

			/*
			Console.WriteLine ("({0},{1}) ({2},{3}) {4}, 2nd: {5}", (int)(kp.X + 0.5),
				(int)(kp.Y + 0.5), (int)(kpN.X + 0.5),
				(int)(kpN.Y + 0.5), be1.Distance, be2.Distance);
			*/
		}

		return (matches);
	}

	/*
	public ArrayList FindMatches (ArrayList keys1, ArrayList keys2)
	{
		ArrayList matches = new ArrayList ();

		//KDTree kd = KDTree.CreateKDTree (keys2);
		foreach (Keypoint kp in keys1) {
			double distNearest = Double.PositiveInfinity;
			int nearest = -1;
			double dist2Nearest = Double.PositiveInfinity;
			int nearest2 = -1;

			for (int kn = 0 ; kn < keys2.Count ; ++kn) {
				Keypoint kp2 = (Keypoint) keys2[kn];

				double dist = Math.Sqrt (KDTree.DistanceSq (kp, kp2));
				if (dist < distNearest) {
					nearest2 = nearest;
					dist2Nearest = distNearest;

					nearest = kn;
					distNearest = dist;
				}
			}

			if (nearest == -1 || nearest2 == -1)
				continue;

			if ((distNearest / dist2Nearest) > 0.6)
				continue;

			matches.Add (new Match (kp, (Keypoint) keys2[nearest]));

			Console.WriteLine ("({0},{1}) ({2},{3}) {4}", (int)(kp.X + 0.5),
				(int)(kp.Y + 0.5), (int)(((Keypoint) keys2[nearest]).X + 0.5),
				(int)(((Keypoint) keys2[nearest]).Y + 0.5), distNearest);

		}

		return (matches);
	}
	*/

	public static ArrayList FilterJoins (ArrayList matches)
	{
		Hashtable ht = new Hashtable ();

		// Count the references to each keypoint
		foreach (Match m in matches) {
			int lI = (ht[m.Kp1] == null) ? 0 : (int) ht[m.Kp1];
			ht[m.Kp1] = lI + 1;
			int rI = (ht[m.Kp2] == null) ? 0 : (int) ht[m.Kp2];
			ht[m.Kp2] = rI + 1;
		}

		ArrayList survivors = new ArrayList ();
		int removed = 0;
		foreach (Match m in matches) {
			//Console.WriteLine ("match: {0}, {1}", (int) ht[m.Kp1], (int) ht[m.Kp2]);

			if (((int) ht[m.Kp1]) <= 1 && ((int) ht[m.Kp2]) <= 1)
				survivors.Add (m);
			else
				removed += 1;
		}

		return (survivors);
	}

	public static void FilterNBest (ArrayList matches, int bestQ)
	{
		matches.Sort (new Match.MatchWeighter ());
		if (matches.Count > bestQ)
			matches.RemoveRange (bestQ, matches.Count - bestQ);
	}
}


public class Match
{
	KeypointN kp1;
	KeypointN kp2;
	public KeypointN Kp1 {
		get {
			return (kp1);
		}
	}
	public KeypointN Kp2 {
		get {
			return (kp2);
		}
	}

	double dist1;
	public double Dist1 {
		get {
			return (dist1);
		}
	}
	double dist2;
	public double Dist2 {
		get {
			return (dist2);
		}
	}

	private Match ()
	{
	}

	// dist1: distance between kp1/kp2,
	// dist2: distance between kp1 and kp3, where kp3 is the next closest
	//   match
	public Match (KeypointN kp1, KeypointN kp2, double dist1, double dist2)
	{
		this.kp1 = kp1;
		this.kp2 = kp2;
		this.dist1 = dist1;
		this.dist2 = dist2;
	}

	public class MatchWeighter : IComparer
	{
		private double distExp;
		private double quotExp;

		public MatchWeighter ()
			: this (1.0, 1.0)
		{
		}

		// The formula goes like this, with lowest weight being best matches:
		// w(kp) = kp.dist1^{distExp} *
		//     {\frac{1}{kp.dist2 - kp.dist1}}^{quotExp}
		//
		// This means, as both dist1 and dist2 are in [0.0 ; 1.0], that a high
		// distExp exponent (and distExp > quotExp) will make the absolute
		// distance for the best match more important. A high value for
		// quotExp will make the difference between the best and second best
		// match more important (as in "how many other candidates are likely
		// matches?").
		public MatchWeighter (double distExp, double quotExp)
		{
			this.distExp = distExp;
			this.quotExp = quotExp;
		}

		public int Compare (object obj1, object obj2)
		{
			Match m1 = (Match) obj1;
			Match m2 = (Match) obj2;

			double fit1 = OverallFitness (m1);
			double fit2 = OverallFitness (m2);
			if (fit1 < fit2)
				return (-1);
			else if (fit1 > fit2)
				return (1);

			return (0);
		}

		public double OverallFitness (Match m)
		{
			double fitness = Math.Pow (m.Dist1, distExp) *
				Math.Pow (1.0 / (m.Dist2 - m.Dist1), quotExp);

			return (fitness);
		}
	}
}


public class MultiMatch
{
	KeypointXMLList[] keysets;
	public KeypointXMLList[] Keysets {
		get {
			return (keysets);
		}
	}

	// Global k-d tree, containing all keys.
	KDTree globalKeyKD;
	// Global key list, containing Keypoint elements
	ArrayList globalKeys;

	// Global match list containing Match objects
	ArrayList globalMatches;

	// Partitioned matches
	MatchSet[,] matchSets;
	int imageCount;

	ArrayList filteredMatchSets;

	public void LoadKeysetsFromMemory (ArrayList memlist)
	{
		imageCount = memlist.Count;
		keysets = (KeypointXMLList[]) memlist.ToArray (typeof (KeypointXMLList));
	}

	public void LoadKeysets (string[] filenames)
	{
		imageCount = filenames.Length;

		keysets = new KeypointXMLList[imageCount];
		for (int n = 0 ; n < imageCount ; ++n) {
			KeypointXMLList keys = KeypointXMLReader.ReadComplete (filenames[n]);
			Console.WriteLine ("Loaded {0} keypoints from {1} for image {2} ({3}x{4})",
				keys.Arr.Length, filenames[n], keys.ImageFile, keys.XDim, keys.YDim);

			keysets[n] = keys;
		}
	}

	// Matches between two images
	public class MatchSet
	{
		string file1;
		public string File1 {
			get {
				return (file1);
			}
		}
		string file2;
		public string File2 {
			get {
				return (file2);
			}
		}
		public int xDim1, yDim1, xDim2, yDim2;

		ArrayList matches;
		public ArrayList Matches {
			get {
				return (matches);
			}
			set {
				matches = value;
			}
		}

		// The best result of the RANSAC matching
		ImageMatchModel bestMatchFit = null;
		public ImageMatchModel BestMatchFit {
			get {
				return (bestMatchFit);
			}
			set {
				bestMatchFit = value;
			}
		}

		KeypointXMLList keys1, keys2;
		public KeypointN[] GetOriginalKeys (int which) {
			if (which == 0)
				return (keys1.Arr);
			else
				return (keys2.Arr);
		}


		private MatchSet ()
		{
		}

		public MatchSet (string file1, int xdim1, int ydim1,
			string file2, int xdim2, int ydim2,
			KeypointXMLList kp1, KeypointXMLList kp2)
		{
			this.file1 = file1;
			this.file2 = file2;
			this.matches = new ArrayList ();

			xDim1 = xdim1;
			yDim1 = ydim1;
			xDim2 = xdim2;
			yDim2 = ydim2;

			keys1 = kp1;
			keys2 = kp2;
		}
	}

	// Find and return a list of MatchSet objects.
	//
	// This is the heart of the matching process.
	//
	// minimumMatches: minimum number of matches required in final results.
	// bestMatches: number of best matches to keep, or zero to keep all.
	// useRANSAC: whether ransac filtering should be used (true recommended
	//     for 2d rigid transformed images, such as panoramas).
	public ArrayList LocateMatchSets (int minimumMatches, int bestMatches,
		bool useRANSAC, bool useAreaFiltration)
	{
		BuildGlobalKD ();
		BuildGlobalMatchList ();

		PartitionMatches ();

		filteredMatchSets = new ArrayList ();

		// Walk all image combinations.
		for (int n0 = 0 ; n0 < imageCount ; ++n0) {
			for (int n1 = n0 + 1 ; n1 < imageCount ; ++n1) {
				MatchSet ms = matchSets[n0, n1];
				if (ms == null || ms.Matches == null)
					continue;

				if (useRANSAC) {
					ArrayList ransacMatches = null;
					int maxX = ms.xDim1 >= ms.xDim2 ? ms.xDim1 : ms.xDim2;
					int maxY = ms.yDim1 >= ms.yDim2 ? ms.yDim1 : ms.yDim2;

					// TODO: 16.0 -> configurable
					ImageMatchModel bestRansac = MatchDriver.FilterMatchSet
						(ms.Matches, 16.0, maxX, maxY);

					ms.BestMatchFit = bestRansac;
					if (bestRansac != null)
						ransacMatches = bestRansac.FittingGround;

					if (ransacMatches == null) {
						Console.WriteLine ("RANSAC says: no good matches from " +
							"{0} original matches", ms.Matches.Count);

						continue;
					} else {
						Console.WriteLine ("RANSAC purged: {0} to {1}",
							ms.Matches.Count, ransacMatches.Count);
					}

					// Overwrite matches with RANSAC checked ones.
					ms.Matches = ransacMatches;
				}

				// Number of RANSAC-ok matches before count-filtering.
				int beforeBestFilterCount = ms.Matches.Count;

				// TODO: replace with area filtering
				Console.WriteLine ("Filtering... ({0}, {1})", ms.File1, ms.File2);

				// First filtration: Join matches
				int beforeJoinFiltering = ms.Matches.Count;
				ms.Matches = MatchKeys.FilterJoins (ms.Matches);
				Console.WriteLine ("   A. Join Filtration: {0} to {1}",
					beforeJoinFiltering, ms.Matches.Count);

				// Second: Area filtration
				if (useAreaFiltration && bestMatches > 0) {
					int beforeAreaFiltering = ms.Matches.Count;
					double pixelCount = ms.xDim1 * ms.yDim1;
					double areaPixels;
					ms.Matches = FilterMatchesByArea (ms.Matches, bestMatches,
						out areaPixels);

					Console.WriteLine ("   B. Area Filtration: {0} to {1}, covering {2:N2} % of image \"{3}\"",
						beforeAreaFiltering, ms.Matches.Count,
						(areaPixels * 100.0) / pixelCount, ms.File1);
				} else if (bestMatches > 0) {
					int beforeScoreFiltering = ms.Matches.Count;
					ms.Matches = FilterMatches (ms.Matches, bestMatches);

					Console.WriteLine ("   B. Score Filtration: {0} to {1}",
						beforeScoreFiltering, ms.Matches.Count);
				}

				Console.WriteLine ("Filtered partition [{0},{1}] from {2} matches down to {3}",
					n0, n1, beforeBestFilterCount, ms.Matches.Count);

				if (ms.Matches.Count >= minimumMatches)
					filteredMatchSets.Add (ms);
			}
		}

		return (filteredMatchSets);
	}

	private ArrayList FilterMatchesByArea (ArrayList matches, int bestMatches,
		out double areaPixels)
	{
		areaPixels = 0.0;

		// Trivial case: no more matches available.
		if (matches.Count < bestMatches)
			return (matches);

		ArrayList points = new ArrayList ();

		// Create a point list.
		foreach (Match m in matches) {
			AreaFilter.Point p = new AreaFilter.Point ();

			p.x = m.Kp1.X;
			p.y = m.Kp1.Y;
			p.user = m;

			points.Add (p);
		}

		AreaFilter areaF = new AreaFilter ();
		ArrayList convexHull = areaF.CreateConvexHull (points);
		//Console.WriteLine ("convex hull holds {0} points", convexHull.Count);

		// Case one: we have more points in the convex hull than we want
		// Solution: Iteratively remove the point that reduces the hull area
		//   the least, until we have only bestMatches left.
		//Console.WriteLine ("Polygon area before: {0}", areaF.PolygonArea (convexHull));
		while (convexHull.Count > bestMatches) {
			double maxArea = -1.0;
			int removeIndex = -1;

			// Remove exactly one element from the convex hull, that element
			// which still maximizes the polygon area (ie image coverage).
			for (int n = 0 ; n < convexHull.Count ; ++n) {
				ArrayList convexHullMinusOne = (ArrayList) convexHull.Clone ();
				convexHullMinusOne.RemoveAt (n);

				double remArea = areaF.PolygonArea (convexHullMinusOne);
				if (removeIndex < 0 || remArea > maxArea) {
					removeIndex = n;
					maxArea = remArea;
				}
			}

			//Console.WriteLine ("DEBUG Removing {0}, area still {1}", removeIndex, maxArea);
			convexHull.RemoveAt (removeIndex);
		}

		//Console.WriteLine ("Polygon area after: {0}", areaF.PolygonArea (convexHull));
		areaPixels = areaF.PolygonArea (convexHull);

		// Case two: we have less points in the convex hull than we want.
		// Solution: Add points based on their average distance to all convex
		//   hull points.
		//
		// We know there are enough matches available as
		// matches.Count >= bestMatches.
		while (convexHull.Count < bestMatches)
		{
			double maxDistance = -1.0;
			Match addMatch = null;

			foreach (Match m in matches) {
				bool matchFound = false;
				foreach (AreaFilter.Point p in convexHull) {
					if (p.user != m)
						continue;

					matchFound = true;
					break;
				}

				// Match already in pointlist.
				if (matchFound)
					continue;

				// Now that we have a unique point, calculate its average
				// distance to all points in the convex hull.
				double dist = 0.0;
				int distCount = 0;
				foreach (AreaFilter.Point p in convexHull) {
					dist += Math.Sqrt (Math.Pow (p.x - m.Kp1.X, 2.0) +
						Math.Pow (p.y - m.Kp1.Y, 2.0));
					distCount += 1;
				}

				dist /= (double) distCount;
				//Console.WriteLine ("  max: {0}, this: {1}", maxDistance, dist);
				if (addMatch == null || dist > maxDistance) {
					addMatch = m;
					maxDistance = dist;
				}
			}

			// Add point, although its not in the hull. It just happens to be
			// farthest away from all points in the hull, so the image
			// coverage is improved most.
			AreaFilter.Point pNew = new AreaFilter.Point ();
			pNew.x = addMatch.Kp1.X;
			pNew.y = addMatch.Kp1.Y;
			pNew.user = addMatch;
			convexHull.Add (pNew);
		}

		ArrayList filteredMatches = new ArrayList ();
		foreach (AreaFilter.Point p in convexHull)
			filteredMatches.Add ((Match) p.user);

		return (filteredMatches);
	}

	private ArrayList FilterMatches (ArrayList matches, int bestMatches)
	{
		matches = MatchKeys.FilterJoins (matches);
		MatchKeys.FilterNBest (matches, bestMatches);

		/*
		Match.MatchWeighter mw = new Match.MatchWeighter ();

		foreach (Match m in matches) {
			Console.WriteLine ("    ({0},{1}) ({2},{3}) {4}, 2nd: {5}, weight {6}",
				(int)(m.Kp1.X + 0.5), (int)(m.Kp1.Y + 0.5),
				(int)(m.Kp2.X + 0.5), (int)(m.Kp2.Y + 0.5),
				m.Dist1, m.Dist2, mw.OverallFitness (m));
		}*/

		return (matches);
	}

	private void BuildGlobalKD ()
	{
		globalKeys = new ArrayList ();
		foreach (KeypointXMLList list in keysets)
			foreach (KeypointN kp in list.Arr)
				globalKeys.Add (kp);

		globalKeyKD = KDTree.CreateKDTree (globalKeys);
		Console.WriteLine ("Created global k-d tree containing {0} keypoints",
			globalKeys.Count);
	}

	// Partition the matches into image pair groups
	private void PartitionMatches ()
	{
		matchSets = new MatchSet[imageCount, imageCount];
		int createCount = 0;
		int maxL = 0;

		// Create all possible partition combinations, while pruning reverse
		// matches
		foreach (Match m in globalMatches) {
			int l0 = FindOrigin (m.Kp1);
			int l1 = FindOrigin (m.Kp2);

			if (l0 > maxL)
				maxL = l0;
			if (l1 > maxL)
				maxL = l1;
			bool reverseAlreadyIn = false;

			// FIXME: remove/is this correct?
			// FIXME: rewrite this whole crappy function
			if (l0 >= l1)
				continue;

			if (matchSets[l1, l0] != null) {
				MatchSet rev = matchSets[l1, l0];
				if (rev != null) {
					foreach (Match mr in rev.Matches) {
						if (mr.Kp1 == m.Kp2 && mr.Kp2 == m.Kp1) {
							reverseAlreadyIn = true;

							break;
						}
					}
				}
			}
			if (reverseAlreadyIn)
				continue;

			if (matchSets[l0, l1] == null) {
				createCount += 1;
				matchSets[l0, l1] = new MatchSet (keysets[l0].ImageFile,
					keysets[l0].XDim, keysets[l0].YDim,
					keysets[l1].ImageFile, keysets[l1].XDim, keysets[l1].YDim,
					keysets[l0], keysets[l1]);
			}

			matchSets[l0, l1].Matches.Add (m);
		}

		Console.WriteLine ("Created {0} match partitions, max l = {1}",
			createCount, maxL);
		/*
		for (int l0 = 0 ; l0 <= maxL ; ++l0) {
			for (int l1 = 0 ; l1 <= maxL ; ++l1) {
				Console.Write ("({0},{1}: {2}), ", l0, l1,
					matchSets[l0, l1] == null ? "empty" :
					String.Format ("{0}", matchSets[l0, l1].Matches.Count));
			}
		}
		*/
		Console.WriteLine ("");
	}

	private int FindOrigin (KeypointN kp)
	{
		for (int ksn = 0 ; ksn < keysets.Length ; ++ksn) {
			KeypointXMLList list = keysets[ksn];

			int lIdx = Array.IndexOf (list.Arr, kp);
			if (lIdx >= 0)
				return (ksn);
		}

		throw (new Exception ("BUG: keypoint origin unknown"));
	}

	public delegate void MatchKeypointEventHandler (int index, int total);
	public event MatchKeypointEventHandler MatchKeypoint;

	private void BuildGlobalMatchList ()
	{
		globalMatches = new ArrayList ();

		int count = 0;
		double searchDepth = Math.Max (130.0,
			(Math.Log (globalKeys.Count) / Math.Log (1000.0)) * 130.0);
		int searchDepthI = (int) searchDepth;

		Console.WriteLine ("Using a BBF cut search depth of {0}", searchDepthI);

		foreach (KeypointN kp in globalKeys) {
			// Raise event in case an event handler has been registered.
			if (MatchKeypoint != null)
				MatchKeypoint (count, globalKeys.Count);

			if ((count % 25) == 0)
				Console.Write ("\r% {0:N2}, {1}/{2}        ",
					(100 * ((double) count)) / ((double) globalKeys.Count),
					count, globalKeys.Count);
			count++;

			// There should be one exact hit (the keypoint itself, which we
			// ignore) and two real hits, so lets search for the three best
			// hits. But it could be the exact match is not found for, as we
			// use probabilistic bbf matching.
			ArrayList kpNNList =
				globalKeyKD.NearestNeighbourListBBF (kp, 3, searchDepthI);

			if (kpNNList.Count < 3)
				throw (new Exception ("BUG: less than three neighbours!"));

			KDTree.BestEntry be1 = (KDTree.BestEntry) kpNNList[0];
			KDTree.BestEntry be2 = (KDTree.BestEntry) kpNNList[1];

			// If be1 is the same (exact hit), shift one
			if (be1.Neighbour == kp) {
				be1 = be2;
				be2 = (KDTree.BestEntry) kpNNList[2];
			}
			if (be1.Neighbour == kp || be2.Neighbour == kp ||
				be1.Neighbour == be2.Neighbour)
				continue;
				//throw (new Exception ("BUG: wrong keypoints caught"));

			if ((be1.Distance / be2.Distance) > 0.6)
				continue;

			globalMatches.Add (new Match (kp, (KeypointN) be1.Neighbour,
				be1.Distance, be2.Distance));
		}
		Console.Write ("\r% {0:N2}, {1}/{2}        ",
			(100 * ((double) count)) / ((double) globalKeys.Count),
			count, globalKeys.Count);

		Console.WriteLine ("\nGlobal match search yielded {0} matches",
			globalMatches.Count);
	}

	// matches: ArrayList of MatchSet
	// returns: ArrayList of ArrayList of string (filenames)
	public ArrayList ComponentCheck (ArrayList matches)
	{
		ArrayList components = new ArrayList ();

		foreach (MatchSet ms in matches) {
			Component c1 = FindComponent (components, ms.File1);
			Component c2 = FindComponent (components, ms.File2);

			// case: new component
			if (c1 == null && c2 == null) {
				Component comp = new Component ();

				comp.Add (ms.File1);
				comp.Add (ms.File2);

				components.Add (comp);
			// c2 is new in c1-component
			} else if (c1 != null && c2 == null) {
				c1.Add (ms.File2);
			// c1 is new in c2-component
			} else if (c1 == null && c2 != null) {
				c2.Add (ms.File1);
			// same component already, do nothing
			} else if (c1 == c2) {
			// different component: join components
			} else if (c1 != c2) {
				c1.Add (c2);
				components.Remove (c2);
			}
		}

		// Now locate all components with no matches at all and add them to
		// the final result.
		foreach (KeypointXMLList klist in keysets) {
			string filename = klist.ImageFile;

			if (FindComponent (components, filename) != null)
				continue;

			Component isolatedFile = new Component ();
			isolatedFile.Add (filename);
			components.Add (isolatedFile);
		}

		return (components);
	}

	private Component FindComponent (ArrayList components, string filename)
	{
		foreach (Component comp in components) {
			if (comp.IsIncluded (filename))
				return (comp);
		}

		return (null);
	}

	public class Component
	{
		ArrayList files = new ArrayList ();

		public void Add (Component comp) {
			foreach (string filename in comp.files)
				Add (filename);
		}

		public bool IsIncluded (string filename)
		{
			return (files.Contains (filename));
		}

		public void Add (string filename)
		{
			if (IsIncluded (filename))
				return;

			files.Add (filename);
		}

		public override string ToString ()
		{
			StringBuilder sb = new StringBuilder ();

			bool first = true;
			int cCount = 0;
			foreach (string filename in files) {
				if (first) {
					first = false;
				} else {
					sb.Append (", ");
					cCount += 2;
				}

				sb.AppendFormat ("{0}", filename);
				cCount += filename.Length;

				if (cCount > 65) {
					sb.Append ("\n  ");
					cCount = 2;
					first = true;
				}
			}

			return (sb.ToString ());
		}
	}

	public BondBall BuildBondBall (ArrayList ransacFiltered, int bottomDefault)
	{
		BondBall bb = null;
		bool first = true;
		string fileNow, fileNext;

		for (int fileN = 0 ; fileN < (keysets.Length - 1) ; ++fileN) {
			fileNow = keysets[fileN].ImageFile;
			fileNext = keysets[fileN + 1].ImageFile;

			Console.WriteLine ("Searching for matches between {0}-{1}",
				fileNow, fileNext);
			// Process only the MatchSet that is build from this exact two
			// image files.
			MatchSet msNext = null;
			foreach (MatchSet ms in ransacFiltered) {
				if (String.Compare (ms.File1, fileNow) == 0 &&
					String.Compare (ms.File2, fileNext) == 0)
				{
					msNext = ms;
					Console.WriteLine ("  found!");
					break;
				}
			}

			// In case no matchset can be found this means we reached the end
			// of the panorama (it could still be a 360 degree one).
			if (msNext == null) {
				Console.WriteLine ("  NOT found!");
				break;
			}

			if (first) {
				Console.WriteLine ("Building bondball");
				if (bottomDefault == -1)
					bb = new BondBall ();
				else
					bb = new BondBall (bottomDefault);

				if (bb.InitiateBond (msNext) == false) {
					Console.WriteLine ("  FAILED");
					break;
				} else {
					Console.WriteLine ("  SUCCESS: {0}", bb);
				}
				first = false;

				continue;
			}

			// Try to add one more image to the row.
			if (bb.AddRowImage (msNext) == true) {
				Console.WriteLine ("Terminating first row creation.");
				break;
			}
		}

		// Case: no bondball has been build, because first pair does not
		// exist.
		if (bb == null)
			return (null);

		ArrayList rowFileNames = new ArrayList ();
		string last = null;
		foreach (MatchSet ms in bb.Sets) {
			rowFileNames.Add (ms.File1);
			last = ms.File2;
		}
		rowFileNames.Add (last);

		Console.WriteLine ("First row is:");
		foreach (string rowFileName in rowFileNames)
			Console.WriteLine ("  {0}", rowFileName);

		bb.FirstRow = rowFileNames;

		// Check if we have a 360 degree panorama, but only if we have more
		// than two images in the first row. This rules out very wide angle
		// lenses (> 180 degrees), which seems ok to me. Heck, is it even
		// possible?
		MatchSet msJoining = null;
		if (bb.Sets.Count > 2) {
			foreach (MatchSet ms in ransacFiltered) {
				if ((String.Compare (ms.File1, bb.Last.File2) == 0 &&
					String.Compare (ms.File2, bb.First.File1) == 0) ||
					(String.Compare (ms.File2, bb.Last.File2) == 0 &&
						String.Compare (ms.File1, bb.First.File1) == 0))
				{
					msJoining = ms;
					break;
				}
			}
		}

		bool is360 = false;
		if (msJoining != null) {
			Console.WriteLine ("Found 360 degree panorama, merging between \"{0}\" and \"{1}\" :-)",
				msJoining.File1, msJoining.File2);

			is360 = true;
		} else {
			Console.WriteLine ("Found no 360 degree boundary, assuming a < 360 degree panorama.");
			Console.WriteLine ("In case this is an error and it is a 360 degree boundary, please");
			Console.WriteLine ("consult the manpage documentation for information how to improve");
			Console.WriteLine ("the detection results. Thank you :-)");

			is360 = false;
		}

		// Align first row.
		bb.StretchImages (is360);

		// Now roughly add all remaining images.
		bool alignGap = true;
		int alignCount = 0;

		Console.WriteLine ("Estimating remaining images' positions");
		while (alignGap == true && alignCount < ransacFiltered.Count) {
			alignGap = false;

			foreach (MatchSet ms in ransacFiltered) {
				// Already aligned.
				if (bb.Positions.Contains (ms.File1) && bb.Positions.Contains (ms.File2))
					continue;

				// Unable to align (yet)
				if (bb.Positions.Contains (ms.File1) == false &&
					bb.Positions.Contains (ms.File2) == false)
				{
					alignGap = true;
					continue;
				}

				BondBall.Position pPos = null;
				string pPosFile = null;

				// Alignable cases: one is part of the aligned set
				if (bb.Positions.Contains (ms.File1) == true &&
					bb.Positions.Contains (ms.File2) == false)
				{
					pPos = bb.EstimateImage (ms);
					bb.Positions.Add (ms.File2, pPos);
					pPosFile = ms.File2;
				} else if (bb.Positions.Contains (ms.File1) == false &&
					bb.Positions.Contains (ms.File2) == true)
				{
					/*
					Console.WriteLine ("\n### BUG DUMP");
					Console.WriteLine ("in positions:");
					foreach (string fname in bb.Positions.Keys) {
						Console.WriteLine ("  \"{0}\": {1}",
							fname, (BondBall.Position) bb.Positions[fname]);
					}

					Console.WriteLine ("candidate now:");
					Console.WriteLine ("  \"{0}\" and \"{1}\"",
						ms.File1, ms.File2);
					Console.WriteLine ("### DUMP END\n");
					*/

					pPos = bb.EstimateImage (ms);
					bb.Positions.Add (ms.File1, pPos);
					pPosFile = ms.File1;
				}
				Console.WriteLine ("  estimated: \"{0}\": {1}",
					pPosFile, pPos);
			}

			alignCount += 1;
		}

		if (alignGap) {
			Console.WriteLine ("");
			Console.WriteLine ("Warning: Unaligned images remain. This is most likely due to loose");
			Console.WriteLine ("         components, see the manual page documentation for details.");
			Console.WriteLine ("");
		} else
			Console.WriteLine ("Done.\n");

		return (bb);
	}
}