open System
open System.Linq
+open System.Collections
open System.Collections.Generic
open Types
open Utils
-type EllipseScore = { mutable matchingScore: float; e: Ellipse }
+// Do not take in account matching score below this when two ellipses are matched.
+let matchingScoreThreshold1 = 0.6
-let matchingScoreThreshold1 = 0.5
-let matchingScoreThreshold2 = 2.0
+let scaleOverlapTest = 0.8
-let ellipseArea e = e.a * e.b * Math.PI
+type private EllipseScoreFlaggedKd (matchingScore: float, e: Ellipse) =
+ let mutable matchingScore = matchingScore
-type MatchingEllipses () =
- let ellipses = List<EllipseScore>()
-
- member this.Add (e: Ellipse) =
-
- // dprintfn "new ellipse: %A, nb: %A" e ellipses.Count
+ member this.Ellipse = e
- let areaE = ellipseArea e
+ member this.MatchingScore = matchingScore
- let mutable matchingScoreE = 0.0
+ member this.AddMatchingScore(score: float) =
+ matchingScore <- matchingScore + score
- for other in ellipses do
- let areaOther = ellipseArea other.e
- let commonArea = EEOver.EEOverlapArea e other.e
- let matchingScore = (2.0 * commonArea / (areaE + areaOther)) ** 2.0
- if matchingScore >= matchingScoreThreshold1
- then
- other.matchingScore <- other.matchingScore + matchingScore
- matchingScoreE <- matchingScoreE + matchingScore
- printfn "Score"
+ member val Processed = false with get, set
+ member val Removed = false with get, set
- ellipses.Add({ matchingScore = matchingScoreE; e = e })
+ interface KdTree.I2DCoords with
+ member this.X = this.Ellipse.Cx
+ member this.Y = this.Ellipse.Cy
- member this.Ellipses : Ellipse list =
- dprintfn "Number of ellipse: %A" ellipses.Count
- (*let sortedEllipses =
- List.filter (fun e -> e.matchingScore >= matchingScoreThreshold2) (List.ofSeq ellipses)
- |> List.sortWith (fun e1 e2 -> e2.matchingScore.CompareTo(e1.matchingScore))*)
+type MatchingEllipses (radiusMin: float) =
+ let ellipses = List<EllipseScoreFlaggedKd>()
+
+ // All ellipses with a score below this are removed.
+ let matchingScoreThreshold2 = 20. * radiusMin
+
+ member this.Add (e: Ellipse) =
+ ellipses.Add(EllipseScoreFlaggedKd(0.0, e))
+
+ member this.Ellipses : Ellipse list =
+ List.ofSeq ellipses |> List.map (fun e -> e.Ellipse)
+
+ // Process all ellipses and return ellipses ordered from the best score to the worst.
+ member this.PrunedEllipses : Ellipse list =
+ if ellipses.Count = 0
+ then
+ []
+ else
+ // 1) Create a kd-tree from the ellipses list.
+ let tree = KdTree.Tree.BuildTree (List.ofSeq ellipses)
+
+ // 2) Compute the matching score of each ellipses.
+ let windowSize = radiusMin
+ for e in ellipses do
+ e.Processed <- true
+ let areaE = e.Ellipse.Area
+ let window = { KdTree.minX = e.Ellipse.Cx - windowSize / 2.0
+ KdTree.maxX = e.Ellipse.Cx + windowSize / 2.0
+ KdTree.minY = e.Ellipse.Cy - windowSize / 2.0
+ KdTree.maxY = e.Ellipse.Cy + windowSize / 2.0 }
+ for other in tree.Search window do
+ if not other.Processed
+ then
+ let areaOther = other.Ellipse.Area
+ match EEOver.EEOverlapArea e.Ellipse other.Ellipse with
+ | Some (commonArea, _, _) ->
+ let matchingScore = 2.0 * commonArea / (areaE + areaOther)
+ if matchingScore >= matchingScoreThreshold1
+ then
+ other.AddMatchingScore(matchingScore * e.Ellipse.Perimeter)
+ e.AddMatchingScore(matchingScore * other.Ellipse.Perimeter)
+ | _ -> ()
+
+ // 3) Sort ellipses by their score.
+ ellipses.Sort(fun e1 e2 -> e2.MatchingScore.CompareTo(e1.MatchingScore))
+
+ // 4) Remove ellipses with a low score.
+ let i = ellipses.BinarySearch(EllipseScoreFlaggedKd(matchingScoreThreshold2, Ellipse(0.0, 0.0, 0.0, 0.0, 0.0)),
+ { new IComparer<EllipseScoreFlaggedKd> with
+ member this.Compare(e1, e2) = e2.MatchingScore.CompareTo(e1.MatchingScore) }) |> abs
+ let nbToRemove = ellipses.Count - i
+ if nbToRemove > 0
+ then
+ for j in i .. nbToRemove - 1 do
+ ellipses.[j].Removed <- true
+ ellipses.RemoveRange(i, nbToRemove)
+
+ // 5) Remove ellipses whose center is into an ellipse with a better score
+ for e in ellipses do
+ if not e.Removed
+ then
+ let window = { KdTree.minX = e.Ellipse.Cx - e.Ellipse.A
+ KdTree.maxX = e.Ellipse.Cx + e.Ellipse.A
+ KdTree.minY = e.Ellipse.Cy - e.Ellipse.A
+ KdTree.maxY = e.Ellipse.Cy + e.Ellipse.A }
+ for other in tree.Search window do
+ if not other.Removed && other.MatchingScore < e.MatchingScore
+ then
+ if e.Ellipse.Scale(scaleOverlapTest).Contains other.Ellipse.Cx other.Ellipse.Cy
+ then
+ other.Removed <- true
+ ellipses.RemoveAll(fun e -> e.Removed) |> ignore
+
+ List.ofSeq ellipses |> List.map (fun e -> e.Ellipse)
- List.filter (fun e -> e.matchingScore >= matchingScoreThreshold2) (List.ofSeq ellipses)
- |> List.sortWith (fun e1 e2 -> e2.matchingScore.CompareTo(e1.matchingScore))
- |> List.map (fun { e = e } -> e)
- // ellipses.Where(fun e -> e.matchingScore >= matchingScoreThreshold2)
- // ([], fun acc { matchingScore = score; e = e } -> if score >= matchingScoreThreshold2 then e :: acc else acc)
-
-
-