A graph theory model using human nature structure①

Liu Jia (劉 佳), Duan Miyi, Li Wenfa, Yuan Jiazheng

(*School of Computer Science and Engineering, Beihang University, Beijing 100191, P.R.China) (**Smart City College, Beijing Union University, Beijing 100101, P.R.China)

A graph theory model using human nature structure①

Liu Jia (劉 佳)***, Duan Miyi*, Li Wenfa②, Yuan Jiazheng**

(*School of Computer Science and Engineering, Beihang University, Beijing 100191, P.R.China) (**Smart City College, Beijing Union University, Beijing 100101, P.R.China)

A graph theory model of the human nature structure (GMH) for machine vision and image/graphics processing is described in this paper. Independent from the motion and deformation of contours, the human nature structure (HNS) embodies the most basic movement characteristics of the body. The human body can be divided into basic units like head, torso, and limbs. Using these basic units, a graph theory model for the HNS can be constructed. GMH provides a basic model for human posture processing, and the outline in the perspective projection plane is the body contour of an image. In addition, the GMH can be applied to articulated motion and deformable objects, e.g., in the design and analysis of body posture, by modifying mapping parameters of the GMH.

articulated motion and deformable objects (AMDO), human nature structure (HNS), graph theory, machine vision, image/graphics processing

0 Introduction

The recognition and processing of the human body in machine vision and image/graphics processing is significant problem. In general, targets are recognized and tracked based on their contours and color textures[1-5]. Color texture is a result of light reflex on the body surface. The texture border and distribution are related to the light reflex as well as the body structure and posture. Therefore, texture distribution provides relevant body pattern information. Because the body posture is variable, the contour described by the texture is deformable, resulting in difficulties in the recognition of the target.

In the case of solid or deformable objects, the appearance features can be described as a shape based on a rigid or deformable frame. Under different movement states or visual angles, three-dimensional (3D) space characteristics of an object determine the contour and texture of the object in an image. However, despite the movement of the object or changes in vision angle, the frame structure (dimensions and connection of the parts) of an object does not change. These are exact characteristics of articulated motion and deformable objects (AMDO). In the study of AMDO, layered articulated graphics are used to build the relationship between articulated rigid and deformation contours[6-8]. The spatial graphic is constructed with vertices and edges to describe the basic structure, thus giving the object contours. The graphic describing the object structure does not vary with the movement of the object, changing lighting conditions, or vision angles, and provides a model of the object’s shape[9,10]. Describing the object’s structure with a graphical methodology not only gives different object shapes, but also provides a new method of recognition[11-15].

By dividing the human body into different basic units and confirming the connection between them, a graph theory model of human nature structure (GMH) is presented. The GMH has simple and clear characteristics, and is invariant with respect to body shape movement or changes in vision angle, making it a useful tool for human body recognition in machine vision or AMDO processing.

The human body shape and nature structure problems are discussed in Section 1, and the basic units of the human body and associated relationships are described in Section 2. In Section 3, the GMH is developed. Section 4 analyzes the contents of the GMH, and finally, Section 5 provides a simple example of GMH application. Section 6 concludes the study.

1 Human body shape and nature structure

A basic model of the human body is needed for machine vision and image/graphical processing. Such a model can be used to describe the human body structure and movement, and is the basis of the recognition process.

One characteristic of natural objects is 3D space distribution. Considering object shapes in machine vision systems, non-fluid objects (including the human body) can be described using a 3D frame. For example, a spring-articulated system can describe the frame of objects or the human body. In nature and engineering, objects have a geometric shape. If certain parts are considered independent, with little variation, then an object can be considered as a geometric collection of several independent parts connected by a specific articulated structure. Fig.1 shows geometric approximations of the human body and a car.

(a) Geometric approximation of the human body

(b) Geometric approximation of a car Fig.1 Geometric approximation

In Fig.1, the links are represented as vertices and the center lines (i.e., the edges) are linked by the vertices. This simple approach forms an object frame. Additionally, the link between edges and vertices can be articulated or rigid.

