Mining recurring events through forest growing

Junsong Yuan; Jingjing Meng; Ying Wu; Jiebo Luo

doi:10.1109/TCSVT.2008.2005616

Mining recurring events through forest growing

Junsong Yuan^*, Jingjing Meng, Ying Wu, Jiebo Luo

^*Corresponding author for this work

Electrical and Computer Engineering

Research output: Contribution to journal › Article › peer-review

6 Scopus citations

Abstract

Recurring events are short temporal patterns that consist of multiple instances in the target database. Without any a priori knowledge of the recurring events, in terms of their lengths, temporal locations, the total number of such events, and possible variations, it is a challenging problem to discover them because of the enormous computational cost involved in analyzing huge databases and the difficulty in accommodating all the possible variations without even knowing the target. We translate the recurring event mining problem into finding temporally continuous paths in a matching-trellis. A novel algorithm that simulates a "forest-growing" procedure in the matching-trellis is proposed. Each tree branch In the resulting forest naturally corresponds to a discovered repetition, with temporal and content variations tolerated. By using locality sensitive hashing (LSH) to find best matches efficiently, the overall complexity of our algorithm is only sub-quadratic to the size of the database. Experimental results on the TRECVID video data of 10.5 hours and a human dance video dataset of 32,260 frames show that our method can effectively and efficiently discover recurring events such as TV commercials from news videos and typical dance moves from human dance sequences, in spite of large temporal and content variations.

Original language	English (US)
Article number	4630766
Pages (from-to)	1597-1607
Number of pages	11
Journal	IEEE Transactions on Circuits and Systems for Video Technology
Volume	18
Issue number	11
DOIs	https://doi.org/10.1109/TCSVT.2008.2005616
State	Published - Nov 2008

Funding

Manuscript received March 06, 2008; revised July 21, 2008. First published September 26, 2008; current version published October 29, 2008. This work was supported in part by National Science Foundation Grants IIS-0347877 and IIS-0308222. This paper was recommended by Associate Editor S. Maybank. J. Yuan and Y. Wu are with the Department of Electrical Engineering and Computer Science, Northwestern University, Evanston, IL 60208 USA (e-mail: [email protected], [email protected]). J. Meng is with Motorola Applied Research and Technology Center, Schaum-burg, IL 60196 USA (e-mail: [email protected]) J. Luo is with Kodak Research Labs, Rochester, NY 14650 USA (e-mail: [email protected].) Color versions of one or more of the figures in this paper are available online at http://ieeexplore.ieee.org. Digital Object Identifier 10.1109/TCSVT.2008.2005616 Fig. 1. A typical dance movement in the Michael Jackson-style dance, performed by two different subjects (first and second rows). Such a dynamic motion pattern appears frequently in the Michael Jackson-style dance and is a recurring event in the dance database. The spatial-temporal dynamics in human motions can contain large variations, such as non-uniform temporal scaling and pose differences, depending on the subject’s performing speed and style. Thus it brings great challenges in searching and mining them.

Keywords

Event mining
Motion pattern discovery
Temporal pattern discovery

ASJC Scopus subject areas

Media Technology
Electrical and Electronic Engineering

Access to Document

10.1109/TCSVT.2008.2005616

Cite this

@article{3c8fae7b2ddd4447975df989d3f16786,

title = "Mining recurring events through forest growing",

abstract = "Recurring events are short temporal patterns that consist of multiple instances in the target database. Without any a priori knowledge of the recurring events, in terms of their lengths, temporal locations, the total number of such events, and possible variations, it is a challenging problem to discover them because of the enormous computational cost involved in analyzing huge databases and the difficulty in accommodating all the possible variations without even knowing the target. We translate the recurring event mining problem into finding temporally continuous paths in a matching-trellis. A novel algorithm that simulates a {"}forest-growing{"} procedure in the matching-trellis is proposed. Each tree branch In the resulting forest naturally corresponds to a discovered repetition, with temporal and content variations tolerated. By using locality sensitive hashing (LSH) to find best matches efficiently, the overall complexity of our algorithm is only sub-quadratic to the size of the database. Experimental results on the TRECVID video data of 10.5 hours and a human dance video dataset of 32,260 frames show that our method can effectively and efficiently discover recurring events such as TV commercials from news videos and typical dance moves from human dance sequences, in spite of large temporal and content variations.",

keywords = "Event mining, Motion pattern discovery, Temporal pattern discovery",

author = "Junsong Yuan and Jingjing Meng and Ying Wu and Jiebo Luo",

note = "Funding Information: Manuscript received March 06, 2008; revised July 21, 2008. First published September 26, 2008; current version published October 29, 2008. This work was supported in part by National Science Foundation Grants IIS-0347877 and IIS-0308222. This paper was recommended by Associate Editor S. Maybank. J. Yuan and Y. Wu are with the Department of Electrical Engineering and Computer Science, Northwestern University, Evanston, IL 60208 USA (e-mail: [email protected], [email protected]). J. Meng is with Motorola Applied Research and Technology Center, Schaum-burg, IL 60196 USA (e-mail: [email protected]) J. Luo is with Kodak Research Labs, Rochester, NY 14650 USA (e-mail: [email protected].) Color versions of one or more of the figures in this paper are available online at http://ieeexplore.ieee.org. Digital Object Identifier 10.1109/TCSVT.2008.2005616 Fig. 1. A typical dance movement in the Michael Jackson-style dance, performed by two different subjects (first and second rows). Such a dynamic motion pattern appears frequently in the Michael Jackson-style dance and is a recurring event in the dance database. The spatial-temporal dynamics in human motions can contain large variations, such as non-uniform temporal scaling and pose differences, depending on the subject{\textquoteright}s performing speed and style. Thus it brings great challenges in searching and mining them.",

year = "2008",

month = nov,

doi = "10.1109/TCSVT.2008.2005616",

language = "English (US)",

volume = "18",

pages = "1597--1607",

journal = "IEEE Transactions on Circuits and Systems for Video Technology",

issn = "1051-8215",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

number = "11",

}

