Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-image

Source of release 0.45.0

0.45.0 / src / live_wire.lucb

## The Magnetic Lasso's live wire, as intelligent scissors: the cheapest path
## between two samples of a small window, a step costing little along a
## strong edge and much across flat color. The window is a few hundred
## samples of one pyramid level round the last anchor and the pointer, so a
## trace costs the same on a postcard and on a 15000×24000 document.
from luce_std import math
import memory
from luce_raster.errors import invalid

## Edge strengths over a window of samples: 0 flat to 1 a full black-to-white
## step, rows of `width`. (`left`, `top`) is the window's corner in the grid.
pub struct Field:
    pub var left: i64
    pub var top: i64
    pub var width: i64
    pub var height: i64
    pub var strength: f32[]

    pub func contains(x: i64, y: i64) -> bool:
        return x >= self.left and y >= self.top and x < self.left + self.width and y < self.top + self.height

    pub func at(x: i64, y: i64) -> f32:
        return self.strength[(usize)((y - self.top) * self.width + (x - self.left))]

## Edge strengths from `luma` (0..1, perceptual), which holds the window with
## one more sample all round: rows of `width` + 2, `height` + 2 of them. The
## Sobel gradient's magnitude, a unit step reading 1.
pub func strengths(luma: const f32[], width: i64, height: i64, out: f32[]) -> !:
    let stride = width + 2
    if width <= 0 or height <= 0 or luma.length < (usize)(stride * (height + 2)) or out.length < (usize)(width * height):
        error(invalid, "the window's luma and strengths must cover it")
    for y in 0..<height:
        let above = (usize)(y * stride)
        let here = above + (usize)stride
        let below = here + (usize)stride
        for x in 0..<width:
            let at = (usize)x
            let gx = (luma[above + at + 2] + 2.0 * luma[here + at + 2] + luma[below + at + 2]) - (luma[above + at] + 2.0 * luma[here + at] + luma[below + at])
            let gy = (luma[below + at] + 2.0 * luma[below + at + 1] + luma[below + at + 2]) - (luma[above + at] + 2.0 * luma[above + at + 1] + luma[above + at + 2])
            let magnitude = math.sqrt((f64)(gx * gx + gy * gy)) / 4.0
            out[(usize)(y * width + x)] = (f32)math.min(1.0, magnitude)

## An edge's pull once `contrast` (0..1) is taken off: edges weaker than it
## count as flat, as the Magnetic Lasso's Contrast option.
func pull(strength: f32, contrast: f64) -> f64:
    if (f64)strength <= contrast:
        return 0.0
    return math.sqrt(((f64)strength - contrast) / math.max(1e-6, 1.0 - contrast))

## The strongest edge within `radius` samples of (`x`, `y`) at `contrast` or
## more, into (`out_x`, `out_y`); (`x`, `y`) itself when there is none: where
## the Magnetic Lasso's Width lets the wire find the edge.
pub func snap(field: const Field*, x: i64, y: i64, radius: i64, contrast: f64, out_x: i64*, out_y: i64*):
    *out_x = x
    *out_y = y
    var best = contrast
    var best_distance: i64 = 0
    for sy in y - radius..<y + radius + 1:
        for sx in x - radius..<x + radius + 1:
            let distance = (sx - x) * (sx - x) + (sy - y) * (sy - y)
            if distance > radius * radius or not field.contains(sx, sy):
                continue
            let strength = (f64)field.at(sx, sy)
            # The strongest wins; of equals, the nearest.
            if strength > best or (strength == best and strength > contrast and distance < best_distance):
                best = strength
                best_distance = distance
                *out_x = sx
                *out_y = sy

