## Archive for July, 2008

### Red Flashlights

July 28, 2008

Some time ago I read an article on a forward operating base (FOB) of the U.S. Marines somewhere in Afghanistan. Because of the threat of rocket attacks, the Marines on that FOB practice strict “light discipline” at night: there are shutters on the windows, no white lights are allowed, and people move around using small red-lensed flashlights.

This reminded me of when I was a kid and watched those Vietnam War movies in which U.S. infantry soldiers used flashlights that looked like this:

The intriguing thing is that the soldiers used red filters on their flashlights. “Why red?”, I wondered back then. Well, 15 or 16 years later, I still don’t know the reason.

Now that I am a bit more educated, I can think of two possible reasons why red flashlights may be a good idea:

• physics: it may happen that photons in the “red” part of the visible spectrum undergo stronger attenuation than “green” or “blue” photons. Or then, perhaps “red” photons are scattered differently than visible photons of other colors. If that’s the case, red flashlights allow their bearers to see what’s around them, but are harder to notice from far away.
• physiology: the human eye is more sensitive to some visible wavelenghts than others. At night, white light causes the pupil to shrink, thus impairing night vision. It seems that red light does not cause such pupil-shrinkage, so night vision won’t be decreased. Supposedly, this is why red lights are used to illuminate aircraft cockpits at night.

Therefore, I suppose that red flashlights are a good idea for both physical and physiological reasons. I searched for some material on this on the internet, and I found some stuff (like this discussion), but nothing very scientific.

Can anyone come up with a reasonable scientific explanation why the military uses flashlights with red filters? I have been waiting for a good answer for almost two decades, and your input will be appreciated.

### Playing with Permutations

July 24, 2008

Let’s play a game:

You build an ordered list $y = (y_1, y_2, \ldots, y_n)$ of $n$ real numbers, and you conceal it from me. You then compute $c_k = \sum_{i=1}^n y_i^k$ for each $k \in \{1,2,\ldots,n\}$, and you give me the $n$-tuple $c = (c_1, c_2, \ldots, c_n)$. Finally, I build a list $x = (x_1, x_2, \ldots, x_n)$ of $n$ real numbers such that $\sum_{i=1}^n x_i^k = c_k$ for all $k \in \{1,2,\ldots,n\}$. Can I conclude that my list is a permutation of yours (or equal to it)?

__________

Each ordered list of $n$ elements is an $n$-tuple. We can also think of an ordered list of $n$ reals as a vector in $\mathbb{R}^n$, where the list’s $i$-th element is the vector’s $i$-th entry.

The following 3-stage diagram hopefully clarifies the essence of this $2$-player game:

where I am player #1, and you’re player #2. The game’s three stages are:

1. player #2 builds an ordered list $y \in \mathbb{R}^n$, but player #1 doesn’t have access to it.
2. player #2 gives player #1 the $n$ “measurements” $c = (c_1, c_2, \ldots, c_n)$, where $c_k = \sum_{i=1}^n y_i^k$.
3. player #1 builds ordered list $x \in \mathbb{R}^n$ from $c = (c_1, c_2, \ldots, c_n)$ such that $\sum_{i=1}^n x_i^k = c_k$ for all $k \in \{1,2,\ldots,n\}$.

We know that it’s always possible to build list $x$, because if $x$ is equal to $y$ or a permutation of $y$, then all $n$ equality conditions

$\begin{array}{rl} \displaystyle\sum_{i=1}^n x_i &= c_1\\ \displaystyle\sum_{i=1}^n x_i^2 &= c_2\\ \vdots\\ \displaystyle\sum_{i=1}^n x_i^n &= c_n\\\end{array}$

will be satisfied. What we don’t know is whether any list $x$ that satisfies the equality conditions will be a permutation of $y$. In more rigorous terms: if $x, y$ are permutations of one another, then it is necessary that the $n$ equalities hold. What we would like to know is whether the fact that the $n$ equalities hold is sufficient for us to conclude that $x, y$ are permutation of one another.

But how can player #1 build the desired ordered list? A possibility would be for player #1 to solve the following system on polynomial equations in variables $x_1, x_2, \ldots, x_n$

$\begin{array}{rl} x_1 + x_2 + \ldots + x_n &= c_1\\ x_1^2 + x_2^2 + \ldots + x_n^2 &= c_2\\ \vdots\\ x_1^n + x_2^n + \ldots + x_n^n &= c_n\\\end{array}$

where $c$ is a contant, and $x$ is a variable.

