Method for object segmentation in videos tagged with semantic labels

[0001] This application claims priority to the Chinese Patent Application No. 201510368762.1, filed on Jun. 29, 2015, which is incorporated herein by reference in its entirety.

[0002] The present invention relates to the field of computer technology and, more particularly, to a method for object segmentation in videos tagged with semantic labels.

[0003] Video object segmentation is a technique for detecting and segmenting an object region of a given semantic category from the video, which is a fundamental technique in the field of computer vision and multimedia analysis, and plays an important role in application aspects such as object retrieval, video editing and video-based three-dimensional modeling. A weakly-labeled method for segmenting video objects refers to a method in which only a semantic category of the video object is labeled by a user, and an object belonging to a category specified by the user is detected and segmented with an algorithm. Considering that most of the Internet videos usually have a user flag, and a semantic tag relevant to the content, therefore, the weakly-labeled method for segmenting video objects is of great importance in the application of analyzing and processing ever-increasing internet video data.

[0004] Since a weakly-labeled video object has a feature that, it is only known about that there is an object belonging to a specified semantic category in the input video, but the specific location information is still unknown. Currently, the most widely adopted solution is based on weakly supervised learning, which particularly is: firstly, positive videos and negative videos are collected, wherein, the positive videos contain the objects from a pre-specified semantic category while the negative videos do not contain any objects from this category; secondly, each video is segmented into spatio-temporal segments, and a semantic category of each spatio-temporal segment is determined according to the association between the positive videos and the negative videos; finally, the positive videos and the negative videos are all co-segmented with a multi-graph optimization model to obtain a segmentation result, that is, the objects belonging to the specified semantic category in the input video.

[0005] The above method for segmenting video objects based on weakly-supervised learning can effectively solve the problem of segmenting a video object under a weakly-labeled condition in some cases, however, since that a weakly-labeled video lacks location information of an object of a specific semantic category, which makes the classification of the positive sample video and the negative sample video inaccurate, and thus a wrong result of video segmentation during segmentation is most likely to occur, in addition, multiple videos are simultaneously needed as the input for segmentation, which renders these methods not applicable for segmenting a semantic category object of a single input video.

[0006] The present invention provides a method for object segmentation in videos tagged with semantic labels, to assist segmentation of an object of a given semantic category in a video by means of an object bounding box detector and an object contour detector, so that the problem that the existing method for segmenting video objects is inaccurate and not applicable to segmenting a semantic category object of a single input video can be solved.

[0007] According to the present invention, there is provided a method for object segmentation in videos tagged with semantic labels, including:

[0008] detecting each frame of the video sequence with an object bounding box detector of the given semantic category, and an object contour detector and obtaining a candidate object bounding box set and a candidate object contour set for each frame of the input video;

[0009] building a joint assignment model for the candidate object bounding box set and the candidate object contour set, and solve this model to obtain the initial object segment sequence, wherein at least one of the initial segment sequences contains the object;

[0010] processing the initial object segment sequence, to estimate a probability distribution of the object shapes in the input video; and

[0011] optimizing the initial object segment sequence with a variant of graph cut algorithm that integrates the shape probability distribution of the object, to obtain the optimal object segment sequence corresponding to the object in the input video.

[0012] The present invention provides a method for object segmentation in videos tagged with semantic labels, to assist segmentation of an object of a given semantic category in an input video by applying an object bounding box detector and an object contour detector, so that the problem of ambiguous video segment classification under a weakly-supervised learning condition can be avoided, further, the method for object segmentation in videos tagged with semantic labels in the present invention is applicable to segmenting an object of a given semantic category of a single input video, not having to process multiple videos at the same time, and thus has a better applicability.

[0019] In order to make the objects, technical solutions, and advantages of the embodiments of the present invention clearer, the technical solutions in the embodiments of the present invention are hereinafter described clearly and completely with reference to the accompanying drawings in the embodiments of the present invention. Obviously, the embodiments described here are part of the embodiments of the present invention but not all of the embodiments. Based on the embodiments of the present invention, other embodiments obtained by those skilled in the art without creative efforts all fall in the scope of the present invention.

[0020] Video object segmentation is a technique for detecting and segmenting an object region of a given semantic category from the video, which is a fundamental technique in the field of computer vision and multimedia analysis, and plays an important role in application aspects such as object retrieval, video editing and video-based three-dimensional modeling.

[0021] Currently, depending on different user input conditions, the existing method for segmenting semantic video objects is mainly divided into three general categories: a label-free method for segmenting video objects, a strongly-labeled method for segmenting video objects, and a weakly-labeled method for segmenting video objects. In the label-free method for segmenting video objects, an algorithm can automatically segment semantic objects from a video, which does not need user interaction; in the strongly-labeled method for segmenting video objects, the user needs to manually segment objects in several key frames of the input video, an algorithm can propagate the segmentation result on the remaining frames, so that the semantic object can be segmented from the whole input video; in the weakly-labeled method for segmenting video objects, the user only needs to label a semantic category to which object in the input video belongs to, an algorithm is used to detect and segment objects of the specified semantic category from the input video. Considering that most of the Internet videos usually have semantic tags annotated by users relevant to the content, therefore, the weakly-labeled method for segmenting video objects is of great importance in the application of analyzing and processing ever-increasing internet video data.

[0022] Under a weakly-labeled condition, it is only known that there is an object belonging to a specified semantic category in the input video, while location information of the object is still unknown. In order to solve this problem, a vision model based on weakly-supervised learning is mainly adopted for solution in the relevant research field, which particularly is: in the framework of weakly-supervised learning, positive videos and negative videos are firstly collected, wherein, the positive videos contain objects from a specific semantic category while the negative videos do not contain any objects from that category; secondly, each video is segmented into spatio-temporal segments (Spatio-temporal Segment), and a semantic category of each spatio-temporal segment is solved according to the visual similarity between the segments in the positive and negative videos; for example, Hartmann learns a segment-based classifier with a linear support vector machine (Linear SVM) and multi-instance boosting (MI-Boosting), and detects an object region of a given semantic category in the input video; Tang et al uses a negative mining method, that is to compare each segment of the positive videos with all the segments of the negative videos, score each segment of all the positive videos according to a neighbor relationship between the positive videos and the negative videos, and judge that the segment with a higher score belongs to a specified semantic category; Xiao et al propose to learn a distance measure between the positive videos and the negative videos with a weakly-supervised Hash algorithm, and give a probability that a video segment belongs to the given semantic category with a K-neighbor classifying method; finally, the positive videos and the negative videos are all co-segmented with a multi-graph optimization model to obtain a segmentation result, that is, the objects belonging to the specified semantic category in the input video.

[0023] The above method for segmenting video objects based on learning can effectively solve the problem of segmenting a video object under a weakly-labeled condition in some case, however, it still has two disadvantages as follows. Firstly, since a weakly-labeled video lacks location information of an object of a specific semantic category, therefore, a category to which a sample segment belongs can be speculated by comparing the appearance of the segment, which makes the classification of the sample segment always inaccurate (for example, two segments with similar appearances may either belong to the same semantic category or belong to different categories), thus makes the classification of the positive sample video and the negative sample video inaccurate. A wrong result of video segmentation is most likely to occur due to such fuzzy sample classification. Secondly, multiple videos are needed as the input for segmentation in the method for segmenting video objects based on weakly-supervised learning, which is not applicable for segmenting object of a single input video.

[0024] Considering that the object detector has many successful application cases in the aspect of image semantic segmentation, for example, Xia et al achieves a highly-efficient image semantic segmentation method with an object detector, without the need of a complicated training process and a pixel-by-pixel accurately-labeled image training set. Therefore, in terms of an input video with a semantic category label, in order to solve the problem existed in the method for segmenting video objects based on weakly-supervised learning, the present invention proposes a method for object segmentation in videos tagged with semantic labels, the method firstly estimates a rough location of the video object with an object detector corresponding to a given semantic category, and on the basis of that, completes segmentation of objects belonging to the semantic category.

[0025] FIG. 1 is a flow chart of the method for object segmentation in videos tagged with semantic labels according to Embodiment 1 of the present invention, as shown in FIG. 1, the method includes:

[0026] Step 101, Detecting each frame of an input video sequence with an object bounding box detector for a semantic category, and an object contour detector according to a semantic category label to which an object belongs, and obtaining a candidate object bounding box set and a candidate object contour set for each frame of the input video;

[0027] Since there may be multiple objects belonging to different semantic categories in the input video, and under a weakly-labeled condition, it is only known that there is an object belonging to a specified semantic category in the input video, while location information of the object is still unknown, therefore, the present invention firstly estimates a rough location of the video object of a specified semantic category with an object detector, that is, detect each frame of the input video with an object bounding box detector first, obtain a candidate object bounding box set for each frame of the input video, and on the basis of the candidate object bounding box set, detect each frame of the input video with an object contour detector, obtain a candidate object contour set for each video frame.

[0028] Step 102, Building a joint assignment model containing the candidate object bounding box set and the candidate object contour set, and solve it to obtain initial object segmentation corresponding to the object in the input video;

[0029] wherein, at least one of the initial segment sequences contains the object.

[0030] Since all the existing object detectors (object bounding box detectors and object contour detectors) are obtained by training on static images therefore, if applied in a video frame directly, the factors such as encoding compression, object occlusion and camera movement will cause that the detected candidate object bounding box set and candidate object contour set are in disorder and inaccurate.

[0031] To this end, by using a joint assignment model the present invention selects the right candidate object bounding boxes and candidate object contours from the noisy candidate object bounding box set and candidate object contour set The selected object contours correspond to the initial object segment sequence of a given semantic category label in the input video.

[0032] Step 103, Processing the initial object segment sequence, to estimate a shape probability distribution of the object in the input video;

[0033] As for the above initial object segmentation, the present invention proposes a method for estimating a shape probability distribution of the object which encodes spatio-temporal consistency, the method estimates the shape probability distribution of the object of a given semantic category in the input video, by analyzing statistical information of many candidate segment sequences that spatially overlapped with the above initial object segment sequence.

[0034] Step 104, Optimizing each initial object sequence with a graph cut algorithm in combination with the shape probability distribution of the object, to obtain the optimal object segmentation results in the input video.

[0035] Optimizing each sequence containing the object in the initial segmenting sequence in sequence with a graph cut algorithm in combination with the shape probability distribution of the object of a given semantic category solved in Step 103, to obtain an optimal segmenting sequence corresponding to the object in the input video.

[0036] Embodiments of the present invention provide a method for object segmentation in videos tagged with semantic labels, to assist segmentation of an object of a given semantic category in an input video by applying an object bounding box detector and an object contour detector, so that the problem of a fuzzy sample video classification under a weakly-supervised learning condition can be avoided, further, the method for object segmentation in videos tagged with semantic labels according to the present invention is applicable for segmenting an object of a given semantic category of a single input video, without the need of processing multiple videos at the same time, and thus shows better applicability.

[0037] FIG. 2 is a flow chart of the method for segmenting video objects tagged with semantic labels according to Embodiment 2 of the present invention. Embodiment 2 of the present invention is to further discuss Step 101 on the basis of the technical solution of Embodiment 1. As shown in FIG. 2, the method for segmenting video objects tagged with semantic labels according to Embodiment 2 of the present invention, a specific implementation of Step 101 includes steps as follows:

[0038] Step 201, Detecting each frame of the input video with the object bounding box detector on at least two thresholds according to the semantic category label to which the object belongs, to calculate a comprehensive performance value of the detection result corresponding to the at least two thresholds, and take a threshold corresponding to a maximum comprehensive performance value selected form the comprehensive performance values as an optimal threshold of the object bounding box detector;

[0039] Since the user manually labels a given semantic category of an object on a training set of each frame of the input video under a weakly-labeled condition, therefore, comprehensive performance values with different magnitudes can be obtained when each frame of the input video is detected on different thresholds with an object bounding box detector, and a threshold corresponding to a maximum comprehensive performance value is selected as an optimal threshold of the object bounding box detector.

[0040] It should be noted that, the detection performance is measured by F-Score value, the F-Score value is also called F-Measure, which is a common evaluation criterion in the IR (information retrieval) field, the bigger F-Score is, the better the detection performance is. Therefore, the threshold corresponding to a maximum F-Score can be taken as the optimal threshold of the object bounding box detector.

[0041] Step 202, Detecting each frame of the input video with the object bounding box detector on the optimal threshold according to the semantic category label to which the object belongs, to obtain an object bounding box set for each frame of the input video, wherein, the final object bounding box set is the union of the object bounding box set for each frame of the input video and a dummy bounding box;

[0042] For example, if detect the t-th frame of the input frame with an object bounding box detector, an object bounding box set for the t-th frame is obtained, which is denoted as D_t⁺, a candidate object bounding box set for the t-th frame contains D_t⁺ and a dummy bounding box D_φ, marked as D_t=D_t⁺+∪{D_φ}. Particularly, the dummy bounding box D_φ is used to indicate an ideal area of the bounding box of the object.

[0043] It should be noted that, the existence of the dummy bounding box has a significance that, when the object bounding box detector fails to detect a certain frame, any detected bounding box in the obtained object bounding box set cannot locate on the object of the input video, if an dummy bounding box is not introduced, objects on the frame cannot be segmented accurately in the subsequent processing, that is, if all the object bounding box sets cannot locate on the object of the input video accurately, then, when the joint assignment model is built subsequently, the algorithm can only select a wrong detection for this frame as part of the solution, which will make the result inaccurate. With the dummy bounding box included, the algorithm can possibly choose the dummy bounding box instead of any of the others, which will not significantly influence the results.

[0044] However, the above problem can be solved to a certain extent with an assumption of the empty bounding box set, when all the object bounding box sets cannot locate on the object of the input video accurately, the algorithm of solving the initial segmenting sequence corresponding to the object can select an empty bounding box set first, and then select a better initial segmenting sequence.

[0045] It should be noted that, the joint allocation model built subsequently containing the candidate object bounding box set and the candidate object contour set joins the object bounding box set with the initial segmenting sequence, and allocation between the object bounding box set and the initial segmenting sequence is interdependent.

[0046] Step 203, Detecting each frame of the input video with an object contour detector based on (Constrained Parametric Min-Cuts, CPMC) after obtaining the candidate object bounding box set for each frame of the input video, to obtain a candidate object contour set for each frame of the input video.

[0047] Particularly, after knowing the candidate object bounding box set for the t-th frame of the input video, on the basis of the candidate object bounding box set, a heat map is computed by counting the number of detections on each pixel location in the frame. In order to improve the detection accuracy of the object contour detector, in the seed placement stage of constrained parametric min-cuts algorithm, additional foreground seeds are placed on the pixel locations with high detection hits. The detected object contours are denoted as S_t, for the t-th frame of the input video.

[0048] Before detecting each frame of the input video with the object contour detector, it is necessary to select seed points of the object contour detector, and the seed point indicates an optimal pixel region to be detected by the object contour detector.

[0049] In order to improve the detection accuracy of the object contour detector, additional foreground seed points are added as follows: detect the t-th frame of the input video with different object bounding box detectors having a lower threshold, to obtain a series of candidate object bounding boxes, and calculate times of each object pixel being covered by the candidate object bounding box, to obtain a heat map of detection results, that is, to obtain a pixel region of each object pixel covered by the candidate object bounding box; select a local maxima of the heat map as the additional foreground seed point, that is, the local maxima of the heat map is the optimal pixel region to be detected.

[0050] In the method for object segmentation in videos tagged with semantic labels according to Embodiment 2 of the present invention, select the optimal threshold of the object bounding box detector, so that the object bounding box detector detects each frame of the input video on the optimal threshold, to obtain an object bounding box set for each frame of the input video, and then detect each frame of the input video with an object contour detector based on constrained parametric min-cuts, to obtain a candidate object contour set for each frame of the input video, thus roughly determining a location of the object of a given semantic category, and improving accuracy of the subsequent video object segmentation.

[0051] FIG. 3 is a flow chart of the method for object segmentation in videos tagged with semantic labels according to Embodiment 3 of the present invention. Embodiment 3 of the present invention is to further discuss Step 102 on the basis of the technical solution of Embodiment 1. As shown in FIG. 3, the method for object segmentation in videos tagged with semantic labels according to Embodiment 3 of the present invention, the Step 102, that is, building a joint assignment model containing the candidate object bounding box set and the candidate object contour set, to solve an initial segmenting sequence corresponding to the object in the input video, particularly includes:

[0052] Step 301, Building the first optimization objective function which targets at obtaining the initial object segment sequence corresponding to the object as the optimization object, by setting an allocated 0-1 variable set indicating the candidate object bounding box set and the candidate object contour set respectively;

[0053] Formalizedly, setting a set A={a_D^k|∀k,t,DεD_t} for the candidate object bounding box set, wherein D_t indicates the candidate object bounding box set of the t-th frame of the input video, a_D^kε{0,1}, when a_D^k takes a value of 1, it means the bounding box D is assigned to the k-th sequence, and when a_D^k takes a value of 0, it means the bounding box D is not assigned to the k-th sequence;

