Ransac

gistfile1.js

Y.Ransac = {
	findHomography: function(matches, iter) {
		var instance = this, bestScore = 0, bestHomography = null, i, mLen = matches.length;

		for (i = 0, iter = ((iter === undefined) ? 100 : iter); i < iter; i++) {
			var pairs = [], j, H;

			for (j = 0; j < 4; j++) {
				pairs.push(matches[YMath.randomInt(mLen)]);
			}

			// if (!instance.isColinear(pairs)) { // TODO: add colinear points checking optimization
				H = instance._findHomography.apply(instance, pairs);

				if (H) {
					var score = instance.score(H, matches);

					if (score > bestScore) {
						bestScore = score;
						bestHomography = H;
					}
				}
			// }
		}

		return bestHomography;
	},

	score: function(H, matches) {
		var instance = this, m, mLen = matches.length, inliners = 0;

		for (m = 0; m < mLen; m++) {
			var match = matches[m],
				dx,
				dy,
				Ph,
				Pe,
				P11,
				x11 = match[0][0],
				y11 = match[0][1],
				x12 = match[1][0],
				y12 = match[1][1];

			P11 = new YMath.Matrix([ [ x11 ], [ y11 ], [1] ]);

			Ph = H.multiply(P11).toArray();
			Pe = [ Ph[0]/Ph[2], Ph[1]/Ph[2] ];

			dx = Pe[0] - x12;
			dy = Pe[1] - y12;

			if (Math.sqrt(dx*dx + dy*dy) < 4) {
				inliners++;
			}
			// console.log(Pe, x12, y12, dx, dy, Math.sqrt(dx*dx + dy*dy), Math.sqrt(dx*dx + dy*dy) < 4);
		}

		return inliners;
	},

	_findHomography: function(pair1, pair2, pair3, pair4) {
		var instance = this, A, Ai, R, C

			// pair1
			p11 = pair1[0],
			x11 = p11[0], y11 = p11[1],
			p12 = pair1[1],
			x12 = p12[0], y12 = p12[1],
			// pair2
			p21 = pair2[0],
			x21 = p21[0], y21 = p21[1],
			p22 = pair2[1],
			x22 = p22[0], y22 = p22[1],
			// pair3
			p31 = pair3[0],
			x31 = p31[0], y31 = p31[1],
			p32 = pair3[1],
			x32 = p32[0], y32 = p32[1],
			// pair4
			p41 = pair4[0],
			x41 = p41[0], y41 = p41[1],
			p42 = pair4[1],
			x42 = p42[0], y42 = p42[1];

		R = new YMath.Matrix([
			[ x12 ], [ y12 ], [ x22 ], [ y22 ], [ x32 ], [ y32 ], [ x42 ], [ y42 ]
		]);

		A = new YMath.Matrix([
			// pair1
			[ x11, y11, 1, 0, 0, 0, -x11*x12, -y11*x12 ],
			[ 0, 0, 0, x11, y11, 1, -x11*y12, -y11*y12 ],
			// pair2
			[ x21, y21, 1, 0, 0, 0, -x21*x22, -y21*x22 ],
			[ 0, 0, 0, x21, y21, 1, -x21*y22, -y21*y22 ],
			// pair3
			[ x31, y31, 1, 0, 0, 0, -x31*x32, -y31*x32 ],
			[ 0, 0, 0, x31, y31, 1, -x31*y32, -y31*y32 ],
			// pair4
			[ x41, y41, 1, 0, 0, 0, -x41*x42, -y41*x42 ],
			[ 0, 0, 0, x41, y41, 1, -x41*y42, -y41*y42 ]
		]);

		Ai = A.getInverse();

		if (Ai) {
			C = Ai.multiply(R).toArray();

			return new YMath.Matrix([
				[ C[0][0], C[1][0], C[2][0] ],
				[ C[3][0], C[4][0], C[5][0] ],
				[ C[6][0], C[7][0], 1 ]
			]);
		}

		return null;
	}
};