## The cheapest 8-connected path from (`from_x`, `from_y`) to (`to_x`,
## `to_y`), both inside the field, as x, y pairs from one end to the other,
## heap-allocated for the caller to free. Dijkstra from the start, stopping
## when the end is reached: an edge-following trace touches little more than
## the samples near the edge.
pub func trace(field: const Field*, from_x: i64, from_y: i64, to_x: i64, to_y: i64, contrast: f64) -> i64[]!:
    if not field.contains(from_x, from_y) or not field.contains(to_x, to_y):
        error(invalid, "the live wire's ends must lie inside its window")
    let count = (usize)(field.width * field.height)
    # The cost to enter each sample: little on a strong edge, 1 on flat color.
    let step = try new f64[count] --- in memory.heap
    defer free(step) in memory.heap
    for index in 0..<count:
        let pulled = pull(field.strength[index], contrast)
        step[index] = 0.05 + 0.95 * (1.0 - pulled)
    let cost = try new f64[count] --- in memory.heap
    defer free(cost) in memory.heap
    let back = try new u32[count] --- in memory.heap
    defer free(back) in memory.heap
    var queue = try Queue.create(count)
    defer queue.destroy()
    for index in 0..<count:
        cost[index] = 1e300
    let start = (usize)((from_y - field.top) * field.width + (from_x - field.left))
    let goal = (usize)((to_y - field.top) * field.width + (to_x - field.left))
    cost[start] = 0.0
    back[start] = (u32)start
    queue.lower(start, cost)
    let width = field.width
    let height = field.height
    while not queue.empty():
        let index = queue.pop(cost)
        if index == goal:
            break
        let x = (i64)index % width
        let y = (i64)index // width
        for dy in (i64)-1..<2:
            for dx in (i64)-1..<2:
                if dx == 0 and dy == 0:
                    continue
                let nx = x + dx
                let ny = y + dy
                if nx < 0 or ny < 0 or nx >= width or ny >= height:
                    continue
                let next = (usize)(ny * width + nx)
                if queue.done(next):
                    continue
                let length = 1.0 if dx == 0 or dy == 0 else 1.41421356
                let reached = cost[index] + step[next] * length
                if reached < cost[next]:
                    cost[next] = reached
                    back[next] = (u32)index
                    queue.lower(next, cost)
    # Walk back from the end, then turn the walk round.
    var steps: usize = 1
    var at = goal
    while at != start:
        at = (usize)back[at]
        steps += 1
    let path = try new i64[steps * 2] --- in memory.heap
    at = goal
    var slot = steps
    while true:
        slot -= 1
        path[slot * 2] = (i64)at % width + field.left
        path[slot * 2 + 1] = (i64)at // width + field.top
        if at == start:
            break
        at = (usize)back[at]
    return path

## A binary heap of samples by cost, each sample in it at most once, its place
## kept so a cheaper cost moves it up: Dijkstra's queue. Costs live in the
## caller's array, passed to each call.
struct Queue:
    var heap: u32[]
    var size: usize
    ## Where each sample sits in the heap; `absent` or `finished` otherwise.
    var place: i64[]

    static func create(count: usize) -> Queue!:
        let heap = try new u32[count] --- in memory.heap
        errdefer free(heap) in memory.heap
        let place = try new i64[count] --- in memory.heap
        for index in 0..<count:
            place[index] = absent
        return Queue(heap = heap, size = 0, place = place)

    func destroy():
        free(self.heap) in memory.heap
        free(self.place) in memory.heap

    func empty() -> bool:
        return self.size == 0

    ## Whether `index` has left the queue: its cost is final.
    func done(index: usize) -> bool:
        return self.place[index] == finished

    ## Put `index` in, or move it up after its cost fell.
    func lower(index: usize, cost: const f64[]):
        var at = self.size
        if self.place[index] >= 0:
            at = (usize)self.place[index]
        else:
            self.size += 1
        while at > 0:
            let parent = (at - 1) // 2
            let above = (usize)self.heap[parent]
            if cost[above] <= cost[index]:
                break
            self.heap[at] = (u32)above
            self.place[above] = (i64)at
            at = parent
        self.heap[at] = (u32)index
        self.place[index] = (i64)at

    ## Take the cheapest out, finished.
    func pop(cost: const f64[]) -> usize:
        let top = (usize)self.heap[0]
        self.place[top] = finished
        self.size -= 1
        if self.size == 0:
            return top
        let last = (usize)self.heap[self.size]
        var at: usize = 0
        while true:
            var child = at * 2 + 1
            if child >= self.size:
                break
            if child + 1 < self.size and cost[(usize)self.heap[child + 1]] < cost[(usize)self.heap[child]]:
                child += 1
            let below = (usize)self.heap[child]
            if cost[below] >= cost[last]:
                break
            self.heap[at] = (u32)below
            self.place[below] = (i64)at
            at = child
        self.heap[at] = (u32)last
        self.place[last] = (i64)at
        return top