TY - JOUR

T1 - Mining recurring events through forest growing

AU - Yuan, Junsong

AU - Meng, Jingjing

AU - Wu, Ying

AU - Luo, Jiebo

N1 - Funding Information: Manuscript received March 06, 2008; revised July 21, 2008. First published September 26, 2008; current version published October 29, 2008. This work was supported in part by National Science Foundation Grants IIS-0347877 and IIS-0308222. This paper was recommended by Associate Editor S. Maybank. J. Yuan and Y. Wu are with the Department of Electrical Engineering and Computer Science, Northwestern University, Evanston, IL 60208 USA (e-mail: [email protected], [email protected]). J. Meng is with Motorola Applied Research and Technology Center, Schaum-burg, IL 60196 USA (e-mail: [email protected]) J. Luo is with Kodak Research Labs, Rochester, NY 14650 USA (e-mail: [email protected].) Color versions of one or more of the figures in this paper are available online at http://ieeexplore.ieee.org. Digital Object Identifier 10.1109/TCSVT.2008.2005616 Fig. 1. A typical dance movement in the Michael Jackson-style dance, performed by two different subjects (first and second rows). Such a dynamic motion pattern appears frequently in the Michael Jackson-style dance and is a recurring event in the dance database. The spatial-temporal dynamics in human motions can contain large variations, such as non-uniform temporal scaling and pose differences, depending on the subject’s performing speed and style. Thus it brings great challenges in searching and mining them.

PY - 2008/11

Y1 - 2008/11

N2 - Recurring events are short temporal patterns that consist of multiple instances in the target database. Without any a priori knowledge of the recurring events, in terms of their lengths, temporal locations, the total number of such events, and possible variations, it is a challenging problem to discover them because of the enormous computational cost involved in analyzing huge databases and the difficulty in accommodating all the possible variations without even knowing the target. We translate the recurring event mining problem into finding temporally continuous paths in a matching-trellis. A novel algorithm that simulates a "forest-growing" procedure in the matching-trellis is proposed. Each tree branch In the resulting forest naturally corresponds to a discovered repetition, with temporal and content variations tolerated. By using locality sensitive hashing (LSH) to find best matches efficiently, the overall complexity of our algorithm is only sub-quadratic to the size of the database. Experimental results on the TRECVID video data of 10.5 hours and a human dance video dataset of 32,260 frames show that our method can effectively and efficiently discover recurring events such as TV commercials from news videos and typical dance moves from human dance sequences, in spite of large temporal and content variations.

AB - Recurring events are short temporal patterns that consist of multiple instances in the target database. Without any a priori knowledge of the recurring events, in terms of their lengths, temporal locations, the total number of such events, and possible variations, it is a challenging problem to discover them because of the enormous computational cost involved in analyzing huge databases and the difficulty in accommodating all the possible variations without even knowing the target. We translate the recurring event mining problem into finding temporally continuous paths in a matching-trellis. A novel algorithm that simulates a "forest-growing" procedure in the matching-trellis is proposed. Each tree branch In the resulting forest naturally corresponds to a discovered repetition, with temporal and content variations tolerated. By using locality sensitive hashing (LSH) to find best matches efficiently, the overall complexity of our algorithm is only sub-quadratic to the size of the database. Experimental results on the TRECVID video data of 10.5 hours and a human dance video dataset of 32,260 frames show that our method can effectively and efficiently discover recurring events such as TV commercials from news videos and typical dance moves from human dance sequences, in spite of large temporal and content variations.

KW - Event mining

KW - Motion pattern discovery

KW - Temporal pattern discovery

UR - http://www.scopus.com/inward/record.url?scp=55149087879&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=55149087879&partnerID=8YFLogxK

U2 - 10.1109/TCSVT.2008.2005616

DO - 10.1109/TCSVT.2008.2005616

M3 - Article

AN - SCOPUS:55149087879

SN - 1051-8215

VL - 18

SP - 1597

EP - 1607

JO - IEEE Transactions on Circuits and Systems for Video Technology

JF - IEEE Transactions on Circuits and Systems for Video Technology

IS - 11

M1 - 4630766

ER -

Mining recurring events through forest growing

Abstract

Funding

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this