M. Ko, G. West, S. Venkatesh, M. Kumar Information Fusion, 2007

Presentation on theme: "M. Ko, G. West, S. Venkatesh, M. Kumar Information Fusion, 2007"— Presentation transcript:

1 M. Ko, G. West, S. Venkatesh, M. Kumar Information Fusion, 2007
Using dynamic time warping for online temporal fusion in multisensor systems M. Ko, G. West, S. Venkatesh, M. Kumar Information Fusion, 2007

2 순서 소개 Dynamic Time Warping 시스템 구조 실험 결과 DTW 학습 온라인 DTW
실험 1 : 가속도 센서를 통한 제스쳐 인식 실험 2 : 다양한 센서를 통한 시나리오 인식 결과

3 소개(1) Multisensor fusion 입출력에 따른 분류(Dasarathy, 1994)
단일 센서처럼 처리하지 못하는 다양한 센서 통합 통합 방법 Raw 레벨 Feature 레벨 Decision 레벨 다양한 분야 결함 감지 및 치료 Wearable computing Context-aware system Raw 데이터나 feature끼리 temporal fusion이 필요함 입출력에 따른 분류(Dasarathy, 1994) Data in – data out Data in – feature out Feature in – feature out Feature in – decision out Decision in – decision out Data in – decision out

4 소개(2) 다양한 센서들끼리의 temporal fusion DTW를 통한 multisensor fusion 다양한 순차의 조합
다차원, 시간, 이산적, 연속적 센서 등 다양한 길이의 데이터 같은 클래스끼리도 다름 DTW를 통한 multisensor fusion DTW를 확장 Endpoint에 대한 고려 다양한 heterogeneous 센서의 통합 Data in – decision out, feature in – decision out HMM과의 성능 비교

5 관련연구 다양한 분야에서의 multisensor fusion
A. Aziz et al, Fuzzy logic data correlation approach in multisensor-multitarget tracking systems, Signal Processing 76, No.2, , 1999 E. Jouseau et al, Neural network and fuzzy data fusion: application to an on-line and real-time vehicle detection system, Pattern Recognition Letters 20, 97~107, 1999 F. Optiz et al, Data fusion development concepts within complex surveillance systems, in: The 7th Int. Conf. on Information Fusion, 2004 S. Morriss, Automated manufacturing systems – Actuators, controls, sensors and robotics, McGraw-Hill, 1994 J. Castellanos et al, Mobile robot localization and map building: A multisensor fusion approach, Kluwer Academic Publishers, 1999 다양한 분야에서의 multisensor fusion 타켓 트래킹, 자동차 감식, 감시 시스템 , 자동 공정, 로보틱스

6 Dynamic time warping(1)
Local distance : 길이 I인 순차적 분류 템플릿 : 길이 J인 순차적 테스트 템플릿 d(I , j) : 분류와 테스트 템플릿 사이의 거리 Warping path(W) i(q) ∈{1 ,…, I) , j(q) ∈{1 ,…, J) 제약 조건 Continuity Endpoint Monotonicity

7 Dynamic time warping(2)
최소 warping path NF : 정규화 계수 거리 테이블 D를 계산하는 식 6 6

8 시스템 구조 데이터 전처리 DTW 인식기 Decision module Raw 데이터를 테스트 템플릿으로 변환
테스트 템플릿과 클래스 템플릿들의 유사도 측정 Decision module 입력과 가장 비슷한 템플릿을 선택

9 데이터 전처리 입력 데이터 적용 기술 연속적인 값에 대한 처리 온라인 : 연속적인 스트리밍 센서 값
오프라인 : segmantation한 센서 값 적용 기술 신호 필터로 잡음과 이상치 제거 DTW는 모든 element에 대해서 측정 함 변수 값들의 정규화 Discrete와 continuous를 조합 연속적인 값에 대한 처리 동작을 구분 짓는 것이 어려움 Sliding window를 통해서 구분 DTW 변화를 통한 End point 측정

10 DTW 인식기 학습(1) 각 행동별 분류 템플릿을 선택하는 과정 분류 템플릿의 선택 방법 실험에서 사용한 방법
Random selection Normal selection Minimum selection Average selection Multiple selection 실험에서 사용한 방법 Random, minimum, multiple selection End region Band-DP( E = E2-E1) Rejection threshold

11 DTW 인식기의 학습(2) DTW에서의 거리 측정 거리 측정 방법 분류 템플릿의 다중 시퀀스 : C( I x V )
테스트 템플릿의 다중 시퀀스 : T( I x V ) V : 변수의 수 거리 측정 방법 Extended Euclidian distance Cosine correlation coefficient WV : 양수의 Weight Vector 온라인 인식의 성능을 향상, 특정한 값을 강조 10 10

12 제안하는 DTW 인식기(1) 기존의 DTW의 문제점 온라인 인식은 end point가 확실치 않음
알려지지 않은 start와 end point 찾기 End point는 거리 테이블의 대각선 반대편에 있어야 함 온라인 인식은 end point가 확실치 않음 기존의 DTW 알고리즘은 부적합 Start point와 end point에 구간을 정해줌 i(1) = 1, j(1) = s , S1<=s<=S2 i(Q) = I , j(Q) = e, E1<=e<=E2 11 11

13 제안하는 DTW 인식기(2) 최소 warping path의 결정 계산의 최적화
분류 템플릿과 테스트 템플릿 간의 최소 누적 거리 s와 e는 start와 end point 계산의 최적화 (S2-S1)과 (E2-E1)을 최소화 12 12

14 온라인 DTW(1) 각 분류 템플릿 Cn별 I x E2의 거리 테이블 존재 테스트 템플릿의 버퍼에 스트리밍 데이터 저장
버퍼의 크기 결정 학습 과정에서의 최대 E2 한번에 한 특징 벡터의 추출 버퍼가 차면 거리 d(I,j)와 warping path W 계산 13 13

15 온라인 DTW(2) 버퍼 T와 각 거리 테이블 D가 sliding window가 됨 시간 복잡도
D에 새로운 벡터에 대한 d( I , j ) 계산 시간 복잡도 업데이트 시간 : O( NI ) 새로운 W 계산 : O( NIE2 ) I : 분류 템플릿의 크기, N : 분류 템플릿의 종류 수 Band-DP를 이용하면 O( NE ) + O( NIE ) E = E1 – E2 14 14

16 온라인 DTW(3) DTW 거리의 정규화 옵션 번호 방법(NF = ) 1 1(정규화 없음) 2
분류 템플릿마다 길이가 다름 정규화 계수(NF) 옵션 번호 방법(NF = ) 1 1(정규화 없음) 2 최적의 warping path 길이 3 분류와 테스트 템플릿 중 긴 길이 4 분류와 테스트 템플릿 중 짧은 길이 5 분류와 테스트 템플릿의 합 15 15

17 Decision 모듈 NN kNN Normal, minimum, average selection
N : 분류 템플릿의 수 , 1 <= n <= N , Cn : 분류 템플릿 , Dn : 거리 테이블 kNN Multiple selection : Cn,m M : 선택된 분류 템플릿의 수, K : 1 <= k <= M 16 16

18 실험 방법 실험 환경 실험 방법 펜티엄 4 , 3.2G 1G RAM Window XP
언어 : DTW = C++ , 그 외 구현 = MATLAB HMM과의 성능 비교 Mixture of Gaussian Bayes Net Toolbox2 사용 실험 방법 오프라인 temporal fusion 분류 정확률 온라인 temporal fusion 분류 정확률 + 최소 편차(Local minimum deviation) 센서별 실험 가속도 센서를 통한 제스쳐 인식 다양한 센서를 통한 시나리오 인식

19 실험 1 환경 가속도 센서를 통한 크리켓 제스쳐 인식 센서 데이터 ADXL202 센서(3-axis, ±2g, 150Hz)
각 손목에 2개 6 channel data 데이터 4명 대상( * 3 = 65개의 샘플) 12가지 제스쳐 Cancel call, dead ball, last hour 등 18 18

20 실험 1 데이터 W : sliding Window size, O : Overlap size, F : Features 19 19

21 실험 1 결과(Offline) 특징별 성능 비교 필터링 여부 및 거리 측정 방법 성능 비교 정규화 방법 성능 비교
M , F : 센서값의 세기, SD : 움직임 필터링 여부 및 거리 측정 방법 성능 비교 정규화 방법 성능 비교 정규화는 여러 종류의 데이터가 들어올 때 유용

22 실험 1 결과(DTW vs HMM)(1) HMM 정확률 ->HMM과 DTW를 비교하는 것은 어려움 HMM 학습의 문제
T3 : 각 제스쳐 별 minimum selection을 통한 학습 데이터 HMM 학습의 문제 초기 파라미터 설정 부족한 학습 데이터 ->HMM과 DTW를 비교하는 것은 어려움

23 실험 1 결과(DTW vs HMM)(2) DTW가 여러 실험자 및 데이터에 대해서 성능이 좋음 데이터 HMM DTW
Data in – decision out : Raw 데이터 Feature in – decision out : 필터링 데이터 데이터 HMM DTW Raw 데이터 85.7~86.5% 97.9% 필터링 데이터 87.8~88.1% 92.5~96.4% W≠50, O≠30 73.9~78.8% 96~98%

24 실험 1 결과(Online)(1) Multiple 적용 여부, Min vs RD, K, NF 별 성능 비교
Min-4 : Minimum+multiple selection RD-4 : Random+multiple selection Min-1 : Minimum selection RD-1 : Random selection Multiple 적용 여부, Min vs RD, K, NF 별 성능 비교

25 실험 1 결과(Online)(2) 12가지 제스쳐에 대한 최소 거리(LMD) RD-1과 제스쳐 5 가 정확률이 떨어짐

26 실험 2 환경 다양한 센서를 시나리오 인식 센서 데이터(J.Mantyjarvi et al, 2004) 3축 가속도 센서
조도 센서 온도계 습도 센서 피부 전기 반응 센서 마이크 데이터(J.Mantyjarvi et al, 2004) 5가지 시나리오를 25번 반복 1 ~ 5분 32가지 센서 값 46045개의 데이터 25 25

27 실험 2 결과(Offline) DTW 정확률 HMM 정확률 T1(랜덤으로 20개의 학습 데이터) : 75.1~88.1%
T2(각 시나리오별 minimum selection한 데이터) : 72.5~78%

28 실험 2 결과(Online) 온라인 DTW 정확률 온라인 DTW LMD T1이 T2보다 정확률 높음 정규화가 정확률을 높여줌
T1-Min-5 새로운 warping path 계산 시간 = 13,334s / 46,065 = 0.29 온라인 DTW LMD

29 결과 온라인 temporal fusion 시스템구축 향후 연구 Dynamic time warping 알고리즘을 이용
다른 길이의 순차적 데이터 처리 가능 이산적이거나 연속적인 센서 값의 조합 가능 두 개의 실제적인 데이터로 테스트 다양한 변수를 변경 HMM과 비교 향후 연구 Dynamic time warping으로 복잡한 문제 해결 중간 값이 없는 순차적인 데이터 중간중간 공백이 있는 데이터