PaperlayerView exact revision on arXiv

Source-linked AI summary

Online Object Tracking, Learning and Parsing with And-Or Graphs

Tianfu Wu, Yang Lu, Song-Chun Zhu

arXiv:1509.08067v6cs.CVcs.LG

TL;DR

Online tracking must handle object and scene variations while inferring an unknown object’s state from video. The paper combines tracking, learning, and parsing with hierarchical And-Or graphs and dynamic programming. It reports better or comparable performance across two public benchmark datasets.

  • Problem

    Online tracking must infer an unknown object’s state despite appearance, structural, scale, occlusion, and scene variations.

    Source: §1.1 · p. 1

  • Method

    AOGTracker uses a hierarchical And-Or graph for part configurations, learns object AOGs online with latent SVM, and performs spatial and temporal dynamic programming.

    Source: §1.2 · p. 3, §7 · p. 16

  • Results

    AOGTracker reports better or comparable performance on two public benchmark datasets, outperforming other TB-100/50/CVPR2013 trackers and achieving the best overall rank in VOT2013.

    Source: §6.1 · p. 14, §7 · p. 16, §6.4 · p. 16

  • Takeaways & Limitations

    The reported results support AOG-based tracking, learning, and parsing as a better-or-comparable approach on the tested public benchmarks.

    Source: §7 · p. 16

    The performance gains require more computation, and HOG coordinate discrepancies reduce overlap measurement particularly in the low-resolution subset.

    Source: §6.1 · p. 14, §6.3 · p. 15

Abstract

from arXiv · show

This paper presents a method, called AOGTracker, for simultaneously tracking, learning and parsing (TLP) of unknown objects in video sequences with a hierarchical and compositional And-Or graph (AOG) representation. %The AOG captures both structural and appearance variations of a target object in a principled way. The TLP method is formulated in the Bayesian framework with a spatial and a temporal dynamic programming (DP) algorithms inferring object bounding boxes on-the-fly. During online learning, the AOG is discriminatively learned using latent SVM to account for appearance (e.g., lighting and partial occlusion) and structural (e.g., different poses and viewpoints) variations of a tracked object, as well as distractors (e.g., similar objects) in background. Three key issues in online inference and learning are addressed: (i) maintaining purity of positive and negative examples collected online, (ii) controling model complexity in latent structure learning, and (iii) identifying critical moments to re-learn the structure of AOG based on its intrackability. The intrackability measures uncertainty of an AOG based on its score maps in a frame. In experiments, our AOGTracker is tested on two popular tracking benchmarks with the same parameter setting: the TB-100/50/CVPR2013 benchmarks, and the VOT benchmarks --- VOT 2013, 2014, 2015 and TIR2015 (thermal imagery tracking). In the former, our AOGTracker outperforms state-of-the-art tracking algorithms including two trackers based on deep convolutional network. In the latter, our AOGTracker outperforms all other trackers in VOT2013 and is comparable to the state-of-the-art methods in VOT2014, 2015 and TIR2015.

1 INTRODUCTION

Online tracking must infer an unknown object’s state despite appearance, structural, and scene variations. The paper introduces an AOG-based framework that combines tracking, learning, and parsing with spatial and temporal inference.

1.1 Motivation and Objective

  • Online tracking must infer an unknown object’s hidden states after its first-frame state is given, despite appearance, structural, scale, occlusion, and scene variations.The challenges also include camera motion, background clutter, distractors, illumination changes, and frame cropping.Source: §1.1 · p. 1
  • A hierarchical and compositional AOG recursively quantizes part configurations and supports online selection of discriminative configurations by pruning.The representation is intended to explore many configurations while facilitating computationally effective inference and learning.Source: §1.1 · pp. 1–2
  • The method seeks to preserve online training-set purity by choosing learning frames carefully to reduce model drifting.Positive examples come from the current trajectory and negatives from outside it; only first-frame examples are guaranteed true positives or negatives.Source: §1.1 · p. 2

1.2 Method Overview

  • An object AOG is learned by pruning the full structure according to training error, then retraining with latent SVM and pruning using positive-example latent assignments.Multiple branches can be retained at Or-nodes when their training error is close to the minimum.Source: §1.2 · p. 3
  • Spatial dynamic programming parses sliding windows in a frame to compute matching scores and optimal parse trees from the object AOG.A parse tree selects a child at each Or-node, and its configuration lays out latent parts in the image.Source: §1.2 · p. 3
  • Joint trajectory inference uses past estimated states and pairwise motion constraints, potentially correcting earlier tracking errors.A temporal dynamic-programming algorithm finds the joint solution under a first-order HMM assumption.Source: §1.1 · p. 2, §1.2 · p. 3

2 RELATED WORK

Prior work spans offline trajectory optimization and online appearance- or part-based tracking. AOGTracker distinguishes itself by learning object structure and appearance online, with tracking results that outperform state of the art on TB-100 and are comparable on VOT benchmarks.

