Systematically reversing α-blended onscreen graphics using Adaptive Techniques 
Prasanna V Rangarajan { prangara@engr.smu.edu}
Abstract
This academic report explores the use of standard adaptive filtering techniques in suppressing broadcast logo’s embedded in television material. The real time nature of the problem necessitates the use of adaptive filters with low computational burden. The proposed approach uses a simplified version of the standard adaptive sinusoidal interference canceller, in an attempt to suppress the logo at the pixel level. An array of these pixel level logo suppressors is used to suppress the complete logo. Experimental results illustrate the success of this approach in suppressing logos in temporally stationary areas of the broadcast. 
I.	 Introduction

M
odern day television broadcasts rely on a host of graphics primitives to “enrich” the viewing experience. The term Digital Onscreen Graphics or DOGS as it is popularly abbreviated, is used frequently in this report to describe such graphics primitives. Some of the frequently used graphics primitives include stock tickers, time & weather display panels, text overlays and company logos. The following figure (Fig.1) illustrates some of the DOGS primitives being overlaid on standard television material. 

Fig.1 Illustration of DOGS primitives overlaid on standard television material

Content developers use techniques such as alpha blending, to overlay transparent screens on live TV and video material. This permits creative display of Picture-in-Picture (PiP), Electronic Program Guides (EPG), program information, subtitles and closed-captions, service-provider logos and on-screen instruction guides.  More often than not, these DOGS primitives are a source of annoyance. Unfortunately, broadcast companies worldwide provide no standard way of disabling/removing these primitives. 

The proposed approach attempts to systematically reverse the process of alpha blending broadcast logos using an array of single-tap adaptive filters, which operate on the region of interest (ROI). The success of the proposed approach depends on the availability of a reference logo image, prior to filtering. The reference image by itself cannot be used to suppress the logo in video material using standard image processing techniques. This is due to cross-coupled nature of alpha blending. 

The rest of the report is organized as follows: Section II provides adequate background information relevant to the problem, Section III describes the proposed approach in significant detail, Section IV outlines some preliminary results and Section V summarizes the work and suggests suitable refinements.
II.	Background Information

A. 	α-BLENDING

The process of overlaying graphics primitives on video frames can be viewed as a mixing process. The mixing can be additive, convolutional, multiplicative or a complex function of these processes. Fig.2 illustrates two such schemes that can be used to overlay images or pieces of text.

 									Fig.2 (a) Additive Mixing 				Fig2 (b) Convolutional Mixing

-blending in particular, is a special form of additive mixing. In its simplest form, -blending entails the use of two colors: a source color and a destination color. The source color is the color contribution from a transparent object. The destination color is the color contribution from a background object. -blending amounts to rendering a background object that is behind the transparent object. It relies on the following formula to control the opacity of the transparent object 

ObjectColor is the contribution from the graphics primitive (or logo) being rendered at the current pixel location. DestinatonColor is the contribution from the frame buffer at the current pixel location. The blending is consistent when the DestinationBlendFactor is chosen so that it equals	(1-SourceBlendFactor), which results in the following simplified equation

The above formula can be rewritten in the context of image processing as,

where, m(x,y) represents a pixel in the alpha blended image,  represents the blending factor, b(x,y) represents the background pixel and f(x,y) represents the foreground pixel. It can be easily observed that the above equation resembles the equation for a line in parametric form. Thus, for extreme values of  the alpha blended image m(x,y) resembles either the foreground image or the background image. Interestingly enough, the process of alpha blending can be viewed as a linear time invariant (LTI) system.

B. 	WAVELET PACKETS
Despite their success, standard transformations such as DCT and wavelets provide compact representations of image data that are better suited for compression. Both schemes accurately fail to capture high-frequency information, especially at low bit-rates where such information is lost due to quantization. Both schemes are best suited for the analysis of signals with most of their energy concentrated in the lower frequencies. A more generic transformation that is suited for analysis of signals over a wider frequency range was proposed by Coifman et al. [], and is popularly referred to as the wavelet packet decomposition.  

