Efficient algorithms for subwindow search in object detection and localization

Recently, a simple yet powerful branch-and-bound method called Efficient Subwindow Search (ESS) was developed to speed up sliding window search in object detection. A major drawback of ESS is that its computational complexity varies widely from O(n²) to O(n⁴) for n × n matrices. Our experimental experience shows that the ESS's performance is highly related to the optimal confidence levels which indicate the probability of the object's presence. In particular, when the object is not in the image, the optimal subwindow scores low and ESS may take a large amount of iterations to converge to the optimal solution and so perform very slow. Addressing this problem, we present two significantly faster methods based on the linear-time Kadane's Algorithm for 1D maximum subarray search. The first algorithm is a novel, computationally superior branchand- bound method where the worst case complexity is reduced to O(n³). Experiments on the PASCAL VOC 2006 data set demonstrate that this method is significantly and consistently faster (approximately 30 times faster on average) than the original ESS. Our second algorithm is an approximate algorithm based on alternating search, whose computational complexity is typically O(n²). Experiments shows that (on average) it is 30 times faster again than our first algorithm, or 900 times faster than ESS. It is thus wellsuited for real time object detection.

Marine object detection using background modelling and blob analysis

Monitoring marine object is important for understanding the marine ecosystem and evaluating impacts on different environmental changes. One prerequisite of monitoring is to identify targets of interest. Traditionally, the target objects are recognized by trained scientists through towed nets and human observation, which cause much cost and risk to operators and creatures. In comparison, a noninvasive way via setting up a camera and seeking objects in images is more promising. In this paper, a novel technique of object detection in images is presented, which is applicable to generic objects. A robust background modelling algorithm is proposed to extract foregrounds and then blob features are introduced to classify foregrounds. Particular marine objects, box jellyfish and sea snake, are successfully detected in our work. Experiments conducted on image datasets collected by the Australian Institute of Marine Science (AIMS) demonstrate the effectiveness of the proposed technique.

Robust object detection under partial occlusion

This thesis focuses on the problem of object detection under partial occlusion in complex scenes through exploring new bottom-up and top-down detection models to cope with object discontinuities and ambiguity caused by partial occlusion and allow for a more robust and adaptive detection of varied objects from different scenes.

Object extraction using genetic algorithms and morphological processing

This paper introduces a novel methodology for object detection using genetic algorithms and morphological processing. The method employs a kind of object oriented structuring element, which are derived using genetic algorithm operating. The population of morphological filters iteratively evaluated according to a statistical performance index corresponding to object extraction ability, and evolves into an optimal structuring elements using the evolution principles of genetic search. Experimental results of object extraction in high resolution satellite images are presented to illustrate the merit and feasibility of the proposed method.

Detection of vehicles with monolithic classifier vis-à-vis a boosted cascaded classifier

This paper describes the comparison of accuracy and performance of two machine learning approaches for visual object detection and tracking vehicles, from an on-road image sequence. The first is a neural network based approach. Where an algorithm of multi resolution technique based on Haar basis functions was used to obtain an image with different scales. Thereafter a classification was carried out with the multilayer feed forward neural network. Principle Component Analysis (PCA) technique was used as a dimension reduction technique to make the classification process much more efficient. The second approach is based on boosting which also yields very good detection rates. In general, boosting is one of the most important developments in classification methodology. It works by sequentially applying a classification algorithm to reweighed versions of the training data, followed by taking a weighted majority vote of the sequence of classifiers thus produced. For this work, a strong classifier was trained by the adaboost algorithm. The results of comparing the two methodologies visà-vis shows the effectiveness of the methods that have been used.

Real-time detection of parked vehicles from multiple image streams

We present a system to detect parked vehicles in a typical commercial parking complex using multiple streams of images captured through IP connected devices. Compared to traditional object detection techniques and machine learning methods, our approach is significantly faster in detection speed in the presence of multiple image streams. It is also capable of comparable accuracy when put to test against existing methods. And this is achieved without the need to train the system that machine learning methods require. Our approach uses a combination of psychological insights obtained from human detection and an algorithm replicating the outcomes of a SVM learner but without the noise that compromises accuracy in the normal learning process. The result is faster detection with comparable accuracy. Our experiments on images captured from a local test site shows very promising results for an implementation that is not only effective and low cost but also opens doors to new parking applications when combined with other technologies.