The link relationship between vertices and edges and the length of the edges are invariant. This basic structural feature of the human body and other objects is called the nature structure, which is an object structure that is not affected by the shape or movement of the object, and is a physical feature of solid objects. None of the vertices and edges, or connections between the two, is affected by the changing shape of the object, vision angle, reflective shine, or the body’s motion. This is precisely the requirement of image or graphics processing for body identification and AMDO. For example, a 3D frame of a car could be built using a graphical description, as shown as Fig.1(b). This frame is not affected by the changing vision angle, lighting, or motion because the structure of the car is rigid.

From the perspective of machine vision and image and graphics processing, the nature structure describes the inherent structure of the object.

Therefore:

The edges represent parts of the object that are geometrically unchanged and/or have certain rigidity.

Vertices represent the link between edges. There are two types of vertices, articulated and rigid. The connecting relationship of vertices and edges is unchangeable.

The adjacent relationship of vertices remains unchanged and is not affected by the motion of the object.

There is an angle between two edges connected to the same vertex, which is fixed for rigid linking and variable for articulated linking.

As discussed above, the nature structure of the object can be formed through its decomposition. Different shapes or contours of the object are the result of movement in the edges and articulated vertices, causing the body posture to change or appear from a different angle. However, the connection relationship between edges and vertices and the lengths of the edges do not change.

2 Decomposition of the human body structure

2.1 Body contour in an image

The body contour is dependent on the relative positions of different parts of the body. For example, the head direction, relative position of the torso and limbs, spatial position of the limbs, and different clothing types all affect the body contour. In general, clothing only affects the body contour in terms of the smoothness of the curves. Based on the affine principle, two-dimensional (2D) images of the body contour are the result of projecting the edge of the body shape under different vision angles.

Consider plane S in the object’s coordinate system. Normal direction n with respect to S is the gaze direction of the vision angle, and the 2D image is formed by the vertical projection of the 3D object. This image is called vision angle projection (VAP) (see Fig.2).

Fig.2 VAP of a 3D object

In fact, S is a plane in the visual range, and could be a photogram, i.e., a frame in a video or an image under some vision angle in machine vision. Clearly, if the object’s nature structure can be described by 3D graphics, then the VAP is a sub-graphic of the 3D graphic Gp, i.e., Gp?G.

In image and graphic processing, VAP objects are commonly encountered. Therefore, target recognition can be achieved by judging whether a given sub-graph belongs to the object’s nature structure graphic. Moreover, the object’s nature structure can be determined by different sub-graph. Additionally, the sub-graph can be used for object silhouette processing, and so on.

In terms of the VAP concept, the human contour in an image is a VAP of the human body under some vision angle. The human contour reflects the spatial distribution of the nature structure, and part or all of the human nature structure (HNS) can be obtained from the human contour supplied by the image.

2.2 Basic units of the human body

Based on the nature structure features and the image feature of the human body contour, the body can be divided into different units, as shown in Fig.3.

Fig.3 shows basic units including head, torso, and limbs. In Fig.4, each basic unit is replaced by a rigid edge, allowing HNS to be constructed as a series of connected edges and vertices.

Head: The geometry of the head does not change as the movement and shape of the body varies. The head may produce different contours in the 2D image formed by VAP. Therefore, the head is a basic unit and is replaced with an edge in the HNS.

Torso: Although the torso has certain bending functions, it is also considered as a unit of certain rigidity for simplified analysis. Thus, the torso is a rigid edge in the HNS.

Fig.3 Units of the human contour

Fig.4 Range of angles among basic units

Limbs: From the skeletal features of the human body, the upper arms, forearms, thighs, and calves all have rigid features. Thus, they can be separated into four basic units. The upper arm and forearm are articulated by one vertex, and the thigh and calf are articulated by another vertex.

Based on the above discussion, the graphic is the HNS constructed with the center line of the units and articulated vertices.

3 Graph theory model of human nature structure

3.1 Complete graph theory model

A full graph theory model requires each terminal of an edge to have a connection with a vertex, as shown in Fig.5.

Fig.5 shows a spatial structure with 11 vertices and 10 edges, in which each edge denotes a basic unit and each vertex denotes a link relationship between two edges. Connecting all basic units together with articulated vertices forms an HNS.

Fig.5 GMH of human nature structure

The GMH shown in Fig.5 can be considered as a graphic G=G(V, E, θ) including the following mapping relationships:

