thesis

                                ...

0 downloads 112 Views 3MB Size
       

              



                    !   !        ! "  #    $

%&  ' (    !)' !  *'  !  ( ! +  ! ,  '       -(   !     ! &      '  

   & 

  & .( /  " '   (  ' ( ,!  ( #0  (   (          (  0    .   .  !  (   (      ! ''        ! ' ./ &        ,! #0  ' ( & '  !  ,! + 1   ( ,! +( 2' !  (  3' ' &   ( .   ( *     (4    0  &   / ,! '   !    ! ''   (     '  ./ &  / '    ( ' .!    !    (   / '    ( !    ' (   ( & .(   

'(   !  . 

   &  (       .  '  (    ! '   & .( /   /   ''   '      ((  (  '    ( ' .! !    (  



                                              5 $ 9

-  1                        3  +                          6    1  7 5+ 8 0              -'  #     :      8.                      

    

    

    

    

    

    

    

    

    

    

    

    

    

    

    

    

 5 9 ;

                          

5

$

9

=

2 .( (  +.  (         '  3  (  (           3  3                   "                      5 /                     $   3                 '                       5 ' '                 5 +!'  '              #  (  (              $ % !                     $ +    (  (          $5   ./                $$  :               $9   ./ ! > .          $=  #                $; (( / (             $< & !'     #       $ & (  6                 3  &' +    ( ,!'  %  9 3  &' +                9  '/    ! 3  +     95 ,!'  %             +   (                

                       

                       

                       

                       

                       

                       

                       

                       

                       

                       

                       

                       

                       

                       

                       

                       

                       

                       

                       

9 <   5 9 < <  5 5 55 5= 5 $ $ $ $$ $$ $9 $= $; 9 95

                         !! 5 5 55

& (                                           1 ( >/                                           '                                       

99 9= 9<

5$ 59 5= 5; 5<

55    &' '     55 1              555 #Æ   !'  % '  55$   3( &         559   3( '         ( -'  #           0                ,  )          %"'                   +   (           

         

         

         

         

         

         

         

         

         

         

         

         

         

         

         

         

         

         

         

         

         

         

         

         

9< 9 = = = =$ == = ; ;

 " #$ %   %                                & $

$

$5

$$ $9

,( "  (                    $ - "  (                $ % '   ,'    % # '                                   $ ./ ?  ! '   ( ' (    $       !  '  ! '     %"'  1                       $5 % ' ( +   3               $5 ./ ?   '   ( ' (    $55       '  ! '     #                              +   (                    

           

           

           

           

           

           

           

           

           

           

           

           

           

           

           

;5 ;5 ;$ ;9 ;9 ;<  .   ./         ( !  (              !  (        .   '  . !  ./    >    ' ! "     (   7  '        5 %" '     "    (     ! '       ( .   (       ! $ #6     ( &   $ . (    /  '(    '"  ! -   '( !    "   ! /       (    '           ( !  (      '   ( (    9  (  !     (   ' %"'       '/ (  

  ( &   = .   

 !     !  0     . 

 ,# !'./        '  ( "'    (     (  (  ' &   ; .   '      :   ( '   !'        ' ( >  (    < .  ''        !    ( !   



 

           >    *  ! .  !'      ( '( ' 4   ( ! ( ' ( ! ' '     @&A    (( .  (    (   (    / ( '   ( ( 3 '   (    L!'    ! '   ( .    (   ( '  *   '  '    '   ((  (/   ( ' (((  '  ( " (     !      (   '   !'     ? (       (     "  ( !' '  (  '     

(       

 ? !  "  &   )  !   ( !  "        ( '          (( ! '  .             (           ( !   ('      ( ''        (( !'  4  # )   !   !      '  (          ' . !     . !  (   !'    '   ' *       /   !              @     (A  (  @!  )A 3  "  

   (     (  

       ! !  > .   ()   !     D -     '   ' *    ! !  (     ( '  .        !    '  ( !      '      ( "        ( .  !  (        (   !.  ! D



 ,D  ' !  !   (    

' !   @!  $9 ( )

( (. A  ( ' !  !          '  '    . 

((

 ,      !   

'  D 3  !     ( '    (

 '  '      (     ( !    '   '    (     ( 7

 3  " D    ! !   (  4 (    ? !  "   8  D 3  '     ((     0  &  ' .    !  ' !  '   

(   ! 

 &'    D 3  ' (   ! (4       

'?   

"

 &' 

 (   D >  '  !'( !        @   

(     (    A  (

'

    @     A 4 

  !  !    '    (  '  !  (         B;C B5C '  ( '   '   !    ! G    ')( (    ' .   '      '        !    !         B59C   (      (    ! !          . '      .   '         !    '        

   B

C B$C B=   $  (    !  (        !  (    ( '    ! '       0        '( (   

(    5 +  0       ' (  (  0  .  '       !' ( )     (   ! '      ( '    (   3  (     .(   .       '  .   '    )(     E! F  E  ! F  *  !  (      !  !.  '  

5

  7 !' ' @        A   !  0  ! .      ( ! .      @(  ( A &     !  !.  !  0  ! .         (         ! '  (  ' !  (     * '       '  (  !      '  .     !   ' ( .      !  (    * (    (  '   !  (Æ   >  (    ' (      ( .          G ! . (   (    ' !        '(    * (  . ( > . "     *  (  !  !'          ' > !   ' (   ' (    !.   G ' ' (    

 (  2 .( ( ' (D   ( ' (  ( (( ' / .( ! .         !     (        . !  !   3     D   ' '  ) (    !   . "   ' .  .      (   (    (   5 '  '   ' (D & '  '      ((    !  !    (  (    !    .   !  !    

  

 .    '  (   (     ' ( ! (    $ #  ( ' (D &    '  '       @ ' A   ( !'    !    '    ''7  '  (    ./ ! !  (      ' .   !   . . (   '    (     !        !.(   . !  ) ' (  (  (  !    (   >  .  !  '  ' (    =

$

  D #  7  ! ' ( ! !  (      '

   

    

 

    !  %&  ' -     %    

"  !  # $ ' "()  *     & +'")*, ! ! $  &  ! "  . / 0   !  1 2    ##

     6  ! *      8 8  ' 9    +'9, :(   3    +3, 0 !  %  



             

3 4  !   . 5# 6 

         77 "         (   $$ 6  !         5 %  '9   :   5 8  :( - 4     ;/ 3       3 .    !   #

$ #%& '(&  ' #

 &

&    !  (   ' (  (( (    (( !'    ? / .( ! ' !  &   

'  .  '   (   

!  !  !   (     3 "'  !  !     ' .  .    ''          (  '       . !     (     (    (    3  !      '  "  ( )   !   ((   ( )( (   ((  # )         (  (  ! (    8   ' .         (Æ       / .(   !     4  &!    ( ( @   A  ' !  (  !   (      &!        '  '  !      (Æ   "  (     (  !   (4      '    '       8     (      !  ./ .  (    !  !     (       (   B5C      / .( ( ' (  (  !    '    !   !  #       ! 

9

 ((   ! ( 

+,    .     ' '        '       !  (   ' ( >   (((   ! (  '    '"      ' ! ' !  (   ./   

   (

        . ! "   ' (  ( (   '  (   ! !   

9$



        !  >    ' ! "     ( !  . ('   '    '  *  (  '  0  3   '   '    !'(     '       !' 1   .     !'   ' (  

  .  (  #Æ   !'    ' ( !'    !  (     ()  " '  ," '       '       (    "  '  0     ' *         ( !'  "  ( 0     ' (   ./ >   ( ' (    7 $  (   ! #'   6  %"'    .  '       (     "  ( B;C  (   7( .           '  0  B ( +    7 '            ' *  ! !    () (   '  0  8 "'    .  '        (   ' (   ./ .        



%& 0 1

  O  ? '  ./ B B C (     (      (   7   3  '  ' !     (  '       B= C .   ' 7(      #  ( !         '  !   '  !    "'   

     

 "      '  !  !'    

"'   (  7(  %    '   (      (     '   (    '  !   #     () (   (       .     '   #     () (   (( *  !          (     .    0  

!        

  ( (   (   ./ .   "' !        0           ./   (    ! '  0   (    '   ! (4   !   '   ( !            "' !      ./   (    ! '  0  8 "'    .    '  ! 0  (    7 

9;

1   &(  ( /  (  8+%#&8  ' B; C       ' (   /        ' (   ! !       ! ( '   ' .       '(     '   '          ' 8 0   '((    ! ' 7(   (      '(   ' (

(      *  %"'    (  '  

( 

 /  0  (    ( (. '   /  ( O BC "  (   '    7    ( !  "   .  ' '    '((  ' 0  ! '  ' ( '  @.  (       !   A  '  '0 (4   .     (  ' (   .   ' (  "  '  0  !'  ' *  .   ( (. '  B; C  (   /     BC         ( !'  "  ( '  0    / .(  '(  *( !  "   ! '  0    ('  ) / .(   ( ! Æ    



   

    ( '

    !  0  . '  ' !'     . 

 !' '   8 '  '    '    ' *  .  

   A   ' ( )      !'

!'   ' 3   ! !' @

'

   '    !'    1        ' (   !' #Æ   !'  ' ( !   ' (    Æ   !' '  !        (  (    '  )( .    ' (  ( !  (4  '     .  . !'  !.     (    '0     '  '    '

     .       '    !'(     !' ( (  BC .  "      !      '    !' !   !' .  '  '   !' !

9<

   !  )(  () ( 

@G  @A @AA K    @U @AA  @!@AA  " #

 K  @ @$#AA @A  ( ! K @#  A! H @"  A!% 

 (    '     .  I   '   !    .   "    (  

.

 ' 

         ( !' .   !    "  ' (  '   ! . "     % ( (    .    (   ! "  @

('  

K 5 !   'AD

  @A   @#"A

U K

     '    ' 

 

 

     (   !  

   '   (   !  

 @A

 @A  (  '   8    !' ! 

!    !    ( (  BC   '7( - D



 &  @ A  &   @ A !    @! A    ! ' 

 @U A











 !  )(  (        '  .  .  "    1

 (  (  (  !     !       







#   



  (  /  

 (    

  '        ((  ( 

        ((

2  !

 '   ! '      !'  !' (    '    '  ! (4   .   !    ! (   (   ' '          !   '   (       '   '(    (  !

 

1     !' (0  !'  ' ( !'   ) 

  .     '  (   )    '   %       (  9

  (0    .  .       (   (  (  (0     (  ( 1 '           ! ) (    !    !'     @( (   (  ( ( '    ( ( ' A !       ''  .       ! '     !   /      '  .  (        " (     ' ( !'    ? '    !'  (       !    .         8   '        (4 '       ' ( '        ( !      ) !' !  !'   . ( )(   '  '   '(     !'   '      ( !' !   !  '          !   ! )       '  '       !  ' (  ! '      (   ((        ! '     7(  Æ   '    (  !   '   ! (  B C



)Æ       

3    ! ' (     Æ   !'   . '   ' (  

       !' (  (   ' (      #   (  

A .  % K    .     (   !    (  !  " .    @   "    ( !   @V    V A %  @   A  '(   Æ   !'     @W    W A  (    6

    



   /   V H )! H V 





V

   V W  K





W

.    

* (       '   ( BC (          (

    '        Æ   !'  '  

=

  (!

'  ' "

/   (       )!   ()     (   !  



 +  @A K   @A    ,-

 ' ! ''   '( 



. A K   @A    @W WA  + @A H +  @W WA  +  @A  +  @W WA @

 Æ   !'  '   ' '7

.   ' (        

(    

 

   .    ' ( Æ  '    '  )(    !  !    ' 

)(   '  (      '  )(  /    '  )(  (  !'   !.  '      !   #   ' (    ' (     (    '  )(  (  '  )(   " )     '( #    .  (      )    '  '    )  '    '    (   )    '        ! E  ' (F      

%

    

     

    '  )(

.!  

 ' (    !  !' '   >    

  (   .    '' (  (

A  ( @   A     ' ' !  !.      )( !  @  

  (    !  ' (  

(0       D

.!  @   A  .!  @  A / @.!  @   A .!  @   AA 







=



.



         ( '   ( ! '  '    !

    '  ' ( '        ( 

.0  

  (4   

(

  !   ' (    '   '   !' H  !    

.0  

 / .  ( '         (   Æ   '  '( !  " !'  & (   (   '  '   (     (   '   0          '  '    (      '  )(  (  0     '   ' (   '   . (   & ((   !  0  '         "  !'    ( )(  (         * "'    '  )(  '  !' 3 5 . !' !'  ' *  !  '" #6  ( E (F  ( 3 5 .    ! '  '    +4 '     (( .  (4          '    .   (  ( '       . (     !' '  

+, ! /

+, ! 5

+, ! 7

+, ! 

+, ! .

+!, ! 7

+, ! 

+, ! /

+ , ! .

+@, ! ;

+, ! /#

+, ! //

+, ! /5

+ , ! /7

+, ! .

+, ! ..

3 5D &' *  ! #6  E (F 3 59 . !' !'  ' *  ! #6  E F  ( 3 5< .    ' !'  #6  E   F 3 5= .    ! '  '    +4

=

+, ! /

+, ! 5

+, ! 7

+, ! 

+, ! .

+!, ! 7

+, ! 

+, ! /

+ , ! .

+@, ! ;

+, ! /#

+, ! //

+, ! /5

+ , ! /7

+, ! .

+, ! ..

3 5D   '   !  ' *  E (F @" !  ' '    (( .  '    ( (4    (( .  (4  A

+, ! /

+, ! 5

+, ! 7

+, ! 

+, ! .

+!, ! 7

+, ! 

+, ! /

+ , ! .

+@, ! ;

+, ! /#

+, ! //

+, ! /5

+ , ! /7

+, ! .

+, ! ..

3 55D %"  ( (  ( '   !' ' *  E (F

=5

Gestural Motion Trajectories

Gestural Motion Trajectories

120

Gestural Motion Trajectories

120

Gestural Motion Trajectories

120

palm1 palm2

Gestural Motion Trajectories

120

palm1 palm2

120

palm1 palm2

palm1 palm2

palm1 palm2

80

80

80

80

80

80

80

60

60

60

60

60

60

40

40

40

40

40

40

20

20

20

20

20

20

0

0

0

0

0

0

20

40

60

80 X-axis

100

120

140

160

0

+, A/ A5

20

40

60

80 X-axis

100

120

140

160

0

+, A5 A7

Gestural Motion Trajectories

20

40

80 X-axis

100

120

140

160

0

+, A7 A

Gestural Motion Trajectories

120

60

20

40

80 X-axis

100

120

140

160

0

+, A A.

Gestural Motion Trajectories

120

20

40

80 X-axis

100

120

140

160

20

0 0

20

40

80 X-axis

100

120

140

160

0

80

80

80

60

60

40

40

40

40

40

40

20

20

20

20

20

20

0 20

40

60

80 X-axis

+, A. A;

100

120

140

160

0 0

20

40

60

80 X-axis

100

120

+ , A; A/#

140

160

0 0

20

40

60

80 X-axis

100

120

+@, A/# A//

140

160

0 0

20

40

60

80 X-axis

100

120

+, A// A/5

140

160

Y-axis

80

Y-axis

80

Y-axis

80

Y-axis

80

Y-axis

100

Y-axis

100

0

20

40

60

80 X-axis

100

120

+, A/5 A/7

140

160

140

160

60

40

20

0 0

120

palm1 palm2

100

0

100

palm1 palm2

100

60

80 X-axis

120

palm1 palm2

100

60

60

Gestural Motion Trajectories

120

palm1 palm2

100

60

40

+, A A/

100

60

20

Gestural Motion Trajectories

120

palm1 palm2

60

+!, A7 A

Gestural Motion Trajectories

120

palm1 palm2

60

60

40

+, A. A7

Gestural Motion Trajectories

120

palm1 palm2

60

Y-axis

100

Y-axis

100

Y-axis

100

Y-axis

100

Y-axis

100

Y-axis

Y-axis

Gestural Motion Trajectories

120

palm1 palm2 100

0

Y-axis

Gestural Motion Trajectories

120

palm1 palm2 100

0 0

20

40

60

80 X-axis

+, A/7 A.

100

120

140

160

0

20

40

60

80 X-axis

100

120

140

160

+ , A. A..

3 5$D %"  (   '  0  !' '  ! #6  E (F @   " 0   .   !'   /  A '     (( .  (4          '    .   (  ( '       . (    ' '  

3 59D &' *  ! #6  E F @ '   !    (    'A



/ %   &    %2 

  '           !' '   .   ' !  '     '   !'  ! '            7  (    ((    Æ   "   '    ! (  ( '   .(   ( .    ( '   !'  ! '  ( (   ' /    (  ( (    4  !   '      > =$

3 5=D   '   !  *   3 59 @ '   !    (    'A

3 5;D %"  ( ' (  ( '     *  ! 3 59

3 5  &% 6:     ( ( (  '     !   "  ' '7  4  !     (    '    - '"    ' (    %  ' # '    )(   /  ! ' !  "      !   /     ( ( .  '  '    '    ! /    Æ   "  ( !' ' *      ! ' (  ( '   "' (    (  '  (         '      /   '(     !  '(   "'         '  !      

   ( !'   (  " !         !      ( !'  " !   '' !     "   !  '0  ( '  " !    "' (   "   !      " (    (      '  !        "  ( !'  '  ( )(  ' (  (  " . '      '   3 5 .  ' *  !  '" #6  ( E (F  ( 3 55 .    !   ( '      '   

!

    

#  '  '      Æ   !'   

  '  (  

'      )      Æ     '  0  ! ( )( '   !        ((   ./ #Æ   !'  ! '     !'   ' ( (  *      555  Æ   !'   ! 

        (     

'  0  !  '   3 5$ .   0  !  '  ! !'   ' *  E (F    " 0   .    !'   /   3 5 .      '  !  '  0      .  /   ( )(   !  ' 

    

    '(   '  ( (   ( '     .  3 ==

Gestural Motion Trajectories

Gestural Motion Trajectories

120

120 palm1

palm1

100

100

80

80

Y-axis

Y-axis

#37 60

40

60 #29 #22 #46 #49 #40 #52 #44 40

#31 #19

#14

#34,#35 #16

#25 20

#55

20

0

0 0

20

40

60

80 X-axis

100

120

140

160

0

+,   @   !    !   !  ')  BC

20

40

60

80 X-axis

100

120

140

+,   @ ( !     !  ')  BC

Gestural Motion Trajectories

Gestural Motion Trajectories

120

120 palm2

palm2

100

100

80

80

Y-axis

Y-axis

160

60

#37

60

40

40

20

20

0

0

#22 #29 #46 #40 #49 #44 #52 #25 #19 #14

#31

#34,#35 #16 #55

0

20

40

60

80 X-axis

100

120

140

160

+,   @   !    !   !  ')  BC

0

20

40

60

80 X-axis

100

120

140

160

+,   @ ( !     !  ')  BC

3 5 D %"  (   '  0  @ '(   !  ! A ! #6  E (F

=;

5; #Æ  '  ! ' ( '    ' (   (  '  0  3 5  ( 5 .  "  ( '  0  !'  ' *  ! #6  E F  ( E   F     '  0  ! '  '   ''       . 120 Motion trajectory of palm region

100

y axis (in pixel)

80

60

40

20

0 0

20

40

60 80 100 x axis (in pixel)

120

140

160

3 5D      !   E F

120 Motion trajectory of palm region

100

y axis (in pixel)

80

60

40

20

0 0

20

40

60 80 100 x axis (in pixel)

120

140

3 5D      !   E   F

=<

160

.

 + /% 3 

> ' +  !   '     ! '     +   ('   (    

!       '    +   ( '

)         ./     ' . (. !  '     (  . (. (     (  .   ./ '/   !   (      (        (      (      ' &  '  ./ >    B=C ('   ( "    !  ' )     +  ( .(     .       (   '    7  ( ! +         '      '7  .   ( '/    !   ./  (   !  (  

 '    

'         '/   ./ !   @       "     !   A 3 5 .  +     !  "'  .     .   *  (      / *     

#1A ! '  0  "  ( !'    ' *  .       .       !  (  ( #  1  '  (  (    +    ! @

!     G         G  (     '  '  

 /   Gesture 1

40

2

integration

window lengh=20 window lengh=10

Output Layer

18 slots Hidden Layer 2 37 slots Hidden Layer 1

window lengh=5

46 slots

x y v θ

Input Layer 50 slots

3 5D #    ! +

=

4

-5  

>   ( (   ! $ #6   ! "'  %  (    !  #6  .      5  9   (  5 !'    ( .  ' 7 ! =

   J / '

!'  3 5 .   '" #6   !'  *  E (F      ( ''    !     (     %  ' *  !  $     "'    (  (   '  "   (   7 '       0  3      "'    (     7  (    #6   '    !'(       .   !' '       .  

;

!    "  (  

  ( ' 

  ( .       '  0   (  ( '

 !'    Æ   !'  

    (    

   0  

    !  (    ( 

)(  

' (   ./ 8 "'  ('      (       7( .   

    '  0 

      !  ./   ''7(  !. 3     ' (  "   '  0   ((       '  ./            '  / B; C B5;C BC '     B C  ( (. '  B; C  (   B9C        !      ( .   +    7   (   "  ( 0      '  ! 0            & .(       '        .     (         ' (      8+%#&8  ' B; C BC  (    B C

;



"   ' /    (  ( (    4  !   '      !' ' !  (     (  /  . '  (    ' (      - (      7    ! /  #  /  ! (4   !    '    '7( 1-  :    . ) (     - (       Æ   '( ' /   4         3      '    ! '   '   (   !   (  (   '(  !        ) !   '(   (   ./      '(   '      ! ' /       !  (   @ DLL...  ' (L! LA .     ! $$; ' ! ' !  !' (4       9 ' /  "  ( 

(  /  '( >   !'./ !  - '"  '( . ! ('  *     /(    (  !  '(

3    *  ! '   ( ' (    !

  )( '     (  ./  B;C

  (      

'      ( *     !  '  ! -  '"  #  !  ' '  !

'  

'   ( 

'   .   ( 

 

!' (  ' !  /(         !     (      '  

(     (     !(  ( 6  ( 

 !  '       ' ( B;C  * !      !    ( '"  '( &  ./  .    (   !'    ' ( '( ;

     7(  !. >   ! (   ! - '"  '(  ( '   '     $ .          '   (  '  !  .(    $   $5 (  "'     (         ( '(   (    $$ >  (    .  ''   $9



+  &

5

&%

&     .   ! (   !  )   - '"  '(  (     '(  (    ! /  "



3     

 (  )   '"  '(   ) (   ./   /  "

4

  .(

2 .    '"  !  )   '   !    2  2  '    &  &    .    !'    

 & K   ( &   





     (   !  @(!A !    

4 @! ('   

A   )  

'"  !' 

@4G 3A K

 &  @4G 1A K  &  @4G 1A K  &  

 









&  

@ A X



   "  Ü     Ü 

2   ( 1 (      !   / . '    ( .   '  !' ( ( !   '  (   3   ! '   - '   1    !  '  !  '   4   (  (  '  !    '   X !  K      

.

&   '"  '  @4G 1A   (!



 (  

3 K @& 1 A !   / . '     ' '    Y  (   ' (    %  ' B9$C    $ ;5



   1   4   )  !

:  (   ((  ( '   '  !  - '"  '( !'   ! (   . I (    %  ' ! '   '   # .  '   '    '"'' /(   *   ! (     1 (  ( >/ B9$C 3  ' D

 ! - '    '"  (       !.  (0  

&4  ( X @.  K  A     /( !  (    



  @4 A K   @ & @4 AA

@$A

.    ((    !   "'7   /(

   * 

5 K    K  ' '7 





  



5



 %  '    '/  '     !  '  !  - '"  '( .  .   E(F '   >      . '     !.  *    .     '  !  '  .  .   E .F '   ! .  . '    !  !   '  '     '  E(F   (      ( > .       !  . .    ( '     .    !' U 

K 5 



 @4 A 

 5 K   @

@4 A A 

@$A

 @4A (        (    (    .  !  '  .

@4A    (    (    ( '  

.

     (  ! U   7 @ 1 (  ( >/? . B9$C ! ( A

.    !.  (  *   !  '  !  '"  '(D

;$

4 

X 

K

& 



@4 A4  

@4 A 

@$5A



@4 A4  4    

@4 A 

@$$A

K

K





@4 A

 



@$9A

.

@4 A K @4  @4A&A @A





@$=A

  % 

& (  ( '   (  ! ) !  - '"  .  ./ ? ' (    '   ( ' (    !  '"  '(  (     ' (    '  ! '   *(   '(  ' (  I (  (   !.     3 (     '       B =C  ( 6  B;C

 

+# 5   "  (  +    (

 (  '  '  .  *   '   @' (   A !  '  (      - '"  .     

 D 4  @4 XA  2 @ K  A

;9

@$;A

   !  )( ( 

5 @ K  G % K   A 6 5V  K

5 6  





@$  ' @           A  (  (    =$  (  "'   (    ==

.

 # 1

>  (     .     (( ,# '( BC  (  ' /  ( '( B9C &        .            

 .     (

 

'"  ' 



 !   ( !   

  (   '  / . 

    .       &     '(          "'      (G      '  /(  (  @A  (   (  

.   (  .   %  '      ' '/    (   .       >  

        !  "    ' ' 9

 @   ('7(A  !      (   *  ! "'   (  '/  '  ' '  @ A ' / >             !  "          " ( '  ! ' /  '/ !      (  *  ! "'   '  ' '  @ A     "    /    ('   '(  G        (      ( .   *  &      / .  !       ,# '(

(   '

7                '  "' (.  ( (   (   7   .      @ L  A    *(  (   !      "' (.  (   7  +    @A  (  !   '   "'       !   ' .      ( 7  '(   @A K    @A K @A  . '     )"(      (  (   



     !  "    ' '     '   (   ' @  A    !               (    7     (  > '   (  / Æ      !   '    @ 6> 6Æ A "'  .          Æ  ?         @A  > &   .  !            " ( ' /  ( '( @ (    ' /  ( >  

'(A    ,#    B;C &         (            )  ( !'      . !' .     "'  (    ' !     BC B5C .    (  !'    !     (   (   (   '( !'  ' (     ( !'         '   ( !'     (  @ ( E F A

'  6

0   

       ! ' 8      ()   D     .

 (    '     .       '  (   . &       !    '"  ' !       (     ' ( (      !'   (  * )( (      !   

0   1                   1 (1  !    ( 5> 8 1  1   (           2 !     1   

'  5>5> =

    .  .  Æ      ! '" !    !  &        (  (  !    .  / 4 (   ' !  .    1  . .    ()     ' !   '(      .    ( !'    '  . .   * !      ' !  "  !   '(      .   !   (   !   (      .( '/ "   *'  !'   '(            

        @    !  'A #     !  ? D     ?   .(    (   !     ()      !  '  .   '(    ? #   ?       ! ?@ A K  

6

8  



 



                 

    $    ?      ?@ A K % 2@ A K 3 !"# 

 

2D 



  

    

    ?@ A K 

1-3      .  ()  E/ (F !      ' 7      !    8  .  ( .       "'

2 '   1-3 

   

     @A    ( 3

 (      ( ! 7 5   ' - 

'   !   (      '  ( ( > .       ' ! 



79

!'    

9 !    

 ! !   

   (

#  (  (  '  ,#   

 '   !  !  ' /  (   ' &   == . .   '   !  \    ( !  

 0   !    

9G



       " ((   

8  







         





  

      

 

@A% @@A  @A    &     @A  

     &   #         

  !"  

9%



  '()*+%     ' "       Æ     #              %           %









0                ! > ;

  

@

 @ A     

     

6 

  @ A        

    #  

#



#      

       ,  

>                    !   0      1-3 @+! A . . .( /  '7     !  0   '     (     !      !    '       !   4    (         B9C BC > '7  





'   *     

 .  $  %  



  !       '  #     !    







       

3

12



          

          

   #  

% @ A







 

     

      

B/ C   '  '    '  (  B5C .     (0

 ! '    )       '(   ' '     

 .   

     ' ' @   9A05 A      "'    ' (  @AG !  (        ( ( 8 .

(0  ! ' ' &  

  ' / (     (  !.D

 &!    D "    @   '  (   '    ' "  A   "'



  

  ( ((  ' '      

 &!    D ' !'       ' '    )(   @  '     A

     ( '     

   !   '    !.( !   @ A

  ' (      >     '  ' (4      

     ( !   '     (    (  ' 

!'    .  ( (  (  !    @ 

=$A 

    '    !  !    ('   ( !    <

  ! 

' 

2 

#       !'./ (   (4 / ( !         / ( !     ((         " ! ,#     (  ' !   .  (    .      '  '  ((  !    ! )    B C  .   "'  '(        

6

 ' .      I( .  '     '    6     !'./   .       / ( !   .    '  

 !

     .    (   !     !   (     ( >

      !    '      3        (   ' !    !  1-3 .  '  (  '    (          (        '    0       )         (  '(   !    

 .    0    

'  (   ! !    0    !'7(      !  D

   .    >     *    !    "'     ( !'   "'  I   ' * !       &    *     6

   !  "' .    ( 

(         ! 

   ( (

 . 

$







                    

       

   

*

3

12

* 

   %    

B/ C  !   "   !  '   B=C (     

        !   )       '(

.

   2  +  

  (   (((  (  "       !     !'./  )      !    ! 1-3

  ! "    !' (  (  !

 "   ! '       ( (4

 (   &  ./ .   

     7  ' ( (      (    '  ! '" 

   !' '           .     ! '" !    ' !         ' !   (      '   #      '  !   ( !' !  0    (   (        ' @     ! !A  ( (   '    ./       0    (       7 3    !     .    !  !  ./ &             '  !       @! A  ' 4   (            ' '  ! '       (    (           ( !     Æ  B9C        ' "  @ '  ! "' *( !   A ( (   '  !      (     '  !      ('        ( (  !  7  *    '  ! "'  ( #      !. !  '                   '"  !                ( ( (   '  !                '    ('  # (       ( .     7        ' !        ( !'  '   (  ( . '/   '   '   !        .  "    (     E  F -         (   ./     (( .   >        B9;C BC >   )  ( !     ('   .      '  ! !  /    (       '   / .       )          '( B5C  )        '    (    

/ @,A ' .         



  (    !      

   (      ''  !  (    !  @  0  ( )A -  ('     @ 'A   !  "   1-3   (    (       !          'G     '  '(      '  !

 #  !   '      (       (  (     ( 

  



.

 7 0    

 > @  ./ ! > . A            ./ !        ''  () (   '   ( !    (      !   ./  '             (    (     !  %       (     (          .   !       G         (   ()   !   0  ' !     @! A "  ( !'  + '    #        '(     ! !  .       G       (      ! >  (      (  (   /(  . ( (  @' !A    !  6

 K       ! !        "'  (   /(   (

 (         (  

( 

 4

 " ' 1 







"   .   ( ( !   ( (

.



(

      !     (   (

1  

%  >  '  (    !   ./   !   !           ' !    &    . '      .     ./ !     0   . ' ()  (4      .  . '     0  #  "'   (   '       ./G  "'  (  (     "'     ./ !

( ' 

(  (     "'    ! 

 (            ( ' / ( G  (   >  ' 

  ( . 

!  (      (   ./    ! 6   ? > .

(   B9C  '    (    . (       .    !   !    / .       )       '( B5C  '  '  '' (        ! >   @A   !     (   

% 

D    E !  > 

    (   !  !   .            ( @A   / @   7 . A "   .   ( (  (  !   !  (   !  .     "'  ( (

(  ( . \    ( !  ! 

8  !  '    !          '"  !     "' ( (     '  ! !       '  ! ! 

   (   ( ( !   

   (   ! ' !   '   '   ('  

.     '  ! !         ' '  ! '       "'  > . (     ((    (

1

(

    . ( 

'   (    '   / = /      (  (       !   ( @   ! .  " A   .  ' /  (   '( 6  K       !   !     /(    ( ( &!   ' (   @    "  1 A  (   (      ' D    ' 



  .     "'      '    ! D

   "   " &!   ' (   @





" ' 1 A  (   (        .   

 "'   D

   "  =  "

#   .     (  / !  !  > . (      '  ! "' *(      !  .   .   ' 

 !   !   (    ' 

.     '  ! !     '    ('   .   '  !    !         ' '  ! '        '(  '  ! "' *( !              (  @((  " A   . 

@  A > .  / .   Æ      

( !   (         !  / ( !   (   .    ( !   '/ ! )    .   '       '  (



( (    '  !    (      B=C B

C

8     ./    (  (   ./     (  (   '  '  '( .     ('     (   >     .  /  '  '  (   )  (   &        (   '  ' '        (   '   .     !   >     (       3 = =  ( =5 ( ' (    >       

   



D · D 1       D ½         D  6  7     "         

  D        D ½         

E (      E E (   # E E (     .   #  E E        #  E E $ $    #  E E  ('F ' . E E ) +         $   E

   

3 =D >D

      

   32 #, +7 :#, +; <

*  D              , )   6 7  %$ 6 7 5 , F# 6 7

6%  32 #, +76%  :#, +; <      %$ 6 7 .  6('F 7

     

3 =D >D            .    ./     (  ( .   (0 ( %      .    ./   (             (   G            '(  .      (      .   ./  ( !    "'

5

     

3

  6% :; < $ D ¾ 

3

   +:; <

 6   67   7 : 6  7        

 6   67  7 : 6  7        

E  $  #$ +  E E  #$   $ +  E

3

   /   :; <

   

         D 

E  .     #G    # E

;    #

3

  $  :#, +; < ?    D ¾    67

E F  H.H ?  E

3 =5D >D

    

#  >  5+  0     *  !       (  (      !    ' # (  (    !'  0     .        ./ .      0       ()   !   0  ' !    !  "  ( !'  ' > (   ()     >   .        ./ !    (4   0   . ' ()  (4      .   @ .A '     0       )     '/  (4        ' .     ()   !  0

 '/

 !   "' !    0     !  '     ' '    '/  (4     G    . '    0  !  (    '    ((    !   ' / (    (  .    '   8     (    )  (   ' !   '"   (   !    '(   .  ( (  



# :   .  ) .  !          '  









  )   . '  !'  !  ( > ( ' ( .  :   (  '   ! ' .   !'         ' $

  .  >    ! 7 . 

!        ' /  .

'    .   '    !'(  (  .  ( '     !              !  :  ( > ( ' ( .    = . !'(           ' @  .  (

  K $  

9 ) !  

' (  (  ( 

=

     ('   !    .          (  "  &    "  ((   .           ('    (  *      (    -   ! ' @

4  A @4  A  @4  A . 4  

       (

         : '  ) (   '         !  ! (    !  '    ' ( . '"'7  (   !    !'    @' (  A : / B5C .  '"'7   ' (    *  ' '7   : ('   ( !         7     ' ! ) (    '     (      (  '7   '  ( (   *(  ''    *   '   .  ( '      !  (  

4

  !  !'



 @4A K -@    *@4 4 A H A 

*@ A   /  !   ( -   !      H        (   .        '    *  ( '     7  '   4   (    7   (     @:A ! 

.

 '     .    ' (  !  ' '  !      (    ' )   ! /  !   .     '  (  (  .   ('     (         .   '      &!  /   !  !'

*@4 4 A K ^@4A  ^@4 A  9 !  .    '     (      . ('       ./    . ('              (  !  3    :   /  !   '  ( ( !    ! '    !  ^ D

      /  !       ' !    ( (  !     .   !   '  ( (     :  .       ;

!    !    '   ' ! .   ( .        .       (.  /     (  ) (  E F /  !  .   :  &               ! /  !   '     !  (  ! :  !'      ! . ' "'   (  (   :  .  . ! (  !'   8        :         (  / ( !    (   (    . .    /   (

..

-5  % -"%

>   '  8 0 &' 6  @8&6 A (      "'  . 8&6      DLL...  ' (L#:%  8&6  (     !  ' !   0  .  ' !   0   . /     ! 9Æ   ;    0   ' .  '7(      !  .  0 ('   @  ( .( A )   ' 7 ! <

 < " 3 =$ .  '

!    0  /  !  .  7     5  (  0   3 =$ 

 (( ' (Æ     7  B$;CG .     0   (   

 "'  % 

 '    (      ' ! 5

 5 " ! 

"' 

3 =$D '  8 0 &' 6  @8&6 A    !   0  !    9Æ  A   0   .  . ( .   (      (( ' (Æ     7  B$;C

<

''

3   !  ! 6.088   

# )    ' (Æ     7   0    8&6 (        !   '  !  0  .     "    ( 7      0  ; ' ! (4  @9Æ  A '  . (     ' (  5= @Æ  A ! ' !     (  '   ' !    .       (  (  '   (         '   (Æ  @ .     '  (A '             '  0           '   @.   (      ' !   0     A > )(   "'   .   '    ) @   % (



(  A             ! < 9M @9$   ! 5=  A 3 == . ' !   0  ' )(     ' ( &     ' .  (       ' (    *   ! '' !    '   (       ' '"       . '  .   ' ' (  '    '" :   B$;C B9=C !   ! (  '  !   '  (      '     ! ' '  (4 ' (

+, )$*$+*$%,

+, )*$+*%,

+, ) *$+!*$%,

+, )%*!+ *%,

+, )%*+ *%,

+!, )*+$*%,

+, )!*$+! *%,

+, )*$+*%%,

+ , )!*+!*$%,

+@, )!$*+!!* !%,

 

3 =9D ' (  0        ' ( @ D D A '    0 .  .      7(   0 .  .    & . ' !  9$  @ ! 5=  'A '(      ) .   5= .   0       











  =D 1      !    ) 5  0   ('  ( !' 8&6

5  0  .  3 =$  (  B$;C

 .   0   8&6

$L ( ' ( .  :   (  '   ! ' .   !'         '   .  >    ! 7 . 

!        ' /  .

'    .   '    !'(  (  .  ( '     !              !  :  ( > ( ' ( .    = . !'(           ' @  .  (

  K $  

9 ) !  

' (  (  ( ( ' (  : ( ' ( @    ( ( !  /  !  A  (     )    8&6 



(    '  '     .   '  ! . !   0 @ A (      (    !  . @;

 A !   0 !   

  =D %"'    !  )      0    8&6  (  _ ! .L 0 < < 9$ =$    

5= 5=   > 6  :   

9 .L  0  ! ( > .L      6   :       

''%

5= 5=  

_ ! .L 0 < < 9$ =$    

9              !    0   8&6  #       0            '     ( .     !  '         !  (   (    '     !  $



   ''   "'' (    :     @: A  .      '      (        '   ' (  !  !  :     ( !'      .       ( ' (     *(  ''  @J,A  ' .      '7   '         '        (  '' *' . .  * !  '        &    .   '  ' (  "   '  !    .  .  (         ' (  !   )   (    ! (      !   ''   ' %"'         (  (    .   ( ' (  ' Æ       ' (   J,  ( * '   ''

4

*  & 

 :     @: A    '       ' (              (         (   ' B5C B5C 8  (     ! :     '  ) (   '   !'      '     " (      !     '  ' '7( #

(  

    / ' '7   (     !   (       (  .  (      ! !   .  . : @: /   /A ('  .  7 . ( !  ('    !      B5C (     : (  9

  '     ) (    !        ! !   .  . : ('    :  '  (    !  "'    0           ('   !     .           (      0 (   8    !     :     ! /  !    (  "  '    '(      0   #               ('    

 .     (  

         !   ) (           0 (   :        ( '       !      (   !'           ( "  '     '  )   /     :  *     *(   '7   '  .      @:A  ( )(       '   . '     ! (  :      '    "    ''     (      !    (

   

4  A @4 A  @4 

"' @

A .

4    

        !.  *(  ''  @J,A  '

 ) (   '  D  '7  0  .



               (    K  

  '  ! ! '

      

)  (

   

' "  ( ( 

4       (  /  !  !  :         

! 9 "' . ( 

 ' " .  9  '  . 

   )  

 '' !    (( '      J,  '   '     ( ''       ''   (  4 !' '       #   ' (   ((  Æ     *(   '7   ' B5=C B$$C B C        !'  !             @:A !'    !      .   * ' ''  (  (      '    (   '     . (   '    !  : .        '  '   ! .      :

=

&    .   ' (  "    !  : (       !'  !          !      . ) (      

4 .     .



4  (      .      ( 

.        &   .(       '      !  "                

(     

 (    '    '   )           ('        *  (      (   B$    (  ( '   .   "                    ( 

4   '  

(        '     

     '    (     (    (  ' (    ( ' (      "   !       

4   '  

 *  !   !    '   (   &!  "        "    (     (              

4 '      Û

  

> .          

   !    3   '   .    ' '     .  '7( (  

4

    

   '   ! 

   '   (   .  (   '          '   ' '' (      '   3   !

   "'   ! :  ! (      !

 

''   ' %  6, '  ( '   .             '      .    (   !   !   6,      '  0   !  6, #!  . "    ! (   .      '  '       *(  ''   ' .        (    !'  '  !     (   ''   '   ( ' Æ    *(  ''   '  ( ' (   Æ   '   :  8 "'       '/ .   ( ' (  . '  (   '"       7(  !.   ; (        :  &   ;5 .   ' (  "  (       ''   ( 

;

     '   &   ;$ .  "'         (    (  (    >  (    .  ''     ( !  ./    ;9

4

%& 0 1

3      ' .  '     "'     ( *(   '7       :  * /  '      ' ! '  ( '' *'  #     ! 9 "' . ( 

 ' " .  9  '  . 

  

)    '' !    (( '   *  (    '7   '    .   J .        (  ( @   ' (     .  ' " !

A

    ( ( '  ' (  

  '7   ' B=C B5C B5=C B C B       (             (     .  ) (   (       !     !   ' ! ( '    "   !

,  *       '   (   . 

   

  (   !      '   &!  "   !     6,   (    '   "       '            3 ; .    .   ( @  A      .   



    ?H? .      ? ?  ( 







 ( 

)  3 ; @A .  

,   (  )           ?H? (      ( ( !   ,  (         ? ? (    !  ( ( ! ,    (  6, !   6,  .   ( !     

   K  @, A

      @, A

      @, A    *   (  * 

      

(   

 ((   6,  (       '      

,

 (

,





,

,

   !  





K@

 A '  

'  !         (   &   .( !  "     ! 

6,  (      ( ( !

,

,

 (  (    !  ( ( !

   !      !        





,  3 ; @ A .      !'  ! ,  

,  

(   !     

,

   !      )(

 (     !    !  !'        !    !

5

 3 ; @ A .        6,    !     . 3 ; @(A .   6, !    !      ,     !  ( ( ! ,  ( ,      ( ( ! , 

  !'  !

,

   (   ' !

& !   ((   3 ; .    !     !  6,  * 

   (    "'      ! 6,  .   !    '      !  !    )(         '  &  .  .      (   !   !  6,       '  l1

l2

l3

l1

l2

l3

p1 +

p2 +

p3 -

p1 +

p2 +

p3 -

l1

l2

l3

l1

l2

l3

p1 +

p2 +

p3 -

p1 +

p2 +

p3 -

(a)

(b)

(c)

(d)

3 ;D     ''   "  (   %    (   (  .   ) ,   (      ?H? .       ? ?



3' !   !





  . 

!'   6,  ' ! 

D

"'7  0 



@   "'  (  @   "' .

  K    

"    

"     

   



 

 

  

. .   !    . ' 







" 

" 











     @    "'  (   

5

   "'        6,  !      !     (  6,  '  ! '   . .  ) (  !      !       3 ;5   '      !  6,  ' &!    !      (    '   .  ) (    



  '       

  !  '  !   ' ( !    @   '   A &   .(     !  !    )(          '   .  3 ;5 @A   . (    / .(   .     !  '      .    . (      *     /       #    (   !  "    !       (  6, &!    !      6,  '      "              (    '      !   !    )(

       '   .  3 ;5 @ A     " !' !   0  !   ''    .    (  .                .  '    '7   '   ( ' Æ   ! .   ' !' l5

l3 l4

l2

l5

l3 l6

l2

l1

l4

l6

l1 l7

l7

l8

l8

(a)

(b)

3 ;5D -'      !    ''   ' @A .    .  !    "  @ A .    .  !    " 

3 ;$ .   ! 9       . D     ( .  ?H?       (     ( .  ?a?       (     ( .     (   '      ! (     :   ( (   3 

 

 (  6, (    !     ( !     (

  &   .(  '    "                 ( ' 

   (   3   (    "     

         (   #   ( .  (     ( $

5

    !   '      ! (     :  #    (   !'   !    100

guard vector 3 l45

90

l1

l17

l4

80

l2 p45

70 p17 60 guard vector 1 guard vector 4

50 optimal separating hyperplane

40

30

20 guard vector 5 guard vector 2

10

guard vector 6 0

0

10

20

30

40

50

60

70

80

90

100

3 ;$D -'       ! (    (    @(   !'   !   AD (     ( $      !   '      ! (   : !   !  

 ('      K @       A   (      K   H   H H     ' +     ('       . 3    





  +  .       ''   '  ( '  .      (     D

A  & ' " !' . 

                





.







    H      H                   

 







  '  !    (   !   ' ( (        ( 

   !     6,  (  > ''7   '  (  '  !.D

/% .D 3 (   (   55



  !'       (      .   *  ? ? &  7



    ( 

 . 

  

, )   *   ! (   ! 

     *    !  (   !       '





   ? ?  (    *    !       !      



      ? ? 5    6,  ' &!    !        (        *    &!      !      . 6,  

    (   $ & 

*

    (             

 /(

0 $

4  A @4  A  @4 

-   ! ' @ ('   (

A .

4 @4  A       ! 

      @    A !       ' : '  ) (   '

        !  ! (    !  '    ' ( . '"'7   (   !    !'    @' A : / B5C .  '"'7   ' (    *  ' '7   : ('          '     '      !'

 @4A K .

   4 H K    *@4 4 A H 



 



*@4 4 A K 4  4 !   :    !  @4A ( '  

   !

4

    '        (            (  (   !'   ! : >    (  '  "    (    (  ) (      (  (   7 J,       '  

5$

     '

*

" $

3            ( .      !  '  B95C  0      !'        ('      .  .         3    7  !'  . '  .  0      !'        ('     8  (  !  !  0  !     0 (     (      (   0 (  

9        ( !   )"(    U . ()   0  ! 9   ¼     ('       9  6

 D 4  9  4¼ K @4 UÆÜ A  9¼ 

.

ÆÜ   

 () ( 

  ÆÜ @% A K  G  G 

% K G   %   . !

4  A @4  A  @4 

-   ! ' @

A .

4 @4  A       !

 ('   (       @    A  0  "  (         ¼

 ((  . ('     !   "' 6 4   (    "   !  ¼  4  .   )  (   ! 4 *  4  (  @ H A  (    U  4¼    7 )   9  ( (    . ()  (   !   "' 

 !  (   ! 3   

 @@4  A @ AB A K '" B   @@  4 A  A .

   '  .   !     '   @4  A   !   ' 

 

B  

 @@4  A @ AB A  B   @@  4 A  A 8     . '    

B   '  59

   )   

'   0  !



4  . 0  '    !       ¼ 

  !.  !  D

¼ K @ U

 

4 A @ AB A ÆÜ A

@@



%.D #    4¼   0 (   9¼      3

1D 3   @4 A  (    @ A .   !.    0 (  

¼

¼ @@¼  4¼ A  A ¼ ¼ ¼ K  @@ 4 A  A H  @  @@4  A @ AB A ÆÜ  Æܼ A  B  @@4¼¼ A BA H @@4¼ ¼  BA K B 

&   .(         



9¼  '      B  !

         (

4

-5  

&      (  '   (   :  .  J, '         (  '/ (  # ''     .   #6#  (  , ' !   "'   '(    ((       0  !  "'     '/  , '  ( ''  !  ( ' (  (      J,    :          !'  &   .( . (     '   :      ' !'  @  ' 

     !

 "' A .   ' ( ( (   '  '         "' 

*

( !   

 ('      3   (    6   "'    ( !'     ! B $C  ( 6   "' 

%     (     ('   ( !' 

5=



  ( !'     ! B= C  3 ;9 .  , '  ( '' *'     !    (     ('    "'    .   ( ' (  !'  J, ''   ! :    * '   , '  ( '' #  "'    .   '  ! (   ! (   ( ' (   ' .   '  !   

CPU Time Usage

Memory Usage

50000

90 QP method Proposed method

QP method Proposed method

45000 80 40000 70

35000

Mega Byte

Second

30000 25000 20000 15000

60

50

40

10000 30 5000 0

20 0

100

200

300

400 500 Number of Examples

600

700

800

0

+,

100

200

300

400 500 Number of Examples

600

700

800

+,

3 ;9D  '/   !  (  '      :  ' ! , '  ( '' *'     )  ('   (   .    ;   ; . ' "'     .       ( !'    !  ('       ( , ' !  ( ' (       (  '  "  (    (  '    :        J, ' (    .   (  ' !' . .     .  '  !

6A    .     .  '  (    (  '  !    ( (       ! 6  (     !

   (  ('    @

 (    !

*

2&   

 ) (   .   !'  >      (   BC %  !  = '  

( 

    .      (    .         ' 

"'    ( (      ! 9 

  !  '  (      !  ! 

5;

  ;D %"'        ( D %  (      (   ('     



_  @'A 9   $   (( ' (  (  !      (  '    9 '( .  '    !   !  (   ' (  ' ( BC B=C B5C !' * .  ' ! (       '  !. ! (            '  >   (  

'  

  (      '

 !     !  0     .   ,# !'./ 

  =    . ( !  !'./    >          (       0     "' B9