{'fraction_non_alphanumeric': 0.03688782110515616, 'fraction_numerical': 0.007133616706708557, 'mean_word_length': 4.673306772908367, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 2, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Visual Chunking: A List Prediction Framework for Region-Based Object Detection

We consider detecting objects in an image by iteratively selecting from a set of arbitrarily shaped candidate regions. Our generic approach, which we term visual chunking, reasons about the locations of multiple object instances in an image while expressively describing object boundaries. We design an optimization criterion for measuring the performance of a list of such detections as a natural extension to a common per-instance metric. We present an efficient algorithm with provable performance for building a high-quality list of detections from any candidate set of region-based proposals. We also develop a simple class-specific algorithm to generate a candidate region instance in near-linear time in the number of low-level superpixels that outperforms other region generating methods. In order to make predictions on novel images at testing time without access to ground truth, we develop learning approaches to emulate these algorithms' behaviors. We demonstrate that our new approach outperforms sophisticated baselines on benchmark datasets.

I. INTRODUCTION We consider the problem of object detection, where the goal is to identify parts of an image corresponding to objects of a particular semantic type, e.g. "car". In recent years, machine learning-based approaches have become derigueur for addressing this difficult problem; one classical approach is to transform the problem into one of binary classification, either on bounding boxes [1], [2], or regions. Such approaches (see Section II for a detailed discussion) typically follow a two stage procedure: 1) generate independent proposals to provide coverage across object instances 2) improve precision and reduce redundancy by pruning out highly overlapping proposals Intuitively, the first step returns a set of proposals with high recall and the second step improves the precision. For the second step, traditional approaches rely on a combination of thresholds and arbitration techniques like Non-Max Suppression (NMS) to produce a final output. Such methods, while remarkably effective at identifying sufficiently separated objects, still have difficulty simultaneously detecting objects that are close together or overlap while preventing multiple detections of the same object (see Fig. 6). While we provide contributions to both stages, our focus is on formalizing and improving the second stage.
We formulate the objective of the second step as that of producing a diverse list of detections in the image. We propose an optimization criterion on this list of detections as a natural extension of the intersection over union metric (IoU) (described in Section III-A), and develop an algorithm that targets this criterion. This approach uses recent work on building performance-bounded lists of predictions [3], 1 Carnegie Mellon University, Pittsburgh, PA 15213, USA Fig. 1: Visual Chunking run on test data. The first prediction is shown in red, the second in green, the third in blue, and the fourth in yellow. [4]. Our algorithm shares information across all candidate detections to build a list of detections, specifically exploiting this information to perform well even when object instances are adjacent. Each decision of appending to the list of detections is made with contextual information from all previous detections. Importantly, our list prediction algorithm is agnostic to the source of candidate detections. This provides our approach with the ability to use any candidate generating method as input for constructing a list.
Each candidate detection is treated as a union of superpixels with no adjacency constraints. We call these unions "chunks," inspired by a well-known task in Natural Language Processing: "chunking," which involves grouping many words together into meaningful semantic instances / entities. We use "region" to refer to a contiguous group of superpixels, and reserve "chunk" to refer to a group of superpixels corresponding to a single semantic instance. The analogy is particularly apt when object instances are adjacent, as in Fig. 1.
For the first step, we develop a class-specific supervised approach of region-based object proposal by iteratively grouping superpixels produced by a low-level segmentation algorithm [5] to form chunks. This helps build a highrecall candidate set. This algorithm learns to "grow" by utilizing class-specific ground-truth labeling by emulating an algorithm that optimizes a chunk's IoU score with an object, which we present in Algorithm 2. This strategy follows from imitation learning approaches [6], [7].
Our technique for building the list of detections can be run for arbitrary list lengths, or budgets. This enables several use cases: building very short lists of highly confident object predictions (high precision), long lists of many candidate regions (high recall), and dynamic length lists tuned by some heuristic(s) (e.g., the highest predicted IoU score of the remaining candidates).
II. RELATED WORK Much work has been done in the combined areas of object detection and semantic labeling. Object detection approaches often seek to place bounding boxes around all instances of objects [1], [8]. [9] casts the multi-class (and multi-instance) detection problem as a structured prediction task instead of NMS as post processing. However, the resulting detections are still bounding boxes.
Intermediate approaches deform the regions inside the output of a detector to produce object segmentations [10], [11], [12], or, conversely, adjust bounding boxes based on low-level features such as boundaries, texture, and color [13], [14]. Again, these approaches refine individual detections relying on the initial detector output. In contrast, we attempt to find the best list of detections given a large collection of candidate detections and regions. Closer to our work, [15] proposes to use a deformable shape model to represent object categories in order to extract region level object detections. This approach reasons about occluders and overlapping detection by using depth layering and is designed for one specific shape model for region-based representation, while our approach is agnostic to the source of region segments and detection boxes.
Direct region-based techniques, such as [16], [17], [18], use region-based information to formulate detections, the produced detections are bounding boxes, and detection performance is analyzed using individual bounding box metrics. [19] produces region-wise segmentations, however they assume the existence of only one object in each image. [20] produces multiple region-wise segmentations, but contiguous and adjacent objects are not resolved, and ignore inter-class context. Other region-based techniques are segmentation algorithms that rely on combining low-level image features with class-specific models [21], [22], [23], [24], control segmentation parameters from object detection [25], or use the box-level detections as features for segmentation [26], [27]. These approaches attempt to find regions that best agree with both the region segments and individual detections but do not explicitly deal with the problem of finding the most consistent list of detections as we do.
Semantic systems such as [28], [29], [30], [31] do produce region-level labels, which can be grouped into detections, however there is no notion of separate detections; connected components of labeling are not grouped into their constituent object instances. [32] uses non-overlapping segmentation proposals in its first stage, thus allowing, in principle, the handling of multiple instances of the same class, without explicitly optimization for multi-instance settings. Although the evaluation criteria in [32] focuses on per-class overlap without accounting for multiple instances, the authors do note the possibility for multi-instance extension. Combining semantic labeling with object detectors has been explored in different ways. Several approaches were proposed to combine pixel-level classification labels and box-level detections into a single inference problem. For example, [33], [34], [35], [36] incorporate detections into a CRF model for semantic labeling. These techniques attempt to generate a holistic representation of the scene that combines objects and regions. These approaches rely on semantic segmentation. Our approach, while incorporating semantic segmentation, is agnostic to the input features, as well as to the source(s) from which candidate detections are generated.
Another group of approaches related to our work address the problem of generating proposals for regions or boxes that are likely to delineate objects, in a class-independent manner. The proposals can then be evaluated by a class-specific algorithm for object detection. They include, for example, generating regions by iterative superpixel grouping [37], [18], and ranking proposed regions [38] or boxes [39], [40] based on a learned objectness score. In [41], the authors investigate an iterative, class-specific region generation procedure that incorporates class-specific models at different scales, and requires bounding boxes as input. Our generation method, in comparison, directly optimizes the instance-based IoU metric, and we provide worst-case and probabilistic performance bounds. All of these approaches are complementary to our work in that we can potentially use any of them as input to our candidate generation step, thus, we incorporate and compare to several of them in our experiments.