The articulated relationships of the vertices and edges are fixed.

There is an angle between any two edges.

The mapping relationships show that G=G(V, E, θ), representing the HNS, is not a dual graph theory model, but is a ternary graphic in which the mapping relationships must be taken into account. From an image and graphics processing perspective, the body shape is dependent on the mapping value of G=G(V, E, θ).

This proves that the full graphic G=G(V, E, θ) of the HNS has the following characteristics:

Vertices denote the linkages between units, the edges linked to a vertex are fixed, and the link relationship is not related to the serial number of the edges and vertices.

For a pair of edges with a common vertex, the angle between two edges varies in the range 0θiθimax.

There are 11 vertices and 10 edges; 5 of the 11 vertices are only connected to one edge.

G is a tree structure that has no loops, meaning one cannot return to the start vertex via other vertices and edges.

From the body structure and movement features, the smallest and largest values of θ are as follows:

Angle between head and torso: -30°θ170°

Angle between upper arm and head: 0°θ2=θ3180°

Angle between upper arm and forearm: 0°θ4=θ7180°

Angle between upper arm and torso: 0°θ5=θ6180°

Angle between thigh and torso: -30°θ8=θ9180°

Angle between thigh and calf: 0°θ10=θ11180° Angle between two thighs: 0°θ12180°

Angle between two upper arms: 0°θ13360°

It is assumed that the edge is the axis of a certain cube, e.g., the axis of a cuboid, a 3D human body model can be built from the GMH, as shown in Fig.6. Fig.6(a) is the 3D human body model formed using GMH and cylinders, and Fig.6(b) is the 2D image of the 3D human body formed with a special VAP.

Fig.6 shows that the nature structure supplies 3D characteristics as well as body contours in a different VAP.

Fig.6 Human body model

3.2 Incomplete graph theory model

An edge that links to only one vertex is called a free edge. After removing some vertices that only connected to one edge from the model in Fig.5, five free edges appear, as shown in Fig.7.

Fig.7 Incomplete GMH

In HNS, the vertices denote articulated connections. A vertex connected with only one edge is a useless vertex that can be removed from GMH. In Fig.7, five edges have one unconnected terminal. Terminals that do not link with a vertex are called free terminals, and Fig.7 has the same function as Fig.5.

Compared with Fig.5, the incomplete graph theory model G=G(V, E, θ) has the following characteristics:

Vertices denote the links among the units, the edges linking to a vertex are fixed, and the link relationship is not related to the serial number of the edges and vertices.

For a pair of edges with a common vertex, the angle varies in the range 0≤θi≤θimax.

There are 6 vertices and 10 edges, and 5 of the 10 edges connect with only one vertex.

G is a tree structure that has no loops, meaning one cannot return to the start vertex via other vertices and edges.

From Fig.5 and Fig.7, the free terminal can be placed at any spatial position and cannot articulate any vertices. This is the basic characteristic of human limbs.

4 Analytic expression of GMH

The mapping of GMH can be described by the connection of vertices and edges and the angle between two edges. From the mapping relationships, an analytic expression for GMH (shown in Fig. 5 and Fig. 7) can be obtained. This analytic expression is the basis of image/graphics processing.

4.1 Basic concepts of graphic analysis

Graphic analysis involves building an adjacency matrix, an associated matrix, and the matrices related to the mapping relationship.

4.1.1 Adjacency matrix and associated matrix

In a graph theory model, vertices viand vjconnected to different ends of one edge are called adjacent vertices. The adjacency matrix denotes the adjacency relationship between vertices. When two vertices are adjacent, there is an edge connecting the two vertices, i.e., xij=(vi, vj), where vi, vj∈V, xij∈E, and V, E are the sets of vertices and edges, respectively. For a graph with n vertices and m edges, the adjacency matrix is an n×n matrix in which element values of 1 denote that there is an edge between the two vertices and element values of 0 denote that there is no edge.

In a graph theory model, the relationships among the vertices and edges can be described using an associated matrix. An edge and a vertex are said to be associated when the edge connects with the vertex. For a graph with n vertices and m edges, the associated matrix is an n×m matrix in which an element value of 1 denotes that that vertex is associated with that edge and an element value of 0 denotes that the vertex is not associated with the edge. The number of edges connected with one vertex is called the degree of the vertex, di.

