+
+let findMaxima (img: Image<Gray, byte>) : IEnumerable<HashSet<Point>> =
+ use suppress = new Image<Gray, byte>(img.Size)
+ let w = img.Width
+ let h = img.Height
+
+ let imgData = img.Data
+ let suppressData = suppress.Data
+
+ let result = List<List<Point>>()
+
+ let flood (start: Point) : List<List<Point>> =
+ let sameLevelToCheck = Stack<Point>()
+ let betterLevelToCheck = Stack<Point>()
+ betterLevelToCheck.Push(start)
+
+ let result' = List<List<Point>>()
+
+ while betterLevelToCheck.Count > 0 do
+ let p = betterLevelToCheck.Pop()
+ if suppressData.[p.Y, p.X, 0] = 0uy
+ then
+ suppressData.[p.Y, p.X, 0] <- 1uy
+ sameLevelToCheck.Push(p)
+ let current = List<Point>()
+
+ let mutable betterExists = false
+
+ while sameLevelToCheck.Count > 0 do
+ let p' = sameLevelToCheck.Pop()
+ let currentLevel = imgData.[p'.Y, p'.X, 0]
+ current.Add(p') |> ignore
+ for i in -1 .. 1 do
+ for j in -1 .. 1 do
+ if i <> 0 || j <> 0
+ then
+ let ni = i + p'.Y
+ let nj = j + p'.X
+ if ni >= 0 && ni < h && nj >= 0 && nj < w
+ then
+ let level = imgData.[ni, nj, 0]
+ let notSuppressed = suppressData.[ni, nj, 0] = 0uy
+
+ if level = currentLevel && notSuppressed
+ then
+ suppressData.[ni, nj, 0] <- 1uy
+ sameLevelToCheck.Push(Point(nj, ni))
+ elif level > currentLevel
+ then
+ betterExists <- true
+ if notSuppressed
+ then
+ betterLevelToCheck.Push(Point(nj, ni))
+
+ if not betterExists
+ then
+ result'.Add(current)
+ result'
+
+ for i in 0 .. h - 1 do
+ for j in 0 .. w - 1 do
+ let maxima = flood (Point(j, i))
+ if maxima.Count > 0
+ then result.AddRange(maxima)
+
+ result.Select(fun l -> HashSet<Point>(l))
+
+
+type PriorityQueue () =
+ let q = List<HashSet<Point>>() // TODO: Check performance with an HasSet
+ let mutable highest = -1 // Value of the first elements of 'q'.
+
+ member this.Next () : byte * Point =
+ if this.IsEmpty
+ then
+ invalidOp "Queue is empty"
+ else
+ let l = q.[0]
+ let next = l.First()
+ l.Remove(next) |> ignore
+ let value = byte highest
+ if l.Count = 0
+ then
+ q.RemoveAt(0)
+ highest <- highest - 1
+ while q.Count > 0 && q.[0] = null do
+ q.RemoveAt(0)
+ highest <- highest - 1
+ value, next
+
+ member this.Max =
+ highest |> byte
+
+ (*member this.UnionWith (other: PriorityQueue) =
+ while not other.IsEmpty do
+ let p, v = other.Next
+ this.Add p v*)
+
+ member this.Add (value: byte) (p: Point) =
+ let vi = int value
+
+ if this.IsEmpty
+ then
+ highest <- int value
+ q.Insert(0, null)
+ elif vi > highest
+ then
+ for i in highest .. vi - 1 do
+ q.Insert(0, null)
+ highest <- vi
+ elif highest - vi >= q.Count
+ then
+ for i in 0 .. highest - vi - q.Count do
+ q.Add(null)
+
+ let pos = highest - vi
+ if q.[pos] = null
+ then
+ q.[pos] <- HashSet<Point>([p])
+ else
+ q.[pos].Add(p) |> ignore
+
+
+ member this.IsEmpty =
+ q.Count = 0
+
+ member this.Clear () =
+ while highest >= 0 do
+ q.[highest] <- null
+ highest <- highest - 1
+
+
+
+type MaximaState = Uncertain | Validated | TooBig
+type Maxima = {
+ elements : HashSet<Point>
+ mutable intensity: byte option
+ mutable state: MaximaState }
+
+
+let areaOpen (img: Image<Gray, byte>) (area: int) =
+ let w = img.Width
+ let h = img.Height
+
+ let maxima = findMaxima img |> Seq.map (fun m -> { elements = m; intensity = None; state = Uncertain }) |> List.ofSeq
+ let toValidated = Stack<Maxima>(maxima)
+
+ while toValidated.Count > 0 do
+ let m = toValidated.Pop()
+ if m.elements.Count <= area
+ then
+ let queue =
+ let q = PriorityQueue()
+ let firstElements = HashSet<Point>()
+ for p in m.elements do
+ for i in -1 .. 1 do
+ for j in -1 .. 1 do
+ if i <> 0 || j <> 0
+ then
+ let ni = i + p.Y
+ let nj = j + p.X
+ let p' = Point(nj, ni)
+ if ni >= 0 && ni < h && nj >= 0 && nj < w && not (m.elements.Contains(p')) && not (firstElements.Contains(p'))
+ then
+ firstElements.Add(p') |> ignore
+ q.Add (img.Data.[ni, nj, 0]) p'
+ q
+
+ let mutable intensity = queue.Max
+ let nextElements = HashSet<Point>()
+
+ let mutable stop = false
+ while not stop do
+ let intensity', p = queue.Next ()
+
+ if intensity' = intensity // The intensity doesn't change.
+ then
+ if m.elements.Count + nextElements.Count + 1 > area
+ then
+ m.state <- Validated
+ m.intensity <- Some intensity
+ stop <- true
+ else
+ nextElements.Add(p) |> ignore
+ elif intensity' < intensity
+ then
+ m.elements.UnionWith(nextElements)
+ if m.elements.Count = area
+ then
+ m.state <- Validated
+ m.intensity <- Some (intensity')
+ stop <- true
+ else
+ intensity <- intensity'
+ nextElements.Clear()
+ nextElements.Add(p) |> ignore
+ else // i' > i
+ seq {
+ for m' in maxima do
+ if m' <> m && m'.elements.Contains(p) then
+ if m'.elements.Count + m.elements.Count <= area
+ then
+ m'.state <- Uncertain
+ m'.elements.UnionWith(m.elements)
+ if not <| toValidated.Contains m' // FIXME: Maybe use state instead of scanning the whole list.
+ then
+ toValidated.Push(m')
+ stop <- true
+ yield false
+ } |> Seq.forall id |> ignore
+
+ if not stop
+ then
+ m.state <- Validated
+ m.intensity <- Some (intensity)
+ stop <- true
+
+ if not stop
+ then
+ for i in -1 .. 1 do
+ for j in -1 .. 1 do
+ if i <> 0 || j <> 0
+ then
+ let ni = i + p.Y
+ let nj = j + p.X
+ let p' = Point(nj, ni)
+ if ni < 0 || ni >= h || nj < 0 || nj >= w
+ then
+ m.state <- Validated
+ m.intensity <- Some (intensity)
+ stop <- true
+ elif not (m.elements.Contains(p')) && not (nextElements.Contains(p'))
+ then
+ queue.Add (img.Data.[ni, nj, 0]) p'
+
+ if queue.IsEmpty
+ then
+ if m.elements.Count + nextElements.Count <= area
+ then
+ m.state <- Validated
+ m.intensity <- Some intensity'
+ m.elements.UnionWith(nextElements)
+ stop <- true
+
+ for m in maxima do
+ if m.state = Validated
+ then
+ match m.intensity with
+ | Some i ->
+ for p in m.elements do
+ img.Data.[p.Y, p.X, 0] <- i
+ | _ -> ()
+ ()
+
+
projects / master-thesis.git / commitdiff