Table Tennis ( Ping Pong ) is arguably the world's second or third most popular sports with an estimated number of 300 million participants [1,2]. The sport is particularly popular in Europe and Asia. A match between top players in China can easily attract tens of millions of spectators. Numerous video clips of Table Tennis matches and lessons have been distributed through DvDs or Internet[2]. Therefore, it is desirable to develop a technique to compress these video clips with very high compression ratio while still maintaining a high quality video playback. Traditional video compression standards like MPEG4 and H2.61 specify various kinds of techniques for compressing videos. Figure 1 shows a typical MPEG4 video compression/decompression process[3,4,5]. In the figure, T represents a transformation like DCT ( Discrete Cosine Transform ) and Q represents quantization; T^-1 and Q^-1 are the corresponding inverse transformation and quantization. ME is motion estimation and MC is motion compensation; uF_n denotes an unfiltered frame.

Figure 1. A typical MPEG4 video codec.

While these standards do a good job in providing generic methods of compression, they fail to make customizations to compress special features and utilize them to achieve very high compression performance.

In this article, we present a framework that is customized for Table Tennis ( TT ) video clip compression; utilizing the special features of a TT match, we can achieve very high compression ratios by combining techniques of image processing and computer graphics. Our main concern here is about TT video clips compression for distribution; the compression is done offline and only once but the uncompression will be done many times and maybe online. Therefore, the compression stage is allowed to be time-consuming and tedious as long as the decompression is fast.

When watching a match, most TT fans including the author are more interested in the players' movement and the ball motion rather than the background audience and some other irrelevant features like the texture of the floor or the color of the table. The central theme of our framework is to replace the actual scenes in a frame with simulated graphics. Because of the characteristics of a TT match, only a small number of parameters are required to generate the simulated graphics. The graphics parameters become the video data and can be further compressed using traditional compression methods.

Figure 2 shows the framework of our compression method , where SAP_n is the set of Scene Animation Parameters generated from the image frame F_n using image processing techniques. As shown in the figure, SAP_n can be compressed by a simple DPCM model[3] coupled with a transformation T and quantization Q; T can be a DCT or in its simplest form, it can be an identity transformation which does not do anything to the prediction errors e. The lossless compression could be arithmetic coding, Huffman coding or run-level coding followed by Huffman coding. The prediction errors e are obtained by subtracting the current 'frame' SAP_n from a previous 'reconstructed-frame' SAP_n-1[3]. In the decoding process, the reconstructed scene animation parameters ( after going through lossless decompression, inverse quantization, inverse transformation and summation ) are fed into a scene animation model which reconstructs the frame from the SAPs.

Figure 2. Block diagram showing compression using image processing and animation.

Figure 3a shows a typical scene of a TT match. As shown in the figure, we need parameters to describe the following objects,

1. the ball,
2. the table,
3. the two players holding paddles

The ball and the table are solid objects and are relatively easy to define and reconstruct. The players are deformable and are more difficult to track. The simplest object to specify is the ball; all we need is to define its pixel position in the current frame. We can use two 10-bit numbers to denote the coordinates of the ball center. Processing the table image is also simple; it can be specified by the coordinates of its four corners. Since a player always holds her paddle, we regard a player-and-paddle as one object and without ambiguity, sometimes refer to it as a player. Obviously, a player is deformable. It is a state of art of research to track a human in a video and animate it. A lot of research on human synthesis and animation has been done in the past decade[6,7]. Sophisticated Open-source applications for modeling and creating human graphics are also available[8]. In the following sections, we shall discuss recognizing, locating, specifying, and reconstructing the ball, the table and the players.

Of all the objects listed above, the table is the easiest to locate as it is a rigid object and has a large size; its position does not change rapidly from frame to frame. We also know that it is blue. ( If it is not, we can obtain the color by first watching a few frames of the video and making an estimate of its color components. As we have mentioned earlier, the compression stage could be tedious. After all, under normal conditions, a table tennis video clip is always edited before it is distributed. ) To extract the table from an image frame, we first segment the image into regions. A lot of segmentation techniques have been developed in the past few decades[9-14]. In our work, we adopted the region-growing techniques [13,14] based on statistical concentration inequalities[15,16] to segment the images and to identify the table. In this method, an image is partitioned into regions that satisfy a similarity criterion such as matching a color or reaching a brightness level. At the beginning, a region starts with a point ( a pixel ) and "grows" by grouping all neighboring points that possess a similar property. Specifically, our similarity criterion is a statistical predicate[15,16]. This is basically a union-find problem and can be implemented efficiently with a method developed by Tarjan[17]. Figure 3b shows the segmented regions of the image shown on Figure 3a based on this statistical method.