The adjacency matrix and associated matrix describe the link relationship between vertices and edges. However, there are no restricted conditions for the connection relationship, i.e., there are no limitations on the spatial distribution of vertices and edges.

4.1.2 Restriction for mapping

Mapping relationships are ignored in general graph theory and do not affect the analysis and solution of certain problems, e.g., the selection of optimum paths. However, in machine vision, the original images provide the contour of the body in a certain posture, and this contour must be analyzed and processed to construct the GMH. Therefore, both the distribution relationship and the angle between two edges have to be considered to determine whether the mapping restrictions are satisfied. Furthermore, changes in the distribution of vertices and edges denote different body postures. Therefore, the concepts of edge length and angles have to be established when creating a GMH. Combining these analysis concepts with the characteristic structures of the adjacency matrix and associated matrix gives the mapping restriction of the GMH.

From Fig.5 and Fig.7:

The edges denote basic units and are connected with two vertices (Fig.5) or only one vertex.

There is only one vertex with di=4, there is only one vertex with dj=3, and only one edge connects these two vertices. This edge denotes the torso.

The vertex with di=4 denotes the articulated point of the head, torso, and two upper arms.

The vertex with dj=3 denotes the articulated point of the torso and two thighs.

For all adjacent edges that have a common vertex with other edges, the angle can vary over a certain range.

These are the mapping restriction relations of GMH.

4.2 Adjacency matrix of GMH

From Fig.5, the adjacency matrix of GMH is

(1)

In A, the elements aijdenote the link relations between viand vj, and

(2)

In the same manner, the adjacency matrix for Fig.7 is

(3)

Eq.(3) is the result of deleting row 1 and column 1, row 4 and column 4, row 6 and column 6, row 9 and column 9, row 11 and column 11 in Eq.(1).

The characteristics of the adjacency matrix of the GMH are as follows:

n×n matrix, where n is the number of vertices; n=11 for the complete GMH and n=6 for the incomplete GMH.

All the diagonal elements are zero.

A=AT.

There is a special edge x=(vi, vj), where vilinks four edges and vjlinks three edges.

A has nothing to do with the order number of the vertices and edges.

Changes in the angle between two edges with a common vertex do not affect A.

The adjacency matrix has nothing to do with the order number of the vertices and edges, that means that, regardless of the sequence number of the vertices, Eqs(1) and (3) for A can always be obtained through permutations of rows and columns of the adjacency matrix. For example, exchanging the order number of v1and v2in Fig.7, the adjacency matrix is

From the expression above, exchanging the first and second rows and then exchanging the first and second columns gives Eq.(3). Additionally, if exchanging the order number of e1and e2, Eq.(3) can be obtained by executing permutations of rows and columns in the new adjacency matrix.

The degree of each vertex is given by the adjacency matrix. The sum of each row or column is the degree of the vertex represented by the number of the row or column. In Fig.1, for example, the sum of the second row or second column is 4, which means that v2links with four edges. Rows/columns 1, 4, 6, 9, and 11 all sum to 1, meaning that vertices v1, v4, v6, v9, v11link to only one edge. A vertex linked to only one edge is called a single edge vertex. Moreover, in Fig.3, rows 3～6 and columns 3～6 all sum to 1, meaning that there are four edges linking to only one vertex. In a GMH, single edge vertices have the same function as free terminals. Therefore, the adjacency matrix of an incomplete GMH can be obtained from the adjacency matrix of a complete GMH by ignoring the single edge vertices.

4.3 Associated matrix of GMH

According to the associated concept of vertices and edges in graph theory, let the number of rows in the matrix represent the order of the vertices and the number of columns represent the order of the edges. The associated matrix of Fig.5 is then

(4)

where

(5)

The associated matrix for Fig.7 is

(6)

Eq.(6) can be obtained from Eq.(4) by deleting rows 1, 4, 6, 9, and 11.

The characteristics of the associated matrix of the GMH are as follows:

n×10 matrix, where n is the number of vertices and 10 is the number of edges; n=11 for the complete GMH and n=6 for the incomplete GMH.