Typically, a multiresolution wavelet analysis filter bank is constructed by iterating a lowpass–highpass filtering and downsampling operation, only on the output of the lowpass branch of the previous stage. The more generic wavelet packet decomposition allows the lowpass–highpass filtering and downsampling operation to be iterated on the highpass branch in the previous stage. This enables better frequency localization of signals. 

Iterating a lowpass-highpass filtering stage with a rate ½ downsampler yields an octave-band wavelet decomposition. Let φ(t) and ψ(t) be the scaling and the wavelet functions, respectively. They obey the standard scale equations

The sequence {gk} corresponds to the wavelet coefficients. Now suppose, u0(t)≡φ(t) and u1(t)≡ ψ(t) , and define

Computing dyadic rescalings and translations of these functions yields the set of functions 
{2-j/2 un(2-j t-k)}, which are overcomplete. A complete basis can be found by selecting a subset of these functions. Selection of the “best” basis for an image can be performed in a number of ways. Coifman et al. suggest the use of a cost function to be applied to each set of parent and child nodes in a pruning process. If the sum of the costs of the children is greater than the parent’s cost, the children are pruned; otherwise the children are retained. The performance of this method depends heavily on the choice of the cost functions. Some cost functions that have been proposed include: the Shannon entropy [2], the number of coefficients that are significant compared to a known threshold.

C. 	BLIND SOURCE SEPARATION

Given a set of observations M, generated using the model M=A S, the goal of blind source separation is to estimate the source vector S when the mixing matrix A is unknown. Although this seems impossible, the problem can be solved by making some key assumptions.
•	The mixing matrix A is square, i.e. there are exactly two sources and two mixtures
•	The mixing matrix A is invertible
•	The two sources are statistically independent
Under the above assumptions, it is possible to recover the sources S up to a multiplicative factor by estimating the mixing matrix A, and then estimating the sources using the expression S=A-1 M.
A brief survey of literature reveals that there exist numerous methods for solving the blind source separation problem. Recent work by Zibulevsky [1] suggests that sparse sources can be separated more efficiently using simple geometric algorithms. The authors contend that given mixture images resulting from a linear combination of two sparse sources which are independent, there is a high probability that a single source contributes more strongly than its counterparts, to a pixel in the mixture. The authors also describe an approach termed the “Geometric Approach” to estimate the mixing matrix based on the preferred orientations in the scatter plots of the mixtures. Angular histograms provide a straightforward way of determining the orientations from the scatter plot. The performance of this approach depends heavily on the separability of the mixtures in the scatter space.

Unfortunately, most natural images have a rather non-sparse nature. Hence they need to be represented in a sparse manner, before the “Geometric Approach” can be used to estimate the mixing matrix. There exist no universal transformations that will sparsify any image. The simplest transformation, which has been found to yield good results for natural images, is the numerical derivative (of the 1st or 2nd order). Convolution with any edge detecting kernel (e.g. Sobel) also produces similar results. The drawback of these simple transformations is that they are highly data dependent, because, an image with a significant amount of texture would produce a non-sparse edge representation. A richer representation that is sparse and that works over a wide range of natural images is provided by the wavelet packet transform described in Section II.B. The task then is to select those functions {2-j/2 un(2-j t-k)} that provide a sparse representation based on some optimal sparseness criterion. A brief survey of literature revealed that the Shannon entropy criterion provides the best results in most circumstances. In the present context, the Shannon entropy criterion is applied jointly to the coefficients at identical node levels in the decomposition tree, for both mixtures. Nodes whose entropy exceeds a chosen threshold are incorporated in the final sparse representation.

In a more generic context, the problem of sparse transformation can be restated as follows: Given the mixtures M, find a linear transformation T that projects the mixture onto some representation space D = TM, where D is sparse. Due to linearity of T, the problem now reduces to that of separating of mixtures obtained by a superposition of sparse sources, which can be easily solved.