2 RELATED WORK

  • Offline tracking methods,,, process recorded videos by generating proposals, linking tracklets, and optimizing trajectories.The passage gives K-shortest path and min-cost flow as examples of trajectory optimization.Source: §2 · p. 3
  • Online tracking starts from a specified object state in streaming video; particle filtering can perform poorly in high-dimensional state spaces, while tracking-by-detection, uses dense on-the-fly sampling.Source: §2 · p. 3
  • Earlier online methods model whole-object appearance or object parts, while missing background models can leave appearance-based tracking vulnerable to distractor-driven drift.The passage describes discriminative tracking as addressing this background-model issue.Source: §2 · p. 3
  • AOGTracker belongs to part-based discriminative tracking and, unlike fixed starmodel configurations, learns both object structure and appearance online.The authors identify it as the first method, to their knowledge, to address explicit online structure learning in tracking.Source: §2 · p. 3
  • AOGs represent many latent part configurations, support robust tracking through stable parts, and produce parse trees that may inform activity or event prediction.The authors contrast this representational capacity with single-template or template-mixture models and describe parse trees as potentially useful beyond tracking.Source: §2 · pp. 3–4
  • TB-100 results outperform state-of-the-art tracking methods, while VOT results are comparable to those methods.The paper describes the TB-100 comparison as outperforming state of the art and the VOT benchmark results as comparable.Source: §2 · p. 4

3 PROBLEM FORMULATION

The formulation treats tracking as Bayesian inference over bounding-box trajectories, then represents part configurations with an And-Or graph (AOG) to support compact exploration of structural alternatives.

3.1.1 Tracking with HMM

  • With a first-order HMM, the given first-frame box anchors inference of later bounding boxes from prediction and image-updating models.The usual marginal-posterior solution is commonly computed using particle filtering.Source: §3.1.1 · p. 4
  • The formulation seeks a joint posterior over the trajectory, enabling feedback inspection of its history.Taking logarithms expresses the objective as a sum of terms over the sequence.Source: §3.1.1 · p. 4

3.1.2 Tracking as Energy Minimization over Trajectories

  • The discriminative trajectory formulation uses an object AOG to score a bounding box through its optimal parse tree, with parts treated as latent variables rather than tracked explicitly.The derivation relies on an independence assumption between object and remaining image domains, and the matching score can be learned discriminatively.Source: §3.1.2 · pp. 4–5

3.2 Quantizing the Space of Part Configurations

  • The part-configuration space is combinatorial without structural constraints, so the method restricts parts to rectangles and decompositions to horizontal or vertical binary splits.The two decomposition rules in Fig. 3 are equivalent representations: a flat structure or a hierarchy with branching factor two.Source: §3.2 · p. 5, Figure 3 · p. 5
  • The construction divides a bounding box into a cell grid, enumerates part types and placements, and recursively composes sub-grids through alternative valid splits.Child sub-grids may overlap up to a specified ratio.Source: §3.2 · p. 5, Figure 4 · p. 5
  • The AOG represents many part configurations through a directed acyclic graph that supports efficient exploration with dynamic programming.The graph's full structure covers a large configuration space using a relatively small set of part instances.Source: Figure 5 · p. 6, §3.2 · p. 6
  • In the AOG, Or-nodes encode alternatives, And-nodes encode decompositions, and terminal-nodes connect parts to image data for appearance variation and occlusion.A parse tree selects a child at each encountered Or-node; the resulting terminal nodes specify a part configuration, while multiple parse trees preserve ambiguity.Source: §3.2 · p. 6

4 TRACKING-BY-PARSING WITH OBJECT AOGS

AOG tracking-by-parsing scores alternative object configurations in a compositional graph, then uses spatial and temporal dynamic programming to infer bounding boxes and trajectories. Trackability, measured from score maps, indicates the quality of the current AOG and helps identify uncertainty.

4.1 Scoring Functions of Nodes in an AOG

  • Terminal nodes score image features, Or-nodes take the best child score, and And-nodes combine child scores according to edge type.The edge-specific operations include sharing an object score, transforming a part score to account for displacement, and composing child scores.Source: §4.1 · p. 7

4.2 Tracking-by-Parsing

  • Spatial DP builds node score-map pyramids bottom-up, then selects root candidates and retrieves their optimal parse trees top-down.Non-maximum suppression retains the top Nbest parse trees for temporal inference.Source: §4.2 · p. 7, Figure 6 · p. 7
  • Temporal DP treats negative parsing scores as per-frame data costs and transition costs as pairwise terms, then backtraces to infer the trajectory.In practice, the method may restrict temporal inference to a short window for long-term tracking.Source: §4.2 · p. 8
  • If no candidates appear in the local ROI, parsing expands to the whole image; if none appear there, the frame’s tracking result is invalid.The method applies spatial and temporal DP in stages without explicitly tracking parts, avoiding loops in inference.Source: §4.2 · p. 8

4.3 The Trackability of an Object AOG

  • Trackability compares a parse-tree node’s score with the mean of its score map; low values flag intrackability and can prompt AOG re-learning.A tracked object is marked intrackable below its running mean trackability minus three standard deviations, although the tracking result may still be valid.Source: §4.3 · p. 8