Figure 3a

Figure 3b

There has been a number of research work on ball localization and tracking in videos[18,19,20], where one reconstructs the trajectory of a moving ball by tracking the ball through the frames of a video sequence. The motion of the ball in a sports game usually has a characteristic trajectory depending on the type of game played. The characteristic trajectory is exploited to help track the ball. However, it is not easy to follow a fastly moving ball; this is because the rapid movement of the ball could cause its image to appear fuzzy in a frame; the ball appears as an elongated smear without sharp contours, confusing most computer vision algorithms. Figure 4 shows an example of this phenonmenon.

Boracchi et al. discussed a model to address the motion blur problem in [21]; they presented an algorithm to estimate the 3D position and velocity of a uniformly-colored moving ball from a single image, by explicitly analyzing and exploiting motion blur. While it is certainly worthwhile to make further explorations of their algorithms in the future, it is too complicated for our application at this moment. The algorithm has to analyze several 1D image intensity profiles in order to extract points belonging to the ball contours at the beginning and the end of the exposure and requires that the camera calibration parameters are known. It would be too computing intensive in our application and also we do not have the camera calibration parameters. We have used a simpler approach here. We use a keyframing technique[22,23,24] commonly used in computer animation to help track the table tennis ball. Often, an animator has a list of values associated with a given parameter at specific frames (called key frames or keys) of the animation. The question to be answered is how best to generate the values of the parameter for the frames between the key frames. The parameter to be interpolated may be a coordinate of the position of an object, or a joint angle of an appendage of a robot, or the transparency attribute of an object, or any other parameter used in the display and manipulation of computer graphic elements. In our case, we want to interpolate the positions of the ping pong ball. Suppose its position is described by a single vector p(t). To animate position using keyframing, one picks times t₀, t₁, ..., t_n and corresponding values for p(t_i) for each i. Other p(t) values with t₀ ≤ t ≤ t_n can be found by interpolation using Bezier or B-spline interpolation[25,26]. Frames that show a clear image of the ball without any blurring are chosen as key frames.

The ball position vectors p(t_i) of these frames can be found by template matching[9,11]. Given a template image vector W with size KxJ, we wish to search for the location where W appears in an image I. The template matching technique consists of forming a correlation measure between two picture functions and determining the location of the maximum correlation. We can define a correlation measure R(u,v) at the reference location (u,v) as

R(u,v) = ∑^K_k=1∑^J_j=1I(u+k,v+j)W(k,j) / ( S_IS_W )
where
S_I = [∑^K_k=1∑^J_j=1I²(u+k,v+j)]^½

S_W = [∑^K_k=1∑^J_j=1W²(k,j)]^½

From Cauchy-Schwarz inequality, we know that -1 ≤ R(u,v) ≤ 1. For a given window W, S_W is a constant. Therefore, the computation can be reduced to
R(u,v) = ∑^K_k=1∑^J_j=1I(k+u,j+v)W(k,j) / S_I
The target location is the location (u,v) that maximizes R(u,v).

Once the ball positions at the clear-image-frames are determined, the positions at other frames are interpolated. The interpolated positions are used as a guide for locating the actual ball positions in those frames. If the searched ball position in a blur-image-frame is too far from the interpolated position, the searched position is discarded and the interpolated position is used. For simplicity, we assume the ball image has constant size at various frames.

