Math still not the answer

I wrote a quick (but not very elegant) python script to retrieve locally enough data from www.metacritic.com for pattern recognition purposes. The main goal is to help me decide how much I will enjoy a movie, before watching it. I included the script at the end of the post, in case you want to try it yourself (and maybe improve it too!). It takes a while to complete, although it is quite entertaining to see its progress on screen. At the end, it provides with two lists of the same length: critics, a list of str containing the names of the critics, and scoredMovies, a list of dict containing, at index k, the evaluation of all the movies scored by the critic at index k in the previous list.

For example:

>>> critics[43]

‘James White’
>>> scoredMovies[43]

{‘hall-pass’: 60,
‘the-karate-kid’: 60,
‘the-losers’: 60,
‘the-avengers-2012′: 80,
‘the-other-guys’: 60,
‘shrek-forever-after’: 80,
‘the-lincoln-lawyer’: 80,
‘the-company-men’: 60,
‘jonah-hex’: 40,
‘arthur’: 60,
‘vampires-suck’: 20,
‘american-reunion’: 40,
‘footloose’: 60,
‘real-steel’: 60}

The number of scored films by critic vary: there are individuals that took the trouble to evaluate up to four thousand flicks! Note also that the names of the movies correspond with their web pages in www.metacritic.com. For example, to see what critics have to say about the “Karate Kid” and other relevant information online, point your browser to www.metacritic.com/movie/the-karate-kid.

Feel free to download a copy of the resulting data [here] (note it is a large file: 1.6MB).

But the fact that we have that data stored locally allows us to gather that information with simple python commands, and perform many complex operations on it.

Sometimes Math is not the answer

I would love to stand corrected in this case, though. Let me explain first the reason behind this claim—It will take a minute, so bear with me:

Say there is a new movie released, and you would like to know how good it is, or whether you and your partner will enjoy watching it together. There are plenty of online resources out there that will give you enough information to make an educated opinion but, let’s face it, you will not have the complete picture unless you actually go see the movie (sorry for the pun).

For example, I fell for “The Blair Witch Project:” their amazing advertising campaign promised me thrill and originality. On top of that, the averaged evaluation of many movie critics that had access to previews claimed that this was a flick not to be missed… Heck, I even bought the DVD for my sister before even watching it!—She and I have a similar taste with respect to movies. The disappointment was, obviously, epic. Before that, and many a time afterwards, I have tripped over the same stone. If nothing else, I learned not to trust commercials and sneak previews any more (“Release the Kraken!,” anyone?)

The only remaining resource should then be the advice of the knowledgeable movie critics—provided you trust on their integrity, that is. Then it hit me: My taste in movies, so similar to my sister’s, could be completely different to that of the “average critic”. Being that the case, why would I trust what a bunch of experts have to say? The mathematician in me took over, and started planning a potential algorithm:

What if?

Sara, Spencer and Cam (left to right) discussing their projects in office hour

“What if?” is a truly powerful question. It is the question that separates the child from the adult; the student from the professional. Average students will go through the motions of a course and ask themselves many times: “What is the point of all this?” On the other hand, the notable students on their way to excellence will ask themselves: “How can I profit from this?” It is these inquiring minds who make it at the end: they are a pleasure to work with, they have the drive and the passion to get the job done, enjoy the process, and they are more likely to give their future employers more of their time in pursue of solutions—not because there is monetary or status gain alone, but because their commitment is only matched with their skill and curiosity.

It is a thrill to witness your own students pose that “What if?” question to themselves, and take steps to accomplish that little dream with the knowledge obtained in class. This semester, I had been blessed with a group of extremely talented people in all my different teaching assignments—especially those in my course on elementary differential equations.

Edge detection: The Convolution Approach

Today I would like to show a very basic technique of detection based on simple convolution of an image with small kernels (masks). The purpose of these kernels is to enhance certain properties of the image at each pixel. What properties? Those that define what means to be an edge, in a differential calculus way—exactly as it was defined in the description of the Canny edge detector. The big idea is to assign to each pixel a numerical value that expresses its strength as an edge: positive if we suspect that such structure is present at that location, negative if not, and zero if the image is locally flat around that point. Masks can be designed so that they mimic the effect of differential operators, but these can be terribly complicated and give rise to large matrices.

The first approaches were performed with simple kernels. For example, Faler came up with the following four simple masks that emulate differentiation:

