I’m tracking moving animals in a video. Each video frame has a few “things” that may qualify to be an animal (dirt, experimenter’s hand, shadows, objects, etc). I’d like to keep track of most of these things, and then once I processed the whole video, choose the track that has the highest probability of belonging to an animal.
The process I use seems to lend itself to a tree data structure: new locations are found in the vicinity of locations from the previous frame. So every location may spawn multiple new locations each of which may spawn even more etc.
Here is my naive implementation of a Node using the excellent AbstractTrees.jl package:
using AbstractTrees
struct TrackTree
previous::CartesianIndex{2}
children::Vector{TrackTree}
end
TrackTree(i::CartesianIndex) = TrackTree(i, TrackTree[])
AbstractTrees.children(tt::TrackTree) = tt.children
guess = #some guess
tt = TrackTree(guess)
for img in video # iterate over the video frames
for leaf in Leaves(tt) # iterate over all the previous' frame's nodes
locations = find_next_locations(leaf.previous, img) # detect new locations in proximity to the previous' frame's locations
for location in locations
push!(leaf.children, TrackTree(location)) # add the new location to the leaf's children
end
end
end
This is my first use of a tree data structure so I’m a bit unsure if this is optimal and would appreciate help if you spot some problems.
Let me just add that at the end, I’ll need some way to compare between all the different tracks. So if my tree has n outer nodes there will be n different tracks I’ll need to compare. Therefore I’ll need a way to retrieve each of these n tracks. I’m as of yet unsure how to do that…
This might get out of hand rather quickly. One common strategy to keep the size of the tree manageable is beam search. This resembles what a particle filter does, maintain a fixed-size set of nodes to explore based on likelihood.
I’ve noticed that your tree node has references to child nodes, but not to parent nodes. Your later analysis may be simplified by having the parent reference in there as well.
How do you count these n tracks (I’m not sure what an outer node means)? A tree has branches and there are potentially an enormous number of possible tracks (hence the requirement for beam search or other pruning). At each level of the tree, the number of potential tracks grows with the branching factor, e.g., for a binary tree, the number of ways to reach the bottom from the root node grows by a factor of 2. In your case, the branching factor will not be fixed, but it will always be \geq 1, e.g., if a parent have three potential child nodes, there are now three new potential tracks.
I’ll build a new implementation that includes the parent’s node as well as the children’s.
The way things are set up now, each node has at least one child (not zero). Most of the quantities I plan to use to determine which track is real are available only at the end of the track (distance of the last location to the first, tortuosity, etc). So I’m not sure how well I’ll be able to prune the tree in the middle of growing it. But I should try and think of ways to do that or:
and the way I retrieve the different tracks from a tree, tt, is:
for leaf in Leaves(tt)
yx = CartesianIndex{2}[]
while isdefined(leaf, :parent)
push!(yx, leaf.data)
leaf = leaf.parent
end
end
But admittedly, this unnecessarily copies the data into a new vector. I’m doing this mostly to see that things work as expected, in actuality I’ll be extracting the measures I’ll use to compare between the different tracks. But you see, I use Leaves to start at the ends of the tree and move my way up. Each leaf represents one and only one possible track. This is what I meant with n tracks from before. If there are n leaves there are n tracks.
(I couldn’t get all the iteration definitions shown in the examples going)
OK, I got “burned” by that. Some settings result in a snappy run, some I had to abort because it was taking so long. So I’ll have to limit the number of children each new location can spawn. I’ll try and improve on this a bit more…
What you’re looking for is an iterator over all paths from the root to a leaf (or from the leave to a root? doesn’t matter, the below should easily be adjustable for the reverse lazy order). Does the order for the leaves matter to you? If not, this should do it:
Iterator for one track
using AbstractTrees
using AbstractTrees: isroot, parent
######
# Tree
######
struct MyTree{D}
data::D
parent::Union{Nothing,MyTree{D}}
subtrees::Vector{MyTree{D}}
function MyTree{D}(d::D, ::Nothing, v::AbstractVector{MyTree{D}}) where D
new{D}(d, nothing, v)
end
function MyTree{D}(d::D, parent::MyTree{D}, v::AbstractVector{MyTree{D}}) where D
ret = new{D}(d, parent, v)
push!(parent.subtrees, ret)
ret
end
end
MyTree(d::T, parent=nothing, v=MyTree{T}[]) where T = MyTree{T}(d, parent, v)
Base.eltype(::Type{MyTree{T}}) where T = T
AbstractTrees.children(t::MyTree) = t.subtrees
AbstractTrees.parent(t::MyTree) = t.parent
AbstractTrees.isroot(t::MyTree) = parent(t) === nothing
Base.show(io::IO, t::MyTree) = print(io, "MyTree{D}(", t.data, ')')
##########
# Iterator
##########
struct TrackIterator{T}
tree::T
end
Base.IteratorEltype(::Type{<:TrackIterator}) = Base.HasEltype()
Base.IteratorSize(::Type{<:TrackIterator}) = Base.SizeUnknown()
Base.eltype(::Type{TrackIterator{T}}) where T = eltype(T)
Base.iterate(t::TrackIterator) = iterate(t, t.tree)
Base.iterate(_::TrackIterator, ::Nothing) = nothing
function Base.iterate(_::TrackIterator{T}, state::T) where T
ret = state.data
isroot(state) && return (ret, nothing)
return ret, parent(state)::T
end
Used like this:
julia> t = MyTree(0)
MyTree{D}(0)
julia> ts = [MyTree(i, t) for i in 1:3]
3-element Vector{MyTree{Int64}}:
MyTree{D}(1)
MyTree{D}(2)
MyTree{D}(3)
julia> print_tree(t)
MyTree{D}(0)
├─ MyTree{D}(1)
├─ MyTree{D}(2)
└─ MyTree{D}(3)
julia> [ collect(TrackIterator(_t)) for _t in Leaves(t) ]
3-element Vector{Vector{Int64}}:
[1, 0]
[2, 0]
[3, 0]
It’s lazy and produces leaves first.
Producing parents first would be better though, as then iteration would be type stable (gotta check whether a parent exists now, check for children is simply “isempty” which doesn’t necessarily have to introduce more type instability).
This is really good. It’s exactly the example I was hoping for. So how would you iterate through parents first…? That would be the more natural direction anyways, since I’d start at the beginning of the track.
The perceptual advantage with iterating by the leaves is that it represents each individual track – each leaf is one track. Iterating by parents doesn’t, or is there a way to know when the iterator got to the end of the branch?
Each frame results in a level in the tree. All branches end in the same level (frame #4 in this example). Each leaf represents one possible track (10 in this example). If we start at one leaf we can climb unambiguously up to the root, which would result in one track (albeit beginning at the end of the track and ending at the beginning of the track).
###################
# ParentTrackIterat
###################
struct ParentTrack{T}
tree::T
end
Base.IteratorEltype(::Type{<:ParentTrack}) = Base.HasEltype()
Base.IteratorSize(::Type{<:ParentTrack}) = Base.SizeUnknown()
Base.eltype(::Type{ParentTrack{MyTree{T}}}) where T = Vector{eltype(T)}
Base.iterate(pt::ParentTrack{MyTree{T}}) where T = iterate(pt, (MyTree{T}[], [pt.tree]))
function Base.iterate(_::ParentTrack, (parents, toProcess))
isempty(toProcess) && return nothing
local el
# push work items until we can't anymore
while true
el = pop!(toProcess)
children = el.subtrees
push!(parents, el)
if isempty(children)
break
else
append!(toProcess, children)
end
end
# we're in a leaf
# get our return value and remove ourselves
c = map(x -> x.data, parents)
pop!(parents)
if !isempty(toProcess) && last(toProcess).parent != el.parent
pop!(parents) # pop the parent
end
return c, (parents, toProcess)
end
using AbstractTrees, AutoHashEquals
@auto_hash_equals mutable struct Node
data::Int
children::Vector{Node}
parent::Union{Node, Nothing}
end
Base.show(io::IO, n::Node) = print(io, n.data, " with ", length(n.children), " children")
Node(data) = Node(data, [], nothing)
Node(parent::Node, data) = Node(data, [], parent)
function Node(data, children::Vector{Node})
n = Node(data, children, nothing)
foreach(c -> c.parent = n, children)
n
end
AbstractTrees.children(n::Node) = n.children
AbstractTrees.printnode(io::IO, n::Node) = print(io, n.data)
isleaf(n::Node) = isempty(n.children)
t = Node(1, [Node(2, [Node(3), Node(4)]), Node(5)])
function iterate_paths(root::Node, memory = Node[])
Channel{Vector{Node}}(0) do ch
for n in PreOrderDFS(root)
if !isempty(memory) && isleaf(last(memory))
while last(memory) != n.parent
pop!(memory)
end
end
push!(memory, n)
if isleaf(n)
put!(ch, memory)
end
end
end
end
c = iterate_paths(t)
for path in c
println(copy(path))
end
Yeah, that’s a bit of a footgun. If you’re careful not to yield on the consuming end you don’t need to duplicate the memory, but this might break on 1.8 anyways. So in summary, the copy should probably go into the producer
Thank a lot people! I’ll try it out with both implementations, or is @pfitzseb better?
So just a naive question: is this the first time someone needed a tree where nodes could have n ≥ 1 children? I mean, shouldn’t this live in a package somewhere? or is this so trivial / specific that no one thought to do it?
Definitely not (in fact, I implemented one for a package I’m writing about two weeks ago), but this is quite a simple data structure in and of itself. I’m actually surprised it’s not in DataStructures.jl yet. It’s just that what you’re trying to extract is unusual (the paths from root → leaf itself) instead of just producing the elements that the paths consists of (which would be easier than returning the array! You just have to copy the tree when you hit a leaf, remove that leaf and start iteration from the new root again).
Trees with an arbitrary amount of children are not really all that interesting algorithmically. They don’t usually have good algorithmic guarantees either - historically, binary trees are preferred (imo because proofs on them are easier, because there’s only a limited amount of cases you have to think about).
Speaking of which - for your original problem, I’d go meta: instead of saving a tree of potential “tracks” per object, I’d create a quadtree per image over the sequence of images for saving the detected “objects” (if there are a lot - else an array or dict with positions and extent of the object should suffice). The reason is quite simple: you’ll have to create & keep track of a lot of independent trees should objects be detected spuriously if you decide to create one tree per object (remember, the computer doesn’t a priori “know” where the next child of the object should be).
For matching objects, there are a few techniques. One keyword for search is Video tracking. Be aware that (as far as I know) the field isn’t particularly good with tracking a lot of distinct objects, mainly because of the computational cost involved (though this may have changed in recent years).
Regarding the original problem: I feel like the tree-based approach is unlikely to work well, but I’m pretty sure you can dig up a bunch of papers on video tracking.
Run object detection on each image and save the result in a quadtree based on the location of each detected object
Once you have a tree per image, you can find out whether two objects are close to one another by checking whether they are close in the tree (which is better than having to compute a real distance between all detected objects) and only if they are somewhat close in the tree, calculate real distances. This may be problematic if there are very fast objects in your video, moving faster than your threshold for closeness (but you’ll have that problem with any distance anyway).
Nevertheless, it should be algorithmically better if you want to strive for performance. It’s a trick similar to using Octrees for simulations in 3D space and only considering neighbours in the tree for influence on each object.
In general, having a fixed number of children per node is often easier to handle algorithmically than an arbitrary number (it also makes proofs easier) because you can give invariants for e.g. childA that are advantegous.