• The Players

  As we have mentioned in the Introduction section, we refer to a player as a deformable object consisting of a human and a paddle. Tracking and recognition of human motion has become an important research topic in image processing and graphics. Human motion tracking and recognition are usually tackled by making simplifying assumptions concerning the motion or imposing constraints on it. Very often, the first step towards human tracking is to segment human figures from the background[27]. A popular and relatively simple method to extract and track a deformable object in an image is the Active Contour Model ( also called "snake" ) [28,29], which finds the contour of an object by balancing the effects of several energy terms. Variations of the Active Contour Model also exist. For example, C. Xu and J.L. Prince improved the model by defining a new non-irrotational external force field, which they called the gradient vector flow ( GVF ) field and referred to the resulted snake as GVF snake[30]. Another approach for tracking a deformable object is to employ deformable templates[12,31,32,33] to automatically detect the objects. In general, retrieval by shape requires object detection and segmentation. Lifeng Liu and Stan Sclaroff had used model-based region- grouping techniques to detect and retrieve deformable objects [34,35]; they also found that using this method along with perceptually-motivated splitting strategy yields good image segmentation results of deformable shapes[36].

  Extracting facial features effectively is still a complex issue as facial features are highly deformable and vary in shape from individual to individual. For example, Yi Xiao and Hong Yan used Delaunay triangulation and Voronoi diagrams to locate facial features of humans[37]; Jorgen Ahlberg presented a method called Active Appearance Model that requires data-training to extract facial animation parameters from videos[38]. All these method involve intensive computing.

  To simplify our model, we do not animate the facial expression; we choose the traditional Active Contour Model ( ACM ) in our work to track the players. Open-source packages for image contour tracking and extraction based on ACM are available. We have adopted the one developed by K.F. Lai[28] in our work; the package is written in C/C++ with detailed documentation and consists of a thesis that comes with the package explaining in detail the principles of ACM. To apply the ACM in tracking, we first divide a player into the following components, assuming that the player is right-handed:

Figure 4. Motion-blur image of ball

Head Upper Body Left Upper Arm Left Lower Arm Left Upper Leg Left Lower Leg Left Hand Left Foot

Lower Body Right Upper Arm Right Lower Arm Right Upper Leg Right Lower Leg Right Hand with Paddle Right Foot

If the player is left-handed, the roles of Left Hand and Right Hand are interchanged. Each component is then tracked by the Active Contour Model. At the very beginning, a user has to provide a briefly estimated contour to each component. The ACM algorithm then iterates over a number of times and finds a better estimate for the actual component contour; these contours are then used to find the component contours of the next frame.

A player is then modeled as the set of components listed above connected by joints and is conveniently represented by a tree structure; the nodes of the tree define all the player components. For simplicity, we assume each component only has one degree of freedom ( DOF ) movement with respect to its parent. We also need a few parameters to specify the orientation and position of the player as a whole. Moreover, we define a player model in its neutral state. Player Animation Parameters ( PAPs ) consisting of deviations of joint angles from the neutral state are used to describe the state of the player at a certain instant. ( Note that the set of PAPs is a subset of the set of SAPs. ) When a neutral player model is deformed, a sequence of PAPs is generated. From the PAPs we obtain the joint angles and when the joint angles are specified, the state of the animated player can be found by forward kinematics[22].

• Scene Animation

  Graphics techniques are employed to reconstruct the scene based on the decoded SAPs. We have used OpenGL and SDL ( Simple DirectMedia Layer )[39] to render the graphics. Rendering the table and the ball is straightforward. Modeling and synthesizing humans are a lot more complex as they are multibodies or articulated objects. Reference 6 gives a detailed discussion on human modeling and animation and current research on this topic. In general, to give a realistic look of a human, each body part is constructed as a mesh[6]. At the moment, we simplify the human model by representing it as a scene graph and we only use the four graphics primitives, sphere, cylinder,i cube and cone with transformation to represent any body part. For example, the eyes of a player can be represented as scaled spheres, and the nose as a scaled cone. A scene graph is a hierarchical approach to describing objects and their relationship to each other. By making use of scene graphs to describe objects, we can separate scene representation from rendering. When a node is undergone a transformation like translation or rotation, all its children will go through the same transformations too. The Virtual Reality Modeling Language ( VRML )[40] is an example of using scene graphs ( internally ) to describe the three-dimensional world. In our work, we have used the simple object-oriented scene graph toolkit developed by Edward Angel[41] to reconstruct the players in 3D; the toolkit is an open-source library which foundation is supplied by OpenGL and Unix; the library includes some basic objects for creating a scene: camera, light, attributes, transformations and some geometry objects, including spheres, cylinders, cubes and cones. A player in the neutral state is constructed using this scene graph toolkit and is then transformed ( or "deformed" ) using the decoded PAPs to obtain the current state.