The sum along each row is the number of edges linking to this vertex.

The sum along each column is the number of vertices linking these edges.

There is a vertex di=4 and a vertex dj=3.

B has nothing to do with the order number of the vertices and edges.

B is unaffected by the angle between the two edges linking a common vertex.

As with the adjacency matrix, the associated matrix only describes the associated relationship of the vertices and edges, and does not uniquely identify the spatial distribution state of the HNS.

The adjacency matrix and associated matrix of GMH provide connection information about the vertices and edges. The adjacency matrix describes the adjacency relationships among vertices and the associated matrix gives the link relationships of vertices and edges. Therefore, the matrices denote the relationships among the vertices and edges, but do not describe differences in body shape. For example, three graphics have the same A and B in Fig.5 and Fig.7.

4.4 Angle matrix of the GMH

To describe the spatial state of the body, one must consider the angle between two edges connected to a common vertex as well as information about the length and percentage of the edges.

With respect to the common plane of a vertex and its associated edges, the angle is the smaller of the angles between the two edges, as shown in Fig.8(a). There are two angles between the two edges linking a common vertex in Fig.8, where the solid line denotes the smaller angle θ and the dotted line denotes the larger angle α, α+θ=2π. Moreover, θ=0 denotes the parallel edges. In the case of the HNS, the orientation of the angles cannot be considered, i.e., the angles are always positive.

Fig.8 Angle between two edges of the same vertex

For G=G(V, E, θ) consisting of n vertices and m edges, the angle matrix is

(7)

This is a square matrix of size m×m in which θii=0. If there is no common vertex between two edges and/or the two edges are parallel, then θij=0.

From Fig.5, the angle matrix of GMH is the square 10×10 matrix (m=10)

(8)

Eq.(8) is also the angle matrix for Fig.7, because these representations have the same associated relationship among the vertices and edges. The number of edges and the number of associated relationships are the same, so the angle matrixes are equal and the single edge vertices do not affect the angle matrix.

From Eq.(8), it is apparent that the angle matrix of the GMH is a symmetric matrix, θ=θT, which shows that the adjacency matrix and associated matrix can be simplified by ignoring the single edge vertices. Such a simplification does not affect the angle matrix; therefore, the analysis of the body posture will not be affected.

Considering Fig.5:

(9)

The values of the diagonal elements in Eq.(9) indicate that each edge is linked to two vertices. Element values equal to 1 denote that two edges connect to the same vertex. Element values of 1 also denote that there is an angle between the two corresponding edges.

From Fig.7:

(10)

Some of the diagonal elements in Eq.(10) have a value of 1, indicating edges that are only associated with one vertex. Again, element values of 1 imply that there is an angle between the corresponding edges.

4.5 Edge length vector of GMH

In Fig.5 and Fig.7, let the edge length vector be

L=(l1,…,l10)T

(11)

For sake of convenience, let

Consider

and construct the following diagonal matrix:

From the above, the liprojection at ljis calculated as follows:

(12)

Moreover, the sum of the mutual projection of both edges of the same vertex is

(13)

where ljcosθijis the ejprojection at ei, j, i=1,…,10.

Moreover,

(14)

From the symmetric character of the angle matrix, there is

cosΘ·L=(LT·cosΘ)T

(15)

5 A simple application

GMH described in previous sections can be used to detect the human body in images and/or the pose design in graph processing.

Convolutional neural networks (CNNs)[9]and multiple-oriented 2D elliptical filters[10]are good methods for human detection in images. Both methods identify human body shapes in an image using complex computations, but find accurate identification difficult. In Ref.[10], for example, the head-shoulder shape obtained from an image has to be matched with a preconfigured head-shoulder silhouette, which is difficult because of the different shapes. In contrast, once the contour has been determined, a GMH can be established and the conformity analysis can be done using the standard matrixes of GMH, such as the adjacency matrix, association matrix, angle matrix, and edge length vector. Moreover, the angle matrix can be used to determine the body posture.

As a simple example for modeling the HNS, Fig.9 shows the processing result of a video image and infrared image, both taken from the same perspective. To further determine whether this contour represents the human body, the GMH is established and analyzed in accordance with Fig.9(c), which is a binary image.

