One of the key preprocessing tasks in information retrieveal from video is the segmentation of the scene, primarily its segmentation into foreground objects and the background. This is actually a classification task, but with the specific property that it is very time consuming and costly to obtain human-labelled training data for classifier training. That suggests to use semisupervised classifiers to this end. The presented work in progress reports the investigation of semisupervised classification methods based on cluster regularization and on fuzzy c-means in connection with the foreground / background segmentation task. To classify as many video frames as possible using only a single human-based frame, the semisupervised classification is combined with a frequently used keypoint detector based on a combination of a corner detection method with a visual descriptor method. The paper experimentally compares both methods, and for the first of them, also classifiers with different delays between the human-labelled video frame and classifier training.
For the indexing of multimedial content, it is beneficial to have annotations of actors, objects or any other information that can occur in a video. A vital preprocessing task to prepare such annotations is the segmentation of the scene into foreground objects and the background.
Traditional methods, such as Gaussian mixture modeling, work on the pixel level and are time consuming on higher resolution video [1]. Another simple method models the background through image averaging, however it requires a static camera [6]. Our approach, on the other hand, is based on the level of detected interest points, and uses semi-supervised classification to assign those points as belonging either to the foreground objects or to the background.
In the next section, we introduce the key points detector we employed for the detection of points of interest. Section 3 recalls two methods of semi-supervised classification we used in our approach. The approach itself is outlined in Section 4. Finally, Section 5 presents the results of its experimental validation performed so far. Traditional supervised classification techniques use only labelled instances in the learning phase. In situations where the number of availabe labelled instances is insufficient, labelling is expensive and time consuming, semisupervised classification can be employed, which uses both labelled and unlabelled instances for learning.
In the reported research, we used the following two methods for semisupervised classification. 3.1
In each frame of the video, a keypoint detector is used to
detect points of interest and compute their descriptors. In
The principle of this method, in detail described in [8],
consists in clustering all labelled and unlabelled instances
k, n = 1, . . . , N, k 6= n, (
π 2 P(qk, qn) = sin
(r(qk, qn) ∗ s(qk, qn))κ , where r(qk, qn) denotes the Pearson correlation coefficient between qk and qn, κ is a parameter controlling the steepeness of the mapping from similarity to penalty, and s(qk, qn) is a normalized similarity of the probability distributions qk and qn, defined s(qk, qn) = 1 − kqk − qnk − dmin dmax − dmin using the notation dmin = min Q, dmax = max Q,
with Q = {kqk − qnk|k, n = 1, . . . , N, k 6= n}. (
exp ∑xk∈Ψ is labelled yk, j ∑iM=1 exp ∑xk∈Ψ is labelled yk,i , where yk,i, i = 1, . . . , M is a crisp or fuzzy label of the labelled instance xk for the class i. For uniformity of notation, the symbol yˆk, j, j = 1, . . . , M can also be used for yk, j if xk is labelled.
The penalty function (
∑ ∑ N j=1 xn labelled
λ max(qn) ∑ ∑ xn unlabelled |φ (xn)| xk∈φ(xn)
L((F(xn)) j, yn, j)+
!
P(qk, qn)L((F(xk)) j, yˆk, j , (
In [8], the following design decisions have been made
for the loss function and the classifier in (
DKL((yˆn,1, . . . , yˆn,M)kF(xn)) =
M
= ∑ yˆn, j ln
j=1
(F(xn)) j
yˆn, j
, n = 1, . . . , N. (
, n = 1, . . . , N, j = 1, . . . , M. 2. As a classifier, a multilayer perceptron with one hidden layer is used, such that the activation function g in its hidden layer is smooth and includes no bias, and its output layer performs the softmax normalization of the hidden layer. Hence, (F(x)) j = exp(g(w >jx))
· ∑iM=1 exp(g(wi>x) · .
The weight vectors w1·, . . . , wM· in (
This method, in detail described in [9], originated from the fuzzy c-means clustering algorithm [2]. Similarly to the original fuzzy c-means, the method is parametrized by a parameter m > 1. What makes this method more general than the original fuzzy c-means, is its dependence on the choice of some kernel K, i.e., a symmetric function on pairs (x, y) of clustered vectors, which has positive semidefinite Gramm matrices (e.g., Gaussian or polynomial kernels). In fact, the fuzzy c-means algorithm corresponds to the choice K(x, y) = x>y.
First, the membership matrix U l is constructed, for clustering nl labelled instances x1l, . . . , xnll into as many clusters as there are classes, i.e., M. For j = 1, . . . , M, k = 1, . . . , nk, Ujl,k = if the instance xkl is labelled with the class j else.
From U l , the initial cluster centers are constructed as v0j =
n ∑k=ln1 Ujl,kxkl , j = 1, . . . , M.
∑k=l1 Ujl,k
If for some t = 0, 1, . . . , the cluster centers vt1, . . . , vtM are
available, such as (10), then they are used together with
the chosen kernel K to construct the membership matrix
(
Uju,,kt =
(1 − K(xku, v j))− m−11 ∑iM=1(1 − K(xku, vi))− m−11 ,
j = 1, . . . , M, k = 1, . . . , nu. (11) Finally, the cluster centers are updated, for t = 0, 1, .. by calculating vtj+1 = =
n n ∑k=l1(Ujl,k)mK(xkl, vtj)xkl + ∑k=l1(Uju,,kt )mK(xku, vtj)xku n n ∑k=l1(Ujl,k)mK(xkl, vtj) + ∑k=l1(Uju,,kt )mK(xku, vtj) .
The computations (11)–(12) are iterated until at least one of the following termination criteria is reached: (i) kU u,t − U u,t−1k < ε,t ≥ 1, for a given matrix norm k · k and a given ε > 0; (ii) a given maximal number of iterations tmax. (12) 4 4.1
Our methodology for the segmentation of video frames into foreground objects and background relies on the assumption that the user typically assigns corresponding labels to points of interest only in the first frame, and even not necessarily to all detected points of interest.
No matter whether the considered method of semisupervised classification is semisupervised classification with cluster regularization or semi-supervised kernel-based fuzzy c-means, the methodology always proceeds in the following steps: 1. In the first frame, the user labels some of the points of interest detected by the ORB detector. 2. Using the considered method of semisupervised classification, the remaining detected points of interest are labelled. 3. Matching points detected in the next frame are assigned the same labels as the points to which they are matched. 4. Using the considered method of semisupervised classification, the remaining points of interest detected in the next frame are labelled. 5. Steps 3 and 4 are repeated till either the points of interest in all frames have been classified or the scene has been so much disrupted between two frames that no points of interest could be matched between them (in such a case, new labelling by the user is needed). (13) (14) (15) 4.2
The Cartesian coordinates ([p]1, [p]2) of a point p of interest are expressed with respect to top left corner of the frame, using as units the frame height and width. Due to that, [p]1 and [p]2 are normalized to [0, 1].
For a match between points of interest pk and pk+1 in subsequent frames k and k + 1, the following criteria have been used: (i) The point pk+1 must lie within the radius rkp from the estimated new position of the point pˆk p kpk+1 − pˆkk < rk .
Here, the estimated position pˆk is calculated as pˆk = ( pk pk + c1(pk − pk−1) if pk−1 is available, else, where c1 > 0, and the radius rkp is calculated as rkp = (ukpW )2, where ukp quantifies the uncertainty pertaining to the point pk in the k-th frame and W denotes the frame width (in the units in which point positions are expressed). The uncertainty up is set to u1p = c2 > 0 in the first frame and is then evolved from frame to frame through linear scaling above a lower limit c3 > 0:
p uk+1 = (max(c3, c4ukp) if pk is matched,
p c5uk if pk is not matched, (16) where 0 < c4 < 1, c5 > 1.
Moreover, if the evolution (16) leads to ukp+1 > c6 for some c6 > c3, then the point p is deactivated and not any more considered for matching. (ii) Hamming distance between the 256-bit binary desciptors of the points is at most 64.
The choice of the real-valued constants in the criterion (i) has been based on the resolution of the video (4K), on the frame rate (25) and on the defaults in the ORB implementation based on [7]. They have been set to the following values: c1 = 0.6, c2 = 0.02, c3 = 0.009, c4 = 0.9, c5 = 1.1, c6 = 0.03.
In each frame, the described implementation was used to find 500 most interesting points. On a linux computer with a 3.3 GHz Intel Xeon E3-1230 processor, this took 95.32 ms. 4.3
As input features for both classification methods, the Cartesian coordinates ([pk]1, [pk]2) of the point in the k-th frame and and the polar coordinates ([pk − pk−1]||, [pk+1 − pk]ϕ ) of its movement with respect to the previous frame are used.
In the implementation of the semisupervised classification with cluster regularization method described in 3.1, we used k-means clustering for an initial clustering of all instances. Although this method allows choosing the number of clusters independently of the number of classes, we have set it to the same value for comparability with semi-supervised kernel-based fuzzy c-means, i.e., to the value 2 corresponding to the classes of foreground objects and background. Hence, we performed k-means clustering with k = 2. Since the k-means algorithm does not output a probability distribution on the set of clusters, we employed a simple procedure proposed in [8] to transform the original distances from an instance xn to cluster centers v1, . . . , vk, to a probability distribution qn, which assures that xn more likely belongs to clusters to which centers it is closer: Consequently, for our case k = 2: (qn)i = 1 −
kxn−vik ∑kj=1 kxn−vik k − 1 (qn)1 = (qn)2 = kxn − v1k + kxn − v2k kxn − v2k kxn − v1k kxn − v1k + kxn − v2k
,
The remaining parameters pertaining to semisupervised classification with cluster regularization were set as proposed in [8]: λ = 0.2, κ = 2, |φ (xn)| = 10.
For the semi-supervised kernel-based fuzzy c-means algorithm described in 3.2, we used a Gaussian kernel function for updating the membership matrix K(x, y) = exp(−kx − yk2/σ 2), where the parameter σ is computed as proposed in [9]: σ = 1 M s N ∑n=1 kxn − vk2 ,
N where v is the center of all instances. The remaining parameters were set as follows: m = 2, ε = 0.001,tmax = 50. 5 5.1
For the validation of the proposed approach we prepared 12 short videos. In all videos, there is a yellow or blue balloon as a foreground object and a green background. On the background, there are a few small red sticky notes to help detecting some key points. The videos were recorded in a UHD resolution.
Here is a brief characterization of all employed videos: • a handheld camera, both the foreground object and the background are sharp, (17) (18) (19) (20) • a handheld camera, only the foreground object is sharp (2 videos), • a static camera, only the background is sharp (2 videos), • a static camera, only the background is sharp, the foreground object is close to the camera, • a static camera, only the foreground object is sharp, a hand is interfering with the background (2 videos), • a static camera, only the foreground object is sharp, it is moving towards the camera, • a static camera, only the foreground object is sharp, it is moving away from the camera, • static camera, only the foreground object is sharp, it passes the scene multiple times (2 videos).
For the testing, labels were available for all points of interest. Unfortunately, those labels were often unreliable. 5.2
On all the employed videos, we measured the quality of classification by means of accuracy, sensitivity, specificity and F-measure of both implemented classification methods.
For the fuzzy c-means method, the accuracy and specificity on the unlabelled data are illustrated for four particular videos in Figure 1.
For the cluster-regularization method, we compared the values of the considered four quality meaures obtained with five classifiers trained in each of the five first video frames with respect to the delay between classifier training and measuring its quality. The results of their comparison are for three particular delays, 1 frame, 5 frames and 10 frames, summarized in Table 1. In addition, for delays up to 50 frames, they are again illustrated for accuracy and sensitivity on the four videos used already in connection with the fuzzy c-means classifier, in Figures 2–5.
The figures (
The presented research integrates two comparatively recent approaches, the keypoint detector ORB, which is a combination of a corner detection method with a visual descriptor method, and two semi-supervised classifiction methods. To our knowledge, this is the first time these approaches are used together for the task of scene segmentation into the foreground objects and the background.
On the other hand, this is a work in progress and the presented results are still rather preliminary, being obtained on 12 artificially created videos with a quite simple scene segmentation. Both approaches should be investigated in the context of more complex segmentations and more realistic scenes. To this end, however, especially the ORB detector needs to be more deeply elaborated with methods of semisupervised classification.
The research reported in this paper has been supported by the Czech Science Foundation (GACˇ R) grant 18-18080S.