• Results

  We applied the above framework to compress a few short table tennis video clips downloaded from the Internet. In general, the program can track the table and the ball fairly well. However, the players who are deformable are more difficult to track; we have to adjust the component contours manually in some of the frames when the ACM fail to find the desired contours. So at the moment, our program only works semi-automatically; some manual work is required to obtain a decoded video that closely resembles the original one. However, it does demonstrate the concept of compressing table tennis video clips for distribution by combining techniques of image processing and computer graphics. If we assume a frame rate of 20 frames per second ( fps ), we can make an estimate of the bit rate in the worst case, where no compression on the SAPs is performed and each SAP requires a 10-bit number to represent. There are totally about 40 SAPs. The bit rate R under this situation is given by

  r = 40 SAP/frame x 10 bits/SAP x 20 frames / second = 8 kbps

  With compression on the SAPs, the bit rate R could be reduced to

  R ≈ 0.2 - 2 kbps

  Note that the bit rate is independent of the frame size. Even if the video image size is very large we still can transmit at the rate of 0.2 to 2 kbps for a reasonable good playback.

• Conclusions

  We have presented a framework for compressing table tennis video clips by combining image processing and computer graphics techniques. A statistical region-growing segmentation algorithm and Hough transform is used to locate the table in a frame. Simple correlating and interpolation techniques are used to locate the ball. The Active Contour Model is used to track the players, which are deformable. Scene animation parameters ( SAPs ) of each frame are extracted and compressed with a simple DPCM model and entropy-encoding. The reconstructed SAPs are fed to a graphics model to reconstruct the playing scene. Experiments done on a few short table tennis video clips show that the framework is feasible and yields very low bit rate though further fine-tuning on the Active Contour Model is needed to make the compression process totally automatic and flawless.

