{'fraction_non_alphanumeric': 0.03731191885038039, 'fraction_numerical': 0.012054099746407438, 'mean_word_length': 4.6941663457835965, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Video Primal Sketch: A Unified Middle-Level Representation for Video

This paper presents a middle-level video representation named Video Primal Sketch (VPS), which integrates two regimes of models: i) sparse coding model using static or moving primitives to explicitly represent moving corners, lines, feature points, etc., ii) FRAME /MRF model reproducing feature statistics extracted from input video to implicitly represent textured motion, such as water and fire. The feature statistics include histograms of spatio-temporal filters and velocity distributions. This paper makes three contributions to the literature: i) Learning a dictionary of video primitives using parametric generative models; ii) Proposing the Spatio-Temporal FRAME (ST-FRAME) and Motion-Appearance FRAME (MA-FRAME) models for modeling and synthesizing textured motion; and iii) Developing a parsimonious hybrid model for generic video representation. Given an input video, VPS selects the proper models automatically for different motion patterns and is compatible with high-level action representations. In the experiments, we synthesize a number of textured motion; reconstruct real videos using the VPS; report a series of human perception experiments to verify the quality of reconstructed videos; demonstrate how the VPS changes over the scale transition in videos; and present the close connection between VPS and high-level action models.


Motivation
Videos of natural scenes contain vast varieties of motion patterns. We divide these motion patterns in a 2 × 2 table based on their complexities measured by two criteria: i) sketchability (Guo et al (2007)), i.e. whether a local patch can be represented explicitly by an image primitive from a sparse coding dictionary, and ii) intrackability (or trackability) (Gong and Zhu (2012)), which measures the uncertainty of tracking an image patch using the entropy of posterior probability on velocities. Fig.1 shows some examples of the different video patches in the four categories. Category A consists of the simplest vision phenomena, i.e. sketch-able and trackable motions, such as trackable corners, lines, and feature points, whose positions and shapes can be tracked between frames. For example, patches (a), (b), (c) and (d) belong to category A. Category D is the most complex and is called textured motions or dynamic texture in the literature, such as water, fire or grass, in which the images have no distinct primitives or trackable motion, such as patches (h) and (i). The other categories are in between. Category B refers to sketchable but intrackable patches, which can be described by distinct image primitives but hardly be tracked between frames due to fast motion, for example the patches (e) and (f) at the legs of the galloping horse. Finally category C includes the trackable but non-sketchable patches, which are cluttered features or moving kernels, e.g. patch (g).
In the vision literature, as it was pointed out by (Shi and Zhu (2007)), there are two families of representations, which code images or videos by explicit and implicit functions respectively.
1, Explicit representations with generative models. (Olshausen (2003); Kim et al (2010)) learned an overcomplete set of coding elements from natural video sequences using the sparse coding model (Olshausen and Field (1996)). (Elder and Zucker (1998)) and (Guo et al (2007)) represented the image/video patches by fitting functions with explicit geometric and photometric parameters. (Wang and Zhu (2004)) synthesized complex motion, such as birds, snowflakes, and waves with a large mount of particles and wave components. (Black and Fleet (2000)) represented two types of motion primitives, namely smooth motion and motion boundaries for motion segmentation. In higher level object motion tracking, people represented different tracking units depending on the underlying objects and scales, such as sparse or dense feature points tracking (Serby et al (2004), Black and Fleet (2000)), kernels tracking (Comaniciu et al (2003); Fan et al (2006)), contours tracking (Maccormick and Blake (2000)), and middle-level pairwise-components generation (Yuan et al (2010)).
2, Implicit representations with descriptive models. For textured motions or dynamic textures, people used numerous Markov models which are constrained to reproduce some statistics extracted from the input video. For example, dynamic textures (Szummer and Picard (1996); Campbell et al (2002)) were modeled by a spatiotemporal auto-regressive (STAR) model, in which the intensity of each pixel was represented by a linear summation of intensities of its spatial and temporal neighbors. (Bouthemy et al (2006)) proposed a mixed-state auto-models for motion textures by generalizing the auto-models in (Besag (1974)). (Doretto et al (2003)) derived an auto-regression moving-average model for dynamic texture. (Chan and Vasconcelos (2008)) and ) extended it to a stable linear dynamical system (LDS) model.
Recently, to represent complex motion, such as human activities, researchers have used Histogram of Oriented Gradients (HOG) (Dalal and Triggs (2005)) for appearance and Histogram of Oriented Optical-Flow (HOOF) (Dalal et al (2006); Chaudhry et al (2009)) for motion. The HOG and HOOF record the rough geometric information through the grids and pool the statistics (histograms) within the local cells. Such features are used for recognition in discriminative tasks, such as action classification, and are not suitable for video coding and reconstruction.
In the literature, these video representations are often manually selected for specific videos in different tasks. There lacks a generic representation and criterion that can automatically select the proper models for different patterns of the video. Furthermore, as it was demonstrated in (Gong and Zhu (2012)) that both sketchability and trackability change over scales, densities, and stochasticity of the dynamics, a good video representation must adapt itself continuously in a long video sequence.

