影像序列之動態表示法研究

Abstract

1999年，實驗室的石璧維學長已經發展出一套新方法，可以依據真實的影像自動的建構出階層式的網形表示法[23]。對於影像序列，用簡單的網形節點的區塊對應（nodal block matching）進一步的追蹤此一網形架構。因為這個網形物件是依照影像的內容來建構的，對於影像分析會有所幫助。在[23]，於影像序列中追蹤網形物件方面所用的方法無法提供一個穩定的動態網形，所以在本篇論文，我們用一個新的觀點來審視移動和移動長度的偵測，進而針對此點加以改進。藉由觀察影像中一小塊區域，亮度對時間的變化，我們可以猜測移動的方向（the predicted direction）。對於在影像平面上的每一點我們都可以預測出一個方向來。有了猜測的方向之後，隨之產生一個時空亮度平面（spatial-temporal plane）。在這平面上，對於預測正確的方向，會有亮度平移的現象。根據這個平面上亮度的平移，我們提出一個運動預測的演算法。實驗的結果顯示，網形物件的追蹤更為穩定。

In the previous work in our lab, B.W. Shyr has developed a new scheme to automatically generate a hierarchical mesh structure for a real image [23]. A primitive nodal block matching method is also used in his approach to track the hierarchical mesh structure in image sequences. Because this hierarchical mesh is built according to the image content, this mesh structure is suitable for image analysis. In this paper, a dynamic representation based on Shyr’s approach is studied. The tracking process is further improved to ensure a more stably tracked mesh. By examining the spatial-temporal intensity in an image sequence, the moving direction, namely the predicted direction, for each spatial location can be estimated. With the predicted direction associated with a spatial point, a so-called spatial-temporal plane is generated. The motion displacement of a node can be estimated according to the intensity shift in the spatial-temporal plane. A new motion estimator that adopts the predicted direction is then proposed. CHAPTER 2 BACKGROUNDS 2 2.1 MESH 2 2.2 MESH IN COMPUTER GRAPHICS 2 2.3 MESH IN IMAGE CODING 3 2.3.1 Image Coding 3 2.3.2 MPEG-4 Related Applications 4 2.4 SOME MESH-BASED ALGORITHMS 5 2.4.1 Yao Wang’s Approach 5 2.4.2 Tekalp’s Approach 8 2.5 SHYR’S APPROACH 11 2.5.1 Jong-Wang Operator 11 2.5.2 Hierarchical, Brink-Based Mesh 12 2.5.3 Dynamic Mesh 14 2.6 MOTION ESTIMATION 16 2.6.1 Optical Flow Method 16 2.6.1.1 Method Based on Block Motion Model 17 2.6.1.2 Horn and Schunk’s Method 18 2.6.1.3 Problems in optical flow methods 19 2.6.2 Block-Based Method 19 2.6.2.1 Generalized/Deformable Block Motion 20 2.6.2.2 Phase-Correlation Method 21 2.6.2.3 Block-Matching Method 23 2.6.3 Obstacles in Motion Estimation 24 CHAPTER 3 MOTION DETECTION 26 3.1 USAGE OF TEMPORAL INFORMATION 26 3.2 MOTION DETECTION 27 3.3 SPATIAL-TEMPORAL RELATIONSHIP 34 3.4 MOTION DETECTOR 38 3.4.1 Observation 38 3.4.2 Variation Force 40 3.4.3 Simulation 41 3.5 MOTION ESTIMATION 46 3.5.1 Using The Inferred Motion Direction 46 3.5.2 Motion Estimation Algorithm 50 3.6 DISCUSSION 54 CHAPTER 4 IMPROVEMENT OF STATIC AND DYNAMIC MESH GENERATION 55 4.1 CURVATURE THRESHOLD 55 4.2 CORRESPONDENCE 57 4.2.1 Locality Adjustment 58 4.2.2 Refinement 60 4.3 MESH TRACKING 64 4.3.1 A Nodal Tracking Method 64 4.3.2 A Segment-Based Tracking Method 66 CHAPTER 5 CONCLUSIONS 68 REFERENCE 69 FIGURE 2.1 A DESIRED MESH OBJECT AND ITS TWO SUBPARTS (FROM TEKALP [15]). 2 FIGURE 2.2 LEFT: LENA (265X256). RIGHT: THE IMAGE SURFACE. 4 FIGURE 2.3 THE MESH GENERATED BY WANG’S APPROACH. [8] 7 FIGURE 2.4 THE ILLUSTRATION OF THE MAPPING AND SPLITTING PROCESS (FROM Y. WANG [9]). 8 FIGURE 2.5 A HIERARCHICAL QUARDTREE MESH (FROM Y.WANG[9]). 8 FIGURE 2.6 THE STRATEGY FOR MESH NODE SELECTION (FROM Y. ALTUNBASAK AND A. TEKALP[16]). 9 FIGURE 2.7 REMOVAL OF BOUNDARY NODES. 10 FIGURE 2.8 INTENSITY PROFILE AND TWO DIFFERENT TYPES OF IMAGE FEATURES. 11 FIGURE 2.9 (A) A SYNTHETIC IMAGE; (B) THE DETECTED IMAGE BRINKS. 12 FIGURE 2.10 THE FLOWCHART OF MESH OBJECT GENERATION. 12 FIGURE 2.11 LEFT: THE MESH OBJECT. RIGHT: THE RECONSTRUCTED IMAGE. 13 FIGURE 2.12 AN EXAMPLE OF A HIERARCHICAL MESH. 14 FIGURE 2.13 TRACKING PROCEDURE. 15 FIGURE 2.14 THE ORIGINAL CLAIRE SEQUENCE (THE UPPER ROW) AND THE RECONSTRUCTED IMAGES FROM THE DYNAMIC MESH (THE BOTTOM ROW). 15 FIGURE 2.15 ILLUSTRATION OF BLOCK MATCHING. 24 FIGURE 2.16 THE OCCLUSION PROBLEM [1]. 24 FIGURE 2.17 THE APERTURE PROBLEM [1]. 25 FIGURE 3﷓1 THE IMAGE CUBE OF THE MOTHER-AND-DAUGHTER SEQUENCE. 27 FIGURE 3﷓2 DIFFERENCE OF VIEWPOINTS FOR MOTION TRACKING. 28 FIGURE 3﷓3 THREE DIFFERENTIATION OPERATORS. (A): TYPE A; (B): TYPE B; (C): TYPE C. 28 FIGURE 3﷓4 (A) IP[K] AT THE PIXEL P OF FIGURE 3﷓1. (B)-(D): THE DETECTION RESULTS AFTER APPLYING TYPE A, TYPE B, AND TYPE C OPERATORS, RESPECTIVELY. 29 FIGURE 3﷓5 (A) LEFT COLUMN: THE 4 CONSECUTIVE FRAMES OF THE ORIGINAL SEQUENCE. (B) RIGHT COLUMN: THE DETECTION RESULTS BY USING THE TYPE A OPERATOR. 31 FIGURE 3﷓6 (A) THE DETECTION RESULTS BY APPLYING TYPE B OPERATOR OVER FIGURE 3﷓5(A). (B) THE DETECTION RESULTS BY APPLYING TYPE C OPERATOR OVER FIGURE 3﷓5(A). 32 FIGURE 3﷓7 (A) A STEP EDGE ON THE FRAME N. (B) THE EDGE SHIFTS TO THE LEFT IN THE FRAME N+1. 33 FIGURE 3﷓8 A FAST TRANSIT IP[K]. 33 FIGURE 3﷓9 THE RELATIONSHIP AMONG MOVING SPEED, IK[P], AND IP[K]. 34 FIGURE 3﷓10 AN EXAMPLE OF MOTION DETECTION FOR A SMOOTH IP(T). 35 FIGURE 3﷓11 (A) THE ORIGINAL FRAME IN THE MOTHER-AND-DAUGHTER SEQUENCE. (B) AND (C): DETECTION RESULTS BY APPLYING TYPE A AND TYPE C OPERATORS, RESPECTIVELY. (D): SUBPART OF (B). (E): SUBPART OF (C). 36 FIGURE 3﷓12 (A) THE ORIGINAL FRAME IN THE MOTHER-AND-DAUGHTER SEQUENCE. (B) THE DETECTION RESULT AFTER APPLYING THE REVISING ALGORITHM AND (C) RESULT AFTER THRESHOLDING. (D) SUBPART OF (B). (E) SUBPART OF (C). 37 FIGURE 3﷓13 AN EXAMPLE OF MOVING DIRECTION PREDICTION. (A): OBSERVED INFORMATION; (B),(C): TWO POSSIBLE I(X;T0) AND THE CORRESPONDING MOVEMENTS. 38 FIGURE 3﷓14 A DIFFERENT VIEW OF THE EXAMPLE IN FIGURE 3﷓13. 39 FIGURE 3﷓15 SOME EXAMPLES OF PREDICTING THE MOVING DIRECTION IN THE 2-D CASE. 40 FIGURE 3﷓16 TWO SUCCESSIVE FRAMES. 42 FIGURE 3﷓17 (A) THE RESULT OF MOVING DIRECTION PREDICTION. (B)-(E): CORRESPOND TO THE A, B, C, AND D AREAS ON, RESPECTIVELY. 42 FIGURE 3﷓18 SOME INDETERMINATE EXAMPLES. 43 FIGURE 3﷓19 THE ILLUSTRATION OF THE APERTURE PROBLEM IN FIGURE 3﷓17(C). 43 FIGURE 3﷓20 AN ILLUSTRATION OF FALSE PREDICTION. 44 FIGURE 3﷓21 AN EXAMPLE OF FALSE DETECTION. (A),(B): TWO CONSECUTIVE FRAMES. (C) THE SUBPART OF (A) OVERLAID WITH PREDICTED MOTION VECTORS. (D) SUBPART OF (B) SHOWING THE DAUGHTER’S COLLAR IS BLOCKED BY THE MOTHER’S HAND. 45 FIGURE 3﷓22 AN EXAMPLE OF TEXTURE PROBLEM. (A) AN IMAGE FRAME IN THE FLOWER GARDEN SEQUENCE; (B) THE DETECTED MOVING DIRECTIONS; (C) DETAILS IN THE FLOWER GARDEN. 46 FIGURE 3﷓23 (A) AN IMAGE FRAME OF THE CLAIRE SEQUENCE WITH THE PREDICTED VECTORS OVERLAID ON IT. (B) THE SUBPART OF (A) SHOWING THE DETAIL OF THE BOUNDARY BETWEEN THE BACKGROUND AND THE HAIR. 47 FIGURE 3﷓24 THREE CUTS AND THEIR RELATED INTENSITIES. 47 FIGURE 3﷓25 THE SPATIAL-TEMPORAL PLANE. 47 FIGURE 3﷓26 AN ILLUSTRATION OF FALSE DETECTION. 48 FIGURE 3﷓27 AN ILLUSTRATION OF THE TEXTURE PROBLEM. 49 FIGURE 3﷓28 (A), (B), (C): THE PROFILES RETRIEVED FROM THE TREE, FLOWER, AND ROOF AREAS IN THE FLOWER GARDEN SEQUENCE, RESPECTIVELY. (D) THE PROFILE RETRIEVED FROM A SMOOTH REGION. 49 FIGURE 3﷓29 AN EXAMPLE OF PROFILE DIVISION. 50 FIGURE 3﷓30 (A) THE VARIATION FORCE OVERLAID WITH THE ORIGINAL IMAGE. (B) THE VARIATION FORCE OVERLAID WITH THE FRAME DIFFERENCE. (C)-(F):SUBPARTS OF (B). 52 FIGURE 3﷓31 MOTION ESTIMATION RESULT OF ONE FRAME OF THE FLOWER GARDEN SEQUENCE. 53 FIGURE 3﷓32 THE MOTION ESTIMATION RESULT OF ONE FRAME OF THE MOTHER-AND-DAUGHTER SEQUENCE. 53 FIGURE 4﷓1 THE USED DOG OPERATOR. 55 FIGURE 4﷓2 AN EXAMPLE OF FEATURE LOCALITY SHIFT BY DIRECTLY MAPPING. 57 FIGURE 4﷓3 THE SIMULATION RESULT OF LOCALITY ADJUSTMENT. (A) MAPPED SEGMENTS; (B) FINE-TUNED SEGMENTS. (A-1 TO 3): DETAILS OF THE IMAGE IN (A); (B-1 TO 3): DETAILS OF THE IMAGE IN (B) 59 FIGURE 4﷓4 THE REFINEMENT PROCEDURE. 61 FIGURE 4﷓5 (A) THE FINE-TUNED SEGMENTS. (B) THE REFINED SEGMENTS. (C) THE FINAL RESULT. 61 FIGURE 4﷓6 AN EXAMPLE OF A HIERARCHICAL MESH AND THE RECONSTRUCTED IMAGES. (A) THE ORIGINAL IMAGE. (B),(C): CONSTRUCTED MESHES AND THE RECONSTRUCTED IMAGES IN SHYR’S APPROACH. (D),(E): CONSTRUCTED MESHES AND THE RECONSTRUCTED IMAGES IN THE REVISED APPROACH. 63 FIGURE 4﷓7 THE TRACKING RESULT BY DIRECTLY USING THE NEW MOTION ESTIMATION METHOD. (A)-(H) RECONSTRUCTED IMAGES FROM TO THE 1ST FRAME TO THE 8TH FRAME. 64 FIGURE 4﷓8 NODE TRACKING RESULTS BY USING THE MOTION ESTIMATION METHOD ACCOMPANIED WITH A CONSTRAINT OVER NODE FEATURE STRENGTH. (1)-(12): RECONSTRUCTED IMAGES OF THE FIRST 12 FRAMES. 65 FIGURE 4﷓9 THE SUBPART OF THE 11TH RECONSTRUCTED IMAGE. 65 FIGURE 4﷓10 AN EXAMPLE OF NON-CONSISTENT MOVEMENTS OF A SEGMENT. 67 FIGURE 4﷓11 TRACKING RESULTS BY USING THE SEGMENT-BASED TRACKING METHOD. (1)-(12): RECONSTRUCTED IMAGES OF THE FIRST 12 FRAMES IN THE CLAIRE SEQUENCE. 67 CHAPTER 1 Introduction In computer graphics (CG), “mesh” has been widely used as an object model and conveyed to various applications. In MPEG-4 standard, it has also been used as an alternative image representation. Once a mesh is generated for a scene, it can be used for multimedia editing and video object manipulations, like the replacement of objects in a scene. Despite of these applications relevant to MPEG-4 and CG, mesh may also be used in image analysis, like pattern analysis, depth estimation in stereo imaging, etc. For these applications, however, how to efficiently build a mesh model is a key technology. In the previous work in our lab, B.W. Shyr has developed a new scheme to automatically generate a hierarchical mesh structure for a real image [23]. A primitive nodal block matching method is also used in his approach to track the hierarchical mesh structure in image sequences. Because this hierarchical mesh is built according to the image content, this mesh structure is suitable for image analysis. In this paper, a dynamic representation based on Shyr’s approach is studied. The tracking process is further improved to ensure a more stably tracked mesh. By examining the spatial-temporal intensity in an image sequence, the moving direction for each spatial location can be estimated. We then carefully discuss these estimated results and pick out only those reliable estimated directions, namely the predicted directions. With the predicted direction associated with a spatial point, a so-called spatial-temporal plane is generated. The motion displacement of a node can be estimated according to the intensity shift in the spatial-temporal plane. A new motion estimator that adopts the predicted direction is then proposed. Firstly, the applications adopting “mesh” model would be briefly mentioned in Chapter 2. In this chapter, existing algorithms for the mesh structure generation for a real image are also reviewed, including the Shyr’s approach. In Chapter 3, we then discuss the motion estimation in a different point of view and develop a motion estimator. In Chapter 4, the improved version for the generation of a static hierarchical mesh is made and then the new tracking algorithm is proposed.