Visual mouse : SIFT detection and PCA recognition

The paper presents the Visual Mouse (VM), a novel and simple system for interaction with displays via hand gestures. Our method includes detecting bare hands using the fast SIFT (Scale-Invariant Feature Transform) algorithm saving long training time of the Adaboost algorithm, tracking hands based on the CAMShift algorithm, recognizing hand gestures in cluttered background via Principle Components Analysis (PCA) without extracting clear-cut hand contour, and defining simple and robustly interpretable vocabularies of hand gestures, which are subsequently used to control a computer mouse. The system provides a fast and simple interaction experience without the need for more expensive hardware and software.

Detection of dynamic background due to swaying movements from motion features

Dynamically changing background (dynamic background) still presents a great challenge to many motion-based video surveillance systems. In the context of event detection, it is a major source of false alarms. There is a strong need from the security industry either to detect and suppress these false alarms, or dampen the effects of background changes, so as to increase the sensitivity to meaningful events of interest. In this paper, we restrict our focus to one of the most common causes of dynamic background changes: 1) that of swaying tree branches and 2) their shadows under windy conditions. Considering the ultimate goal in a video analytics pipeline, we formulate a new dynamic background detection problem as a signal processing alternative to the previously described but unreliable computer vision-based approaches. Within this new framework, we directly reduce the number of false alarms by testing if the detected events are due to characteristic background motions. In addition, we introduce a new data set suitable for the evaluation of dynamic background detection. It consists of real-world events detected by a commercial surveillance system from two static surveillance cameras. The research question we address is whether dynamic background can be detected reliably and efficiently using simple motion features and in the presence of similar but meaningful events, such as loitering. Inspired by the tree aerodynamics theory, we propose a novel method named local variation persistence (LVP), that captures the key characteristics of swaying motions. The method is posed as a convex optimization problem, whose variable is the local variation. We derive a computationally efficient algorithm for solving the optimization problem, the solution of which is then used to form a powerful detection statistic. On our newly collected data set, we demonstrate that the proposed LVP achieves excellent detection results and outperforms the best alternative adapted from existing art in the dynamic background literature.

Learning to detect texture objects by artificial immune approaches

This paper introduces a novel method to detect texture objects from satellite images. First, a hierarchical strategy is developed to extract texture objects according to their roughness. Then, an artificial immune approach is presented to automatically generate segmentation thresholds and texture filters, which are used in the hierarchical strategy. In this approach, texture objects are regarded as antigens, and texture object filters and segmentation thresholds are regarded as antibodies. The clonal selection algorithm inspired by human immune system is employed to evolve antibodies. The population of antibodies is iteratively evaluated according to a statistical performance index corresponding to object detection ability, and evolves into the optimal antibody using the evolution principles of the clonal selection. Experimental results of texture object detection on satellite images are presented to illustrate the merit and feasibility of the proposed method.

Efficient subwindow search with submodular score functions

Subwindow search aims to find the optimal subimage which maximizes the score function of an object to be detected. After the development of the branch and bound (B&B) method called Efficient Subwindow Search (ESS), several algorithms (IESS [2], AESS [2], ARCS [3]) have been proposed to improve the performance of ESS. For nn images, IESS's time complexity is bounded by O(n³) which is better than ESS, but only applicable to linear score functions. Other work shows that Monge properties can hold in subwindow search and can be used to speed up the search to O(n³), but only applies to certain types of score functions. In this paper we explore the connection between submodular functions and the Monge property, and prove that sub-modular score functions can be used to achieve O(n³) time complexity for object detection. The time complexity can be further improved to be sub-cubic by applying B&B methods on row interval only, when the score function has a multivariate submodular bound function. Conditions for sub-modularity of common non-linear score functions and multivariate submodularity of their bound functions are also provided, and experiments are provided to compare the proposed approach against ESS and ARCS for object detection with some nonlinear score functions.

Exploiting monge structures in optimum subwindow search