Overview and contributions
Motivated by the above observations, we study a unified middle-level representation, called video primal sketch (VPS), by integrating the two families of representations. Our work is inspired by Marr's conjecture for a generic "token" representation called primal sketch as the output of early vision (Marr (1982)), and is aimed at extending the primal sketch model proposed by (Guo et al (2007)) from images to videos. Our goal is not only to provide a parsimonious model for video compression and coding, but more importantly, to support and be compatible with high-level tasks such as motion tracking and action recognition. Fig.2 overviews an example of the video primal sketch. Fig.2.(a) is an input video frame which is separated into sketchable and non-sketchable regions by the sketchability map in (b), and trackable primitives and intrackable regions by the trackability map in (c). The sketchable or trackable regions are explicitly represented by a sparse coding model and reconstructed in (d) with motion primitives, and each non-sketchable and intrackable region has a textured motion which is synthesized in (e) by a generalized FRAME (Zhu et al (1998)) model (implicit and descriptive). The synthesis of this frame is shown in (f) which integrates the results from (d) and (e) seamlessly. (e) Synthesis for implicit regions (textured motions) by sampling the generalize FRAME model through Markov chain Monte Carlo using the explicit regions as boundary condition.
(f) Synthesized frame by combining the explicit and implicit representations.
As Table 1 shows, the explicit representations include 3, 600 parameters for the positions, types, motion velocities, etc of the video primitives and the implicit representations have 420 parameters for the histograms of a set of filter responses on dynamic textures. This table shows the efficiency of the VPS model. This paper makes the following contributions to the literature.
1. We present and compare two different but related models to define textured motions. The first one is a spatio-temporal FRAME (ST-FRAME) model, which is a non-parametric Markov random field and generalizes the FRAME model (Zhu et al (1998)) of texture with spatio-temporal filters. The ST-FRAME model is learned so that it has marginal probabilities that match the histograms of the responses from the spatio-temporal filters on the input video. The second one is a motion-appearance FRAME model (MA-FRAME), which not only matches the histograms of some spatio-temporal filter responses, but also matches the histograms of velocities pooled over a local region. The MA-FRAME model achieves better results in video synthesis than the ST-FRAME model, and it is, to some extent, similar to the HOOF features used in action classification (Dalal et al (2006); Chaudhry et al (2009)). 2. We learn a dictionary of motion primitives from input videos using a generative sparse coding model. These primitives are used to reconstruct the explicit regions and include two types: i) generic primitives for the sketchable patches, such as corners, bars etc; and ii) specific primitives for the non-sketchable but trackable patches which are usually texture patches similar to those used in kernel tracking (Comaniciu et al (2003)). 3. The models for implicit and explicit regions are integrated in a hybrid representation -the video primal sketch (VPS), as a generic middle-level representation of video. We will also show how VPS changes over information scales affected by distance, density and dynamics. 4. We show the connections between this middle-level VPS representation and features for high-level vision tasks such as action recognition.
Our work is inspired by Gong's empirical study in Gong and Zhu (2012), which revealed the statistical properties of videos over scale transitions and defined intrackability as the entropy of local velocities. When the entropy is high, the patch cannot be tracked locally and thus its motion is represented by a velocity histogram. Gong and Zhu (2012) did not give a unified model for video representation and synthesis which is the focus on the current paper.
This paper extends a previous conference paper (Han et al (2011)) in the following aspects: 1. We propose a new dynamic texture model, MA-FRAME, for better representing velocity information. Benefited from the new temporal feature, the VPS model can be applied to high-level action representation tasks more directly. 2. We compare spatial and temporal features with HOG (Dalal and Triggs (2005)) and HOOF (Dalal et al (2006)) and discuss the connections between them. 3. We do a series of perceptual experiments to verify the high quality of video synthesis from the aspect of human perception.
The remainder of this paper is organized as follows. In Section 2, we present the framework of video primal sketch. In Section 3, we explain the algorithms for explicit representation, textured motion synthesis and video synthesis, and show a series of experiments. The paper is concluded with a discussion in Section 4.

Video primal sketch model
In his monumental book (Marr (1982)), Marr conjectured a primal sketch as the output of early vision that transfers the continuous "analogy" signals in pixels to a discrete "token" representation. The latter should be parsimonious and sufficient to reconstruct the observed image without much perceivable distortions. A mathematical model was later studied by Guo, et al (Guo et al (2007)), which successfully modeled hundreds of images by integrating sketchable structures and non-sketchable textures. In this section, we extend it to video primal sketch as a hybrid generic video representation.
Let I[1, m] = {I (t) } m t=1 be a video defined on a 3D lattice Λ ⊂ Z 3 . Λ is divided disjointly into explicit and implicit regions, Then the video I is decomposed as two components I Λex are defined by explicit functions I = g(w), in which, each instance is corresponded to a different function form of g() and indexed by a particular value of parameter w. And I Λim are defined by implicit functions H(I) = h, in which, H() extracts the statistics of filter responses from image I and h is a specific value of histograms. In the following, we first present the two families of models for I Λex and I Λim respectively, and then integrate them in the VPS model.

Sketchable Region
Trackable Region Fig. 3 Comparison between sketchable and trackable regions.

Explicit representation by sparse coding
The explicit region Λ ex of a video I is decomposed into n ex disjoint domains (usually n ex is in the order of 10 2 ), Here Λ ex,i ⊂ Λ defines the domain of a "brick". A brick, denoted by I Λex,i , is a spatio-temporal volume like a patch in images. These bricks are divided into the three categories A, B and C as we mentioned in section 1. The size of Λ ex,i influences the results of tracking and synthesis to some degree. The spatial size should depend on the scale of structures or the granularity of textures, and the temporal size should depend on the motion amplitude and frequency in time dimension, which are hard to estimate in real applications. However, a general size works well for most of cases, say 11 × 11 pixels× 3 frames for trackable bricks (sketchable or non-sketchable), or 11 × 11 pixels×1 frame for sketchable but intrackable bricks. Therefore, in all the experiments of this paper, the size of Λ ex,i is chosen as such. Fig.3 shows one example comparing the sketchable and trackable regions based on sketchability and trackability maps shown in Fig.2(b) and (c) respectively. It is worth noting that the two regions overlaps with only a small percentage of the regions is either sketchable or trackable.
Each brick can be represented by a primitive B i ∈ ∆ B through an explicit function, B i means the ith primitive from the primitive dictionary ∆ B , which fits the brick I Λex,i best. Here i indexes the parameters such as type, position, orientation and scale of B i . α i is the corresponding coefficient. represents the residue, which is assumed to be i.i.d. Gaussian.
For an trackable primitive, B i (x, y, t) includes 3 frames and thus encodes the velocity (u, v) in the 3 frames. For sketchable but intrackable primitive, B i (x, y, t) has only 1 frame. As Fig. 4 illustrates, the dictionary ∆ B is composed of two categories: -Common primitives ∆ common B . These are primitives shared by most videos, such as blobs, edges and ridges etc. They have explicit parameters for orientations and scales. They are mostly belong to sketchable region as shown in Fig. 3.
-Special primitives ∆ special B . These bricks do not have common appearance and are limited to specific video frames. They are non-sketchable but trackable, and are recorded to code the specific video region. They are mostly belong to trackable region but not included in sketchable region as shown in Fig. 3.
To be noted, the primitives and categories shown in Fig. 4 are some selected examples, but not the whole dictionary. The details for learning these primitives are introduced in section 3.2.
(4) uses only one base function and thus is different from conventional linear additive model. Follows the Gaussian assumption for the residues, we have the following probabilistic model for the explicit region I Λex where B = (B 1 , ..., B nex ) represents the selected primitive set, n is the size of each primitive, n ex is the number of selected primitives and σ i is estimated standard deviation of representing natural videos by B i .

