\chapter{Movie and Video Scale-Time Equalization}
\label{chapter_ste}

\begin{resume}
Le papillonnage, ou {\em flicker}, désigne ce changement rapide et artificiel de la luminosité et du contraste que l'on observe dans les films anciens ou les vidéos à faible échantillonnage. Cet artefact peut provenir aussi bien de défauts d'exposition au moment du tournage que de dégradation physiques survenues au cours du temps. Le réduire est primordial pour améliorer la qualité visuelle d'un film, voire comme prétraitement avant d'autres manipulations ou restaurations. Ce chapitre présente une analyse axiomatique du problème, très semblable à celle mise en place au chapitre~\ref{chapter_midway}, et conduisant à une correction du {\em flicker} de type temps-échelle, simple et rapide. Cette correction est testée sur des séquences réelles et synthétiques. Les résultats sont visuellement très satisfaisants.
\end{resume}

\medskip

\noindent
\begin{abstract}
Image flicker is a general film effect, which can be observed in low sampled videos as well as in old films, and consists of fast variations of the frame contrast and brightness. Reducing flicker of a sequence improves its visual quality and can be an essential first treatment before ulterior manipulations. This chapter presents an axiomatic analysis of the problem, which leads to a global and fast method of ``de-flicker'', based on scale-space theory. The stability of this process, called \textit{Scale-Time Equalization}, is ensured by the scale-time framework. Results on real and artificial sequences are given, and show a great visual improvement. 
\end{abstract}

\medskip

This chapter corresponds to the article ``Movie and Video Scale-Time Equalization. Application to the reduction of flicker.''~\cite{delon03movie}, submitted.

\medskip

\section{Introduction}

Image flicker is a general film effect, especially known for its presence in old movies. It consists of fast variations of the frame contrast and brightness. Old movies suffer at the same time from age related degradations and from the primitive technology used at the early age of cinema. In their case, flicker can be caused  by physical degradations of the film, by the use of not very stable chemical products, or by aberrations in the exposure time for each frame (\cite{kokaram}), etc... But intensity flicker can also be observed in many amateur videos, whose luminosity has not been controlled during the shooting, or more strongly in the frequent case of low time sampling, as in video surveillance. 

There have been few attempts to remove flicker, probably because the problem seems quite easy to solve. However, this is not the case, as flicker can have many aspects, and is not well removed by simple affine transformations on the intensity of each frame. Most of the time, the problem is considered as a global degradation of the image. In a sense, this strong assumption is a simplification of the problem, but global methods (dependent only on the images histograms) are {\it a priori} much more robust to shaking, to motion and to noise presence, than local ones. After a state of the art and a discussion on the subject, we will make this basic assumption in this chapter. We will then see what kind of ``time smoothing'' generic method can be considered. Such a method should involve a scale of correction, representing the size of the time neighborhood used to change each image. This size should correspond to the limit between the flicker variations and the ``natural'' intensity variations in the movie. Except for this time scale, which is obviously user dependent, we look for a method without any {\it a priori} assumption or user parameters.

 The role of time scale however must be formalized and leads us to involve {\it scale-space theory}. This theory, founded by Witkin~\cite{witkin}, Marr~\cite{marr82vision} and Koenderink~\cite{koenderink}, and among others pursued by Florack, Romeny, Viergever and Lindeberg~\cite{lindeberg,lindeberg3,lindeberg2}, links, under basic assumptions, iterated filtering to partial differential equations. It leans on the central concept of causality, which must be understood here in the sense stated by F. Guichard and J.M. Morel in~\cite{morel2}: it gathers such requirements as regularity, recursivity (semi-group structure) and a local comparison principle. As we shall see, these principles, associated with an axiomatic analysis of key examples, lead directly to a simple solution of filtering, connected with the midway image equalization presented in chapter~\ref{chapter_midway} and based on~\cite{Cox}. We will see why this scale-time dimension ensures the stability of the method. The end of the chapter will be devoted to experiments.

\section{First steps on the subject}

%\subsection{Some notations}
%Let us begin with some notations that we will use all along the chapter.
%Let $v:\Omega \rightarrow [0,1]$ ($\Omega \subseteq {\mathbb{R}}^2$) be an
%image \footnote{This definition is not
%restrictive, the range of an image can be put on $[0,1]$ by an
%affine transformation.} and $h$ the distribution of its intensity values (also called histogram of $u$). The \textit{cumulative histogram} of $v$ is the
%function $H:[0,1]\rightarrow [0,1]$ defined by:
%$$H(x)=\int_0^x h(t)dt$$

%\begin{proposition}
%Let $\ph:[0,1]\rightarrow [0,1]$ be a continuous and strictly
%increasing function (such a function will be called an
%\textit{increasing homeomorphism} on $[0,1]$). Then $\ph(v)$ is a
%new image, whose cumulative histogram is $H \circ {\ph}^{-1}$.
%\end{proposition}
%We point out that such a transformation, called {\bf contrast change}, preserves the order of the
%gray levels in $v$ and doesn't create or cancel any image
%information. 
%If we assume that $H$ is continuous and strictly increasing, it follows that $H(v)$ is an image whose distribution function is uniform on $[0,1]$. This transformation is called \textit{histogram equalization}. General information on histogram modification can be found, for example, in~\cite{woods}.

We define a movie $u$ as a sequence of images $(u_t)_{t \in {\mathbb R}}$ having the same set of definition $\Omega$. $(H_t)_{t \in {\mathbb R}}$ denotes the sequence of its cumulative histograms. In what follows, we will always note $T$ a ``de-flicker'' operator, and $\tilde{u}=T(u)$ the deflickered sequence. For a sake of simplicity, we assume that the set of definition $\Omega$ is fixed and that all the films that we consider are defined on $\Omega$. As we will see that the results found for $T$ are independent from $\Omega$, this hypothesis is not restrictive.

\subsection{Previous work}

The papers about flicker can be classified in two categories: those which treat image flicker as a phenomenon affecting the whole image in an equal way, and those which treat it as a local degradation.  In~\cite{richardson,richardson2}, P. Richardson and D. Suter observe that a standard compression algorithm (MPEG) is not really suitable for old movies because of their obvious degradations, and propose to restore a sequence prior to compression by a motion-corrected temporal filtering technique. Before this filtering, the flicker is reduced by applying an affine stretching to the histogram of each frame, so that it fills a given dynamic range. If this global correction is simple and seems judicious at first, it is emphasized in~\cite{Fer} that it is not really satisfying. In his Phd Thesis~\cite{Fer}, E. Decencière proposes precisely methods to correct intensity flicker in movies, which take as basic assumption that each image suffers an affine degradation of the form 
$$u_t=\alpha_t u_t^o +\beta_t,$$
where $u_t$ is the observed frame at time $t$ and $u_t^o$ is the original frame. If the  frame at time $t-1$ has been restored, he restores the frame at time $t$ with the assumption that some moments of the current frame remain constant (the mean and/or the extrema of the frame for instance).
All the frames are restored this way. Finally, according to his conclusions, the most satisfying results are obtained by fixing the mean and the difference between the extrema of the frame. The affine correction methods have the advantage of being fast and simple, but such iterative methods involve an obvious drawback: they are always very sensitive to initialization. Here, the first frame is not restored and must be chosen very carefully, because its characteristics will be propagated to all frames. Recursive methods also lack of symmetry properties: it would be natural for a deflickering process to depend neither on the time direction, nor on the time origin. Another important drawback is the fact that there is no reason for the observed intensity degradations to be well modeled by an affine transformation. 