Optimum subwindow search for object detection aims to find a subwindow so that the contained subimage is most similar to the query object. This problem can be formulated as a four dimensional (4D) maximum entry search problem wherein each entry corresponds to the quality score of the subimage contained in a subwindow. For n x n images, a naive exhaustive search requires O(n⁴) sequential computations of the quality scores for all subwindows. To reduce the time complexity, we prove that, for some typical similarity functions like Euclidian metric, χ² metric on image histograms, the associated 4D array carries some Monge structures and we utilise these properties to speed up the optimum subwindow search and the time complexity is reduced to O(n³). Furthermore, we propose a locally optimal alternating column and row search method with typical quadratic time complexity O(n²). Experiments on PASCAL VOC 2006 demonstrate that the alternating method is significantly faster than the well known efficient subwindow search (ESS) method whilst the performance loss due to local maxima problem is negligible.

Recognising and monitoring high-level behaviours in complex spatial environments

The recognition of activities from sensory data is important in advanced surveillance systems to enable prediction of high-level goals and intentions of the target under surveillance. The problem is complicated by sensory noise and complex activity spanning large spatial and temporal extents. This paper presents a system for recognising high-level human activities from multi-camera video data in complex spatial environments. The Abstract Hidden Markov mEmory Model (AHMEM) is used to deal with noise and scalability The AHMEM is an extension of the Abstract Hidden Markov Model (AHMM) that allows us to represent a richer class of both state-dependent and context-free behaviours. The model also supports integration with low-level sensory models and efficient probabilistic inference. We present experimental results showing the ability of the system to perform real-time monitoring and recognition of complex behaviours of people from observing their trajectories within a real, complex indoor environment.

Neighborhood coherence and edge based approaches to film scene extraction

In order to enable high-level semantics-based video annotation and interpretation, we tackle the problem of automatic decomposition of motion pictures into meaningful story units, namely scenes. Since a scene is a complicated and subjective concept, we first propose guidelines from film production to determine when a scene change occurs in film. We examine different rules and conventions followed as part of Film Grammar to guide and shape our algorithmic solution for determining a scene boundary. Two different techniques are proposed as new solutions in this paper. Our experimental results on 10 full-length movies show that our technique based on shot sequence coherence performs well and reasonably better than the color edges-based approach.

Processing multiple image streams for real-time monitoring of parking lots

We present a system to detect parked vehicles in a typical parking complex using multiple streams of images captured through IP connected devices. Compared to traditional object detection techniques and machine learning methods, our approach is significantly faster in detection speed in the presence of multiple image streams. It is also capable of comparable accuracy when put to test against existing methods. And this is achieved without the need to train the system that machine learning methods require. Our approach uses a combination of psychological insights obtained from human detection and an algorithm replicating the outcomes of a SVM learner but without the noise that compromises accuracy in the normal learning process. Performance enhancements are made on the algorithm so that it operates well in the context of multiple image streams. The result is faster detection with comparable accuracy. Our experiments on images captured from a local test site shows very promising results for an implementation that is not only effective and low cost but also opens doors to new parking applications when combined with other technologies.

A hybrid approach for multiple particle tracking microrheology

Geometric object detection has many applications, such as in tracking. Particle tracking microrheology is a technique for studying mechanical properties by accurately tracking the motion of the immersed particles undergoing Brownian motion. Since particles are carried along by these random undulations of the medium, they can move in and out of the microscope's depth of focus, which results in halos (lower intensity). Two-point particle tracking microrheology (TPM) uses a threshold to find those particles with peak, which leads to the broken trajectory of the particles. The halos of those particles which are out of focus are circles and the centres can be accurately tracked in most cases. When the particles are sparse, TPM will lose certain useful information. Thus, it may cause inaccurate microrheology. An efficient algorithm to detect the centre of those particles will increase the accuracy of the Brownian motion. In this paper, a hybrid approach is proposed which combines the steps of TPM for particles in focus with a circle detection step using circular Hough transform for particles with halos. As a consequence, it not only detects more particles in each frame but also dramatically extends the trajectories with satisfactory accuracy. Experiments over a video microscope data set of polystyrene spheres suspended in water undergoing Brownian motion confirmed the efficiency of the algorithm.