III. APPROACH
Our task is to output a list of chunks, i.e., list of sets of superpixels as described in Section I, with high intersection over union (IoU) scores with each of the ground truth instances in the image. This metric is formalized in Section III-A. We decompose the task into two parts: • Generation of a set of candidate chunks containing some elements that cover individual object instances. • Iterative construction of a list of chunks by selecting from an arbitrarily generated set of candidate chunks so as to maximize a natural variant of intersection over union score for multiple object instances and multiple predictions. In the second stage, the candidate chunks can be generated from any algorithm, providing our method with the ability to augment our set of grown candidates constructed by other means. We start by describing the method by which we build lists of detections for the second stage, and first define a natural scoring function to evaluate any input list of chunks given ground truth on the pixels corresponding to objects of interest in a scene. We provide an efficient greedy algorithm that is guaranteed to optimize this metric to within a constant factor given access to ground-truth and this arbitrary set of (potentially overlapping) candidate chunks.
Our test-time approach, following recent work in structured prediction [4], [6], is to learn to emulate the sequential greedy strategy. The result is a predictor that takes a candidate set of chunks and iteratively builds a list of chunks that are likely to overlap well with separate objects in the scene.
We do not place assumptions on the given candidate set of chunks: the list predictor is agnostic to the way the candidate set of chunks is generated. Such a set can be heuristically generated in many ways, e.g., those created from the baseline approaches described in Section IV. In Section III-C, we provide an algorithm designed to generate a candidate based on a fixed superpixel-based segmentation, and in Section III-D extend this algorithm to the case of growing multiple chunks per images.

