Detection of human carrying baggage from video sequences 1

4.1 Background modeling

One of the important processes for extracting candidate object regions is to construct a background model. It is used for subtracting the frames in order to separate foreground and background pixels. The subtraction procedure is generally applied with the Gaussian Mixture Model (GMM) method, but it requires a high computational cost due to complexity of process with training stage [9, 10]. Therefore, a simple background model based on statistic is applied. First, the statistical data on each pixel are computed over N previous frame indexes. Suppose I (x, y) = {I₁ (x, y) , …, I _N  (x, y)} be set of pixel brightness values (e.g. gray intensity) on the location (x, y). The maximum and minimum pixel values, I _H  (x, y) and I _L  (x, y) on this location are then calculated. These values are considered for updating the background model. It is observed that if this location only contains background pixels, the color difference between maximum and minimum intensity values of the pixel should be low enough. In this case, the value of this pixel should be used for updating the background model. In contrary, the pixel is considered as containing foreground. Pixels with maximum and minimum brightness values are represented as vector (r _max , g _max , b _max ) and (r _min , g _min , b _min ), respectively. Here, a color difference is calculated as a distance in the 3D color space [11] and if difference is below a threshold δ _d , then the background model is modified by as B t + 1 = ( 1 - β ) B t + β I H + I L 2(1) where B _t is the current background model, B_t+1 is the new background model and β < 1 is the learning rate defining how the new values affect the current background model. If the new objects appear in the video sequence, they will be smoothly blended to the background model.