Implicit representations by FRAME models
The implicit region Λ im of video I is segmented into n im (usually n im is no more than 10) disjoint homogeneous textured motion regions, One effective approach for texture modeling is to pool the histograms for a set of filters (Gabor, DoG and DooG) on the input image (Bergen and Adelson (1991); Chubb and Landy (1991); Heeger and Bergen (1995);Zhu et al (1998); Portilla and Simoncelli (2000)). Since Gabor filters model the response functions of the neurons in the primary visual cortex, two texture images with the same histograms of filter responses generate the same texture impression, and thus are considered perceptually equivalent (Silverman et al (1989)). The FRAME model proposed in (Zhu et al (1998)) generates the expected marginal statistics to match the observed histograms through the maximum entropy principle. As a result, any images drawn from this model will have the same filtered histograms and thus can be used for synthesis or reconstruction.
We extend this concept to video by adding temporal constraints and define each homogeneous textured motion region I Λim,j by an equivalence class of videos, where h j = (h 1,j , ..., h K,j ) is a series of 1D histograms of filtered responses that characterize the macroscopic properties of the textured motion pattern. Thus we only need to code the histograms h j and synthesize the textured motion region I Λim,j by sampling from the set Ω K (h j ). As I Λim,j is defined by the implicit functions, we call it an implicit representation. These regions are coded up to an equivalence class in contrast to reconstructing the pixel intensities in the explicit representation.
To capture temporal constraints, one straightforward method is to choose a set of spatio-temporal filters and calculate the histograms of the filter responses. This leads to the spatio-temporal FRAME (ST-FRAME) model which will be introduced in section 2.3. Another method is to compute the statistics of velocity. Since the motion in these regions is intrackable, at each point of the image, its velocity is ambiguous (large entropy). We pool the histograms of velocities locally in a way similar to the HOOF (Histogram of Oriented Optical-Flow) (Dalal et al (2006); Chaudhry et al (2009)) features in action classification. This leads to the motionappearance FRAME (MA-FRAME) model which uses histograms of both appearance (static filters) and velocities. We will elaborate on this model in section 2.4.

Implicit representation by spatio-temporal FRAME
ST-FRAME is an extension of the FRAME model (Zhu et al (1998)) by adopting spatio-temporal filters. A set of filters F is selected from a filter bank ∆ F . Fig.5 illustrates the three types of filters in ∆ F : i) the static filters for texture appearance in a single image; ii) the motion filter with certain velocity; and iii) the flicker filter that have zero velocity but opposite signs between adjacent frames. For each filter F k ∈ F, the spatio-temporal filter response of I at (x, y, t) ∈ Λ im,j is F k * I(x, y, t). The convolution is over spatial and temporal domain. By pooling the filter responses over all (x, y, t) ∈ Λ im,j , we obtain a number of 1D histograms where z indexes the histogram bins, and δ(z; x) = 1 if x belongs to bin z, and δ(z; x) = 0 otherwise. Following the FRAME model, the statistical model of textured motion I Λim,j is written in the form of the following Gibbs distribution, where β k = (β k,1 , β k,2 , ...β k,3 ) are potential functions.
According to the theorem of ensemble equivalence (Wu et al (2000)), the Gibbs distribution converges to the uniform distribution over the set Ω K (h j ) in (7), when Λ im,j is large enough. For any fixed local brick Λ 0 ⊂ Λ im,j , the distribution of I Λ0 follows the Markov random field model (9). The model can describe textured motion located in an irregular shape region Λ im,j .
The filters in F are pursued one by one from the filter bank ∆ F so that the information gain is maximized at each step.
H 0 k and H syn k are the response histograms of F k before and after synthesizing I Λim,j by adding F k respectively. The larger the difference, the more important is the filter.
Following the distribution form of (9), the probabilistic model of implicit parts of I is defined as where F = (F 1 , ..., F K ) represents the selected spatiotemporal filter set.
In the experiments described later, we demonstrate that this model can synthesize a range of dynamic textures by matching the histograms of filter responses. The synthesis is done through sampling the probability by Markov chain Monte Carlo.

Implicit representation by motion-appearance FRAME
Different from ST-FRAME, in which, temporal constraints are based on spatio-temporal filters, the MA-FRAME model uses the statistics of velocities, in addition to the statistics of filter responses for appearance.
For the appearance constraints, the filter response histograms H (s) are obtained similarly as ST-FRAME in (10) where the filter set F includes static and flicker filters in ∆ F .
For the motion constraints, the velocity distribution of each local patch is estimated via the calculation of trackability (Gong and Zhu (2012)), in which, each patch is compared with its spatial neighborhood in adjacent frame and the probability of the local velocity v is computed as Here, σ is the standard deviation of the differences between local patches from adjacent frames based on various velocities. The statistical information of velocities for a certain area of texture is approximated by averaging the velocity distribution over region Λ im,j = (x,y,t)∈Λim,j p(v|I(x, y, t − 1), I(x, y, t)).
) collect the filter responses and velocities histograms of the video. The statistical model of textured motion I Λim,j can be written in the form of the following joint Gibbs distribution, Here, β is the parameter of the model. In summary, the probabilistic model for the implicit regions of I is defined as where F = (F 1 , ..., F K ) represents the selected filter set.
In the experiment section, we show the effectiveness of the MA-FRAME model and its advantages over the ST-FRAME model.

