当前位置：搜档网 › Computational Approaches to Temporal Sampling of Video Sequences · 25

Computational Approaches to Temporal Sampling of Video Sequences · 25

Computational Approaches to Temporal Sampling

of Video Sequences

TIECHENG LIU

University of South Carolina

and

JOHN R.KENDER

Columbia University

Video key frame extraction is one of the most important research problems for video summarization,indexing,and retrieval. For a variety of applications such as ubiquitous media access and video streaming,the temporal boundaries between video key frames are required for synchronizing visual content with audio.In this article,we de?ne temporal video sampling as a uni?ed process of extracting video key frames and computing their temporal boundaries,and formulate it as an optimization problem. We?rst provide an optimal approach that minimizes temporal video sampling error using a dynamic programming process. The optimal approach retrieves a key frame hierarchy and all temporal boundaries in O(n4)time and O(n2)space.To further reduce computational complexity,we also provide a suboptimal greedy algorithm that exploits the data structure of a binary heap and uses a novel“look-ahead”computational technique,enabling all levels of key frames to be extracted with an average-case computational time of O(n log n)and memory usage of O(n).Both the optimal and the greedy methods are free of parameters, thus avoiding the threshold-selection problem that exists in other approaches.We empirically compare the proposed optimal and greedy methods with several existing methods in terms of video sampling error,computational cost,and subjective quality. An evaluation of eight videos of different genres shows that the greedy approach achieves performance very close to that of the optimal approach while drastically reducing computational cost,making it suitable for processing long video sequences in large video databases.

Categories and Subject Descriptors:I.4.9[Image Processing and Computer Vision]:Applications

General Terms:Algorithms

Additional Key Words and Phrases:Video summarization,key frame selection,video content analysis,ubiquitous media access, temporal video sampling

ACM Reference Format:

Liu,T.and Kender,https://www.sodocs.net/doc/5c6062478.html,putational approaches to temporal sampling of video sequences.ACM Trans.Multimedia https://www.sodocs.net/doc/5c6062478.html,mun.Appl.3,2,Article7(May2007),23pages.DOI=10.1145/1230812.1230813https://www.sodocs.net/doc/5c6062478.html,/10.1145/1230812. 1230813

1.INTRODUCTION

With the proliferation of automatic video acquisition devices and the development of storage technolo-gies,digital libraries increasingly have large collections of videos.Consequently,it is imperative to Authors’addresses:T.Liu,Department of Computer Science and Engineering,University of South Carolina,Columbia,SC29208; email:tiecheng@https://www.sodocs.net/doc/5c6062478.html,;J.R.Kender,Department of Computer Science,Columbia University,New York,NY10027;email: jrk@https://www.sodocs.net/doc/5c6062478.html,.

Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for pro?t or direct commercial advantage and that copies show this notice on the?rst page or initial screen of a display along with the full citation.Copyrights for components of this work owned by others than ACM must be honored.Abstracting with credit is permitted.To copy otherwise,to republish,to post on servers,to redistribute to lists,or to use any component of this work in other works requires prior speci?c permission and/or a fee.Permissions may be requested from Publications Dept.,ACM,Inc.,2Penn Plaza,Suite701,New York,NY10121-0701USA,fax+1(212)869-0481, or permissions@https://www.sodocs.net/doc/5c6062478.html,.

c 2007ACM1551-6857/2007/05-ART7$5.00DOI10.1145/1230812.1230813https://www.sodocs.net/doc/5c6062478.html,/10.1145/1230812.1230813

ACM Transactions on Multimedia Computing,Communications and Applications,Vol.3,No.2,Article7,Publication date:May2007.

2?T.Liu and J.R.Kender

ef?ciently process these videos for users to easily browse and search them.Also considering that video clients differ signi?cantly in computing capability,in display resolution,and in storage,it is also cru-cial to adapt these videos for ubiquitous media access[Chang2003],allowing different clients to access video content through various bandwidth-limited networks.

In recent years,video summarization[Chua and Ruan1995;Idris and Panchanathan1997;Mandal et al.1999;Ardizzone and Hacid1999]has emerged as an effective technique for indexing and quick ac-cess of video content.By analyzing the content of videos,video summarization techniques use drastically reduced data to represent the original videos.While video summarization methods differ signi?cantly in mathematical formulation,in the de?nition of content signi?cance,and in video feature extraction, they can be classi?ed into three categories based on the representation form of video summaries. (1)Key-frame-based approaches.In these approaches,a subset of representative frames:key frames,

which contain signi?cant visual content are selected as video summaries.The representative frames are extracted using different techniques,for example,video segmentation[Yeung and Liu1995;

Zhang et al.1995;Chua and Ruan1995],data clustering[Yeung and Yeo1996;Zhuang et al.

1998;Girgensohn and Boreczky1999],dynamic buffer model[Liu and Kender2001],minimum set distance[Chang et al.1999],and motion analysis[Wolf1996;Divakaran et al.2002;Liu et al.

2003].There are also techniques that have been developed with special emphasis on particular video genres like home videos[Kender and Yeo2000]and instructional videos[Liu and Kender 2002].

(2)Video skimming techniques.Short video segments,instead of video frames,are retrieved as con-

densed versions of the original videos.Smith and Kanade[1997]?rst proposed the video skimming method using a combination of image and language techniques.Sundaram and Chang[2001]fur-ther improved it by optimizing a utility function of video shots and by condensing“computable scenes”in videos.Recently,there have been improvements of video skimming techniques in the compressed domain[Peker and Divakaran2004],using a motion attention model[Ma and Zhang 2002],and via general temporal analysis of audio and visual data[Lee et al.2004].

(3)Image-based semantic summarization.In some video genres,synthesized images,for example,the

mosaicked images of the video scenes,can summarize video content better than the key frames do.Aner and Kender[2004]introduced a mosaic-based summarization approach to represent video scenes and applied it to situation comedy videos.An approach[Liu and Kender2003]of seman-tic summarization was developed for instructional videos by stitching the textual content in these videos without resorting to pixel-level image mosaicking.In addition,motion features can be ex-tracted for visualizing,summarizing,and searching video content[Chang et al.1997;Teodosio and Bender2005].

These three categories of video summarization approaches each have their own advantages and disadvantages,and they are applied to different applications to satisfy different users’requirements. The key-frame-based approaches,although having a simple form of visual summary,are still useful in a lot of scenarios due to the following reasons:(a)Key-frame-based summarization methods use sampled video frames to represent the original video content,thus the video summaries only need a very small storage space.The video index simply consists of frame numbers and pointers,and the key frames can be extracted on demand from videos for various applications.(b)In the applications of accessing and streaming videos over networks of limited and dynamically changing bandwidths, the key frame summaries can be used as highly compressed versions of the original videos.(c)For ubiquitous media access[Chang2003],video summaries at different levels-of-details are required, because video clients and network bandwidths vary signi?cantly.The key-frame-based approaches are able to provide a hierarchy of key frames for ubiquitous media https://www.sodocs.net/doc/5c6062478.html,paratively,video skimming ACM Transactions on Multimedia Computing,Communications and Applications,Vol.3,No.2,Article7,Publication date:May2007.

Computational Approaches to T emporal Sampling of Video Sequences?3 and semantic-image-based techniques are limited in providing video summaries at multiple levels of detail.

1.1The Challenges of Key-Frame-Based Video Summarization

As explained above,summarizing videos with key frames is still one of the most effective ways to provide ubiquitous media access.However,extracting video key frames and organizing them are still challenging in three aspects:the computational complexity,the support for ubiquitous media access, and the dif?culty of locating temporal boundaries between key frames.

First,to retrieve key frames from videos is a computationally expensive task,as an extended video contains more than a hundred thousand frames and a digital library may have thousands of digital videos.Prior key frame selection approaches[Yeung and Yeo1996;Zhuang et al.1998;Girgensohn and Boreczky1999;Chang et al.1999]achieve computational complexity at best O(n2)for a video of n frames;thus?nding a more ef?cient key-frame-based summarization approach is crucial.In most video key frame retrieval methods,the computation of content difference among video frames is usu-ally required,and it is a signi?cant part of the overall computation.Early research mainly used image histogram-based measures[Zhuang et al.1998;Chang et al.1999].Recently,more advanced and so-phisticated measures[Rubner et al.1998;Zhang and Chang2004]of video content difference have been proposed and shown to be effective in some applications[Robles-Kelly and Hancock2005].With more computationally expensive measures being introduced,the problem of computational complexity is getting more critical.

The second challenge comes from the lack of support for ubiquitous media access.For streaming videos over dynamically changing networks,any level of detail of the videos should be accessible. Prior research provides either a?xed number of key frames or a key frame hierarchy of?xed levels determined by the syntactic structure of the videos[Chua and Ruan1995;Zhang et al.1995].For unedited videos such as home and instructional videos,the syntactic structure of video shots is not available,making it dif?cult to build a key frame hierarchy using previous approaches[Chua and Ruan1995;Fan et al.2004].In addition,a desirable key frame selection method should be non-parametric,as it is dif?cult to determine the appropriate thresholds and parameters for different videos.

Another challenge in key-frame-based summarization approaches is the computation of the temporal boundaries among key frames.The temporal boundaries indicate which video segment one key frame summarizes.So in video streaming applications,they synchronize video key frames with the audio track.Equivalently,the temporal boundaries of the key frames form a partition of the video sequence. While previous research separates these two closely related problems,in this article,we solve these two problems:key frame selection and video partition,in one uni?ed process.Note that the video partition problem mentioned before is not equivalent to syntactic video segmentation,because the video partition is task-driven instead of structure-driven and is not restricted by video syntactic structures such as shots and scenes.

1.2Contributions

This article addresses these challenges in video key frame extraction and makes contributions in the following aspects:(a)We de?ne the problem of temporal video sampling and provide a uni?ed process for key frame selection and video partition by formulating it as an optimization problem.(b)We provide an optimal dynamic programming approach that solves the temporal video sampling problem in polynomial computational time.(c)We further present a greedy algorithm that exploits a binary-heap data structure and a“look-ahead”computational technique to achieve near optimal performance with O(n log n) average-case computational time and O(n)space.(d)Both the optimal dynamic programming approach ACM Transactions on Multimedia Computing,Communications and Applications,Vol.3,No.2,Article7,Publication date:May2007.

4?T.Liu and J.R.Kender

and the suboptimal greedy approach are nonparametric and can retrieve all levels of key frames for ubiquitous media access.

1.3Organization of the Article

The rest of the article is organized as follows.In Section2,we introduce more related work on key-frame-based video summarization approaches.Section3de?nes the problem of temporal video sampling,and formulates it as an optimization problem.In Section4,we present the optimal dynamic-programming approach that extracts video key frames in O(n4)time and O(n2)space.To reduce computational complexity,Section5further provides a greedy algorithm that retrieves all levels of key frames in O(n log n)average-case computational time and O(n)storage.In Section6,we demonstrate the ex-perimental results and compare our proposed algorithms with several other methods in terms of the de?ned performance measure,computational cost,and subjective quality.Finally,Section7gives the conclusions of the work.

2.RELATED RESEARCH

In this section,we introduce related research with special emphasis on the works of key-frame-based video summarization.Depending on whether a video segmentation process is required,key-frame-based video indexing and summarization methods can be classi?ed as segmentation-based approaches or non-segmentation approaches.

In the?rst category[Chua and Ruan1995;Zhang et al.1995,2003;Koh et al.1999;Rong et al. 2004],key frame selection is based on video segmentation,and one or more key frames are extracted from each syntactic unit,such as a video shot.Although effective on professionally edited videos[Smith and Kanade1998],these methods are limited by video segmentation accuracy[Boreczky and Rowe 1996]and are not quite suitable for semi-edited(e.g.,instructional)videos,unedited(e.g.,home)videos, or extended single-shot(e.g.,surveillance)videos.For these videos,video segmentation cannot provide much help for key frame selection due to the lack of structure.Even for edited videos,the segmentation-based methods can only retrieve a?xed number of key frames,or a hierarchy of?xed key frame levels, determined by the syntactic structure.For the applications of ubiquitous media access,a key frame hierarchy of all levels is usually required,as the network bandwidths and the users’requirements may vary in a wide range.These segmentation-based approaches are usually data-driven instead of task-driven,and hence it is dif?cult to use them to process such demands as“retrieving1%of video frames as key frames”.

