Enforcing a specific topology in image segmentation is a very important but challenging problem, which has attracted much attention in the computer vision community. Most recent works on topology-constrained image segmentation focus on binary segmentation, where the topology is often described by the connectivity of both foreground and background. In this paper, we develop a new multi-labeling method to enforce topology in multi-label image segmentation. In this case, we not only require each segment to be a connected region (intra-segment topology), but also require specific adjacency relations between each pair of segments (inter-segment topology). We develop our method in the context of segmentation propagation, where a segmented template image defines the topology, and our goal is to propagate the segmentation to a target image while preserving the topology. Our method requires good spatial structure continuity between the template and the target such that the template segmentation can be used as a good initialization for segmenting the target. In addition, we focus on multi-label segmentation where a segment and its adjacent segments form a ring structure, which is among the most complex type of inter-segment topology for 2D structures. We apply the proposed method to segment 3D metallic image volumes for the underlying grain structures and achieve better results than several comparison methods. Finally, we also apply the proposed method to interactive segmentation and stereo matching applications.

Multi-target tracking plays a key role in many computer vision applications including robotics, human-computer interaction, event recognition, etc., and has received increasing attention in past several years. Starting with an object detector is one of many approaches used by existing multi-target tracking methods to create initial short tracks called tracklets. These tracklets are then gradually grouped into longer final tracks in a heirarchical framework. Although object detectors have greatly improved in recent years, these detectors are far from perfect and can fail to detect the object of interest or identify a false positive as the desired object. Due to the presence of false positives or mis-detections from the object detector, these tracking methods can suffer from track fragmentations and identity switches. To address this problem, we formulate multi-target tracking as a min-cost flow graph problem which we call the average shortest path. This average shortest path is designed to be less biased towards the track length. In our average shortest path framework, object misdetection is treated as an occlusion and is represented by the edges between track-let nodes across non consecutive frames. We evaluate our method on the publicly available ETH dataset. Camera motion and long occlusions in a busy street scene make ETH a challenging dataset. We achieve competitive results with lower identity switches on this dataset as compared to the state of the art methods.

Offline handwritten text recognition is a very challenging problem. Aside from the large variation of different handwriting styles, neighboring characters within a word are usually connected, and we may need to segment a word into individual characters for accurate character recognition. Many existing methods achieve text segmentation by evaluating the local stroke geometry and imposing constraints on the size of each resulting character, such as the character width, height and aspect ratio. These constraints are well suited for printed texts, but may not hold for handwritten texts. Other methods apply holistic approach by using a set of lexicons to guide and correct the segmentation and recognition. This approach may fail when the lexicon domain is insufficient. In this paper, we present a new global non-holistic method for handwritten text segmentation, which does not make any limiting assumptions on the character size and the number of characters in a word. Specifically, the proposed method finds the text segmentation with the maximum average likeliness for the resulting characters. For this purpose, we use a graph model that describes the possible locations for segmenting neighboring characters, and we then develop an average longest path algorithm to identify the globally optimal segmentation. We conduct experiments on real images of handwritten texts taken from the IAM handwriting database and compare the performance of the proposed method against an existing text segmentation algorithm that uses dynamic programming.

Reliably measuring the similarity of two shapes or images (instances) is an important problem for various computer vision applications such as classification, recognition, and retrieval. While pairwise measures take advantage of the geometric differences between two instances to quantify their similarity, recent advances use relationships among the population of instances when quantifying pairwise measures. In this paper, we propose a novel method which refines pairwise similarity measures using population cues by examining the most similar instances shared by the compared shapes or images. We then use this refined measure to organize instances into disjoint components that consist of similar instances. Connectivity is then established between components to avoid hard constraints on what instances can be retrieved, improving retrieval performance. To evaluate the proposed method we conduct experiments on the well-known MPEG-7 and Swedish Leaf shape datasets as well as the Nister and Stewenius image dataset. We show that the proposed method is versatile, performing very well on its own or in concert with existing methods.

Segmentation propagation, similar to tracking, is the problem of transferring a segmentation of an image to a neighboring image in a sequence. This problem is of particular importance to materials science, where the accurate segmentation of a series of 2D serial-sectioned images of multiple, contiguous 3D structures has important applications. Such structures may have distinct shape, appearance, and topology, which can be considered to improve segmentation accuracy. For example, some materials images may have structures with a specific shape or appearance in each serial section slice, which only changes minimally from slice to slice, and some materials may exhibit specific inter-structure topology that constrains their neighboring relations. Some of these properties have been individually incorporated to segment specific materials images in prior work. In this paper, we develop a propagation framework for materials image segmentation where each propagation is formulated as an optimal labeling problem that can be efficiently solved using the graph-cut algorithm. Our framework makes three key contributions: 1) a homomorphic propagation approach, which considers the consistency of region adjacency in the propagation; 2) incorporation of shape and appearance consistency in the propagation; and 3) a local non-homomorphism strategy to handle newly appearing and disappearing substructures during this propagation. To show the effectiveness of our framework, we conduct experiments on various 3D materials images, and compare the performance against several existing image segmentation methods.

Both appearance and shape play important roles in object localization and object detection. In this paper, we propose a new superedge grouping method for object localization by incorporating both boundary shape and appearance information of objects. Compared with the previous edge grouping methods, the proposed method does not subdivide detected edges into short edgels before grouping. Such long, unsubdivided superedges not only facilitate the incorporation of object shape information into localization, but also increase the robustness against image noise and reduce computation. We identify and address several important problems in achieving the proposed superedge grouping, including gap filling for connecting superedges, accurate encoding of region-based information into individual edges, and the incorporation of object-shape information into object localization. In this paper, we use the bag of visual words technique to quantify the region-based appearance features of the object of interest. We find that the proposed method, by integrating both boundary and region information, can produce better localization performance than previous subwindow search and edge grouping methods on most of the 20 object categories from the VOC 2007 database. Experiments also show that the proposed method is roughly 50 times faster than the previous edge grouping method.

In this paper, we propose two new, perceptually motivated strategies to better measure the similarity of 2D shape instances that are in the form of closed contours. The first strategy handles shapes that can be decomposed into a base structure and a set of inward or outward pointing “strand” structures, where a strand structure represents a very thin, elongated shape part attached to the base structure. The similarity of two such shape contours can be better described by measuring the similarity of their base structures and strand structures in different ways. The second strategy handles shapes that exhibit good bilateral symmetry. In many cases, such shapes are invariant to a certain level of scaling transformation along their symmetry axis. In our experiments, we show that these two strategies can be integrated into available shape matching methods to improve the performance of shape classification on several widely-used shape data sets.

Object localization in an image is usually handled by searching for an optimal subwindow that tightly covers the object of interest. However, the subwindows considered in previous work are limited to rectangles or other specified, simple shapes. With such specified shapes, no subwindow can cover the object of interest tightly. As a result, the desired subwindow around the object of interest may not be optimal in terms of the localization objective function, and cannot be detected by a subwindow search algorithm. In this paper, we propose a new graph-theoretic approach for object localization by searching for an optimal subwindow without pre-specifying its shape. Instead, we require the resulting subwindow to be well aligned with edge pixels that are detected from the image. This requirement is quantified and integrated into the localization objective function based on the widely-used bag of visual words technique. We show that the ratio-contour graph algorithm can be adapted to find the optimal free-shape subwindow in terms of the new localization objective function. In the experiment, we test the proposed approach on the PASCAL VOC 2006 and VOC 2007 databases for localizing several categories of animals. We find that its performance is better than the previous efficient subwindow search algorithm.