(a) Frame from a video image, (b) Contour according to infrared image, (c) Combined result of (a) and (b) Fig.9 Human body shape extraction

Fig.10 Establish local rectangular boxes

From this binary image, a GMH can be established gradually as a series of rectangular boxes (Fig.10). The specific steps are as follows:

Step 1 Establish the human body outline rectangular box (HBORB). For pixels with values of 1 along the x and y directions, the maximum and minimum values of the pixel’s coordinates are first identified and a rectangle is created, as shown in Fig.9(c).

Step 2 Establish the head part rectangular box (HPRB). From the top down alongthe y-axis for each row (x-axis), coordinate (xi, yi) of pixels with a value of 1 that adjoin pixels with a value of 0 is searched to determine the maximum, minimum, and mean of the x-coordinate for each row, and stop the search when y=Y/5 or the difference between the minimum and maximum values of x in a row is 2X/3. After this search, Y is the top border of the HPRB, minimum y is the bottom border of the HPRB, the mean of minimum x is the left border of HPRB, and the mean of the maximum x is the right border of HPRB. The box is shown in Fig.10(a).

Step 3 Establish the torso part rectangular box (TPRB). From the bottom border of HPRB, the x border is searched along the direction of the y-axis to determine TPRB in a similar way as for HPRB. Note that if the bottom border has not been determined by the time 0.4Y is reached, then 0.4Y is designated as the bottom border of TPRB. The box is shown in Fig.10(a).

Step 4 Establish the lower limbs part rectangular box (LLPRB). In a similar way as for the TPRB, LLPRB can be formed. Note that the search should stop at y=0. The box is shown in Fig.10(a).

Step 5 Establish the upper arm part rectangular box (UAPRB). Beginning at the top of the TPRB, pixels are searched from the left border along the x direction. If there is a pixel value of 1 adjoining a pixel value of 0, then this is the right border of the left UAPRB; if no such pixel has been identified by x=X/2,then set x=X/3 as the right border of the left UAPR. The height of the left UAPRB is the height of the TPRB. The right UAPRB is created in the same way. The box is shown in Fig.10(b).

Step 6 Establish the legs part rectangular box (LPRB). Beginning at the top of the LLPRB downwards to 2/3 the height of the LLPRB, the border of the human contour is searched, and the maximum x and minimum x are used as borders of the left LPRB. The height of the LPRB is the same as that of the LLPRB, as shown in Fig.10(c). The right LPRB can be established in a similar way, as shown in Fig.10(d).

Step 7 Determine edge e1and vertex v1from the HPRB. Using the HPRB, the straight line from the center point of the top to the center point of the bottom is edge e1, and the central point of the bottom is vertex v1.

Step 8 Determine edge e2and vertex v2from the TPRB. Using the TPRB, the straight line from v1to the center of the bottom border of the TPRB is edge e2, and the center of the bottom border of the TPRB is vertex v2.

Step 9 Determine edges e3, e4, e5, e6and vertices v3, v4from the UAPRB. From the left upper arm, if the bottom extends beyond the base of the TPRB or enters the LLPRB, then v3is the intersection point of the center line of the left UAPRB and the horizontal line at 0.2 times the height of the TPRB upwards; if the y coordinate of the left UAPRB is higher than 0.5 times the height of the left UAPRB, then v3is the center point of the left UAPRB. The straight line from v3to v2gives edge e3, and the straight line from v3to the center of the top of the LLPRB gives e4. In a similar way, the right upper arm can be used to determine vertex v4and edges e5, e6.

Step 10 Determine edges e7, e8, e9, e10and vertexes v5, v6from the LLPRB. The midpoint of the vertical center line of the left LPRB is vertex v5, and the point at the center of the top border of the right LPRB is vertex v6. The straight line from v5to v2gives edge e7, and the straight line from v6to v2gives edge e9. Finally, the straight line from v5to the center of the bottom of the left LPRB and the straight line from v6to the center of the bottom of the right LPRB give edges e8and e10, respectively.

By the above procedure, the GMH can be recovered from the body contour, as shown in Fig.11.

Fig.11 GMH from the body contour

6 Conclusion