Approaches in the second category[Yeung and Liu1995;Yeung and Yeo1996;Zhuang et al.1998; DeMenthon et al.1998;Hanjalic and Zhang1999;Girgensohn and Boreczky1999;Ferman and Tekalp 2003]do not need video segmentation as a prerequisite process,but they are usually restricted by com-putational complexity.In addition,an inherent dif?culty in these methods is the search of appropriate thresholds or parameters in order to extract a target number of key frames;likewise,the computation of temporal boundaries among key frames is ignored in most of these methods.Some approaches in this category are described in the following.

In the unsupervised clustering approach[Zhuang et al.1998],video frames are grouped into clusters and the frames that are closest to the cluster centroids are extracted as key frames.Hanjalic and Zhang [1999]further improved the clustering method with an unsupervised clustering-validity analysis to retrieve not only key frames but also the previews of videos.In Zhuang et al.[1998],the?rst video frame is always selected as a cluster.For the following frames,their distances to the existing clusters are measured.If the minimum distance is larger than a prede?ned threshold,the frame is chosen as a new cluster;otherwise it is combined with the nearest cluster.In Zhuang et al.[1998],parameter selection is an intrinsic problem.To extract a certain number of key frames,?nding the appropriate ACM Transactions on Multimedia Computing,Communications and Applications,Vol.3,No.2,Article7,Publication date:May2007.

Computational Approaches to T emporal Sampling of Video Sequences?5 cluster size is very dif?cult.Iterative adjustment of the threshold is computationally expensive,and there is no guarantee of convergence.

Chang et al.[1999]provided a video indexing approach that converts the key frame selection problem to the problem of searching the minimum set-cover of video frames with a semi-Hausdorff distance de?-nition.Unfortunately,the minimum set-cover problem is a well-known NP-complete problem.Although an approximation algorithm is proposed in Chang et al.[1999]to solve the problem in O(n2)time and space,the computational complexity is still high for long video sequences.Moreover,the approxima-tion algorithm has the same parameter selection and convergence problems as those in the clustering method.

Yeung and Liu[1995]provided a tolerance-band method to extract video key frames,and used it as a preprocessing step for video shot clustering.The tolerance-band method selects the?rst frame as a key frame,and then searches the frames after it.If a subsequent frame has a distance to the key frame larger than a designated threshold,this new frame is selected as the next key frame.Similar to the clustering and the set-cover methods,it still suffers from the threshold selection problem,and it cannot guarantee the retrieval of a designated number of key frames.

Sun and Kankanhalli[2000]provided a clustering-based method to retrieve representative frames and to use them for video summarization and browsing.A video sequence is?rst divided into units of an equal number of frames.In each unit,the histogram distance between the?rst and the last frame is considered as the“content change”of the unit.All the content changes are sorted.At each iteration, a?xed proportion of the units with small content changes are removed,and the remaining units are merged.The number of units is tuned iteratively until a desirable number is reached.This method is similar to the tolerance-band method in nature,with an improvement of the iterative tuning of the threshold.Unfortunately,two problems still exist in this method.First,the difference between the?rst and the last frame in a unit does not re?ect the content redundancy of the unit,since the two end frames can be very similar while the middle frames are quite different.Second,the method also suffers from the problem of?nding appropriate parameters for unit size and for the proportion of units to be removed in each iteration.

Lee and Kim[2002]formulated the video key-frame-selection problem from the perspective of signal processing.They extend signal sampling and quantization theory to this application.However,in Lee and Kim’s method,the content difference between frames is measured as pixel intensity difference, which is very sensitive to image noise and motion.In addition,the method was only tested on a very short video clip of41frames.

Some video key frame selection methods[Wolf1996;Divakaran et al.2002;Fauvet et al.2004] are based on motion analysis.In Wolf’s[1996]method,video motion is measured as the sum of the magnitudes of optical?ow of each pixel,and the video key frames are retrieved at the local minima of the motions to avoid the frames with motion blur.Fauvet’s[2004]method retrieves a?xed number of key frames.However,for the application of ubiquitous media access,a hierarchy of video key frames is desirable.In both Wolf[1996]and Fauvet et al.[2004],the computation is not ef?cient since they require the optical?ow computation for each video frame.Divakaran et al.[2002]developed a very ef?cient key frame selection method based on the analysis of motion activities in videos.In Divakaran et al.[2002],motion activity is considered as a measure of summarizability,and more video key frames are retrieved from the video segment of high motion activities.This method can also be used to retrieve a hierarchy of video key frames.

In Chiu et al.[2000],videos are represented as strings,with“1”representing the boundary frames and“0”representing the video frames within segments,and a standard genetic algorithm is applied for incremental video segmentation.In this method,the?tness function is de?ned as the weighted sum of key-frame distances;it does not consider the content difference between the key frames and the original ACM Transactions on Multimedia Computing,Communications and Applications,Vol.3,No.2,Article7,Publication date:May2007.

6?T.Liu and J.R.

Kender

……

……………………………)(1p f )(k p f f (1))

(n f τττ1

τ f (2)Fig.1.Illustration of the temporal video sampling problem:given a video sequence f (1),f (2),...,f (n ),?nd k optimal key frames f (p 1),...,f (p k )and their temporal boundaries τ1,...,τk +1.

video frames.After video segmentation,the boundary frames and the ?rst frame of the ?rst segment are selected as key frames,which may not be the optimal key frames for some videos.In addition,this work was only evaluated on a lecture video in which different segments (e.g.,Powerpoint slide shots,talking head shots)can be easily separated by measuring histogram differences.

There are also key-frame selection approaches particularly designed for video streaming applications

[Ho et al.2004;Zhou and Liou 2002].Zhou and Liou [2002]provided a nonlinear video sampling scheme for applications of video streaming over bandwidth-restrained networks,with the consideration of the constraints of client video buffers.However,this method does not specify how to extract a key frame hierarchy ,and the problem of high computational cost still exists.

3.TEMPORAL VIDEO SAMPLING

We propose four desirable features for video key frame selection.First,a computationally ef?cient algorithm is required.Second,the memory usage of such an algorithm should also be relatively small.Third,the temporal boundaries between key frames need be determined in the key frame selection process.Finally ,all levels of key frames need to be retrieved for ubiquitous media access.

Considering the limitations of previous approaches,we propose temporal video sampling ,a uni?ed process for both key frame selection and video partition,which is de?ned as follows:Given a de?nition of semantic distance between video frames,compute all levels of key frames and their temporal boundaries in a computationally ef?cient way ,for the applications of video indexing and ubiquitous media access.Besides extracting key frames with respect to users’requirements,another goal of temporal video sampling is to ?nd the key-frame temporal boundaries,also called the partition points in this article.These temporal boundaries are essential in video streaming applications where key frames need to be synchronized with audio.In addition,the temporal boundaries help interactive browsing and searching of video content by specifying which video segment one key frame summarizes.

Note that temporal video sampling is task-oriented instead of structure-driven:The tasks of temporal video sampling are such as “providing users with the 20best key frames for browsing video content”and “?nding the top 50key frames to transmit over a bandwidth-limited network”,instead of “choosing one key frame per video shot.”The methods presented in this article are for temporally sampling videos at a rate of O (10)?O (103)(sampling one key frame per tens to thousands of frames).This range of sampling rate is especially useful for video streaming and ubiquitous media access.

3.1Optimization Criterion for T emporal Video Sampling

In this subsection,we propose an optimization criterion for temporal video sampling.Denote a con-tinuous video signal as f (t )and a discrete video sequence as f (m ).Suppose f (p 1),f (p 2),...,f (p k )are the k key frames to be extracted and τ1,...,τk +1are the temporal boundaries among them.In this ACM Transactions on Multimedia Computing,Communications and Applications,Vol.3,No.2,Article 7,Publication date:May 2007.

Computational Approaches to T emporal Sampling of Video Sequences ?7

article,τi ,1≤i ≤k +1,are also called “partition points”because they partition a video into k segments.These temporal boundaries are essential for interactive access and search of video content.τi indicates the temporal boundary between key frames f (p i ?1)and f (p i ).For video streaming applications,the temporal boundaries,{τi },determine when to display the next key frame.Speci?cally ,key frame f (p i )is displayed starting at time τi /λand ending at τi +1/λ,where λis the frame rate of the video sequence (for MPEG videos,λ=29.97frames per second).Equivalently ,key frame f (k )summarizes the video segment [f (τi ),f (τi +1)).

To evaluate the quality of the selected key frames,a distance de?nition,d (·,·),between video frames is required in order to measure the similarity of video content.Theoretically ,any metric de?nition can be used as the distance.For example,the L 1histogram distance is widely used in research for its low computational complexity and robustness to motions and noise.Finding an appropriate distance (or similarity)measure between two images is a well-researched topic,and a large amount of literature is available [Rubner et al.1998;Zhang and Chang 2004;Robles-Kelly and Hancock 2005].We assume,in this article,that a distance that well measures the content difference of video frames is given,and,based on that,we propose computational approaches to sampling video sequences.The experimental results,as will be introduced in Section 6,will show the effectiveness of our proposed methods,using two different distance de?nitions.

Given a distance measure d (·,·)between video frames,the distance between two videos f (t )and g (t )(t ∈[0,T ])is de?ned as D (f (t ),g (t ))= 1T T

d 2(f (t ),g (t ))dt .(1)This distanc

e is a Euclidean metric in nature,measuring the normalized L 2-distance o

f two videos.Specially when

g (t )is a temporally sampled version of f (t ):g (t )=f (p i ),t ∈[t i ,t i +1),i =1...k ,the above equation is revised as D (f (t ),g (t ))= 1T k i =1 t i +1t i

d 2(f (t ),f (p i ))dt .(2)Extending this de?nition to discret

e video sequences,the key frame sequence is expressed as

g (m )=f (p i ),τi ≤m <τi +1,

where i =1,...,k and τ1,...,τk +1are the k +1temporal boundaries.As the sampled video sequence g (m )has the same duration as the original video,τ1=1and τk +1=n +1,where n is the total number of frames.For video streaming applications,a key frame f (p i )is displayed during the temporal interval (τi /λ,τi +1/λ).Hence the distance of these two video sequences is D (f (·),g (·))= 1n k i =1τi +1?1 j =τi

d 2(f (j ),f (p i )).(3)W

e further de?ne the temporal video sampling error (VSE)o

f selectin

g k key frames {f (p 1),...,f (p k )}from a video sequence f (·),as

E (f (·),k )=k

i =1τi +1?1 j =τi d 2(f (j ),f (p i )).(4)

ACM Transactions on Multimedia Computing,Communications and Applications,Vol.3,No.2,Article 7,Publication date:May 2007.

8?T.Liu and J.R.Kender

The temporal sampling error de?ned in Eq.4re?ects the deviation of the sampled video sequence from the original sequence.By minimizing the temporal sampling error,the key frame sequence that is closest in visual content to the original sequence is retrieved.This optimization criterion allows a content-based distance to be used,thus making it a more general and accurate measure than the regular signal-level SNR measure.Since the video sampling error (VSE)accumulates the visual differences of the frame sequences,by selecting an appropriate distance d (·,·),the content difference between the key frames and the original video is well represented.

3.2Optimal k -Selection of Video Sequence

The problem of selecting k optimal key frames (with respect to the temporal sampling error)is de?ned as the optimal k-selection problem ,and it is formulated as follows.

Given a number k,k

min p i ,τi ,i =1..k E (f (·),k ).(5)

Solving this optimization problem is a nontrivial task.It requires the solving of two subproblems—optimal key frame selection and optimal video partition—in one integrated process.In other words,both {f (p i )}and {τi }need to be solved with respect to the de?ned optimization criterion.In comparison,most previous work only focuses on one of these two subproblems.For example,the clustering-based approach [Zhuang et al.1998]does not explicitly provide temporal boundaries,and the video segmen-tation approach [Boreczky and Rowe 1996]does not select key frames with respect to an optimization criterion.

After the optimal k -selection problem is solved,all levels of key frames can be retrieved and orga-nized in a hierarchical structure,allowing ?exible video content access and ubiquitous media access.Such an optimal k -selection problem re?ects the demands of users and/or the requirements of network bandwidths.For the applications of browsing and searching video content,a full key frame hierarchy enables content search at any level of detail.For the applications of ubiquitous media access,a hier-archy of key frames allows the dynamic decision of frame dropping for maximizing the visual content transmitted.

4.OPTIMAL APPROACH USING DYNAMIC PROGRAMMING

In searching of the optimal k key frames,one straightforward way is to investigate all possible combi-nations of k key frames and to ?nd the optimal selection,but that takes n k computational time.The computational cost is excessively expensive.However,we may apply a dynamic programming approach to reduce the computational complexity .The problem of selecting k optimal key frames is converted to a k -step decision problem by exploiting the optimal substructure that exists within the optimal solution.This optimal approach takes O (n 4)time to retrieve all levels of key frames,as we will show in the details in this section.

The optimal dynamic-programming method ?rst locates the optimal partition points.We show in Lemma 1that as long as the partition points are ?xed,the key frames can be retrieved and the video sampling error can be determined.

L EMMA 1.Given k +1partition points τ1,τ2,...,τk +1,?nding the optimal k key frames and com-puting the minimum video sampling error E (f (·),k )take O (n 2)time,where n is the total number of frames.

ACM Transactions on Multimedia Computing,Communications and Applications,Vol.3,No.2,Article 7,Publication date:May 2007.

Computational Approaches to T emporal Sampling of Video Sequences ?9

……Step 1

Step 2Step k-1Step k

Fig.2.Illustration of the dynamic programming approach for ?nding k optimal partition points.

De?ne E (f (·),α,β,m )as the minimum video sampling error (VSE)of choosing m key frames from {f (α),dots ,f (β?1)}.Obviously ,

E (f (·),τi ,τi +1,1)=

min τi ≤p <τi +1τi +1?1 j =τi d 2(f (j ),f (p ))and

E (f (·),k )=k

i =1E (f (·),τi ,τi +1,1).

The computation of E (f (·),τi ,τi +1,1)takes O ((τi +1?τi )2)time.Suppose the optimal partition points τ1,τ2,...,τk +1are determined:the complexity of computing the minimum VSE and ?nding the optimal k key frames is then O (n 2),since (τ2?τ1)2+(τ3?τ2)2+···+(τk +1?τk )2≤(τk +1?τ1)2=n 2.One extension of the conclusion is that the computation of E (f (·),α,β,m )and ?nding m optimal key frames in {f (α),...,f (β?1)}take O ((β?α)2)time.

4.1Dynamic Programming Process

L EMMA 2.For a given k,the optimal k key frames and their temporal boundaries can be retrieved using dynamic programming,in O (kn 3)time.

We propose the dynamic programming approach for optimal key frame selection.The optimal k -partition problem is reduced to a k -step dynamic programming problem.To partition a video sequence {f (1),f (2),...,f (n )}into k segments,we need k +1partition points τ1,τ2,...,τk ,τk +1.It is obvious that τ1=1and τk +1=n +1,since the ?rst segment always starts at the beginning and the last segment ends at the last frame.

As shown in Figure 2,to calculate the k +1optimal partition points,we use a k -step dynamic pro-gramming process to determine the partition points τ2,...,τk .The ?rst partition point τ1is always ?xed (τ1=1).The second partition point τ2can be selected from {2,...,n ?k },and the minimum video sampling error E ?(f (·),τ1,τ2,1)is calculated in a straightforward way as mentioned in this section.We record the minimum VSE for each possible τ2value.The next partition point τ3is then selected from {3,...,n ?k +1}.For each possible value of τ3,we compute the minimum VSE of selecting two key frames

ACM Transactions on Multimedia Computing,Communications and Applications,Vol.3,No.2,Article 7,Publication date:May 2007.

10?T.Liu and J.R.Kender

between frame f (τ1)and f (τ3):E ?(f (·),τ1,τ3,2)=min 2≤τ2

Starting from the last key frame,a general backtracking computation is applied to retrieve all the partition points τ1,τ2,...,τk +1.We follow the back-pointers to the prestored prior optimal subsequences,and retrieve these optimal k partition points.According to Lemma 1,after the k +1partition points are ?xed,the optimal k key frames {f (p 1),...,f (p k )}can also be easily determined.

As shown in this dynamic programming process,to compute these k optimal partition points,an array of size k (n ?k +1)is needed to store the optimal subsequences for ?nal retrieval,and another n ?k +1sized array is used to store the optimal values.Therefore,total memory usage is O (k (n ?k )).As for computational complexity ,from Lemma 1,we know that given two partition points τj and τj +1,the computation of E ?(f (·),τj ,τj +1,1)is (τj +1?τj )2.At the ?rst step of dynamic programming,it is necessary to compute E ?(f (·),τ1,τj ,1)for j =2,...,n .So the computation at this step is n j =2(j ?1)2=O (n 3).At each step j ,the minimum VSE E ?(f (·),τ1,τj ,j ?1)for all j ≤τj ≤n are already calculated,so we only need to compute the E (f (·),τj ,τj +1,1)}for all τj and τj +1.Since the constraints j ≤τj ≤n and τj <τj +1≤n +1hold,at step j ,the computation is