Fig.3 Scatter plot of mixtures before (a) and after (b) the sparse transformation [1]
The number of principal orientations in the scatter plot reveals the number of sources. In the scatter 
plot shown in Fig.3, the number of principal orientations and hence the number of sources equals two. A histogram of the angles of points in the scatter plot reveals the mixing coefficients. The angular histogram corresponding to the scatter plot in Fig.3 is shown in Fig. 4. The angular histogram in Fig.4 exhibits two peaks indicative of two sources, the angles corresponding to the two

     Fig.4 Angular histogram after the sparse transformation               Fig.5 (c)-(d) Synthetic mixtures
 			 																											    (g)-(h) Reconstruction with sparse ICA [1]

peaks provide an estimate of the contribution of the sources to each mixture and thus an estimate of the mixing matrix. The values of the angles are used to reconstruct the mixing matrix under the assumption that the sum of each of its columns equals 1. Fig.5 provides an illustrative example of the process of blind source separation using sparse ICA.
III.	Proposed Approach

A. REVERSING α-BLENDING USING SPARSE ICA

The problem of reversing -blending can be viewed as a linear blind source separation problem. The motivation for this approach is that given any pair of ’s, the process of alpha blending can be formulated as follows

or, equivalently as M=AS, where A is the unknown mixing matrix, S the source vector and M the mixture vector. The above formulation closely resembles the blind source separation problem discussed in Section II.C. Hence, sparse ICA could be used to unmix the sources and thus reverse the process of -blending. However, for sparse ICA to perform consistently, the sum of the column elements in the mixing matrix should equal unity. Hence the above formulation reduces to a more convenient form shown below

The symmetric nature of the mixing matrix reveals that the process of reversing α-blending can be viewed as the process of recovering the sources s1 and s2 from two extreme instances of alpha blending. Symmetry in the mixing matrix can be imposed easily if the mixtures m1 and m2 are generated synthetically.

In the context of logo suppression in standard television material, blind source separation amounts to identifying the independent components in a video frame embedded with a translucent logo. The independent components s1 and s2 in such a frame are the logo and the background material respectively. Sparse ICA can now be used to unmix the independent components. The drawback of this approach is that requires the mixtures m1 and m2 to be generated using a symmetric mixing model. It is extremely difficult to obtain video frames that exhibit such a behavior. In conclusion, the sparse ICA model cannot be used to suppress the logo in standard television material.

B. REVERSING α-BLENDING USING AN ARRAY OF SINGLE-TAP ADAPTIVE FILTERS

Alternately, the problem of reversing -blending can be viewed as that of signal enhancement or interference suppression. Thus, a whole set of adaptive filtering techniques that are best suited for the above task can now be employed. The following paragraphs outline one such scheme that can be adapted for the purpose of logo suppression in standard television material.

The block schematic of a sinusoidal interference canceller is shown in Fig.6. Fig.7 illustrates the block schematic of a pixel level logo suppression system, which will be described in detail in the paragraphs to follow. There is a striking resemblance between the two systems. One obvious difference is the presence of an additional gain block on the input signal path. Another obvious difference is the replacement of a generic N-tap adaptive filter in Fig. 6 by a single-tap adaptive gain  element in Fig. 7. Thus, the  pixel level logo suppression system is a simplified version of  the
adaptive sinusoidal interference canceller. The adaptive filter in the system of Fig.6 has two non-zero weights, one corresponding to the gain element given by B/A and the other corresponding to 

Adaptive Filter

Fig.6 Block Diagram of an Adaptive Sinusoidal Interference Canceller

Fig.7 Block Diagram of an Adaptive Pixel level logo suppressor

the delay θ in samples. If in the system of Fig.6, θ=0, the adaptive filter has just one non-zero weight corresponding to the gain element given by B/A. The situation now resembles that shown in Fig. 7. Thus the pixel level logo suppressor can be viewed as a sinusoidal interference canceller with zero phase interference. The error signal in Fig.7 is the logo suppressed residual.