Hybrid model for video representation
The ST or MA-FRAME models for the implicit regions I Λim use the explicit regions I Λex as boundary conditions, and the probabilistic models for I Λex and I Λim are given by (5) and (11) respectively Here, I ∂Λim represents the boundary condition of I Λim , which belong to the reconstruction of I Λex . It leads to seamless boundaries in the synthesis.
By integrating the explicit and implicit representation, the video primal sketch has the following probability model, where Z is the normalizing constant.
We denote by V P S = (B, H) the representation for the video I Λ , where H = ({h k,1 } K1 k=1 , ..., {h k,nim } Kn im k=1 ) includes the histograms described by F and V; and B includes all the primitives with parameters for their indexes, position, orientation and scales etc. p(V P S) = p(B, H) = p(B)p(H) gives the prior probability of video representation by V P S. p(B) ∝ exp{−|B|}, in which, |B| is the number of primitives. p(H) ∝ exp{−γ tex (H)}, in which, γ tex (H) is the energy term and for instance, γ tex (H) = ρn im to penalize the number of implicit regions. Thus, the best video representation V P S * is obtained by maximizing the posterior probability, following the video primal sketch model in (18). Table 1 shows an example of V P S. For a video of the size of 288 × 352 pixels, about 30% of the pixels are represented explicitly by n ex = 300 motion primitives. As each primitive needs 11 parameters (the side length of the patch according to the primitive learning process in section 3.2) to record the profile and 1 more to record the type, the number of total parameters for the explicit representation is 3,600. n im = 3 textured motion regions are represented implicitly by the histograms, which are described by K 1 = 11, K 2 = 12 and K 3 = 5 filters respectively. As each histogram has 15 bins, the number of the parameters for the implicit representation is 420.

Sketchability and Trackability for Model Selection
The computation of the VPS involves the partition of the domain Λ into the explicit regions Λ ex and implicit regions Λ im . This is done through the sketchability and trackability maps. In this subsection, we overview the general ideas and refer to previous work on sketchability (Guo et al (2007)) and trackability (Gong and Zhu (2012)) for details.
Let's consider one local volume Λ 0 ⊂ Λ of the video I. In the video primal sketch model, I Λ0 may be modeled either by the sparse coding model in (5) or by the FRAME model in (11). The choice is determined via the competition between the two models, i.e. comparing which model gives shorter coding length (Shi and Zhu (2007)) for representation.
If I Λ0 is represented by the sparse coding model, the posterior probability is calculated by where n = |Λ 0 |. The coding length is Since σ 2 is estimated via the given data temporarily in real application, 1 n i I Λ0 − α i B i 2 = σ 2 holds by definition. As a result, the coding length is derived as, If I Λ0 is described by the FRAME model, the posterior probability is calculated by The coding length is estimated through a sequential reduction process. When K = 0, with no constraints, the FRAME model is a uniform distribution, and thus the coding length is log |Ω 0 | where |Ω 0 | is the cardinality of the space of all videos in Λ. Suppose the intensities of the video range from 0 to 255, then log |Ω 0 | = 8 × |Λ 0 |. By adding each constraint, the equivalence Ω(K) will shrink in size, and the ratio of the compression log |Ω K−1 | |Ω K | is approximately equal to the information gain in (10). Therefore we can calculate the coding length by By comparing L im (I Λ0 ) and L ex (I Λ0 ), whoever has the shorter coding length will win the competition and be chosen for I Λ0 .
In practice, we use a faster estimation which utilizes the relationship between the coding length and the entropy of the local posterior probabilities.
Consider the entropy of p(B|I Λ0 ), It measures the uncertainty of selecting a primitive in ∆ B for representation. The sharper the distribution p(B|I Λ0 ) is, the lower the entropy H(B k |I Λ0 ) will be, which gives smaller L ex (I Λ0 ) according to (21). Hence, is lower and I Λ0 is modeled by the sparse coding model, else it is modeled by the FRAME model. It is clear that H(B k |I Λ0 ) has the same form and meaning with sketchability (Guo et al (2007)) in appearance representation and trackability (Gong and Zhu (2012)) in motion representation. Therefore, sketchability and trackability can be used for model selection for each local volume. Fig.2 (b) and (c) show the sketchability and trackability maps calculated by the local enetropy of posteriors. The two maps decide the partition of the video into the explicit implicit regions. Within the explicitly regions, they also decide whether a patch is trackable (using primitives with size of 11 × 11 pixels ×3 frames) or intrackable (using primitives with 11×11 pixels ×1 frame).

Spatio-temporal filters
In the vision literature, spatio-temporal filters have been widely used for motion information extraction (Adelson and Bergen (1985)), optical flow estimation (Heeger (1987)), multi-scale representation of temporal data (Lindeberg and Fagerstrm (1996)), pattern categorization (Wildes and Bergen (2000)), and dynamic texture recognition (Derpanis and Wildes (2010)). In the experiments, we choose spatio-temporal filters ∆ F as shown in Fig.5. It includes three types: 1 Static filters. Laplacian of Gaussian (LoG), Gabor, gradient, or intensity filter on a single frame. They capture statistics of spatial features. 2 Motion filters. Moving LoG, Gabor or intensity filters in different speeds and directions over three frames. Gabor motion filters move perpendicularly to their orientations. 3 Flicker filters. One static filter with opposite signs at two frames. They contrast the static filter responses between two consequent frames and detect the change of dynamics.
For implicit representation, the filters are 7 × 7 pixels in size and have 6 scales, 12 directions and 3 speeds. Each type of filter has a special effect in textured motion synthesis, which will be discussed in section 3.3 and shown in Fig.8.

