Abstract:
A method of recognizing an activity on the basis of a semi-Markov conditional random field (CRF) model is provided. The method includes segmenting an input signal measured by an accelerometer to output frame sequences, extracting training feature vectors from the frame sequences, building a codebook containing kernel vectors from the training feature vectors; quantizing vector sequences into discrete symbol sequences, using linear chain semi-Markov CRF model to compute the likelihood of a label given its corresponding symbol sequence.

Description:
CROSS REFERENCE TO RELATED APPLICATION 
       [0001]    This application claims the benefit under 35 U.S.C. §119(a) of Korean Patent Application No. 10-2009-0092277, filed on Sep. 29, 2009, in the Korean Intellectual Property Office, the entire disclosure of which is incorporated herein by reference for all purposes. 
       BACKGROUND 
       [0002]    1. Field 
         [0003]    The following description relates to a method of recognizing an activity on the basis of a semi-Markov conditional random field (CRF) model. 
         [0004]    2. Description of the Related Art 
         [0005]    Activity recognition is applied to various fields ranging from daily life to industry, and thus is becoming more important in people&#39;s lives. Activity recognition is frequently performed using many different sensors. Among these sensors, an accelerometer has been known as an effective sensor for measuring an activity because of low cost and low power consumption. 
         [0006]    Lately, CRF models are used in sequential data modeling, thereby resulting in useful outcomes. These have been disclosed in reference document “Conditional random fields: Probabilistic models for segmenting and labeling sequence data” by John Lafferty, Andrew McCallum and Fernando Pereira. 
         [0007]    However, such a conventional CRF cannot model the durations of activities nor the transitions over a long time period between activities. 
         [0008]    To solve these problems, various modifications of the CRF have been proposed [Sunita Sarawagi, et al., 2004, and D. L. Vail, et al., 2001]. However, these modifications of the CRF have unrealistic complexity or do not completely solve the problems. For example, the first CRF proposed by John Lafferty, et al., in 2001 cannot model a duration of a state due to the Markov assumption. 
         [0009]    Content disclosed by Sunita Sarawagi, et al. in 2004 to overcome this limitation is intended to lessen the Markov property using a semi-CRF. However, when activity recognition is applied, an unknown activity or null activity occurs between two expected activities or target activities, and thus the semi-CRF cannot capture an activity transition over a long time period either. 
       SUMMARY 
       [0010]    The following description relates to a solution to conventional problems, which is based on the extension of a semi-Markov conditional random field (CRF) model and has appropriate complexity. 
         [0011]    According to an exemplary aspect, there is provided a method of recognizing an activity on the basis of a semi-Markov conditional random field (CRF) model, including: segmenting an input signal measured by an accelerometer to output frame sequences; extracting training feature vectors from the frame sequences; building a codebook containing kernel vectors from the training feature vectors; quantizing vector sequences into discrete symbol sequences; using linear chain semi-Markov CRF model to compute the likelihood of a label given its corresponding symbol sequence. 
         [0012]    Additional aspects of the invention will be set forth in the description which follows, and in part will be apparent from the description, or may be learned by practice of the invention. 
         [0013]    It is to be understood that both the foregoing general description and the following detailed description are exemplary and explanatory and are intended to provide further explanation of the invention as claimed. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0014]    The accompanying drawings, which are included to provide a further understanding of the invention and are incorporated in and constitute a part of this specification, illustrate exemplary embodiments of the invention, and together with the description serve to explain the aspects of the invention. 
           [0015]      FIG. 1  illustrates a semi-Markov conditional random field (CRF) according to an exemplary embodiment of the present invention. 
           [0016]      FIG. 2  shows graphs of bell-shaped probability functions for duration modeling according to an exemplary embodiment of the present invention. 
           [0017]      FIG. 3  is a block diagram illustrating an example of activity recognition to which a semi-Markov CRF model according to an exemplary embodiment of the present invention is applied according to an exemplary embodiment of the present invention. 
           [0018]      FIG. 4  is a block diagram illustrating a process of generating a kernel vector according to an exemplary embodiment of the present invention. 
           [0019]      FIG. 5  is a flowchart illustrating a process of calculating Z according to an exemplary embodiment of the present invention. 
       
    
    
     DETAILED DESCRIPTION 
       [0020]    The invention is described more fully hereinafter with reference to the accompanying drawings, in which exemplary embodiments of the invention are shown. This invention may, however, be embodied in many different forms and should not be construed as limited to the exemplary embodiments set forth herein. Rather, these exemplary embodiments are provided so that this disclosure is thorough, and will fully convey the scope of the invention to those skilled in the art. In the drawings, the size and relative sizes of layers and regions may be exaggerated for clarity. Like reference numerals in the drawings denote like elements. 
         [0021]      FIG. 1  illustrates a semi-Markov conditional random field (CRF) according to an exemplary embodiment of the present invention. 
         [0022]    Heretofore, activity recognition solutions using a Markov model have not considered the correlation between activities and the durations of the activities and thus have not had high complexity. 
         [0023]    An exemplary embodiment of the present invention relates to a semi-Markov CRF model having an algorithm whereby training and inference are simultaneously and rapidly performed to take the correlation between activities and the durations of the activities into consideration. 
         [0024]    In other words, an exemplary embodiment of the present invention extends a semi-Markov CRF, thereby capturing an activity transition over a long time period while using the duration modeling performance of a conventional semi-Markov CRF. 
         [0025]    To this end, a semi-Markov CRF with discontinuous state time is configured according to an exemplary embodiment of the present invention, and the semi-Markov CRF has a linear chain structure as shown in  FIG. 1 . 
         [0026]    In  FIG. 1 , y 1 , y 2 , y 3  and y 4  denote states, and x denotes an input symbol value. In the semi-Markov CRF, a predetermined state is indicated by s i =(y i , b i , e i ), and an i-th state is defined by the three parameters y i , b i  and e i . The parameter y i  relates to i-th state information, the parameter b i  relates to an i-th beginning time, and the parameter e i  relates to an i-th ending time. 
         [0027]    The beginning time and ending time of an activity are separate from each other and satisfy Expression 1 below. 
         [0000]      0&lt;b i ≦e i  
 
         [0000]      e i &lt;b i+1    [Expression 1]
 
         [0028]    A probability P(S|X) of a state sequence S given by an input sequence X is calculated by Expression 2 below. 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       P 
                        
                       
                         ( 
                         
                           S 
                           | 
                           X 
                         
                         ) 
                       
                     
                     = 
                     
                       
                         
                           ∏ 
                           
                             i 
                             = 
                             1 
                           
                           P 
                         
                          
                         
                             
                         
                          
                         
                           Ψ 
                            
                           
                             ( 
                             
                               
                                 s 
                                 
                                   i 
                                   - 
                                   1 
                                 
                               
                               , 
                               
                                 s 
                                 i 
                               
                               , 
                               X 
                             
                             ) 
                           
                         
                       
                       
                         Z 
                         X 
                       
                     
                   
                    
                   
                     
 
                   
                    
                   
                     
                       Z 
                       X 
                     
                     = 
                     
                       
                         ∑ 
                         
                           S 
                           ′ 
                         
                       
                        
                       
                         
                           ∏ 
                           
                             i 
                             = 
                             1 
                           
                           
                             P 
                             ′ 
                           
                         
                          
                         
                             
                         
                          
                         
                           Ψ 
                            
                           
                             ( 
                             
                               
                                 s 
                                 
                                   i 
                                   - 
                                   1 
                                 
                                 ′ 
                               
                               , 
                               
                                 s 
                                 i 
                                 ′ 
                               
                               , 
                               X 
                             
                             ) 
                           
                         
                       
                     
                   
                 
               
               
                 
                   [ 
                   
                     Expression 
                      
                     
                         
                     
                      
                     2 
                   
                   ] 
                 
               
             
           
         
       
     
         [0029]    In Expression 2, Ψ denotes a probability of activity transition from s i−1  to s i . 
         [0030]    Ψ is calculated by Expression 3 below. 
         [0000]    
       
         
           
             
               
                 
                   
                     Ψ 
                      
                     
                       ( 
                       
                         
                           s 
                           
                             i 
                             - 
                             1 
                           
                         
                         , 
                         
                           s 
                           i 
                         
                         , 
                         X 
                       
                       ) 
                     
                   
                   = 
                   
                     ( 
                     
                       
                         
                           
                             
                                
                               
                                 
                                   Q 
                                   T 
                                 
                                  
                                 
                                   ( 
                                   
                                     
                                       y 
                                       
                                         i 
                                         - 
                                         1 
                                       
                                     
                                     , 
                                     
                                       y 
                                       i 
                                     
                                   
                                   ) 
                                 
                               
                             
                             × 
                           
                         
                       
                       
                         
                           
                             
                                
                               
                                 
                                   Q 
                                   D 
                                 
                                  
                                 
                                   ( 
                                   
                                     
                                       y 
                                       i 
                                     
                                     , 
                                     
                                       
                                         e 
                                         i 
                                       
                                       - 
                                       
                                         b 
                                         i 
                                       
                                       + 
                                       1 
                                     
                                   
                                   ) 
                                 
                               
                             
                             × 
                           
                         
                       
                       
                         
                           
                             
                                
                               
                                 
                                   Q 
                                   O 
                                 
                                  
                                 
                                   ( 
                                   
                                     
                                       y 
                                       i 
                                     
                                     , 
                                     
                                       b 
                                       1 
                                     
                                     , 
                                     
                                       e 
                                       i 
                                     
                                   
                                   ) 
                                 
                               
                             
                             × 
                           
                         
                       
                       
                         
                           
                              
                             
                               
                                 Q 
                                 O 
                               
                                
                               
                                 ( 
                                 
                                   IA 
                                   , 
                                   
                                     
                                       e 
                                       
                                         i 
                                         - 
                                         1 
                                       
                                     
                                     + 
                                     1 
                                   
                                   , 
                                   
                                     
                                       b 
                                       i 
                                     
                                     - 
                                     1 
                                   
                                 
                                 ) 
                               
                             
                           
                         
                       
                     
                     ) 
                   
                 
               
               
                 
                   [ 
                   
                     Expression 
                      
                     
                         
                     
                      
                     3 
                   
                   ] 
                 
               
             
           
         
       
     
         [0031]    Q T (y′, y), Q D (y, d), Q O (y, t 1 , t 2 ), and Q O (IA, t 1 , t 2 ) in Expression 3 can be calculated by Expression 4 below. 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       
                         Q 
                         T 
                       
                        
                       
                         ( 
                         
                           
                             y 
                             ′ 
                           
                           , 
                           y 
                         
                         ) 
                       
                     
                     = 
                     
                       
                         
                           w 
                           T 
                         
                          
                         
                           ( 
                           
                             
                               y 
                               ′ 
                             
                             , 
                             y 
                           
                           ) 
                         
                       
                        
                       
                         δ 
                          
                         
                           ( 
                           
                             
                               
                                 y 
                                 
                                   t 
                                   - 
                                   1 
                                 
                               
                               = 
                               
                                 y 
                                 ′ 
                               
                             
                             , 
                             
                               
                                 y 
                                 t 
                               
                               = 
                               y 
                             
                           
                           ) 
                         
                       
                     
                   
                    
                   
                     
 
                   
                    
                   
                     
                       δ 
                        
                       
                         ( 
                         X 
                         ) 
                       
                     
                     = 
                     
                       { 
                       
                         
                           
                             
                               
                                 
                                   1 
                                    
                                   
                                       
                                   
                                    
                                   if 
                                    
                                   
                                       
                                   
                                    
                                   X 
                                    
                                   
                                       
                                   
                                    
                                   is 
                                    
                                   
                                       
                                   
                                    
                                   true 
                                 
                               
                             
                             
                               
                                 
                                   0 
                                    
                                   
                                       
                                   
                                    
                                   if 
                                    
                                   
                                       
                                   
                                    
                                   X 
                                    
                                   
                                       
                                   
                                    
                                   is 
                                    
                                   
                                       
                                   
                                    
                                   false 
                                 
                               
                             
                           
                            
                           
                             
 
                           
                            
                           
                             
                               Q 
                               D 
                             
                              
                             
                               ( 
                               
                                 y 
                                 , 
                                 d 
                               
                               ) 
                             
                           
                         
                         = 
                         
                           
                             
                               
                                 w 
                                 D 
                               
                                
                               
                                 ( 
                                 y 
                                 ) 
                               
                             
                              
                             
                               
                                 
                                   ( 
                                   
                                     d 
                                     - 
                                     
                                       m 
                                       y 
                                     
                                   
                                   ) 
                                 
                                 2 
                               
                               
                                 2 
                                  
                                 
                                     
                                 
                                  
                                 
                                   σ 
                                   y 
                                   2 
                                 
                               
                             
                              
                             
                               δ 
                                
                               
                                 ( 
                                 
                                   
                                     y 
                                     t 
                                   
                                   = 
                                   y 
                                 
                                 ) 
                               
                             
                              
                             
                               
 
                             
                              
                             
                               
                                 Q 
                                 O 
                               
                                
                               
                                 ( 
                                 
                                   y 
                                   , 
                                   
                                     t 
                                     1 
                                   
                                   , 
                                   
                                     t 
                                     2 
                                   
                                 
                                 ) 
                               
                             
                           
                           = 
                           
                             
                               
                                 ∑ 
                                 
                                   t 
                                   = 
                                   
                                     t 
                                     1 
                                   
                                 
                                 
                                   t 
                                   2 
                                 
                               
                                
                               
                                 
                                   ∑ 
                                   o 
                                 
                                  
                                 
                                   
                                     
                                       w 
                                       O 
                                     
                                      
                                     
                                       ( 
                                       
                                         y 
                                         , 
                                         o 
                                       
                                       ) 
                                     
                                   
                                    
                                   
                                     δ 
                                      
                                     
                                       ( 
                                       
                                         
                                           
                                             y 
                                             t 
                                           
                                           = 
                                           y 
                                         
                                         , 
                                         
                                           
                                             x 
                                             t 
                                           
                                           = 
                                           o 
                                         
                                       
                                       ) 
                                     
                                   
                                    
                                   
                                     
 
                                   
                                    
                                   
                                     
                                       Q 
                                       O 
                                     
                                      
                                     
                                       ( 
                                       
                                         IA 
                                         , 
                                         
                                           t 
                                           1 
                                         
                                         , 
                                         
                                           t 
                                           2 
                                         
                                       
                                       ) 
                                     
                                   
                                 
                               
                             
                             = 
                             
                               
                                 ∑ 
                                 
                                   t 
                                   = 
                                   
                                     t 
                                     1 
                                   
                                 
                                 
                                   t 
                                   2 
                                 
                               
                                
                               
                                 
                                   ∑ 
                                   o 
                                 
                                  
                                 
                                   
                                     
                                       w 
                                       O 
                                     
                                      
                                     
                                       ( 
                                       
                                         IA 
                                         , 
                                         o 
                                       
                                       ) 
                                     
                                   
                                    
                                   
                                     δ 
                                      
                                     
                                       ( 
                                       
                                         
                                           
                                             y 
                                             t 
                                           
                                           = 
                                           IA 
                                         
                                         , 
                                         
                                           
                                             x 
                                             t 
                                           
                                           = 
                                           0 
                                         
                                       
                                       ) 
                                     
                                   
                                 
                               
                             
                           
                         
                       
                     
                   
                 
               
               
                 
                   [ 
                   
                     Expression 
                      
                     
                         
                     
                      
                     4 
                   
                   ] 
                 
               
             
           
         
       
     
         [0032]    In Expression 4, W D  is the weight of duration (D), W T  is the weight of activity transition (T), and W O  is the weight of observation (O). It is apparent that explicit duration information can be integrated in the model. 
         [0033]    Also, in Expression 4, d is a duration variable, t 1  and t 2  are time variables, IA is a label of unknown activities, m y  is an average duration, and y is a label value of an expected activity having the average duration m y . 
         [0034]    As can be seen from the above expressions, an exemplary embodiment of the present invention uses a bell-shaped probability function for duration modeling. The shape of the probability function is shown in  FIG. 2 . Graphs  21 ,  22  and  23  shown in  FIG. 2  show probability function shapes having different means and standard deviations (sd) of durations (15, 1), (10, 2) and (5, 2), respectively. 
         [0035]    Together with definition of the model, measurement of an increase or decrease of a parameter is performed using Expression 5, Expression 6 and Expression 7 below. 
         [0000]    
       
         
           
             
               
                 
                   
                       
                   
                    
                   
                     Gradient 
                      
                     
                         
                     
                      
                     of 
                      
                     
                         
                     
                      
                     Activity 
                      
                     
                         
                     
                      
                     Transition 
                      
                     
                         
                     
                      
                     Weight 
                   
                 
               
               
                 
                   [ 
                   
                     Expression 
                      
                     
                         
                     
                      
                     5 
                   
                   ] 
                 
               
             
             
               
                 
                   
                       
                   
                    
                   
                     
                       
                          
                         
                           Z 
                           X 
                         
                       
                       
                          
                         
                           
                             w 
                             T 
                           
                            
                           
                             ( 
                             
                               
                                 y 
                                 ′ 
                               
                               , 
                               y 
                             
                             ) 
                           
                         
                       
                     
                     = 
                     
                       
                         ∑ 
                         
                           t 
                           = 
                           1 
                         
                         T 
                       
                        
                       
                         
                           γ 
                            
                           
                             ( 
                             
                               
                                 y 
                                 ′ 
                               
                               , 
                               t 
                             
                             ) 
                           
                         
                          
                         
                           β 
                            
                           
                             ( 
                             
                               y 
                               , 
                               
                                 t 
                                 + 
                                 1 
                               
                             
                             ) 
                           
                         
                          
                         
                            
                           
                             
                               Q 
                               T 
                             
                              
                             
                               ( 
                               
                                 
                                   y 
                                   ′ 
                                 
                                 , 
                                 y 
                               
                               ) 
                             
                           
                         
                       
                     
                   
                 
               
               
                 
                     
                 
               
             
             
               
                 
                   
                       
                   
                    
                   
                     Gradient 
                      
                     
                         
                     
                      
                     of 
                      
                     
                         
                     
                      
                     Duration 
                      
                     
                         
                     
                      
                     Weight 
                   
                    
                   
                       
                   
                 
               
               
                 
                   [ 
                   
                     Expression 
                      
                     
                         
                     
                      
                     6 
                   
                   ] 
                 
               
             
             
               
                 
                   
                       
                   
                    
                   
                     
                       
                         
                           
                              
                             
                               Z 
                               X 
                             
                           
                           
                              
                             
                               
                                 w 
                                 D 
                               
                                
                               
                                 ( 
                                 y 
                                 ) 
                               
                             
                           
                         
                         = 
                         
                           
                             ∑ 
                             
                               d 
                               = 
                               1 
                             
                             D 
                           
                            
                           
                             
                               ∑ 
                               
                                 t 
                                 = 
                                 1 
                               
                               T 
                             
                              
                             
                               θ 
                                
                               
                                 ( 
                                 
                                   y 
                                   , 
                                   t 
                                   , 
                                   d 
                                 
                                 ) 
                               
                             
                           
                         
                       
                       , 
                       
                           
                       
                        
                       where 
                     
                      
                     
                        
                     
                      
                     
                         
                     
                      
                     
                       
                         θ 
                          
                         
                           ( 
                           
                             y 
                             , 
                             t 
                             , 
                             d 
                           
                           ) 
                         
                       
                       = 
                       
                         ( 
                         
                           
                             
                               
                                 
                                   
                                     λ 
                                      
                                     
                                       ( 
                                       
                                         y 
                                         , 
                                         
                                           t 
                                           - 
                                           1 
                                         
                                       
                                       ) 
                                     
                                   
                                    
                                   
                                     ζ 
                                      
                                     
                                       ( 
                                       
                                         y 
                                         , 
                                         
                                           t 
                                           + 
                                           d 
                                         
                                       
                                       ) 
                                     
                                   
                                    
                                   
                                      
                                     
                                       G 
                                        
                                       
                                         ( 
                                         
                                           y 
                                           , 
                                           t 
                                           , 
                                           
                                             t 
                                             + 
                                             d 
                                             - 
                                             1 
                                           
                                         
                                         ) 
                                       
                                     
                                   
                                 
                                 + 
                               
                             
                           
                           
                             
                               
                                 
                                   
                                     ζ 
                                      
                                     
                                       ( 
                                       
                                         y 
                                         , 
                                         
                                           t 
                                           + 
                                           d 
                                         
                                       
                                       ) 
                                     
                                   
                                    
                                   
                                      
                                     
                                       
                                         
                                           Q 
                                           O 
                                         
                                          
                                         
                                           ( 
                                           
                                             IA 
                                             , 
                                             1 
                                             , 
                                             
                                               t 
                                               - 
                                               1 
                                             
                                           
                                           ) 
                                         
                                       
                                       + 
                                       
                                         G 
                                          
                                         
                                           ( 
                                           
                                             y 
                                             , 
                                             t 
                                             , 
                                             
                                               t 
                                               + 
                                               d 
                                               - 
                                               1 
                                             
                                           
                                           ) 
                                         
                                       
                                     
                                   
                                 
                                 + 
                               
                             
                           
                           
                             
                               
                                 
                                   
                                     λ 
                                      
                                     
                                       ( 
                                       
                                         y 
                                         , 
                                         
                                           t 
                                           - 
                                           1 
                                         
                                       
                                       ) 
                                     
                                   
                                    
                                   
                                      
                                     
                                       
                                         G 
                                          
                                         
                                           ( 
                                           
                                             y 
                                             , 
                                             t 
                                             , 
                                             
                                               t 
                                               + 
                                               d 
                                               - 
                                               1 
                                             
                                           
                                           ) 
                                         
                                       
                                       + 
                                       
                                         
                                           Q 
                                           O 
                                         
                                          
                                         
                                           ( 
                                           
                                             IA 
                                             , 
                                             
                                               t 
                                               + 
                                               d 
                                             
                                             , 
                                             T 
                                           
                                           ) 
                                         
                                       
                                     
                                   
                                 
                                 + 
                               
                             
                           
                           
                             
                               
                                  
                                 
                                   
                                     
                                       Q 
                                       O 
                                     
                                      
                                     
                                       ( 
                                       
                                         IA 
                                         , 
                                         1 
                                         , 
                                         
                                           t 
                                           - 
                                           1 
                                         
                                       
                                       ) 
                                     
                                   
                                   + 
                                   
                                     G 
                                      
                                     
                                       ( 
                                       
                                         y 
                                         , 
                                         t 
                                         , 
                                         
                                           t 
                                           + 
                                           d 
                                           - 
                                           1 
                                         
                                       
                                       ) 
                                     
                                   
                                   + 
                                   
                                     
                                       Q 
                                       O 
                                     
                                      
                                     
                                       ( 
                                       
                                         IA 
                                         , 
                                         
                                           t 
                                           + 
                                           d 
                                         
                                         , 
                                         T 
                                       
                                       ) 
                                     
                                   
                                 
                               
                             
                           
                         
                         ) 
                       
                     
                   
                 
               
               
                 
                     
                 
               
             
             
               
                 
                   
                       
                   
                    
                   
                     
                       G 
                        
                       
                         ( 
                         
                           y 
                           , 
                           t 
                           , 
                           
                             t 
                             + 
                             d 
                             - 
                             1 
                           
                         
                         ) 
                       
                     
                     = 
                     
                       
                         
                           Q 
                           O 
                         
                          
                         
                           ( 
                           
                             y 
                             , 
                             t 
                             , 
                             
                               t 
                               + 
                               d 
                               - 
                               1 
                             
                           
                           ) 
                         
                       
                       + 
                       
                         
                           Q 
                           D 
                         
                          
                         
                           ( 
                           
                             y 
                             , 
                             d 
                           
                           ) 
                         
                       
                     
                   
                 
               
               
                 
                     
                 
               
             
             
               
                 
                   
                       
                   
                    
                   
                     Gradient 
                      
                     
                         
                     
                      
                     of 
                      
                     
                         
                     
                      
                     Observation 
                      
                     
                         
                     
                      
                     Weight 
                   
                 
               
               
                 
                   [ 
                   
                     Expression 
                      
                     
                         
                     
                      
                     7 
                   
                   ] 
                 
               
             
             
               
                 
                   
                       
                   
                    
                   
                     
                       
                         
                           
                              
                             
                               Z 
                               X 
                             
                           
                           
                              
                             
                               
                                 w 
                                 O 
                               
                                
                               
                                 ( 
                                 
                                   y 
                                   , 
                                   o 
                                 
                                 ) 
                               
                             
                           
                         
                         = 
                         
                           
                             ∑ 
                             
                               
                                 
                                   i 
                                   , 
                                   t 
                                   , 
                                   d 
                                 
                                 
                                   
                                     x 
                                     i 
                                   
                                   = 
                                   o 
                                 
                               
                               
                                 i 
                                 ∈ 
                                 
                                   [ 
                                   
                                     t 
                                     , 
                                     
                                       t 
                                       + 
                                       d 
                                       - 
                                       1 
                                     
                                   
                                   ] 
                                 
                               
                             
                           
                            
                           
                             θ 
                              
                             
                               ( 
                               
                                 y 
                                 , 
                                 t 
                                 , 
                                 d 
                               
                               ) 
                             
                           
                         
                       
                       , 
                       and 
                     
                      
                     
                       
 
                     
                      
                     
                         
                     
                      
                     
                       
                         
                           
                              
                             
                               Z 
                               X 
                             
                           
                           
                              
                             
                               
                                 w 
                                 O 
                               
                                
                               
                                 ( 
                                 
                                   IA 
                                   , 
                                   o 
                                 
                                 ) 
                               
                             
                           
                         
                         = 
                         
                           
                             ∑ 
                             
                               
                                 t 
                                 = 
                                 1 
                               
                               
                                 
                                   x 
                                   i 
                                 
                                 = 
                                 o 
                               
                             
                             T 
                           
                            
                           
                             v 
                              
                             
                               ( 
                               t 
                               ) 
                             
                           
                         
                       
                       , 
                       where 
                     
                      
                     
                       
 
                     
                      
                     
                       
                         v 
                          
                         
                           ( 
                           t 
                           ) 
                         
                       
                       = 
                       
                         ( 
                         
                           
                             
                               
                                 
                                   
                                     ∑ 
                                     
                                       y 
                                       ′ 
                                     
                                   
                                    
                                   
                                     
                                       ∑ 
                                       y 
                                     
                                      
                                     
                                       
                                         α 
                                          
                                         
                                           ( 
                                           
                                             
                                               y 
                                               ′ 
                                             
                                             , 
                                             
                                               t 
                                               - 
                                               1 
                                             
                                           
                                           ) 
                                         
                                       
                                        
                                       
                                         β 
                                          
                                         
                                           ( 
                                           
                                             y 
                                             , 
                                             
                                               t 
                                               + 
                                               1 
                                             
                                           
                                           ) 
                                         
                                       
                                        
                                       
                                          
                                         
                                           
                                             
                                               Q 
                                               T 
                                             
                                              
                                             
                                               ( 
                                               
                                                 
                                                   y 
                                                   ′ 
                                                 
                                                 , 
                                                 y 
                                               
                                               ) 
                                             
                                           
                                           + 
                                           
                                             
                                               Q 
                                               O 
                                             
                                              
                                             
                                               ( 
                                               
                                                 IA 
                                                 , 
                                                 t 
                                                 , 
                                                 t 
                                               
                                               ) 
                                             
                                           
                                         
                                       
                                     
                                   
                                 
                                 + 
                               
                             
                           
                           
                             
                               
                                 
                                   
                                     α 
                                      
                                     
                                       ( 
                                       
                                         
                                           y 
                                           ′ 
                                         
                                         , 
                                         
                                           t 
                                           - 
                                           1 
                                         
                                       
                                       ) 
                                     
                                   
                                    
                                   
                                      
                                     
                                       
                                         Q 
                                         O 
                                       
                                        
                                       
                                         ( 
                                         
                                           IA 
                                           , 
                                           t 
                                           , 
                                           T 
                                         
                                         ) 
                                       
                                     
                                   
                                 
                                 + 
                               
                             
                           
                           
                             
                               
                                 
                                   
                                     β 
                                      
                                     
                                       ( 
                                       
                                         y 
                                         , 
                                         
                                           t 
                                           + 
                                           1 
                                         
                                       
                                       ) 
                                     
                                   
                                    
                                   
                                      
                                     
                                       
                                         Q 
                                         O 
                                       
                                        
                                       
                                         ( 
                                         
                                           IA 
                                           , 
                                           1 
                                           , 
                                           t 
                                         
                                         ) 
                                       
                                     
                                   
                                 
                                 + 
                               
                             
                           
                           
                             
                               
                                  
                                 
                                   
                                     Q 
                                     O 
                                   
                                    
                                   
                                     ( 
                                     
                                       IA 
                                       , 
                                       1 
                                       , 
                                       T 
                                     
                                     ) 
                                   
                                 
                               
                             
                           
                         
                         ) 
                       
                     
                   
                 
               
               
                 
                     
                 
               
             
           
         
       
     
         [0036]    The functions α, λ, γ, β, η and ζ in Expression 5, Expression 6 and Expression 7 can be obtained by Expression 8 below. 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       α 
                        
                       
                         ( 
                         
                           y 
                           , 
                           t 
                         
                         ) 
                       
                     
                     = 
                     
                       
                         
                           α 
                            
                           
                             ( 
                             
                               y 
                               , 
                               
                                 t 
                                 - 
                                 1 
                               
                             
                             ) 
                           
                         
                          
                         
                            
                           
                             
                               Q 
                               O 
                             
                              
                             
                               ( 
                               
                                 IA 
                                 , 
                                 t 
                                 , 
                                 t 
                               
                               ) 
                             
                           
                         
                       
                       + 
                       
                         γ 
                          
                         
                           ( 
                           
                             y 
                             , 
                             t 
                           
                           ) 
                         
                       
                     
                   
                    
                   
                     
 
                   
                    
                   
                     
                       λ 
                        
                       
                         ( 
                         
                           y 
                           , 
                           t 
                         
                         ) 
                       
                     
                     = 
                     
                       
                         ∑ 
                         
                           y 
                           ′ 
                         
                       
                        
                       
                         
                           α 
                            
                           
                             ( 
                             
                               
                                 y 
                                 ′ 
                               
                               , 
                               t 
                             
                             ) 
                           
                         
                          
                         
                            
                           
                             
                               Q 
                               T 
                             
                              
                             
                               ( 
                               
                                 
                                   y 
                                   ′ 
                                 
                                 , 
                                 y 
                               
                               ) 
                             
                           
                         
                       
                     
                   
                    
                   
                     
 
                   
                    
                   
                     
                       γ 
                        
                       
                         ( 
                         
                           y 
                           , 
                           t 
                         
                         ) 
                       
                     
                     = 
                     
                       
                         ∑ 
                         
                           d 
                           = 
                           1 
                         
                         D 
                       
                        
                       
                         ( 
                         
                           
                             
                               
                                 
                                   
                                     λ 
                                      
                                     
                                       ( 
                                       
                                         y 
                                         , 
                                         
                                           t 
                                           - 
                                           d 
                                         
                                       
                                       ) 
                                     
                                   
                                    
                                   
                                      
                                     
                                       G 
                                        
                                       
                                         ( 
                                         
                                           y 
                                           , 
                                           
                                             t 
                                             - 
                                             d 
                                             + 
                                             1 
                                           
                                           , 
                                           t 
                                         
                                         ) 
                                       
                                     
                                   
                                 
                                 + 
                               
                             
                           
                           
                             
                               
                                  
                                 
                                   
                                     
                                       Q 
                                       O 
                                     
                                      
                                     
                                       ( 
                                       
                                         IA 
                                         , 
                                         1 
                                         , 
                                         
                                           t 
                                           - 
                                           d 
                                         
                                       
                                       ) 
                                     
                                   
                                   + 
                                   
                                     G 
                                      
                                     
                                       ( 
                                       
                                         y 
                                         , 
                                         
                                           t 
                                           - 
                                           d 
                                           + 
                                           1 
                                         
                                         , 
                                         t 
                                       
                                       ) 
                                     
                                   
                                 
                               
                             
                           
                         
                         ) 
                       
                     
                   
                    
                   
                     
 
                   
                    
                   
                     
                       β 
                        
                       
                         ( 
                         
                           y 
                           , 
                           t 
                         
                         ) 
                       
                     
                     = 
                     
                       
                         
                           β 
                            
                           
                             ( 
                             
                               y 
                               , 
                               
                                 t 
                                 + 
                                 1 
                               
                             
                             ) 
                           
                         
                          
                         
                            
                           
                             
                               Q 
                               O 
                             
                              
                             
                               ( 
                               
                                 IA 
                                 , 
                                 t 
                                 , 
                                 t 
                               
                               ) 
                             
                           
                         
                       
                       + 
                       
                         η 
                          
                         
                           ( 
                           
                             y 
                             , 
                             t 
                           
                           ) 
                         
                       
                     
                   
                    
                   
                     
 
                   
                    
                   
                     
                       η 
                        
                       
                         ( 
                         
                           y 
                           , 
                           t 
                         
                         ) 
                       
                     
                     = 
                     
                       
                         ∑ 
                         
                           d 
                           = 
                           1 
                         
                         D 
                       
                        
                       
                         ( 
                         
                           
                             
                               
                                 
                                   
                                     ζ 
                                      
                                     
                                       ( 
                                       
                                         y 
                                         , 
                                         
                                           t 
                                           + 
                                           d 
                                         
                                       
                                       ) 
                                     
                                   
                                    
                                   
                                      
                                     
                                       G 
                                        
                                       
                                         ( 
                                         
                                           y 
                                           , 
                                           t 
                                           , 
                                           
                                             t 
                                             + 
                                             d 
                                             - 
                                             1 
                                           
                                         
                                         ) 
                                       
                                     
                                   
                                 
                                 + 
                               
                             
                           
                           
                             
                               
                                  
                                 
                                   
                                     G 
                                      
                                     
                                       ( 
                                       
                                         y 
                                         , 
                                         t 
                                         , 
                                         
                                           t 
                                           + 
                                           d 
                                           - 
                                           1 
                                         
                                       
                                       ) 
                                     
                                   
                                   + 
                                   
                                     
                                       Q 
                                       O 
                                     
                                      
                                     
                                       ( 
                                       
                                         IA 
                                         , 
                                         
                                           t 
                                           + 
                                           d 
                                         
                                         , 
                                         T 
                                       
                                       ) 
                                     
                                   
                                 
                               
                             
                           
                         
                         ) 
                       
                     
                   
                    
                   
                     
 
                   
                    
                   
                     
                       ζ 
                        
                       
                         ( 
                         
                           y 
                           , 
                           t 
                         
                         ) 
                       
                     
                     = 
                     
                       
                         ∑ 
                         
                           y 
                           ′ 
                         
                       
                        
                       
                         
                           β 
                            
                           
                             ( 
                             
                               
                                 y 
                                 ′ 
                               
                               , 
                               t 
                             
                             ) 
                           
                         
                          
                         
                            
                           
                             
                               Q 
                               T 
                             
                              
                             
                               ( 
                               
                                 y 
                                 , 
                                 
                                   y 
                                   ′ 
                                 
                               
                               ) 
                             
                           
                         
                       
                     
                   
                 
               
               
                 
                   [ 
                   
                     Expression 
                      
                     
                         
                     
                      
                     8 
                   
                   ] 
                 
               
             
           
         
       
     
         [0037]      FIG. 3  is a block diagram illustrating an example of activity recognition to which a semi-Markov CRF model according to an exemplary embodiment of the present invention is applied according to an exemplary embodiment of the present invention. 
         [0038]    When an input signal  31  for training or testing measured by an accelerometer is input to a sliding window  32  (operation  31 ), the sliding window  32  segments the input signal into frame sequences  33  (operation  32 ). The sliding window  32  segments the input signal  31  using the Hamming function. The Hamming function is frequently used for filter design, and serves to receive a factor which is a number and segment a signal. 
         [0039]    A feature extractor  34  extracts feature vectors from the segmented frame sequences  33  (operation  33 ). The extracted feature vectors are provided to a vector quantizer  35  (operation  34 ). 
         [0040]    The vector quantizer  35  receives and combines the feature vectors with a kernel vector  38 , thereby constructing a discrete input sequence (operation  35 ). The discrete input sequence is provided to a semi-Markov CRF unit  36 . In a training phase, a manual state label set is required when there is an additional input to the semi-Markov CRF unit  36 . 
         [0041]    On the basis of the discrete input sequence received from the vector quantizer  35 , the semi-Markov CRF unit  36  can capture an activity transition by Expression 1 to Expression 8 and output a recognition result. 
         [0042]    Meanwhile, the kernel vector  38  input to the vector quantizer  35  together with the feature vector is generated through a separate process, which will be described below with reference to  FIG. 4 . 
         [0043]    When a training input signal  41  is input to the sliding window  32 , the sliding window  32  generates one set of frames from the input signal and provides the generated frames to the feature extractor  34 . The feature extractor  34  extracts feature vectors  42  from the one set of frames. 
         [0044]    The extracted feature vectors  42  are provided to a clustering unit  43 , and the clustering unit  43  collects the input feature vectors  42  to generate the kernel vector  38 . 
         [0045]    The generated kernel vector  38  is provided to the vector quantizer  35  of  FIG. 3 , and in the vector quantizer  35 , feature vectors are quantized by the most similar kernel vector. 
         [0046]    As a result, in an exemplary embodiment of the present invention, inference from sequential feature vectors and training by kernel vectors are simultaneously and rapidly performed, so that an activity transition recognition result can be output. 
         [0047]      FIG. 5  is a flowchart illustrating a process of calculating Z of Expression 2 according to an exemplary embodiment of the present invention. 
         [0048]    The probability P(S|X) of a label state sequence can be calculated by Expression 2 as mentioned above. See Expression 2. 
         [0000]    
       
         
           
             
               P 
                
               
                 ( 
                 
                   S 
                   | 
                   X 
                 
                 ) 
               
             
             = 
             
               
                 
                   ∏ 
                   
                     i 
                     - 
                     1 
                   
                   P 
                 
                  
                 
                   Ψ 
                    
                   
                     ( 
                     
                       
                         s 
                         
                           i 
                           - 
                           1 
                         
                       
                       , 
                       
                         s 
                         i 
                       
                       , 
                       X 
                     
                     ) 
                   
                 
               
               
                 Z 
                 X 
               
             
           
         
       
     
         [0049]    As mentioned above, the function P(S|X) requires the function Z x , which is calculated by the following equation: 
         [0000]    
       
         
           
             
               Z 
               X 
             
             = 
             
               
                 ∑ 
                 
                   S 
                   ′ 
                 
               
                
               
                 
                   ∏ 
                   
                     i 
                     = 
                     1 
                   
                   
                     P 
                     ′ 
                   
                 
                  
                 
                     
                 
                  
                 
                   
                     Ψ 
                      
                     
                       ( 
                       
                         
                           s 
                           
                             i 
                             - 
                             1 
                           
                           ′ 
                         
                         , 
                         
                           s 
                           i 
                           ′ 
                         
                         , 
                         X 
                       
                       ) 
                     
                   
                   . 
                 
               
             
           
         
       
     
         [0050]    A process of calculating the function Z x  is illustrated in a flowchart of  FIG. 5 . 
         [0051]    Referring to  FIG. 5 , when a current time t exceeds a reference value T, Z is directly calculated. On the other hand, when the current time t is the reference value T or less, the function ψ is calculated for each time band to sequentially perform ΣΠ operation. 
         [0052]    To this end, first, operations  501 ,  502 , and  504  constitute a loop with the variable t. Also, operations  506 ,  507 , and  510  constitute a loop with a variable d, and operations  508 ,  512 , and  514  constitute a loop with a variable y′. In operations  509  and  513 , the functions α, γ and λ are calculated by Expression 8, and in operation  515 , the standardized factor Z is calculated. 
         [0053]    As apparent from the above description, in activity recognition using an accelerometer according to an exemplary embodiment of the present invention, training and inference are simultaneously performed in a semi-Markov CRF. Thus, an activity transition can be effectively captured for a long duration. 
         [0054]    It will be apparent to those skilled in the art that various modifications and variations can be made in the present invention without departing from the spirit or scope of the invention. Thus, it is intended that the present invention covers the modifications and variations of this invention provided they come within the scope of the appended claims and their equivalents.