The logo in standard television material can be suppressed by using an array of such pixel level logo suppressors. Each pixel level suppressor is made up of a single tap adaptive filter. Hence, the complete system for a logo image with width W and height H uses is composed of  W.H adaptive 
filters. This is an instance of the classic “Divide and Conquer” approach. 
C. ANALYSIS OF THE PIXEL LEVEL LOGO SUPPRESSION SYSTEM

This paragraph attempts to analyze the performance of the pixel level logo suppression system when standard LMS algorithm is used to estimate the unknown gain element. From standard LMS theory it is obvious that the gain element will assume a value that produces the least mean square error between the alpha-blended signal and the estimated signal. In other words, the estimated signal is nearest to the alpha-blended signal in mean square sense. In the ideal scenario, the error signal is identical to the background intensity signal except for the scaling factor. In reality however, the contribution of the logo intensity to the desired signal cannot be fully estimated. This is mainly due to the lack of a “good” estimate of the logo intensity. In the current problem, the logo intensity is estimated by averaging the logo area of a frame over several seconds of video material. In conclusion, the error signal is the logo suppressed version of the alpha-blended signal.

Derivation of Steepest Descent Algorithm								Final LMS Algorithm
			 Initialization 

          Weight Update Equation

Final Weight Update Equation 		
IV.	Results
A. PIXEL LEVEL SUPPRESSOR
A news video clip from ABC shot during 1998 was used to train the adaptive filter. The training sequence comprised a series of 6000 frames confined to the logo area in a video frame. The duration of the training data is roughly equivalent to 200 seconds of video at 30 fps (frames/sec). The logo area corresponds to a square area of 40x40 pixels at the bottom right of the video frame. The logo image used in the adaptive filter is obtained by averaging the logo area over a series of frames. Fig.8 (a) shows a sample video frame from the training sequence and Fig.8 (b) shows the logo image obtained from averaging several frames.

Fig.8 (a) Sample video frame from the training sequence 								Fig.8 (b) Average logo image 
Figs. 9 and 10 illustrate the evolution of the filter weight, the MSE, the error signal and the various intermediate signals for two distinct pixels in the logo area. From Figs. 9(a) and 10(a) it is evident that 				is a smoothed version of the desired signal. In other words, the adaptive filter behaves like a low-pass filter, filtering out the temporally varying component in the video signal. The fact that the adaptive filter behaves like a low-pass filter is also evident from the integrator like evolution of the estimated signal. A quick look at the Figs. 9(d) and 10(d) reveal that the weight does not converge in the strict sense. The weight tries to adapt to the local variations in the intensity of the blended logo image. Further, the MSE in Figs. 9(c) and 10(c) show no signs of convergence. This is due to the fact that the adaptive filter tries to adapt to the stationary component of the video material, which is the logo. Thus, the error signal comprises the non-stationary part of the video material, which is the background video material. Isolated spikes in the MSE plot are due to scene changes in the video material. It is near impossible to design an adaptive filter that can adapt to scene changes, as they are highly data dependent.
A step size of 0.01 chosen for the purpose of the experiment produces good results. Choosing a large step size results in overly conservative low-pass filtering causing poor logo suppression. Choosing a small step size results in aggressive low-pass filtering and results in loss of detail in the logo area.

Highlights
•	The single-tap adaptive filter behaves like a low-pass filter, the behavior is evident from the integrator like response in stationary areas
•	The weight does not converge in the strict sense
•	The MSE does not converge in the strict sense
•	Isolated spikes in the MSE plot correspond to scene changes in the video material

Fig.11 (a)-(b) Logo Area before and after logo suppression
This example illustrates a case where the background is spatially constant. The logo suppression system does a poor job of suppressing the logo.