Learning motion primitives and reconstructing explicit regions
After computing the sketchability and trackability maps of one frame, we extract explicit regions in the video. By calculating all the coefficients of each part with motion primitives from the primitive bank, α i,j = I Λtr,i , B j , all the α i,j are ranked from high to low. Each time, we select the primitive with the highest coefficient to represent the corresponding domain and then do local suppression to its neighborhood to avoid excessive overlapping of extracted domains. The algorithm is similar to matching pursuit (Mallat and Zhang (1993)) and the primitives are chosen one by one.
In our work, in order to alleviate computational complexity, α i,j are calculated by filter responses. The filters used here are 11 × 11 pixels and have 18 orientations and 8 scales. The fitted filter F j gives a raw sketch of the trackable patch and extracts property information, such as type and orientation, for generating the primitive. If the fitted filter is a Gabor-like filter, the primitive B j is calculated by averaging the intensities of the patch along the orientation of F j , while if the fitted filter is a LoG-like filter, B j is calculated by averaging the intensities circularly around its center. Then B j is added to the primitive set B with its motion velocities calculated from the trackability map. It is also added into ∆ B for the dictionary buildup. The size of each primitive is 11 × 11, the same as the size of the fitted filter. And the velocity (u, v) are two parameters for recording motion information. In Fig.4, we show some examples of different types of primitives, such as blob, ridge and edge. Fig.6 shows some examples of reconstruction by motion primitives. In each group, the original local image, the fitted filter, the generated primitive and the motion velocity are given. In the frame, each patch is marked by a square with a short line for representing its motion information.
Through the matching pursuit process, the sketchable regions are reconstructed by a set of common primitives. Fig.7 shows an example of the sketchable region reconstruction by using a series of common primitives. By comparing the observed frame (a) and reconstructed frame (b), (c) shows the error of reconstruction. The more detailed quantitative assessment is given in section 3.7. It is evident that a rich dictionary of video primitives can lead to a satisfactory reconstruction of explicit regions of videos.
For non-sketchable but trackable regions, based on the trackability map, we get the motion trace of each local trackable patch. Because each patch cannot be represented by a shared primitive, we record the whole patch and motion information as a special primitive for video reconstruction. It is obvious that special primitives increase model complexity compared with common primitives. However, as stated in section 2.1, the percentage of special primitives for the explicit region reconstruction of one video is very small (around 2-3%), hence it will not affect the final storage space significantly.

