Simultaneous and Causal Appearance Learning and Tracking

Electronic Letters on Computer Vision and Image Analysis 5(3):44-54, 2005 Simultaneous and Causal Appearance Learning and Tracking J. Melench´on, I. Iriondo and L. Meler Communications and Signal Theory Department, Enginyeria La Salle, Universitat Ramon Llull, Pg. Bonanova 8, 08022, Barcelona, Spain Received 20 December 2004 ; accepted 22 March 2005 Abstract A novel way to learn and track simultaneously the appearance of a previously non-seen face without intrusive techniques can be found in this article. The presented approach has a causal behaviour: no future frames are needed to process the current ones. The model used in the tracking process is refined with each input frame thanks to a new algorithm for the simultaneous and incremental computation of the singular value decomposition(SVD) and the mean of the data. Previouslydevelopedmethods about iterative computation of SVD are taken into account and an original way to extract the mean information from the reduced SVD of a matrix is also considered. Furthermore, the results are produced with linear computational cost and sublinear memory requirements with respect to the size of the data. Finally, experimental results are included, showing the tracking performance and some comparisons between the batch and our incremental computation of the SVD with mean information. 1 Introduction The last years have witnessed extraordinary advances in computer and communications technology, leading to an increasing availability of information and processing capabilities of multimedia data [1], [2]. This fact is resulting in a higher and wider demand for easier access to information [3]. On one hand, this information is mainly stored in digital format, so its acces is limited to the user’s ability to communicate with computers. On the other hand, it has been remarked the great expressive power of the natural language used in human-human communication, as well as its intrinsic multimodal features [4]. Consequently, the acces to digital information could be carried out using this natural language: reducing the necessity of knowing a specific way to interact with the computer and taking advantage of its expressive features. Moreover, multimodal interfaces with an audio visual system like a talking head could be used in order to speak to the user in natural language. As a result, talking heads used in multimodal interfaces seem to be a proper solution for making acces to information easier and more pleasing for human users. As explained in [4], multimodal input analysis is necessary when working with multimodal interfaces and relies on interaction devices e.g. facial trackers. Some non-intrusive visual trackers can be used in this sheme because they retain information regarding to position, scale, orientation and appearance of the tracked element, e.g. [5], [6], [7], [8] and [9]. Nevertheless, the whole sequence is needed by these algorithms to be processed off-line (they have a non-causal behaviour); as a result, a real time implementation of these methods is impossible, even without considering their computational cost. This temporal restriction is caused by the computation Correspondence to: [email protected] Recommended for acceptance by Perales F., Drapper B. ELCVIA ISSN:1577-5097 Published by Computer Vision Center / Universitat Aut`onoma de Barcelona, Barcelona, Spain Melench´ on et al. / Electronic Letters on Computer Vision and Image Analysis 5(3):44-54,2005 45 of a Singular Value Decomposition (SVD) over the whole observed data. Moreover, memory resources are greatly affected by this fact, limiting the duration of the observed sequence. Incremental SVD computation techniques as [10], [11] and [12] may be useful in this case, but they do not take into consideration the mean of the data, which is crucial in the classification of the different gestures. Fortunately, this is taken into account in [13] and [14]. By one hand, the work presented in [13] does not does not propose a method to extract the mean information from a given SVD and it can only update the SVD from two other known SVD. By the other hand, Skoˇcaj presented in [14] a method with a similar performance to the one achieved in this paper, but he focused on incremental Principal Component Analysis rather than incremental SVD. In this paper, a new method for updating both SVD and mean information as well as extracting the mean of the data contained in a given SVD without increasing the cost order of either time or memory is presented in Sect. 2. The application of this new method is carried out in Sect. 3 by a causal algorithm for the tracking and learning of the facial appearance of a person. Experimental results are given in Sect. 4 and concluding remarks are explained in Sect. 5. 2 Incremental SVD with Mean Update 2.1 Fundamentals The singular value decomposition of matrix Mp×q=[m1···mq]is given by: Mp×q=Up×pΣp×qVT q×q,(1) where U=[u1··· up]and V=[v1··· vq]are orthonormal matrices; uiare the eigenvectors of MMT and span the column space of M;viare the eigenvectors of MTMand span the row space of M; and Σis a diagonal matrix with the singular values of either MM Tand MTMin descending order. Notice that if M is a rank rmatrix, where r≤pand r≤q, its corresponding Σhas only rnon-null singular values and (1) can be rewritten as the thin SVD:Mp×q=Up×rΣr×rVT q×r. By the other hand, let Cr×q=UT p×rMp×qbe the projections of the columns of Mover the eigenspace spanned by U. Using the thin SVD expression the projections matrix C=[c1··· cq]can be written also as Cr×q=Σr×rVT q×r. In other fields, like classification problems pointed by [13], a more suitable representation of Mcan be achieved including mean information m=1 qq i=1 miin (1), which has to be computed and substracted previously from Min order to be able to generate the SVD of M−m·1: Mp×q=Up×rΣr×rVT q×r+mp×111×q.(2) 2.2 Updating SVD Assuming an existing SVD (1), if new columns Ip×c=[I1··· Ic]are added in order to obtain a new matrix M p×(q+c)=Mp×qIp×c, the SVD of Mcan be updated from (1) using methods like [11] and [12], achieving: M  p×(p+c)=U  p×rΣ  r×rV T (q+c)×r.(3) Otherwise, if the representation of Mis chosen to be as (2) and mis set to 1 q+cq k=1 mk+c l=1 Ilthe SVD becomes: M p×(q+c)=U p×rΣ r×rVT (q+c)×r+m p×111×(q+c).(4) Starting from (2) and matrix I,(4) can be obtained using the method proposed by [13] if the SVD of Iis previously computed and qand care known beforehand. A new method for updating both the SVD and the mean using only the new observations and previous factorization is presented in Sect. 2.3. 46 Melench´ on et al. / Electronic Letters on Computer Vision and Image Analysis 5(3):44-54,2005 2.3 Updating SVD and Mean Begining with an existing factorization of M ias in (5), it is desired to obtain the SVD and mean of Mfshown in (6): Mi=UiΣiVT i+mi1.(5) Mf=MiI=UfΣfVT f+mf1.(6) Defining ˆ Mi(7) and centering new columns Iaround mi(8), it can be written: ˆ Mi=Mi−mi1=UiΣiVT i.(7) MiI−mi1=UfΣfVT f+mf1−mi1.(8) Mi−mi1I−mi1=UfΣfVT f+(mf−mi)1.(9) ˆ Miˆ I=UtΣtVT t.(10) The new columns Ip×c(see sect. 2.2) will be known through this paper as the update block. Note that (10) is the updated SVD from (7) when some new observationsˆ Iare added. This update can be done as [12] suggests: ˆ Miˆ I= UiQi· ΣiUT iˆ I 0Q T iˆ I· VT i0 01 = UiQi·UdΣdVT d· VT i0 01 =UtΣtVT t(11) where QR-decomposition is done toˆ I−UiUT iˆ I=QiRito obtain an orthogonal basis Qifor the reconstruction error. Next, the mean update algorithm can be executed starting from the knowledge of V T t=ˆ VT t+vt1, where vt=1 q+cq+c k=1 vk: ˆ Miˆ I=UtΣtˆ VT t+UtΣtvt1=UtΣtˆ VT t+mt1.(12) ˆ Miˆ I=UtΣtRT vQT v+mt1=UfΣfVT uQT v+mt1=UfΣfVT f+mt1.(13) ˆ Miˆ I+mi1=UfΣfVT f+mt1+mi1.(14) MiI=UfΣfVT f+mf1.(15) It is assumed QvRvas the QR-decomposition of ˆ Vt,UfΣfVT uas the SVD of UtΣtRT vand mf=mt+mi. Note that (15) and (6) are the same expression. 2.4 Mean Extraction from a Given SVD The previous method can also be used to extract the mean information from an existing SVD, e.g. trying to express S=UtΣtVT tas S=UfΣfVT f+s·1setting ˆ Miˆ I=Sand mt=0in (12) to (15). 2.5 Time and Memory Complexity The mean update presented in section 2.3 does not increase the order of resources required in methods of incremental SVD developed in [10], [12], [11], [13] and [14] . The computational cost becomes Oqr2+pr2 and the memory complexity is O(pr +qr), as shown in Table 1. 3 On-the-fly Face Training In this paper, On-the-fly Face Training is defined as the process of learning the photo-realistic facial appearance model of a person observed in a sequence in a rigorous causal fashion. This fact means that it is not necessary to take into account subsequent images when adding the information of the current one, which is considered only once. Note that the facial appearance is learnt in the same order as the captured images, allowing a real-time learning capability in near future, as computational resources are constantly being increased. Melench´ on et al. / Electronic Letters on Computer Vision and Image Analysis 5(3):44-54,2005 47 Table 1: Resource order requirements of the proposed mean update algorithm Operation Comp. cost Mem. requirements VT q×r−1 qq k=1 (vk)r×111×q→ˆ VT q×rO(qr)O(qr +r) ˆ Vq×r→(Qv)q×r(Rv)r×rOqr2Oqr +r2 (Ui)p×r(Σi)r×rRT vr×r→Tp×rOpr2+r3Opr +r2 Tp×r→(Uf)p×r(Σf)r×rVT ur×rOpr2Opr +r2 (Vf)q×r→(Qv)q×r(Vu)r×rOqr2Oqr +r2 Totals, assuming prand grO qr2+pr2O(pr +qr) 3.1 Data Representation An Nimage sequence S=[I1··· IN]and a set of four masks Π=π1 ,...,π4, attached to four facial elements (like mouth, eyes or foerehead), are given. For each image I t, its specific mouth, eyes and forehead appearance are extracted using Π, obtaining four observation vectors o r t(see Fig. 1). Therefore, four observation matrices Orcan be obtained from the application of the set of masks Πover the sequence S. Dimensionality reduction of Orcan be achived using SVD [15]: Or=[or 1···or N]=UrΣr(Vr)T+or11×N, where or=1 NN k=1 or k. Note that facial element appearances can be parameterized as C r=Σr(Vr)T(see Sect. 2.1). In the example proposed in this paper, faces composed of 41205 pixels could be codified with 35 coefficients, representing a reduction of more than 99.9% without any loss of perceptual quality (see Fig. 2). 3.2 Training Process One major drawback of the parametrization presented in section 3.1 consists in the image alignment of the sequence [5]. Unless all face images through the whole sequence have the same position, ghoslty results may appear and suboptimal dimensionality reduction will be achieved. The tracking scheme presented in this paper combines simultaneously both processes of learning and alingment. First of all, the four masks π rare manually extracted from the first image I1of sequence Sand the first observation vectors o 1 1,...,o4 1are obtained. Next, Figure 1: (a)Masks πr.(b)Image It.(c)Regions Rr t, obtained from the application of each mask πrover image It.(d)Vectors or trelated to the defined regions. 48 Melench´ on et al. / Electronic Letters on Computer Vision and Image Analysis 5(3):44-54,2005 (a) (b) Figure 2: (a) Three observed frames of a subject’s face. (b) The same synthesized frames after learning the appearance model of this person. the corresponding alignment coefficients a1are set to 0; they represent the affine transformation used to fit the masks onto the face on each frame [5]. Using the tracking algorithm presented in [7] over the second image I2, observations o1 2,...,o4 2and alignment coefficients a2are stored. At this point, each facial element rcan be factorized as [or 1or 2]=Or 2=Ur 2Σr 2(Vr 2)T+or 2=Ur 2(Cr 2)T+or 2, where the current mean observation is generated by or 2=or 1+or 2 2, the eigenvectors of Or 2(Or 2)Tare found in Ur 2and the texture parametrization of the r-th facial element in images I1and I2is obtained in Cr 2. Once this initialization is done, the On-the-fly Training Algorithm (Figure 3) can be executed. Besides, only those columns of U r t+1 and Vr t+1 whose values of Σr t+1 exceed a threshold τare considered, keeping only those eigenvectors with enough information. The value of τdecreases from 0,5to 0,5·10−3in the first images (1 seconds at 25 im/s) in order to allow better face localization when almost no information is known about its appearance [14]. Notice that alignment parameters acan be used to extract gestural information in a multimodal input system [16]. On-the-fly Training Algorithm In: U2,Σ2,V2,¯o2, alignment coefficients a2and set of four masks Π 1. Set k=2 2. Using Uk,Σk,Vk,¯ok,akand Π, the images of the new update block are aligned, generating Lobservation vectors or k+1 and alignment information ak+1 for each image. 3. Obtain U k+1,Σk+1,Vk+1 and ¯ok+1 from U k,Σk,V k,¯ok, and o k+1 (4)-(8). 4. Trim Uk+1 and V k+1 according to Σk+1. 5. Set k=k+1and go to Step 2 until there is no more new images. Out: Uf,Σf,Vf,¯ofand alignment coefficients affor each image. 3.3 Cost analysis In this section, the computational cost and memory requirements of the incremental computation of matrices Uf,Σfand Vfand vector ¯ofof the previous On-the-fly algorithm is presented in table 2. As could be seen in the previous section, this incremental process consists of successive SVD and data mean updates, explained in section 2.3 to achieve a final factorization of the whole observation matrix O: Op×q=(Uf)p×s(Σf)s×s(Vf)q×sT+¯op×1·11×q(16) The value sconsists in the number of eigenvectors kept in matrices U k+1 (step 4 of the On-the-fly algorithm). Also, it must be noted that he update block size is specified by c. In this analysis, we presuppose that p>q, Melench´ on et al. / Electronic Letters on Computer Vision and Image Analysis 5(3):44-54,2005 49 Table 2: Resource order requirements of the proposed SVD and mean update algorithm over a matrix O p×q using update block size cand the seigenvectors corresponding to the largest ssingular values of O p×q.To obtain more compact expressions, value n=s+chas been used. Value kidentifies the iteration number. Id. Operation Computational cost Memory requirements SVDΣkUT kˆ I 0Q T kˆ In×nOn2On2 UkQkp×n·(Ud)n×nOpn2O(pn) VT dn×n·VT k0 01 n×(kc+c) O(kc +c)n2O((kc +c)n) Mean update Os2(p+kc +c)O(s(p+kc +c)) Total Oqs2 c+n(n+p+q)On(p+q+s)+c2 q>sand q>c. Moreover, if additional considerations are taken into account for the values of cand s, particular cost functions can be described as follows: •When cand sare of small order of magnitude (o.o.m.) compared to q, the lowest computational cost is obtained: O(sq (p+q)). •If only chas small o.o.m., the computational cost becomes the highest one: Oqss c(s+p+q). •For small o.o.m of sonly, the computational cost becomes O(qc(c+p+q)). •When all c,s,pand qare of the same o.o.m., O(q(s+c)(s+c+p+q)). The computational cost order of the batch process is O(pq (p+q)), which is higher than the first assumption and slightly higher than the two last ones. Note that the two last cases have also a similar cost. Regarding to memory costs, the batch process has memory requirements of order Oq2+sp, while the proposed incremental approach has O(c+s)(p+q+s)+c2. As can be noted, for small values of cand s the presented approach achieves great memory reduction and do not increase its order in the other cases. Figure 3: Block diagram of the On-the-fly Training Algorithm 50 Melench´ on et al. / Electronic Letters on Computer Vision and Image Analysis 5(3):44-54,2005 (a) (b) Figure 4: Output tracking results of the learning process for: (a) the On-the-fly Training Algorithm and (b) the non-causal algorithm. 4 Experimental Results In this section, the performance of our incremental algorithm is shown. First, tracking results are specified in section 4.1, showing a comparison between the presented algorithm and its previous version. Next, precision results about incremental SVDwith mean update are presented in section 4.2. Finally, in section 4.2.2 execution time is put in correspondence with the cost analysis obtained from section 3.3. 4.1 On-the-fly training algorithm The On-the-fly Training Algorithm has been tested over a short sequence and a long one, both recorded at a frame rate of 25 im/s. The short sequence consists of 316 images and it has been used to compare the results obtained from our On-the-fly Training Algorithm and its previous non-causal version [7]. Achieving the same quality in the results (see Fig. 4), the presented algorithm has reduced the execution time about 66% with respect to [7] and has required about 7Mbytes in front of the 200 Mbytes consumed by [7] (see the comparison in Fig. 5). Later, if we focus on the long sequence (10000 frames), its processing requirements were impossible to met with the non-causal algorithm [7] because its huge memory cost of 6000 Mbytes, although massive storage systems (e.g. hard drives) were used; the On-the-fly Training Algorithm reduced the memory requirements to 17 Mbytes with a processing time of a little more than 10 hours (using a 2GHz processor) (see Fig. 5). 4.2 Incremental SVD and mean computation In this section, the goodness of the results given by the proposed incremental SVD and mean update algorithm (sect. 2.3) is analyzed and compared to the ideal performance offered by the batch solution. 4.2.1 Precision comparisons Some experiments have been developed in order to test the analysis shown in the previous section (3.3). Two video sequences have been recorded and the face has been aligned in each one using our On-the-fly training algorithm. Starting from these aligned observations set stored columnwise in every O k, we have factorized it using both the batch SVD process and our incremental SVD with mean update algorithm (sect. 2.3), obtaining two approximations of the form: Ok p×q≈Uk p×sΣk s×sVk q×sT+¯ok p×1·11×q(17) Melench´ on et al. / Electronic Letters on Computer Vision and Image Analysis 5(3):44-54,2005 51 (a) (b) Figure 5: Solid line represents the On-the-fly Training Algorithm performance while the dashed one belongs to the non-causal algorithm presented in [7]. (a) Computation time in seconds. (b) Memory used in bytes. Ok p×q≈ˆ Uk p×sˆ Σk s×sˆ Vk q×sT+ˆok p×1·11×q(18) where matrices Uk,Σkand Vkare the trimmed version of the thin-SVD of ˆ Ok=Ok−¯ok·1and ¯okis the mean column of Ok; matrices ˆ Uk,ˆ Σkand ˆ Vkand vector ˆokare the corresponding ones when obtained with the incremental approach presented in section 2.3. This incremental process has been executed with different sizes of update block cand different threshold τ(sect. 3.2); the higher the threshold, the lesser eigenvalues kept in the model (with a non-linear case specific relation s=f(c, τ, k)). Next, we define: eb(c, τ)= ∀k    Mk p×q−Uk p×sΣk s×sVk q×sT −¯ok p×1·11×q   2(19) ei(c, τ)= ∀k    Mk p×q−ˆ Uk p×sˆ Σk s×sˆ Vk q×sT −ˆok p×1·11×q   2(20) Function ebis shown in fig.6(a) and eiis represented in fig.6(b). Following the reduction and compression of matrices teorem found in [15], it can be assured that e b(c, τ)≤ei(c, τ)for any cand τ. Figure 6(c) represents the relative error as a function of cand τ. This relative error is measured asei(c,τ)−eb(c,τ) eb(c,τ)and, as can be observed, all three figures achieve it lowest value when both cand τhave low values (1-5and 0.001, respectively). 4.2.2 Execution time We have measured the execution time of both the batch and our incremental computation process done in section 4.2.1. The execution time of our incremental SVD and mean update algorithm is depicted in fig.7asa function of update block size and treshold (sect.3.2) and has been obtained as the mean execution time related to the observation matrices Ok. It can be noted that the analysis made in sect.3.3 is reflected in fig.7. It must be noted that the fastest results (about a third of the computation time belonging to the batch approach) can be achieved for small update block sizes and large threshold, which translates in taking into account few (1-2) eigenvectors. By the other hand, the heaviest computational load corresponds to the assumption of small block size (1-5) and low threshold (0.001), which translates to a larger number of eigenvectors (30) and further overcomes the computation time of the batch process. Finally, it can also be seen that as the block size grows, the computational cost becomes more independent with respect to the threshold (or number of eigenvector kept). 52 Melench´ on et al. / Electronic Letters on Computer Vision and Image Analysis 5(3):44-54,2005 (a) Batch SVD (b) Incremental algorithm (c) Relative error Figure 6: (b) Error between the original data matrix Oand the factorization obtained by our incremental SVD and mean update algorithm. Figure 7: Execution time of the algorithm with different number of eigenvectors and update block size 4.2.3 Conclusions It can be concluded that the best alternative consists in using a small block size (i.e.1-10) with a relatively small threshold (i.e.0.01, obtaining about 10 eigenvectors); it achieves a relative error of less than 10 −3with half the computation time of the corresponding batch process. Moreover, when both update block size and threshold are small enough (τ=0.001, obtaining more than 30 eigenvectors, and c=1), the incremental SVD and mean update algorithm achieves the best performance but with the heaviest computational load. By the other hand, the fastest option, achieved with small update block size and high threshold (τ=0.1,c=1), offers a poor precision compared to the previous cases. Finally, if we increase the update block size (c>10), both computational and precision results also get worse. 5 Concluding Remarks In this paper, a new method for extracting the mean of an existing SVD is presented, without increasing either the cost order of memory or time. This fact has allowed us to offer an incremental computation of SVD preserving a zero data mean, which has been analyzed and compared with the batch approach. The precision offered by our method is high enough to allow photorealistic reconstructions of observed face images using half the computation time of the non-incremental processes. Fields that can benefit from it can be, e.g.: classification problems, where the mean information is used to center the data; incremental computation of covariation matices, which need to be centered around its mean; causal construction of eigenspaces, where the principal components of the data are included, as well as the mean information. With respect to the latter, the On-the-fly Algorithm is presented in this work. Given an image sequence and a set of masks, this algorithm is capable of generating a separate eigenspace for each facial element (learning all their appearance variations due to changes