A. Objective function and greedy optimization
We establish an objective function to evaluate the quality of any list, and devise a greedy algorithm to approximately maximize this objective function given access to the groundtruth. This will lead to the development of learning algorithm that produces a prediction procedure that operates on novel images.
Given an image with ground truth instance set G = {g 1 , ..., g m } and candidate chunk set C = {c 1 , ..., c n }, our goal is to sequentially build a list of chunks out of C so as to maximize the sum of IoU's with respect to ground truth instances. Denoting L = (c 1 , c 2 , . . . , c k ) as a size-k list of chunks, we first establish correspondences between candidate chunks and ground truth instances to enable pairwise IoU computation. Note that each c i is associated with at most one ground truth instance g i , and each g i is associated with at most one c i . For analytic convenience, we augment G with k − m dummy ground truth instancesĝ to deal with the case in which the length of the list is larger than the number of ground truth instances (|L| > |G|). Every chunk c has zero intersection with eachg. Each feasible assignment corresponds to a permutationL = (c p1 , c p2 , . . . , c p k ) of L, and the sum of IoU scores for this permutation can be written as the following: h(L; G) = k i=1 |cp i ∩gi| |cp i ∪gi| . It is natural to define the quality metric f (L; G) of a list L to be the sum of IoU scores under the optimal assignment, i.e., f (L; G) = maxL ∈P (L) h(L, G), where P (L) denotes all permutations of L. Our goal during training is to find list L to maximize f : This scoring metric, which is a natural generalization of the IoU metric common in segmentation and single instance detection [42], [43], encourages lists of a fixed length that contain chunks that are relevant and diverse in covering multiple ground truth instances. Unfortunately, the metric as written down does not possess a clear combinatorial structure like modularity or submodularity that would beget easy optimizability.
Interestingly, however, Problem (1) can be cast as an equivalent maximum weighted bi-partite graph matching problem. This problem can be shown to be a submodular maximization problem under matroid partition constraints, and a greedy algorithm as shown in Algorithm 1 has multiplicative performance guarantees [44]. In addition to these guarantees, such a greedy algorithm is desirable as it is easily imitable at test time, and has a recursive solution: the k + 1 length list is exactly the k length list with the next greedily chosen item appended. The greedy algorithm behaves as follows: at each iteration, it chooses the chunk with the highest IoU with one of the remaining ground truth instances. More precisely, a chunk's best overlap with each remaining ground truth is defined as y(c; G re ) = max g∈Gre |c∩g| |c∪g| (the "greedy marginal"), where G re is the set of remaining unpaired ground truth instances. At each step, the algorithm chooses the chunk with the highest y(c; G re ) value, appends it to the list, and removes its associated ground truth from the set of remaining ground truth. This associated ground truth element is given by π gr (c; G re ) = arg max g∈Gre |c∩g| |c∪g| .

Algorithm 1 Greedy List Generation with Ground-Truth Access
Input: Set of candidate chunks C, set of ground truth instances G, size of predicted list k Output: A near-optimal list L gr of chunks L gr = ∅, G re = G for i = 1 to k do c gr i = arg max c∈C y(c; G re ), g gr i = π gr (c; G re ).
choose the highest scoring (chunk, GT) pair L gr = L gr ⊕ c gr i . append the chunk to the list Gre = Gre \ g gr i .
remove the associated GT from the remaining GT set end for Return L gr Critically, the greedy algorithm is recursive, meaning longer lists of predictions always include shorter lists, and is within a constant factor of optimal 1 : Theorem 1: Let L gr i be the list of the first i elements in L gr and L * i be the optimal solution of Problem (1) among size-i lists f (L gr i ) ≥ 1 2 f (L * i ), ∀i = 1, · · · , k. See the appendix for proof of Theorem 1, which invokes results from [44]. The implication is that if we are given a budget |L| to build the list, then each L gr i scores within a constant factor of the optimal list among all lists of budget i, for i = 1, . . . , |L|. This is an important property for producing good predictions earlier in the list and for producing the list of chunks rapidly. The empirical performance is usually much better than this bound suggests.