Foreground/Background segmentation is straightforward using intensity difference, D (x, y) between current frame I _t  (x, y) and background model B (x, y) in certain pixel location, (x, y). General background segmentation methods utilizes single thresholding to decide whether the pixel is either foreground or background. In contrast, inspired with canny edge detector, the utilization of double threshold values, small and large thresholds, T _s and T _l , is introduced. Technically, if the difference value is more than a large threshold, the pixel is classified as foreground. If the difference value is located between small and large thresholds and its 8-neighborhood pixels are foregrounds, the pixel is classified as foreground. Otherwise, the pixel is classified as background. Mathematically, this process is defined as: L ( x , y ) = { 1 if D ( x , y ) ≥ T l 1 if T s ≤ D ( x , y ) ≤ T l ∧ M ≥ 5 0 otherwise(2) where D (x, y) = |I _t  (x, y) - B (x, y) |, and M is the number of neighborhood pixels that belong to foreground pixels.

In order to verify whether the foreground object is human or not, a learning framework for human model is developed. It is also useful to filter out non human foreground regions due to imperfect background/foreground segmentation. First, the connected component labeling was applied on the L binary maps for localizing the candidate regions. In preliminary of verification stage, the histogram of oriented gradient (HOG) features [12] are extracted on each candidate region by firstly re-sizing regions into 128 × 64 pixels size [13]. The HOG features are computed on a dense grid of cells using local contrast normalization on overlapping blocks. A nine-bin histogram of unsigned pixel oriented weighted by magnitude is created for each cell. These histograms are normalized over each overlapping block. The components of the feature vector are the values from the histogram of each normalized cell. After extracting HOG features, the support vector machine is employed to train the human model. Finally, each verified foreground human region is further analyzed for the possibility existence of baggage, otherwise the region would be eliminated.

6.1 Pixel-level feature maps

In this section, feature extraction based on scalable histogram of oriented gradient (SHOG) [15] is implemented. In most feature extraction method, the region should be resized equal to template size in order to obtain same feature dimension for each region. However, resizing region might cause losing of the local information, especially scale up process due to interpolation problem of pixel value. In contrast, fixed-length SHOG feature could be obtained from region regardless of pixel size, so it contains more rich local information which allows extracting high-discriminated features. First, Sobel operator [16] computes intensity gradient values in x and y direction, respectively, G x = I ⊗ [ - 1 0 + 1 - 2 0 + 2 - 1 0 + 1 ](3)G y = I ⊗ [ + 1 + 2 + 1 0 0 0 - 1 - 2 - 1 ](4) and then magnitude M and gradient orientation θ, are computed as following formula M = G x 2 + G y 2 and θ = arctan ( G y G x )(5) where I is an input image, ⊗ is the convolution operation. Second, the image intensity gradient is divided into feature maps based on per-pixel orientation. Adopted from standard HOG [12], nine feature maps of oriented gradients are constructed in which each maps corresponds to 20 degrees for construction the feature.

SHOG is extracted by aggregating per-pixel feature maps of oriented gradient within block from 2 × 2 to 16 × 16 block sizes with increment of 2. Different block size will accumulate different number of pixels within block. For example, if input image of 64 × 64 pixel sizes is divided into 2 × 2 block sizes, each block contains 32 × 32 pixels. However, if it is divided into 4 × 4 block sizes, each block will have 16 × 16 pixels. The final feature vector is obtained by combining the average magnitude values within block on each feature maps of oriented gradient and normalizing them using the L₂-Norm [17]. Finally, the feature vector has 5,256 elements (584 blocks × 9 elements/block). From these processes, it can be ascertained that feature dimension is always fixed, regardless of the input image size. All histograms for each block sizes are concatenated into one histogram, named SHOG [15].

Algorithm 1 GA-based sub-feature selection

1: generaten initial chromosomes

2: compute fitness value of each chromosome

3: sort fitness value with descending order

4: repeat

5:   fori ← 1 to kdo

6:   Select randomly chromosomes p₁, p₂

7:   offspring _i  ← crossover (p₁, p₂)

8:   offspring _i  ← mutation (offspring _i )

9:   Compute fitness value of offspring _i

10:  end for

11:  mergek offspring to population

12:  sortn + k chromosomes

13:  removek worst chromosomes

14: until (fixed number iteration)

6.3 Genetic algorithm-based feature selection

In many classification process, a high dimensional feature may cause an expensive computational cost. In addition, some data in certain dimension may not be very useful for distinguishing object class. Therefore, the feature dimension reduction based on a genetic algorithm (GA) approach [18] is carried out in order to reduce computational cost, but the recognition rate is still promising.

The general framework of GA can be seen at Algorithm 1. As initial population, n chromosomes with l genes are randomly created, where each gene represents the feature index. The fitness value of each chromosome is computed based on the detection rate of the nearest cluster neighbor classifier [19]. The chromosomes are sorted out based on their fitness value. The chromosome parents are taken from the chromosomes with high fitness values in the population. Hereafter, k-offspring are generated using the crossover and mutation process. These new offspring are merged to the population, whilek-chromosomes with the worst values are removed from the population.

The crossover process selects one random pivot point for generating a new offspring from recombination of sub-chromosomes of the first and the second parents. If it is lower than a fixed threshold, a new offspring is formed by combining the left part of the first parent and the right part of the second parent and vice verse. In contrary, the mutation process is performed based on probability of a random number. If the random number is larger the predefined threshold, one randomly selected gen of new offspring is replaced with a gen from the original feature of the first parent. To be noted that the picked gen should not already exist in the mutated offspring.

7.1 Support vector machine

Support Vector Machine classifier [20, 21] is used to learning of component as a weak classifier. Formally, given some training data D = { ( x i , y i ) } | x i ∈ R p , y i ∈ { - 1 , 1 } } i = 1 n, where the y _i is either 1 or -1, indicating the class to which feature x _i belongs. In our task, y _i  = 1 can be considered as either body part or baggage, and y _i  = -1 is classified as background. Each x _i is a p-dimensional real vector. Our goal is to find the maximum-margin dividing points among two classes. Any hyperplane can be written as the set of points x satisfying w ^T x - b = 0, where w the normal vector to the hyperplane. The parameter b ∥ w ∥ determines the offset of the hyperplane from the origin along the normal vector. By assuming our training data are linearly separable, two hyperplanes that separate the data are determined. These hyperplanes can be described by the equation w ^T x - b ≥ 1 and w ^T x - b ≤ -1 according two classes of data. By using geometry, the distance between these two hyperplane is 2 ∥ w ∥. To maximize the distance, the denominator ∥w∥ should be minimized. Thus, the optimization problem is formulated asfollow

min 1 2 ∥ w ∥ 2 s . t . y i ( w T x + b ) ≥ 1(6)

Finally, The output probability of SVM classification is computed by Φ ( x ) = P ( y = 1 | x ) = 1 1 + exp ( - h ( x ) )(7) where h (x) is the signed distance of feature vector x to the margin of the SVM model.