n +1

τj +1=j +1(τj +1?j )2=c (n ?j )3+o ((n ?j )3),

where c is a constant.At the last step,τk +1=n +1,and the computation is only O ((n ?k )3).Therefore,the total computation of retrieving the k optimal key frames is k ?1 j =1

c (n ?j )3 +O ((n ?k )3)=O (kn 3).

4.2Key Frame Hierarchy

T HEOREM 1.For a video sequence of n frames,an optimal approach based on dynamic programming can retrieve all levels of key frames together with their temporal boundaries in O (n 4)time.

Similarly to the process of retrieving the optimal k partition points,to retrieve the key frame at any level,we use an n -step dynamic programming process similar to that shown in Figure 2.For any value k ,we can retrieve the optimal k -partition points using the recorded values from step 1to step k .Since there is a total of n steps,the computation of a full hierarchy of all levels of key frames is O (n 4),and the storage usage is obviously O (n 2).Considering that the computation of frame distance is usually the most expensive operation,we may precompute the distances between all pairs of frames and save the results in an array .

Unlike the prior research that builds a key frame hierarchy based on syntactic video structures,this optimal approach generates key frames at all levels,thus it is more useful for the applications where a seamless conversion between different key frame levels is required,such as video streaming over a low-bandwidth and dynamically changing network.This dynamic programming approach retrieves a whole key frame hierarchy in polynomial time (O (n 4))and O (n 2)space.At the same time,it guarantees ACM Transactions on Multimedia Computing,Communications and Applications,Vol.3,No.2,Article 7,Publication date:May 2007.

Computational Approaches to Temporal Sampling of Video Sequences?11 Table I.The Data Elements in a Binary Heap Node N(p i)

E(f(p i))Impact value,key of the binary heap.

E left(f(p i))The left video sampling error(left VSE)of f(p i).

E right(f(p i))The right video sample error(right VSE)of f(p i).

τleft(p i)The left temporal boundary of f(p i),i.e.,the boundary between f(p i)and f(p i?1).

τright(p i)The right temporal boundary of f(p i),i.e.,the boundary between f(p i)and f(p i+1).

?τ(p i)The look-ahead temporal boundary.

an optimal solution at each level of key frames.While this algorithm is applicable to short video clips of thousands of frames,we develop a more ef?cient algorithm for extended video sequences,as we will explain in detail in the following section.

5.GREEDY APPROACH USING BINARY HEAP

The dynamic programming approach,although optimal,is still computationally expensive.To further reduce the computational complexity,we provide a suboptimal greedy approach that takes O(n log n) average-case computational time to build a whole key frame hierarchy and that needs only O(n)memory. The greedy approach uses a bottom-up level-to-level optimal approach:The optimal k?1key frames are selected from the k key frames that are already extracted.It starts with all the n frames.At each process it removes one key frame according to the optimization criterion.It continues this process until a target number of key frames are retrieved,or the whole key frame hierarchy is built.In implementing the greedy approach,we exploit the data structure of a binary heap and apply a novel computational technique called“look-ahead computation,”which dramatically reduces computation.

In this greedy approach,it is an optimal process from one to the next,but it does not guarantee the selected k(other than n?1)key frames are optimal ones.We empirically show in Section6that the greedy approach achieves results very close to the optimal solution,and it is superior to the prior key frame selection methods in terms of the video sampling error we de?ned.

5.1Data Structure

We exploit the data structure of a binary heap to facilitate the computation.As shown in Table I,each node relates to one key frame in the video sequence.We denote the node that relates to the key frame f(p i)as N(p i).The node N(p i)contains the information of the two temporal boundaries(partition points)associated with it:τleft(p i),the temporal boundary between f(p i)and its previous key frame f(p i?1),andτright(p i),the temporal boundary between f(p i)and its next key frame f(p i+1).Obviously,τleft(p i)=τi andτright(p i)=τi+1.

We then de?ne two values associated with the node N(p i),the left video sampling error E left(f(p i)) and the right video sampling error E right(f(p i)),as

E left(f(p i))=p i?1

m=τi

d2(f p

,f m)

and

E right(f(p i))=τi+1?1

m=p i

d2(f p

,f m).

Thus the video sampling error of choosing f(p i)as the key frame for the segment{fτ

i ,...,fτ

i+1?1

}is the

sum of the left and the right VSEs:E(f(·),τi,τi+1,1)=E left(f p

i )+E right(f p

).The total video sampling

ACM Transactions on Multimedia Computing,Communications and Applications,Vol.3,No.2,Article7,Publication date:May2007.

12?T.Liu and J.R.Kender

error (VSE)of choosing the k video key frame {f p 1,...,f p k }therefore is

E (f (·),1,n ,k )=k

i =1(E left (f (p i ))+E right (f (p i ))).

Each node N (p i )also has an “impact value” E (f (p i )),which represents the change of VSE if the key frame f (p i )is removed in the next step.The impact values are the keys of the binary heap.Suppose {f (p 1),...,f (p k )}are the extracted k key frames and the VSE is E (f (·),1,n ,k ),if f (p i )is deleted in the next step,the VSE of the remaining k ?1key frames {f (p 1),...,f (p i ?1),f (p i +1),...,f (p k )}is changed to

E (f (·),1,n ,k ?1)=E (f (·),1,n ,k )+ E (f (p i )).(6)

The greedy algorithm selects the k ?1key frames from the k already selected key frames.It is obvious from Eq.6that to minimize the VSE of the k ?1key frames,is also to remove the node with the minimum impact value.The impact values always show how much VSE will change if in the future the frame is deleted.In a binary heap,the nodes are arranged according to the keys (the impact values)and the root node always contains the minimum key ,so the greedy process is to delete the root node and to reheapify all the remaining nodes.

The node N (p i )also contains other information such as the pointers to the previous and the next key frames.A complete list of the data elements of a node N (p i )is stated in Table I.In this table,the “look-ahead”temporal boundary of a frame f (p i )refers to the new temporal boundary between f (p i ?1)and f (p i +1)if f (p i )is deleted.

5.2Computation of Greedy Sampling

The greedy algorithm for temporal video sampling,or greedy sampling in short,consists of three main steps:Initialization,Delete-Min Operation,and Look-Ahead Computation.First,it initializes the values of the nodes and builds the binary heap.Next,it deletes the node with the minimum key (impact value)and updates the values of its temporally neighboring https://www.sodocs.net/doc/5c6062478.html,st,it updates the impact values and other elements of the nodes that are affected by deleting the node using a “look-ahead computation.”It repeats the last two steps until the user-designated level of k key frames is achieved,or a whole key frame hierarchy is built.The process is illustrated in Figure 3.

5.2.1Initialization.The greedy algorithm starts with the original n frames.Each frame is rep-resented as a node in the binary heap.For each node N (i ),its impact value E (f (i ))is initialized as E (f (i ))=?????d 2(f (i ),f (i +1)),i =1

d 2(f (i ?1),f (i )),i =n min {d 2(f (i ),f (i +1)),d 2(f (i ?1),f (i ))},1

The impact value E (f (i ))measures the change of the video sampling error if f (i )is deleted.Initially ,all frames in the video sequence are key frames,and the VSE value is 0.For each node N (i ),the left and right temporal boundaries are initialized as τleft (i )=i and τright (i )=i +1,respectively .At the beginning,all frames are key frames,and there is no sampling error.For any 1≤i ≤n ,E left (i )=E right (i )=0.Additionally ,the look-ahead temporal boundary is set as ?τ(i )= i ,i f d (f (i ),f (i ?1))≤d (f (i ),f (i +1)),i +1,otherwise .

ACM Transactions on Multimedia Computing,Communications and Applications,Vol.3,No.2,Article 7,Publication date:May 2007.

