/*
* Created by: Miguel Angel Medina P�rez (miguel.medina.perez@gmail.com)
* Created:
* Comments by: Miguel Angel Medina P�rez (miguel.medina.perez@gmail.com)
*/
using System;
using System.Collections.Generic;
using System.Drawing;
using System.Drawing.Drawing2D;
using PatternRecognition.FingerprintRecognition.Core;
using PatternRecognition.FingerprintRecognition.FeatureRepresentation;
namespace PatternRecognition.FingerprintRecognition.Matchers
{
/// <summary>
/// An implementation of the algorithm proposed by Medina-P�rez et al. in 2009.
/// </summary>
/// <remarks>
/// <para>
/// This is an implementation of the algorithm proposed by Medina-P�rez et al. in [1].
/// </para>
/// <para>
/// References:
/// </para>
/// <para>
/// <list type="number">
/// <item>
/// M. A. Medina-P�rez, A. Guti�rrez-Rodr�guez, and M. Garc�a-Borroto, "Improving Fingerprint Matching Using an Orientation-Based Minutia Descriptor," in 14th Iberoamerican Congress on Pattern Recognition, CIARP 2009, Guadalajara, M�xico, 2009, pp. 121-128.
/// </item>
/// </list>
/// </para>
/// </remarks>
public class MTK : Matcher<Tico2003Features>, IMinutiaMatcher
{
#region public
/// <summary>
/// Minutia count threshold for the global minutia matching step.
/// </summary>
/// <remarks>
/// This threshold limits the minimum count of global matching minutiae. For more information refer to the original paper.
/// </remarks>
public int MtiaCountThr
{
get { return mtiaCountThr; }
set { mtiaCountThr = value; }
}
/// <summary>
/// Distance threshold for the global minutia matching step.
/// </summary>
/// <remarks>
/// This threshold is used to compare minutia distances in the global minutia matching step. For more information refer to the original paper.
/// </remarks>
public int GlobalDistThr
{
get { return gDistThr; }
set { gDistThr = value; }
}
/// <summary>
/// Angle threshold for the global minutia matching step.
/// </summary>
/// <remarks>
/// This threshold is used to compare angles in the global minutia matching step. For more information refer to the original paper.
/// </remarks>
public double GlobalAngleThr
{
get { return gAngThr * 180 / Math.PI; }
set { gAngThr = value * Math.PI / 180; }
}
/// <summary>
/// Matches the specified fingerprint features.
/// </summary>
/// <param name="query">
/// The query fingerprint features.
/// </param>
/// <param name="template">
/// The template fingerprint features.
/// </param>
/// <returns>
/// The fingerprint similarity value.
/// </returns>
public override double Match(Tico2003Features query, Tico2003Features template)
{
List<MinutiaPair> matchingMtiae;
return Match(query, template, out matchingMtiae);
}
/// <summary>
/// Matches the specified fingerprint features and outputs the matching minutiae.
/// </summary>
/// <param name="query">
/// The query fingerprint features.
/// </param>
/// <param name="template">
/// The template fingerprint features.
/// </param>
/// <param name="matchingMtiae">
/// The matching minutiae.
/// </param>
/// <returns>
/// The fingerprint similarity value.
/// </returns>
public double Match(object query, object template, out List<MinutiaPair> matchingMtiae)
{
Tico2003Features qTico2003Features = query as Tico2003Features;
Tico2003Features tTico2003Features = template as Tico2003Features;
try
{
matchingMtiae = null;
var localMatchingMtiae = GetLocalMatchingMtiae(qTico2003Features, tTico2003Features);
if (localMatchingMtiae.Count == 0)
return 0;
int max = 0;
int notMatchingCount = int.MaxValue;
for (int i = 0; i < localMatchingMtiae.Count; i++)
{
List<MinutiaPair> currMatchingMtiae =
GetGlobalMatchingMtiae(localMatchingMtiae, localMatchingMtiae[i], ref notMatchingCount);
if (currMatchingMtiae != null && currMatchingMtiae.Count > max)
{
max = currMatchingMtiae.Count;
matchingMtiae = currMatchingMtiae;
}
}
return Eval(qTico2003Features, tTico2003Features, matchingMtiae);
}
catch (Exception e)
{
if (query.GetType() != typeof(Tico2003Features) || template.GetType() != typeof(Tico2003Features))
{
string msg = "Unable to match fingerprints: Invalid features type!";
throw new ArgumentOutOfRangeException(msg, e);
}
throw e;
}
}
#endregion
#region private
private List<MinutiaPair> GetLocalMatchingMtiae(Tico2003Features query, Tico2003Features template)
{
var qIndex = new Dictionary<Minutia, int>(query.Minutiae.Count);
var tIndex = new Dictionary<Minutia, int>(template.Minutiae.Count);
var mtiaPairs = new List<MinutiaPair>(query.Minutiae.Count * template.Minutiae.Count);
var simArr = new double[query.Minutiae.Count + 1, template.Minutiae.Count + 1];
simArr[query.Minutiae.Count, template.Minutiae.Count] = 0;
for (int i = 0; i < query.Minutiae.Count; i++)
{
var qMtia = query.Minutiae[i];
qIndex.Add(qMtia, i);
for (int j = 0; j < template.Minutiae.Count; j++)
{
var tMtia = template.Minutiae[j];
var currSim = Angle.AngleDif180(qMtia.Minutia.Angle, tMtia.Minutia.Angle) >= Math.PI / 4 ? 0 : qMtia.Compare(tMtia);
simArr[i, j] = currSim;
simArr[i, template.Minutiae.Count] += currSim;
simArr[query.Minutiae.Count, j] += currSim;
}
}
for (int j = 0; j < template.Minutiae.Count; j++)
tIndex.Add(template.Minutiae[j], j);
for (int i = 0; i < query.Minutiae.Count; i++)
{
var qMtia = query.Minutiae[i];
for (int j = 0; j < template.Minutiae.Count; j++)
{
var tMtia = template.Minutiae[j];
double currPos = (simArr[i, j] * simArr[i, j]) /
(simArr[i, template.Minutiae.Count] + simArr[query.Minutiae.Count, j] -
3 * simArr[i, j]);
if (currPos != 0)
{
var currMtiaPair = new MinutiaPair
{
QueryMtia = qMtia,
TemplateMtia = tMtia,
MatchingValue = currPos
};
mtiaPairs.Add(currMtiaPair);
}
}
}
var qMatches = new Dictionary<Minutia, Minutia>(60);
var tMatches = new Dictionary<Minutia, Minutia>(60);
mtiaPairs.Sort(new MtiaPairComparer());
var matchingPairs = new List<MinutiaPair>(60);
for (int i = 0; i < mtiaPairs.Count; i++)
{
var pair = mtiaPairs[i];
if (!qMatches.ContainsKey(pair.QueryMtia) || !tMatches.ContainsKey(pair.TemplateMtia))
{
matchingPairs.Add(pair);
if (!qMatches.ContainsKey(pair.QueryMtia))
qMatches.Add(pair.QueryMtia, pair.TemplateMtia);
if (!tMatches.ContainsKey(pair.TemplateMtia))
tMatches.Add(pair.TemplateMtia, pair.QueryMtia);
pair.MatchingValue = simArr[qIndex[pair.QueryMtia], tIndex[pair.TemplateMtia]];
}
}
return matchingPairs;
}
private List<MinutiaPair> GetGlobalMatchingMtiae(List<MinutiaPair> localMatchingPairs, MinutiaPair refMtiaPair, ref int notMatchingCount)
{
List<MinutiaPair> globalMatchingMtiae = new List<MinutiaPair>(localMatchingPairs.Count);
var qMatches = new Dictionary<Minutia, Minutia>(localMatchingPairs.Count);
var tMatches = new Dictionary<Minutia, Minutia>(localMatchingPairs.Count);
qMatches.Add(refMtiaPair.QueryMtia, refMtiaPair.TemplateMtia);
tMatches.Add(refMtiaPair.TemplateMtia, refMtiaPair.QueryMtia);
MtiaMapper mm = new MtiaMapper(refMtiaPair.QueryMtia, refMtiaPair.TemplateMtia);
int currNotMatchingMtiaCount = 0;
int i;
for (i = 0; i < localMatchingPairs.Count; i++)
{
MinutiaPair mtiaPair = localMatchingPairs[i];
if (!qMatches.ContainsKey(mtiaPair.QueryMtia) && !tMatches.ContainsKey(mtiaPair.TemplateMtia))
{
Minutia query = mm.Map(mtiaPair.QueryMtia);
Minutia template = mtiaPair.TemplateMtia;
if (dist.Compare(query, template) <= gDistThr && MatchDirections(query, template))
{
globalMatchingMtiae.Add(mtiaPair);
qMatches.Add(mtiaPair.QueryMtia, mtiaPair.TemplateMtia);
tMatches.Add(mtiaPair.TemplateMtia, mtiaPair.QueryMtia);
}
else
currNotMatchingMtiaCount++;
}
if (currNotMatchingMtiaCount >= notMatchingCount)
break;
if (globalMatchingMtiae.Count + (localMatchingPairs.Count - i - 1) < MtiaCountThr)
break;
}
if (i == localMatchingPairs.Count)
{
notMatchingCount = currNotMatchingMtiaCount;
globalMatchingMtiae.Add(refMtiaPair);
return globalMatchingMtiae;
}
return null;
}
private class MtiaMapper
{
public MtiaMapper(Minutia query, Minutia template)
{
dAngle = template.Angle - query.Angle;
this.template = template;
this.query = query;
}
public Minutia Map(Minutia m)
{
return new Minutia
{
Angle = m.Angle + dAngle,
X = Convert.ToInt16(Math.Round((m.X - query.X) * Math.Cos(dAngle) - (m.Y - query.Y) * Math.Sin(dAngle) + template.X)),
Y = Convert.ToInt16(Math.Round((m.X - query.X) * Math.Sin(dAngle) + (m.Y - query.Y) * Math.Cos(dAngle) + template.Y))
};
}
private readonly float dAngle;
private Minutia template;
private Minutia query;
}
private bool MatchDirections(Minutia query, Minutia template)
{
return Angle.AngleDif180(query.Angle, template.Angle) <= gAngThr;
}
private class MtiaPairComparer : IComparer<MinutiaPair>
{
public int Compare(MinutiaPair x, MinutiaPair y)
{
return (x == y) ? 0 : (x.MatchingValue < y.MatchingValue) ? 1 : -1;
}
}
private double Eval(Tico2003Features query, Tico2003Features template, List<MinutiaPair> matchingPair)
{
if (matchingPair == null)
return 0;
var qCenterMtia = matchingPair[matchingPair.Count - 1].QueryMtia;
var tCenterMtia = matchingPair[matchingPair.Count - 1].TemplateMtia;
// Computing query bounding region
var qPolygon = GetBounds(query);
qPolygon =
(new PolygonMapper(qCenterMtia, tCenterMtia)).Map(qPolygon);
var qBoundingRegion = new FingerprintRegion(qPolygon);
// Computing template bounding region
var tPolygon = GetBounds(template);
var tBoundingRegion = new FingerprintRegion(tPolygon);
// Mapping query minutiae
var mtiaMapper = new MtiaMapper(qCenterMtia, tCenterMtia);
var qMtiae = new List<Minutia>(query.Minutiae.Count);
for (int i = 0; i < query.Minutiae.Count; i++)
{
var mtia = query.Minutiae[i];
qMtiae.Add(mtiaMapper.Map(mtia));
}
int qCount = 0;
for (int i = 0; i < qMtiae.Count; i++)
{
var mtia = qMtiae[i];
if (tBoundingRegion.Contains(mtia))
qCount++;
}
int tCount = 0;
foreach (var mtia in template.Minutiae)
if (qBoundingRegion.Contains(mtia))
tCount++;
double sum = 0;
foreach (var mtiaPair in matchingPair)
sum += mtiaPair.MatchingValue;
return qCount >= MtiaCountThr && tCount >= MtiaCountThr ? 1.0 * sum * sum / (qCount * tCount) : 0;
}
private class FingerprintRegion
{
public FingerprintRegion(Point[] polygon)
{
byte[] types = new byte[polygon.Length];
int i;
for (i = 0; i < polygon.Length; i++)
types[i] = (byte)PathPointType.Line;
path = new GraphicsPath(polygon, types);
}
public bool Contains(Minutia m)
{
return path.IsVisible(m.X, m.Y);
}
private readonly GraphicsPath path;
}
private Point[] GetBounds(Tico2003Features features)
{
int minX = int.MaxValue;
int minY = int.MaxValue;
int maxX = int.MinValue;
int maxY = int.MinValue;
foreach (var mtiaDesc in features.Minutiae)
{
if (minX > mtiaDesc.Minutia.X)
minX = mtiaDesc.Minutia.X;
if (minY > mtiaDesc.Minutia.Y)
minY = mtiaDesc.Minutia.Y;
if (maxX < mtiaDesc.Minutia.X)
maxX = mtiaDesc.Minutia.X;
if (maxY < mtiaDesc.Minutia.Y)
maxY = mtiaDesc.Minutia.Y;
}
var resultingBound = new Point[5];
resultingBound[0] = new Point(minX - 1, maxY + 1);
resultingBound[1] = new Point(maxX + 1, maxY + 1);
resultingBound[2] = new Point(maxX + 1, minY - 1);
resultingBound[3] = new Point(minX - 1, minY - 1);
resultingBound[4] = new Point(minX - 1, maxY + 1);
return resultingBound;
}
private class PolygonMapper
{
public PolygonMapper(Minutia query, Minutia template)
{
dAngle = template.Angle - query.Angle;
this.template = template;
this.query = query;
}
public Point[] Map(Point[] polygon)
{
var newPolygon = new Point[polygon.Length];
for (int i = 0; i < polygon.Length; i++)
{
newPolygon[i].X =
Convert.ToInt16(
Math.Round((polygon[i].X - query.X) * Math.Cos(dAngle) -
(polygon[i].Y - query.Y) * Math.Sin(dAngle) + template.X));
newPolygon[i].Y =
Convert.ToInt16(
Math.Round((polygon[i].X - query.X) * Math.Sin(dAngle) +
(polygon[i].Y - query.Y) * Math.Cos(dAngle) + template.Y));
}
return newPolygon;
}
private float dAngle;
private Minutia template;
private Minutia query;
}
private int gDistThr = 12;
private double gAngThr = Math.PI / 6;
private readonly MtiaEuclideanDistance dist = new MtiaEuclideanDistance();
private int mtiaCountThr = 6;
#endregion
}
}
Submit an article or tip