B. List prediction learning
In essence, the greedy strategy is a sequential list prediction process where at each round it maximizes the marginal benefit given the previous list of predictions and ground truth association. Maximization of the marginal benefit at each position of the list yields chunks that have high IoU with ground truth instances and minimal overlap with each other. At test time, however, there is no access to the ground-truth. Therefore, we take a learning approach to emulate the greedy algorithm. We train a predictor to imitate Algorithm 1, with the goal of preserving the ranking of all candidate chunks based on the greedy increments y(c; G re ). This predictor uses both information about the current chunk and information about the currently built list to inform its predictions. In our experiments, we train random forests as our regressor with features as Φ(c, L) (each chunk's feature is a function of itself and the currently built list, as described in Section IV-B), and regression targets y(c; G re ) (the score for a chunk at each iteration is the greedy marginal, or how much a chunk candidate covers a new object instance). This regression of "region IoU " is similar to that explored in [45], except it is explicitly reasoning about multiple objects, as well as the current contents of the predicted list. The prediction procedure is similar to the greedy list generation as in Algorithm 1, with the difference that there is no access to the ground truth.

C. Growing for a single instance
To generate a set of diverse chunks (output of stage 1 in the detection process), we develop a class-specific algorithm that "grows" chunks via iterative addition of superpixels, with the goal of producing diverse candidate detections that cover each ground truth object instance. We first analyze the case where there is only a single object of interest g in the image. We consider a chunk c to be a union of superpixels s, i.e., c = ∪ n i=1 {s i }. Let R(c) denote the IoU score between c and g.
To grow a chunk, Algorithm 2 starts with an empty chunk (no superpixels), and adds single superpixels to the current chunk sequentially. After each addition, the resulting chunk is copied and added to the set of candidate chunks. Let α i = |si∩g| |si| be the ratio of intersection area with ground truth to the size of a superpixel s i . The set of chunks generated by the greedy algorithm described in Algorithm 2 is guaranteed to contain the optimal chunk if the input predictor G returned the exact value of α i , i.e.,α i = α i .

Algorithm 2 Single Instance Chunk Growing Algorithm
Input: Set of superpixels S, grower predictor G. Output: A set of chunks, C G . c = ∅, C G = ∅ Sort elements in S by decreasing order ofα i = G(s i ) Theorem 2: Let G * be an oracle growing predictor, i.e., G * (s i ) = α i = |si∩g| |si| . The output set of C G from Algorithm 2 by setting G = G * contains the best chunk given the set of superpixels S.
See appendix for proof. At testing time, we must give an estimate of α i , i.e.,α i . We train a random forest regressor as our predictor G with features θ for estimation. We analyze the performance of Algorithm 2 under approximation by relating the squared regression error of G to the IoU score of the Fig. 2: Selected images of the best grown chunks for images with single and multiple objects. Each chunk grows independently of the others. Given the initial seed, superpixels are iteratively added to the growing chunk. The predictor greedily adds superpixels that it believes make the highest contribution to the overall class-specific IoU score of the currently growing chunk. grown best chunk in the chain. We note that the test-time performance depends on both the size of the squared error and the number of predictions made. Notably, the error bound has no explicit dependence on the area sizes of ground truth object instances and images. See appendix for proof.
Theorem 3: Given a regressor G that achieves no worse than absolute error uniformly across all superpixels, let c * G be the best chunk in the predicted set C G . The IoU score of c * G is no worse than 2 of the IoU score of the optimal chunk c * : R(c * G ) > R(c * ) − 2 . Corollary 1: Suppose regressor G has expected sq. error δ over the distribution of superpixels, let n be the number of superpixels in the image, then we have for any η ∈ (0, 1),

D. Growing for multiple instances
We run the growing algorithm more than once to cover multiple objects. Instead of making predictions based solely on features of each individual superpixel, we augment the information available to the predictor by including a feature of the current grown chunk, θ(s i , c) (see Section IV-B for more information about grower features). This yields predictors that prefer choosing superpixels in close proximity to the currently growing chunk, and allows us not to explicitly encode contiguity requirements, as objects may be partially occluded in a way that renders them discontiguous. We also modify Algorithm 2 by "seeding" the chunks at a set of superpixel locations, L (the initialization step, c = ∅, becomes c = {s i } ∀s i ∈ L), and running the growing procedure on each of these seeds separately. See appendix for the pseudo-code description modified from Algorithm 2. In practice, we choose a seeding grid interval and a maximum chunk size cutoff, yielding |C G | ∼ 700. In Figure 2, we visualize the sequential growth of the best chunks for each object instance.

IV. EXPERIMENTS
We describe our experiments and predictor features in the next two sections, and discuss the results of each experiment in their respective captions.

A. Datasets and baseline algorithms
We perform experiments on imagery from 3 different datasets. We refine the Stanford Background Dataset [46]   from each prediction pool (dashed lines) and predicted candidates (solid lines) on a 50/50 split of LM+Sun Adjacent Cars dataset. Our chunk generating method (dark blue) generates candidates of similar quality to that of SCALPEL (light blue). On this dataset, our DPM-based baselines (magenta and dark cyan) perform quite well, but the best performing list prediction method (green line) is our list predictor that uses the SP ∩ DPM chunks as the candidate pool, and essentially has learned how to reorder them. This demonstrates how our approach can utilize and improve different candidate sources. labeling to include a vehicle class with instance labeling. We also perform experiments on PASCAL VOC 2012 ( Fig. 5 and Tables II and I). This dataset possesses relatively few images containing adjacent and/or overlapping instances of the same class. Therefore, we created a subset of the LM+Sun dataset [31] of images containing at least 2 adjacent cars, consisting of 1,042 images.

B. Features
As discussed in III-B, the features Φ(c, L) should encode the quality of a chunk c (e.g. "Does the chunk look like a vehicle?") and similarity with the currently predicted list L (e.g. "Is this chunk similar to previously predicted chunks" ). One of the quality features is built upon the superpixel-wise multi-class label distribution from [30], where we compute label distribution for each chunk via aggregating histograms of its constituent superpixels. The other quality features are shape features including central moments of the chunk, area, and scale relative to the image. The similarity features we use primarily encode spatial information between predictions. We use a candidate's I U with previous predictions, the spatial histogram used in [9] and the size of the current list. Chunks with high similarity with previously predicted chunks in the list are less favored.
The features θ(s, c ) for the grower encode information about the quality of proposed chunk c = c ∪ {s} by growing c with superpixel s. The grower uses the same quality features that characterize c used by the list predictor, as well as several of the class-agnostic features described in [18], specifically color similarity (color histogram intersection), which encourages regions to be built from similarly colored regions, and region fill, which encourages growing compact chunks. See [18] for further details. As each superpixel is iteratively added to the chunk, similarity to the growing chunk for remaining candidate superpixels is recomputed.
We evaluate three methods 2 leveraging existing bounding box detections and superpixel-wise semantic labeling algorithm, all of which serve as our baseline systems for building lists of predictions: 1) Bounding box detector output after NMS filtering 2) Connected components of scene parsing ("SP") / semantic labeling 3) A combination of 1) and 2): intersection of connected components with bounding boxes, which creates chunks for every bounding box by extracting the labeled region inside ("SP ∩ DPM"). The third baseline is intended to capitalize on desirable properties of each component while avoiding their less desirable properties: boxes usually violate the object boundaries, and semantic labeling does not separate adjacent instances. The downside to this baseline is that it can suffer from compounding both   [15]), and first slot scores (corresponding to the average overlap of the first prediction in each image) for systems trained and tested on the standard PASCAL 2012 train and val sets. We find that the very small amount of co-occurring instance training data was not sufficient to enable our system to perform as well as it did in our other experiments on images with co-occurring instances. While [15]   detector and scene parsing errors. See Fig. 6 for a visual comparison.
We investigate the region generating methods of SCALPEL [41] and Selective Search [18], and in Fig. 3 compare our chunk generating method against them on our LM+Sun Adjacent Cars dataset with the Average Best Object method suggested by [41], and additionally train our system by using these methods to fill the candidate pool. In Table II, we compare different list predictions methods on vehicle and person data, respectively.

V. CONCLUSION
We provide a novel method for producing region-based object detections in images, treating the problem as a list prediction from a set of candidate region proposals. We formulate a scoring criterion for multiple object instances and multiple predictions. We develop a list prediction algorithm that directly optimized the criterion. Our approach is agnostic to proposal generation method and provides a recursive solution for all list lengths, enabling it to easily produce any k best guesses for objects. We provide a method for class-specific candidate generation algorithm, yielding good coverage of objects. We demonstrate that our list prediction is a useful method for improving arbitrary candidate pools.