Vadim Kantorov

Ivan Laptev

Efficient feature extraction, encoding and classification for action recognition

Local video features provide state-of-the-art performance for action recognition. While the accuracy of action recognition has been continuously improved over the recent years, the low speed of feature extraction and subsequent recognition prevents current methods from scaling up to real-size problems. We address this issue and first develop highly efficient video features using motion information in video compression. We next explore feature encoding by Fisher vectors and demonstrate accurate action recognition using fast linear classifiers. Our method improves the speed of video feature extraction, feature encoding and action classification by two orders of magnitude at the cost of minor reduction in recognition accuracy. We validate our approach and compare it to the state of the art on four recent action recognition datasets.

Introduction

The amount of video has increased dramatically over recent years and continues to grow. Striking indications of this development include 6000 years of video uploaded to YouTube yearly 1 and millions of surveillance cameras installed only in the UK. According to Cisco 2 , video is expected to dominate Internet traffic by 91% in 2014.

The access to information in such gigantic quantities of video data requires accurate and efficient methods for automatic video analysis. Much work has been recently devoted to automatic video understanding and recognition of human actions in particular [16,[START_REF] Liu | Recognizing human actions by attributes[END_REF]22,[START_REF] Sadanand | Action bank: A high-level representation of activity in video[END_REF][START_REF] Schüldt | Recognizing human actions: a local SVM approach[END_REF][START_REF] Wang | Dense trajectories and motion boundary descriptors for action recognition[END_REF]. While the recognition accuracy has been continuously improved, current methods remain limited to relatively small datasets due to the low speed of video processing, often ranging in the order of 1-2 frames per second. This stands in a sharp contrast with the needs of large-scale video indexing and retrieval in modern video archives. Fast video recognition is also required by client applications, e.g., for automatic onthe-fly video moderation and video editing. Efficient video representations enabling fast event recognition will also foster solutions to new problems such as automatic clustering 1 http://youtube.com/t/press_statistics 2 http://newsroom.cisco.com/dlls/2010/prod_060210.html of very large video collections.

The main goal of this work is efficient action recognition. We follow the common bag-of-features action recognition pipeline [16,[START_REF] Schüldt | Recognizing human actions: a local SVM approach[END_REF][START_REF] Wang | Dense trajectories and motion boundary descriptors for action recognition[END_REF] and explore the speed and memory trade-offs of its main steps, namely, feature extraction, feature encoding and classification. Given their success for action recognition, we represent video using motion-based HOF [16] and MBH [START_REF] Wang | Dense trajectories and motion boundary descriptors for action recognition[END_REF] local descriptors. Motion estimation at dense grid, however, is a time-consuming process that limits the speed of feature extraction. In this work we avoid motion estimation and design fast descriptors using motion information from video compression. In contrast to the dense optical flow (OF), video compression provides sparse motion vectors only (we call it MPEG flow). As one contribution of this paper, we show that the use of sparse MPEG flow instead of the dense OF improves the speed of feature extraction by two orders of magnitude and implies only minor reduction in classification performance.

Feature encoding typically involves assignment of local descriptors to one or several nearest elements in a visual vocabulary. Given the large number of video descriptors, the speed of this step is a major bottleneck. We evaluate using kd-forest approximate nearest neighbor search [25] and analyze the associated trade-off between the speed and recognition accuracy. We next investigate Fisher vector (FV) encoding [START_REF] Perronnin | High-dimensional signature compression for large-scale image classification[END_REF] and show improved action recognition while using fast linear classifiers. We evaluate the speed and accuracy of our approach on Hollywood-2 [START_REF] Marszałek | Actions in context[END_REF], UCF50 [START_REF] Reddy | Recognizing 50 human action categories of web videos[END_REF], HMDB51 [START_REF] Kuehne | Hmdb: A large video database for human motion recognition[END_REF] and UT-Interaction [START_REF] Ryoo | UT-Interaction Dataset[END_REF] benchmarks. The implementation of out method is available at [7].

The rest of the paper is organized as follows. After reviewing related work in Section 2 we address efficient extraction of local video features in Section 3. Section 4 describes our fast video encoding. Section 5 presents experimental results.

Related work

Recent methods show significant progress towards action recognition in realistic and challenging videos from YouTube, movies and TV [16,[START_REF] Laptev | Retrieving actions in movies[END_REF][START_REF] Liu | Recognizing human actions by attributes[END_REF]22,[START_REF] Rodriguez | Action mach: a spatio-temporal maximum average correlation height filter for action recognition[END_REF][START_REF] Sadanand | Action bank: A high-level representation of activity in video[END_REF][START_REF] Wang | Dense trajectories and motion boundary descriptors for action recognition[END_REF]. Among other approaches, bag-of-features (BOF) methods [5, [START_REF] Laptev | On space-time interest points[END_REF][START_REF] Schüldt | Recognizing human actions: a local SVM approach[END_REF] have gained popularity due to their simplic-ity, wide range of application and high recognition accuracy. BOF methods represent actions by collections of local space-time descriptors aggregated over the video. Several alternative local descriptors have been proposed including histograms of flow orientations (HOF) [16], histograms of 3D gradients (HOG3D) [START_REF] Klaser | A spatio-temporal descriptor based on 3D-gradients[END_REF][START_REF] Scovanner | A 3-dimensional sift descriptor and its application to action recognition[END_REF], motion boundary histograms (MBH) [4,[START_REF] Wang | Dense trajectories and motion boundary descriptors for action recognition[END_REF], shapes of point trajectories [START_REF] Matikainen | Trajectons: Action recognition through the motion analysis of tracked features[END_REF][START_REF] Messing | Activity recognition using the velocity histories of tracked keypoints[END_REF][START_REF] Wang | Dense trajectories and motion boundary descriptors for action recognition[END_REF], local trinary patterns [START_REF] Kliper-Gross | Motion interchange patterns for action recognition in unconstrained videos[END_REF][START_REF] Yeffet | Local Trinary Patterns for human action recognition[END_REF] and others. Mid-level features such as action attributes [START_REF] Liu | Recognizing human actions by attributes[END_REF] and action bank [START_REF] Sadanand | Action bank: A high-level representation of activity in video[END_REF] have also been explored. Recent evaluation [START_REF] Wang | Dense trajectories and motion boundary descriptors for action recognition[END_REF] demonstrates that MBH, HOF and HOG descriptors sampled along dense point trajectories outperform other methods on a number of challenging datasets [START_REF] Wang | Dense trajectories and motion boundary descriptors for action recognition[END_REF]. More recent extensions demonstrate improvements using motion stabilization and person trajectories [START_REF] Jain | Better exploiting motion for better action recognition[END_REF][START_REF] Wang | Action Recognition with Improved Trajectories[END_REF]. We follow [START_REF] Wang | Dense trajectories and motion boundary descriptors for action recognition[END_REF] and design a new motion-based local descriptor that drastically improves the speed of previous methods at the cost of minor decrease in the recognition accuracy.

Efficient action recognition has been addressed by several methods. The work [START_REF] Babu | Recognition of human actions using motion history information extracted from the compressed video[END_REF][START_REF] Yeo | Compressed domain real-time action recognition[END_REF][START_REF] Yeo | High-speed action recognition and localization in compressed domain videos[END_REF] is particularly related to ours as it makes use of motion information from video compression for fast action recognition. This previous work, however, designs action-specific descriptors and, hence, its speed scales linearly with the number of action classes. In contrast, we design a generic action representation and evaluate its accuracy and efficiency on many action classes in challenging settings. Yeffet and Wolf [START_REF] Yeffet | Local Trinary Patterns for human action recognition[END_REF] extend the fast LBP image descriptor to a Local Trinary Pattern (LTP) descriptor in video and evaluate its accuracy on action recognition. While LTP was claimed to run in real time, no quantitative evaluation of its speed was reported in [START_REF] Yeffet | Local Trinary Patterns for human action recognition[END_REF]. Differently to LTP, we use flow-based MBH and HOF descriptors which have recently shown excellent results for action recognition [START_REF] Wang | Dense trajectories and motion boundary descriptors for action recognition[END_REF]. Yu et al. [40] have proposed another pixelbased local descriptor for efficient action recognition. We quantitatively compare our method with [40] and show improvements in both the speed and accuracy. Closely related to our work, [START_REF] Shi | Sampling strategies for real-time action recognition[END_REF] has recently improved the speed of local feature extraction in video by random feature sampling. We experimentally compare our method to [START_REF] Shi | Sampling strategies for real-time action recognition[END_REF] and show one order of magnitude improvement in speed while also demontrating improved accuracy.

Alternative schemes for feature encoding have been recently evaluated for image classification in [START_REF] Chatfield | The devil is in the details: an evaluation of recent feature encoding methods[END_REF]. Fisher vector (FV) encoding [24] has been shown to provide best accuracy using efficient linear kernels for classification. FV encoding has been successfully applied for event detection [START_REF] Revaud | Event retrieval in large video collections with circulant temporal encoding[END_REF] and we are confirming its improved performance and efficiency compared to the histogram encoding typically used in action recognition. We also investigate efficient computation of FV using approximate nearest neighbor methods for descriptor assignment. FV encoding enables high recognition accuracy using fast linear classifiers which is a big advantage for large-scale video recognition.

Contributions. The contributions of this work are the following. First, we design and thoroughly evaluate an efficient motion descriptor based on the video compression which is 100x faster to compute at a minor degradation of recognition performance compared to the state-of-theart [START_REF] Wang | Dense trajectories and motion boundary descriptors for action recognition[END_REF]. Second, to the best of our knowledge, we are the first to evaluate both efficiency and classification performance of FV and VLAD for action recognition and find it improving the recognition rates without loss in speed compared to the histogram encoding.

Efficient video features

Dense Trajectory (DT) features together with MBH and HOF descriptors achieve state-of-the-art accuracy in action recognition [START_REF] Wang | Dense trajectories and motion boundary descriptors for action recognition[END_REF] at the cost of high computational requirements. The analysis in [START_REF] Wang | Dense trajectories and motion boundary descriptors for action recognition[END_REF] indicates that most of the running time (61%) is spent on the computation of optical flow, while the second most expensive operation (36%) is aggregation of dense flow measurements into histogram descriptors (discarding the "save features to disk" part). In this paper we alleviate the expense of both of these steps by (i) reusing motion estimates available from video compression and (ii) constructing descriptors from very sparse motion measurements. In this section we first analyze the quality of motion vectors available in compressed video representations and then describe our efficient video descriptor.

Motion fields from video compression

Consequent video frames are highly redundant with most of the changes between frames typically originating from the object or camera motion. As the storage of sparse motion vectors is much more efficient compared the storage of pixel values, video compression schemes heavily rely on motion estimation and encode coarse motion information in compressed video representations such as MPEG. This motion field can be accessed at the time of video decompression without additional cost 3 .

Motion estimation by video encoders is designed to optimize video compression size and may not necessarily correspond to the true motion in the video. To verify the quality of the motion field obtained from video compression (here called MPEG flow), we compare it with the ground truth flow as well as with the output of optical flow methods by Lucas and Kanade [START_REF] Lucas | An iterative image registration technique with an application to stereo vision[END_REF] and Farnebäck [6]. We choose these two methods since they are deployed in existing implementations of local motion descriptors [16] and [START_REF] Wang | Dense trajectories and motion boundary descriptors for action recognition[END_REF] which we use in this work for comparison. Figure 1 eight orientation values and one "no-motion" bin since this representation of flow is used in this paper for the construction of our fast video descriptor. The details and measurement results are in Figure 1.

We have evaluated quantitative performance of MPEG flow in the standard Clean setup of the MPI Sintel benchmark. Despite the fact that the motion field obtained from MPEG flow has low resolution, the obtained results (EPE all=11.148 and EPE matched=6.706) outperform sev-eral methods reported on the MPI Sintel web-page http: //sintel.is.tue.mpg.de/results. Qualitatively, the level of noise in MPEG flow and optical flow estimates is comparable both for synthetic and real video examples as illustrated in Figure 2. This indicates that the substitute of the slow optical flow used in video descriptors [16,[START_REF] Wang | Dense trajectories and motion boundary descriptors for action recognition[END_REF] by the "virtually free" MPEG flow may not have large implications on the performance of subsequent recognition steps.

MPEG flow video descriptor

We follow the design of previously proposed local spacetime descriptors [16,[START_REF] Wang | Dense trajectories and motion boundary descriptors for action recognition[END_REF] and define our descriptor by histograms of MPEG flow vectors accumulated in a video patch. Each patch is divided into cells as illustrated in Figure 3 and the normalized histograms from patch cells are concatenated into a descriptor vector. Constrained by the coarse 16 × 16 pixel spatial resolution of MPEG flow, we align descriptor grid cells with positions of motion vectors (red points in Figure 3). We also use bilinear interpolation of flow and increase the spatial resolution of the flow field by the factor of two (yellow points in Figure 3) 4 .

Following [START_REF] Wang | Dense trajectories and motion boundary descriptors for action recognition[END_REF], we compute HOF descriptors as histograms of MPEG flow discretized into eight orientation bins and a no-motion bin. For MBHx and MBHy descriptors the spatial gradients of the v x and v y components of the flow are similarly discretized into nine orientation bins. The final descriptor is obtained by concatenating histograms from each cell of the 2 × 2 × 3 descriptor grid followed by l 2 -normalization of every temporal slice. HOG descriptors are computed at the same sparse set of points.

The above scheme defines a 32 × 32 × 15 pixel descriptor which we compute at every location of the video defined by the spatial stride of 16 pixels and temporal stride of 5 frames. To sample multiple spatial scales, we similarly define a 48 × 48 × 15 pixel descriptor sampled with 24 pixels spatial stride. For a video of 640 × 480 pixels spatial resolution we obtain around 300 descriptors per frame. This is comparable to ≈ 350 dense trajectory features produced by the method in [START_REF] Wang | Dense trajectories and motion boundary descriptors for action recognition[END_REF] for the same video resolution.

Main computational advantages of our descriptor originate from the elimination of the optical flow computation and from the coarse sampling of flow vectors. As we demonstrate experimentally in Section 5, these modifications imply drastic improvements of computational requirements at the cost of minor reduction in the classification performance. 4 We found interpolation of the flow to be important in our experiments

Descriptor encoding

The purpose of descriptor encoding is to transform collections of local image or video descriptors {x i . . . x N } into fixed-size vector representations. In this paper we investigate three different descriptor encoding schemes and propose their computational improvements as described below.

Histogram encoding

Histogram encoding is a common method for representing video by local descriptors. First, for each descriptor type (HOG, HOF, MBHx, MBHy) a vocabulary of K visual words is constructed using K-means. Then each descriptor is assigned to one of the visual words and the visual word indices are accumulated in a histogram. We follow [16] and use "space-time pyramid" which allows to capture the rough spatial and temporal layout of action elements. We split videos into six spatio-temporal grids (x × y × t: 1x1x1, 2x2x1, 1x3x1, 1x1x2, 2x2x2, 1x3x2, a total of 24 cells). In total we have C = 96 channels = 4 descriptor types × 24 cells, that is one channel per a pair of descriptor type and grid cell. Each cell accumulates its own histogram which is then l 1 -normalized, thus the total histogram representation is of size C • K. We also employ space-time pyramids for the Fisher vector and VLAD encoding methods described in Sections 4.2 and 4.3 respectively.

For visual word assignment we experimented with using brute-force nearest neighbors and with using the kd-trees from the FLANN library [21]. The motivation for using kd-trees is the significant improvement in processing speed over the brute-force algorithm (see Subsection 5.2). The main parameters for the kd-trees method are the number of trees and the number of tests made during the descent over trees.

Fisher Vector

Fisher Vector (FV) has been reported to consistently improve the performance in image classification and image retrieval tasks [11]. Another advantage of FV encoding over histogram encoding is it's good performance using fast linear classifiers. FV encoding assumes that descriptors are generated by a GMM model with diagonal covariance matrices. Similarly to histogram encoding, the GMM model of K Gaussians is first learned on the training set. Once the model (µ k , σ k ) is learned, the FV representation of the descriptors {x 1 . . . x N } is given by the two parts [24]: where q ki is the Gaussian soft assignment of the descriptor x i to the k-th Gaussian, π k are the mixture weights, division and square are term-by-term operations. The u part captures the first-order differences, the v part captures the secondorder differences. The final representation of size C • 2DK is given by concatenation of the two parts. As suggested in [24], we then take signed square root and l 2 -normalize the result. We apply the same normalization scheme to VLAD, described next.

u k = 1 N √ π k N i=1 q ki x i -µ k σ k v k = 1 N √ 2π k N i=1 q ki x i -µ k σ k 2 -1 (1)

VLAD

The VLAD encoding is the simplified version of Fisher vector which considers only the first-order differences and assigns descriptors to a single mixture component. It was also shown to outperform the histogram encoding in [11]. In our implementation we keep the soft-assignment factor q ki . The VLAD representation of size C • DK is then given by concatenating:

u k = i:N N (xi)=µ k q ki (x i -µ k )

Experimental evaluation

In this section we evaluate the proposed descriptor and encoding schemes on Hollywood2 [START_REF] Marszałek | Actions in context[END_REF], UCF50 [START_REF] Reddy | Recognizing 50 human action categories of web videos[END_REF], HMDB51 [START_REF] Kuehne | Hmdb: A large video database for human motion recognition[END_REF] and UT-Interaction [START_REF] Ryoo | UT-Interaction Dataset[END_REF] action recognition benchmarks (see Figure 4) and compare the speed and accuracy of action recognition to recent methods [START_REF] Shi | Sampling strategies for real-time action recognition[END_REF][START_REF] Wang | Dense trajectories and motion boundary descriptors for action recognition[END_REF]40]. We follow standard evaluation setups and report mean average precision (mAP) for Hollywood2 and mean accuracy (acc) for UCF50, HMDB51 and UT-Interaction datasets. The processing speed is reported in frames-per-second (fps), run at a single-core Intel Xeon E5345 (2.33 GHz).

To recognize actions we use SVM with multi-channel exponential χ 2 -kernel [START_REF] Zhang | Local features and kernels for classification of texture and object categories: A comprehensive study[END_REF] together with histogram-based action representations. For Fisher vector and VLAD encodings we use linear SVMs.

Descriptor evaluation Table 1 (Left) presents results of action recognition using the proposed MPEG flow (MF) features compared to

Dense Trajectories (DT) baseline [START_REF] Wang | Dense trajectories and motion boundary descriptors for action recognition[END_REF] using histogram encoding. For the full combination of four descriptors the performance of DT (∼60.0%) is approximately four per-cent higher compared to MF features (∼56.2%). When comparing the speed of feature extraction for both methods measured on videos with 640 × 480 pixels spatial resolution, our method achieves 168fps which is about 7 times faster than real-time and 140 times faster compared to [START_REF] Wang | Dense trajectories and motion boundary descriptors for action recognition[END_REF]. The speed measurements in this experiment include the time of feature computation as well as the time for video reading and decompression. Our method spends most of the time on the aggregation of histogram-based video descriptors using intergral space-time histograms. Compared to [START_REF] Wang | Dense trajectories and motion boundary descriptors for action recognition[END_REF] we save ∼66% by avoiding OF computation, ∼4% by sparser descriptor sampling and ∼29% by the aggregation of sparse motion vectors. The run-time of our descriptor is, hence, <1% of descriptor computation time in [START_REF] Wang | Dense trajectories and motion boundary descriptors for action recognition[END_REF]. Reducing the number of descriptor types increases the speed of our method to 347fps (14 times real time) at the cost of <4% drop in mAP.

DT features [START_REF] Wang | Dense trajectories and motion boundary descriptors for action recognition[END_REF] are computed along point tracks which is different to our features computed inside the fixed-size video patches. To identify the source of ∼4% mAP drop of our method compared to [START_REF] Wang | Dense trajectories and motion boundary descriptors for action recognition[END_REF], we simplify DT features by first approximating free-shape trajectories in DT features by constant velocity trajectories (DT V*). In the second simplification we remove trajectory information from DT descriptor and compute DT features in fixed axes-parallel cuboids (DT V0). The results of these modifications in the first two lines of Table 2 indicate 1% drop due to DT V* and 1% further drop in mAP due to DT V0. Explicitly including the shape of trajectories into the descriptor (last line of 58.9% HOF+MBHx+MBHy+HOG [START_REF] Wang | Dense trajectories and motion boundary descriptors for action recognition[END_REF] 60.0% HOF+MBHX+MBHY+HOG+TRAJ [START_REF] Wang | Dense trajectories and motion boundary descriptors for action recognition[END_REF] 60.3% Table 2. Action classification accuracy on Hollywood2 dataset for different versions of the dense trajectory features [START_REF] Wang | Dense trajectories and motion boundary descriptors for action recognition[END_REF] in combination with histogram encoding this experiment we conclude that the shape of trajectories does not contribute to other descriptors significantly. We believe that the difference in accuracy of DT features and our method should be in the denser and more accurate flow estimation deployed by DT. Per-class action classification comparison of MF and DT features is illustrated in Figure 5.

Descriptor encoding evaluation

While our method achieves high speed descriptor computation, the feature quantization becomes a bottle-neck with nearest-neighbor (NN) quantization performing only at the rate of 10fps when using efficient l 2 -distance implementation. To improve quantization speed, we experiment with tree-based approximate nearest neighbor (ANN) quantization schemes implemented in FLANN [21]. The trade-off between computational time and the accuracy of quantization measured on the final recognition task is illustrated in Figure 6. Notably, the quantization using four trees and 32 tests in ANN search does not degrade recognition performance and achieves factor ≈ 5x speed-up compared to NN. Further increase of the speed implies approximately linear degradation of classification accuracy.

We next investigated Fisher Vector (FV) [START_REF] Perronnin | High-dimensional signature compression for large-scale image classification[END_REF] and VLAD encodings [START_REF] Jegou | Aggregating local descriptors into a compact image representation[END_REF] described in Section 4. The VLAD encoding has already been applied to action reconition in [START_REF] Jain | Better exploiting motion for better action recognition[END_REF], but here we also evaluate the full Fisher vector. We train a GMM model with K = 256 Gaussians [11]. Results in Figure 6 and Table 4 indicate improvements in both the speed and accuracy when using FV and VLAD encodings compared to the histogram encoding. As for the histogram encoding, FLANN provides considerable speed-up for FV and VLAD encodings.

Table 5 presents action recognition results for the UCF50 dataset. Similar to the Hollywood2 dataset, the accuracy of our methods is only a few percent below the state-ofthe-art results in [START_REF] Wang | Dense trajectories and motion boundary descriptors for action recognition[END_REF] with FV and VLAD encodings providing improvements over the histogram encoding both in speed and accuracy. The overall speed improves the speed of [START_REF] Wang | Dense trajectories and motion boundary descriptors for action recognition[END_REF] by two orders of magnitude. Table 6 presents results for the UT-Interaction dataset and compares our method with the efficient action recognition method [40]. Our method demonstrates better classification accuracy compared to [40] and improves the speed of [40] by one order of magnitude.

In Table 7 we compare our results on the HMDB dataset to [START_REF] Shi | Sampling strategies for real-time action recognition[END_REF] that investigates the effect of feature sampling on the trade-off between computational efficiency and recognition performance. For the MBH descriptor our method obtains significant improvement both in speed and accuracy, despite the fact that in [START_REF] Shi | Sampling strategies for real-time action recognition[END_REF] the system was evaluated on Intel i7-3770K (3.50 GHz) which runs 1GHz faster than our Intel Xeon E5345 (2.33 GHz). Both systems were evaluated on a single core with no multithreading.

Recently, the method in [START_REF] Wang | Dense trajectories and motion boundary descriptors for action recognition[END_REF] has been further improved using motion stabilization [START_REF] Jain | Better exploiting motion for better action recognition[END_REF][START_REF] Wang | Action Recognition with Improved Trajectories[END_REF] and feature extraction from person tracks [START_REF] Wang | Action Recognition with Improved Trajectories[END_REF]. These extensions are complementary to our work and can be used to improve results of our method.

Parameter sensitivity

MPEG flow might be influenced by the types and parameters of video codecs. To investigate this aspect, we evaluate the performance of action recognition for two common video codecs (x264 and xvid) under varying video compression bit-rates. 16) ch [START_REF] Schüldt | Recognizing human actions: a local SVM approach[END_REF] ch (16) ch [START_REF] Schüldt | Recognizing human actions: a local SVM approach[END_REF] ch [START_REF] Liu | Recognizing human actions by attributes[END_REF] ch(4) ch [START_REF] Schüldt | Recognizing human actions: a local SVM approach[END_REF] ch(4) ch (16) ch [START_REF] Liu | Recognizing human actions by attributes[END_REF] ch(4) ch( 16) ch [START_REF] Schüldt | Recognizing human actions: a local SVM approach[END_REF] ch( 8 video codecs and decreasing video quality corresponding to low values of bit-rates.

We have also evaluated the influence of sparse flow sampling on the speed and accuracy of action recognition. In Table 3 we illustrate accuracy of our method when using Farneback flow and MPEG flow. Denser flow sampling (Farneback) leads to slight improvements in recognition accuracy by the cost of significantly increased computation time. Notably, sparse Farneback and MPEG flow show similar recognition performance. [START_REF] Schüldt | Recognizing human actions: a local SVM approach[END_REF] 58.2% 40.9 32.9 DT [START_REF] Wang | Dense trajectories and motion boundary descriptors for action recognition[END_REF] 59.9% 1.2 5.1 1.0 [START_REF] Wang | Dense trajectories and motion boundary descriptors for action recognition[END_REF] 48.3% 3.1

Table 7. Comparison of our method to [START_REF] Shi | Sampling strategies for real-time action recognition[END_REF] on the HMDB dataset [START_REF] Kuehne | Hmdb: A large video database for human motion recognition[END_REF]. The speed is reported for videos with the spatial resolution 360 × 240 pixels

Conclusions

We present an efficient method for extracting and encoding local video descriptors for action recognition. We show that sparse motion vectors from video compression enable accurate action recognition at reduced computational cost. We next apply and evaluate Fisher vector encoding for action recognition and demonstrate the improved speed and accuracy. Our method is fast and enables accurate action recognition using linear classifiers. Implementation of our method is available from [7].

Figure 1 .

 1 Figure 1. Comparison of optical flow estimation for a synthetic video sequence "bandage 1" from MPI Sintel dataset [2]. On the right we compare the ground truth flow with the flow obtained from DivX video compression (MPEG flow) as well as optical flow estimated with Lukas-Kanade [18] and Farnebäck [6] methods. The direction of flow vectors is quantized into eight equally distributed orientations and is color-coded according to the color-wheel on the bottom-right. White color represents no motion. The error of the flow is obtained by the ratio of incorrectly quantized flow values when compared to the ground truth and evaluated over the whole video. While the resolution of MPEG flow is lower compared to other methods, the accuracy of all three methods is comparable both quantitatively and qualitatively.

  vectors (vx,vy) Interpolated flow vectors (vx,vy) grid cell 16x16x5 pixels ~Figure 3. MPEG flow (MF) video descriptor defined at positions of MPEG flow vectors. Each 2 × 2 × 3 descriptor cell is accumulated from quantized values of original and interpolated flow vectors indicated by the red and yellow circles respectively.

Figure 4 .

 4 Figure4. Sample frames from action recognition datasets. From top to bottom: Hollywood2[START_REF] Marszałek | Actions in context[END_REF], UCF50[START_REF] Reddy | Recognizing 50 human action categories of web videos[END_REF], HMDB51[START_REF] Kuehne | Hmdb: A large video database for human motion recognition[END_REF], UT-Interaction[START_REF] Ryoo | UT-Interaction Dataset[END_REF].

) 4 Figure 6 .

 46 Figure 6. Performance of action recognition and the speed of descriptor encodings in Hollywood2 dataset for different types and parameters of encoding schemes. kd(x) indicates the number of trees x in the kd-forest used for ANN descriptor assignment. ch(y) indicates the number of tests y when descending the forest.

Table 2 )

 2 does not improve performance significantly. From

		Classification	Speed
		(mAP)	(fps)
		MF (our) DT [35] MF (our) DT [35]
	HOF	47.2%	52.9%	346.8			xvid	x264
	MBHx	49.0%	52.0%	330.3		5000 kbit/s 58.9% 57.5%
	MBHy	50.4%	56.1%	330.3		1000 kbit/s 58.2% 57.4%
	HOF+MBHx+MBHy	53.9%	58.9%	218.7		500 kbit/s	57.7% 57.1%
	HOF+MBHx+MBHy+HOG	56.2%	60.0%	168.4	1.2	250 kbit/s	57.7% 57.0%

Table 1 .

 1 Left: Evaluation of action classification accuracy and the speed of feature computation for Hollywood2 action recognition benchmark. The speed of feature computation is reported for video of spatial resolution 640×480 pixels. Right: Evaluation of action recognition accuracy in Hollywood2 under the variation of video compression in terms of video codecs and compression bit-rates. The results are reported for MF descriptors in combination with FV encoding.

		mAP
	HOF+MBHx+MBHy+HOG (V0)	58.0%
	HOF+MBHx+MBHy+HOG (V*)

Table 3 .

 3 Results in Table 1 (Right) indicate the stable performance of action recognition for different types of Action classification accuracy on Hollywood2 dataset using sparse sampling of Farneback flow and MPEG flow followed by FV feature encoding. The reported speed of feature extraction is affected by the increased computational cost of aggregating motion vectors into local descriptors.

					Farneback flow	MPEG flow
	Sampling stride	mAP	fps	mAP	fps
				16 58.3%	35.2	58.2% 168.4
				8 58.6%	24.1
				4 59.2%	13.7
			1				CD -HOF+MBHx+MBHy+HOG DT -HOF+MBHx+MBHy+HOG
	Average Precision	0.2 0.4 0.6 0.8
			0
	A n s w e r P h o n e D r iv e C a r F ig E a t h t P e r s o n G e t O u t C a r H a n d S h a k e u g P e r s o n K is s H	R u n S it D o w n S it U p S t a n d U p	A ll	.
	Figure 5. Per-class action classification results for DT [35] and our
	MF features using HOF+MBHx+MBHy+HOG descriptor combi-
	nation and histogram encoding on the Hollywood2 benchmark.
	mAP	0.56 0.57 0.58 0.59 0.6		ch(	ch(8)	NN FV noopt FLANN kd(4) FLANN kd(2) FV kd(4) VLAD kd ( )
			0.55					ch(4)
			0.54
			0 0.53	50	100	FPS	150	200	250

Table 4 .

 4 Comparison of our method to the state of the art on Hol-lywood2 dataset. The speed of[START_REF] Wang | Dense trajectories and motion boundary descriptors for action recognition[END_REF] and of our method is reported for videos with spatial resolution 640 × 480 pixels.

			Feat. Quant. Total
		Acc.	(fps)	(fps)	(fps)
	MF FLANN(4-32) 81.6%		52.4	48.1
	MF VLAD(4)	80.6%	591.8	671.4 314.6
	MF FV(32)	82.2%		171.3 132.8
	DT [35]	85.6%	2.8	5.1	1.8

Table 5 .

 5 Comparison of our method to the state of the art on the UCF50 dataset[START_REF] Reddy | Recognizing 50 human action categories of web videos[END_REF]. The speed is reported for videos with the spatial resolution 320 × 240 pixels.

		Acc.	Total FPS
	FV(32)	87.6%	99.2
	PSRM+BOST[40] 83.3%	10.0

Table 6 .

 6 Accuracy and speed of action recognition in the UTinteraction dataset[START_REF] Ryoo | UT-Interaction Dataset[END_REF].

			Feat. Quant. Total
		Acc.	(fps)	(fps)	(fps)
	MF ALL FV(32)	46.7% 455.6 129.7 101.0
	MF MBH FV(32)	45.4% 683.3 268.0 192.5
	MF ALL VLAD(32) 46.3% 455.6 455.6 227.8
	MBH [34]	41.1% 33.9	267.1	30.8
	HOG3D [34]	33.3% 49.6	290.8	42.2
	DT

Full video decompression may not be required.


Trinh Dang

Nguyen

Bao Quoc

Duong

Eric Zamai

Muhammad Kashif
email: kashif.shahzad@grenoble-inp.fr

Trinh Nguyen

Quoc-Bao Duong

Muhammad

Bayesian network model with dynamic structure identification for real time diagnosis

Keywords: Index terms-Fault diagnosis, Automated Manufacturing Systems, Logical diagnosis, Bayesian network

This paper proposes a method for real time diagnosis against product quality drifts in an automated manufacturing system. We use Logical Diagnosis model to reduce the search space of suspected equipment in the production flow, which is then formulated as a Bayesian network to compute risk priority for each equipment, using joint and conditional probabilities. The objective is to quickly and accurately localize the possible fault origins and support effective decisions on corrective maintenance. The key advantages offered by this method are (i) reduced unscheduled equipment breakdowns, and (ii) increased and stable production capacities, required for success in highly competitive and automated manufacturing systems. Moreover, this is a generic method and can be deployed on fully or semi automated manufacturing systems.

I. INTRODUCTION

Nowadays, manufacturing processes are more and more complex. One of main challenges for manufacturing domain is to improve and optimize the production process quality and equipment effectiveness during production operations. To improve product quality and reduce associated costs, fault isolation, detection and diagnosis techniques have been developed. For the fault diagnosis, many methods are proposed through a diagnosis model as presented in [START_REF] Venkatasubramanian | A review of process fault detection and diagnosis: Part I: Quantitative model-based methods[END_REF], [START_REF] Ruiz | On-line fault diagnosis system support for reactive scheduling in multipurpose batch chemical plants[END_REF] to localize more quickly and accurately the root causes of a detected failure. Theses model based methods are designed with flexibility to apply to different production systems.

However, the production system comprises of hundreds of equipment, monitored by thousands of sensors. Thus, we must analyze a large amount of production information for system control, monitoring and fault diagnosis. Generally, it is difficult to identify a diagnosis model and corresponding variables. Hence, probabilistic approaches are well suited techniques to analyze the large amount of production information and describe the behavior of system components as presented in [START_REF] Weber | Overview on Bayesian networks applications for dependability, risk analysis and maintenance areas[END_REF]. These approaches can be performed without understanding the underlying structure of a production system [START_REF] Bouaziz | Dependability of complex semiconductor systems: Learning Bayesian networks for decision support[END_REF]. Among the probabilistic approaches, the Bayesian network (BN) approach is widely used to identify a graphical structure model that describes relationships between variables in production system. So, its conditional probabilities will be calculated to provide the risk priorities and support corrective maintenance decisions. However, a difficulty of BN approaches is to identify the graphical structure during learning phase [START_REF]Data mining and knowledge discovery handbook[END_REF]. Due to the complexity of present-day manufacturing system, identification of this graphical structure is complex to be performed by a maintenance engineer [START_REF] Bouaziz | Dependability of complex semiconductor systems: Learning Bayesian networks for decision support[END_REF]. Moreover, a production system depends on the products, recipes, equipment, maintenance and human factors. These elements are frequently changed due to the introduction of new production technologies and maintenance management philosophies. A change in one element may trigger effect to others. For example, to manufacture a new product, the corresponding technology, recipe, equipment, human factors may change. Consequently, we need to retrain the learning step of BN model to adapt with newly emerging situations of the production system. The time and workload for computation are very large, so that results in poor maintenance and additional costs.

Consequently, this paper focuses on potential diagnosis that use Logical Diagnosis model [START_REF] Deschamps | Diagnosis for control system reconfiguration[END_REF]. This reduces the search space for faulty equipment from a given production flow and optimizes the learning step for the subsequent BN. The BN model, based on the graphical structure, received from Logical Diagnosis model then computes joint and conditional probabilities for each node, to support corrective maintenance decisions. The proposed method enables real time diagnosis for corrective maintenance in fully or semi automated manufacturing systems.

The characteristics of case study and diagnosis objective are introduced in the next section. Section 3 presents a review on fault diagnosis methods. The Logical Diagnosis model that results in suspected equipment against a failure drift explained in Section 4, whereas Section 5 represents the principles of Bayesian network theory. The proposed diagnosis model is described in Section 6. We use an example to explain the application of proposed method as illustrated in Section 7. At the end of this paper, the conclusion and future perspectives are discussed in Section 8.

II. CASE STUDY AND DIAGNOSIS OBJECTIVE

A. Case study

Manufacturing processes evolve to adapt increasing demand diversity. Speed, reliability, flexibility, cost, rapid product innovation and quality are all related to design a manufacturing process [START_REF] Brown | Strategic manufacturing for competitive advantage: transforming operations from shop floor to strategy[END_REF]. Many types of manufacturing system presented in [START_REF] Phillips | Manufacturing Plant Layout: Fundamentals and fine points of optimum facility design[END_REF] support the design and management of manufacturing processes. In fact, the customers demands frequently change, and so, it leads to the changes in corresponding products. It requires the flexibility of manufacturing system. This is reason to explain that flexible manufacturing systems (FMS) are widely used in complex and highly competitive manufacturing domains such as (micro-)electronic, automotive industry. FMS is a complex automated manufacturing system that consists of several production workshops, connected by an appropriate transport system. These production workshops and transport system are controlled by a control and automation system. The FMS is generally characterized by multiple products, production lines, recipes, and human factors. Generally, a complex system may have many production processes driven by a control law to perform demands of the control system. The structure of a production process describes product type, product lines and corresponding equipment in the operating part of controlled system. Any change in one of elements (such as product, equipment, recipe and human) through control law leads to adapt the existing processes.

Consequently, our research is based in the context of a general complex system under dynamic production environment with characteristics: multiple products, production lines, recipes, and human factors as shown in Fig. 1.

B. Diagnosis objective

In complex engineering applications, systems can be composed of many components and subsystems, and the ways in which these elements interact will affect the way failures propagate within the subsystems and across subsystem boundaries [START_REF] Hine | A review of diagnostic techniques for ISHM applications[END_REF]. For monitoring the execution of these elements, the hierarchical and modular controls are often used as presented in [START_REF] Jones | A multi-leve/multi-layer architecture for intelligent shopfloor control[END_REF]. In this context, an automated manufacturing system is organised by Computer Integrated Manufacturing (CIM) architecture that contains : controlled system, product flow and control system, as shown in Fig. 2. The controlled system consists of actuators and sensors. These sensors allow controlling and monitoring the executions of actuators and product flows. Each elementary part of the controlled system (actuators and sensors) is controlled by a local control module, and these two elements are called Functional Chain (FC) [START_REF] Henry | Controlled system model adapted for control law synthesis[END_REF]. They receive and execute demands from the coordination level of control system. When a FC cannot correctly execute a demand, it implies that a fault is produced. A fault may be created by a component and can propagate to other components through production lines. Therefore, this failure propagation may have Fig. 2. CIM architecture of an automated production system consequences on many components; and so, the new faults perhaps continue to occur. Thus, when a fault is detected by a metrology, its root causes may come from one or a part of elements of system. In summary, the diagnosis objective is to precisely and quickly locate the root causes to save recovery time (for return to a normal status) of the production system.

III. FAULT DIAGNOSIS METHODS STATUS

Diagnosis methods such as Fault Detection and Isolation (FDI) [START_REF] White | Automated diagnosis of feature model configurations[END_REF], Failure Mode and Effects Analysis (FMEA) [START_REF] Xiao | Multiple failure modes analysis and weighted risk priority number evaluation in FMEA[END_REF] are classically used for fault diagnosis in a production equipment. An advantage of these approaches is its simple integration in the production system. From detection information and the symptoms of failure, these kinds of approaches are proposed to model the possible failures in the production system. However, it is not feasible to analyze a complex system to describe all the failures and their causes. When an unpredicted fault occurs, the diagnosis cannot provide a result without human supports. In a complex system, a fault can propagate from equipment to others through product flows and it may trigger the consequences to others system elements; and so, the unpredicted failures frequently occur. In this case, the existing failure model cannot explain such problem.

Other techniques based on failure propagation to analyze component dependencies are propagation graph [START_REF] Abdelwahed | Notions of diagnosability for timed failure propagation graphs[END_REF] and temporal chronic [START_REF] Strasser | Diagnostic alarm sequence maturation in timed failure propagation graphs[END_REF]. These approaches are based on historical production data to locate components that are possible origins of a detected fault. However, there are many problems as follows: First, the actions of components in a system as presented in [START_REF] Abdelwahed | Notions of diagnosability for timed failure propagation graphs[END_REF] are considered independent. In fact, several operations may use the same functional chain to execute the demands of control system. Thus, the corresponding actions are not independent. Second, these approaches do not analyse the behaviors of the functional chains (FC), so they cannot explain the consequences between elements of a FC and between different FCs. Finally, these approaches cannot reduce the size of the model. Due to the cyclical operation of the control system, a large amount of information from the production system provokes the problem of combinatory explosion. Consequently, we are especially interested in the Logical Diagnosis model proposed in [START_REF] Deschamps | Diagnosis for control system reconfiguration[END_REF]. In this model, a diagnosis function is proposed to characterize the historical information data of a controlled system to search the suspected potential fault origins in real time. Hence, this model provides a set of possible origins under the form of a directed graph, and its size is reduced by the exploitation of the controlled system observations. This is appropriate to diagnose the faults of production equipment and products. However, this model does not show suspect level of each member in this set of fault origins. It is difficult in deciding a maintenance order. In a complex system, the set of possible fault origins is still large and this approach would be extended to optimize corrective maintenance activities.

In order to evaluate the suspect level of potential failure candidates, the probabilistic approaches are widely used such as Neural network [START_REF] Khomfoi | Fault Diagnostic System for a Multilevel Inverter Using a Neural Network[END_REF] and Bayesian network [START_REF] Weber | Overview on Bayesian networks applications for dependability, risk analysis and maintenance areas[END_REF]. These approaches enable to calculate the probability values from the large database and associated variables in a production system. These probability values allow evaluating the suspect level (high or low) in order to support decision of a maintenance strategy. In particular, the BN models have the advantages that fit to be applied in manufacturing industry as explained in [START_REF] Weber | Overview on Bayesian networks applications for dependability, risk analysis and maintenance areas[END_REF]. The methods based on BN are introduced in [START_REF] Bouaziz | Dependability of complex semiconductor systems: Learning Bayesian networks for decision support[END_REF] to make a diagnosis in a multiple variables system. The Confidence level of feedback information is proposed in [START_REF] Duong | Confidence estimation of feedback information for logicdiagnosis[END_REF] to provide the probability value that shows the correct actions confidence of reported information from equipment. When the database is available, these approaches are practical tools for the corrective maintenance. However, they must be extended. The structure of confidence level model for information feedback, as presented in [START_REF] Duong | Confidence estimation of feedback information for logicdiagnosis[END_REF], is static with seven parameters. In the context of flexible manufacturing system with characteristics such as multiple products, production lines, recipes and human factors, the production situation often change as we presented in above section. Hence, the set of parameters that can have an impact on the equipment confidence is dynamic. In addition, the BN model must be updated with the information for new situations. In practice, when the information in database is available, learning approaches are often used for modelling BN as presented in [START_REF] Neal | A view of the EM algorithm that justifies incremental, sparse, and other variants[END_REF]. In the learning approaches, a graphical structure and probabilistic rules are estimated from observed data. We can cite a number of learning approaches introduced in [START_REF]Data mining and knowledge discovery handbook[END_REF], [START_REF] Neal | A view of the EM algorithm that justifies incremental, sparse, and other variants[END_REF] such as EM, Maximum likelihood, IC&IC, K2, and Genetic algorithm. Many studies in [START_REF] Bouaziz | Dependability of complex semiconductor systems: Learning Bayesian networks for decision support[END_REF], [START_REF] Neal | A view of the EM algorithm that justifies incremental, sparse, and other variants[END_REF] show that these learning approaches are still complex in identifying variables as they depend strongly on expert opinions. The learning workload for computation is still large [START_REF] Neal | A view of the EM algorithm that justifies incremental, sparse, and other variants[END_REF]. This spends too much time and is not appropriate for real time structural identification as it depends on the exploitation of databases. In fact, production environments are increasingly stressed by strong competition. It shows that the time for locating the root causes of failures and process recovery (return the process to a normal status) is very important. These challenges promote the researches to apply BN model for real time fault diagnosis and corrective maintenance optimization. This idea is to simplify the variables identification during learning phase in the BN, (iii) the historical information of production system is used to estimate probabilistic rules in learning step of BN model, (iv) the conditional probabilities of nodes in structural model are computed. These probabilistic values allow evaluating the suspect level for each possible fault origin. In the next section, we will present the principles of the Logical Diagnosis model.

IV. LOGICAL DIAGNOSIS MODEL

The Logical Diagnosis model proposed in [START_REF] Deschamps | Diagnosis for control system reconfiguration[END_REF] is one part in the treatment of failure propagation through a product in a complex production process. In this model, a diagnosis function is proposed to characterize the historical information from a controlled system in locating the possible origins of a detected fault. This diagnosis function is presented in three main points:

• First, a model generates in real time the normal operation of operating part and collects all the necessary information from coordination level for fault diagnosis through the Operation Models that are presented in [START_REF] Henry | Controlled system model adapted for control law synthesis[END_REF]. An Operation Model contains information of Functional Chains (equipment, sensors and local control modular), (Pre-)conditions, (Pre-)constraints and effects of operations as shown in Fig. 3. The model for diagnosis describes a graphical structure of a production process that consists of system components (as illustrated in Fig. 4) and its relationships following product flows (the arrows → in Fig. 4).

• Second, a mechanism to reduce this model is developed based on the exploitation of the controlled system observations. Following an operation in this model, if the information provided by these two elements is not coherent, the controlled system sends to the coordination level a faulty execution report. If the coordination level does not receive a faulty execution report from these Functional Chains, it can conclude that the corresponding element is reliable. These reliable elements (the black nodes in Fig. 4) will be removed from the model, while the suspect elements (the white nodes in Fig. 4) will be retained.

• Finally, a mechanism is defined, based on the failure propagation approach (the dash arrows ⇢ in Fig. 4), that allows us searching the possible origins and the possible consequences of a fault when the model receives a faulty execution report from the Functional Chain as described in Fig. 4. The size of this model is reduced in real time by the observation of controlled system. It helps to cut down the space of suspected elements in system. This is very important in using the BN for fault diagnosis in a complex manufacturing, due to it is impossible to learn all system variables and all production information for model identification. Besides, following with dynamic production environment, the BN need the time for its structure update, so that leads to additional cost and poor maintenance. Whereas, the Logical Diagnosis model executes in real time and adapts well with the changes of production environment.

In this paper, the suspect operations are considered as possible origins {O 1 , ...O i , ...O n } of detected fault. The reduced model describes the logical links between possible fault origins; thus, these logical links are considered as the causeconsequence relationships according to the failure propagation. The form of reduced model is a directed graph in which the nodes represent suspect operations, while the arcs represent the paths of failure propagation through product flows. The set of possible fault origins and the information of reduced model will be used for structural identification of BN model; and therefore the conditional probabilities are computed next. The main points of BN theory are presented in the next section.

V. BAYESIAN NETWORK THEORY

There are a number of studies that present presented the Bayesian network (BN) theories such as [START_REF] Weber | Overview on Bayesian networks applications for dependability, risk analysis and maintenance areas[END_REF], [START_REF] Bouaziz | Dependability of complex semiconductor systems: Learning Bayesian networks for decision support[END_REF]. In literature, a BN is defined by:

• a directed acyclic graph G, G = (V, E), where V is the ensemble of nodes of G, and E is the ensemble of edges of G.

• a finite probabilistic space (Ω, Z, P ), with Ω is a nonempty space, Z is a collection of subspace of Ω, and P is a probability measure on Z with P (Ω) = 1.

• an ensemble of random variables associated to the nodes of G and defined on (Ω, Z, P ), such as:

P (V 1 , V 2 , ..., V n ) = n i=1 P (V i C(V i )) (1)
where C(V i ) is the ensemble of causes (parents) of V i in the graph G.

The Bayes rule is given by the equation (2):

P (X Y ) = P (Y X).P (X) P (Y ) (2)
• P (X Y ) is the conditional probability of X given by Y . • P (Y X) is the likelihood function of Y given X.

• P (X) and P (Y ) are the prior probabilities of X and Y .

When we need to extract the distribution over some subset of variables or a single variable, we need to marginalize or sum out the variables other than the variables of interest as explained in [START_REF] Manfredotti | Modeling and inference with relational dynamic Bayesian networks[END_REF]. The marginalization rule for any sets of variable X and Y is given by :

P (X) = y P (X, y); y ∈ Y (3)
The distribution over X can be obtained by summing out all the other variables from any joint distribution containing X. We can use the conditional probabilities instead of joint probabilities to compute the probabilities over X as shown in Equation (4):

P (X) = y P (X y).P (y); y ∈ Y (4)

VI. DIAGNOSIS MODEL

A. Model description

The proposed model comprises of logical diagnosis model and BN model as shown in Fig. 5. In this model, we use the results given by a logical diagnosis model introduced in Section 4 for the dynamically structural identification of a BN. After that, the probability values are computed by the BN model to support the decision-making for corrective maintenance. The model for diagnosis is based on the control system and dynamic reconfiguration as proposed in [START_REF] Deschamps | Diagnosis for control system reconfiguration[END_REF], [START_REF] Henry | Controlled system model adapted for control law synthesis[END_REF]. The reactive loop is characterized by collaboration of several supervision, monitoring and control (SM&C) functions such as detection, diagnosis, prognosis, decision and automatic control [START_REF] Zamai | An architecture for control and monitoring of discrete events systems[END_REF]. The coordination level of control system has capacity to manage a set of Functional Chains and corresponding information. It demands and memorizes the information from the production database. It also provides the information for diagnosis.

Our methodology consists of: (i) searching possible root causes against a detected fault in the past evolution of the operating part in controlled system, (ii) computing the probability values that show the suspect levels against candidates. The process of diagnosis model execution is illustrated as following principles:

• This model is generated by the coordination level of a control system. This coordination level sends commands and receives reports in real time for and from all system components. This coordination level also provides the necessary information for the logical diagnosis.

• Once a failure is detected by a metrology, a set of possible origins and its correlations are defined by the logical diagnosis model.

• This set of possible origins and corresponding information are sent to BN model. Thus, a graphical structure of failure mode is determined to support the structural identification in learning step of BN model.

• After the establishment of graphical structure of BN model, the conditional probabilities associated with all nodes of network are computed based on historical information in the production database. All computed results are stored in the production database to support decision-making for corrective maintenance.

B. The execution of diagnosis model

for i = 1 to n do Initialize k i = 1 for i ′ = 1 to n and i ′ ≠ i do if O i ′ is located in front of O i and has directly logical relationship with O i then O i ′ =Parent of O j O ki i = O i ′ and k i = k i + 1 end if end for N i = k i and delete k i end for return P arents(O i )= O ki i ; k i = 1 to N i ; i = 1 to n
• Second, we obtain a graphical structure of BN model.

Each node in this structure may be a parent of childnodes and may be a child of other parent-nodes. For instance, a set of parents a detected fault node is a finite number of mutually exclusive operation with l j = 1⋯L j . In this case, the BN model has a hierarchical structure as shown in Fig. 6. • Third, after a graphical structure is identified, the learning step of BN model will be performed to calculate the probabilities P (O i P roduct) of each node O i following the product, and next the conditional probabilities between the child-nodes and its parents based on the historical information of production system from the database. We consider that each member of the set of fault origins has two states {1, 0}. Thus, the conditional probabilities over each operation O j with (j = 1⋯N ) and its parents O

⎛ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ p O j = 1 O 1 j = 1, ...O kj j = 1, ...O Nj j = 1 ⋮ p O j = 1 O 1 j = 0, ...O kj j = 0, ...O Nj j = 0 p O j = 0 O 1 j = 1, ...O kj j = 1, ...O Nj j = 1 ⋮ p O j = 0 O 1 j = 0, ...O kj j = 0, ...O Nj j = 0 ⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠ (5)
• Finally, the model computes the conditional probabilities P (O i f ault, P roduct) over node O i with (i = 1⋯n) given by detected fault according to the Product as illustrated in the next equation:

P (O i f ault, P roduct) = n j=1 Oj P (O i ).P (O j O i ). P (f ault O 1 , ..., O j , ..., O n , P roduct) (6)
with j = 1⋯n, j ≠ i. They are used to support a decision of a maintenance operator.

The above sections show that a set of possible origins is dynamically determined when a fault is detected. And when the data is available, the corresponding conditional probabilities are calculated by diagnosis model. This set of possible origins and these probability values are sent and stored in the production database by the coordination level.

C. Application capacity of proposed diagnosis model

The advantages of proposed model are: first to locate a possible fault origins set in real time, second to reduce the space of this set by the evaluation of suspect levels, and finally less workload for structure identification of BN model. In the proposed model, the set of possible root causes is significantly reduced by the Logical Diagnosis model. Next, this is used to simplify a structural identification of BN model. Hence, the BN model receives a graphical structure with only elements at the possible origins of a detected fault. While other elements not related to the detected fault are removed. Consequently, it does not need to compute all probabilities of all elements in the production system.

In addition, the probabilistic values given by BN model help to continue reducing the set of possible origins through risk priority. This shows that we can save the recovery time of a production system. This also implies that the combination of a deterministic approach (logical diagnosis) and a probabilistic approach (Bayesian network) help us to locate more accurately and quickly equipment as the root cause of a detected fault. Consequently, this proposed model is feasible to apply for fault diagnosis in complex automated manufacturing systems with large production information.

The next section presents an example to explain the application of proposed diagnosis model in an automated production system.

VII. APPLICATION EXAMPLE

To illustrate the basic principles of proposed method, we propose an example that consists of two cylinders as shown in Fig. 7. The product is transported from position A to position B by the cylinder 1 and from position C to position D by the cylinder 2. A conveyor is used to transfer the product between positions B, C, E. Three sensors SA, SD, SE are installed in positions A, D, E to observe the position of a product. The goal of this system is to transport the products to position D. These monitoring sensors allow the verification of the values of product state variables. We consider that this production system is integrated with a diagnosis model that has a diagnosis mechanism as proposed in above section. The coordination level observes and qualifies the execution of all operations that are executed by the controlled system. Following the operation to put product in position A, if the Functional Chain (FC) of sensor SA does not send a faulty execution report to the coordination level, it means that this FC has correlation between the product observation and information on production system behavior. Hence, the Fig. 8. Evolutions model following the product flows corresponding (Pre-)conditions and (Pre-)constraints are also qualified as correct, then corresponding nodes (colored in black) are removed from the model. Finally, we obtain a reduced model that contains the suspect elements (the white nodes in Figure 8). When product is not detected at D, the FC of sensor SD send a faulty execution report to the coordination level. The mechanism based on a failure propagation approach is used to search for reduced model with the possible origins of this fault.

According to the faulty report of Product at position D, a set of possible origins consists of {Cylinder 1, Product in B, Product in C, Cylinder 2} followed by the failure propagation. This set is transformed to a graphical structure of BN model by Algorithm 1 (presented in Section 4). This graphical structure and the conditional probabilities between the parent-nodes and child-notes are presented in Fig. 9. The conditional probabilities of machines, which are given when product is in bad state, are shown as TABLE I. The result shows that the possible origins of the fault detected on product by metrology may be one member of the set {Cylinder 1, Product in B, Product in C, Cylinder 2}. Furthermore, the result shown in TABLE I concludes that the conditional probability P(Product in C Product in D) of node Product in C corresponding to a given fault Product in D has maximum value. Consequently, the node Product in C must be first investigated by the personal maintenance. This example also implies that if we do not use the BN, the set of possible origins have 4 members {Cylinder 1, Product in B, Product in C, Cylinder 2}. Thus, we must investigate all of these 4 members as potential causes. However, if the BN model is used, the computed conditional probabilities help to make decision to investigate the member with highest suspect level.

Moreover, if the diagnosis process is performed based on a BN model without the Logical Diagnosis model, all the nodes (black and white) in Fig. 8 may be possible origins of detected fault at node Product in D. We must use a learning method to identify the graphical structure of the BN. The computation time and work-load become larger than the case of within Logical Diagnosis model. In summary, the combination of two techniques allows making use of its advantages and avoiding inconveniences. The proposed model is dedicated to advance real time diagnosis and simplify the decision making for a maintenance strategy. It is appropriate to apply on the flexible manufacturing systems under dynamic production environment.

VIII. CONCLUSION

The proposed approach in this paper dynamically generates the structure of the BN and the associated probabilities. We used a Logical Diagnosis model to significantly reduce the search space for suspect equipment in the given production flow. This reduced set of possible origins as directed graph provides the cause-consequent relation to simplify the failure model identification in learning phase of BN. In addition, the associated probabilities are computed by the BN model evaluate the suspect level of each member in the set of possible fault origins. Our methodology has capacity to combine the advantages of both methods of Logical Diagnosis and BN.

In the context of complex manufacturing system that is characterized by multiple products, production lines, recipes and human factors. The elements of system often change under flexible production activities. The proposed model is appropriate in dynamically locating the root causes, in less time and less workload to compute the conditional probability values. The diagnosis results support decision-making for corrective maintenance activities. This diagnosis objective is first based on the precisely and quickly locating the faults that come from equipment and products. Moreover, it must take into account the different fault sources as recipes and human factors; and furthermore their correlations. Consequently, our future work will improve on the fault diagnosis in a general manufacturing system with multiple sources of faults.

Fig. 1 .

 1 Fig. 1. A Flexible Manufacturing System

  This paper proposes a diagnosis model that enables real time localization of the possible fault and root causes, thus dynamically computing conditional probabilities between a fault and its possible causes. This model is based on a Logical Diagnosis model and a BN model. The Logical Diagnosis model aides to reduce the workload of model identification for diagnosis model. It has four main steps: (i) the Logical Diagnosis model provides a set of possible fault origins. The relationships of members in this set are used to construct a graphical structure, (ii) we use this structure for the BN model.

Fig. 3 .

 3 Fig. 3. Operation Model

Fig. 4 .

 4 Fig. 4. Structural model

Fig. 5 .

 5 Fig. 5. Diagnosis model

Algorithm 1

 1 When a fault is detected by a metrology, the diagnosis model manages its execution and will demand the diagnosis results from Logical Diagnosis model and the BN model. The Logical Diagnosis model provides a reduced model of the set of possible fault origins {O 1 , ...O i , ...O n } as presented in Section 4. This information is sent to BN through the coordination level, and it is used to construct the BN model. The conditional probabilities are computed based on the principal theories as presented in Section 5. The BN model for diagnosis will be established and performed as follows: • First, an algorithm as proposed below (Algorithm 1) is used for equivalent transition from a set of possible root causes and its directed graphical structure given by logical diagnosis model to a graphical structure of BN model. In Algorithm 1, we assume that a set of possible root causes has n members as {O 1 , ...O i , ...O n }. Each member O i of the set obtained by logical diagnosis model is considered as one node in the BN. The other members O i ′ ; (i ′ = 1⋯n, i ′ ≠ i) are the parents of node O i if they are in front of the node O i and have directly logical relationship with O i following a product flow in directed graph. Equivalent transition of a graphical structure Inputs : A set of n possible origins and its relationships. Outputs : A graphical structure of Bayesian network model.

{O 1 ,

 1 ...O j , ...O N }. Each operation O j with (j = 1⋯N ) has a set of parents as O 1 j , ...O kj j , ...O Nj j , with k j = 1⋯N j . Therefore, each member O kj j has a set of parents as O kj ,1 j , ...O kj ,lj j , ...O kj ,Lj j

Fig. 6 .

 6 Fig. 6. Graphical structure of BN model

  1 j , ...O kj j , ...O Nj j are defined as a matrix P O j O 1 j , ...O kj j , ...O Nj j as shown in equation 5:

Fig. 7 .

 7 Fig. 7. Example to illustrate the application of diagnosis model

Fig. 9 .

 9 Fig. 9. The graphical structure and the conditional probabilities of its nodes The Fig.9 illustrates the graphical structure for BN and the corresponding conditional probabilities. Where: • P(Cylinder 1 Product), P(Cylinder 2 Product) are the

TABLE I .

 I

THE PROBABILITY RESULTS P(Cylinder 1 Product in D) 0.0342 P(Product in B Product in D) 0.0371 P(Product in C Product in D) 0.2057 P(Cylinder 2 Product in D) 0.0527