Note that, adding all the values of each matrix, one obtains zero. This is consistent with the third property required for our kernels: in the event of a locally flat area around a given pixel, convolution with any of these will offer a value of zero.

Read more…

OpArt

OpArt is, by definition, a style of visual art based upon optical illusions. Let it be a painting, a photograph or any other mean, the objective of this style is to play with the interaction of what you see, and what it really is. A classical OpArt piece involves confusion by giving impression of movement, impossible solids, hidden images, conflicting patterns, warping, etc. And of course, Mathematics is a perfect vehicle to study—and even perform—this form of art.

In this post I would like to show an example of how to use trivial mathematics to implement a well-known example (shown above) in with the tikz package, and leave as homework another more interesting example.

Observe first the image above: the optical effect arises when conflicting concentric squares change the direction of their patterns. You may think that the color is the culprit of this effect but, as you will see below, it is only the relationship between the pure black-and-white patterns what produces the impression of movement.

So you want to be an Applied Mathematician

The way of the Applied Mathematician is one full of challenging and interesting problems. We thrive by association with the Pure Mathematician, and at the same time with the no-nonsense, hands-in, hard-core Engineer. But not everything is happy in Applied Mathematician land: every now and then, we receive the disregard of other professionals that mistake either our background, or our efficiency at attacking real-life problems.

I heard from a colleague (an Algebrist) complains that Applied Mathematicians did nothing but code solutions of partial differential equations in Fortran—his skewed view came up after his naïve observation of a few graduate students working on a project. The truth could not be further from this claim: we do indeed occasionally solve PDEs in Fortran—I give you that—and we are not ashamed to admit it. But before that job has to be addressed, we have gone through a great deal of thinking on how to better code this simple problem. And you would not believe the huge amount of deep Mathematics that are involved in this journey: everything from high-level Linear Algebra, Calculus of Variations, Harmonic Analysis, Differential Geometry, Microlocal Analysis, Functional Analysis, Dynamical Systems, the Theory of Distributions, etc. Not only are we familiar with the basic background on all those fields, but also we are supposed to be able to perform serious research on any of them at a given time.

My soon-to-be-converted Algebrist friend challenged me—not without a hint of smugness in his voice—to illustrate what was my last project at that time. This was one revolving around the idea of frames (think of it as redundant bases if you please), and needed proving a couple of inequalities involving sequences of functions in —spaces, which we attacked using a beautiful technique: Bellman functions. About ninety minutes later he conceded defeat in front of the board where the math was displayed. He promptly admitted that this was no Fortran code, and showed a newfound respect and reverence for the trade.

It doesn’t hurt either that the kind of problems that we attack are more likely to attract funding. And collaboration. And to be noticed in the press.

Alright, so some of you are sold already. What is the next step? I am assuming that at his point you own your Calculus, Analysis, Probability and Statistics, Linear Programming, Topology, Geometry, Physics and you are able to solve most known ODEs. From here, as with any other field, my recommendation is to slowly build a Batman belt: acquire and devour a sequence of books and scientific articles, until you are very familiar with their contents. When facing a new problem, you should be able to recall from your Batman belt what technique could work best, in which book(s) you could get some references, and how it has been used in the past for related problems.

Following these lines, I have included below an interesting collection with the absolutely imprescindible books that, in my opinion, every Applied Mathematician should start studying:

Smallest Groups with Two Eyes

Today’s riddle is for the Go player. Your task is to find all the smallest groups with two eyes and place them all together (with the corresponding enclosing enemy stones) in a single board. Let me give you some tips first:

• Smallest groups in the corner: In the corner, six stones are the minimum needed to complete any group with two eyes. There are only four possibilities, and I took the liberty of placing them on the board for you:

  

• Smallest groups on the side: Consider any of the smallest groups with two eyes on a side of the board. How many stones do they have? [Hint: they all have the same number of stones] How many different groups are there?
• Smallest groups in the interior: Consider finally any of the smallest groups with two eyes in the interior of the board. How many stones do they have? [again, they all have the same number of stones]. How many different groups are there?

Since it is actually possible to place all those groups in the same board, this will help you figure out how many of each kind there are. Also, once finished, assume the board was obtained after a proper finished game (with no captures): What is the score?

The ultimate metapuzzle