In order to allow completely general transformations, the authors of~\cite{naranjo} propose a solution based on histogram matching: ``The purpose is to change each image histogram into a target histogram calculated as average of image histogram and its neighbours''.
 This method is judicious and seems to give good results (an example is available at \textit{http://gpiserver.dcom.upv.es/restoration.html}). However, we will see later its drawbacks and why the scale-time equalization, which has large similarities with it, is more suitable.
%The papers dealing with the flicker as a global degradation are in majority. This leads indeed to faster and simpler algorithms than local treatments, which have to manage with motion detectors. For a local treatment of flicker, see~\cite{roos}. 

A first local treatment of flicker is proposed by Roosmalen et al. in~\cite{roos}. The idea is to split the frame in overlapping blocks, and to consider that the flicker is affine on these blocks. After the local estimation of parameters, a rejection criterion is introduced in order to avoid problems due to local motion or blotches in the correction. However, this method is still sensible to outliers, and suffers from its recursive form, which creates a bias in the correction and remains very sensible to initialization. Ohuchi et al.~\cite{ohuchi} propose a more robust method that models the transformation between two consecutive frames by
$$u_{t+1}(x)=\alpha_t(x) u_t(x)+\beta_t(x)+\gamma_t(x),$$
where $\alpha_t$ and $\beta_t$ are second order polynomials. The coefficients of $\alpha_t$ and $\beta_t$ are estimated by minimizing a function of $\gamma_t$, chosen in order to be robust to outliers. A scale parameter decides if a local change is due to flicker or motion. This method still suffers of its lack of symmetry in the time direction. Moreover, the choice of the scale parameter is critic, and can lead to confuse a severe flicker with motion. Finally, this method relies on a specific (polynomial) model, that might not be well adapted to all examples (see Figure~\ref{superman}).



\subsection{Flicker: local or global ? Brightness axiom.}

Before trying to treat or remove intensity flicker from a sequence, we should wonder how to define it.
%The first question about intensity flicker we have to answer even before trying to treat it is ``how to define it ?''. 
We referred to it as variations of the frame brightness in a movie, but did not specify if those variations could be local in space or should be considered as global. As we said, papers which treat it as a local phenomenon have to involve motion detectors. Indeed, if we consider the very simple case of a dark object moving on a light background, as represented in Figure~\ref{moving_object}, the local histogram of the central region (delimited by a doted line on the figure) changes obviously in time, whereas the global image histogram remains identical.
% If we decided to take local variations into account, a film as presented in Figure~\ref{flip} where the frame is composed of two gray levels which flip from left to right, could be considered as flickering.
%\psfrag{first frame}{\textit{first frame}}
%\psfrag{second frame}{\textit{second frame}}
%\psfrag{third frame}{\textit{third frame}}
%\psfrag{etc...}{\textit{etc...}}
%\begin{figure}[h]
%\epsfxsize=8cm \centerline{\epsfbox{flip.eps}}
%\caption{\em The current frame is composed of two gray levels which flip from left to right. Should this film be considered as flickering or not ?}
%\label{flip}
%\end{figure}
\begin{figure}[htbp]
\centering{
\includegraphics[width=12.0cm]{moving_object}}
\caption{\em Successive frames of a moving object on a white background. The local brightness of the image changes, whereas the global histogram remains constant.}
\label{moving_object}
\end{figure}
In the same way, any motion of an object on a background could be interpreted as local flicker. Consequently, a local treatment of flicker has to involve motion detectors in order to avoid correcting local changes due to motion and not to flicker. Ultimately, even a film composed of images of a centered gaussian noise of standard deviation $\sigma$ is flickering at the scale of the pixel, whereas the global brightness impression does not change. In addition to motion, a local definition of flicker is also much more sensible to global shaking (usual in old films), local blotches, or noise presence. Consequently, such a definition may well mix several phenomena, and depends a lot on the size of the chosen locality. In comparison, a global definition of flicker relies only on the histograms of the frames, which do not change much in case of shaking, object motion or in presence of jitter noise. These are principally the reasons why we chose to give up the use of the spatial and geometrical coherence between the frames, and decided to define flicker as a global phenomenon. 
As a consequence, if $T:u \rightarrow \tilde{u}$ is a flicker (or, in a symmetric way, deflicker) operator, we consider that:

\begin{axiom}{0, Globality}
$$\forall t \in {\mathbb R},\;\forall (x,y) \in \Omega,\; \left(u_t(x)=u_t(y) \Rightarrow \tilde{u}_t(x)=\tilde{u}_t(y)\right),$$
$$ \forall t \in {\mathbb R},\;\forall (x,y) \in \Omega,\; \left(u_t(x)<u_t(y) \Rightarrow \tilde{u}_t(x)<\tilde{u}_t(y)\right).$$
\end{axiom}

This means that $T$ affects each frame of the film by a contrast change. If the original film is $(u_s)_{s \in {\mathbb R}}$, the flicker changes it to $(\ph_s(u_s))_{s \in {\mathbb R}}$, where each $\ph_s$ is a contrast change. As we define it, deflickering is then mostly independent from denoising and from motion detectors.


\subsection{Remarks on Naranjo's method}

As precised in the state of the art, affine methods~\cite{Fer}, besides their sensitivity to initialization, are clearly not sufficient in general to model all the transformations imposed by flicker, even if we suppose that these transformations are global. The deflickering method proposed by V. Naranjo and A. Albiol in~\cite{naranjo} is based on contrast changes: the histogram of a frame $u_t$ is specified on a joint histogram, computed as an average of the histograms of the images $u_s$, $s \in  [t-T,t+T]$. This can be a good and fast method in a number of cases. However, we have seen in chapter~\ref{chapter_midway} the reason why a direct average between two images histograms was not at all a satisfying intermediary between them. Let us generalize this property to the case of image sequences. We have observed in many films that the evolution of the current frame's histogram during time is not always smooth and can present severe jumps. Assume that $u$ is composed of frames all translated from a single image $u_0$: $\forall t \in [a,c], u_t=u_0+\lambda(t)$, $\lambda(t)$ having a discontinuity at $b$, as proposed in Figure~\ref{inversebetter.fig}.

%\psfrag{ha}{$h_a$}
%\psfrag{hb-}{$h_{b^-}$}
%\psfrag{hb+}{$h_{b^+}$}
%\psfrag{hc}{$h_c$}
%\psfrag{ht atb}{$h_{t,\; a \leq t \leq b}$}
%\psfrag{ht btc}{$h_{t,\; b<t\leq c}$}
%\psfrag{time b-}{time $b^{-}$}
%\psfrag{time b+}{time $b^{+}$}
%\psfrag{grey level}{grey level}
\begin{figure}[htbp]
\centerline{
\subfigure{
\includegraphics[width=2.5cm, angle =270]{inversebetter}}}
\centerline{
\subfigure{
\includegraphics[width=1.8cm, angle =270]{moyenne}
\includegraphics[width=1.8cm, angle =270]{inversemoyenne}}}
\caption{\em 
Top: Successive histograms of the frames of a film, with a jump at time $b$. In this case, a direct weighted mean of the sequence of histograms is not adapted, in so far as it creates a new histogram with two modes (bottom left), and therefore stands a chance of making some new structure appear in the film.
Bottom right: Reasonable intermediate histogram.
}
\label{inversebetter.fig}
\end{figure}
%\begin{figure}[h]
%\epsfxsize=8cm \centerline{\epsfbox{inversebetter.eps}}
%\caption{\em Successive histograms of the frames of a film, with a jump at time $b$. In this case, a direct weighted mean of the sequence of histograms is not adapted, in so far as it creates a new histogram with two modes (shown on the left of Fig.\ref{moyenne.fig}), and therefore stands a chance of making some new structure appear in the film. }
%\label{inversebetter.fig}
%\end{figure}
%\begin{figure}[h]
%\centerline{\epsfxsize=4cm \epsfbox{moyenne.eps}
%\epsfxsize=4cm \epsfbox{inversemoyenne.eps}}
%\caption{\em Left: Weighted mean of the previous histograms. Right: Kind of intermediate given by the scale-time equalization.}
%\label{moyenne.fig}
%\end{figure}
For a frame $u_t$ with $t$ near to $b$, a direct weighted mean of the histograms gives a result which looks like the bottom left histogram of the figure. We see that it stands a chance of creating a new histogram with several modes when all the histograms of the original frames were unimodal. The grey levels of the frame, which were concentrated around some level $n_t$, are separated in two distant regions, and this separation can make some new structure appear. In this case, it would be much more natural an respectful of the frame dynamics to define the new histogram as the translation of the previous ones, located around an average value, as the one represented on the bottom right of the figure. The Scale-Time Equalization that we will define in the next section, relies on the same principle as Naranjo's method: replacing each image histogram by a target one, defined as a weighted intermediary between it and its neighbours. However, as we have shown (see chapter~\ref{chapter_midway} for details), the definition of an intermediary between several histograms must be understood  in a ``transport'' sense, and not in an ``average'' sense. 
% TROP COMPLIQUE ICI
%Actually, the main advantage of the Scale-Time Equalization lies on its principle itself: in the case of a film whose all images have the same geometry and only differ by contrast changes, the result of the S.T.E. at scale $s$ is exactly the convolution in time of the frame with the same gaussian at scale $s$ (\textit{ie} that each pixel is smoothed in time by the heat equation). In this limit case, the result of S.T.E. is optimal, all the frames are smoothed pixel by pixel, and tend towards a common image: the average in time of all the frames of the film. But since a deflickering method is only based on the frames histograms (which is the case in the paper of Naranjo and Albiol), the particular case of a film whose all images have the same geometry can be considered as generic. Therefore, among those methods, the Scale-Time Equalization is optimal, in a sense.


\section{Scale-Time Equalization.}

\subsection{Action on level sets. Morphologic axiom.}

As stated before, we impose to our operator $T$ to follow axiom $0$, \textit{i.e.} to act on each image only through a contrast change. It follows that $T$ leaves the topographic map \footnote{ The topographic map of an image $v$ is the set of its level sets, ordered by inclusion and taken independently from their grey levels. If $\ph$ is a strictly increasing function, $\ph(v)$ has the same topographic map as $v$. See~\cite{morel} for more information on topographic maps.} of each $u_t$ unchanged, which naturally raises the question of the action of $T$ on level sets.

Let us start with a very simple example, illustrated by Figure~\ref{fonforme}: let $u$ be a film representing a flickering dark moving object on a flickering lighter background. We argue that in this case, the flicker that affects the object should be treated independently of the flicker that affects the background. This strong assumption compensates the globality imposed by axiom $0$: it localizes the action of the operator $T$ separately on the object and on the background (see also the first example in the experiments section, and Figure~\ref{superman}). 
\begin{figure}[htbp]
\centering{
\includegraphics[width=11.0cm]{fonforme}}
\caption{\em Successive frames of a film, representing a dark moving object on a flickering light background. In this kind of film, a deflickering operator should act independently on the object and on the background. This is the aim of axiom $1$.}
\label{fonforme}
\end{figure}
In this example, the object corresponds to the $p$ darkest pixels of the image, and the background to the $N-p$ lightest ones. If we note, for every $\lambda$ in $[0,1]$,
$${\chi}^{\lambda}(t)=\{x \in \Omega,\; H_t(u_t(x))\leq \lambda \},$$
$${\chi}_{\lambda}(t)=\{x \in \Omega,\; H_t(u_t(x))> \lambda \},$$
then the set ${\chi}^{\lambda}(t)$ corresponds to the $\lambda \%$ darkest pixels of $u_t$, and ${\chi}_{\lambda}(t)$ to the $(1-\lambda) \%$ lightest ones. Thus, the previous statement can be translated by the following axiom,

\begin{axiom}{1, Figure/Background Independence}
For every $\lambda$ in $[0,1]$, the action of $T$ on the sequence $t \rightarrow\chi^{\lambda}(t)$ is independent of the action of $T$ on the sequence $t \rightarrow\chi_{\lambda}(t)$.
\end{axiom}

If this property holds, it is equivalent to say that $T$ acts independently on each ``level set of rank $\lambda$'' sequence.

%This property can be expressed more specifically by the sentence: suppose that, in each image $u_t$, we replace the gray level of the $p$ darkest pixels, by the gray level of the $p^{th}$ darkest pixel (the film thus obtained is called $u^c$), then we state that $T$ should commute with such an operation, \textit{i.e.} that $T(u^c)$ should be exactly the film $T(u)$ whose images have been submitted to the same thresholding. 
%If $\lambda \in [0,1]$, we define the ``rank thresholding operators''  $S_{\lambda}^{\geq}$ and $S_{\lambda}^{\leq}$, which act on each image $u_t$ of a film $u$ in the following way:
%\begin{eqnarray*}
%S_{\lambda}^{\geq}(u_t)(x)&=&u_t(x) \hspace{1cm} \text{ if } H_t(u_t(x)) \leq \lambda \\
%&=& H_t^{-1}(\lambda) \hspace{6mm} \text{ else. }\\
%S_{\lambda}^{\leq}(u_t)(x)&=&u_t(x) \hspace{1cm} \text{ if } H_t(u_t(x)) \geq \lambda\\
%&=& H_t^{-1}(\lambda)  \hspace{6mm} \text{ else. }
%\end{eqnarray*} 



%$S_{\lambda}^{\leq}$ (resp. $S_{\lambda}^{\geq}$) changes the values of a proportion $\lambda$ (resp. $1-\lambda$) of the pixels and all gray levels of $S_{\lambda}^{\leq}(u_t)$ are gray levels of $u_t$ ($S_{\lambda}^{\leq}$ gives to the $\lambda$ darkest pixels of $u_t$ the gray value $H_t^{-1}(\lambda)$, \textit{i.e.} exactly the gray level of rank $\lambda$ in $u_t$). Thus, our previous statement can be summed up by the axiom:

%\begin{axiom}{1, Figure/Background Independence}
%For all $\lambda$ in $[0,1]$, $T$ commutes with $S_{\lambda}^{\geq}$ and $S_{\lambda}^{\leq}$.
%\end{axiom}



This axiom simplifies considerably the possibilities of action for $T$. 
Indeed, let us introduce the set ${\mathcal C}$ of films defined on $\Omega$ and constituted of constant images (\textit{i.e.} each image of the film is a constant, but the value of the constant changes with time). We know from axiom $0$ that ${\mathcal C}$ is stable under the action of $T$. Moreover, there is an obvious bijection between ${\mathcal C}$ and ${\mathcal F_{\mathbb R}}$, the set of real functions. Thus, the action of $T$ on ${\mathcal C}$ can be completely represented by the action of an operator $\breve{T}$ on ${\mathcal F_{\mathbb R}}$. Now, we have the following result:
\medskip
\begin{proposition}
The action of an operator $T$ satisfying axioms $0$ and $1$ only depends on its action on ${\mathcal C}$, the set of films constituted of constant images. More precisely, if $\breve{T}$ denotes the corresponding action on the set of real functions, the action of $T$ on any film $u$ consists in separate actions of the operator $\breve{T}$ on the functions $t \rightarrow H_t^{-1}(\lambda)$.
\label{prop_axioms01}
\end{proposition}

%\medskip
%\begin{demo}
%Axiom 0 implies that $T$ leaves the topographic map of each image unchanged. Thus, if $u$ is a film and $\tilde{u}$ its image by $T$, the level set $\{\tilde{u}_t=\tilde{H}_t^{-1} (\lambda)\}$ is exactly the same as $\{u_t=H_t^{-1} (\lambda)\}$. Therefore, the knowledge of the histogram sequence $(\tilde{H}_t)_{t \in {\mathbb R}}$ determines completely the film $\tilde{u}$.
%Now, $S_{\lambda}^{\geq} S_{\lambda}^{\leq} (u)$ is a film constituted of constant images, corresponding to the real sequence $(H_t^{-1}(\lambda))_{t \in {\mathbb R}}$, and in the same way, $S_{\lambda}^{\geq} S_{\lambda}^{\leq} (\tilde{u})$ is a film constituted of constant images of values $(\tilde{H}_t^{-1}(\lambda))_{t \in {\mathbb R}}$. Axiom 1 implies that $T(S_{\lambda}^{\geq} S_{\lambda}^{\leq} (u))$ is equal to $S_{\lambda}^{\geq} S_{\lambda}^{\leq} (\tilde{u})$, which means that the image of the real sequence $(H_t^{-1}(\lambda))_{t \in {\mathbb R}}$ by $\breve{T}$ is exactly $(\tilde{H}_t^{-1}(\lambda))_{t \in {\mathbb R}}$. To conclude, the knowledge of $\breve{T}$ allows to compute all the rank sequences  $(\tilde{H}_t^{-1}(\lambda))_{t \in {\mathbb R}}$ from $H$, and therefore to determine $\tilde{u}$ from $u$.
%\end{demo}
Each function $t \rightarrow H_t^{-1}(\lambda)$ gives the evolution during the time of the grey levels of rank $\lambda$ in the images of the film.
The study of the action of $T$ on films constituted of constant images is the aim of one of the next subsections.

\subsection{The scale-time structure of deflicker.}
Before studying the particular case of a film of constant images, there is still a general and simple requirement that we can impose on $T$. The kind of transformation that we want to perform should naturally not depend on the choice of the time origin for the film, and should also give the same result if we reverse the time direction.

\begin{axiom}{2, Time Shift Invariance}
$T$ must commute with translations and symmetries in time:
$$\forall u,\; \forall \mu \in {\mathbb R},\;\; T(\tau_\mu (u))=\tau_\mu (T(u)), $$
$$\forall u,\;T((u_{-t}))=(T(u)_{-t}).$$
\end{axiom}

This axiom leads actually to the question of the link between the operator $T$ and the time: if the intensity flicker has to be removed, we must avoid to make disappear the natural variations of luminosity in the film, which are much slower. This need becomes more and more necessary when the length of the sequence increases. Hence, the reduction of flicker should be seen as a scale-time problem. A flicker reduction method should be flexible enough to allow the choice of a ``scale'' of correction, corresponding to the limit between intensity variations due to flicker, and those ``natural'' to the movie. 

A natural way to keep the possibility of luminosity variations from one image to another after the treatment, is to use, instead of $T$, a family $(T_s)_{s \in {\mathbb R}}$ of deflicker operators, the scale parameter $s$ being linked with the depth of correction. Each element of the family is obviously supposed to follow the axioms 0,1 and 2, and the next section should allow to determine the form of the operators $T_s$. 

 

\subsection{The particular case of a film constituted of constant images.}

In this paragraph, we will end up with the formulation of axioms for deflicker. Surprisingly (as shown previously), it is enough to state them in the case of constant images movies. This very intuitive framework will lead to proposition~\ref{prop_ste}.

Now, let $c=(c_t)_{t \in {\mathbb R}} \in {\mathcal C}$, the set of films on $\Omega$ constituted of constant images. We study here the action on $c$ of a family $(T_s)_{s \in {\mathbb R}}$ of operators following axioms $0$ to $2$. First, if all of the constants $c_t$ are identical, equal to the constant $\mu$, we impose naturally that each of the $T_s$ keeps the film unchanged:

\begin{axiom}{3, Preservation of constants}
If  $\exists \mu,\;\forall t \in {\mathbb R},\;c_t=\mu$, then $\forall s,\; T_s(c)=c$.
\end{axiom}

The action of the operators $(T_s)_{s \in {\mathbb R}}$ on a sequence $\{c_t,t \in {\mathbb R}\}$ is equivalent to a smoothing process in one dimension. By making once more the parallel between ${\mathcal C}$ and ${\mathcal F_{\mathbb R}}$, \textbf{we call $(\breve{T}_s)_{s \in {\mathbb R}}$ the corresponding smoothing process on ${\mathcal F_{\mathbb R}}$, in order not to mistake its action for that of $(T_s)_s$}. The results found for $(\breve{T}_s)$ will determine the action of $(T_s)$ on films via its separated actions on the ``rank'' sequences $(H_t^{-1}(\lambda))_t$.
%\footnote{Let us remind that $(H_t^{-1} (\lambda))_t$ is the sequence of gray levels of rank $\lambda$ in $u$.}.

At this time of the reasoning, any family of one dimension smoothing operators following axioms 2 (time shift invariance) and 3 (preservation of the constants) could be considered as convenient for $(\breve{T}_s)$. However, some natural assumptions, as the classical assumptions of scale-space theory, can be made on this process. Several axiomatics are possible (see~\cite{lindeberg} for a review of the main ones), depending on the authors, but they all lead to the same conclusion: the convolution with a gaussian kernel. We choose here the most general list of axioms, as stated in~\cite{morel2}. First, we impose a pyramidal structure on the family, which means that the signal at scale $s$ can be computed from the signal at scale $s-h$, for $h$ small enough. Next, we state that the family $(\breve{T}_s)$ should naturally satisfy the following local comparison principle: if $c$ is locally larger than $c'$, it remains larger for a small enough smoothing. Finally, it seems sensible to impose a regularity assumption on the family $(\breve{T}_s)_{s \in {\mathbb R}}$. All of these assumptions compose the following axiom:



\begin{axiom}{4, Scale-Time Structure of $(\breve{T}_s)$}
The scale-time family $(\breve{T}_s)_{s \in {\mathbb R}}$ is causal, which means that $(\breve{T}_s)_{s \in {\mathbb R}}$
\begin{itemize}
\item is pyramidal: $\breve{T}_{s+h}=\breve{T}_{s+h,s}\breve{T}_s,\; \breve{T}_0=Id$;
\item satisfies a local comparison principle: if $c(t)>c'(t)$ for $t$ in a neighborhood of $t_0$ and $t \neq t_0$ , then for $h$ small enough $$(\breve{T}_{s+h,s}c)(t_0) \geq (\breve{T}_{s+h,s}c')(t_0),$$
 and if $c\geq c' $ everywhere, then $\forall h,\; \breve{T}_{s+h,s}c \geq \breve{T}_{s+h,s}c'$;
\item is regular: for $c$ a quadratic form, there exists a function $F$ continuous with respect to the first variable, such that when $h \rightarrow 0$:
$$\frac{(\breve{T}_{s+h,s}c-c)(x)}{h}\rightarrow F(D^2c(t),Dc(t),t,c(t),s).$$ 
\end{itemize}
\end{axiom}


Finally, for the sake of simplicity, we choose to impose an axiom of linearity on $(\breve{T}_s)_{s \in {\mathbb R}}$.

\begin{axiom}{5, Linearity}
 The scale-time $(\breve{T}_s)_{s \in {\mathbb R}}$ is linear.
\end{axiom}

This last axiom is a deliberated choice which allows to determine completely the action of $(\breve{T}_s)_{s \in {\mathbb R}}$ (see~\cite{morel2} for a proof).

\medskip
\begin{theorem}
Let $(\breve{T}_s)_{s \in {\mathbb R}}$ be a ``scale-time'' family of operators acting on functions $c:{\mathbb R}\rightarrow{\mathbb R}$ and satisfying the axioms 2 to 5. Then, for each function $c:\mathbb{R} \rightarrow \mathbb{R}$, and up to a rescaling $s'=f(s)$, 
$$\breve{T}_s c= G_s *_t c,\text{ where } G_s(t)= \frac{1}{(4 \pi s)^{\frac{1}{2}}} e^{-\frac{t^2}{4s}},$$
and where $*_t$ denotes the convolution in $t$.
\label{theorem_scale_space}
\end{theorem}

%\rem 
Other solutions, non linear, could be considered for the action of the family. The quality of the results given by this specific process will be obviously its best justification. Let us mention that the median filter on a neighboorhood might be an alternative choice, more adapted to scene changes.


\subsection{Scale-Time Equalization (STE).}

The association of proposition~\ref{prop_axioms01} and of the previous theorem gives the following result, where $*_t$ denotes the convolution in the time direction.

\medskip
\begin{proposition}
Let $(T_s)_{s \in {\mathbb R}}$ be a family of operators acting on films and satisfying axioms 0 to 3. We call $(\breve{T}_s)_{s \in {\mathbb R}}$ the family acting on real functions and reproducing the action of $(T_s)$ on ${\mathcal C}$, the set of films of constant images. We suppose that $(\breve{T}_s)_{s \in {\mathbb R}}$ satisfies axioms 4 and 5. 
Then, there exists a rescaling $s'=f(s)$, such that the action of $(T_s)$ on any film $u$ can be described via the formula 
 $$\breve{T}_s(t\rightarrow H_t^{-1}(\lambda))=G_s *_t (t\rightarrow H_t^{-1}(\lambda)),$$
 where
$$ G_s(t)= \frac{1}{(4 \pi s)^{\frac{1}{2}}} e^{-\frac{t^2}{4s}}.$$
\label{prop_ste}
\end{proposition}
\medskip

\begin{demo}
Proposition~\ref{prop_axioms01} tells us that the action of each operator $T_s$ of the family  on a film $u$ can be described by the separated actions of the corresponding operator $\breve{T}_s$ on the functions $t \rightarrow (H_t^{-1}(\lambda))_t$ ($H_t$ being the cumulative histogram of the image $u_t$). Now, theorem~\ref{theorem_scale_space} determines completely the action of the family $(\breve{T}_s)$.
\end{demo}

The previous theorem describes completely the action of a family of operators following the axioms previously stated. This action is nothing more than a convolution of each ``rank function'' of the film by a gaussian. It will be called \textit{Scale-Time Equalization}. In order to improve the understanding of this action, we shall now  study its stability and its effects on different moments of the frames. In the last section, we will experiment it on sequences presenting an artificial or a real flicker.

\subsection{Stability}
First, let us study the effect of this time-smoothing process on the mean of the frames. If we note $m_{u}(t)$ the mean of the image $u_t$, we have:
$$m_{u}(t)=\int_0^1 xh_t(x)dx=1-\int_0^1 H_t(x)dx=\int_0^1 {H_t}^{-1}(x)dx.$$
Consequently, any linear operation on the sequence ${H_t}^{-1}$  generates  the same linear operation on the function $m_{u}(t)$. Hence the following proposition:

\begin{proposition}
$$\forall t_0, \; m_{T_s(u)}(t_0) = G_s*_t(m_u)(t_0).$$
\label{prop_mean}
\end{proposition}

The mean function is smoothed by the heat equation. In the same way, every value $\alpha_t$ which can be written linearly from the values ${H_t}^{-1}(x)$ is also smoothed by the heat equation, as the median, for example, which is actually equal to ${H_t}^{-1}(\frac{1}{2})$. The behaviour of the mean function in a real example and for different choices of $s$ can be observed in the experiment section (Figure~\ref{job} (c)).


The notion of stability here is closely related to the concrete application of the method. Indeed, in the theoretical study, we considered the film $u$ as if it was infinite, which is of course not the case. The movie $u$ has a finite discrete length $P$. In order to apply the previous method, we consider $u$ as a time-periodic function. There is no reason for introducing an interaction between the first and the last image of the film, so we choose to symmetrise $u$ on $[0,2P]$ before its periodisation. Hence, $u$ is considered as periodic of period $2P$.

We will call $f:[0,1]\times[0,2P] \rightarrow [0,1]$ the function $f(\lambda,t)=H^{-1}_t(\lambda)$. So, the process involved consists in a convolution in time by $G_s$ of each periodic function $f(\lambda,.)$. 
We have the following result of convergence:
\medskip
\begin{proposition}
If $\;\forall \lambda \in [0,1],\; f(\lambda,.) \in L^1([0,2P])$, then 
$$ f^s(\lambda,t):= \left(G_s*_t f(\lambda,.)\right)(t) \underset{s \rightarrow +\infty}{\longrightarrow} \frac{1}{2P}\int_0^{2P} f(\lambda,t')dt',$$
 uniformly in  $t$  and  $\lambda$.
\end{proposition}
\medskip

\begin{demo}
If $\lambda$ is given, the Fourier series of  $t \rightarrow f^s(\lambda,t)$ can be expressed in function of that of $f(\lambda,.)$, by:
$$\forall n \in {\mathbb N},\; c_n(f^s(\lambda,.))=c_n(f(\lambda,.)) \times e^{-s (\frac{2\pi n}{P})^2}.$$
Now, if $s>0$, $f^s(\lambda,.)$ is $C^{\infty}$ by construction, and then can be written as the sum of its Fourier series. Consequently, and for $s\geq1$:
$$|f^s(\lambda,t)-\frac{1}{2P}\int_0^{2P} f(\lambda,t')dt'|\leq \sum_{n \neq 0} |c_n(f(\lambda,.))|e^{-s (\frac{2\pi n}{P})^2}\leq \left(\sum_{n \neq 0} |c_n(f(\lambda,.))|e^{-(\frac{2\pi}{P})^2(n^2-1)}\right) e^{-(\frac{2\pi}{P})^2s}.$$
Now, for each $n$, we have $|c_n(f(\lambda,.))|\leq 1$ (because $0\leq f\leq 1$ everywhere), then $f^s(\lambda,t)$ converges toward $\frac{1}{2P}\int_0^{2P} f(\lambda,t)dt$ uniformly in $(\lambda,t)$ when $s \rightarrow +\infty$.
\end{demo}



The smoothing process at scale $s$ changes each inverse cumulative histogram $\lambda \rightarrow H^{-1}_{t_0}(\lambda)$ into $\lambda \rightarrow (G_s*_{t}H_t^{-1}(\lambda))(t_0)$, which converges uniformly, when $s \rightarrow \infty$, towards a limit function  $\lambda \rightarrow \frac{1}{2P}\int_0^{2P}  H_t^{-1}(\lambda)dt$. 
Now, even if $f$ is in $L^1([0,1]\times[0,2P])$ and continuous in $\lambda$,  it is not certain that this limit function is invertible. It is strictly increasing, but its continuity is not guaranteed. For that, we will also suppose that $f$ is equicontinuous in $\lambda$ \footnote{Equicontinuity in $\lambda$ means here that 
$$\forall \epsilon>0,\; \forall x,\; \exists\alpha,\; \forall t \in {\mathbb R},\; \forall y,\;\left(|x-y|\leq\alpha \; \Rightarrow |f(x,t)-f(y,t)|\leq\epsilon\right)$$}. With this hypothesis, we are assured that $\lambda \rightarrow \frac{1}{2P}\int_0^{2P} f(\lambda,t)dt$ (and, in the same way, each $f^s(\lambda,t)$) is an homeomorphism of $[0,1]$. Consequently, we can define the function $H_{lim}:[0,1]\rightarrow [0,1]$:
$$H_{lim}(\lambda)= \left( \frac{1}{2P}\int_0^{2P} H_t^{-1}(\lambda)dt \right)^{-1}.$$ 
Finally, the following result deals directly with the convergence of the cumulative histograms (not the inverse ones) toward $H_{lim}$.


\medskip
\begin{proposition}
If $(t,\lambda) \rightarrow H^{-1}_t(\lambda)$ is in $L^1([0,1]\times[0,2P])$ and equicontinuous in $\lambda$, then, for all $t$, the sequence of functions $(\lambda \rightarrow H^s_t(\lambda))_s$ converges uniformly toward $H_{lim}$ when $s \rightarrow \infty$.
\label{prop_hlim}
\end{proposition}
\medskip


\medskip
\begin{lemme}
Let $(h_s)$ be a sequence of increasing homeomorphisms on $[0,1]$, converging uniformly toward $h$. We also suppose that $h$ is strictly increasing. Then, the sequence $h_s^{-1}$ converges uniformly to $h^{-1}$.
\end{lemme}

\begin{demo}
$h$ is continuous as a uniform limit of continuous functions, and strictly increasing from $[0,1]$ onto $[0,1]$. Thus $h$ is an homeomorphism of $[0,1]$. It follows that $h^{-1}$ is continuous and even uniformly continuous on $[0,1]$. Thus,
$$\forall \epsilon>0,\;\exists \alpha>0,\;\forall (x,y) \in [0,1]^2,\;|x-y|\leq \alpha \Rightarrow |h^{-1}(x)-h^{-1}(y)|\leq \epsilon.$$
Now, $h_s$ converges uniformly toward $h$ on $[0,1]$, so we can write:
$$ \exists A>0,\;\forall s >A,\;\forall x \in [0,1],\;|h(h_s^{-1}(x))-h(h^{-1}(x))|=|h(h_s^{-1}(x))-h_s(h_s^{-1}(x))| \leq \alpha.$$
Thus, $\forall s >A,\;\forall x \in [0,1],\;|h_s^{-1}(x)-h^{-1}(x)|\leq \epsilon$. Hence, $(h_s^{-1})$ converges uniformly to $h^{-1}$ when $s \rightarrow \infty$.
\end{demo}




\begin{demoof}{Proposition~\ref{prop_hlim}}
If $t$ is fixed, the sequence of functions $\lambda \rightarrow (f^s(\lambda,t))$ follows the assumptions of the lemma (each function is an homeomorphism thanks to the hypothesis of equicontinuity on $f$). The uniform convergence is the result of the previous proposition. And finally, $H_{lim}^{-1}$ is strictly increasing as an average of strictly increasing functions.   

\end{demoof}


%For the real sequence presented in the following section, we have computed the limit histogram theoretically (\textit{i.e.} by its formula, cf Figure~\ref{joblimite}) and in practice, as a limit (Figure~\ref{jobhisto}).
%DIRE QUE CES RESULTATS NOUS ENCOURAGEN>>T A PRENDRE UN SIGMA GRAND POUR TOUTE SEQUENCE A PEU PRES COHERENTE, ET QU'ON NE PRECISERA PAS FORCEMENT DANS LA SUITE. 

This stability result supports the idea to use large scales in order to equalize a sequence. In a sense, the scale represents the size of the time neighborhood that we choose to equalize each image of the film. The more the scale is large, the more the final histograms of the sequence will be similar and tend toward $H_{lim}$. If a sequence does not contain scene transitions, which is the case in the experiments of next section, we can consider as reasonable to choose $s \geq 10$.

\subsection{Link with the midway equalization}

As announced in introduction, scale-time equalization can be closely related to the Inverse Average Equalization presented in chapter~\ref{chapter_midway}. This chapter presents a midway image equalization, with the intention of giving the same histogram to a pair of images (a stereo pair, two shots of the same painting, etc...), while keeping their previous grey level dynamics as much as possible. We recall that an axiomatic analysis of the problem, based on the expected results for a short list of key examples,  revealed that if $u_0$ and $u_1$ are the images, the ``right'' intermediate cumulative histogram between $H_0$ and $H_1$ is $\left( \frac{{H_0}^{-1}+{H_1}^{-1}}{2}\right)^{-1} $. 

Now, consider a periodic film $u$, and $(u_n)_{n \in \{0 \dots N-1\}}$ its samples on $\{0,\frac{P}{N},...\frac{(N-1)P}{N}\}$. The previous formula cannot be applied directly to all the frames $(u_n)$ for obvious reasons (as the lack of flexibility), but it can be applied to all the pairs $(H_i,H_{i+1})$ simultaneously: for each $i$, ${H_i}^{-1}$ is then replaced by $\frac{{H_i}^{-1}+{H_{i+1}}^{-1}}{2}$. For the sake of symmetry in the time direction, it has to be followed by the same operation in the reverse direction (${H_i}^{-1}$ replaced by $\frac{{H_{i-1}}^{-1}+{H_{i}}^{-1}}{2}$). The entire operation can finally be summed up by: replace ${H_i}^{-1}$ by $\frac{{H_{i-1}}^{-1}+2{H_{i}}^{-1}+{H_{i+1}}^{-1}}{4}$. When the number $N$ of samples is fixed, the repetition of this operation brings all the histograms of the film closer to each other, and ultimately they all converge toward their inverse mean $(\frac{1}{N}\sum H_i^{-1})^{-1}$. Moreover, we can show, under some general assumptions, that when the number of samples $N$ increases and tends toward $+\infty$, the iteration of this operation converges towards the convolution with a gaussian. This is a well known result in scale-space theory, as stated in~\cite{morel}: ``from the asymptotic viewpoint, all local linear isotropic ``low-pass'' iterated filters are equivalent to the heat equation''.

In order to enounce properly this property in our case, we define the linear operators $L_N:{\mathbb R}^N \rightarrow {\mathbb R}^N$, such that
$$L_N:x=(x_0,x_1,...,x_{N-1}) \rightarrow (\frac{2x_i+x_{i+1}+x_{i-1}}{4})_{i=0...N-1}.$$
We call $\Delta_N=\frac{1}{4}(2\delta_0+\delta_{\frac{P}{N}}+\delta_{-\frac{P}{N}})$, and $S_N$ the sampling operator on $\{0,\frac{P}{N},...\frac{(N-1)P}{N}\}$.
Suppose that $f$ is a periodic real function of period $P$, then we have clearly
$L_N(S_N(f))=S_N(\Delta_N*f)$, and after $n$ iterations~: 
$$\forall N \in {\mathbb N},\;\forall n \in {\mathbb N},\; L_N^{(\circ n)}(S_N(f))=S_N(\Delta_N*^{( n)}f).$$

Finally, the asymptotic property evoked above can be expressed as:

\medskip
\begin{proposition}
Let $f$ be a real periodic function of period $P$, such that its Fourier series $(c_k(f))_{k \in {\mathbb N}} \in  l^1({\mathbb N})$, then:
$$\forall s>0,\;\;||\Delta_N*^{(n)}f- G_s*f||_{\infty} \underset{\frac{n}{N^2} \rightarrow \frac{4s}{P^2},\; n\rightarrow +\infty}{\longrightarrow} 0,$$
and consequently, for all $s>0$: 
$$ \sup_{k \in [0,N-1]} |L_N^{(\circ n)}(S_N(f))(\frac{kP}{N})-G_s*a(\frac{kP}{N})| \underset{\frac{n}{N^2} \rightarrow \frac{4s}{P^2},\; n\rightarrow +\infty}{\longrightarrow}0.$$
\end{proposition}
\medskip

\begin{demo}
$\Delta_N*^{(n)}f$ and $G_s*f$ are periodic functions of period $P$, and can be written as uniform limits of their Fourier series (because $(c_k(f))_{k} \in  l^1({\mathbb N})$). Hence, we have
$$||\Delta_N*^{(n)}f- G_s*f||_{\infty} \leq \sum_{k} |c_k(\Delta_N*^{(n)}f)-c_k(G_s*f)|. \;\;\; \text{ Now,}$$
$$c_k(\Delta_N*^{(n)}f)=\left(\frac{1}{4}(2+e^{-i\frac{2k\pi}{N}}+e^{i\frac{2k\pi}{N}})\right)^n c_k(f)=\cos^{2n}\left({\frac{k\pi}{N}}\right) c_k(f),\;\;\text{ and }$$
$$c_k(G_s*f)=\hat{G_s}(\frac{2k\pi}{P})c_k(f)=e^{-\frac{4k^2 {\pi}^2}{P^2}s}c_k(f).$$ 
Moreover, $(c_k(f))_{k} \in l^1({\mathbb N})$, thus 
$$\forall \epsilon>0,\;\; \exists k_0 \in {\mathbb N},\;\;\;\sum_{|k|> k_0}~|c_k(f)|~<~\frac{\epsilon}{2}.$$ 

Consequently, we can write
$$||\Delta_N*^{(n)}f- G_s*f||_{\infty}\leq \sum_{k} |\cos^{2n} \left(\frac{k\pi}{N} \right)-e^{-\frac{4k^2 {\pi}^2}{P^2}s}| |c_k(f)| \leq \sum_{|k| \leq k_0} |\cos^{2n}\left({\frac{k\pi}{N}}\right)-e^{-\frac{4k^2 {\pi}^2}{P^2}s}||c_k(f)| +\epsilon. $$

If we develop  $\cos^{2n}(\frac{k\pi}{N})$ for $N$ large enough (and $|k|\leq k_0$), it gives
$$\cos^{2n}\left(\frac{k\pi}{N}\right)=e^{-2n \log(1-k^2\pi^2/2N^2+O(k^4/N^4))}=e^{-nk^2\pi^2/N^2+O(nk^4/N^4)},\; \text{ thus, }$$

\begin{eqnarray*}
\sum_{|k| \leq k_0} |\cos^{2n}{\frac{k\pi}{N}}-e^{-\frac{4k^2 {\pi}^2}{P^2}s}||c_k(f)| &\leq& \sum_{|k| \leq k_0} |e^{-k^2 {\pi}^2\left(\frac{n}{N^2}-\frac{4s}{P^2} \right)+\frac{nk_0^4}{N^2}O(\frac{1}{N})}-1||c_k(f)|e^{-\frac{4k^2 {\pi}^2}{P^2}s}\\
&\leq& ||(c_k(f))||_{l^1({\mathbb N})}\sum_{|k| \leq k_0} |e^{-k^2 {\pi}^2 \left(\frac{n}{N^2}-\frac{4s}{P^2} \right)+\frac{nk_0^4}{N^2}O(\frac{1}{N})}-1|\\
\end{eqnarray*}
This sum has a finite number of terms, and each of them tends toward $0$ when $n \rightarrow \infty$ and $\frac{n}{N^2}\rightarrow \frac{4s}{P^2}$, hence the sum tends also toward $0$ under the same conditions. 

\end{demo}

This proposition makes the connection between the iteration of a discrete filter based on midway equalization, and the scale-time equalization presented here. Ultimately, when the number of iterations increases, proportionaly to the square of the number of frames on $[0,P]$, both filters become equivalent.


\section{Some experiments}
We have tested our algorithm on several sequences, presenting either an artificial or a real flicker. The results are presented here via some images of each sequence before and after the equalization process. However, it is not easy to evaluate the quality of the results on still images, and the improvement is much more obvious seeing the films in motion: the sequences used here and their corrections by scale-time equalization can be found at \textit{http://www.cmla.ens-cachan.fr/$\sim$delon}. One of the advantages of the globality hypothesis relies on the speed of the process: for images of 720x576 size, the whole process treats around 4 images by second on a 800 MHz PC, and 18 images by second for a 240x180 size.
Let us begin with two sequences presenting an artificial flicker. 


\begin{figure}[c]
\subfigure[]{
\centerline{
\includegraphics[width=3cm]{superman1}   
\includegraphics[width=3cm]{superman2}   
\includegraphics[width=3cm]{superman3}   
\includegraphics[width=3cm]{superman4}}}
\subfigure[]{
\centerline{
\includegraphics[width=3cm, height=3cm]{histo_superman1}   
\includegraphics[width=3cm, height=3cm]{histo_superman2}   
\includegraphics[width=3cm, height=3cm]{histo_superman3}   
\includegraphics[width=3cm, height=3cm]{histo_superman4}}}
\subfigure[]{
\centerline{
\includegraphics[width=3cm]{out_superman1}   
\includegraphics[width=3cm]{out_superman2}   
\includegraphics[width=3cm]{out_superman3}   
\includegraphics[width=3cm]{out_superman4}}}  
\subfigure[]{
\centerline{
\includegraphics[width=3cm, height=3cm]{histo_out_superman}   
\includegraphics[width=3cm, height=3cm]{histo_out_superman}   
\includegraphics[width=3cm, height=3cm]{histo_out_superman}   
\includegraphics[width=3cm, height=3cm]{histo_out_superman}}  }
\caption{\em (a) Successive images with the same geometry, where flicker has been added independently to the 3 different level sets.
(b) Corresponding histograms. We see that there is no affine transform that maps one histogram on another.
(c) Same images after Scale-Time Equalization at a large scale. The values of the level sets have been regularized in time, and the geometry does not change, hence the four images become identical.
(d) Resulting histograms of the four previous images. As expected, they are identical.}
\label{superman}
\end{figure}




\begin{figure}[c]
\subfigure[]{
\centerline{
\includegraphics[width=5cm]{reuilly_with_flicker_001}   
\includegraphics[width=5cm]{reuilly_with_flicker_010}   
\includegraphics[width=5cm]{reuilly_with_flicker_020}}}
\subfigure[]{
\centerline{
\includegraphics[width=5cm]{histo_reuilly_with_flicker_001}   
\includegraphics[width=5cm]{histo_reuilly_with_flicker_010}   
\includegraphics[width=5cm]{histo_reuilly_with_flicker_020}}}
\subfigure[]{
\centerline{
\includegraphics[width=5cm]{reuilly_restored_001}   
\includegraphics[width=5cm]{reuilly_restored_010}    
\includegraphics[width=5cm]{reuilly_restored_020}}}
\subfigure[]{
\centerline{
\includegraphics[width=5cm]{histo_reuilly_restored_001}   
\includegraphics[width=5cm]{histo_reuilly_restored_010}    
\includegraphics[width=5cm]{histo_reuilly_restored_020}}}
\caption{\em 
(a) Three images of a film to which we added a global and highly non-affine artificial oscillating flicker, and (b) their intensity histograms. 
(c) Same images after Scale Size Equalization at a large scale. The artificial flicker has completely vanished. The original sequence is restored. (d) Intensity histograms of the restored images. We see that they are very close to each other.
}
\label{reuilly}
\end{figure}



\begin{figure}[htbp]
\subfigure{
\centerline{
\includegraphics[width=5cm]{reuilly_noised_flickering_001}   
\includegraphics[width=5cm]{reuilly_noised_flickering_010}    
\includegraphics[width=5cm]{reuilly_noised_flickering_020}}}
\subfigure{
\centerline{
\includegraphics[width=5cm]{reuilly_noised_restored_001}   
\includegraphics[width=5cm]{reuilly_noised_restored_010}    
\includegraphics[width=5cm]{reuilly_noised_restored_020}}}
\caption{\em 
Top: Images of Figure~\ref{reuilly}, to which we added a gaussian noise of standard deviation $\sigma=60$ before adding the flicker.
Bottom: Same images after Scale-Time Equalization.
}
\label{reuilly_noise}
\end{figure}



\subsection{Sequences with an artificial flicker}

The first one is a very simple synthetic case, which tends to illustrate the works of the method. The images of the film, that can be seen on Figure~\ref{superman} (a), are all made from a single image. This original image has only three different grey levels: the first one corresponds to the clothes of the character, the second one to its skin, and the last one to the background. The different images of the film are obtained by making these values vary independently in time (but without changing the global order of the values: the background is always the lighter one, etc...). This way, each image of the film has an histogram composed of three peaks, located at grey values that change in time (Figure~\ref{superman} (b)). In this example the flicker is clearly global, but completely non-affine. It cannot either be modeled by the local model of Ohuchi's paper~\cite{ohuchi}. Moreover, if we tried to replace each histogram by a direct weighted average of its neighbour histograms (such as suggested in Naranjo and Albiol paper~\cite{naranjo}) the result would be catastrophic: it would create histograms with several peaks distributed all over the possible range, which has no sense. Now, as we have seen, the Scale-Time Equalization compute for each level set an average in the time direction of the grey values taken by the set. Which means here that the grey values of the background will be equalized together, etc... All the images of the film here have the same geometry, therefore, at a large scale, all the images obtained are identical (Figure~\ref{superman} (c)). The corresponding limit histogram ((d)) is composed of the same three peaks, located at the computed average values. We can remark that if the character was moving in position from one image to the other, the result would not change, as it just relies on histograms.

The second example is a short film shot outdoor, to which we added an artificial flicker. Concretely, each image $u_t$ is replaced by an image $\ph_t(u_t)$, where $\ph_t$ is a polynomial function whose coefficients change with time. Figure~\ref{reuilly}~(a) shows three images of the degraded film (there is ten frames between two consecutive images), and their intensity histograms, which look pairwise very far from each other. On the same figure, we represented the corresponding restored images and their intensity histograms. We can see that the histograms of the frames after restoration are almost identical, because of the large scale chosen for restoration. The subjective quality of the result is certain: visually, we can not distinguish this restored sequence from the original one (before the degradation). 

This example gives us the possibility to study the sensibility of our algorithm to the presence of noise. Theoretically, if we add a noise $b$ to an image $u$, its intensity distribution  becomes $h_u * h_b$, where $h_b$ is the noise distribution. If the noise is gaussian, the histogram $h_u$ is smoothed by this operation, which should not be at all disturbing for the STE process. If the noise is an impulsive noise, added to $p \%$ of the pixels, its distribution is of the form $h_b=(1-p)\delta_0+p$. Thus, $h_u * h_b= (1-p) h_u +p \bar{h_u}$, which still should not be much disturbing for the restoration process when $p$ is not too large.
In order to test it concretely, we made the following experiment: before the flickering process, we added a gaussian noise of standard deviation $\sigma$ to each image of the original film, and restored this new sequence with our algorithm. For each image $u$ of the original sequence, $u_{noise}$ denotes the corresponding noised image, $u_{noise+flicker}$ the corresponding noised image after the flickering process, and $u_{restored}$ the same image after deflickering. For each image of Figure~\ref{reuilly}, we represented on Figure~\ref{reuilly_noise} the images $u_{noise+flicker}$ and $u_{restored}$ for $\sigma~=~60$. Visually, the results are quite good, even for this large value of $\sigma$. Logically, $u_{restored}$ should be closer to $u_{noise}$ than $u_{noise+flicker}$. In order to verify it, we measured, for different values of $\sigma$, the average $L^2$ norms of the differences $u_{noise}-u_{restored}$ and $u_{noise}-u_{noise+flicker}$ for the three images of Figure~\ref{reuilly}:

\vspace{0.5cm}

\centerline{
\begin{tabular}{|l|l|l|l|l|}
\hline
$\sigma$ (noise std. dev.): & 0 & 10 & 30 & 60 \\
\hline
\multicolumn{5}{|c|}{$\|u_{noise}-u_{noise+flicker}\|_2$}\\
\hline
image 1            & 51.62 &  51.45  & 50.01 & 46.45 \\
image 10           & 15.84 &  15.76  & 15.32 & 14.13 \\
image 20           & 53.98 &  53.74 & 52.25 & 47.97  \\
\hline
\multicolumn{5}{|c|}{$\|u_{noise}-u_{restored}\|_2$}\\
\hline
image 1            &  5.25 &   5.43 &  5.06 &  4.43 \\
image 10           &  3.93 &   4.55 &  4.25 &  4.58 \\
image 20           &  4.74 &   5.20 &  5.70 &  8.16  \\
\hline
\end{tabular}
}
\vspace{0.5cm}


As expected, we see that the method is very robust to gaussian noise. The global $L^2$ difference between each image and its corresponding restored image does not change much when $\sigma$ increases. We begin to see differences around $\sigma=60$, but they remain reasonable: for $\sigma=100$, the ratio $\|u_{noise}-u_{restored}\|_2 / \|u_{noise}-u_{noise+flicker}\|_2$ is still around $1/5$ for most of the images. 
 The results for an impulsive noise are quite similar: for a noise proportion of $30\%$, the previous ratio is still around $1/10$ for images 1 and 20, and around $1/5$ for image 10.


\subsection{Sequences with a real flicker}
The first real sequence is an extract of Chaplin's movie \textit{His New Job} (1915), and has been found on the page proposed by Naranjo and Albiol in their paper~\cite{naranjo}.  Despite the fact that the camera is fixed and the scene is shot indoor, the sequence suffers from a severe real flicker. This proves that the flicker can come from different sources, and be produced by non natural causes (certainly the ageing of the film in this particular case).
%This sequence is quite representative of the fact that flicker can have artificial (\textit{i.e.} not natural) causes: here, the camera is fixed and the scene is shot indoor, yet, the extract suffers from severe flicker. 
Figure~\ref{job} (a) shows three samples of the film, taken at equal intervals of time, and  the same images after the Scale-time Equalization. We can observe (even if it is more obvious seeing the film in motion) that the flicker has globally almost vanished.   
%This observation is confirmed by Figure~\ref{jobhisto}, which presents the cumulative histograms of the four frames before and after the scale-time equalization. As we can see, the four histograms are quite far from each other in the original sequence, and are almost identical after the process. In the end, when the scale tends toward $+\infty$, they all converge toward the theoretical limit histogram as predicted in \textit{Proposition 6}. This theoretical limit is computed and represented in Figure~\ref{joblimite}. 
The same figure shows the time-evolution of the current frame mean when $s$ increases. As predicted in \textit{Proposition~\ref{prop_mean}}, this mean function is just smoothed by the heat equation at scale $s$. When $s \rightarrow \infty$, the mean function converges towards the constant function computed as the average of all the frames means.

The second real example (Figure~\ref{cure}) is an extract of another Chaplin's film, called \textit{The Cure} (1917). The real flicker present in this part of the film is much worse than in the first example. In particular, some images are very dark and low contrasted. After an equalization at a large scale, we can see that the flicker has almost vanished. However, the quantization noise has globally increased, especially in low contrasted zones. This drawback is inherent in any deflickering method, local or global, affine or not: indeed, it appears as soon as the grey level dynamic of an image is enlarged, even locally. A good way to avoid it is to bound the slope of the contrast function that is applied to the image for restoring it.


\begin{figure}[htbp]
\subfigure[]{
\centerline{
\includegraphics[width=5cm]{charlot0}   
%\includegraphics[width=2cm]{charlot20.jpg} 
\includegraphics[width=5cm]{charlot40}   
\includegraphics[width=5cm]{charlot80}}
}
\subfigure[]{
\centerline{
\includegraphics[width=5cm]{out_charlot0}   
%\includegraphics[width=2cm]{out_charlot20.jpg}
\includegraphics[width=5cm]{out_charlot40}   
\includegraphics[width=5cm]{out_charlot80}}}  
\subfigure[]{
\centerline{
\includegraphics[width=7cm]{moyennejob}}}
\caption{\em (a) Three images of Chaplin' s film \textit{His New Job}, taken at equal intervals of time. This extract of the film suffers from a severe real flicker.
(b) Same images after the Scale-Time Equalization at scale $s=100$. The flicker observed before has globally decreased.
(c) Evolution of the mean of the current frame in time and at three different scales. The most oscillating line is the mean of the original sequence. The second one is the mean at scale $s=10$. The last one, almost constant, corresponds to the large scale $s=1000$. As expected from proposition~\ref{prop_mean}, the mean function is smoothed by the heat equation.}
\label{job}
\end{figure}


\begin{figure}[htbp]
\subfigure{
\centerline{
\includegraphics[width=5cm]{charlot2_71}   
\includegraphics[width=5cm]{charlot2_80} 
%\includegraphics[width=2cm]{charlot2_90.jpg}   
\includegraphics[width=5cm]{charlot2_101}}}
\subfigure{
\centerline{
\includegraphics[width=5cm]{out_charlot2_72}   
\includegraphics[width=5cm]{out_charlot2_081}
%\includegraphics[width=2cm]{out_charlot2_091.jpg}   
\includegraphics[width=5cm]{out_charlot2_102}}}  
\caption{\em Top: Three images of Chaplin's film \textit{The Cure}, taken at equal interval of time. This part of the film presents a strong real flicker. Some images in particular are very dark and low contrasted.
Bottom: Same images after a scale-time equalization at a large scale. The flicker has almost vanished.}
\label{cure}
\end{figure}


\section{Conclusion}
This chapter presented a global way of reducing the effects of flicker in films by a scale-time process. This process has been constructed following a group of general and elementary axioms, such as figure/background independence or time-shift invariance, associated with basic axioms of scale-space theory. As a global process, this method is robust to gaussian noise, shaking, and motion. This simple method is more generic than global affine methods, and we have seen why it is more respectful of the grey level dynamics of the frames than the method proposed by Naranjo and Albiol in their paper. The scale-time dimension leads to simple results of stability, ensures the robustness of the method to blotches or impulsive noise, and guarantees that no bias or deviation can appear in time, contrary to recursive methods. Results on sequences containing an artificial or a real flicker are convincing: the subjective quality of the films has clearly improved. In all cases the flicker becomes almost imperceptible. In cases of a flicker mixing both very local changes and global oscillations, this process can still be used as a first step of deflickering before a local treatment. Now, it is clear that such a deflickering process looses its sense in the presence of scene transitions. It should therefore be associated with a well chosen time-cut detector (for instance, see~\cite{naranjo2}). 

%The limit histogram produced by this process can be useful for other applications. For example, suppose that a sequence of frames is globally too dark or not enough contrasted. Each image can be corrected separately, but it produces a different contrast change for each frame, and can be long and tedious. Instead, the contrast change can be directly computed from the joint histogram and applied to all the frames. More generally, the common histogram can be used in any case of a group of images whose histograms are close. 








%\begin{figure}
%\centerline{\epsfxsize=2cm
%\epsfbox{job_115.ps}
%\epsfxsize=2cm
%\epsfbox{job_125.ps}
%\epsfxsize=2cm
%\epsfbox{job_135.ps}
%\epsfxsize=2cm
%\epsfbox{job_145.ps}}
%\caption{\em Four images of the Chaplin' s film \textit{His New Job}, taken at equal intervals of time. This extract of the film suffers from severe flicker.}
%\label{job}
%\end{figure}

%\begin{figure}
%\centerline{\epsfxsize=2cm
%\epsfbox{result_115.ps}
%\epsfxsize=2cm
%\epsfbox{result_125.ps}
%\epsfxsize=2cm
%\epsfbox{result_135.ps}
%\epsfxsize=2cm
%\epsfbox{result_145.ps}}
%\caption{\em The same images of the film after the Scale-Time Equalization (described in \textit{Proposition 3}) at scale $s=10$. The flicker observed before has globally decreased.}
%\label{job_restored}
%\end{figure}

%\begin{figure}
%\centerline{\epsfxsize=4cm
%\epsfbox{jobmoyenne.ps}}
%\caption{\em Evolution of the mean of the current frame at different scales. As shown in $\textit{Proposition 4}$, the mean function is smoothed by the heat equation.}
%\label{jobmoyenne}
%\end{figure}

%\begin{figure}
%\centerline{\epsfxsize=4cm
%\epsfbox{job_histos.ps}
%\epsfxsize=4cm
%\epsfbox{jobrestored_histos.ps}}
%\caption{\em Cumulative Histograms of the four frames of Fig.\ref{job} before and after the Scale-Time Equalization. We can observe that the four cumulative histograms converge toward the theoretical limit histogram of Fig.\ref{joblimite}, as stated in \textit{Proposition 6}.}
%\label{jobhisto}
%\end{figure}

%\begin{figure}
%\centerline{\epsfxsize=4cm
%\epsfbox{joblimite.ps}}
%\caption{\em Theoretical limit histogram of the algorithm, \textit{i.e.} for a periodic film of period $P$: $H_{lim}(\lambda)= \left( \frac{1}{P}\int_0^{P} H_t^{-1}(\lambda)dt \right)^{-1}$ }
%\label{joblimite}
%\end{figure}




%\begin{figure}
%\centerline{\epsfxsize=1.6cm
%\epsfbox{cure_72.ps}
%\epsfxsize=1.6cm
%\epsfbox{cure_78.ps}
%\epsfxsize=1.6cm
%\epsfbox{cure_84.ps}
%\epsfxsize=1.6cm
%\epsfbox{cure_90.ps}
%\epsfxsize=1.6cm
%\epsfbox{cure_96.ps}}
%\caption{\em Five images of the Chaplin's film \textit{The Cure}, taken at equal interval of time.}
%\label{cure}
%\end{figure}

%\begin{figure}
%\centerline{\epsfxsize=1.6cm
%\epsfbox{result_72.ps}
%\epsfxsize=1.6cm
%\epsfbox{result_78.ps}
%\epsfxsize=1.6cm
%\epsfbox{result_84.ps}
%\epsfxsize=1.6cm
%\epsfbox{result_90.ps}
%\epsfxsize=1.6cm
%\epsfbox{result_96.ps}}
%\caption{\em Same images after a scale-time equalization at a large scale. The flicker has almost vanished.}
%\label{cure_restored}
%\end{figure}




