\documentclass[twocolumn]{article}
%\documentstyle[twocolumn,/mann/a/a/bigu/inputs/tinycaptionfont]{article}
\newcommand{\us}{U.S. Pat. }
\newcommand{\path}{/mann/a/a/bigu/}
\input{/mann/a/a/bigu/extracommands.tex}
\input{/mann/a/a/bigu/figs/psfig.sty}
\input{/mann/a/a/bigu/figs/figcommands.tex}
%%% no effect in latex 2.09 or 2e \input{\path/inputs/tinycaptionfont.sty}
\usepackage{/mann/a/a/bigu/inputs/tinycaptionfont} % works for latex2e
\usepackage{amsmath}
\usepackage{amsfonts}

% Set dimensions of columns, gap between columns, and paragraph indent
\setlength{\textheight}{8.875in}
\setlength{\textwidth}{6.875in}
\setlength{\columnsep}{0.3125in}
\setlength{\topmargin}{0in}
\setlength{\headheight}{0in}
\setlength{\headsep}{0in}
\setlength{\parindent}{1pc}
\setlength{\oddsidemargin}{-.1875in}  % Centers text.
\setlength{\evensidemargin}{-.1875in}

% Add the period after section numbers.  Adjust spacing.
\newcommand{\Section}[1]{\vspace{-8pt}\section{\hskip -1em.~~#1}\vspace{-3pt}}
\newcommand{\SubSection}[1]{\vspace{-3pt}\subsection{\hskip -1em.~~#1}
        \vspace{-3pt}}
\begin{document}
\date{} % Don't want date printed

\section{Introduction to comparametric equations}

\subsection{What does a camera measure}
Cameras are often present in computer vision systems that are
used to measure various quantities, yet an often overlooked
question is ``what does a camera itself measure''?

We know it measures light, in some sense, but we wish to understand exactly
what is being measured.

A camera actually acts as an array of sensors that each measure light.
In an electronic camera these sensors may simply be the pixels.  At
one time, cameras once used a thin light sensitive material called ``film''
or glass plates, having some kind of light sensitive
chemical such as silver salts deposited thereupon, such that the
sensing surface was continuous rather than being on a discrete
lattice of pixels.  In this case
we simply consider a small patch of the sensing surface that will
ultimately be (usually on a discrete lattice) scanned for further analysis.

Let us construct (either as a thought experiment, or as a do experiment
that can actually be carried out) a simple one pixel camera.  Once we
understand what one pixel measures, we can then better understand what can
be measured from many pixels working together.

Perhaps the simplest way to construct our one pixel camera is to use
a light sensor.  The cheapest and most common kinds of light sensors
are usually photoresistors, such as the cadmium sulphide photocells
found in the small controllers that automatically turn streetlights
on after dark.

Cameras measure electromagnetic energy, but
unlike an ideal radio receiving antenna that one might connect to a
spectrum analyzer, a camera measures electromagnetic radiation only
within a certain region of the electromagnetic spectrum.
Typically cameras are sensitive to that which we call light,
e.g. to electromagnetic energy falling close to the visible,
the infrared, or the ultraviolet portion of the spectrum.  Moreover, the
camera's sensitivity to light is not very flat across the
spectrum over which it is sensitive.  Thus a camera is certainly not
a radiometer, and the measurements that it makes are certainly not
radiometric.

Moreover, cameras have spectral sensitivities that are quite different
from that of the human eye, and are therefore certainly not
photometers.

Different kinds of cameras have different spectral sensitivity profiles,
that are neither flat (radiometric) nor match the human eye (photometric),
and therefore cameras are referred to as quantimetric devices.
A quantimetric measurement refers to a measurement that can be quantified
in some measurable units, where the camera itself can be used as the
measurement instrument.  The quantimetric unit, typically
denoted by the letter $q$, is usually made relative
to some reference value, $q_0$, so that it can be expressed as a ratio, or
as a logarithmic ratio (often in decibels).

In this experiment we will consider quantimetric
analysis of the Radio Shack Cadmium Sulphide photocell
because it is readily available as a test sample
(Radio Shack part number 276-1657).  However any surplus
photocell, or even a real camera, may be used.

\subsubsection{Construction of a one pixel camera}
Photoresistors are devices in which resistance is a function
of incident light.
Typically an increase in light results in a decrease in resistance.
Most are known to obey an empirical law: 
\begin{equation}
R = R_0 q^{-\gamma},
\label{eq:photoresistor}
\end{equation}
where $\gamma$ is usually a positive constant less than one.
The fact that $\gamma$ is less than one indicates that the
photocell tends to compress dynamic.  Cameras also compress
dynamic range in a similar way.
Values for the constants of the Radio Shack 276-1657 CDS cell
are $R_0=2000\Omega$ (for $q$ in units of Lux) and $\gamma=0.75$.
(See Chapter 3 of the
University of Toronto Physical Sciences PSCB01H3S course text,
http://www.utsc.utoronto.ca/~quick/PSCB01H3S/Manual/).

Let us assume that a camera is an instrument for converting light
into numbers.  We will thus construct a camera from the photocell
by simply connecting it to an ohm meter.  A satisfactory ohm meter
might be the MICRONTA 22-201U which has a moving coil meter movement,
as shown in Fig.~\ref{fig:multimeter}.
\begin{figure}
 \figc{photocell_experiment/multimeter_crop_grey_und.eps,width=3in}
 \caption{Typical resistance meter used in photocell experiment.}
 \label{fig:multimeter}
\end{figure}

The needle swings to the right when the resistance is less.
Like most similar ohm meters, $\infty$ is at the far left and
$0$ is at the far right, with intermediate values in between.

It is more convenient to consider conductance, which is the
reciprocal of resistance, and to define the camera's response
function, $f$, as conductance of the photocell. Equation 
(\ref{eq:photoresistor}) now becomes:
\begin{equation}
  f(q) = \beta q^\gamma,
\end{equation}
where $\beta=1/R_0$.
The quantimetric function, $f$,
increases with increasing quantity of light, $q$.
Thus the needle on the meter will be at the far left when $f=0=q$,
and will swing more to the right as $f$ and $q$ increase.

We wish to determine
$f$ as a function of $q$ (e.g. suppose that we did not already know
the relationship between $f$ and $q$).
Suppose that we have just a lamp and the camera (photocell plus ohm meter),
together with a piece of black cardboard we can use to cover half of the
lamp, but that we have no other measurement instruments.
We assume that the lamp is round or has some other shape that makes it
easy to cover up exactly half of it.

We are therefore able to cover half of the lamp, and then
point the lamp at the camera (sensor), and take a reading $f(q_0)$,
(See Fig~\ref{fig:photocell_experiment}(a)), and then
uncover the lamp while leaving it exactly in the same place.
Uncovering the lamp exactly doubles the quantity of light received
by the camera (sensor), so that we then know what $f(2q_0)$ is.
(See Fig~\ref{fig:photocell_experiment}(b).)
\begin{figure}
 \figc{photocell_experiment/photocell_experiment.idraw,width=3in}
 \caption{Photocell experiment: for each of  various distances between
          the lamp and the camera, a reading is taken with the lamp
          exactly half covered, versus with the lamp not covered.
          Other than the camera, lamp, and black card, no other devices
          (such as rulers or other measurement instruments) are needed
          in order to characterize the response of the photocell to light.}
 \label{fig:photocell_experiment}
\end{figure}
Although we do not know the absolute quantity $q_0$, we do know the
relative quantity $2q_0/q_0 = 2$, e.g. we do know the fact that we have
exactly doubled the quantity of light, and we can record a set of ordered
pairs $(f(q_0),f(2q_0))$.  We can put the lamp at various different
distances from the camera (sensor) and for each such lamp position,
we can generate an ordered pair.
Let us suppose
that we take ten such ordered pairs of measurements, e.g. continuing with
$(f(q_1),f(2q_1))$ and so on, all the way up to $(f(q_9),f(2q_9))$.
We can plot these ordered pairs on a graph, as shown in
Fig~\ref{fig:photocell_experiment_comparametric_plot}.
\begin{figure}
 \figc{photocell_experiment/photocell_experiment_comparametric_plot.idraw,width=3in}
 \caption{Datapoints from photocell experiment: ordered pairs of points
          taken by reading the camera with the lamp uncovered
          and exactly half covered.}
 \label{fig:photocell_experiment_comparametric_plot}
\end{figure}
This is just like an $(x,y)$ plot, except that the axes are actually
functions, $f(q)$, and $f(2q)$ instead of just scalar quantities.
The first axis is $f$ so
it is convenient to use the next letter of the alphabet, $g$, after $f$
in order to denote the other axis.  Thus we have an $(f,g)$ plot ---
a plot of a function against a plot of a function of a function, where
$g=f(2q)$.

We can fit a curve through the points.
The solid line shows one possible curve, namely
a straight line of slope approximately $1.68$.
The dotted line shows another possible curve.  Repeated measurements,
however, lead us to believe that the relationship is simply $g=1.68f$,
as shown by the solid line.

This is simply a plot of the photocell's response function $f(q)$ against
a contracted (squashed in) version of the same function $f(2q)$.
Such a plot is called a {\em comparametric plot}.

The notion of a parametric plot is familiar to almost everyone.
A parametric plot of a circle, for example, is simply a set of
ordered pairs $(rcos(\theta),rsin(\theta))$ where the parameter $\theta$
takes us counterclockwise around the circle.
A comparametric plot is just a special kind of parametric plot, where
both axes pertain to the same function at different rates.

\subsubsection{Solving comparametric equations}
From the comparametric plot shown in
Fig~\ref{fig:photocell_experiment_comparametric_plot}
we have determined that $g=f(2q)=1.68f(q)$.  This equation,
$g=1.68f$ is called a comparametric equation.
In general, solving a comparametric equation $g(f(q))=f(kq)$,
for some comparametric ratio $k$ (in this case $k=2$)
means determining a family of possible functions $f(q)$ that
satisfy this equation.

In our specific case, therefore, we wish to know what possible
functions $f(q)$ give a straight line (of slope $1.68$) when plotted
against themselves contracted (by a factor of 2).

Fig~\ref{fig:photocell_experiment_unrolled} depicts two plots,
one being a smooth function $f(q)$ who's comparametric plot is a
straight line of slope $1.68$, and the other being a quasi-periodic function
who's comparametric plot is also a straight line of slope $1.68$.
\begin{figure}
 \figc{photocell_experiment/photocell_experiment_unrolled.idraw,width=3in}
 \caption{Two examples of possible solutions to the comparametric function
          $g=1.68f$.  One solution, plotted as the thick line,
          is given by $f(q)=q^0.75$.
          Another solution plotted as the thin line, consists of
          a triangular wave, square-shaped wave, and round shaped wave
          between $q$ and $2q$ so that we can see how the waveform
          has comparametric periodicity.  In each ``period'', the function
          is stretched by
          a factor of two as we go to the right (or contracted by a factor of
          two as we go to the left), and
          composed by a factor of $g()$ as we go to the right,
          or $g^{-1}()$ as we go to the left.  This phenomenon is called
          comparametric periodicity. %% (or comparametric ambiguity).
          Thus there is a comparametric uncertainty in the solution to
          a comparametric equation.
          %%of Fig.~\protect\ref{fig:photocell_experiment_comparametric_plot}.
         }
 \label{fig:photocell_experiment_unrolled}
\end{figure}
Both of these functions have the same comparametric plot.
Both are solutions to the comparametric equation $g=1.68f$.

The quasi-periodic function illustrates that any function
can be specified on, for exmaple, the interval from $q$ to $2q$,
and then merely replicated into the interval to the
right scaling by $(2*,g\circ)$, e.g.
by stretching to twice the width and composing to
$g()$ of the height,
in this case, merely multiplying by $1.68$ times the height, since
in this specific case, $g$ is linear.
This recipe can be applied recursively in both the left and right
directions.  Therefore, in general, solutions to comparametric equations
are not unique.  However, we might choose a function that is semimonotonic,
with semimonotonic slope, semimonotonic curvature,
(and so-on, including possibly further derivatives),
of which $f(q)=\beta q^\gamma$ is the preferred general solution
to $g=2^\gamma f$.

\subsection{Directly solving a comparametric equation by unrolling while
         collecting the data}
We started by knowing the response function of the photocell,
e.g. knowing the solution of the comparametric equation, and then
confirming that this known function was in fact a solution.

Now suppose we did not know the solution, and did not know
how to solve the comparametric equation, in general.

In this case, we can construct a simple way of simultaneously collecting
comparametric data, and arriving at a numerical solution to the
comparametric equation, namely, to obtain samples of the function $f(q)$.

Refer back to Fig~\ref{fig:photocell_experiment}(a) where half the
lamp is blocked with the black cardboard, to obtain $f(q_0)$.
Now suppose we unblock the lamp, as shown in
Fig~\ref{fig:photocell_experiment}(b) to obtain
$f(2_{q_0})$.  The IMPORTANT NEXT STEP is to now cover exactly half the lamp again
and then MOVE THE LAMP TOWARD THE PHOTOCELL UNTIL THE OBSERVED METER READING
IS EXACTLY THE SAME AS IT WAS WHEN THE LAMP WAS NOT COVERED.
Thus the situation as shown in Fig~\ref{fig:photocell_experiment}(c)
will be that $q_1=2q_0$.

The procedure is repeated.  Uncover the lamp to obtain
$f(2q_1)=f(4q_0)$.  Then cover it again, and move it still closer
to the sensor, until the reading is the same as it was in
Fig~\ref{fig:photocell_experiment}(d).
Then uncover the lamp again, to obtain
$f(4q_1)=f(8q_0)$.

Plotting these data points will provide the eight points denoted as
filled in black circles in Fig~\ref{fig:photocell_experiment_unrolled}.
Of course we still have the coparametric uncertainty of what should
be inserted between the points, but if a power law is suspected, we
can assume the smooth monotonic function of the form
$f=\beta q^\gamma$ and determine the value of $\gamma$ from the
data.

\subsection{Doing the experiment in bulk}
With an actual camera, there are multiple pixels, not just one.
So rather than exactly doubling the exposure by using a black card
to cover half the lamp, suppose that we take two pictures of the same
subject matter, the two pictures differing only
in exposure.  Suppose that one picture is exatly twice the exposure of the
other.

Pictures usually consist of a two dimensional lattice of pixels,
upon which falls a two dimensional distribution of light $q(x,y)$ for
the first picture, and $2q(x,y)$ for the second picture (because the
exposure is twice as much for the second picture.
Thus the two pictures may be written as:
\begin{eqnarray}
  v_f &=& f(q(x,y))\\
  v_g &=& f(2q(x,y)) = g(q(x,y)).
\end{eqnarray}

A typical size for a picture is an array that is
480 pixels high and 640 pixels wide (same aspect ratio
as standard NTSC television aspect ratio, namely 4:3).
Let us consider a simpler example, namely two pictures that are each
3 pixels high and 4 pixels wide:
\begin{equation}
 v_f = \left[ \begin{array}{cccc}
                           1 & 3 & 2 & 3\\
                           3 & 2 & 1 & 2\\
                           0 & 0 & 2 & 0
                    \end{array}
            \right];
 v_g = \left[ \begin{array}{cccc}
                           2 & 3 & 3 & 3\\
                           2 & 2 & 2 & 2\\
                           0 & 1 & 3 & 0
                    \end{array}
            \right].
\end{equation}

In this example, assume that we have a 2 bit camera, such that it
has grey values that go from 0 to 3.

We now introduce the so-called comparagram.
The comparagram is a two dimensional array of size $M$ by $N$
where $M$ is the number of grey values in the first image, and
$N$ is the number of grey values in the second image,
where entry $J[m,n]$ is a count of how many times a pixel
in image 1 has greyvalue $m$ and the corresponding pixel in
image 2 has greyvalue $n$.
In this case
both images have 4 grey values, so the comparagram is a 4 by 4 matrix:
\begin{equation}
	\nonumber
	\begin{bmatrix}
		2& 1& 0& 0 \\
		0& 0& 2& 0 \\
		0& 0& 2& 2 \\
		0& 0& 1& 2 
	\end{bmatrix}.
\end{equation}

Summing across rows gives the histogram of the first image:
\begin{equation}
	\nonumber
	h_f = \begin{bmatrix}3 &2& 4& 3\end{bmatrix}.
\end{equation}

Summing down colums gives the histogram of the second image,
\begin{equation}
	\nonumber
	h_g = \begin{bmatrix}2& 1& 5& 4\end{bmatrix}.
\end{equation}

\section{Typical cameras}
Some video cameras function much like the photocell, but with a value of
$\gamma = 0.54$ instead of the $\gamma$ values of $0.6$ to $0.9$ that
are typical of photocells.

However, most cameras follow a more complicated law than the simple
power law.  In particular, various laws such as a simple 2 parameter law
$(\frac{q^a}{q^a+1})^c$ have been proposed~\cite{intelligentimageprocessing}
and used in various research applications such as wearable imaging
systems~\cite{intelligentimageprocessing}, computer vision, and
robotics~\cite{candocia2} %Candocia_FCRAR2002.pdf

More generally, we begin without any specific assumptions about the
response function, $f$, by first constructing the comparagram from
two differently exposed pictures of the same subject matter.
See Fig.~\ref{inputpictures}(a) and Fig.~\ref{inputpictures}(b).
\begin{figure}
 \figlcrabc{1.1in}{hart_house_soldiers_tower_newer/s013.eps,width=1in}
           {1.1in}{hart_house_soldiers_tower_newer/s016.eps,width=1in}
           {1.1in}{hart_house_soldiers_tower_newer/s035.eps,width=1in}
 \caption{Differently exposed pictures of the same subject matter
          arising from changes in camera settings or from camera motion.
          (a) When light colored objects enter the field of view,
          such as when a bright sky takes up a good portion of the image,
          the exposure will typically be reduced.
          (b) To obtain detail in darker areas of the image the exposure
          may be increased.  Here the exposure has been increased by a factor
          of two.
          (c) A change in composition (e.g. looking at darker subject matter
          to the right) gives rise to a change in exposure (in this case,
          the exposure also increased by a factor of two).
         }
 \label{inputpictures}
\end{figure}
Typically a difference in exposure will result in any two
successive frames, due to some amount of camera motion,
in the sense that most cameras have some kind of automatic exposure mechanism.
Typically, due to noise in images (sensor noise, as well as
the inter-frame motion artifacts, etc), comparagrams do not provide points
that only lie on a slender curve.
More typically, comparagrams
are define a cloud of points clustered along an underlying curve.
Thus slenderization of the comparagram~\cite{intelligentimageprocessing}
is a typical first step in recovery of the comparametric function, $g(f)$.
See Fig.~\ref{comparaslim}
\begin{figure}
 \figc{photocell_experiment/comparagram_to_comparagraph.idraw,width=2.7in}
 \caption{{\bf Slenderizing a comparagram by marginalization:}
          A comparagram is constructed from the two differently exposed
          pictures of Fig.~\protect\ref{inputpictures}(a)
          and Fig.~\protect\ref{inputpictures}(b).  The dynamic range of
          comparagrams tends to be quite high, so here it is displayed on
          a logarithmic scale, $log(J+\epsilon)-log(\epsilon)$,
          $epsilon>0$ preventing calculation of $log(0)$ (and thresholding
          noise below -60dB or so).  Next summing down columns produces
          the marginal $h_f$ along the $f$ axis.
          Summing along rows produces the marginal $h_g$ along the $g$ axis.
          Whatever tone scale is selected for the optimal
          display of the comparagram (typically logarithmic or power law)
          will affect $h_f$ and $h_g$, so $h_f$ and $h_g$ are typically
          logarithmic histograms (or power law compressed histograms).
          Cumulative sums are taken (giving logarithmic cumulatives
          or power law cumulatives).  The comparagram is then re-constructed
          from only its marginals, such that only a slender ridge remains.
          When the width of this slender ridge is collapsed to zero,
          the result is referred to as a {\em comparagraph} of the underlying
          {\em comparamateric function}\protect\cite{intelligentimageprocessing}.
         }
 \label{comparaslim}
\end{figure}

\section{Constructing a Comparagraph from a Comparagram}
Ideally, a comparagram is a function which plots $f(q)$ against $f(2q)$ 
which appears much like the solid line in 
Fig.~\ref{fig:photocell_experiment_comparametric_plot}.
Unfortunately, the comparagram does not usually appear as this ideal function.
Rather, the comparagram appears as a cloud of points around the function.
Three methods are commonly used for  recovering the underlying comparametric
function, for example, first moments may be calculated down each of the 
columns of the comparagram or across each row of the comparagram. Or,
a maximum likelyhood estimator can be used to  pick the indices of
the comparagram which have the highest values as entries. 
Alternatively, a combination of row and column calculations could be taken.
However, due to the nature of the comparagram,  
he marginals of the comparagram may be used. This method is referred to
as the cumulagram algorithm.

\subsection{The cumulagram and it's computation}
Looking at the previous 
example, the histogram of the first image is: $\{3,2,4,3\}$. The corresponding 
histogram of the second image is $\{2,1,5,4\}$. If each position of the
histogram is numbered from $0$ to $3$, the first histogram has 3 entries
in it's first position. We then ask, ``how far must one look into
the second histogram to account for all of the data in the first
histogram's first position?''. 
To simplfy this task the histograms are converted to 
cumulatives, such that each entry of the cumulative expresses how much of
the data is present at each point of the corresponding histogram. 
This implies that the cumulative of the first histogram is
$\{3,5,9,12\}$. The cumulative of the second histogram is $\{2,3,8,12\}$.

Looking at the first entry of the first cumulative, there are 3 data points.
We now progress through the
second cumulative until all three data points have been account for. The 
first entry in the second cumulative is $2$, which does not account for 
all of the data. The second entry is $3$ which accounts for all of the 
data in the first cumulagram entry exactly. For this reason the first cumulagram
entry is 1 (as 1 is the index of the second cumulative where all of the
data has been accounted for). Continuing the process, the second entry in
the first cumulative is 5. Looking at the second cumulative, the second 
entry is 3 and therefore does not account for enough data, however, the third 
entry is 8, which accounts for too much of 
the data. Thus, we must interpolate between these two points (1 and 2) to 
find a reasonable value. Following this method,  
the third value will fall between 
2 and 3, and finally the last value will be exactly 3.

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
RESULTS:
%   USING PGMTOPPM:
%image 0 to image 1  not aligned 1.991235 aligned 1.908436
%image 1 to image 2  not aligned 3.517230 aligned 2.745831
%image 2 to image 3  not aligned 0.866383 aligned 2.146798
%image 3 to image 4  not aligned 1.042952 aligned 2.011035
%image 4 to image 5  not aligned 1.343583 aligned 1.719070
%   USING GIMP:
%image 0 to image 1  not aligned 2.530293 aligned 2.011216
%image 1 to image 2  not aligned 3.444645 aligned 4.051448
%image 2 to image 3  not aligned 2.785258 aligned 1.984015
%image 3 to image 4  not aligned 2.771012 aligned 1.996743
%image 4 to image 5  not aligned 2.226825 aligned 1.986862
Results are shown in Table~\ref{estkresults}.
\begin{table} \begin{center} \begin{tabular}{|c|c|c|} \hline \hline
Iteration 0 &  Iteration 1 &  True value\\
\hline
 2.530293   &   2.011216  &   2  \\
 3.444645   &   4.051448  &   4  \\
 2.785258   &   1.984015  &   2  \\
 2.771012   &   1.996743  &   2  \\
 2.226825   &   1.986862  &   2
\\ \hline \hline
\end{tabular} \end{center}
\caption[]{\small
         Comparison of aaaaaaaaa.}
\label{estkresults}
\end{table}
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa

%To understand a cumulagram, a simple example of an alternate method of 
%producing a comparagram may be illustrative. In the text 
%\cite{intelligentimageprocessing} Mann gives the example of two tape 
%recorders playing back the same recording. One tape recorder plays back
%at twice the speed of the second. Suppose that the material recorded 
%which is shared by the tape recorders is a simple beep which has a
%frequency of 10 beeps per second on the slow tape recorder and 20 beeps
%per second on the fast tape recorder. 
%
%Using the previous notation, $f(1) = 10$, $g(1) = 20$, $f(2) = 20$, 
%$g(2) = 40$. Also $\gamma(10) = 20$ and $\gamma(20) = 40$. If again
%no knowledge of the original functions is known, but $\gamma$ is known,
%then    

%%%\bibliographystyle{apalike}
\bibliographystyle{unsrt}
\bibliography{\path/conf/chirplet}

\end{document}