Algorithm 2 Boosting Algorithm

1: fort = 1, …, Tdo

2:  Compute empirical error of part classifier t,

3:  ɛ t = ∑ i = 1 n D t ( i ) [ pos ≠ Φ t ( x i , y i , l i , p i ) ]

4:  Ifɛ _t  ≥ 1/2 Then Stop

5:  Setr t = ∑ i = 1 N D t ( i ) Φ t ( x i , y i , l i , p i )

6:  Setω t = 1 2 log ( 1 + r t 1 - r t )

7:  SetD t + 1 ( i ) = D t ( i ) exp ( - ω t Φ t ( x i , y i , l i , p i ) ) 2 ɛ t ( 1 - ɛ t )

8: end for

Boosting is an approach to machine learning based on the idea of constructing a highly accurate classifier by combining many relatively weak and inaccurate classifiers. Here, the output probability of SVM over body and baggage components are considered as weak classifiers. Formally, the component is represented by c _i  = {x, y, s, v}, where specifying an anchor position (x, y) relative to full body in the s ^th scale of image and feature vector v. The score of component interpolation for model m based on hybrid of boosting [22] is defined as follows J ( m ) = ∑ i = 1 N ω i φ i ( x , y , s , v )(8) where ω _i is the weighting, ω _i  > 0 and φ _i is the output probability of classifier of the component c _i , N is the number of components, which are used for current classifier. The results of each kind of component are then clustered into each group for combining component processes. These weighting values are determined by using boosting machine.

There have been many boosting methods to find the weighting value of linear combination of several classifiers. One of the simplest and the most efficient is Adaptive Boosting [23]. Given the training data (x₁, y₁, l₁, p₁) , …, (x _n , y _n , l _n , p _n ), where n is the number of training samples. First, the weighting factor of each data is set to be D₁ (i) =1/n. The AdaBoost method is then performed as shown in Algorithm 2.

The human-baggage region detection is decided based on the score for each model according to the best possible placement of baggage and other components relative to body region. Let M be the number of possible models trained in the framework. The final score of object hypothesis being human-baggage object is the model which has the highest score values comparing to other models that formulated as Equation (9). In addition, if the value of J _final is less than a fixed threshold, the object hypothesis is classified as other object which represents either human without baggage or non-human regions. J final = max m 1 , . . . , m M ( J ( m 1 ) , J ( m 2 ) , . . . , J ( m M ) )(9)

The procedure from subsection 7.3 usually obtains multiple overlapping bounding boxes of human-baggage regions. Therefore, it is necessary to combine these regions for unifying detection and rejecting misdetections. A greedy procedure is used for eliminating repeated detection in the same region via non-maximum suppression [2]. Given a set of detection J which each detection is defined by a bounding box location and a score. The detection in J is then sorted by score, and the final detection is determined by choosing the highest scoring ones and skipping the detection with bounding box that are at least covered by previously selected bounding box.

8.1 Datasets

Our model was tested on human-baggage dataset, collected from subset of iLIDS [24], PETS2006 [25] and our own images. The dataset is divided into two groups, training and testing video sequences. The training video contains 976 image frames containing 162 human-baggage (positive samples) and 542 human without baggage regions (negative samples). For training of the spatial model, the human-baggage region samples are cropped manually into four components: head, body, leg, and baggage. The testing video contains 1,657 image frames containing 252 human-baggage and 672 human without baggage regions. Figure 4 shows several positives samples of our dataset used in our training.

8.2 Parameter selection in background modeling

The optimal parameter values were found by conducting experiment using a training video and were cross-validated using a testing video. Figure  5 depicts evaluation results of training and validation stages using six-best different parameter settings over training dataset. The results are calculated from human verification accuracy on the foreground segmentation stage. Based on the results, it is found that if the learning rate is set more than 0.5, the background modeling is updated faster. In this case, the stationary persons who remain on the scene within a short time period are blended as background and could not be considered as candidate regions of human carrying baggage. In consequence, the accuracy of system will decrease. On the other hand, if the learning rate is set too low, the background modeling is updated very slowly. In this case, the static objects on the scene could be detected as foreground for a longer time. Thus, our method could produce many false regions. Selecting different T _s and T _l also affects the accuracy. If a large threshold T _l is getting smaller, the model produces more foreground objects. Because of this, the false regions lead the human verification stage fails to extract candidate regions. In contrast, a bigger value of T _l will decrease detected moving objects. Finally, the optimal parameters were found as follows: (1) A background modeling was updated with rate β = 0.3 and the foreground segmentation was applied using small and large thresholds, T _s  = 50 and T _l  = 75.