The ability to identify the human body is an important application in machine vision and image/graphics processing. Determining how to build a relevant model is a key process in body recognition. A model built using the human nature structure has been described. The proposed approach uses a graph theory model of the human nature structure, referred to as the GMH. As the human nature structure is not affected by body posture or shape, the resulting GMH is not related to the body posture or shape. Unlike general graph theory analysis, the GMH must consider certain mapping restrictions and can also be used for AMDO processing and represented analytically by the adjacency matrix, associated matrix, angle matrix, and the edge length vector, each of which incorporates the mapping restriction conditions. The computational complexity of machine vision and/or image/graphics processing applications could be reduced by GMH.

[ 1] Ugo M. On the optimal detection of curves in noisy pictures. Communications of the ACM， 1971, 14(5): 335-345

[ 2] Wang M, Lai Y K, Liang Y, et al. BiggerPicture: data-driven image extrapolation using graph matching. ACM Transactions on Graphics, 2014, 33(6):173:1-13

[ 3] Jordaan I, Marshall L. Edit distance-based digraph similarity. In: Proceedings of the 2015 Annual Research Conference on South African Institute of Computer Scientists & Information Technologists, Stellenbosch, South African, 2015. 23

[ 4] Huang C, Han T X He Z, et al. Constellational contour parsing for deformable object detection. Journal of Visual Communication and Image Representation, 2016, 38(C): 540-549

[ 5] Ramoser H, Schlogl T, Beleznai C, et al. Shape-based detection of humans for video surveillance applications. In: Proceedings of the International Conference on Image Processing, Barcelona, Spain, 2003, 2: III-1013-1016

[ 6] Jim P N. Survey on model-based manipulation planning of deformable objects. Robotics and Computer-Integrated Manufacturing, 2012,28(2):154-163

[ 7] Artner N M, Ion A, Kropatsch Wa, et al. Reprint of: multi-scale 2D tracking of articulated objects using hierarchical spring systems. Pattern Recognition, 2011, 44(9):1969-1979

[ 8] Paoli C D, Singh K. Secondskin sketch-based construction of layered 3d models. ACM Transactions on Graphics, 2015, 34(4):126: 1-10

[ 9] Ruochen W, Zhe X. A pedestrian and vehicle rapid identification model based on convolutional neural network. In: Proceedings of the International Conference on Internet Multimedia Computing & Service, Zhangjiajie, China, 2015. 1-4

[10] Cho S H, Kim D, Kim T, et al. Pose robust human detection using multiple oriented 2d elliptical filters. In: Proceedings of the ACM Workshop on Vision Networks for Behavior Analysis, Vancouver, Canada, 2008. 9-16

[11] Marcard T V, Pons-Moll A, Rosenhahn B. Human Pose Estimation from Video and IMUs. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2016, 38(8): 1533-1547

[12] Huang C H, Boyer E, Navab N, et al. Human shape and posetracking using keyframes. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), Columbus, USA, 2014. 3446-3453

[13] Loper M, Mahmood N, Romero J, et al. SMPL: a skinned multi-person linear model. ACM Transactions on Graphics, 2015, 34(6): 248:1-248:16

[14] Chen L, Wei H, Ferryman J. A survey of human motion analysisusing depth imagery. Pattern Recognition Letters, 2013, 34(15): 1995-2006

[15] Ionescu C, Papava D, Olaru V, et al. Human3.6m: large scale datasets and predictive methods for 3d human sensingin natural environments. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2014, 36(7):1325-1339

Liu Jia, born in 1978. She is pursuing a doctorate in School of Computer Science and Engineering, Beihang University. She received her B.S. and M.S. degrees from Yanshan University in 1999 and 2003 respectively. Her research interests include image processing and video processing.

10.3772/j.issn.1006-6748.2017.04.002

①Supported by the National Natural Science Foundation of China (No. 71373023, 61372148, 61571045), Beijing Advanced Innovation Center for Imaging Technology (No. BAICIT-2016002), the National Key Technology R&D Program (No. 2014BAK08B02, 2015BAH55F03) and the Importation and Development of High-Caliber Talents Project of Beijing Municipal Institutions (No. CIT&TCD201504039).

②To whom correspondence should be addressed. E-mail: xxtliujia@buu.edu.cn

on Jan. 15， 2017**