If you have been following this blog for a while, you already know of my fascination with metapuzzles. I have recently found one of the most beautiful examples of these riddles in this August’s edition of Ponder This, and following the advice of Travis, I will leave it completely open for the readers to give it a go. Enjoy!

A mathematician wanted to teach his children the value of cooperation, so he told them the following:

“I chose a secret triangle for which the lengths of its sides are all integers.

To you my dear son Charlie, I am giving the triangle’s perimeter. And to you, my beloved daughter Ariella, I am giving its area.

Since you are both such talented mathematicians, I’m sure that together you can find the lengths of the triangle’s sides.”

Instead of working together, Charlie and Ariella had the following conversation after their father gave each of them the information he promised.

Charlie: “Alas, I cannot deduce the lengths of the sides from my knowledge of the perimeter.”

Ariella: “I do not know the perimeter, but I cannot deduce the lengths of the sides from just knowing the area. Maybe our father is right and we should cooperate after all.”

Charlie: “Oh no, no need. Now I know the lengths of the sides.”

Ariella: “Well, now I know them as well.”

Find the lengths of the triangle’s sides.

Where are the powers of two?

The following construction gives an interesting pairing map between the positive integers and the lattice of integer-valued points in the plane:

• Place at the origin.
• For each level populate the points of the plane on the square with vertices starting from at the position and going counter-clockwise.

  

After pairing enough positive integers on the lattice, pay attention to the powers of two: they all seem to be located on the same two horizontal lines: and

Is this statement true?

Geolocation

Recall the First Spherical Law of Cosines:

Given a unit sphere, a spherical triangle on the surface of the sphere is defined by the great circles connecting three points , , and on the sphere. If the lengths of these three sides are (from to (from to and (from to and the angle of the corner opposite is then

In any decent device and for most computer languages, this formula should give well-conditioned results down to distances as small as around three feet, and thus can be used to compute an accurate geodetic distance between two given points in the surface of the Earth (well, ok, assuming the Earth is a perfect sphere). The geodetic form of the law of cosines is rearranged from the canonical one so that the latitude can be used directly, rather than the colatitude, and reads as follows: Given points and with positions and respectively, the distance between the two points is given by the following formula.

where is the radius of the Earth in miles (well, ok, the average radius of the Earth…)

A nice application of this formula can be used for geolocation purposes, and I recently had the pleasure to assist a software company (thumb-mobile.com) to write such functionality for one of their clients.

Go to www.lizardsthicket.com in your mobile device, and click on “Find a Location.” This fires up the location services of your browser. When you accept, your latitude and longitude are tracked. After a fast, reliable and resource-efficient algorithm, the page offers the location of the restaurant from the Lizard’s chain that is closest to you. Simple, right?

Boundary operators

Consider the vector space of polynomials with coefficients on a field , with the obvious sum of functions and scalar multiplication. For each , consider the subspaces spanned by polynomials of order ,

These subspaces have dimension Consider now for each the maps defined in the following way:

where if and otherwise.

Schematically, this can be written as follows

and it is not hard to prove that these maps are homeomorphisms of vector spaces over

Notice this interesting relationship between and

The kernel of and the image of are isomorphic!

The reader will surely have no trouble to show that this property is satisfied at all levels: As a consequence, for all

We say that a family of homomorphisms are boundary operators if for all If this is the case, then trivially The example above is a bit stronger, because of the isomorphism of both subspaces.

So this is the question I pose as today’s challenge:

Describe all boundary operators

Include a precise relationship between kernels and images of consecutive maps.

The Cantor Pairing Function

The objective of this post is to construct a pairing function, that presents us with a bijection between the set of natural numbers, and the lattice of points in the plane with non-negative integer coordinates.

We will accomplish this by creating the corresponding map (and its inverse), that takes each natural number and drops it at a location in the lattice, as the following diagram suggests:

El País’ weekly challenge

For a while now, the Spanish newspaper “El País” has been posing a weekly mathematical challenge to promote a collection of books, and celebrate a hundred years of their country’s Royal Mathematical Society.

The latest of these challenges—the fourth—is a beautiful problem in combinatorics:

Consider a clock, with its twelve numbers around a circle: Color each of the twelve numbers in either blue or red, in such a way that there are exactly six in red, and six in blue. Proof that, independently of the order chosen to color the numbers, there always exists a line that divides the circle in two perfect halves, and on each half there will be exactly three numbers in red, and three numbers in blue.

While there are many different ways to solve this challenge, I would like to propose here one that is solely based upon purely counting techniques.

Read more

Math Genealogy Project

I traced my mathematical lineage back into the XIV century at The Mathematics Genealogy Project. Imagine my surprise when I discovered that a big branch in the tree of my scientific ancestors is composed not by mathematicians, but by big names in the fields of Physics, Chemistry, Physiology and even Anatomy.

There is some “blue blood” in my family: Garrett Birkhoff, William Burnside (both algebrists). Archibald Hill, who shared the 1922 Nobel Prize in Medicine for his elucidation of the production of mechanical work in muscles. He is regarded, along with Hermann Helmholtz, as one of the founders of Biophysics.

Thomas Huxley (a.k.a. “Darwin’s Bulldog”, biologist and paleontologist) participated in that famous debate in 1860 with the Lord Bishop of Oxford, Samuel Wilberforce. This was a key moment in the wider acceptance of Charles Darwin’s Theory of Evolution.

There are some hard-core scientists in the XVIII century, like Joseph Barth and Georg Beer (the latter is notable for inventing the flap operation for cataracts, known today as Beer’s operation).

My namesake Franciscus Sylvius, another professor in Medicine, discovered the cleft in the brain now known as Sylvius’ fissure (circa 1637). One of his advisors, Jan Baptist van Helmont, is the founder of Pneumatic Chemistry and disciple of Paracelsus, the father of Toxicology (for some reason, the Mathematics Genealogy Project does not list any of these two in my lineage—I wonder why).

There are other big names among the branches of my scientific genealogy tree, but I will postpone this discovery towards the end of the post, for a nice punch-line.

Posters with your genealogy are available for purchase from the pages of the Mathematics Genealogy Project, but they are not very flexible neither in terms of layout nor design in general. A great option is, of course, doing it yourself. With the aid of python, GraphViz and a the sage library networkx, this becomes a straightforward task. Let me show you a naïve way to accomplish it:

Basic Statistics in sage

No need to spend big bucks in the purchase of expensive statistical software packages (SPSS or SAS): the R programming language will do it all for you, and of course sage has a neat way to interact with it. Let me prove you its capabilities with an example taken from one of the many textbooks used to teach the practice of basic statistics to researchers of Social Sciences (sorry, no names, unless you want to pay for the publicity!)

Estimating Mean Weight Change for Anorexic Girls

The example comes from an experimental study that compared various treatments for young girls suffering from anorexia, an eating disorder. For each girl, weight was measured before and after a fixed period of treatment. The variable of interest was the change in weight; that is, weight at the end of the study minus weight at the beginning of the study. The change in weight was positive if the girl gained weight, and negative if she lost weight. The treatments were designed to aid weight gain. The weight changes for the 29 girls undergoing the cognitive behavioral treatment were

A Homework on the Web System

In the early 2000′s, frustrated with the behavior of most computer-based homework systems in the market, my advisor—Bradley Lucier—decided to take matters into his own hands, and with the help of a couple of students, developed an amazing tool: It generated a great deal of different problems in Algebra and Trigonometry. A single problem model had enough different variations so that no two students would encounter the same exercise in their sessions. It allowed students to input exact answers, rather than mere calculator approximations. It also allowed you to input your answer in any possible legal way. In case of an error, the system would occasionally indicate you where the mistake was produced.

It was solid, elegant, fast… working in this project was sheer delight. The most amazing part of it all: it only took one graduate student to write the codes for the problems and checking for validity of answer. Only two graduate students worked in the coding of this project, with the assistance of several instructors, and Brad himself. He wrote a fun article explaining how the project came to life, enumerating the details that made it so solid, and showing statistical evidence that students working with this environment benefitted more than with traditional methods of evaluation and grading. You can access that article either [here], or continue reading below.

Apollonian gaskets and circle inversion fractals

Recall the definition of an iterated function system (IFS), and how on occasion, their attractors are fractal sets. What happens when we allow more general functions instead of mere affine maps?

The key to the design of this amazing fractal is in the notion of limit sets of circle inversions.

Toying with basic fractals

I will skip all the mathematical theory behind Fractals (dimensions, measures, etc) to focus directly into the description and implementation of some of the most basic examples. In this post, I will cover the ideas behind three classical techniques:

• Iterated function systems
• Membership tests
• Lindenmayer systems

Unusual dice

I heard of this problem from Justin James in his TechRepublic post My First IronRuby Application. He tried this fun problem as a toy example to brush up his skills in ruby:

Roll simultaneously a hundred 100-sided dice, and add the resulting values. The set of possible outcomes is, of course, Note that there is only one way to obtain the outcome 100—all dice showing a 1. There is also only one way to obtain the outcome 10000—all dice showing 100. For the outcome 101, there are exactly 100 different ways to obtain it: all dice except one show a 1, and one die shows a 2. The follow-up question is:

Write a (fast) script that computes the different ways in which we can obtain each of the possible outcomes.

Read more…

Wavelets in sage

There are no native wavelet packages in sage. But there is a great module in python that contains, among other things, forward and inverse discrete wavelet transforms (for one and two dimensions). It comes bundled with seventy-six wavelet filters, and allows support to build your own! The name is PyWavelets, written by Tariq Rashid, and can be retrieved from pypi.python.org/pypi/PyWavelets. In order to install it in sage, take the following steps:

Read more…

Edge detection: The Scale Space Theory

Consider an image as a bounded function with no smoothness or structure assumptions a priori. Most relevant information of a given image is contained in the contours of the mapped objects: Think for example of a bright object against a dark background—the area where these two meet presents a curve where the intensity varies strongly. This is what we refer to as an “edge.”

Initially, we may consider the process of detection of an edge by the simple computation of the gradient This gradient should have a large intensity and a direction which indicates the perpendicular to the curve. It therefore looks sound to simply compute the gradient of and choose the points where these values are large. This conclusion is a bit unrealistic for two reasons:

1. The points where the gradient is larger than a given threshold are open sets, and thus don’t have the structure of curves.
2. Large gradient may arise in certain locations of the image due to tiny oscillations or noise, but completely unrelated to the objects being mapped. As a matter of fact, there is no reason to assume the existence or computability of any gradient at all in a given digital image.

Read more…

Bertrand Paradox

Classically, we define the probability of an event as the ratio of the favorable cases, over the number of all possible cases. Of course, these possible cases need to be all equally likely. This works great for discrete settings, like dice rolls, card games, etc. But when facing non-discrete cases, this definition needs to be revised, as the following example shows:

Consider an equilateral triangle inscribed in a circle. Suppose a chord of the circle is chosen at random. What is the probability that the chord is longer than a side of the triangle?

First example	Second example	Third example

Read more…

Voronoi mosaics

While looking for ideas to implement voronoi in sage, I stumbled upon a beautiful paper written by a group of japanese computer graphic professionals from the universities of Hokkaido and Tokyo: A Method for Creating Mosaic Images Using Voronoi Diagrams. The first step of their algorithm is simple yet brilliant: Start with any given image, and superimpose an hexagonal tiling of the plane. By a clever approximation scheme, modify the tiling to become a voronoi diagram that adaptively minimizes some approximation error. As a consequence, the resulting voronoi diagram is somehow adapted to the desired contours of the original image.

(Fig. 1)	(Fig. 2)	(Fig. 3)	(Fig. 4)

In a second step, they manually adjust the Voronoi image interactively by moving, adding, or deleting sites. They also take the liberty of adding visual effects by hand: emphasizing the outlines and color variations in each Voronoi region, so they look like actual pieces of stained glass (Fig. 4).

Image Processing with numpy, scipy and matplotlibs in sage

In this post, I would like to show how to use  a few different features of numpy, scipy and matplotlibs to accomplish a few basic image processing tasks: some trivial image manipulation, segmentation, obtaining of structural information, etc.  An excellent way to show a good set of these techniques is by working through a complex project.  In this case, I have chosen the following:

Given a HAADF-STEM micrograph of a bronze-type Niobium Tungsten oxide (left), find a script that constructs a good approximation to its structural model (right).

Courtesy of ETH Zurich

For pedagogical purposes, I took the following approach to solving this problem:

1. Segmentation of the atoms by thresholding and morphological operations.
2. Connected component labeling to extract each single atom for posterior examination.
3. Computation of the centers of mass of each label identified as an atom. This presents us with a lattice of points in the plane that shows a first insight in the structural model of the oxide.
4. Computation of Delaunay triangulation and Voronoi diagram of the previous lattice of points. The combination of information from these two graphs will lead us to a decent (approximation to the actual) structural model of our sample.

Let us proceed in this direction:

Super-Resolution Micrograph Reconstruction by Nonlocal-Means Applied to HAADF-STEM

We outline a new systematic approach to extracting high-resolution information from HAADF–STEM images which will be beneficial to the characterization of beam sensitive materials. The idea is to treat several, possibly many low electron dose images with specially adapted digital image processing concepts at a minimum allowable spatial resolution. Our goal is to keep the overall cumulative electron dose as low as possible while still staying close to an acceptable level of physical resolution. We wrote a letter indicating the main conceptual imaging concepts and restoration methods that we believe are suitable for carrying out such a program and, in particular, allow one to correct special acquisition artifacts which result in blurring, aliasing, rastering distortions and noise.

Below you can find a preprint of that document and a pdf presentation about this work that I gave in the SEMS 2010 meeting, in Charleston, SC. Click on either image to download.

The Nonlocal-means Algorithm

The nonlocal-means algorithm [Buades, Coll, Morel] was designed to perform noise reduction on digital images, while preserving the main geometrical configurations, as well as finer structures, details and texture. The algorithm is consistent under the condition that one can find many samples of every image detail within the same image.

Barbara	Noise added, std=30	Denoised image, h=93

The algorithm has the following closed form: Given a finite grid of the form for some compact set , a signal , and a family of windows satisfying the conditions

1. for all .
2. If , then ,

the nonlocal-means operator with filtering parameter , is defined by

where the weights are defined by

Here, denotes a patch of the image supported on the window .

Notice that the similarity check between patches is nothing but a simple Gaussian weighted Euclidean distance, which accounts for difference of grayscales alone. Efros and Leung prove that this distance is a reliable measure for the comparison of texture patches, and at the same time copes very well with additive white noise; in particular, if and are respectively the noisy and original images, and is the noise variance, then the most similar patches in the noisy image are also expected to be the most similar in the original:

The hunt for a Bellman Function.

This is a beautiful and powerful mathematical technique in Harmonic Analysis that allows, among other things, to prove very complicated inequalities in the theory of Singular Integral Operators, without using much of the classical machinery in this field.

The Bellman function was the tool that allowed their creators (Fedor Nazarov and Sergei Treil) to crack the problem of weighted norm inequalities with matrix weights for the case and finally solve it completely.

Copies of the original paper can be found at the authors’ pages; e.g. [www.math.brown.edu/~treil/papers/bellman/bell3.ps] (notice the postscript file is huge, as the article has more than 100 pages).

Let me illustrate the use of Bellman functions to solve a simple problem:

Dyadic- version of the Carleson Imbedding Theorem

Let be the set of all dyadic intervals of the real line. Given a function , consider the averages , on each dyadic interval .
Let be a family of non-negative real values satisfying the Carleson measure condition—that is, for any dyadic interval ,
Then, there is a constant such that for any ,

Presentation: Hilbert Transform Pairs of Wavelets

Now in the stage of the Approximation Theory Seminar, I presented a general overview of the work of Selesnick and others towards the design of pairs of wavelet bases with the “Hilbert Transform Pair property”. Click on the image below to retrieve a pdf file with the slides.

Presentation: The Dual-Tree Complex Wavelet Transform

In the first IMI seminar, I presented an introduction to the survey paper “The Dual-Tree Complex Wavelet Transform“, by Selesnick, Baraniuk and Kingsbury. It was meant to be a (very) basic overview of the usual techniques of signal processing with an emphasis on wavelet coding, an exposition on the shortcomings of real-valued wavelets that affect the work we do at the IMI, and the solutions proposed by the three previous authors. In a subsequent talk, I will give a more mathematical (and more detailed) account on filter design for the dual-tree WT. Click on the image below to retrieve a pdf version of the presentation.

Presentation: Curvelets and Approximation Theory

Find below a set of slides that I used for my talk at the IMA in the Thematic Year on Mathematical Imaging. On them, there is a detailed construction of my generalized curvelets, some results by Donoho and Candès explaining their main properties, and a bunch of applications to Imaging. Click on the slide below to retrieve the pdf file with the presentation.

Poster: Curvelets vs. Wavelets (Mathematical Models of Natural Images)

Together with Professor Bradley J. Lucier, we presented a poster in the Workshop on Natural Images during the thematic year on Mathematical Imaging at the IMA. We experimented with wavelet and curvelet decompositions of 24 high quality photos from a CD that Kodak® distributed in the late 90s. All the experiment details and results can be read in the file Curvelets/talk.pdf.

The computations concerning curvelet coefficients were carried out in Matlab, with the Curvelab 2.0.1 toolbox developed by Candès, Demanet, Donoho and Ying. The computations concerning wavelet coefficients were performed by Professor Lucier’s own codes.

Wavelet Coefficients

To aid in my understanding of wavelets, during the first months I started studying this subject I wrote a couple of scripts to both compute wavelet coefficients of a given pgm gray-scale image (the decoding script), and recover an approximation to the original image from a subset of those coefficients (the coding script). I used OCaml, a multi-paradigm language: imperative, functional and object-oriented.

The decoding script uses the easiest wavelets possible: the Haar functions. As it was suggested in the article “Fast wavelet techniques for near-optimal image processing“, by R. DeVore and B.J. Lucier, rather than computing the actual raw wavelet coefficients, one computes instead a related integer value (a code). The coding script interprets those integer values and modifies them appropriately to obtain the actual coefficients. The storage of the integers is performed using Huffman trees, but I used a very simple one, not designed for speed or optimization in any way.

Following a paper by A.Chambolle, R.DeVore, N.Y.Lee and B.Lucier, “Non-linear wavelet image processing: Variational problems, compression and noise removal through wavelet shrinkage“, these scripts were used in two experiments later on: computation of the smoothness of an image, and removal of Gaussian white noise by the wavelet shrinkage method proposed by Donoho and Johnstone in the early 90′s.

Progressive reconstruction of a grey-scale image of size with the largest (in absolute value) coefficients,

Modeling the Impact of Ebola and Bushmeat Hunting on Western Lowland Gorillas

In May 2003, together with fellow Mathematician Stephanie Gruver, Statistician Young-Ju Kim, and Forestry Engineer Carol Rizkalla, we worked on this little project to apply ideas from Dynamical Systems to an epidemiology model of the Ebola hemorrhagic fever in the Republic of Congo. The manuscript ebola/root.pdf is a first draft, and contains most of the mathematics behind the study. Carol worked in a less-math-more-biology version: ebola/Ecohealth.pdf “Modeling the Impact of Ebola and Bushmeat Hunting on Western Lowland Gorillas,” and presented it to EcoHealth, where it has been published (June 2007). She also prepared a poster for the Sigma-Xi competition: Click on the image below to retrieve a PowerPoint version of it.

Triangulations

As part of a project developed by Professor Bradley J. Lucier, to code a PDE solver written in scheme, I worked in some algorithms to perform “good triangulations” of polygons with holes (“good triangulations” meaning here, those where all the triangles have their three angles as close to 60º as possible). I obtained the necessary theoretical background and coding strategies from the following references:

• Mark de Berg et al., “Computational Geometry by Example.“
• Francis Chin and Cao An Wang, “Finding the Constrained Delaunay Triangulation and Constrained Voronoi Diagram of a simple Polygon in Linear Time.“
• Joseph O’Rourke, “Computational Geometry in C.“
• Jim Ruppert, “A Delaunay Refinement Algorithm for Quality 2-dimensional Mesh Generation.“

Mechanical Geometry Theorem Proving

In 1977, Professor Wen-Tsun Wu succeeded in developing a method of mechanical geometry theorem proving. This method has been applied to prove or even discover hundreds of non-trivial difficult theorems in elementary and differential geometries on a computer in an almost trivial manner. Usign Ritt’s differential algebra, Wu established a method for solving algebraic and differential equations by transforming an equation system in the general form to equation systems in triangular form. This is the Ritt-Wu decomposition algorithm, that later on was shown to be equivalent to perform a series of operations on ideals, very easily carried out by means of Gröbner basis manipulation.

I wrote a script in MAPLE to perform evaluations of the validity of some simple theorems in Euclidean Geometry, and wrote a small paper (in Spanish) on one of my findings, that was published in Bol. Asoc. Prof. Puig Adams, in October’99: “Sobre demostración automática de un problema geométrico“.

The example I cover in that short article can be seen below.

Given: Circles , that intersect each other in points and , and given points , in circle , consider line through and , and line through and . The intersections of line with circle are and . The intersections of line with circle are and . Consider the segments (connecting with ) and (connecting with ).

To prove: Segments and are parallel.