Synthesizing textured motions by ST-FRAME
Each local volume I Λ0 of textured motion located at Λ 0 follows a Markov random field model conditioned on its local neighborhood I ∂Λ0 following (9), where Lagrange parameters β k = {β ∈ β are the discrete form of potential function β k () learned from input videos by maximum likelihood, But the closed form of β is not available in general. So it can be solved iteratively by In order to draw a typical sample frame from p(I; F, β), we use the Gibbs sampler which simulates a Markov chain. Starting from any random image, e.g. a white noise, it converges to a stationary process with distribution p(I; F, β). Therefore, we get the final converged results dominated by p(I; β, F), which characterizes the observed dynamic texture.
Initialize I syn (m) as a uniform white noise image.
| ≤ for k = 1, 2, ..., K. Fig.8 shows an example of the synthesis process. (f) is one frame from textured motion of ocean. Starting from a white noise frame in (a), (b) is synthesized with only 7 static filters. It shows high smoothness in spatial domain, but lacks temporal continuity with previous frames. However, in (c) the synthesis with only 9 motion filters has similar macroscopic distribution to the observed frame, but appears quite grainy over local spatial relationship. By using both static and motion filters, the synthesis in (d) performs well on both spatial and temporal relationships. Compared with (d), the synthesis by 2 extra flicker filters in (e), shows more smoothness and more similar to the observed frame.
In Fig.9, we show four groups of textured motion (4 bits) synthesis by Algorithm 1: ocean (a), water wave (b), fire (c) and forest (d). In each group, as time passes, the synthesized frames are getting more and more different from the observed one. It is caused by the stochasticity of textured motions. Although the synthesized and observed videos are quite different on pixel level, the two sequences are perceived extremely identical by human after matching the histograms of a small set of filter responses. This conclusion can be further supported by perceptual studies in section 3.9. Fig.10 shows that as I syn (m) changes from white noise ( Fig.8(a)) to the final synthesized result (Fig.8(e)), the histograms of filter responses become matched with the observed ones. Table 2 shows the comparison of compression ratios between ST-FRAME and the dynamic texture model (Doretto et al (2003)). It has a significantly better compression ratio than the dynamic texture model, because  Table 2 The number of parameters recorded and the compression ratios for synthesis of 5-frame textured motion videos by ST-FRAME and the dynamic texture model (Doretto et al (2003) the dynamic texture model has to record PCA components as large as the image size.

Computing velocity statistics
One popular method for velocity estimation is optical flow. Based on the optical flow, HOOF features extract the motion statistics by calculating the distribution of velocities in each region. Optical flow is an effective method for estimating the motions at trackable areas, but does not work for the intrackable dynamic texture areas. The three basic assumptions for optical flow equations, i.e. brightness constancy between matched pixels in consecutive frames, smoothness among adjacent pixels and slow motion, are violated in these areas due to the stochastic nature of dynamic textures. Therefore, we go for a different velocity estimation method. Considering one pixel I(x, y, t) at (x, y) in frame t, we denote its neighborhood as I ∂Λx,y,t . Comparing patch I ∂Λx,y,t with all the patches in the previous frame within a searching radius, each patch corresponding to one velocity v = (v x , v y ), we obtain a distribution This distribution describes the probability of the origin of the patch, i.e. the location where the patch I ∂Λx,y,t moves from. Equivalently, it reflects the average probability of the motions of the pixels in the patch. Therefore, by clustering all the pixels according to their velocity distribution, the cluster center of each cluster gives the velocity statistics of all the pixels in this cluster approximately, which reflects the motion pattern of these clustered pixels. Fig.14 and Fig.15 show some examples of velocity statistics, in which the brighter, the higher probability while the darker, the lower probability. The meanings of these two figures are explained later. Compared to HOOF, the estimated velocity distribution is more suitable for modeling textured motion. Firstly, the velocity distribution is estimated pixelwisely. Hence it can depict more non-smooth motions. Secondly, although it seeks to compare the intensity pattern around a point to nearby regions at a subsequent temporal instance, which seems to also take brightness constancy assumption into account, the difference here is that it calculates the probability of motions rather than the single pixel correspondence. As a result, the constraints by the assumption is weakened, and it has the ability to represent stochastic dynamics.

Synthesizing textured motions by MA-FRAME
In MA-FRAME model, similar to ST-FRAME, each local volume I Λ0 of textured motion follows a Markov random field model. However, the difference is that MA-FRAME extracts motion information via the distribution of velocities v.
In the sampling process, I Λim,j and v Λim,j are sampled simultaneously following the joint distribution in (15), In experiments, we design an effective way for sampling from the above model. For each pixel, we build a 2D-distribution matrix, whose two dimensions are velocities and intensities respectively, to guide the sampling process. The sampling probability for every candidate (labeled by one velocity and one intensity) is obtained by integrating motion score, appearance score and multiplying smoothness weight, The details are explained with the illustration by Fig.11 for the sampling method at one pixel. For each pixel (x, y) of the current frame I t , we consider its every pos- Each velocity corresponds to a position (x−v x,i , y −v y,j ) in the previous frame I t−1 . Under velocity v i,j , the perturbation range of I t−1 (x−v x,i , y − v y,j ) yields the intensity candidates for I t (x, y) which is a smaller interval than [0, 255] and thus saves computational complexity. In the shown example ( Fig.11(a)), v max = 1 and the perturbed intensity range is Therefore we have 9 velocity candidates and 2m + 1 intensity candidates for each velocity, hence the size of the sampling matrix is 9 × (2m + 1) (Fig.11(b)). With the motion constraints given by matching the velocity statistics, the velocity candidates have their motion scores. With the appearance constraints given by matching the filter response histograms, intensity candidates have  their appearance scores. By integrating the two sets of scores, we obtain a preliminary sampling matrix shown in Fig.11(b). In order to guarantee the motion of each pixel is as consistent as possible with its neighborhoods to make the macroscopic motion smooth enough, we add a set of weights on the distribution matrix, in which each multiplier for candidates of one velocity is calculated by The weights encourage the velocity candidate which is closer to the velocities of its neighbours. With the weights, the sampled velocities are prone to be regarded as "blurred" optical flow. The main difference is that it preserves the uncertainty of dynamics in a texture motion, but not definite velocities of every local pixel. After multiplying the weights to the preliminary matrix, we get the final sampling matrix. Although the  main purpose of MA-FRAME is sampling intensities of each pixel from a textured motion, the sampling for intensities is highly related to velocities, and the sampling process is actually based on the joint distribution of velocity and intensity.
In summary, textured motion synthesis by MA-FRAME is given as follows

Repeat
Calculate {h syn(s) k , k = 1, 2, ..., K s } and {h syn(v) k , k = 1, 2, ..., K v } from I syn . Update β k , k = 1, ..., K and p(I; F, β). Sample (I syn (m) , V syn (m) ) ∼ p(I, V; F, β) by Gibbs sampler. Fig.12 and Fig.13 show two examples of textured motion synthesis by MA-FRAME. Different from the synthesis results by ST-FRAME, it can deal with videos of larger size, higher intensity level (8 bits here compared to 4 bits in ST-FRAME experiments) and more frames because of its smaller sample space and higher temporal continuity. Furthermore, it generates better motion pattern representations. Fig.14 shows the comparison of velocities statistics between the original video and the synthesized video of different textured motion clusters, the brighter, the higher motion probability while the darker, the lower probability. It is easy to tell that they are quite consis- Fig. 14 Five pairs of global statistics of velocities for comparison. Each patch corresponds to the neighborhood lattices as shown in Fig.11(a). The brighter means higher motion probability while the darker means lower probability. Fig. 15 Ten pairs of local statistics of velocities for comparison. Upper row: original; lower row: synthesis. Each patch corresponds to the neighborhood lattices as shown in Fig.11(a). The brighter means higher motion probability while the darker means lower probability. tent, which means the original and synthesized videos have similar macroscopical motion properties.
We also test local motion consistency between observed and synthesized videos by comparing velocity distributions of every pair of corresponding pixels. Fig.15 shows the comparisons of ten pairs of randomly chosen pixels. Most of them match well. It demonstrated that the motion distributions of most of local patches also preserve well during the synthesis procedure.

Dealing with occlusion parts in texture synthesis
Before providing the full version of computational algorithm for VPS, we first introduce how to deal with occluded areas.
In video, dynamic background textures are often occluded by the movement of foreground objects. Synthesizing background texture by ST-FRAME uses histograms of spatio-temporal filter responses. When a textured region becomes occluded, the pattern no longer belongs to the same equivalence class. In this event, the spatio-temporal responses are not precise enough for matching the given histograms, and may cause a deviation in the synthesis results. These errors may ac-cumulate over frames and the synthesis will ultimately degenerate completely. Synthesis by MA-FRAME has a greater problem because the intensities in the current frame are selected from small perturbations in intensities from the previous frame. If a pixel cannot be found from the neighborhood in the previous frame that belongs to the same texture class, the intensity it adopts may be incompatible with other pixels around it.
In order to solve this problem, occluded pixels are sampled separately by the original (spatial) FRAME model, which means, we have two classes of filter response histograms 1 Static filter response histograms H S . Histograms are calculated by summarizing static filter responses of all the textural pixels; 2 Spatio-temporal filter response histograms H ST . Histograms are calculated by summarizing spatio-temporal filter responses of all the non-occluded textured pixels.
Therefore, in the sampling process, the occluded pixels and non-occluded pixels are treated differently. First, their statistics are constrained by different sets of filters; second, in MA-FRAME, the intensities of nonocclude pixels are sampled from the intensity perturbation of their neighborhood locations in previous frame, while the intensities of occluded pixels are sampled from the whole intensity space, say 0-255 for 8 bits grey levels.

Synthesizing videos with VPS
In summary, the full version of the computational algorithm for video synthesis of VPS is presented as follows.
Algorithm 3. Video Synthesis via Video Primal Sketch Input a video I obs = {I obs (1) , ..., I obs (m) }. Compute sketchability and trackability for separating I obs into explicit region I Λex and implicit region I Λim . for t=1:m Reconstruct I obs (t)Λex by the sparse coding model with the selected primitives B chosen from the dictionary ∆ B to get I syn (t)Λex . For each region of homogeneous textured motion Λ im,j , using I syn (t)Λex as boundary condition, synthesize I obs (t)Λim,j by ST-FRAME model or MA-FRAME with the selected filter set F chosen from the filter bank ∆ F to get I syn (t)Λim . The synthesis of the ith frame of the video I syn (t) is given by aligning I syn (t)Λex and I syn (t)Λim together seamlessly.

end for
Output the synthesized video I syn . Fig.2 shows this process as we introduced in section 1. Fig.16 shows three examples of video synthesis (YCbCr color space, 8 bits for grey level) by VPS frame by frame. In every experiment, observed frames, trackability maps, and final synthesized frames are shown. In Table 3, H.264 is selected as the reference of compression ratio compared with VPS, from which we can tell VPS is competitive with state-of-art video encoder on video compression.
For assessing the quality of the synthesized results quantitatively, we adopt two criteria for different representations, rather than the traditional approach based on error-sensitivity as it has a number of limitations ). The error for explicit representations is measured by the difference of pixel intensities while for implicit representations, the error is given by the difference of filter response histograms, Table 4 shows the quality assessments of the synthesis, which demonstrates good performance of VPS on synthesizing videos.

Computational Complexity Analysis
In this subsection, we analyze the computational complexity of the algorithms studies in this paper. We discuss the complexity for four algorithms in the following. The implementation environment is the desktop computer with Intel Core i7 2.9 GHz CPU, 16GB memory and Windows 7 operating system. 1) Video modeling by VPS. Suppose one frame of a video contains N pixels, of which, N ex pixels belong to explicit regions and N im in implicit regions. Let the size of the filter dictionary be N F and the filter size be S F , the computational complexity for calculating filter responses is O(N N F S F ). For extracting and learning explicit bricks, the complexity is no more than O(N ex √ S F ). For calculating the response histograms of K chosen filters within the implicit regions, the complexity is no more than O(N im Kk) if there are k homogeneous textural area in the regions. To sum up, the total computation complexity for video coding is no more than O(N N F S F + N ex √ S F + N im Kk). In our experiments, for coding one frame of the video with the size of 288 × 352, the time consumption is less than 0.5 seconds.
2) Reconstruction of explicit regions. Because the information of all the basis for explicit regions are recorded and there needs no additional computations for reconstructing, the computational complexity can be regarded as O(1) and the reconstruction costs no time in comparison to other components.
3) Synthesis of implicit regions by Gibbs sampling by ST-FRAME. For one round sampling, each of the N im pixels will be sampled in the range of the overall intensity levels, say L. For every sampling candidate, i.e. one intensity, the score is calculated via the change of synthesized filter response histograms. To reduce the computation burden, we can simply update the change of filter responses caused by the change of the intensity on the current pixel. This operation requires KS F times of multiplications. As a result, the computational complexity for one round sampling of one frame is O(N im LKS F ). In the experiments of this paper, one frame will be sampled for about 20 rounds. Then the running time is about 2 minutes if the image is 4 bits and the size of implicit region is 10, 000 pixels. 4) Synthesis of implicit regions by Gibbs sampling by MA-FRAME. The computational complexity of MA-FRAME is quite similar with ST-FRAME. The biggest difference is the number of sampling candidates. As the number of velocity candidates is N v and the intensity perturbation range is [−m, m], the computational complexity is O(N im N v mKS F ), which is on the same level with ST-FRAME. However, in real ap-plication, because the intensities of the neighborhood of one pixel are not far away, the intensities of the candidates with different velocities is quite redundant. As a result, MA-FRAME may save a lot of time compared with ST-FRAME, especially when the intensity level is high. For one frame with 8 bits and 60, 000 pixels, the running time is about 4 minutes within 20 rounds sampling.
In summary, the computational complexity of video modeling / coding by VPS is small, but that of video synthesis is quite large. It is because of texture synthesis procedure. In VPS, the textures are modeled by MRF and synthesized via a Gibbs sampling process, which is well known as a computational costing method. However, the video synthesis is only one of the applications of VPS and is used for verifying the correctness of the model. As a result, it is not the very important issue we care about here.

