7a4c51b46395fbbde788278750ab4917c01c5c28
1
module MatchingEllipses
5 open System.Collections
6 open System.Collections.Generic
12 // Do not take in account matching score below this when two ellipses are matched.
13 let matchingScoreThreshold1 = 0.6
15 // All ellipses with a score below this are removed.
16 let matchingScoreThreshold2 = 2.
18 type private EllipseScoreFlaggedKd (matchingScore
: float, e
: Ellipse) =
19 let mutable matchingScore = matchingScore
21 member this
.Ellipse = e
23 member this
.MatchingScore = matchingScore
25 member this
.AddMatchingScore(score
: float) =
26 matchingScore <- matchingScore + score
28 member val Processed = false with get
, set
29 member val Removed = false with get
, set
31 interface KdTree.I2DCoords with
32 member this
.X = this
.Ellipse.Cx
33 member this
.Y = this
.Ellipse.Cy
36 type MatchingEllipses (radiusMin
: float) =
37 let ellipses = List<EllipseScoreFlaggedKd>()
39 member this
.Add (e
: Ellipse) =
40 ellipses.Add(EllipseScoreFlaggedKd(0.0, e
))
42 member this
.Ellipses : Ellipse list =
43 List.ofSeq
ellipses |> List.map
(fun e
-> e
.Ellipse)
45 // Process all ellipses and return ellipses ordered from the best score to the worst.
46 member this
.PrunedEllipses : Ellipse list =
51 // 1) Create a kd-tree from the ellipses list.
52 let tree = KdTree.Tree.BuildTree (List.ofSeq
ellipses)
54 // 2) Compute the matching score of each ellipses.
55 let windowSize = radiusMin
58 let areaE = e
.Ellipse.Area
59 let window = { KdTree.minX
= e
.Ellipse.Cx - windowSize / 2.0
60 KdTree.maxX
= e
.Ellipse.Cx + windowSize / 2.0
61 KdTree.minY
= e
.Ellipse.Cy - windowSize / 2.0
62 KdTree.maxY
= e
.Ellipse.Cy + windowSize / 2.0 }
63 for other
in tree.Search window do
64 if not
other.Processed
66 let areaOther = other.Ellipse.Area
67 match EEOver.EEOverlapArea e
.Ellipse other.Ellipse with
68 | Some (commonArea
, _
, _
) ->
69 let matchingScore = 2.0 * commonArea
/ (areaE + areaOther)
70 if matchingScore >= matchingScoreThreshold1
72 other.AddMatchingScore(matchingScore)
73 e
.AddMatchingScore(matchingScore)
76 // 3) Sort ellipses by their score.
77 ellipses.Sort(fun e1 e2
-> e2
.MatchingScore.CompareTo(e1
.MatchingScore))
79 // 4) Remove ellipses wich have a low score.
80 let i = ellipses.BinarySearch(EllipseScoreFlaggedKd(matchingScoreThreshold2, Ellipse(0.0, 0.0, 0.0, 0.0, 0.0)),
81 { new IComparer<EllipseScoreFlaggedKd> with
82 member this
.Compare(e1
, e2
) = e2
.MatchingScore.CompareTo(e1
.MatchingScore) }) |> abs
83 let nbToRemove = ellipses.Count - i
86 for j
in i .. nbToRemove - 1 do
87 ellipses.[j
].Removed <- true
88 ellipses.RemoveRange(i, nbToRemove)
90 // 5) Remove ellipses whose center is into an ellipse with a better score
94 let window = { KdTree.minX
= e.Ellipse.Cx - e.Ellipse.A
95 KdTree.maxX
= e.Ellipse.Cx + e.Ellipse.A
96 KdTree.minY
= e.Ellipse.Cy - e.Ellipse.A
97 KdTree.maxY
= e.Ellipse.Cy + e.Ellipse.A }
98 for other in tree.Search window do
99 if not
other.Removed && other.MatchingScore < e.MatchingScore
101 if e.Ellipse.Scale(0.8).Contains other.Ellipse.Cx other.Ellipse.Cy
103 other.Removed <- true
104 ellipses.RemoveAll(fun e -> e.Removed) |> ignore
106 List.ofSeq
ellipses |> List.map
(fun e -> e.Ellipse)