5 ONLINE LEARNING OF OBJECT AOGS

Online learning updates an object AOG from tracking-derived examples, estimates its parameters with latent SVM, and learns a compact structure by pruning. It re-learns structure and parameters at critical moments, otherwise updating parameters only when tracking results are valid.

5.1 Maintaining the Training Dataset Online

  • Valid tracking results supply positive examples, while other unsuppressed candidates become hard negatives; invalid results leave the training dataset unchanged.The initial positives include locally shifted boxes, and the first-frame negatives are mined from the remaining image.Source: §5.1 · p. 9

5.2 Estimating Parameters of a Given Object AOG

  • Latent SVM estimates AOG parameters with an l2-regularized empirical hinge loss, optimizing by coordinate descent with positive latent assignments and LBFGS.The detection threshold is set to the minimum score among positives.Source: §5.2 · p. 9

5.3 Learning Object AOGs

  • Structure learning selects discriminative branches using training error, then prunes part configurations assigned to fewer than 10% of relabeled positives.The refined AOG is verified against the training threshold and IoU NMS threshold; reducing model complexity speeds tracking-by-parsing.Source: §5.3 · pp. 9–10
  • A critical moment triggers re-learning when intrackable frames and new valid tracking results both exceed their respective thresholds since the previous re-learning.Parts are first placed at the object’s spatial resolution; if verification fails, learning retries at twice that resolution, which handled all testing sequences.Source: §5.3 · p. 10

6 EXPERIMENTS

The experiments evaluate AOGTracker on TB-100/50/CVPR2013 and VOT benchmarks, comparing its performance, model variants, and tracking components. Results include consistent gains on the TB benchmarks and the best overall rank in VOT2013, with comparable performance in VOT2014.

6 EXPERIMENTS

  • The experiments use the same parameter setting throughout, with at most 100 valid tracking frames used for re-learning.The authors state that the shared settings emphasize online learning and that the frame cap reduces learning time complexity.Source: §6 · p. 10

6.1 Results on TB-50/100/CVPR2013

  • AOGTracker consistently outperforms the other trackers on TB-100, TB-50, and TB-CVPR2013 across OPE, SRE, and TRE success plots.The plots include two deep-learning trackers in the TB-CVPR2013 OPE comparison.Source: Figure 9 · p. 11, §6.1 · p. 14
  • AOGTracker gains more than 12% in 10 TB-50 subsets, with its least improvement in the low-resolution subset.The authors attribute the low-resolution result to HOG cell-based coordinates causing overlap-measurement loss relative to pixel coordinates.Source: §6.1 · p. 14

6.2 Analyses of AOG models and the TLP Algorithm

  • AOG-st performs best overall; AOG variants outperform whole-object templates, and structure re-learning consistently improves overall performance.AOGFixed-st slightly exceeds AOG-st on Motion-Blur and Out-of-View, where intrackability is not adequate; temporal DP helps AOG models, while ObjectOnly-s slightly exceeds ObjectOnly-st.Source: §6.2 · p. 15

6.3 Comparison with State-of-the-Art Methods

  • The authors attribute TB-100 performance to complementary HOG, LBP, and color features, learned part configurations, online structure re-learning, temporal DP, and feature-pyramid and whole-frame search.They report that temporal DP also helps maintain the purity of the online training dataset, while whole-frame re-detection addresses out-of-view targets.Source: §6.3 · p. 15

6.4 Results on VOT

  • VOT evaluation is short-term: after target loss, the toolkit re-initializes the tracker and counts failures, measuring accuracy and robustness.Trackers are tested repeatedly on each sequence.Source: §6.4 · p. 15
  • In VOT2013, AOGTracker has the best accuracy and overall rank, while its robustness is slightly worse than PLT, LGT, and LGTpp.PLT won the VOT2013 challenge.Source: Figure 13 · p. 15, §6.4 · p. 16
  • AOGTracker is comparable to other trackers in VOT2014, where rotated bounding boxes expose a limitation in its handling of rotation.It reports 51% accuracy in VOT2015 and 65% accuracy, tied for third place, in VOT-TIR2015.Source: Figure 14 · p. 15, §6.4 · p. 16

7 DISCUSSION AND FUTURE WORK

The discussion concludes that the paper presents an AOG-based tracking, learning, and parsing framework with spatial and temporal dynamic programming and online learning of AOG structure and parameters. The authors describe ongoing work on faster inference and future extensions to generic AOGs and richer scene and event information.

7 DISCUSSION AND FUTURE WORK

  • The framework combines spatial and temporal dynamic programming with online learning of AOG structure and parameters; experiments show better or comparable performance on two public benchmark datasets.Source: §7 · p. 16
  • Ongoing work seeks faster inference as AOGs grow during online learning, including learned decision policies across template-based and part-based computing processes.The paper describes α-process, β-process, and combined α + β-process tracking.Source: §7 · p. 16
  • Future work would combine generic and target-specific AOGs, updating both online, toward life-long video learning without annotations and integration of scene and event grammars.Source: §7 · p. 16
Loading 1509.08067v6…