Perceptual Study
The error assessment of VPS is consistent with human perception. To support this claim, in this subsection, we present a series of human perception experiments and explore the relationship between perception accuracy. In the experiments below, the 30 participants include graduate students and researchers from mathematics, computer science and medical science. The age range is from 22 to 39, and they all have normal or correctedto-normal vision.
In the first experiment, we randomly crop several clips of videos with different sizes from the four synthesized textured motion examples and their corresponding original videos (as shown in the left side of Fig. 17, 18 and 19, each video is shown one frame as an example which is marked by (a), (b), (c) and (d) respectively, and they are in different sizes but shown in the same size after zooming for better shows). And then for original and synthesized examples respectively, each participant is shown 40 clips one by one (10 clips from each texture) and is required to guess which texture they come from. We show 3 representative groups of results below for demonstration, in which the sizes of cropped examples are 5 × 5, 10 × 10 and 20 × 20 respectively. Both of the confusion rates (%) of original and synthesized examples are shown in the tables on the right side in Fig. 17, 18 and 19. Each row gives the average confusion rates, which the video clip labeled by the row title is judged coming from textures labeled by the column titles. In order to test if the syntheses are perceived the same with the original videos, we compare the original and synthesis confusion tables in each group. From the results, we can tell that the confusion tables are mostly consistent. For more precise quantitative estimation, we also analyze the recognition accuracies by ANOVA in Table 5, in which, each row shows the corresponding F and p values for each texture in all the three groups. The results show that the recognition accuracies on original and synthesized textures do not differ significantly. Also, it is noted that texture (a) and (b) appear similarly while (c) and (d) tend to be confused with each other. Therefore, the confusion rates between (a) and (b), (c) and (d) are apparently larger. However, from Fig. 17 to 19, as the size of cropped videos gets larger, the confusion rate becomes lower, and actually when the size goes larger than 25 × 25 in this experiment, the accuracies get very close to 100%. This experiment demonstrates the fact that the dynamic textures synthesized by the statistics of dynamic filters can be well discriminated by human vision, although the synthesized one and the original one are totally different on pixel level. Therefore it is evident that the approximation of filter response histograms reflects the quality of video synthesis. Furthermore, it is proved that larger area textures give much better perception effect because human can extract more macroscopic statistical information and motion-appearance characteristics, while small size local areas can only provide salient structural information which may be shared by a various of different videos. In the second experiment, we test if the synthesized video by VPS gives similar vision impact compared with the original video. Each time we provide the original and the synthesized videos to one participant in the same scale. The videos are played synchronously and the participants are required to point out which is the original video in 5 seconds. Each pair of videos is tested in four scales, 100%, 75%, 50% and 25%. The accuracy are shown in Table 6. From the result, when the videos are shown in larger scales, it is easier to discriminate the original and synthesized videos, because a lot of structural details can be noticed by the observers. But as the scale gets smaller, the macroscopic information gives the major impact to the vision system, therefore the original and synthesized video are perceived almost the same, so that the accuracy get lower and approach to 50%. From this experiment, it is evident that although VPS cannot give the complete reconstruction of a video on pixel level, especially for dynamic textures, but the synthesis gives human similar vision impact, which means most of the key information for perception are kept via VPS model.
3.10 VPS adapting over scales, densities and dynamics As it was observed in (Gong and Zhu (2012)) that the optimal visual representation at a region is affected by distance, density and dynamics. In Fig.20, we show four video clips from a long video sequence. As the scale changes from high to low over time, the birds in the videos are perceived by lines of boundary, groups of kernels, dense points and dynamic textures respectively. We show the VPS of each clip and demonstrate that the proper representations are chosen by the model. Fig.21 shows the types of chosen primitives for explicit representations, in which circles represent blob-like type while short lines represent edge-like type primitives. Table 7 gives corresponding comparisons between the number of blob-like and edge-like primitives in each scale. For each scale, the comparison is within first 50, 100, 150 and 200 chosen primitives respectively. It is quite obvious that the percentage of chosen edge-like primitives in large scale frame is much higher than that in small scale. Meanwhile, in large scale frame, the bloblike primitives start to appear very late, which shows the fact that edge-like primitives are much more important in this scale for representing videos. But in small scale frame, the blob-like primitives possess a large percentage at the very beginning, and the number increase of edge-like primitives gets quicker and quicker while more and more primitives are chosen. This phenomenon demonstrates blob-like structures are much more prominent in small scale. So from this experiment, it is evident that VPS can choose proper representations automatically and furthermore, the representation patterns may reflect the scale of the videos.

