@conference {13391, title = {On Computing Compression Trees for Data Collection in Wireless Sensor Networks}, booktitle = {2010 Proceedings IEEE INFOCOM}, year = {2010}, month = {2010/03/14/19}, pages = {1 - 9}, publisher = {IEEE}, organization = {IEEE}, abstract = {We address the problem of efficiently gathering correlated data from a wireless sensor network, with the aim of designing algorithms with provable optimality guarantees, and understanding how close we can get to the known theoretical lower bounds. Our proposed approach is based on finding an optimal or a near-optimal compression tree for a given sensor network: a compression tree is a directed tree over the sensor network nodes such that the value of a node is compressed using the value of its parent. We focus on broadcast communication model in this paper, but our results are more generally applicable to a unicast communication model as well. We draw connections between the data collection problem and a previously studied graph concept called weakly connected dominating sets, and we use this to develop novel approximation algorithms for the problem. We present comparative results on several synthetic and real-world datasets showing that our algorithms construct near-optimal compression trees that yield a significant reduction in the data collection cost.}, keywords = {Approximation algorithms, Base stations, Communications Society, Computer networks, Computer science, computing compression trees, Costs, data collection, Data communication, data compression, designing algorithms, Educational institutions, Entropy, graph concept, Monitoring, Protocols, trees (mathematics), weakly connected dominating sets, Wireless sensor networks}, isbn = {978-1-4244-5836-3}, doi = {10.1109/INFCOM.2010.5462035}, author = {Li,Jian and Deshpande, Amol and Khuller, Samir} } @conference {14227, title = {Learning shift-invariant sparse representation of actions}, booktitle = {2010 IEEE Conference on Computer Vision and Pattern Recognition (CVPR)}, year = {2010}, month = {2010/06/13/18}, pages = {2630 - 2637}, publisher = {IEEE}, organization = {IEEE}, abstract = {A central problem in the analysis of motion capture (MoCap) data is how to decompose motion sequences into primitives. Ideally, a description in terms of primitives should facilitate the recognition, synthesis, and characterization of actions. We propose an unsupervised learning algorithm for automatically decomposing joint movements in human motion capture (MoCap) sequences into shift-invariant basis functions. Our formulation models the time series data of joint movements in actions as a sparse linear combination of short basis functions (snippets), which are executed (or {\textquotedblleft}activated{\textquotedblright}) at different positions in time. Given a set of MoCap sequences of different actions, our algorithm finds the decomposition of MoCap sequences in terms of basis functions and their activations in time. Using the tools of L1 minimization, the procedure alternately solves two large convex minimizations: Given the basis functions, a variant of Orthogonal Matching Pursuit solves for the activations, and given the activations, the Split Bregman Algorithm solves for the basis functions. Experiments demonstrate the power of the decomposition in a number of applications, including action recognition, retrieval, MoCap data compression, and as a tool for classification in the diagnosis of Parkinson (a motion disorder disease).}, keywords = {action characterization, Action recognition, action retrieval, action synthesis, Character recognition, data compression, human motion capture, HUMANS, Image matching, Image motion analysis, image representation, Image sequences, Information retrieval, joint movements, large convex minimizations, learning (artificial intelligence), learning shift-invariant sparse representation, Matching pursuit algorithms, minimisation, Minimization methods, MoCap data compression, Motion analysis, motion capture analysis, motion disorder disease, motion sequences, orthogonal matching pursuit, Parkinson diagnosis, Parkinson{\textquoteright}s disease, Pursuit algorithms, shift-invariant basis functions, short basis functions, snippets, sparse linear combination, split Bregman algorithm, time series, time series data, Unsupervised learning, unsupervised learning algorithm}, isbn = {978-1-4244-6984-0}, doi = {10.1109/CVPR.2010.5539977}, author = {Li,Yi and Ferm{\"u}ller, Cornelia and Aloimonos, J. and Hui Ji} } @article {12464, title = {Video Pr{\'e}cis: Highlighting Diverse Aspects of Videos}, journal = {IEEE Transactions on Multimedia}, volume = {12}, year = {2010}, month = {2010/12//}, pages = {853 - 868}, abstract = {Summarizing long unconstrained videos is gaining importance in surveillance, web-based video browsing, and video-archival applications. Summarizing a video requires one to identify key aspects that contain the essence of the video. In this paper, we propose an approach that optimizes two criteria that a video summary should embody. The first criterion, {\textquotedblleft}coverage,{\textquotedblright} requires that the summary be able to represent the original video well. The second criterion, {\textquotedblleft}diversity,{\textquotedblright} requires that the elements of the summary be as distinct from each other as possible. Given a user-specified summary length, we propose a cost function to measure the quality of a summary. The problem of generating a précis is then reduced to a combinatorial optimization problem of minimizing the proposed cost function. We propose an efficient method to solve the optimization problem. We demonstrate through experiments (on KTH data, unconstrained skating video, a surveillance video, and a YouTube home video) that optimizing the proposed criterion results in meaningful video summaries over a wide range of scenarios. Summaries thus generated are then evaluated using both quantitative measures and user studies.}, keywords = {$K$-means, CAMERAS, combinatorial mathematics, combinatorial optimization, Cost function, data compression, Exemplar selection, Image segmentation, Internet, Iron, Length measurement, multimedia systems, Ncut, optimisation, Optimization methods, original video, Permission, shot segmentation, Surveillance, user specified summary length, video précis, Video sharing, video signal processing, Video summarization}, isbn = {1520-9210}, doi = {10.1109/TMM.2010.2058795}, author = {Shroff, N. and Turaga,P. and Chellapa, Rama} } @article {12352, title = {Parameterized Looped Schedules for Compact Representation of Execution Sequences in DSP Hardware and Software Implementation}, journal = {IEEE Transactions on Signal Processing}, volume = {55}, year = {2007}, month = {2007/06//}, pages = {3126 - 3138}, abstract = {In this paper, we present a technique for compact representation of execution sequences in terms of efficient looping constructs. Here, by a looping construct, we mean a compact way of specifying a finite repetition of a set of execution primitives. Such compaction, which can be viewed as a form of hierarchical run-length encoding (RLE), has application in many very large scale integration (VLSI) signal processing contexts, including efficient control generation for Kahn processes on field-programmable gate arrays (FPGAs), and software synthesis for static dataflow models of computation. In this paper, we significantly generalize previous models for loop-based code compaction of digital signal processing (DSP) programs to yield a configurable code compression methodology that exhibits a broad range of achievable tradeoffs. Specifically, we formally develop and apply to DSP hardware and software synthesis a parameterizable loop scheduling approach with compact format, dynamic reconfigurability, and low-overhead decompression}, keywords = {Application software, array signal processing, code compression methodology, compact representation, Compaction, data compression, Design automation, Digital signal processing, digital signal processing chips, DSP, DSP hardware, embedded systems, Encoding, Field programmable gate arrays, field-programmable gate arrays (FPGAs), FPGA, Hardware, hierarchical runlength encoding, high-level synthesis, Kahn process, loop-based code compaction, looping construct, parameterized loop schedules, program compilers, reconfigurable design, runlength codes, scheduling, Signal generators, Signal processing, Signal synthesis, software engineering, software implementation, static dataflow models, Very large scale integration, VLSI}, isbn = {1053-587X}, doi = {10.1109/TSP.2007.893964}, author = {Ming-Yung Ko and Zissulescu,C. and Puthenpurayil,S. and Bhattacharyya, Shuvra S. and Kienhuis,B. and Deprettere,E. F} } @conference {18568, title = {Field-to-frame transcoding with spatial and temporal downsampling}, booktitle = {Image Processing, 1999. ICIP 99. Proceedings. 1999 International Conference on}, volume = {4}, year = {1999}, month = {1999///}, pages = {271 -275 vol.4 - 271 -275 vol.4}, abstract = {We present an algorithm for transcoding high-rate compressed bitstreams containing field-coded interlaced video to lower-rate compressed bitstreams containing frame-coded progressive video. We focus on MPEG-2 to H.263 transcoding, however these results can be extended to other lower-rate video compression standards including MPEG-4 simple profile and MPEG-1. A conventional approach to the transcoding problem involves decoding the input bitstream, spatially and temporally downsampling the decoded frames, and re-encoding the result. The proposed transcoder achieves improved performance by exploiting the details of the MPEG-2 and H.263 compression standards when performing interlaced to progressive (or field to frame) conversion with spatial downsampling and frame-rate reduction. The transcoder reduces the MPEG-2 decoding requirements by temporally downsampling the data at the bitstream level and reduces the H.263 encoding requirements by largely bypassing H.263 motion estimation by reusing the motion vectors and coding modes given in the input bitstream. In software implementations, the proposed approach achieved a 5 times; speedup over the conventional approach with only a 0.3 and 0.5 dB loss in PSNR for the Carousel and Bus sequences}, keywords = {data compression, decoding, Encoding, field-coded interlaced video, field-to-frame transcoding, frame-coded progressive video, H.263 motion estimation, H.263 transcoding, high-rate compressed bitstreams, lower-rate compressed bitstreams, Motion estimation, MPEG-1, MPEG-2, MPEG-4, spatial downsampling, standards, temporal downsampling, transcoder, video coding, video compression standards}, doi = {10.1109/ICIP.1999.819593}, author = {Wee,S.J. and Apostolopoulos,J.G. and Feamster, Nick} } @article {14963, title = {Enhancing LZW Coding Using a Variable-Length Binary Encoding}, volume = {ISR-TR-1995-70}, year = {1995}, month = {1995///}, institution = {Institute for Systems Research, University of Maryland, College Park}, abstract = {We present here a methodology to enhance the LZW coding for text compression using a variable-length binary encoding scheme. The basic principle of this encoding is based on allocating a set of prefix codes to a set of integers growing dynamically. The prefix property enables unique decoding of a string of elements from this set. We presented the experimental results to show the effectiveness of this variable-length binary encoding scheme.}, keywords = {algorithms, data compression, Systems Integration Methodology}, url = {http://drum.lib.umd.edu/handle/1903/5654}, author = {Acharya,Tinku and JaJa, Joseph F.} } @article {15045, title = {VLSI Architectures and Implementation of Predictive Tree- Searched Vector Quantizers for Real-Time Video Compression}, volume = {ISR-TR-1992-48}, year = {1992}, month = {1992///}, institution = {Institute for Systems Research, University of Maryland, College Park}, abstract = {We describe a pipelined systolic architecture for implementing predictive Tree-Searched Vector Quantization (PTSVQ) for real- time image and speech coding applications. This architecture uses identical processors for both the encoding and decoding processes. the overall design is regular and the control is simple. Input data is processed at a rate of 1 pixel per clock cycle, which allows real-time processing of images at video rates. We implemented these processors using 1.2um CMOS technology. Spice simulations indicate correct operation at 40 MHz. Prototype version of these chips fabricated using 2um CMOS technology work at 20 MHz.}, keywords = {data compression, IMAGE PROCESSING, Signal processing, Speech processing, Systems Integration, systolic architecture, Vector quantization, VLSI architectures}, url = {http://drum.lib.umd.edu/handle/1903/5230}, author = {Yu,S.-S. and Kolagotla,Ravi K. and JaJa, Joseph F.} }