let absent: i64 = -1
let finished: i64 = -2

# mark: Tests ===================================================================================

## A window of `width` by `height` flat at 0.2 with a vertical step to 0.9 at
## column `edge`: its strengths.
func stepped(width: i64, height: i64, edge: i64) -> Field!:
    let luma = try new f32[(usize)((width + 2) * (height + 2))] --- in memory.heap
    defer free(luma) in memory.heap
    for y in 0..<height + 2:
        for x in 0..<width + 2:
            luma[(usize)(y * (width + 2) + x)] = 0.9 if x - 1 >= edge else 0.2
    let strength = try new f32[(usize)(width * height)] --- in memory.heap
    try strengths(luma, width, height, strength)
    return Field(left = 100, top = 50, width = width, height = height, strength = strength)

test "a step's strength is its height, flat color none":
    var field = try stepped(40, 30, 20)
    defer free(field.strength) in memory.heap
    assert(field.at(119, 60) > 0.3 and field.at(120, 60) > 0.3 and field.at(110, 60) == 0.0 and field.at(130, 60) == 0.0)

test "snap finds the edge within the width, and stays put without one":
    var field = try stepped(40, 30, 20)
    defer free(field.strength) in memory.heap
    var x: i64 = 0
    var y: i64 = 0
    snap(&field, 115, 60, 6, 0.1, &x, &y)
    assert((x == 119 or x == 120) and y == 60)
    snap(&field, 105, 60, 6, 0.1, &x, &y)
    assert(x == 105 and y == 60)
    # Above the contrast, the edge is too weak to snap to.
    snap(&field, 115, 60, 6, 0.9, &x, &y)
    assert(x == 115)

test "the wire runs along an edge rather than straight across flat color":
    var field = try stepped(60, 60, 30)
    defer free(field.strength) in memory.heap
    # From the edge's top to its bottom, bowing no further than its sides.
    let path = try trace(&field, 130, 52, 130, 107, 0.1)
    defer free(path) in memory.heap
    assert(path[0] == 130 and path[1] == 52 and path[path.length - 2] == 130 and path[path.length - 1] == 107)
    var off: usize = 0
    var index: usize = 0
    while index < path.length:
        if path[index] < 129 or path[index] > 130:
            off += 1
        index += 2
    assert(off == 0)
    # Between points off the edge the wire detours to it: its middle lies on
    # the edge although the straight line is ten samples away.
    let detour = try trace(&field, 122, 55, 122, 105, 0.1)
    defer free(detour) in memory.heap
    let middle = detour.length // 4 * 2
    assert(detour[middle] >= 129 and detour[middle] <= 130)

test "a trace in flat color is the straight line, one sample a step":
    var field = try stepped(50, 50, 1000)
    defer free(field.strength) in memory.heap
    let path = try trace(&field, 100, 50, 140, 50, 0.1)
    defer free(path) in memory.heap
    assert(path.length == 41 * 2)
    let diagonal = try trace(&field, 100, 50, 120, 70, 0.1)
    defer free(diagonal) in memory.heap
    assert(diagonal.length == 21 * 2)