Fig.11 (c)-(d) Logo Area before and after logo suppression
This example illustrates another case where the background is spatially constant. The logo suppression system does a poor job of suppressing the logo.

Fig.11 (e)-(f) Logo Area before and after logo suppression
This example illustrates a case where the background has a lot of high frequency data. The logo suppression system does a great job of suppressing the logo.

Fig.11 (g)-(h) Logo Area before and after logo suppression
This example illustrates a case where the background is spatially smooth. The logo suppression system does a decent job of suppressing the logo.

The thing to note in all the above images is that the logo suppressed image does not possess the same dynamic range as the original image. Hence suitable post-processing needs to be done in order to obtain practically useful results.

A natural question that arises at the end of all this is: why take the trouble of using an adaptive filter, when all its doing is subtracting a scaled version of a reference logo image from each video frame. It is important to realize that subtracting the estimated logo image from each video frame does not guarantee a spatially smooth removal of the logo from the video frame. A straightforward subtraction will result in artifacts in the residual image. If this were to work, the adaptive gain element would always be constant, which is not the case. Hence the need for an adaptive gain element is justified.

B. SPARSE ICA
In order to evaluate the performance of the sparse ICA algorithm synthetic images were employed. The synthetic mixtures were generated as a result of additive and convolutional mixing, using standard test images that are popular in the image processing community. The test images used in this experiment included the ‘Cameraman’, ’Text’ and ’Lena’. A 2-level wavelet packet decomposition together with a threshold Shannon entropy criterion was used to realize the sparse transform.
Fig.12 Additive Mixture Separation using Sparse ICA

The figure shown above illustrates the process of separating additive mixtures using sparse ICA. The mixing matrix used to synthesize the mixture images and the corresponding mixing matrix estimated by the sparse ICA algorithm is shown below

The sparse ICA technique works well provided the peaks in the angular histogram are well separated. This occurs when the mixing ratio is > 1. However, when the mixing ratio approaches unity the system falls apart. Fig. 13 illustrates such a scenario. The mixing matrix used to synthesize the mixture images and the corresponding mixing matrix estimated by the sparse ICA algorithm is shown below

Fig.13 Additive Mixture Separation using Sparse ICA

The next figure illustrates the process of convolutional mixture separation using sparse ICA. 
The sparse ICA technique is able to separate the sources in the mixture images effectively, as the source images are unlike one another. This is evident from the scatter plot in Fig. 13. As a matter of fact, one of the source images is a natural scene while the other is a computer generated scene.

Fig.14 Convolutional Mixture Separation using Sparse ICA
 V.	Conclusion
Experiments carried out during the course of this academic exercise have revealed that a novel adaptation of the sinusoidal interference canceller could be used to suppress -blended broadcast logos in standard television material. Since each pixel in the logo area is filtered using a single-tap adaptive filter, the resulting system exhibits low computational complexity and book-keeping. The only drawback of this system is its inability to suppress the logo in temporally non-stationary areas of the video material. It is difficult to build an adaptive filter that would track the non-stationarity in the video material, as the non-stationarity is highly data dependent. 

In the weight update equation for the LMS algorithm, rather than using the instantaneous estimate of the error signal, an average of the error signal over several samples could be used. This provides a better approximation to the steepest descent weight update equation than the LMS algorithm. In a sense this amounts to using a Block-LMS algorithm. It is not obvious at the time of this writing what a good choice for the block size would be. It is expected that additional experiments would be needed to provide concrete answers.
VI.	References

[1] A. M. Bronstein, M. M. Bronstein, M. Zibulevsky and Y. Y. Zeevi, “Blind Separation of reflections using Sparse ICA”, 4th Intl. Symposium on Independent Component Analysis and Blind Signal Separation, April 2003

[2] R. R. Coifman and M. V. Wickerhauser, “Entropy-based algorithms for best basis selection,” IEEE Trans. Inform. Theory, vol. 38, pp. 713–718, Mar. 1992