• References
  1. http://www.johann-sandra.com/popular.htm
  2. http://www.ittf.com/
  3. Iain E.G. Richardson, "H.264 and MPEG-4 Video Compression", John Wiley & Sons Ltd., 2003
  4. Iain E.G. Richardson, "H,264/MPEG-4 Part 10 White Paper", http://www.vcodex.com
  5. T.L. Yu, "Implementation of Video Player for Embedded Systems", Proceedings of IASTED on Signal and Image Processing, p. 25-30, Honolulu, Hawaii, August 20-22, 2007.
  6. Edited by Nikos Sarris and Michael G. Strintzis, "3D Modeling & Animation: Synthesis and Analysis Techniques for the Human Body", IRM Press, 2005.
  7. Editied by Igor S. Pandzic, and Robert Forchheimer, "MPEG-4 Facial Animation: The Standard, Implementation and Applications", John Wiley & Sons, 2002.
  8. http://www.dedalo-3d.com/
  9. Ernest L. Hall, "Computer Image Processing and Recognition", Academic Press, 1979.
  10. Anil K. Jain, "Fundamentals of Digital Image Processing", Prentice Hall, 1989.
  11. Rafael C. Gonzalez, and Richard E. Woods, "Digital Image Processing", Addison-Wesley, 1992.
  12. Pedro F. Felzenszwalb, "Representation and Detection of Deformable Shapes", IEEE Trans. Pattern Analysis and Machine Intelligence, vol 27, no. 2, pp. 208-219, Feb. 2005.
  13. C. Fowlkes, D. Martin, J. Malik. "Learning Affinity Functions for Image Segmentation: Combining Patch-based and Gradient-based Approaches", IEEE Conference on Computer Vision and Pattern Recognition ( CVPR ), Madison, WI, (June 2003).
  14. D. Martin, C. Fowlkes, J. Malik. "Learning to Detect Natural Image Boundaries Using Local Brightness, Color and Texture Cues", IEEE Transactions on Pattern Analysis and Machine ( TPAMI ) 26 (5) p.530-549, May 2004.
  15. Richard Nock and Frank Nielsen, "Statistical Region Merging", IEEE Transactions on Pattern Analysis and Machine Intelligence, 2004.
  16. Frank Nielsen and Richard Nock, "On Region Merging: the Statistical Soundness of Fast Sorting, with Applications", IEEE Computer Vision and Pattern Recognition 2003.
  17. Tarjan, R. E. "Efficiency of a Good But Not Linear Set Union Algorithm," Journal of the ACM (JACM), 22(2), p. 215-225, 1975.
  18. A.O. Gopal Pingali and Y. Jean, "Ball tracking and virtual replays for innovative tennis broadcasts", Proc. of ICPR 2000 Conference, p. 4152, Washington, DC, 2000, IEEE Computer Society
  19. G.J.J. Ren, J. Orwell and M. Xu, "A general framework for 3d soccer estimation and tracking", Proc. of ICIP 2004 Conference, 2004.
  20. L.C. Jonathan Rubin, B.C. Wuensche and C. Stevens, "Computer vision for low cost 3-d golf ball and club tracking", Proc. of Image and Vision Computing, New Zealand, 2005.
  21.G. Boracchi et al., "Ball Position and Motion Reconstruction from Blur in a Single Perspective Image", Proc. of 14th International Conference on Image Analysis and Processing (ICIAP 2007), IEEE Computer Society.
  22. Samuel R. Buss, "3-D Computer Graphics: A Mathematical Introduction with OpenGL", Cambridge University Press, 2003.
  23. Michael E. Mortenson, "Geometric Modeling", John Wiley & Sons, New York, 1985.
  24. David F. Rogers, J. Alan Adams, "Mathematical Elements for Computer Graphics", McGraw Hill, New York, 1976.
  25. D.F. Rogers, "An Introduction to NURBS: With Historical Perspective", Morgan Kaufmann, San Francisco, 2001.
  26. L.L. Schumaker, "Spline Functions: Basic Theory", Wiley, New York, 1981.
  27.Nikos Sarris and Michael g. Strintzis, "3D Modeling & Animation: Synthesis and Analysis Techniques for the Human Body", IRM Press, 2005.
  28. K.F. Lai, "Deformable Contours: Modeling, Extraction, Detection and Classification", Ph.D. Thesis, Electrical Engineering, University of Wisconsin-Madison, 1994.
  29. Andrew Blake and Michael Isard, "Active Contours" Springer-Verlag, 1998. ( Provide codes in Author's Web site )
  30. C. Xu and J.L. Prince, "Snakes, Shapes and Gradient Vector Flow", IEEE Transactions on Image Processing, 7(3), pp.359-369, March 1998.
  31. A.K. Jain, Y.Zhong and S. Lakshmanan, "Object matching using deformable templates", PAMI, 18(3), p.267-278, 1996.
  32. K. Mardia and K. de Souza, "Deformable template recognition of multiple occluded objects", PAMI, 19(9), p.1035-1042, 1997
  33. A. Yuille, D.S. Cohen, and P. Hallinan, "Feature extraction from faces using deformable templates", IJCV, 8(2), p.99-111, 1992.
  34. Liu, L., and Sclaroff, S. "Deformable Shape Detection and Description via Model-Based Region Grouping." Proc. IEEE Conf. on Computer Vision and Pattern Recognition, (CVPR), Vol. 2, June, 1999, pp.21-27
  35. Stan Sclaroff, and Lifeng Liu. "Deformable Shape Detection and Description via Model-Based Region Grouping." IEEE Trans. on Pattern Analysis and Machine Intelligence, May, 2001, Vol. 23, No.5, pp. 475-489.
  36. Lifeng Liu, and Stan Sclaroff. "Region Segmentation via Deformable Model-Guided Split and Merge." The International Conference on Computer Vision (ICCV) , Jul., 2001.pp. I:98-104.
  37. Yi Xiao, and Hong Yan, "Facial feature location with Delaunay triangulation/Voronoi diagram calculation", Proceedings of the Pan-Sydney area workshop on Visual information processing, p. 103-108, Volume 11, 2001.
  38. Jorgen Ahlberg, "Extracting MPEG-4 FAPs from Video", MPEG-4 Facial Animation, Edited by Igor S. Pandzic and Robert Forchheimer, John Wiley & Sons, 2002, p.103-113.
  39. http://www.libsdl.org/
  40. http://www.web3d.org/
  41. Edward Angel, "Interactive Computer Graphics: A Top-Down Approach with OpenGL", 3rd Edition, Addison-Wesley, 2002.