VPS supporting action representation
VPS is also compatible with high-level action representation. By grouping meaningful explicit parts in a principled way, it represents an action template. In Fig.22, (b) is the action template given by the deformable action template model (Yao and Zhu (2009)) from the video shown in (a). The action template is essentially the sketches from the explicit regions. (c) shows an action synthesis with only filters from a matching pursuit process. While in (d), following the VPS model, the action parts and a few sketchable background are reconstructed by the explicit representation, and the large region of water is synthesized by the implicit representation; thus we get the synthesis of the whole video. Here, the explicit regions correspond to meaningful "template" parts, while the implicit regions are auxiliary background parts.
In order to show the relationship between VPS representation and effective high-level features, we take an KTH video (Schuldt et al (2004)) as an example. Fig.23 and Fig.24 show the spatial and temporal features of explicit regions respectively. In Fig.23, we compare VPS spatial descriptor with well-known HOG feature (Dalal and Triggs (2005)), which has been widely used for object representation recently. (b) is the HOG descriptor for the human in one video frame (a). (c) shows structural features extracted by VPS, where circles and short edges represent 53 local descriptors. Compared with HOG in (b), VPS makes a local decision on each area based on statistics of filter responses, therefore it provides shorter coding length than HOG. Furthermore, it gives more precise description than HOG, e.g. the head part is represented by a circle descriptor, which contains more information than pure filter response histogram like HOG. And (d) gives a synthesis with corresponding filters, which shows the human boundary precisely.
In Fig.24, we show the motion information between two continuous frames (a) and (b) extracted by MA-FRAME in VPS. (d) gives the clustered motion styles in the current video. The motion statistics of the five styles are shown in (e) respectively. It is obvious that region 1 represents the area of head, which is almost still in the waving motion, while region 5 is for two arms, which shows definite moving direction. Region 3 represents the legs, which is actually an oriented trackable area. Region 2 and 4 are relatively ambiguous in motion direction, which are basically background of textures in the video. After giving the trackability map shown in (c) based on these motion styles, the motion template pops up.
In summary, the information extracted by VPS is compatible with high-level object and motion representations. Especially, it is very close to HOG and HOOF descriptors, which are proven effective spatial and temporal features respectively. The main difference is VPS makes a local decision to give a more compact expression and be better for visualization. Therefore, VPS does not only give a middle-level representation for video, but also has strong connection with low-level vision features and high-level vision templates.

Discussion and Conclusion
In this paper, we present a novel video primal sketch model as a middle-level generic representation of video. It is generative and parsimonious, integrating a sparse coding model for explicitly representing sketchable and trackable regions and extending the FRAME models for implicitly representing textured motions. It is a video extension of the primal sketch model (Guo et al (2007)). It can choose appropriate models automatically for video representation.
Based on the model, we design an effective algorithms for video synthesis, in which, explicit regions are reconstructed by learned video primitives and implicit regions are synthesized through a Gibbs sampling procedure based on spatio-temporal statistics. Our experiments shows that VPS is capable for video modeling and representation, which has high compression ratio and synthesis quality. Furthermore, it learns explicit and implicit expressions for meaningful low-level vision features and is compatible with high-level structural and motion representations, therefore provides a unified video representation for all low, middle and high level vision tasks.
In ongoing work, we will strengthen our work from several aspects, especially enhance the connections with low-level and high-level vision tasks. For low-level study, we are learning a much richer dictionary of ∆ B for video primitives, which is more comprehensive. For high-level application, we are applying the VPS features to object and action representation and recognition.