Computational Approaches to Temporal Sampling of Video Sequences ?13)1(f )2(f )3(f )4(f )5(f )6(f )

7(f

(a)

)1(f )2(f )3(f )4(f )6(f )7

(b))1(f )2(f )3(f )4(f )6(f )7

(c)

Fig.3.Illustration of the three steps of the greedy algorithm:(a)Initialization;(b)Delete-Min;(c)Look-ahead Computation.The processes (b)and (c)are repeated until the heap is exhausted.In this ?gure,we use different gray scales to visualize the impact values (keys)of the nodes.Note that we reevaluate the impact values of nodes 4and 6using look-ahead computation in step (c),so the positions of these two nodes in the binary heap change accordingly .

A binary heap is then built using the impact values as keys.We use the regular heapify process with the computation of O (n log n )to build the binary heap.

5.2.2Delete-Min Operation.At this step,we delete the node with the minimum impact value in the heap.Since a binary heap always has the minimal key at its root node,this is simply a “delete-min”operation.Assume the key frames {f (p 1),...,f (p k )}are already selected at level k ,the binary heap then contains k nodes N (p i ),i =1,···,k .If node N (p j )is the root node,we delete N (p j ),leaving k ?1remaining key frames {f (p 1),...,f (p j ?1),f (p j +1),...,f (p k )}.The video sampling error is updated as

E (f (·),1,n ,k ?1)=E (f (·),1,n ,k )+ E (f (p j )).

Since frame f (p j )is temporally adjacent to frames f (p j ?1)and f (p j +1),the deletion of the node N (p j )causes changes in the values in N (p j ?1)and N (p j +1).We update the data elements of these two nodes:

τright (p j ?1)←?τ(p j ),

τleft (p j +1)←?τ(p j ),E right (p j ?1)← ?τ(p j )?1m =p j ?1+1d 2(f (m ),f (p j ?1)),E left (p j +1)← p j +1?1m =?τ(p j

)d 2(f (m ),f (p j +1)).As for computational expense,since the root node of a binary heap has the minimum key ,locating and removing the root node take constant time.After the root node is deleted,a regular reheapify process is applied to maintain the data structure of the binary heap.This reheapify process takes O (log k )computational time for a heap of k nodes.

ACM Transactions on Multimedia Computing,Communications and Applications,Vol.3,No.2,Article 7,Publication date:May 2007.

14?T.Liu and J.R.Kender

f )

(a) f )2+(b)

)

(?p )(?p )(?p ??1?j left j left j right 1+j right 1+j right 1?j left 11j j left j right +?Fig.4.Illustration of the look-ahead computation and the update of nodes.(a)The state of the key frames and their temporal boundaries before f (p i )is deleted.(b)After the deletion,the temporal boundaries of f (p i ?1)and f (p i +1)are updated.The new look-ahead boundaries ?τ(p i ?1)and ?τ(p i +1)are recalculated and updated;the impact values E (f (p j ?1))and E (f (p j +1))are also reevaluated,using the look-ahead computation technique.

5.2.3Look-Ahead Computation.At level k ,suppose that the extracted k key frames are f (p 1),...,f (p k )and N (p i )is the root node,then N (p i )is deleted in the delete-min step,and the remaining nodes are reheapi?ed.Among the remaining k ?1nodes N (p 1),...,N (p i ?1),N (p i +1),...,N (p k ),the data elements (e.g.,impact values,look-ahead boundaries)of N (p i ?1)and N (p i +1)are affected,as f (p i ?1)and f (p i +1)are temporally adjacent to f (p i ).Therefore,we need to update the impact values and the other data elements of the nodes N (p j ?1)and N (p j +1).Such an updating process is called “look-ahead computation,”because the updated values are to be used in the future —if at a future level,N (p j ?1)or N (p j +1)is the root node of the heap and is deleted,the video sampling error (VSE),and the temporal boundaries can be directly updated with the information stored in the nodes.

In the level-to-level greedy sampling,the affected nodes are those whose corresponding frames are temporally adjacent to the deleted key frame.Because only a constant number of nodes are af-fected by the deletion of the root node,the computation is greatly reduced.We use the look-ahead computational technique to further reduce the computational complexity .In the case of retrieving k ?1key frames from a set of k frames,a straightforward process is needed to test each of the k candidate frames for deletion and to compute the VSE values,which would mean a computation of O (k )at step k ,yielding a total computation of O ( n k =1k )=O (n 2).However,with the look-ahead computation,we may reduce the average-case computation to O (n log n ),as we will explain in the following.

The binary heap stores the impact values of the nodes,and optimizing VSE is changed to a simple delete-min operation.The look-ahead computation updates the VSE values and the temporal bound-aries so that they can be used in future levels,and the computation is local.Without loss of gener-ality ,we suppose N (p i )is the root node at level k .In the following,we show the look-ahead com-putation of the impact value and the temporal boundaries for node N (p j ?1);a similar approach is applied to N (p j +1).Figure 4illustrates the process of look-ahead computation after frame f (p j )is deleted.

ACM Transactions on Multimedia Computing,Communications and Applications,Vol.3,No.2,Article 7,Publication date:May 2007.

Computational Approaches to Temporal Sampling of Video Sequences ?15

As de?ned here,the look-ahead temporal boundary of N (p j ?1),?τ(p j ?1),is the partition point (between f (p j ?2)and f (p j +1))that minimizes the local sampling error (LSE)in {f (p j ?2),...,f (p j +1?1)}:

LSE (p j ?2,?τ(p j ?1),p j +1)=

min p j ?2≤m

LSE (p j ?2,m ,p j +1)=m ?1

t =p j ?2d 2(f (p j ?2),f (t ))+p j +1?1 t =m d 2(f (p j +1),f (t )).

The local sampling error,LSE (p j ?2,m ,p j +1),refers to the video sampling error in the segment {f (p j ?2),...,f (p j +1?1)}if m is selected as the new boundary between f (p j ?2)and f (p j +1).The impact value of the node N (p j ?1)is thus updated as

E (f (p j ?1))=LSE (p j ?2,?τ(p j ?1),p j +1)?E right (f (p j ?2))?E left (f (p j +1)).

The look-ahead temporal boundary ?τ(p j ?1)of node N (p j ?1)can be found by using a cumulative summation.First we calculate the left-most value,LSE (p j ?2,p j ?2+1,p j +1).All other values can be derived iteratively ,proceeding to the right:

LSE (p j ?2,t +1,p j +1)=LSE (p j ?2,t ,p j +1)

+d 2(f (p j ?2),f (t ))?d 2(f (p j +1),f (t )).

And the ?τ(p j ?1)is calculated as

?τ(p j ?1)=argmin t {LSE (p j ?2,t ,p j +1)},t =p j ?2,...,p j +1?1.

The computation of all these LSE values takes 2(p j +1?p j ?2)units of frame-distance computation.The update of node N (p j +1)follows the same approach,so the look-ahead computation after the deletion of the node N (p j )takes 2(p j +1?p j ?2)+2(p j +2?p j ?1)units of frame distance computation.

5.3Computational Complexity

Memory usage of the algorithm is O (n )by using the data structure of a binary heap.The average-case computational complexity is O (n log n ),as follows.Heap initialization takes O (n log n )time.At each level k ,searching for the frame with minimum impact value and updating current boundaries take constant time,or O (n )time over all levels.After the root node is deleted,reheapify takes O (log k )time at level k .For all levels,the reheapify process takes O (n log n )time.

As for the look-ahead computation,since the impact of frame deletion is limited to the neighboring frames,the computation is drastically reduced.As shown in the last subsection,if frame f (p j )is removed at level k ,then the look-ahead computation takes 2(p j +1?p j ?2)+2(p j +2?p j ?1)units of distance computation.Since the average interval between two adjacent key frames at level k is n /k ,the average computation time at level k for look-ahead computation is 8n /k ,giving the total computation time of n

k =18n /k =O (n log n )for all https://www.sodocs.net/doc/5c6062478.html,bining all processes (initialization,delete-min,and

look-ahead computation),the greedy sampling has an average-case computational time of O (n log n ).Considering that this computational time is for the retrieval of all levels of the key frame hierarchy ,the reduction of computational complexity from polynomial to O (n log n )is signi?cant.

6.PERFORMANCE EVALUA TION

In our evaluation,we include several well-known key frame selection algorithms for comparison.The evaluated algorithms are:(1)our optimal dynamic programming method (Optimal );(2)our subopti-mal greedy method (Greedy );(3)a trivial ?xed-rate temporal sampling method (Fixed-Rate );(4)the

ACM Transactions on Multimedia Computing,Communications and Applications,Vol.3,No.2,Article 7,Publication date:May 2007.

16?T.Liu and J.R.Kender

Table II.The Experimental Videos Used in Evaluation.The Abbreviations of the

Video Genres Are:Doc–Documentary,Home–Home Video,Sitcom–Situation

Comedy,News–News Video,Instru–Instructional Video

Short Video Clips Long Video Sequences

Video1Video2Video3Video4Video5Video6Video7Video8

Duration30sec45sec46sec83sec27min39min40min75min

Frame#91413451365250148,45070,73871,203134,068

Genre Doc Home Doc Sitcom Doc Sitcom News Instru

tolerance-band method(Band)[Yeung and Liu1995];(5)the unsupervised clustering method(Cluster) [Zhuang et al.1998];and(6)the set-cover method(Set)[Chang et al.1999].The?xed-rate method is a trivial method,as it samples video frames uniformly.Because methods(3)–(6)do not explicitly provide the temporal boundaries between key frames,we add a postprocessing step to extract the key frame boundaries that minimize the video sampling error for the given key frames.The testing data consists of eight videos,with four short video clips and four long video sequences;the details of these videos are shown in Table II.We deliberately chose videos of different genres for a more comprehensive evaluation.

6.1Evaluation Based on Video Sampling Error

We?rst compare the optimal dynamic programming algorithm and the suboptimal greedy algorithm with the four existing methods with respect to the Video Sampling Error(VSE).Although these methods allow any metric to be used,it is unrealistic to evaluate all possible metrics.In the following experiments, we evaluate these methods on two well-known and widely used distance metrics,and we expect a similar conclusion holds on other metrics.The?rst distance we evaluated is the L1metric of image histograms; the second metric we used is the Earth Mover’s Distance(EMD),developed and?rst introduced to computer vision research by Rubner et al.[1998].As shown in Rubner et al.[1998],EMD is an effective metric for measuring image content differences.In our evaluation,the signature used for EMD is the histogram in YUV color space with a size of4×4×4.

In Figures5and6,we evaluate different key frame selection methods on four short videos using Nor-malized Video Sampling Error.As shown in Section4,the dynamic programming method guarantees an optimal solution,hence it has the minimum VSE among all methods.Therefore,we use the dynamic programming VSE as the reference,and for the other?ve methods,their VSE is normalized by that of the dynamic programming:Normalized VSE=VSE/VSE optimal,where VSE optimal is the video sampling error achieved by the dynamic programming method.Obviously,the normalized VSE should be greater than1,and lesser values indicate better results.The sampling density in the?gures means the percent-age of frames selected as key frames.In Figures5and6,two different metrics(L1histogram distance and EMD)are applied to video1–4.The results clearly show that the greedy algorithm achieves the best performance among the?ve methods in terms of VSE,and the VSE difference between the greedy and the optimal approaches is very small.In all the videos tested and all the sampling densities evaluated, the greedy algorithm produces much less VSE than the other four methods do.Loosely speaking,in this evaluation setting,the clustering method is the second closest to the optimal method in terms of VSE,and the trivial?xed-rate sampling has the worse performance.

We further evaluate these methods on long video sequences(video5–8)with the L1histogram metric. Due to the restrictions of computational complexity and memory usage,some methods are not appli-cable to long video sequences.The optimal method requires O(n2)memory,and so does the set-cover method.Since long video sequences have104–105frames,the demand on memory and storage is exces-sive for the optimal approach and the set-cover method.The clustering method requires an iterative process to adjust the threshold,and it does not guarantee the convergence for any number of clusters. Therefore,for long video sequences,we only evaluated the methods that are applicable to long video ACM Transactions on Multimedia Computing,Communications and Applications,Vol.3,No.2,Article7,Publication date:May2007.

Computational Approaches to Temporal Sampling of Video Sequences

?17

