Tree-Structured Reinforcement Learning for Sequential Object Localization

1 Introduction

• Existing proposal algorithms search locations and scales separately, often ignoring correlations among proposals such as spatial layouts or semantic relationships.The paper motivates incorporating cues from previously predicted and potentially future proposals.Source: §1 · p. 1
• Tree-RL learns to localize multiple objects sequentially using both the current observation and historical search paths, with a long-term reward for localizing all objects.The reward balances exploration of uncovered objects with refinement of the current one.Source: §1 · pp. 1–2
• Starting from the whole image, Tree-RL recursively takes the best scaling and local-translation actions, yielding diverse near-optimal paths that cover objects across scales and locations.The figure distinguishes scaling windows from locally translated windows.Source: §1 · p. 2, Figure 1 · p. 2
• Tree-RL achieves similar recall to RPN on PASCAL VOC 2007 and 2012 using significantly fewer candidate windows, with more accurate localizations and higher detection mAP when combined with Fast R-CNN.The experiments are reported in the introduction without numerical values.Source: §1 · p. 2

2 Related Work

• Object proposal methods use low-level cues or learned anchors to generate windows, but often treat proposals independently and may waste computation on images with few objects.Examples include Selective Search, Edge Boxes, and RPN.Source: §2 · p. 2
• Active-search methods reduce windows through strategies such as branch-and-bound, context-driven search, and sequential evaluation using spatial context.The paper cites approaches by Lampert et al., Alexe et al., and Gonzeles-Garcia et al.Source: §2 · pp. 2–3
• Visual-attention models use information from previous steps to guide sequential tasks such as image captioning and character recognition.The cited examples use recurrent neural networks to focus on different regions over time.Source: §2 · p. 3
• Unlike prior multi-object handling that repeats single-object search with inhibition-of-return, Tree-RL searches multiple objects in one run and supplies multiple paths rather than regression anchors.The paper contrasts its top-down tree search with a method that recursively divides windows and treats visited windows as anchors.Source: §2 · p. 3

3.1 Multi-Object Localization as a Markov Decision Process

• The MDP state combines current-window features, whole-image features, and action history; actions scale or locally translate the window, while rewards reflect localization gains across objects.The reward gives +1 or −1 according to whether any ground-truth object has higher IoU with the next window, and adds +5 for a first-time hit above IoU 0.5.Source: §3.1 · pp. 3–4

3.2 Tree-Structured Search

• At each window, tree search recursively follows the best scaling and local-translation actions, retaining multiple near-optimal paths to better handle objects at different scales.Scaling changes window size, whereas local translations largely preserve it; exploring both branches helps address the risk of favoring large objects.Source: §3.2 · pp. 4–5

3.3 Deep Q-learning

• Training uses episodes from the whole image, ε-greedy action selection, replay memory, and mini-batch Q-learning updates to train the network weights.During exploitation, the agent randomly selects from the best action in each action group, matching the two-branch test-time search.Source: §3.3 · p. 5

3.4 Implementation Details

• Training used 25 epochs on about 16,000 VOC trainval images; tree depths 5 and 6 yield 31 and 63 test-time steps, respectively.The discount factor is 0.9, and ε is annealed from 1 to 0.1 over the first 10 epochs before remaining at 0.1.Source: §3.4 · pp. 5–6, Table 2 · p. 6

Experimental setup

• Recall comparisons use VOC 2007 because VOC 2012 ground-truth annotations are not public; the online server returns only whole-test detection mAP for VOC 2012.Source: §4 · p. 6

Tree-RL vs Single Optimal Search Path RL

• Tree-RL beats single-path RL in nearly all recall scenarios, especially for large objects, but trails on small objects at 31 windows and IoU 0.6 or 0.7; its recall keeps rising with tree depth.The paper defines large objects as containing more than 2,000 pixels; the authors attribute the small-object exception to a search tree that is too shallow at five levels.Source: §4 · p. 6

Recall Comparison to Other Object Proposal Algorithms

• Tree-RL significantly outperforms BING, Edge Boxes, Geodesic Object Proposal, Selective Search, and RPN with few proposals; its advantage narrows as proposals increase but persists at high IoU.The comparison covers VOC 2007; Figure 5 presents recall across IoU thresholds and proposal counts.Source: Figure 5 · p. 7, §4 · p. 7

Detection mAP Comparison to Faster R-CNN

• With top 255 proposals, Tree-RL (VGG-16) + Fast R-CNN (ResNet-101) outperforms RPN + Fast R-CNN and Faster R-CNN on detection mAP.Tables 3 and 4 report detection results on the VOC 2007 and 2012 testing sets.Source: §4 · p. 7, Table 3 · p. 8, Table 4 · p. 8

Visualizations

• Figure 6 shows level-2 to level-4 windows in green, yellow, and red; within 15 proposals through level 4, Tree-RL localizes most large or middle-sized objects.The first level is the whole image.Source: Figure 6 · p. 8, §4 · p. 8

• Tree-RL sequentially searches for objects while considering global interdependency between them.Source: §5 · p. 8
• Tree-RL achieves recall comparable to RPN with fewer proposals and higher localization accuracy.Source: §5 · p. 8
• Combined with Fast R-CNN, Tree-RL achieves detection mAP comparable to Faster R-CNN (ResNet-101).Source: §5 · p. 8