[0054] Likewise, setting a set B={b_S^k|∀k,t,SεS_t} for the candidate object contour set, wherein, S_t indicates a candidate object contour set of the t-th frame of the input video, b_S^kε{0,1}, when b_S^k takes a value of 1, it means the contour S is assigned to the k-th sequence, and when b_S^k takes a value of 0, it means the contour S is not assigned to the k-th sequence.

[0055] Building a first optimization objective function i.e., Formula (1), for obtaining the initial segment sequence corresponding to the object, constraint conditions of the objective function are Formula (2);

[0056] $\begin{array}{cc}\underset{A,B}{\min }L\left(A,B\right)+{\lambda }_1{\Omega }_1\left(A,B\right)+{\lambda }_2{\Omega }_2\left(B\right)\}& \left(1\right)\\ \{\begin{array}{c}{a}_D^k,b_S^k\in \left\{0,1\right\},\forall k,t,D\in D_t,S\in S_t\\ \sum _{D\in D_t}{a}_D^k=\sum _{S\in S_t}{b}_S^k\le 1,\forall k,t\\ \sum _k{a}_D^k\le 1,\sum _k{b}_S^k\le 1,\forall t,D\in D_t,S\in S_t\\ \left(\sum _{D\in D_{t-m}}{a}_D^k\right)\left(1-\sum _{D\in D_t}{a}_D^k\right)\left(\sum _{D\in D_{t+n}}{a}_D^k\right)=0,\forall k,t,m,n\\ \sum _t\sum _{D\in D_t}{a}_D^k=\sum _t\sum _{S\in S_t}{b}_S^k\ge 1,\forall k,t\end{array}& \left(2\right)\end{array}$

[0057] wherein, L(A,B) is a loss function, indicating a confidence of the selected object bounding boxes object contours; Ω₁(A,B) is a penalty term, indicating a time domain smoothness of the selected object bounding boxes and object contours on adjacent t-th frame and t+1-th frame of the input video; Ω₂(B) is a penalty term, indicating the spatial overlap among the selected object contours in the different sequences; λ₁ is a parameter of the penalty term of Ω₁(A,B), and λ₂ is a parameter of the penalty term of Ω₂(B).

[0058] Theoretically, value ranges of the parameters λ₁ and λ₂ can be determined depending on an accuracy, optionally, in the embodiments of the present invention, the parameters λ₁ and λ₂ are respectively λ₁=10, λ₂=1000.

[0059] Further, the constraint conditions described above have restricting functions respectively as follows:

[0060] the constraint condition of a_D^k,b_S^kε{0,1}, ∀k,t,DεD_t, SεS_t is used to restrict value ranges of the variable a_D^k of the set A and the variable b_S^k of the set B;

[0061] the constraint condition of

[0062] $\sum _{D\in D_t}{a}_D^k=\sum _{S\in S_t}{b}_S^k\le 1,\forall k,t$
is used to restrict that each sequence can select at most one bounding box or contour on each frame of the input video;

[0063] the constraint condition of

[0064] $\sum _k{a}_D^k\le 1,\sum _k{b}_S^k\le 1,\forall t,D\in D_t,S\in S_t$
is used to restrict that each bounding box or contour is assigned to at most one sequence;

[0065] the constraint condition of

[0066] $\left(\sum _{D\in D_{t-m}}{a}_D^k\right)\left(1-\sum _{D\in D_t}{a}_D^k\right)\left(\sum _{D\in D_{t+n}}{a}_D^k\right)=0,\forall k,t,m,n$
is used to restrict the consecutiveness of the sequence, provided that the sequence must select a bounding box or contour on continuous video frames;

[0067] the constraint condition of

[0068] $\sum _t\sum _{D\in D_t}{a}_D^k=\sum _t\sum _{S\in S_t}{b}_S^k\ge 1,\forall k,t$
is used to restrict that each sequence can select at least one bounding box and contour in the input video.

[0069] Particularly, L(A,B) is a loss function, indicating a confidence coefficient of the selected object bounding boxes and object contours wherein, the confidence for each bounding box or object contour takes a value from 0 to 1, the confidence values are obtained from the output of the used object detectors. Generally speaking, the loss function of L(A,B) is particularly indicated by Formula (3):

[0070] $\begin{array}{cc}\mathrm{fL}\left(A,B\right)=-\sum _{t,k}\sum _{D\in D_t}\sum _{S\in S_t}\xi \left(\mathrm{Df},S\right)a_D^k{b}_S^k& \left(3\right)\end{array}$

[0071] wherein, the expression of ξ(Df,S) is indicated by Formula (4):

[0072] $\begin{array}{cc}\xi \left(\mathrm{Df},S\right)=\{\begin{array}{cc}\pi \left(D,S\right)\log \left(\frac{r\left(D\right)o\left(S\right)}{1-r\left(D\right)o\left(S\right)}\right),& \mathrm{if}D\ne D_{\varphi }\\ 0,& \mathrm{otherwise}\end{array}& \left(4\right)\end{array}$

[0073] Wherein,

[0074] $\pi \left(R_1,R_2\right)=\frac{R_1\bigcap R_2}{R_1\bigcup R_2}$
in Formula (4) indicates an area overlapping ratio between region R₁ and region R₂ (i.e., a ratio of an intersected area to a unioned area between region R₁ and region R₂), o(S) indicates an objectness score of contour S as the outcome of the object contour detector, r(D) indicates a confidence score of bounding box D as the transferred outcome of the object bounding box detector; r(D) is calculated by Formula (5):

[0075] $\begin{array}{cc}r\left(D\right)=\frac{1}{1+\exp \left(-\frac{1}{1.5{\lambda }_d}\left(\hat{r}\left(D\right)-\gamma \right)\right)}& \left(5\right)\end{array}$

[0076] In Formula (5), {circumflex over (r)}(D) is a confidence score of object bounding box D given by the object bounding box detector, γ is an optimal threshold of the object bounding box detector, λ_d is an average value of all the object bounding box scores ({circumflex over (r)}(D)−γ).

[0077] Ω₁(A,B) is a penalty term, indicating a time domain smoothness of the selected object bounding boxes and object contours on adjacent t-th frame and t+1-th frame of the input video, a formalized expression is Formula (6):

[0078] $\begin{array}{cc}{\Omega }_1\left(A,B\right)=\sum _{t,k}\sum _{\underset{S\in S_t}{D\in D_t}}\sum _{\underset{S_0\in S_{t+1}}{D_0\in D_{t+1}}}\eta \left(D,S,D_0,S_0\right)a_D^k{b}_S^k{a}_{D_0}^k{b}_{S_0}^k& \left(6\right)\end{array}$

[0079] wherein, the specific expression of η(D,S,D₀,S₀) is Formula (7):

[0080] $\begin{array}{cc}\eta \left(D,S,D_0,S_0\right)=\frac{{\chi }^2\left(f\left(S\right),f\left(S_0\right)\right)}{1+\pi \left(\stackrel{\_}{D},D_0\right)\pi \left(\stackrel{\_}{S},S_0\right)}& \left(7\right)\end{array}$

[0081] Particularly, f(S) is a feature vector indicating the appearance of contour S, and is expressed as a concatenation between Hue color histogram and 64-dimensional texton histogram, χ² indicates the Chi-Square distance between Hue color histogram and 64-dimensional texton histogram. D and S indicate the projected region of D and S from the t-th frame to the t+1-th frame by an optical flow matching algorithm, bounding box D₀ is included in a candidate object bounding box set D_t+1 of the t+1-th frame, contour S₀ is included in a candidate object contour set S_t+1 of the t+1-th frame.

[0082] The penalty term of Ω₂(B) indicates the overlap degree of the candidate object contour sets selected between different sequences, which is particularly indicated by Formula (8):

[0083] $\begin{array}{cc}{\Omega }_2\left(B\right)=\sum _{t,k}^{}\sum _{k\ne k_0}^{}\sum _{S,S_0\in S_t}^{}{b}_S^k{b}_{S_0}^{k_0}\pi \left(S,S_0\right)& \left(8\right)\end{array}$

[0084] When calculating the penalty term of Ω₂(B), both contours S and S₀ are from the candidate object contour set S_t of the t-th frame.

[0085] Step 302, Converting the problem of solving the initial segmenting sequence corresponding to the object into a problem of solving minimal cost-maximal flow.

[0086] Since the joint assignment model containing the candidate object bounding box set and the candidate object contour set constructed as above contains tens of thousands of binary variables and complicated inequality constraints, it is difficult to be solved with common optimization methods, therefore, embodiments of the present invention convert the problem of solving the initial segmenting sequence corresponding to the object into a problem of solving minimal cost-maximal flow of a network flow.

[0087] Particularly, the first optimization objective function expression

[0088] $\underset{A,B}{\min }L\left(A,B\right)+{\lambda }_1{\Omega }_1\left(A,B\right)+{\lambda }_2{\Omega }_2\left(B\right)\}$
can be converted to the equivalent objective function

[0089] $\underset{{\delta }_x,{\delta }_y,K}{\min }\left\{-{\xi }^T{\delta }_x+{\lambda }_1{\eta }^T{\delta }_y+{\lambda }_2{\delta }_x^T{\mathrm{\Pi \delta }}_x\right\},$
by substituting

[0090] $\sum _k^{}{a}_D^k{b}_S^k$
with an auxiliary variable

[0091] ${\delta }_x\left(D,S\right)s,\mathrm{and}\sum _k^{}{a}_D^k{a}_{D_0}^k{b}_S^k{b}_{S_0}^k\mathrm{with}{\delta }_y\left(D,D_0,S,S_0\right);$

[0092] wherein, ξ, η, δ_x, δ_y are all column vectors, used to record variables relevant to all the bounding boxes and contours respectively; the matrix Π is used to record an overlapping region between contours; the auxiliary variable δ_x(D,S) is used to indicate an activated status of a node represented by a combination (D,S), auxiliary variable δ_y(D,D₀,S,S₀) is used to indicate an activated status of an edge of a node for connecting the combination (D,S) and the combination (D₀,S₀), D₀εD_t+1 indicates that D₀ belongs to the candidate object bounding box set D_t+1 of the t+1-th frame of the input video, S₀εS_t+1 indicates that S₀ belongs to the candidate object bounding box set S_t+1 of the t+1-th frame of the input video, the

[0093] $\underset{{\delta }_x,{\delta }_y,K}{\min }\left\{-{\xi }^T{\delta }_x+{\lambda }_1{\eta }^T{\delta }_y+{\lambda }_2{\delta }_x^T{\mathrm{\Pi \delta }}_x\right\}$
indicates a second optimization object function expression with an optimization object of minimal cost-maximal flow.

[0094] Step 303, Solving K_max initial sequences satisfying the problem of minimal cost-maximal flow;

[0095] Since the second optimization object function expression indicating the minimal cost-maximal flow problem contains a quadratic term, the minimal cost-maximal flow algorithm cannot be used directly to solve the initial segmenting sequence, therefore, when solving the above problem based on the minimal cost-maximal flow algorithm, the quadratic term is ignored first, and then the second optimization object function expression is simplified to

[0096] $\underset{{\delta }_x,{\delta }_y,K}{\min }\left\{-{\xi }^T{\delta }_x+{\lambda }_1{\eta }^T{\delta }_y\right\}.$

[0097] Therefore, the process to solve K_max initial sequences satisfying the problem of minimal cost-maximal flow includes:

[0098] Firstly, the network flow is solved with the minimal cost-maximal flow algorithm to obtain a sequence; secondly, the bounding box and contour (and relevant edges thereof) selected by the sequence are removed from the original network flow, to obtain an updated network flow. This process is repeated until the newly-added sequence triggers one of the following cases: one is that a constraint condition of the optimization problem is not satisfied; the other is that the objective function value increases.

[0099] In all the obtained sequences, sequences with a length less than 5 frames are discarded, to obtain K_max sequences as an initial solution for the minimal cost-maximal flow problem of the network flow.

[0100] Step 304, Re-selecting an object contour of the first K initial sequences in the K_max initial sequences respectively with a K shortest path algorithm, to obtain K candidate sequence sets;

[0101] Assuming that the number K of the candidate sequence is known (1≦K≦K_max), in terms of each sequence among the first K initial sequences, maintain the selected candidate object bounding box unchanged, and re-select the object contour with the K Shortest Path algorithm, to obtain K candidate sequence sets consisting of M new sequences and the original K initial sequences. Wherein, M can be any positive integer, the bigger the value of M is, the better the segmentation result may be, and M is usually set to be M=100 in the experiment.

[0102] Step 305, Optimization on the selection status of each candidate sequence with 0-1 variable for each candidate sequence in K candidate sequence sets through 0-1 quadratic programming;

[0103] Select one candidate sequence respectively from each of the K candidate sequence sets, so that the newly-selected K candidate sequence sets make the optimization object of the original network flow minimal.

[0104] Let με{0,1}^MK indicate selection statuses of all the candidate sequences in the K candidate sequence sets, wherein, 1 indicates to be selected while 0 indicates not to be selected, then the problem of solving minimal cost-maximal flow of the network flow is converted into a problem of solving 0-1 quadratic programming, which is indicated by Formula (9):

[0105] $\begin{array}{cc}\underset{\mu }{\min }\left({\mu }^{T}s+{\mu }^{T}A\mu \right)& \left(9\right)\end{array}$

[0106] The constraint condition is Cμ=1.

[0107] Particularly, each component of column vector S records a loss function value and a time domain smoothness penalty function value of a corresponding sequence, matrix A records a sum of the overlapping areas between any of the two sequences, and constraint matrix Cε{0,1}^K×MK defines that the sum of selecting status variable of sequences in each candidate set is 1.

[0108] Step 306, Solving the problem of 0-1 quadratic programming with an optimizer, to obtain the initial segmenting sequence corresponding to the object.

[0109] The above problem of quadratic programming can be solved with a common optimizer, such as Gurobi optimizer.

[0110] In terms of each K value satisfying 1≦K≦K_max, candidate sequence of the object and object function values of a first optimization object function expression taking the initial segmenting sequence corresponding to the object as the optimization object can be solved by applying step 303. Select a K* making the object function value minimal and take this sequence as a final solution for the first optimization object function expression, and select the optimal contour sequence as the initial segmenting sequence corresponding to the object.

[0111] By means of Step 301 to Step 306, the initial segmenting sequence corresponding to the object of a given semantic category can be obtained, and the initial segmenting sequence can roughly locate the object of a given semantic category in the input video, and lay the foundation for subsequently solving the optimal segmenting sequence corresponding to the object.

[0112] In the method for segmenting video objects tagged with semantic labels according to Embodiment 3 of the present invention, the object tagged with a given semantic category can be selected from a disorder candidate object bounding box set and candidate object contour set, by building the joint allocation model containing the candidate object bounding box set and the candidate object contour set, and the problem of solving the initial segmentation sequence of the object is expressed with the first object function expression, the problem of solving the initial segmenting sequence corresponding to the object is converted into a problem of solving minimal cost-maximal flow, and the initial segmenting sequence corresponding to the object of a given semantic category in the input video is finally solved with a minimal cost-maximal flow algorithm and 0-1 quadratic programming local search. However, since that the object bounding box and contour detector are applied individually for each video frame, the initial segmentation may be inconsistent on different video frames. To address this problem, consistent spatiotemporal shape probability distribution is further estimated from the initial segmentation sequence.

[0113] FIG. 4 is a flow chart of the method for segmenting video objects tagged with semantic labels according to Embodiment 4 of the present invention. Embodiment 4 of the present invention is to further discuss Step 103 on the basis of the technical solution of Embodiment 1. As shown in FIG. 4, the method for segmenting video objects tagged with semantic labels according to Embodiment 4 of the present invention, the Step 103, that is, processing the initial segmenting sequence, to estimate a shape probability distribution of the object in the input video, specific implementation steps include:

[0114] Step 401, Selecting the candidate object contours having an overlapping ratio more than a preset threshold with the initial segmenting sequence from all the candidate object contour sets of the input video;

[0115] Particularly, in all the candidate object contours of the input video, keep candidate object contours having an overlapping ratio more than a preset threshold with the initial segmenting sequence, and remove candidate object contours having an overlapping ratio less than the preset threshold. The preset threshold is set at will as required by the user, and is generally 50%.

[0116] Step 402, adding a candidate contour having a highest matching degree on the next frame found from the candidate object contour with an optical flow matching method into a candidate segmenting sequence, by taking any candidate object contour on any frame of the input video as a starting point with a greedy algorithm, to obtain N candidate segmenting sequences;

[0117] In detail, this step is to construct N candidate segmentation sequences from the candidate object contours having an overlapping ratio more than the preset threshold with a greedy algorithm, the specific construction method is that: search and add a candidate contour having a highest matching degree on the next frame with an optical flow matching method into a candidate segmenting sequence, by taking a certain candidate object contour on a certain frame of the input video as a starting point of the segmenting sequence, and this process is repeated until one of the following two cases is satisfied: one is that the final frame of the input video is arrived; the other is that the overlapping degree of the projected region between any candidate contour on the next frame and the current candidate contour is less than a preset threshold. The preset threshold is optionally 50%.

[0118] According to the method described above, after constructing the candidate segmenting sequence, removing the candidate contour selected by the candidate segmenting sequence, and repeatedly constructing the candidate segmenting sequence for the remaining candidate contours until all the candidate contours are selected, and thereby construct N candidate segmentation sequences.

[0119] Step 403, Setting an initial scoring expression for each candidate segmenting sequence respectively, to compute an initial score of each candidate segmenting sequence based on an appearance consistency and a time domain consistency of the object;

[0120] Particularly, denote the r-th candidate segmenting sequence as {S_r,l}_l=1^Lr, wherein, L_r is the length of the r-th candidate segmenting sequence, 1≦r≦N, then, the initial score of the r-th candidate segmentation is expressed as Formula (10):

[0121] $\begin{array}{cc}{\alpha }_r^0=\sum _{l=1}^{L_r}o\left(S_{r,l}\right)+\sum _{l=1}^{L_r-1}{e}^{-\frac{1}{{\lambda }_f}{\chi }^2\left(f\left(S_{r,l}\right),f\left(S_{r,l+1}\right)\right)}& \left(10\right)\end{array}$

[0122] Wherein, λ_f is an average value of all the values χ² (f(S_r,l),f(S_r,l+1));

[0123] Step 404, Setting a scoring expression of N candidate segmenting sequences after optimization, to build a third optimization object function expression taking the N candidate segmenting sequences as an optimization object, by taking the scoring expression of the N candidate segmenting sequences after optimization as variables;

[0124] Optionally, denote the re-calculated scores of the N candidate segmentation sequences after optimization as α={α_r}_r=1^N, then the objective function to re-calculate the scores of candidate segmentation sequences by taking the appearance and temporal consistency into account can be expressed as Formula (11):

[0125] $\begin{array}{cc}\underset{0\le \alpha \le 1}{\min }\left\{\sum _{r=1}^N{\left({\alpha }_r-{\alpha }_r^0\right)}^2+{\theta }_1{C}_1\left(\alpha \right)+{\theta }_2{C}_2\left(\alpha \right)\right\}& \left(11\right)\end{array}$

[0126] Wherein,

[0127] $\sum _{r=1}^N{\left({\alpha }_r-{\alpha }_r^0\right)}^2$
is a loss function, configured to restrict the deviations between the re-calculated scores and the initial scores; C₁(α) and C₂(α) are penalty terms, C₁(α) is used to represent the appearance consistency of scoring between candidate segmentation sequences; C₂(α) is used to represent temporal consistency of scoring between candidate segmentation sequences; θ₁ and θ₂ are parameters of C₁(α) and C₂(α) respectively.

[0128] Optionally, parameters of θ₁ and θ₂ are set to be θ₁=θ₂=1.5.

[0129] Formula (11) is to avoid the re-calculated scores from deviating the initial scores too much, while enforcing appearance and temporal consistencies between the re-calculated scores.

[0130] Particularly, the appearance consistency penalty term C₁(α) is expressed by Formula (12):

[0131] $\begin{array}{cc}{C}_1\left(\alpha \right)=\sum _{r=1}^N\sum _{s\in R_r}^{}{w_{r,s}\left({\alpha }_r-{\alpha }_s\right)}^2& \left(12\right)\end{array}$

[0132] Wherein, weight w_r,s=e^−dist(r,s) is a similarity between the r-th candidate segmenting sequence and the s-th candidate segmenting sequence, dist(r,s) is the Hausdorff distance of contour features between the r-th candidate segmenting sequence and the s-th candidate segmenting sequence, R_r is the set of candidate segmentation sequences whose feature distances between the r-th candidate segmentation sequence are below a given threshold. The appearance consistency penalty term C₁(α) can make the scores of the candidate sequences with similar appearance as close as possible.

[0133] The time domain consistency penalty term C₂(α) is expressed by Formula (13):

[0134] $\begin{array}{cc}{C}_2\left(\alpha \right)=\sum _{d\in \left\{1,2\right\}}^{}\sum _{p=1}^P{\left(A_p{\beta }_p-\sum _{q\in M_p^d}^{}{\omega }_{q,p}^dA_p{\beta }_p\right)}^2& \left(13\right)\end{array}$

[0135] Wherein, {A_p}_p=1^P is the set of superpixels, |A_p| indicates the area (number of pixels) of the superpixel A_p, β_p indicates the score of the superpixel A_p, which is calculated by

[0136] ${\beta }_p=\frac{1}{N}\sum _{r\in {\Pi }_p}^{}{\alpha }_{r,}$
wherein, Π_p is the set of candidate segmentation sequences covering the superpixel A_p; M_p¹ (M_p²) indicates the set of superpixels that are temporally matched to the p-th superpixel by forward (backward) optical flows, ω_q,p¹ (ω_q,p²) indicates the proportion of the area of the p-th superpixel that are mapped to the superpixel A_qεM_p¹(M_p²). The temporal consistency penalty term C₂(α) is to make the shape probability distribution of adjacent pixels in time domain as close as possible.

[0137] Step 405, optimizing the objective function with L-BFGS algorithm, to obtain the shape probability distribution of the object in the input video.

[0138] After solving the objective function

[0139] $\underset{0\le \alpha \le 1}{\min }\left\{\sum _{r=1}^N{\left({\alpha }_r-{\alpha }_r^0\right)}^2+{\theta }_1{C}_1\left(\alpha \right)+{\theta }_2{C}_2\left(\alpha \right)\right\}$
with the L-BFGS algorithm, to obtain the optimal solution α*, the shape probability of each pixel is the averaged score of the candidate segmenting sequence covering the pixel, and thus the shape probability distribution of the object in the input video can be obtained.

[0140] In the method for object segmentation in videos tagged with semantic labels according to Embodiment 4 of the present invention, the initial segmentation sequence is processed under the joint constraints of the appearance consistency penalty term and the time domain consistency penalty term, the appearance consistency penalty term can effectively enhance the shape probability values of the segmentation sequences corresponding to the objects, the time domain consistency penalty term can reduce the effect of background noise based on video interframe relationship and obtain a visually more consistent shape probability distribution of the object.

[0141] FIG. 5 is a flow chart of the method for segmenting video objects tagged with semantic labels according to Embodiment 5 of the present invention. Embodiment 5 of the present invention is to further discuss Step 104 on the basis of the technical solutions of Embodiment 1 to Embodiment 4. As shown in FIG. 5, the method for object segmentation in videos tagged with semantic labels according to Embodiment 5 of the present invention, the Step 104, that is, optimizing each sequence containing the object in sequence with graph cut algorithm in combination with the shape probability distribution of the object, to obtain an optimal segmenting sequence corresponding to the object in the input video, specific implementation steps include:

[0142] Step 501, Constructing a 4-neighbor graph structure G={V,E} taking pixels as nodes and neighboring relationship between pixels as edges in terms of each frame of the input video;

[0143] wherein, V is a node set, E is an edge set;

[0144] Step 502, Building the fourth optimization objective function, indicated by Formula (14), by indicating a foreground status and a background status of each pixel on each frame of the input video with x=(x₁, x₂, . . . , x_n)ε{0,1}ⁿ;

[0145] $\begin{array}{cc}\underset{x}{\min }E\left(x\right)=\sum _{i\in V}^{}{u}_i\left(x_i\right)+\sum _{\left(i,j\right)\in E}^{}{v}_{\mathrm{ij}}\left(x_i,x_j\right)& \left(14\right)\end{array}$

[0146] The optimization objective of the fourth optimization object function expression is to obtain the best foreground/background status x* so that the pixel can be segmented into a foreground and a background and a local smoothness of the candidate segmenting sequence can be maintained;

[0147] wherein, u_i indicates a data item with a definition formula indicated by Formula (15):
u_i(x_i)=−ρ log(A(x_i))+(1−ρ)log(S(x_i))  (15)

[0148] In the formula, A(x_i) is the foreground probability given by a Gaussian mixture model, indicating the foreground object appearance of the i-th pixel, S(x_i) is a shape probability of the i-th pixel solved in Step 103; particularly, Gaussian mixture models of the foreground and the background are learned from the foreground pixels and background pixels determined by the initial segmenting sequence respectively.

[0149] v_i is the smoothing item, defined by a contrast sensitive Potts model (Contrast Sensitive Potts Model) commonly used in the graph cut algorithm.

[0150] Step 503, Solving the fourth optimization object function expression with the graph cut algorithm, to obtain the foreground/background status x*;

[0151] Particularly, the optimization objective can be solved quickly with the graph cut (Graph Cut) algorithm.

[0152] Step 504, Constituting each optimization segmenting sequence corresponding to the object by a set of the flag status x* of all the pixels on each frame in the input video;

[0153] Step 505, Constituting an optimal segmenting sequence corresponding to the object in the input video by the set containing each optimization segmenting sequence corresponding to the object.

[0154] After individual optimization of each initial segmentation sequence containing the object with steps according to Embodiment 5 of the present invention, the determined foreground regions may be overlapped. To solve this problem, the present invention further provides a simple processing method, that is, extract the appearance feature (color histogram and texton histogram) of the overlapping region first, and then compare it with foreground region of each segmenting sequence closest to the overlapping region under Chi-Square distance measure, and assign the semantic category of the segmentation sequence with the minimum feature distance to the overlapping region.

[0155] In the method for object segmentation in videos tagged with semantic labels according to Embodiment 5 of the present invention, the foreground status and the background status of each pixel on each frame of the input video are indicated with one optimization objective function expression by constructing the 4-neighbor graph structure, and an optimal segmenting sequence corresponding to the object in the input video is obtained by solving with the graph cut algorithm, so as to achieve segmentation of the object of a given semantic category.

[0156] In the method for object segmentation in videos tagged with semantic labels according to Embodiment 1 to Embodiment 5 of the present invention, firstly, an object bounding box detector and an object contour detector are applied to roughly estimate the locations of the object of a given semantic category, so that the problem of ambiguous sample selection and classification under weakly-supervised learning condition can be avoided, secondly, a joint assignment model containing the candidate object bounding box set and the candidate object contour set is built, so that the object bounding boxes and contours that best cover the objects to be segmented can be selected from the set of noisy, inaccurate object bounding box and contour candidates, and finally, the initial segmentation sequence of the object in the input video is optimized in combination with the shape probability distribution of the object, to make the obtained optimal segmentation sequence of the object more accurate and spatiotemporally consistent. Further, the method for object segmentation in videos tagged with semantic labels according to the present invention is applicable to segmenting an object of a semantic category of a single input video, not having to process multiple videos at the same time, and thus has a better applicability.

[0157] The method for object segmentation in videos tagged with semantic labels according to the present invention is widely applicable to semantic parsing of video contents in a computer vision system in the fields such as national defense and military, film-making and public safety.

[0158] Finally, it should be noted that the above embodiments are merely provided for describing the technical solutions of the present invention, but not intended to limit the present invention. It should be understood by persons skilled in the art that although the present invention has been described in detail with reference to the foregoing embodiments, modifications can be made to the technical solutions described in the foregoing embodiments, or equivalent replacements can be made to partial or all technical features in the technical solutions; however, such modifications or replacements do not cause the essence of corresponding technical solutions to depart from the scope of the embodiments of the present invention.