3456Video Sampling Density (Video # 1)

N o r m a l i z e d V S E

0123456Video Sampling Density (Video # 2)N o r m a l i z e d V S E 01

3456Video Sampling Density (Video # 3)N o r m a l i z e d V S E 0123456

Video Sampling Density (Video # 4)

N o r m a l i z e d V S E

https://www.sodocs.net/doc/5c6062478.html,parison of the Normalized Video Sampling Error (Normalized VSE)among ?ve different key frame selection methods,using the L 1histogram metric.

sequences—our greedy method (Greedy),the ?xed-rate sampling (Fixed-Rate),the tolerance-band method [Yeung and Liu 1995](Band),and,additionally ,the motion-based method [Divakaran et al.2002](Motion).The motion-based method [Divakaran et al.2002]is included because it can be con-sidered as a very ef?cient approach to the set-cover method.The experimental results of the video sampling errors are shown in Table III.

Table III clearly shows that our greedy algorithm produces the least video sampling errors at the evaluated sampling densities.As the sampling density decreases (Fewer key frames are selected),the video sampling errors of the evaluated methods all increase accordingly .The tolerance-band method is better than ?xed-rate sampling at high sampling densities,but at low sampling densities (e.g.,1%),it is not much better than ?xed-rate sampling in terms of the video sampling error.The VSE of the motion-based method is closest to that of the greedy algorithm,and it is signi?cantly better than the tolerance band method and the ?xed rate sampling.There are two reasons that the motion-based method is consistently worse than the greedy algorithm in the evaluation.First,the motion-based method does not explicitly optimize the video sampling error.Second,our evaluation criterion is based on image histograms,but histogram differences may be very small for the videos of high motion activities.

6.2Computational Time and Memory Usage

As shown in Sections 4and 5,the optimal dynamic-programming method takes O (n 4)computational time and O (n 2)storage,and the greedy approach only needs O (n log n )average-case computational time and O (n )space.The low computational complexity of the greedy algorithm makes it more suitable to process long video sequences and large video databases.In Table IV,we measure the computa-tional times of the ?ve nontrivial key frame selection methods.The evaluation platform is a Pentium 4Workstation with 1.7G Hz CPU and 512M memory .Table IV shows the times of building key frame

ACM Transactions on Multimedia Computing,Communications and Applications,Vol.3,No.2,Article 7,Publication date:May 2007.

18?T.Liu and J.R.

Kender

45678910

Video Sampling Density (Video # 1)

N o r m a l i z e d V S E

0123456789

10Video Sampling Density (Video # 2)

N o r m a l i z e d V S E

45678910

Video Sampling Density (Video # 3)N o r m a l i z e d V S E

012345678910Video Sampling Density (Video # 4)

N o r m a l i z e d V S E

https://www.sodocs.net/doc/5c6062478.html,parison of the Normalized Video Sampling Error (Normalized VSE)among ?ve different key frame selection methods,using the EMD metric.

hierarchies that contain all levels of key frames,using the EMD metric.Strictly speaking,the cluster-ing and the set-cover methods cannot retrieve all levels of key frames because they do not guarantee convergence for all settings of the parameters.In our implementation,we only retrieve the key frame levels that can be computed using these two methods.When evaluating long video sequences with the EMD metric,only the greedy methods and the trivial ?xed-rate sampling methods are applicable.The ?xed-rate method takes a minimum computational time.The optimal,the tolerance-band,the unsupervised clustering,and the set-cover methods are not applicable to long video sequences due to their excessive memory requirements and extreme computational complexity .A rough estimation of the computational time,based on the computational cost of EMD,indicates that it takes years to build a full key frame hierarchy using the methods other than the greedy and the ?xed-rate sampling,assuming that the demand of memory and storage can be satis?ed.

Table IV clearly shows that the greedy algorithm takes much less computation time than the clus-tering,the tolerance-band,and the set-cover methods.Besides excessive computational cost,another inherent dif?culty in the tolerance-band,the clustering,and the set-cover methods is the parameter selection problem:how to select the appropriate thresholds or parameters to retrieve key frames at a target sampling density .Although the parameters can be adjusted iteratively ,the iterative search-ing process is usually computationally expensive,and there is no guarantee of convergence.Conse-quently ,most of the computational time of the tolerance band method is spent on searching for the appropriate threshold to achieve the desired sampling density;a similar cost is also incurred in the clustering and the set-cover methods.By comparison,the greedy algorithm has no parameter selec-tion problem,for it is a nonparametric algorithm and guarantees that any number of key frames are retrievable.

ACM Transactions on Multimedia Computing,Communications and Applications,Vol.3,No.2,Article 7,Publication date:May 2007.

Computational Approaches to Temporal Sampling of Video Sequences?19 Table III.Video Sampling Error(in106)of Different Methods on Long Video Sequences

with L1Histogram Metric

Video Sampling Error at Different Sampling Densities

Method1%2%5%10%20%

Greedy169.6774.2828.0913.32 6.26 Video5Fixed-Rate471.96195.1678.7942.3922.19

Band915.56258.5259.5423.539.10

Motion273.17135.4537.2318.367.82

Greedy371.01102.8326.9910.47 4.29 Video6Fixed-Rate1076.43490.40165.1385.5141.99

Band1305.33369.4561.8420.09 6.47

Motion521.42172.0335.7916.27 5.40

Greedy426.85183.1466.2228.3312.61 Video7Fixed-Rate1066.28457.79199.5493.2245.04

Band1533.53571.39151.1854.4519.57

Motion647.32252.1890.3541.0715.23

Greedy127.4966.6826.8912.52 5.38 Video8Fixed-Rate371.41214.04108.8654.3725.52

Band553.01267.5076.6326.318.48

Motion279.13152.2047.3518.36 6.69 Table IV.The Computational Time and the Number of Distances Computed Using

Different Methods With EMD Metric

Computation Time(in minutes)Number of Distances Computed(in103)

Method video1video2video3video4video1video2video3video4

Optimal8326427829734099029323125

Greedy 4.2 6.3 6.512.328.443.944.787.8

Band461121343972897638042147

Cluster42951455412325367121976

Set671651866704099029323125

Computation Time(in hours)Number of Distances Computed(in106)

Method video5video6video7video8video5video6video7video8

Greedy 6.28.99.819.2 2.57 3.75 4.138.12

Table V.The Ratio,in Percentage,of the

Computational Time for Frame Distance

Calculation to the Overall Computational Time.

EMD Metric is Used in the Measurement

Video#Optimal Greedy Band Cluster Set

video167.3%92.4%85.9%75.5%83.4%

video246.7%95.2%93.1%77.1%74.7%

video345.8%94.0%82.0%67.1%68.5%

video414.4%97.6%73.9%49.9%63.7%

In Table V,we decompose the computational time in Table IV into the frame distance computation time and nondistance computation time,and measure the proportion of the distance-computation time. We can see from Table V that in the greedy algorithm,most computational time is spent on the frame distance calculation.For long video sequences(video5–8),the percentages of distance computational time in the greedy algorithm are94.4%,96.0%,96.0%,and96.3%,respectively.Since the greedy algo-rithm maintains both the frame-distance computation and the nondistance computation at O(n log n), the proportion of distance computation time varies in a small range in all the videos,regardless of the ACM Transactions on Multimedia Computing,Communications and Applications,Vol.3,No.2,Article7,Publication date:May2007.

20?T.Liu and J.R.Kender

Table VI.Subjective Evaluation of Video Sampling Quality.The Larger

Value is Better.“NA”Indicates that the Method is Not Evaluated On Long

Video Sequences Because of its Excessive Computational Complexity

Method video1video2video3video4video5video6video7video8

Optimal 4.4 4.1 4.0 4.1NA NA NA NA

Greedy 4.1 4.1 4.0 4.0 1.0 1.0 1.0 1.0

Fixed0.50.40.20.10000

Band 1.1 1.2 1.1 1.3NA NA NA NA

Cluster 3.2 3.5 3.8 3.7NA NA NA NA

Set 1.7 1.7 1.9 1.8NA NA NA NA

frame number n.For other key frame selection methods,Table V shows a trend of decreasing proportion of distance computation time with the increasing frame numbers.

The low space complexity O(n)of the greedy algorithm further makes it suitable for processing long video sequences.The optimal and the set-cover methods require O(n2)storage,which restricts them from being applied to long video sequences.On our evaluation platform,for the longest video sequence (video8),it takes only4.3minutes to retrieve all levels of key frame using the L1histogram metric and19.2hours to do so using the EMD metric;the memory usage is merely18.3megabytes.Since the greedy algorithm is free of parameters,it avoids the problem of parameter selection and guarantees the retrieval of any number of key frames.

6.3Subjective Evaluation of Video Sampling Quality

Subjective evaluation of the quality of video key frames is a dif?cult task,and there is no standard evaluation methodology available.Most previous work has presented sample key-frame images to indi-cate the subjective quality.In this work,we conduct a user study and evaluate the quality of video key frames based on users’subjective ratings.First,we use the different methods(with the EMD metric)to extract key frames and their temporal boundaries from the eight testing videos(video1–8)at different sampling densities.Then we ask10referees(undergraduate students)to view the results and to give subjective ratings.The guidelines we give the referees are:(a)the key frames should summarize the video content well;(b)the key frames should not miss important visual content of the video;(c)the key frames should be as little redundant as possible;and(d)the visual content of the key frames should synchronize well with the audio.

With these guidelines,the referees view the key frame sequences at?ve different sampling densities (1%,2%,5%,10%,20%).The key frames are displayed as a slide show,and they change at the temporal boundaries.This simulates the applications of video streaming on a low-bandwidth network,and of accessing previews of videos.Each referee is required to rank the quality of video key frames retrieved by different methods,and we assign scores according to the ranking list:The lowest one has a score of 0,and each higher one has one more score.For example,if a referee ranks the key-frame quality as “optimal>greedy>cluster>set>?xed>band,”then the scores are:optimal–5,greedy–4,cluster–3,set-cover–2,?xed-rate–1,and tolerance-band–0.In the case of long video sequences,we can only compare the?xed-rate method with the greedy method,so a ranking of“greedy>?xed”gives score1to the greedy and0to the?xed-rate sampling.We take the average of all the scores rated by the referees as the?nal score for each method.The results of the subjective evaluation using this methodology are shown in Table VI.

The subjective evaluation results in Table VI show that the optimal method and the greedy method have comparatively better subjective quality on videos1–4with the EMD metric.For long video se-quences,the referees unanimously agree that the greedy algorithm achieves better results than the trivial?xed-rate video frame sampling.For the short video sequences,the average scores in Table VI ACM Transactions on Multimedia Computing,Communications and Applications,Vol.3,No.2,Article7,Publication date:May2007.

物流信息管理习题答案

参考答案：第一章一：1.× 2.√ 3. × 二：1. B 2. B 3. B 案例分析： 1.物流信息系统的概念：以采集、处理和提供物流信息服务为目标的系统，即可以采集、输入、处理数据，可以存储、管理、控制物流信息，可以向使用者报告物流信息，辅助决策，使其达到预定的目标。 2.根据沃尔玛中国公司的信息系统的应用案例可以看到，物流信息系统能够解决下述问题：适度的库存、需求和供给的调节、缩短从订货到发货的时间、提高订单处理的精度、防止发货和配送出现差错、回答信息咨询、降低物流总成本等。这些问题的解决能够大大地提高物流的效率，从而提升企业的竞争力。基于互联网和信息技术的物流信息系统，由于其投入相对少，又能显著提高企业物流的营运效率和管理水平，因而使越来越多的企业愿意采纳这项管理和信息技术为一体的系统第二章一：1. √ 2. × 3. √ 二：1.C 2.A 3.D 第三章一：1.× 2.√ 3.× 二：1. B 2. D 3.ABC 第四章一：1. × 2. √ 3. × 二：1. C 2. B 3. C 案例分析答案要点： 1、每件货品及包装箱都附有电子标签。 2、通过射频包装标签上的信息了解分销中心内的存货情况。 3、标签读写装置能自动读取产品的目的地及装运数据。 4、货物到达店铺时，读取器只需自动读取最外面的包装标签信息，一个包装，一张表单，店员就可得知箱内所有产品信息，无需再单独盘点商品。 5、仓库门口还装有读取器，当有货物进入或被拿出仓库时，店内的电脑系统就会自动更新仓库内存货信息和店面铺货情况。 6、当一天营业结束时，店员再也不用逐件清点货品，只要拿着读取器扫过衣服，一次可以读5～7件的货品信息，这样大大节省了店员清点货品的时间。 7、为顾客制作电子标签，可集成于顾客的手机中，也可以是单独的一张智能卡，顾客的个人信息及在本店中的购买信息会被输入标签中.当顾客进入商店，商店门口的读取器即读取了顾客随身携带的电子标签信息，顾客所有信息即会被显示在店铺的电脑屏上，店员根据这些信息推荐适合顾客的衣服。 8、虚拟试衣间玻璃幕墙上装有读取装置，当顾客拿着带有电子标签的衣服进入试衣间时，读取装置就自动读取所有信息，虚拟配衣程序也随之启动。

新版人教版高中语文课本的目录。

必修一阅读鉴赏第一单元1.*沁园春?长沙……………………………………毛泽东3 2.诗两首雨巷…………………………………………戴望舒6 再别康桥………………………………………徐志摩8 3.大堰河--我的保姆………………………………艾青10 第二单元4.烛之武退秦师………………………………….《左传》16 5.荆轲刺秦王………………………………….《战国策》18 6.*鸿门宴……………………………………..司马迁22 第三单元7.记念刘和珍君……………………………………鲁迅27 8.小狗包弟……………………………………….巴金32 9.*记梁任公先生的一次演讲…………………………梁实秋36 第四单元10.短新闻两篇别了，“不列颠尼亚”…………………………周婷杨兴39 奥斯维辛没有什么新闻…………………………罗森塔尔41 11.包身工………………………………………..夏衍44 12.*飞向太空的航程……………………….贾永曹智白瑞雪52 必修二阅读鉴赏第一单元1.荷塘月色…………………………………..朱自清2.故都的秋…………………………………..郁达夫3.*囚绿记…………………………………..陆蠡第二单元4.《诗经》两首氓采薇5.离骚………………………………………屈原6.*《孔雀东南飞》(并序) 7.*诗三首涉江采芙蓉《古诗十九首》短歌行……………………………………曹操归园田居(其一)…………………………..陶渊明第三单元8.兰亭集序……………………………………王羲之9.赤壁赋……………………………………..苏轼10.*游褒禅山记………………………………王安石第四单元11.就任北京大学校长之演说……………………..蔡元培12.我有一个梦想………………………………马丁?路德?金1 3.*在马克思墓前的讲话…………………………恩格斯第三册阅读鉴赏第一单元1.林黛玉进贾府………………………………….曹雪芹2.祝福………………………………………..鲁迅3. *老人与海…………………………………….海明威第二单元4.蜀道难……………………………………….李白5.杜甫诗三首秋兴八首(其一) 咏怀古迹(其三) 登高6.琵琶行(并序)………………………………..白居易7.*李商隐诗两首锦瑟马嵬(其二) 第三单元8.寡人之于国也…………………………………《孟子》9.劝学……………………………………….《荀子》10.*过秦论…………………………………….贾谊11.*师说………………………………………韩愈第四单元12.动物游戏之谜………………………………..周立明13.宇宙的边疆………………………………….卡尔?萨根14.*凤蝶外传……………………………………董纯才15.*一名物理学家的教育历程……………………….加来道雄第四册阅读鉴赏第一单元1.窦娥冤………………………………………..关汉卿2.雷雨………………………………………….曹禹3.*哈姆莱特……………………………………莎士比亚第二单元4.柳永词两首望海潮(东南形胜) 雨霖铃(寒蝉凄切) 5.苏轼词两首念奴娇?赤壁怀古定风波(莫听穿林打叶声) 6.辛弃疾词两首水龙吟?登建康赏心亭永遇乐?京口北固亭怀古7.*李清照词两首醉花阴(薄雾浓云愁永昼) 声声慢(寻寻觅觅) 第三单元8.拿来主义……………………………………….鲁迅9.父母与孩子之间的爱……………………………..弗罗姆10.*短文三篇热爱生

初中语文古文赏析曹操《短歌行》赏析(林庚)

教育资料《短歌行》《短歌行》赏析(林庚) 曹操这一首《短歌行》是建安时代杰出的名作，它代表着人生的两面，一方面是人生的忧患，一方面是人生的欢乐。而所谓两面也就是人生的全面。整个的人生中自然含有一个生活的态度，这就具体地表现在成为《楚辞》与《诗经》传统的产儿。它一方面不失为《楚辞》中永恒的追求，一方面不失为一个平实的生活表现，因而也就为建安诗坛铺平了道路。这首诗从“对酒当歌，人生几何”到“但为君故，沉吟至今”，充分表现着《楚辞》里的哀怨。一方面是人生的无常，一方面是永恒的渴望。而“呦呦鹿鸣”以下四句却是尽情的欢乐。你不晓得何以由哀怨这一端忽然会走到欢乐那一端去，转折得天衣无缝，仿佛本来就该是这么一回事似的。这才是真正的人生的感受。这一段如是，下一段也如是。“明明如月，何时可掇?忧从中来，不可断绝。越陌度阡，枉用相存。契阔谈宴，心念旧恩。月明星稀，乌鹊南飞。绕树三匝，何枝可依。”缠绵的情调，把你又带回更深的哀怨中去。但“山不厌高，海不厌深”，终于走入“周公吐哺，天下归心”的结论。上下两段是一个章法，但是你并不觉得重复，你只觉得卷在悲哀与欢乐的旋涡中，不知道什么时候悲哀没有了，变成欢乐，也不知道什么时候欢乐没有了，又变成悲哀，这岂不是一个整个的人生吗?把整个的人生表现在一个刹那的感觉上，又都归于一个最实在的生活上。“我有嘉宾，鼓瑟吹笙”，不正是当时的情景吗?“周公吐哺，天下归心”，不正是当时的信心吗? “青青子衿”到“鼓瑟吹笙”两段连贯之妙，古今无二。《诗经》中现成的句法一变而有了《楚辞》的精神，全在“沉吟至今”的点窜，那是“青青子衿”的更深的解释，《诗经》与《楚辞》因此才有了更深的默契，从《楚辞》又回到《诗经》，这样与《鹿鸣》之诗乃打成一片，这是一个完满的行程，也便是人生旅程的意义。“月明星稀”何以会变成“山不厌高，海不厌深”?几乎更不可解。莫非由于“明月出天山”，“海上生明月”吗?古辞说：“枯桑知天风，海水知天寒”，枯桑何以知天风，因为它高；海水何以知天寒，因为它深。唐人诗“一叶落知天下秋”，我们对于宇宙万有正应该有一个“知”字。然则既然是山，岂可不高?既然是海，岂可不深呢?“并刀如水，吴盐胜雪”，既是刀，就应该雪亮；既是盐，就应该雪白，那么就不必问山与海了。山海之情，成为漫漫旅程的归宿，这不但是乌鹊南飞，且成为人生的思慕。山既尽其高，海既尽其深。人在其中乃有一颗赤子的心。孟子主尽性，因此养成他浩然之气。天下所以归心，我们乃不觉得是一个夸张。 .

物流管理信息系统习题答案

第一章物流管理信息系统概述一、填空题 1．时效性可识别性可存储性可传递性可利用性可共享性2．计划信息控制及作业信息统计信息支持信息3．及时准确实用经济二、选择题 1．D 2．C 三、名词解释 1．信息答：信息是客观事物存在方式和运动状态的反映。 2．物流信息答：物流信息是反映物流活动内容的信息的总称。狭义的物流信息是指直接产生于物流活动的信息。广义的物流信息是指直接产生于物流活动以及与其他流通活动有关的信息。 3．物流管理信息系统答：物流管理信息系统是指以人员为主导，利用计算机硬件、软件、网络通信设备及其他办公设备，进行物流信息的收集、存储、传输、处理、维护和输出，为物流管理者及其他管理人员提供信息服务或战略、决策支持的人机结合系统。四、简答题 1．物流信息具有哪些特点？答：物流信息具有以下几方面特点。（1）信息量大，涉及面广物流信息在现代物流的多品种、小批量、多层次、多频度及个性化的服务活动中大量产生，且随物流环节的不同，广泛分布在不同的生产厂家、仓库、货场、配送中心、运输商、零售商、客户等众多场所。随着物流信息技术的推广和应用，物流信息这种量大、面广的特征将俞趋明显。（2）来源多样，种类繁多

物流管理信息系统物流信息不仅包括企业内部产生的各种物流信息，还包括企业间因商业活动而产生的物流信息，以及与物流活动相关的其他信息，如相关的法律信息、市场信息、消费者需求信息等。因而，物流信息的来源是多样化的，且信息种类复杂多样。（3）更新快，实时性强物流信息是伴随着物流活动的开展而产生的。随着经济的发展，市场竞争越来越激烈，物流活动的开展也越来越频繁。物流信息的更新速度因此而变快，这使得物流信息表现出非常强的实时性。物流信息的这一特性，要求我们必须及时掌握最新的物流信息，为物流管理和决策提供依据。 2．物流信息具有哪些作用？答：物流信息具有以下几方面作用。（1）有助于物流活动各环节的相互衔接物流活动的高效运行，要求物流运输、装卸、仓储、包装、配送、流通加工等各环节之间有计划地精确衔接，物流信息就是衔接各个环节的纽带。（2）有助于物流活动的协调与管理在企业内部，物流信息有助于协调不同部门之间的物流流程活动。在企业之间，物流信息的有效传递能够反馈不同企业之间的物流活动，有利于各企业合理地组织、协调和管理物流活动。（3）有助于物流决策水平的提高物流信息是企业进行物流决策的重要依据，特别是客户需求方面的物流信息，对物流决策具有关键作用。例如，配送中心根据货物的配送量和车辆使用信息，合理地安排配送方式、路线、车辆等物流活动，以减少作业成本等。有效地利用物流信息，有利于企业作出正确的物流决策，从而实现作业目标，提高企业竞争力。 3．处理物流信息应符合哪些要求？答：物流信息的处理应符合以下要求。（1）及时物流信息的处理要及时是指对物流活动的实时信息要及时地进行记录、反馈、加工、检索和传递，使物流信息尽可能地与物流活动同步。这是因为，物流信息具有更新快、实时性强的特点，在一定时间内具有重要价值的物流信息，很可能在下一时间点就变得分文不值。因此，为了充分利用物流信息的使用价值，促使物流活动的顺利、高效进行，必须及时地对物流信息进行处理。（2）准确物流信息的处理要准确是指处理物流信息所依据的原始数据必须可靠，且·2·

高中语文文言文曹操《短歌行(对酒当歌)》原文、翻译、赏析

曹操《短歌行【对酒当歌】》原文、翻译、赏析译文原文面对美酒应该高歌，人生短促日月如梭。对酒当歌，人生几何？好比晨露转瞬即逝，失去的时日实在太多！譬如朝露，去日苦多。席上歌声激昂慷慨，忧郁长久填满心窝。慨当以慷，忧思难忘。靠什么来排解忧闷？唯有狂饮方可解脱。何以解忧？唯有杜康。那穿着青领（周代学士的服装）的学子哟，你们令我朝夕思慕。青青子衿，悠悠我心。正是因为你们的缘故，我一直低唱着《子衿》歌。但为君故，沉吟至今。阳光下鹿群呦呦欢鸣，悠然自得啃食在绿坡。呦呦鹿鸣，食野之苹。一旦四方贤才光临舍下，我将奏瑟吹笙宴请宾客。我有嘉宾，鼓瑟吹笙。当空悬挂的皓月哟，你运转着，永不停止；明明如月，何时可掇？我久蓄于怀的忧愤哟，突然喷涌而出汇成长河。忧从中来，不可断绝。远方宾客踏着田间小路，一个个屈驾前来探望我。越陌度阡，枉用相存。彼此久别重逢谈心宴饮，争着将往日的情谊诉说。契阔谈讌，心念旧恩。明月升起，星星闪烁，一群寻巢乌鹊向南飞去。月明星稀，乌鹊南飞。绕树飞了三周却没敛绕树三匝，何枝

翅，哪里才有它们栖身之所？可依？高山不辞土石才见巍峨，大海不弃涓流才见壮阔。（比喻用人要“唯才是举”，多多益善。）山不厌高，水不厌深。只有像周公那样礼待贤才（周公见到贤才，吐出口中正在咀嚼的食物，马上接待。《史记》载周公自谓： “一沐三握发，一饭三吐哺，犹恐失天下之贤。”），才能使天下人心都归向我。周公吐哺，天赏析曹操是汉末杰出的政治家、军事家和文学家，他雅好诗章，好作乐府歌辞，今存诗22首，全是乐府诗。曹操的乐府诗多描写他本人的政治主张和统一天下的雄心壮志。如他的《短歌行》，充分表达了诗人求贤若渴以及统一天下的壮志。《短歌行》是政治性很强的诗作，主要是为曹操当时所实行的政治路线和政策策略服务的，但是作者将政治内容和意义完全熔铸在浓郁的抒情意境之中，全诗充分发挥了诗歌创作的特长，准确而巧妙地运用了比兴手法，寓理于情，以情感人。诗歌无论在思想内容还是在艺术上都取得了极高的成就，语言质朴，立意深远，气势充沛。这首带有建安时代"志深比长""梗概多气"的时代特色的《短歌行》，读后不觉思接千载，荡气回肠，受到强烈的感染。对酒当歌，人生几何？譬如朝露，去日苦多。慨当以慷，幽思难忘。何以解忧，唯有杜康。青青子衿，悠悠我心。但为君故，沈吟至今。呦呦鹿鸣，食野之苹。我有嘉宾，鼓瑟吹笙。明明如月，何时可掇？忧从中来，不可断绝。越陌度阡，枉用相存。契阔谈，心念旧恩。月明星稀，乌鹊南飞，绕树三匝，何枝可依？山不厌高，海不厌深，周公吐哺，天下归心。《短歌行》是汉乐府的旧题，属于《相和歌?平调曲》。这就是说它本来是一个乐曲的名称，这种乐曲怎么唱法，现在当然是不知道了。但乐府《相和歌?平调曲》中除了《短歌行》还有《长歌行》，唐代吴兢《乐府古题要解》引证古诗“长歌正激烈”，魏文帝曹丕《燕歌行》“短歌微吟不能长”和晋代傅玄《艳歌行》“咄来长歌续短歌”等句，认为“长歌”、“短

电子商务物流管理__试卷一及参考答案

试卷一名词解释（每小题3分，共15分） 1、电子商务物流 2、联合运输 3、物流一体化 4、供应链 5、国际多式联合运输二、填空题（每空0.5分，共10分） 1、按照物流在供应链中的作用不同，可以将物流分类为、、、、 2、包装的功能：、、、。 3、仓储管理的基本原则：、、、。 4、电子商务物流技术的评价标准：、、。 5、物流成本管理的原则：、、、。三、判断正误并说明理由（每小题3分，共15分） 1、物流能够消除商品生产和消费之间的场所间隔、时间间隔、社会间隔。 2、“我需要什么就采购什么”是电子商务采购的观念。 3、虚拟配送就是在虚拟环境中建立虚拟配送中心，并不是实际存在的配送中心。 4、国际物流节点是整个物流系统或与节点相接的物流信息的传递、收集、处理和发送的集中地。 5、物流成本管理的对象是成本。四、选择题(单选或多选，请将正确选项的标号填写在题干后的括号内，每小题2分，共10分) 1、物流被认为是： A、第一利润源 B、第二利润源 C、第三利润源 D、不产生利润 2、仓库管理模式可以分为：ABC A、自建仓库仓储 B、租赁仓库仓储 C、第三方仓储 D、供应商仓储 3、以顾客为中心体现了物流网络营销的特点 A、职能化 B、信息化 C、柔性化 D、网络化 4、多式联运经营人责任期间是从接受货物之时起到交付货物之时止，在此期间对货主负全程运输责任，根据多式联运责任制的范围和索赔限额，目前国际上一般的做法有： A、统一责任制 B、分段责任制 C、修正统一责任制 D、独立责任制 5、根据供应链的研究对象及其范围，供应链可以分为： A、企业供应链 B、商业供应链 C、产品供应链 D、基于供应链合作伙伴关系的供应链五、简述题（每小题5分，共20分） 1、简述物流的功能。 2、简述电子商务交易的流程 3、简述企业竞价采购平台 4、简述区域公共物流信息平台的基本功能。 5、简述有效客户反应的作用。

高中外研社英语选修六Module5课文Frankenstein's Monster

Frankenstein's Monster Part 1 The story of Frankenstein Frankenstein is a young scientist/ from Geneva, in Switzerland. While studying at university, he discovers the secret of how to give life/ to lifeless matter. Using bones from dead bodies, he creates a creature/ that resembles a human being/ and gives it life. The creature, which is unusually large/ and strong, is extremely ugly, and terrifies all those/ who see it. However, the monster, who has learnt to speak, is intelligent/ and has human emotions. Lonely and unhappy, he begins to hate his creator, Frankenstein. When Frankenstein refuses to create a wife/ for him, the monster murders Frankenstein's brother, his best friend Clerval, and finally, Frankenstein's wife Elizabeth. The scientist chases the creature/ to the Arctic/ in order to destroy him, but he dies there. At the end of the story, the monster disappears into the ice/ and snow/ to end his own life. Part 2 Extract from Frankenstein It was on a cold November night/ that I saw my creation/ for the first time. Feeling very anxious, I prepared the equipment/ that would give life/ to the thing/ that lay at my feet. It was already one/ in the morning/ and the rain/ fell against the window. My candle was almost burnt out when, by its tiny light，I saw the yellow eye of the creature open. It breathed hard, and moved its arms and legs. How can I describe my emotions/ when I saw this happen? How can I describe the monster who I had worked/ so hard/ to create? I had tried to make him beautiful. Beautiful! He was the ugliest thing/ I had ever seen! You could see the veins/ beneath his yellow skin. His hair was black/ and his teeth were white. But these things contrasted horribly with his yellow eyes, his wrinkled yellow skin and black lips. I had worked/ for nearly two years/ with one aim only, to give life to a lifeless body. For this/ I had not slept, I had destroyed my health. I had wanted it more than anything/ in the world. But now/ I had finished, the beauty of the dream vanished, and horror and disgust/ filled my heart. Now/ my only thoughts were, "I wish I had not created this creature, I wish I was on the other side of the world, I wish I could disappear!” When he turned to look at me, I felt unable to stay in the same room as him. I rushed out, and /for a long time/ I walked up and down my bedroom. At last/ I threw myself on the bed/ in my clothes, trying to find a few moments of sleep. But although I slept, I had terrible dreams. I dreamt I saw my fiancée/ walking in the streets of our town. She looked well/ and happy/ but as I kissed her lips，they became pale, as if she were dead. Her face changed and I thought/ I held the body of my dead mother/ in my arms. I woke, shaking with fear. At that same moment，I saw the creature/ that I had created. He was standing/by my bed/ and watching me. His

人教版高中语文必修必背课文精编WORD版

人教版高中语文必修必背课文精编W O R D版 IBM system office room 【A0816H-A0912AAAHH-GX8Q8-GNTHHJ8】

必修1 沁园春·长沙（全文）毛泽东独立寒秋，湘江北去，橘子洲头。看万山红遍，层林尽染，漫江碧透，百舸争流。鹰击长空，鱼翔浅底，万类霜天竞自由。怅寥廓，问苍茫大地，谁主沉浮。携来百侣曾游，忆往昔峥嵘岁月稠。

恰同学少年，风华正茂，书生意气，挥斥方遒。指点江山，激扬文字，粪土当年万户侯。曾记否，到中流击水，浪遏飞舟。雨巷（全文）戴望舒撑着油纸伞，独自彷徨在悠长、悠长又寂寥的雨巷，我希望逢着一个丁香一样地

结着愁怨的姑娘。她是有丁香一样的颜色，丁香一样的芬芳，丁香一样的忧愁，在雨中哀怨，哀怨又彷徨；她彷徨在这寂寥的雨巷，撑着油纸伞像我一样，像我一样地默默彳亍着冷漠、凄清，又惆怅。她默默地走近，走近，又投出太息一般的眼光

她飘过像梦一般地，像梦一般地凄婉迷茫。像梦中飘过一枝丁香地，我身旁飘过这个女郎；她默默地远了，远了，到了颓圮的篱墙，走尽这雨巷。在雨的哀曲里，消了她的颜色，散了她的芬芳，消散了，甚至她的太息般的眼光丁香般的惆怅。撑着油纸伞，独自

彷徨在悠长、悠长又寂寥的雨巷，我希望飘过一个丁香一样地结着愁怨的姑娘。再别康桥（全文）徐志摩轻轻的我走了，正如我轻轻的来；我轻轻的招手，作别西天的云彩。那河畔的金柳，是夕阳中的新娘；波光里的艳影，在我的心头荡漾。软泥上的青荇，油油的在水底招摇；在康河的柔波里，我甘心做一条水草！那榆荫下的一潭，不是清泉，是天上虹揉碎在浮藻间，沉淀着彩虹似的梦。寻梦？撑一支长篙，向青草更青处漫溯，满载一船星辉，在星辉斑斓里放歌。

曹操《短歌行》其二翻译及赏析

曹操《短歌行》其二翻译及赏析引导语：曹操(155—220)，字孟德，小名阿瞒，《短歌行二首》是曹操以乐府古题创作的两首诗，第一首诗表达了作者求贤若渴的心态，第二首诗主要是曹操向内外臣僚及天下表明心迹。短歌行其二曹操周西伯昌，怀此圣德。三分天下，而有其二。修奉贡献，臣节不隆。崇侯谗之，是以拘系。后见赦原，赐之斧钺，得使征伐。为仲尼所称，达及德行，犹奉事殷，论叙其美。齐桓之功，为霸之首。九合诸侯，一匡天下。一匡天下，不以兵车。正而不谲，其德传称。孔子所叹，并称夷吾，民受其恩。赐与庙胙，命无下拜。小白不敢尔，天威在颜咫尺。晋文亦霸，躬奉天王。受赐圭瓒，钜鬯彤弓，卢弓矢千，虎贲三百人。威服诸侯，师之所尊。八方闻之，名亚齐桓。翻译姬昌受封为西伯，具有神智和美德。殷朝土地为三份，他有其中两分。整治贡品来进奉，不失臣子的职责。只因为崇侯进谗言，而受冤拘禁。后因为送礼而赦免，受赐斧钺征伐的权利。他被孔丘称赞，品德高尚地位显。始终臣服殷朝帝王，美名后世流传遍。齐桓公拥周建立功业，存亡继绝为霸首。

聚合诸侯捍卫中原，匡正天下功业千秋。号令诸侯以匡周室，主要靠的不是武力。行为磊落不欺诈，美德流传于身后。孔子赞美齐桓公，也称赞管仲。百姓深受恩惠，天子赐肉与桓公，命其无拜来接受。桓公称小白不敢，天子威严就在咫尺前。晋文公继承来称霸，亲身尊奉周天王。周天子赏赐丰厚，仪式隆重。接受玉器和美酒，弓矢武士三百名。晋文公声望镇诸侯，从其风者受尊重。威名八方全传遍，名声仅次于齐桓公。佯称周王巡狩，招其天子到河阳，因此大众议论纷纷。赏析《短歌行》 (“周西伯昌”)主要是曹操向内外臣僚及天下表明心迹，当他翦灭群凶之际，功高震主之时，正所谓“君子终日乾乾，夕惕若厉”者，但东吴孙权却瞅准时机竟上表大说天命而称臣，意在促曹操代汉而使其失去“挟天子以令诸侯”之号召，故曹操机敏地认识到“ 是儿欲据吾著炉上郁!”故曹操运筹谋略而赋此《短歌行 ·周西伯昌》。西伯姬昌在纣朝三分天下有其二的大好形势下，犹能奉事殷纣，故孔子盛称 “周之德，其可谓至德也已矣。 ”但纣王亲信崇侯虎仍不免在纣王前还要谗毁文王，并拘系于羑里。曹操举此史实，意在表明自己正在克心效法先圣西伯姬昌，并肯定他的所作所为，谨慎惕惧，向来无愧于献帝之所赏。并大谈西伯姬昌、齐桓公、晋文公皆曾受命“专使征伐”。而当今天下时势与当年的西伯、齐桓、晋文之际颇相类似，天子如命他“专使征伐”以讨不臣，乃英明之举。但他亦效西伯之德，重齐桓之功，戒晋文之诈。然故作谦恭之辞耳，又谁知岂无更讨封赏之意乎 ?不然建安十八年(公元 213 年)五月献帝下诏曰《册魏公九锡文》，其文曰“朕闻先王并建明德，胙之以土，分之以民，崇其宠章，备其礼物，所以藩卫王室、左右厥世也。其在周成，管、蔡不静，惩难念功，乃使邵康公赐齐太公履，东至于海，西至于河，南至于穆陵，北至于无棣，五侯九伯，实得征之。世祚太师，以表东海。爰及襄王，亦有楚人不供王职，又命晋文登为侯伯，锡以二辂、虎贲、斧钺、禾巨鬯、弓矢，大启南阳，世作盟主。故周室之不坏，系二国是赖。”又“今以冀州之河东、河内、魏郡、赵国、中山、常山，巨鹿、安平、甘陵、平原凡十郡，封君为魏公。锡君玄土，苴以白茅，爰契尔龟。”又“加君九锡，其敬听朕命。” 观汉献帝下诏《册魏公九锡文》全篇，尽叙其功，以为其功高于伊、周，而其奖却低于齐、晋，故赐爵赐土，又加九锡，奖励空前。但曹操被奖愈高，心内愈忧。故曹操在曾早在五十六岁写的《让县自明本志令》中谓“或者人见孤强盛，又性不信天命之事，恐私心相评，言有不逊之志，妄相忖度，每用耿耿。

管理信息系统第一章习题答案

管理信息系统（第四版）黄梯云主编第一章复习思考题答案：（1）什么是信息？信息和数据有何区别？答：信息是关于客观事实的可通信的知识。首先，信息是客观世界各种事物的特征的反映，其次，信息是可以通信的，最后，信息形成知识。信息的概念不同于数据。数据是记录客观事物的，可鉴别的符号，这些符号不仅包括数字还包括字符，文字，图形等。数据经过处理仍然是数据。处理数据是为了便于更好地解释。只有经过解释，数据才有意义，才成为信息。可以说，信息是经过加工之后，对客观世界产生影响的数据。同一数据，每个人的解释可能不同，其对决策的影响也可能不同。决策者利用经过处理的数据作出决策，可能取得成功，也可能遭受失败，关键在于对数据的解释是否正确，因为不同的解释往往来自不同的背景和目的。（2）试述信息流与物流，资金流，事物流的关系？答：组织中各项活动表现为物流，资金流，事物流和信息流的运动。“物流”是实物的流动过程。物质的运输，产品从原材料的采购，加工直至销售都是物流的表现形式。“资金流”指的是伴随物流而发生的资金的流动过程。“事物流”是各项管理活动的工作流程，如原材料进厂进行的验收，登记，开票，付款等流程，厂长作出决策前进行的调查研究，协商，讨论等流程。信息流伴随物流，资金流，事物流的流动而流动，既是其他各种流的表现和描述，又是由于掌握，指挥，控制其他流的运行和资源。（3）如何理解人是信息的重要载体和信息意义的解释者？答：信息系统包括信息处理系统和信息传输系统两个方面。信息处理系统对数据进行处理，使它获得心的结构与形态或者产生新的数据。由于信息的作用只有在广泛交流中才能充分发挥出来，因此，通信技术的就不极大地促进了信息系统的发展。广义的信息系统概念已经延伸到与通信系统相等同。这里的通信不仅之通讯，而且意味着人际交流和人际沟通，其中包含思想的沟通，价值观的沟通和文化的沟通。广义的咨询（沟通）系统强调“人”本身不但是一个重要的沟通工具，还是资讯意义的阐述者，所有的沟通媒介均需要使资讯最终可为人类五官察觉与阐述，方算是资讯的沟通媒介。（4）什么是信息技术？信息技术在哪些方面能给管理提供支持？答：广义而言，信息技术是指能充分利用与扩展人类信息器官功能的各种方法、工具与技能的总和。该定义强调的是从哲学上阐述信息技术与人的本质关系。中义而言，信息技术是指对信息进行采集、传输、存储、加工、表达的各种技术之和。该定义强调的是人们对信息技术功能与过程的一般理解。狭义而言，信息技术是指利用计算机、网络、广播电视等各种硬件设备及软件工具与科学方法，对文图声像各种信息进行获取、加工、存储、传输与使用的技术之和。该定义强调的是信息技术的现代化与高科技含量。信息技术对计划职能的支持；对组织职能和领导职能的支持；对控制职能的支持，在上可见，信息系统对管理具有重要的辅助和支持作用，现代管理要依靠信息系统来实现其管理职能，管理思想和管理方法。（5）为什么说管理信息系统并不能解决管理中的所有问题？答：管理是一种复杂的获得，它既涉及客观环境，又涉及人的主观因素。由于生产和社会环境的复杂性，也由于事物之间复杂的相互联系和事物的多变性，等等原因，人们在解决管理问题时不可能掌握所有的数据，更不能把所有的。待选择的解决方案都考虑进去，而管理信息系统解决问题时运行的程序是由人来编写的。管理信息系统是一个人机结合的系统，人不能解决的问题，依靠计算机也无法解决，

(完整版)Unit7TheMonster课文翻译综合教程四

Unit 7 The Monster Deems Taylor 1He was an undersized little man, with a head too big for his body ― a sickly little man. His nerves were bad. He had skin trouble. It was agony for him to wear anything next to his skin coarser than silk. And he had delusions of grandeur. 2He was a monster of conceit. Never for one minute did he look at the world or at people, except in relation to himself. He believed himself to be one of the greatest dramatists in the world, one of the greatest thinkers, and one of the greatest composers. To hear him talk, he was Shakespeare, and Beethoven, and Plato, rolled into one. He was one of the most exhausting conversationalists that ever lived. Sometimes he was brilliant; sometimes he was maddeningly tiresome. But whether he was being brilliant or dull, he had one sole topic of conversation: himself. What he thought and what he did. 3He had a mania for being in the right. The slightest hint of disagreement, from anyone, on the most trivial point, was enough to set him off on a harangue that might last for hours, in which he proved himself right in so many ways, and with such exhausting volubility, that in the end his hearer, stunned and deafened, would agree with him, for the sake of peace. 4It never occurred to him that he and his doing were not of the most intense and fascinating interest to anyone with whom he came in contact. He had theories about almost any subject under the sun, including vegetarianism, the drama, politics, and music; and in support of these theories he wrote pamphlets, letters, books ... thousands upon thousands of words, hundreds and hundreds of pages. He not only wrote these things, and published them ― usually at somebody else’s expense ― but he would sit and read them aloud, for hours, to his friends, and his family. 5He had the emotional stability of a six-year-old child. When he felt out of sorts, he would rave and stamp, or sink into suicidal gloom and talk darkly of going to the East to end his days as a Buddhist monk. Ten minutes later, when something pleased him he would rush out of doors and run around the garden, or jump up and down off the sofa, or stand on his head. He could be grief-stricken over the death of a pet dog, and could be callous and heartless to a degree that would have made a Roman emperor shudder. 6He was almost innocent of any sense of responsibility. He was convinced that

人教版高中语文必修一背诵篇目

高中语文必修一背诵篇目 1、《沁园春长沙》毛泽东独立寒秋，湘江北去，橘子洲头。看万山红遍，层林尽染；漫江碧透，百舸争流。鹰击长空，鱼翔浅底，万类霜天竞自由。怅寥廓，问苍茫大地，谁主沉浮？携来百侣曾游，忆往昔峥嵘岁月稠。恰同学少年，风华正茂；书生意气，挥斥方遒。指点江山，激扬文字，粪土当年万户侯。曾记否，到中流击水，浪遏飞舟？ 2、《诗两首》（1）、《雨巷》戴望舒撑着油纸伞，独自 /彷徨在悠长、悠长/又寂寥的雨巷，我希望逢着 /一个丁香一样的 /结着愁怨的姑娘。她是有 /丁香一样的颜色，/丁香一样的芬芳， /丁香一样的忧愁，在雨中哀怨， /哀怨又彷徨； /她彷徨在这寂寥的雨巷，撑着油纸伞 /像我一样， /像我一样地 /默默彳亍着冷漠、凄清，又惆怅。 /她静默地走近/走近，又投出太息一般的眼光，/她飘过 /像梦一般地， /像梦一般地凄婉迷茫。像梦中飘过 /一枝丁香的， /我身旁飘过这女郎；她静默地远了，远了，/到了颓圮的篱墙， /走尽这雨巷。在雨的哀曲里， /消了她的颜色， /散了她的芬芳， /消散了，甚至她的太息般的眼光， /丁香般的惆怅/撑着油纸伞，独自 /彷徨在悠长，悠长又寂寥的雨巷， /我希望飘过 /一个丁香一样的 /结着愁怨的姑娘。（2）、《再别康桥》徐志摩轻轻的我走了， /正如我轻轻的来； /我轻轻的招手， /作别西天的云彩。那河畔的金柳， /是夕阳中的新娘； /波光里的艳影， /在我的心头荡漾。软泥上的青荇， /油油的在水底招摇； /在康河的柔波里， /我甘心做一条水草！那榆阴下的一潭， /不是清泉，是天上虹 /揉碎在浮藻间， /沉淀着彩虹似的梦。寻梦？撑一支长篙， /向青草更青处漫溯， /满载一船星辉， /在星辉斑斓里放歌。但我不能放歌， /悄悄是别离的笙箫； /夏虫也为我沉默， / 沉默是今晚的康桥！悄悄的我走了， /正如我悄悄的来；/我挥一挥衣袖， /不带走一片云彩。 4、《荆轲刺秦王》太子及宾客知其事者，皆白衣冠以送之。至易水上，既祖，取道。高渐离击筑，荆轲和而歌，为变徵之声，士皆垂泪涕泣。又前而为歌曰：“风萧萧兮易水寒，壮士一去兮不复还！”复为慷慨羽声，士皆瞋目，发尽上指冠。于是荆轲遂就车而去，终已不顾。 5、《记念刘和珍君》鲁迅（1）、真的猛士，敢于直面惨淡的人生，敢于正视淋漓的鲜血。这是怎样的哀痛者和幸福者？然而造化又常常为庸人设计，以时间的流驶，来洗涤旧迹，仅使留下淡红的血色和微漠的悲哀。在这淡红的血色和微漠的悲哀中，又给人暂得偷生，维持着这似人非人的世界。我不知道这样的世界何时是一个尽头！

相关主题

人教版高中语文课文

外国文学名着赏析

themonster课文翻译

短歌行二首与赏析

物流信息管理1答案

农田水利学试题答案

相关文档

人教版高中语文必修必背课文

人教版高中语文必修一

人教版高中语文必修三教案全册

新版人教版高中语文课本的目录。

最新人教版高一语文必修一

人教版高中语文课文目录1

人教版高中语文必修一背诵篇目

人教版高中语文必修1-5全册教案

人教版高中语文必修三

人教版高中语文必修(1-5)必背课文

人教版高中语文必修必背课文

人教版高中语文必修必背课文精编WORD版

人教版高中语文课本诗文汇编(新版教材)

人教版高中语文必修一至必修五文言文电子课本

旧人教版高中语文教材目录-推荐下载

新课标人教版高中语文必修一至必修五背诵

人教版高中语文必修

人教版高中语文必修1-5教案

人教版高中语文必修二全套教案

人教版高一语文必修下册(2020版)电子课本课件【全册】

最新文档

幼儿园小班科学《小动物过冬》PPT课件教案

2021年春新青岛版(五四制)科学四年级下册 20.《露和霜》教学课件

自然教育课件

小学语文优质课火烧云教材分析及课件

(超详)高中语文知识点归纳汇总

高中语文基础知识点总结(5篇)

高中语文基础知识点总结(最新)

高中语文知识点整理总结

高中语文知识点归纳

高中语文基础知识点总结大全

超详细的高中语文知识点归纳

高考语文知识点总结高中

高中语文知识点总结归纳

高中语文知识点整理总结

高中语文知识点归纳

高中语文知识点归纳(大全)

高中语文知识点总结归纳(汇总8篇)

高中语文基础知识点整理

化工厂应急预案

化工消防应急预案(精选8篇)

Computational Approaches to Temporal Sampling of Video Sequences · 25

物流信息管理 习题答案

最新The_Monster课文翻译

新版人教版高中语文课本的目录。

初中语文古文赏析曹操《短歌行》赏析(林庚)

物流管理信息系统习题答案

高中语文文言文曹操《短歌行(对酒当歌)》原文、翻译、赏析

电子商务物流管理__试卷一及参考答案

高中外研社英语选修六Module5课文Frankenstein's Monster

人教版高中语文必修必背课文精编WORD版

曹操《短歌行》其二翻译及赏析

管理信息系统第一章习题答案

(完整版)Unit7TheMonster课文翻译综合教程四

人教版高中语文必修一背诵篇目

相关文档

最新文档

物流信息管理习题答案