Hough-like methods (Implicite Shape Model, Hough forest, 9 ...) have been successfully applied in multiple computer vision fields like 10 object detection, tracking, skeleton extraction or human action detection. However, these methods are known to generate false positives. To handle 12 this issue, several works like Max-Margin Hough Transform (MMHT) or 13 Implicit Shape Kernel (ISK) have reported significant performance im-14 provements by adding discriminative parameters to the generative ones 15 introduced by the Implicit Shape Model (ISM). In this paper, we pro-16 pose to use only discriminative parameters that are globally optimized 17 according to all the variables of the Hough transform. To this end, we 18 abstract the common vote process of all Hough methods into linear equa- 19 tions, leading to a training formulation that can be solved using linear 20 programming solvers. 21 Our new Hough Transform significantly outperforms the previous ones 22 on HoneyBee and TUM datasets, two public databases of action and 23 behaviour segmentation. 24 25 1 Introduction 26 The Hough Transform has first been introduced to detect lines in picture. The 27 main idea of this method is to perform the detection not directly in the picture 28 space but in the line parameter space (Hough space) where each line in the image 29 is mapped into a single point. This method has subsequently been extended to 30 parametric objects [1], and non-parametric objects [9] (eg. car, pedestrian, sport 31 activities, ...). For non parametric objects, the Hough Transform first learns a 32 probabilistic-like parametrization of the objects on a training database, and, 33 then performs the detections as a local problem in the corresponding Hough 34 space. 35 Due to this property of local detection, Hough Transform is a very fast pro-36 cess both in theory (time complexity theory) and practice. For this reason, it 37 has been applied in context of real-time system like [6] for skeleton extraction 38 ICIAP #23 ICIAP #23 ICIAP 2013 Submission #23. CONFIDENTIAL REVIEW COPY. DO NOT DISTRIBUTE. II and more generally in multiple computer vision fields like tracking [5], object 39 detection [4], human action detection [18], image segmentation [10] or human 40 action segmentation [19]. In the context of temporal signals segmentation and recognition, the Hough 42 Transform is composed of three steps: 43 1: Feature extraction and quantization to form codewords 44 2: Each codeword votes for each time (in a large neighborhood) and each label 45 according to a specific learned weight 46 3: All the votes are agglomerated to form the Hough score from which segmen-47 tation decisions are taken 48 More formally, the Hough Transform (step 2-3) is based on a function θ() 49 that links codewords, time displacements (quantified into a finite set) and labels 50 to vote weights. Thus, a codeword w extracted at time t votes with a weight 51 θ (w, l, ∆ t ) for the hypothesis that a label l is present at time t + ∆ t (this weight 52 does not depend on the time t but only on the relative time displacement ∆ t ). Hence, given a set of localized codewords W = {w, t}, the Hough score H for 54 the label l at the time t is: and, the decision about the label (in L) at time t is given by: Hence, all the purpose of the training is to select values for θ (w, l, ∆ t ) that 57 will provide correct decisions when following the equations (1) (2) at testing 58 time. Several works, recalled in section 2, propose to improve the generative 59 votes used by the Implicit Shape Model (ISM method) by introducing a partial 60 discriminative optimization process during the vote estimation step. In section 61 3, we propose to extend these methods by optimizing globally all the votes in a 62 discriminative way. With this new learning process, our Hough method signifi-63 cantly outperforms previous ones on two public datasets of signal segmentation 64 (the Honeybee dataset [12] and the TUM dataset [15]) as reported in section 4, 65 before the conclusion in section 5. 66 2 State of the Art 67 In this section, we present the different published methods to select the vote 68 weight during the training step of Hough Transform. 69 2.1 Implicit Shape Model 70 In the ISM [9], the Hough Transform (the set of θ ()-values) is based on gener-71 ative weights. Let P (l, ∆ t |w) be the probability that the label at time t + ∆ t 110 these methods define links between codewords and votes. There are, of course, 111 various ways to select the features and the codewords, like, the Hough forest 112 methods which are major methods of the state of the art. Hough forests use ISM 113 votes, but the mapping between features (usually data patches) and codewords (a 114 leaf in a weak binary classifier tree) is constructed such that all training features 115 associated with a same codeword are expected to come from training examples 116 with a same label. Several works, like [4], report that this automatic feature 117 mapping process associated with ISM votes leads to significant experimental 118 improvements against codewords obtained without learning, by K-means for 119 example. 120 However, in this paper, we focus on the optimisation of the weights used 121 during the vote process and so to the link between codewords and votes which is 122 generic whatever the features and codewords used. Thus, the proposed method 123 can be employed in the Hough forest context by substituting the weights esti-124 mated by ISM by the weights optimized by our proposed method. 125 The common point between MMHT, ISK and SISM is that they add dis-126 criminative parameters to the generative ones introduced by the ISM. In this 127 paper, we propose to use only discriminative votes strongly optimized. We call 128 this method Deeply Optimized Hough Transform (DOHT). 129 3 Deeply Optimized Hough Transform 130 The goal of the training process is to establish a correspondence between code-131 words and weights. While the ISM methods only use generative weights, MMHT, 132 ISK and SISM introduce discriminative parameters optimized according to code-133 words, training examples or displacements. Using these methods that optimize 134 only one parameter of θ (w, l, ∆ t ), a small number of coefficients λ have to be 135 determined. So the optimization process can be solved using SVM. We propose 136 in this paper to optimize all the weights in a global way, according to all the 137 parameters of θ (w, l, ∆ t ) in multi-class context. In this way, we do not use ISM 138 values and the method becomes deeply discriminative. The problem is that the 139 number of unknown parameters is more important and their optimisation using 157 close for a small δ and for all w and l, we regularly quantify all possible ∆ t 158 values. Finally, the problem to solve is formulated as: As previously stated, a significant difference between MMHT,ISK or SISM 161 and DOHT is that we optimize simultaneously all values θ (w, l, ∆ t ) of the theta 162 function, and not only some variables in order to improve the θ ISM function. 173 DOHT) in action segmentation or behavior segmentation contexts. As ISK is 174 only adapted to detection and can not be straightforwardly extended to segmen-175 tation, we can not compare it to the others methods. 176 4 Experimental Results 177 Experiments have been conducted on the TUM [15] and Honeybee [12] datasets. 178 These datasets are well designed for segmentation as each frame (here, frames 179 and times are equivalent) is associated with a label. 180 4.1 Application to Human Action Segmentation 181 TUM is a multi-sensor dataset and in particular it contains skeleton streams 182 (fig. 1). It is composed of 19 sequences around 2 minutes each containing 9 183 kinds of actions (each action is a label) like Lowering an object, Opening a 184 drawer performed by 5 peoples. To provide results comparable to [19], the same 185 experimental protocol is applied for splitting data between training and testing 186 set, and, results are given in terms of accuracy (number of correctly labelled 187 frames divided by the total number of frames). 188 3 www-01.ibm.com/software/websphere/products/optimization/academic-initiative/ 199 the vector (p t−τ , ..., p t+τ ) as a feature extracted at time t. Similar features are 200 also considered in [14, 19, 16] which report the efficiency of interest points tra-201 jectories for human action recognition. Finally, all these features are clustered 202 by K-means. The cluster centers defines the codebook and features are mapped 203 to their nearest codeword. More precisely, we consider the 8 main articulations: feet, hands, knees, el-205 bows with τ = 6. The quantization with K-means is performed independently for 206 each articulation with K = 10, resulting in 80 codewords. The few parameters 207 of this experiments (τ , K, Υ and the quantification granularity of ∆ t for the 208 optimization process (see section 3)) empirically provide the best performances. Results of this experiment are presented in table 2. 210 In this experiment, DOHT significantly outperforms ISM, MMHT and SISM 211 and achieves equivalent performance than a SVM based on the same features and 212 codeword applied on the optimal segmentation (obtained from the ground truth) 213 from [2]. Hence, for this dataset, we achieve equivalent performance than the best 214 published (82.6% against 84.3%) without using the optimal segmentation. 215 ICIAP #23 ICIAP #23 ICIAP 2013 Submission #23. CONFIDENTIAL REVIEW COPY. DO NOT DISTRIBUTE. VIII 4.2 Application to Behaviour Segmentation 216 Experiments have also been conducted on the Honeybee dataset [12]. The Honey-217 bee dataset provides tracking output of honey bees having 3 kinds of behaviours 218 (each behaviour corresponds to a label) correlated with their trajectories (figure 219 2). It composed of 6 large sequences. To provide results comparable to [12], the 220 same leave-one-out cross validation is applied. A global measure is obtained by 221 averaging accuracy from all runs. 222 (a) theoretic behaviour (b) tracking output Green correspond to waggle, magenta to right turn and blue to left turn. Fig. 2. Honeybee dataset [12] The input signals in this dataset are the sequences of bee 2D positions and 223 orientations (x t , y t , α t ). As in the previous experiment, normalized short tempo-224 ral series of (2D here) positions are considered as features. Let us call R (β) the 225 matrix of the 2D rotation of angle −β and p (t) = (x t , y t ), then we consider the 226 vector (R (α t ) (p t−τ − p t ) , ..., R (α t ) (p t+τ − p t )) as the feature extracted at time 227 t. All these features are clustered using K-means. The cluster centers defines the 228 codebook and features are mapped to their nearest codeword. More precisely, short series of size τ = 0, 3, 6 are considered in this experi-230 ment. K-means is performed independently for each τ with K = 16, 32, 64 re-231 spectively, resulting in 112 codewords. The few parameters of this experiments 232 empirically provide the best performances. Results of this experiment are pre-233 sented in table 2. 234 In this experiment, DOHT significantly outperforms ISM, MMHT and SISM. 235 In addition, DOHT achieves equivalent performances than the best published 236 results [7]. In [7], a multi-class SVM is applied on each temporal windows (with 237 similar kind of features and codewords). Then, segmentation is computed using 238 dynamic programming. As scores are computed on each temporal windows, this 239 method is quadratic in the maximal length of an activity while our is linear. 240 This quadratic property is a common drawback caused by performing scoring 241 as a global problem. Hence, for this dataset, we achieve equivalent performances 293 12. S.M. Oh, J.M. Rehg, T. Balch, and F. Dellaert. Learning and inferring motion pat-294 terns using parametric segmental switching linear dynamic systems. 300 temporal context modeling for action recognition. In IEEE Conference on Com-301 puter Vision and Pattern Recognition. IEEE, 2009. 302 15. M. Tenorth, J. Bandouch, and M. Beetz. The tum kitchen data set of everyday 303 manipulation activities for motion tracking and action recognition. In IEEE 12th
Among them, we choose the DOHT method REF that is, at present, the more efficient since it optimizes all the voting scores used in the Hough method.
Deeply optimized Hough transform: Application to action segmentation
ICIAP
Computer Science