The game I propose on this post stems from two closely related problems I have been thinking of since January 2008. I have written a few posts on these problems already:

### The mysterious Lena

July 22, 2008

Anyone who has ever worked on Digital Image Processing is surely acquainted with the image of Lena (aka: “Lenna”):

I doubt there’s one single book on Digital Image Processing that does not contain this image. The Lena photo can be found on countless scientific papers. Numerous algorithms have been tested using her photo. Lena is definitely a celebrity in the Image Processing community.

But, who is the mysterious Lena after all?!? She’s Lena Söderberg (b. 1951), a Swedish model who is also known by her maiden name Lena Sjööblom / Lenna Sjööblom. She appeared in the centerfold of the November 1972 issue of the Playboy magazine. In mid-1973, engineers at the Signal & Image Processing Institute (SIPI) were searching for good test images. Someone found a copy of the November 1972 issue of the Playboy magazine, and the engineers scanned the centerfold photo of Lena. Over the past decades, the Lena image has been the de facto standard for testing Image Processing algorithms. The mysterious Lena is considered the “First Lady of the Internet”, and an “Information Age Madonna”. Apart from Mona Lisa, no image has been studied harder.

In 1988, Lena Söderberg was pleasantly amused to find out what had happened to her picture. In 1997, she was a guest at the 50th annual Conference of the Society for Imaging Science and Technology, where she was busy signing autographs, posing for pictures, and giving a presentation about herself.

__________

Related:

### Bust of Mystery

July 15, 2008

Ippolita Maria Sforza (1445-1488) lived in Italy during the Renaissance. She was a member of the powerful Sforza family from Milan.

[ the marble bust of Ippolita Maria Sforza, by Francesco Laurana ]

Ippolita was the mother of Isabella di Aragona (1470-1524), who is also known as “Isabella of Aragon” or “Isabella of Naples”. You may have never heard of Isabella di Aragona, but perhaps you have seen her portrait numerous times: it is argued that Isabella is the model for Leonardo da Vinci‘s immortal painting, the Mona Lisa.

[ Is she Isabella di Aragona? ]

I am more than happy to leave that speculation to the art historians.

__________

The bust of Ippolita Maria Sforza

In 1488, artist Francesco Laurana (1430–1502) sculpted a bust of Ippolita Maria Sforza. It is believed that Ippolita died in 1488, so the sculpture was probably crafted in Ippolita‘s last days.

Here’s the twist: it’s also argued that the bust is not of Ippolita Maria Sforza, but of Isabella di Aragona instead!!! It seems that Isabella was quite a mystery woman:

• she may be the Mona Lisa.
• she may also be the model for the bust believed to be of her mother’s.
• she may even have been married to Leonardo da Vinci and given birth to his children.

Who knows?! Let’s take a look at the photo of the bust. Does it look like the model was 43-year-old Ippolita, or 18-year-old Isabella? Draw your own conclusions.

To make things even more confusing and uncertain, there’s also Ippolita Sforza (born in 1481), who was the daughter of a cousin of Isabella di Aragona! Don’t laugh: this younger Ippolita Sforza had a daughter who was also named Ippolita!! This is truly a biographer’s nightmare.

If the  bust was indeed crafted in 1488,  it’s practically impossible that the model is 7-year old Ippolita Sforza. Therefore, for the sake of clarity, when I say “Ippolita Sforza” I mean Ippolita Maria Sforza.

__________

3-D model of the bust

Art History may be fascinating, but I am more interested in technology. What led me to write this post is that there’s a 3-D model of the bust of Ippolita Maria Sforza. The bust was scanned by the Visual Computing Lab of the ISTI – CNR. The original 3-D model has 500K faces (each face is a polygon, a triangle to be precise) and is available at this model gallery (it can also be found here). You can download the 500K model in two formats:

You can visualize and process these models using MeshLab, for example. There are other software tools, such as VRMesh Studio, but I like MeshLab because it is free, open source, and very user-friendly.

Visualizing the 500K model with MeshLab, we have:

[ 500K model rendered with smoothed mesh polygons ]

This model’s mesh is quite fine. A coarser model would allow us to see the triangle mesh on the model’s surface. MeshLab comes with a sample 50K model (in PLY format) of the bust of Ippolita (a decimation by a factor of 10 of the original 500K model). This 50K model looks like:

[ 50K model rendered with flat mesh polygons ]

Taking a closer look one can see the triangle mesh more clearly:

[ close-up of  Ippolita's face (50K model) ]

I really like meshed models. I don’t know why.

I used VRMesh Studio to export both these models in point cloud format (a ASCII text file where each row contains the 3 coordinates of each point in the cloud). This might come handy if I ever feel like processing the point cloud in MATLAB.

### Playing with SymPy

July 5, 2008

I have been playing with SymPy lately. SymPy is, basically, a Python library for Symbolic Mathematics. It’s precisely the kind of CAS I was looking for: simple, lightweight, easy to use, syntactically tasteful, open-source, and free. SymPy just makes sense. Simplicity über alles.

SymPy was started in 2005, by Ondřej Čertík, a Physics student from Czech Republic. Kudos to Ondřej for his initiative! And thanks to all of those who contributed to the SymPy project! Here are some slides on SymPy, by Ondřej:

You can download SymPy from here. If you don’t have Python installed in your computer, you can play with the SymPy online shell (which runs on the Google App Engine).

__________

An example

Let’s consider the system of polynomial equations in $\mathbb{R}[x_1, x_2, x_3]$

$\begin{array}{rl}x_1 + x_2 + x_3 = y_1 + y_2 + y_3 \\x_1^2 + x_2^2 + x_3^2 = y_1^2 + y_2^2 + y_3^2\\x_1^3 + x_2^3 + x_3^3 = y_1^3 + y_2^3 + y_3^3\end{array}$,

where $y = (y_1, y_2, y_3) \in \mathbb{R}^3$ is a known vector (whose entries are distinct). We will denote $x = (x_1, x_2, x_3)$. Let function $g_k: \mathbb{R}^3 \rightarrow \mathbb{R}$ be defined as

$g_k(z) = \displaystyle\sum_{i=1}^3 z_i^k$.

The system of polynomial equations can thus be rewritten as

$\begin{array}{rl}p_1(x) = 0\\p_2(x) = 0\\p_3(x) = 0\end{array}$

where $p_k(x) = g_k(x) - g_k(y)$ for all $k \in \{1,2,3\}$. According to my conjecture, this system of equations should have exactly $3! = 6$ solutions. Solving the system is not very easy because the equations $p_k(x) = 0$ are nonlinear in variables $x_1, x_2, x_3$. A CAS would be useful.

For example, we could implement function $g_k: \mathbb{R}^3 \rightarrow \mathbb{R}$ with the following Python script:

def g(z,k):
"""Computes g_k(z), where z is a list of reals and k is a positive integer"""

# checks function arguments for errors
if len(z)==0:
return "ERROR: First argument must be a non-empty list of symbols!"
if (type(k) != int) or (k < 1):
return "ERROR: Second argument must be a positive integer!"

# computes g_k(z) and returns it
acc = 0
for i in range(0,len(z)):
acc += (z[i])**k
return acc



We could then compute the Gröbner basis of the set of polynomials $\{p_1(x), p_2(x), p_3(x)\}$, and the solutions of the system of polynomial equations for a given $y$, say, $y = (1,2,3)$:

from sympy import *

# number of equations and symbolic variables
n = 3

# defines set S = {1, 2,..., n}
S = range(1,n+1)

# declares symbolic variables
x = [Symbol('x%d' % i) for i in S]

# initializes y vector
#y = [Symbol('y%d' % i) for i in S]
y = S

# defines system of polynomial equations in variables [x1, x2, x3]
P = [g(x,k) - g(y,k) for k in S]

# computes Groebner basis and solutions of the system of polynomials
GB = groebner(P, order='lex')
Sols = solve_system(P)

# prints results
print "Groebner basis: %s" % GB
print "Solutions: %s" % Sols
print "There are %d solutions." % len(Sols)



The output is:

• Gröbner basis: the Gröbner basis is a set of three polynomials $\{b_1(x), b_2(x), b_3(x)\}$, where

$\begin{array}{l} b_1(x) = -6 + x_1 + x_2 + x_3\\ b_2(x) = 11 - 6 x_2 - 6 x_3 + x_2 x_3 + x_2^2 + x_3^2\\ b_3(x) = -6 + 11 x_3 - 6 x_3^2 + x_3^3\end{array}$.

• Solutions: there are $3! = 6$ solutions

$\{(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)\}$.

As expected, the solutions of the system of polynomial equations are the $3! = 6$ permutations of the elements of $y = (1,2,3)$. Of course, this does not prove the conjecture. All it proves is that my conjecture works for the particular case where $n=3$ and $y = (1,2,3)$.

__________

Related: