Multiscale Dynamic Time and Space Warping
Thesis (S.M.)--Massachusetts Institute of Technology, Computation for Design and Optimization Program, 2008.
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | eng |
| Published: |
Massachusetts Institute of Technology
2009
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/45279 |
| _version_ | 1811070599490961408 |
|---|---|
| author | Fitriani |
| author2 | Brian W. Anthony. |
| author_facet | Brian W. Anthony. Fitriani |
| author_sort | Fitriani |
| collection | MIT |
| description | Thesis (S.M.)--Massachusetts Institute of Technology, Computation for Design and Optimization Program, 2008. |
| first_indexed | 2024-09-23T08:38:36Z |
| format | Thesis |
| id | mit-1721.1/45279 |
| institution | Massachusetts Institute of Technology |
| language | eng |
| last_indexed | 2024-09-23T08:38:36Z |
| publishDate | 2009 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/452792019-04-09T18:56:49Z Multiscale Dynamic Time and Space Warping Multiscale DTSW Fitriani Brian W. Anthony. Massachusetts Institute of Technology. Computation for Design and Optimization Program. Massachusetts Institute of Technology. Computation for Design and Optimization Program. Computation for Design and Optimization Program. Thesis (S.M.)--Massachusetts Institute of Technology, Computation for Design and Optimization Program, 2008. Includes bibliographical references (p. 149-151). Dynamic Time and Space Warping (DTSW) is a technique used in video matching applications to find the optimal alignment between two videos. Because DTSW requires O(N4) time and space complexity, it is only suitable for short and coarse resolution videos. In this thesis, we introduce Multiscale DTSW: a modification of DTSW that has linear time and space complexity (O(N)) with good accuracy. The first step in Multiscale DTSW is to apply the DTSW algorithm to coarse resolution input videos. In the next step, Multiscale DTSW projects the solution from coarse resolution to finer resolution. A solution for finer resolution can be found effectively by refining the projected solution. Multiscale DTSW then repeatedly projects a solution from the current resolution to finer resolution and refines it until the desired resolution is reached. I have explored the linear time and space complexity (O(N)) of Multiscale DTSW both theoretically and empirically. I also have shown that Multiscale DTSW achieves almost the same accuracy as DTSW. Because of its efficiency in computational cost, Multiscale DTSW is suitable for video detection and video classification applications. We have developed a Multiscale-DTSW-based video classification framework that achieves the same accuracy as a DTSW-based video classification framework with greater than 50 percent reduction in the execution time. We have also developed a video detection application that is based on Dynamic Space Warping (DSW) and Multiscale DTSW methods and is able to detect a query video inside a target video in a short time. by Fitriani. S.M. 2009-04-29T17:19:45Z 2009-04-29T17:19:45Z 2008 2008 Thesis http://hdl.handle.net/1721.1/45279 310976611 eng M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission. http://dspace.mit.edu/handle/1721.1/7582 151 p. application/pdf Massachusetts Institute of Technology |
| spellingShingle | Computation for Design and Optimization Program. Fitriani Multiscale Dynamic Time and Space Warping |
| title | Multiscale Dynamic Time and Space Warping |
| title_full | Multiscale Dynamic Time and Space Warping |
| title_fullStr | Multiscale Dynamic Time and Space Warping |
| title_full_unstemmed | Multiscale Dynamic Time and Space Warping |
| title_short | Multiscale Dynamic Time and Space Warping |
| title_sort | multiscale dynamic time and space warping |
| topic | Computation for Design and Optimization Program. |
| url | http://hdl.handle.net/1721.1/45279 |
| work_keys_str_mv | AT fitriani multiscaledynamictimeandspacewarping AT fitriani multiscaledtsw |