8.3 Optimal feature selection analysis

This part evaluates the effect of feature selection based on genetic algorithm. Each component is modeled as binary classification, e.g head or non-head. The fitness value of each component and the average of fitness values for all components are calculated. For evaluating the effectiveness feature selection using genetic algorithm, the following two issues are investigated: (1) the effect of crossover and mutation probability, and (2) the effect of percentage of feature dimension. The summary of evaluation results can be seen in Fig. 6. As shown in Fig. 6(a), small crossover and mutation probabilities give a better fitness value. The optimal average fitness value is obtained when the crossover and mutation probabilities are set equal to 0.2 and 0.2, respectively. In addition, the number of iterations is linear with the average fitness value. In the other word, the fitness value is getting better when number of iterations is higher. Next, the percentage of feature dimension is investigated to obtain optimal dimension size which gives a good accuracy as well as a fast processing time. As seen in Fig. 6(b), when the percentage values are set between 1% and 20%, the fitness values are increased significantly, but this significant improvement does not occur after 20%. The fitness values between 20% and 50% dimension size are almost constant. Thus, it can be concluded that 20% dimension size is good enough for representing full dimension of feature. In training evaluation, 20% and full dimension sizes achieve 95.18% and 96.71% in accuracy, respectively, with different only around 2%. However, a 20% dimension size could perform faster classification process. Thus, for full implementation, the 20% feature dimension is used and it is compared with full dimension in term of accuracy and processing time.

8.4 Detection results

First, our model was evaluated for classifying the regions into either human with or without baggage. The human carrying baggage regions are set to be positive samples. Human without baggage region are set to be negative samples. All samples are collected manually and are cropped to fit object region and annotated their components based on our model. The method achieves detection rate of 0.56 and 0.58 for training and testing data, respectively. Figure 7 shows the result of our model for detecting either human or human with baggage. The proposed method achieves detection rate of 58.12% when background modeling was applied and 52.02% with sliding window only. These results outperform HOG+SVM [12], LBP+SVM [26], and HOG+LBP+SVM [27] with detection rate 39.31%, 39.93%, and 41.22%, respectively.

Next, our method was evaluated on the full video sequences. In practical implementation, the same human-baggage region is usually detected several times as overlapped bounding boxes. Therefore, it is necessary to combine the overlapped regions for unifying detection and rejecting missdetection. The detected regions are grouped based on their position, and prediction probability (score), as described in Subsection 7.4. Some typical results from the proposed method are depicted in Fig. 8.

8.5 Processing time analysis

The specification of computer for implementing the proposed approach was Intel i7-4770 CPU (3.40 GHz), 8 GB RAM. The system was implemented using C++ and OpenCV under windows 7 operating system. OpenCV was used for basic image processing. The processing speed of the proposed approach was examined on three video sequences of iLIDS datasets. The frame is resized into 640 × 480 pixels. As show in Table 1, our approach could perform on 6 fps for full feature dimension. The fastest process was obtained in background modeling and foreground segmentation as these stages only apply statistical information without performing any learning model. On the other hand, The most expensive part is the component detection on the human region. Our model contains four different components such as head, body, leg and baggage components. Each component model localizes its position in difference scales and translations.

Next, the effect of feature selection in processing time was investigated. As shown in Table 2, the proposed approach with 20% feature dimension size is almost 5 times faster than using full size of feature dimension. It performs average processing times as much as 40.12 ms, while using full dimension the average processing time is around 176.54 ms. However, the accuracy difference between them is only 7%. Thus, the genetic algorithm-based feature selection gains a good improvement in term of processing time while still maintaining the accuracy of detection. Furthermore, the method was also evaluated using sliding window approach without background modeling. The accuracy is promising, but it requires a long processing time and is almost 5 times slower than the proposed approach.