The math behind 360 degree fisheye to landscape conversion

October 29, 2009 By

I wrote an article to convert a 360 degree fisheye image to a landscape view some time ago. I also realised I didn’t explain the math very much, mainly because I thought it’s fairly obvious. On hindsight, it doesn’t seem obvious. My apologies.

Commenter Eric pointed out a math technique called linear fractional transformation. It’s basically a function that can map lines and circles to lines or circles.

In theory, it seems applicable to our problem. When I tried working out the solution, I failed. 2 possible reasons: my math sucks, or the technique isn’t applicable to the problem. It’s probably the former…

My postulate is that, the fisheye-landscape conversion has an edge condition that maps a line to a point. Specifically, the bottom of the destination image maps to one point, the centre of the source image. Thus linear fractional transformation is probably not suitable. I’m happy to hear from you if you’ve found a way to make it work.

Let’s bring up the explanation diagram I had from before:

Fisheye to landscape explanation diagram

I have assumed a source image that’s square (width equals height) and its width has an even number of pixels. With this, let the given image be of width and height of 2l pixels. The idea is to construct an image with width of 4l pixels and height of l pixels, which is the landscape view of the source fisheye image.

The dimensions of the destination image was arbitrarily chosen. I just find that a height of l pixels (or half the height of the source image) to be convenient. The centre of the source image is assumed to be the centre of the small “planet”. This means the pixels along the horizontal and vertical bisectors of the source image will not be distorted (much) by the conversion.

Oh right, I haven’t told you about the exacts of the conversion math…

You should know that only the pixels in the inscribed circle of the source image would be in the destination image. This is due to the “uncurling” effect. The pixels not in the inscribed circle would be out of range in the destination image.

So, imagine the source image as a representation of the Cartesian plane. The centre of the image is the origin. The point A, is the eastern point of the inscribed circle. Points B, C and D are the northern, western and southern points of the inscribed circle respectively.

I’m using the Cartesian plane because the Cartesian quadrants make the math easier. Circles mean sines and cosines, so I’d rather work with angles in the typical form than do all the funny angle modifications. I’m not masochistic, you know…

What you should understand now is this: the pixels along the top of the destination image come from the pixels along the circumference of the inscribed circle on the source image.

We’ll be iterating over the destination image (remember my messy index preference?) Let’s start at the top left corner. We’ll be iterating 4l pixels to the top right corner. This is visualised as going anti-clockwise on the source image from point A, to D, to C, to B and back to A.

So, 4l pixels is equivalent to 2 PI radians?

At the top left corner, we start with 2 PI radians (so to speak). As we iterate to the top right corner, the angle reduces to 0. Thus this formula:

theta = (4l – x)/(4l) * 2PI
where x is the Cartesian x axis.

Generally speaking, iterating from the left to right on the destination image is equivalent to going anti-clockwise on the source image.

Now, as we iterate from the top left of the destination image to the bottom left, it’s equivalent to going from point A on the source image to the centre of the source image. Thus:

radius = l – y
where y is the Cartesian y axis.

Generally speaking, iterating from the top to bottom of the destination image is equivalent to going from edge of source image to centre of source image.

And once you understand that, the rest is just coding. I merged the code for converting Cartesian to raster coordinates together (more details here with code here). The code was deliberately left unoptimised so it’s easier to read.

For example,

theta = 2.0 * Math.PI * (double)(4.0 * l - j) / (double)(4.0 * l);

could be

theta = Math.PI * (double)(4.0 * l - j) / (double)(2.0 * l);

to save on operations. But the 2.0 * Math.PI makes it more meaningful.

The if condition

if (x >= 0 && x < (2 * l) && y >= 0 && y < (2 * l))

could have had the (2 * l) part assigned to a variable to avoid multiplication multiple times. You're welcome to use a variable perhaps named iSourceWidth for example.

And that's all I have. I hope you have fun with the code.

Filed Under: Mathematics Tagged With: , , , ,

The leap year 1900 “bug” in Excel

October 26, 2009 By

No it’s not really a bug in Microsoft Excel. What happens is that Excel will accept 29 Feb 1900 as a valid date.

“Wait, the year 1900 is not a leap year. 29 Feb 1900 is invalid!”

Yes, I agree. I wrote something about leap years before. From what I understand, it’s a historical issue, that

There are two kinds of Excel worksheets: those where the epoch for dates is 1/1/1900 (with a leap-year bug deliberately created for 1-2-3 compatibility that is too boring to describe here), and those where the epoch for dates is 1/1/1904.

[emphasis mine]

The “1-2-3″ refers to Lotus 1-2-3, a spreadsheet program. To get the Lotus users to come over to Excel, Excel had to be able to import files in the Lotus format. Unfortunately, leap years weren’t well understood then, so Excel used the wrong leap year calculation, as did other spreadsheet software, which Microsoft acknowledges.

I’m talking about this because I’m creating Excel files in the Open XML format (for reporting purposes). In particular, I work with dates. For example, I have to create reports for call detail records that pass through satellites for my users. The date value is one of the most looked at piece of information.

Anyway, to study how dates are stored in Excel, I created an Excel file with date information such as “26/10/2009 12:34″ and saved it. I used to save it in the (Excel 2003) XML format, but with Open XML and the Microsoft Office Compatibility Pack (for Office 2003 and earlier versions), I tried the .xlsx format.

I renamed the .xlsx to .zip (because Open XML files are just zip files), then unzipped the package. I looked at /xl/worksheets/sheet1.xml and looked for my date data. It disappeared! They’re just floating point numbers!

Actually, those floating point numbers represent the number of days since the epoch 1 Jan 1900.

How did I discover that? I can’t remember the details. I think I printed consecutive days such as 1 Jan 2009, 2 Jan 2009 and so on, and then checked the floating point number in the resulting XML file. I found that they differed by a difference of 1.

Then I made the brilliant mother of all light bulbs and postulated that perhaps the floating point numbers started counting from an epoch. The only epoch worth my while was 1 Jan 1900.

So I amended my test program to start generating date values
01/01/1900
02/01/1900
03/01/1900
04/01/1900
05/01/1900
and so on.

I looked at the resulting XML file and saw 1, 2, 3, 4, 5 and so on. My next brilliant bit of deduction was that the trailing decimal values must be fractional values of days. Pleased with myself, I proceeded to test that theory.

It worked fine. Till I hit 29 Feb 1900. My instincts warned me, “That doesn’t look right.” Generally, I look out for edge cases, and in the case of dates, 29 Feb. I did some calculations and woah, 29 Feb 1900 isn’t valid! Yet there it was in the Excel file, displayed and formatted correctly by Excel.

That’s when I dug around and found Joel’s article.

So how do you fix it?

DateTime dtEpoch = new DateTime(1900, 1, 1, 0, 0, 0, 0);
DateTime dt = DateTime.ParseExact("05 Mar 1900", "dd MMM yyyy", null);
TimeSpan ts = dt - dtEpoch;
double fExcelDateTime;
// Excel has "bug" of treating 29 Feb 1900 as valid
// 29 Feb 1900 is 59 days after 1 Jan 1900, so just skip to 1 Mar 1900
if (ts.Days >= 59)
{
	fExcelDateTime = ts.TotalDays + 2.0;
}
else
{
	fExcelDateTime = ts.TotalDays + 1.0;
}

If the date in question is on or after 1 Mar 1900, simply add one to the floating point value.

You might wonder why we added one more to the value in each section of the if-else portion. If the date is on or after 1 Mar 1900, shouldn’t it be +1.0 instead of +2.0?

Because it’s a counting problem. We excluded the epoch date itself when we calculated the TimeSpan ts, so we’re adding it back in.

You might wonder why you couldn’t have used 31 Dec 1899 as the base. You can. I just think 31 Dec 1899 doesn’t quite ring a bell. 1 Jan 1900 is more striking.

“But I don’t use the year 1900 at all! I mean, even the year 2000 is, like, so last century. The year 1900 is like, Babylonian!”

Hmm… ok. *shrugs*

There’s also updated material and source code, together with more information on how to work with Open XML. Click here to find out more.

Filed Under: Curiosita Tagged With: , , , , ,

Figuring out who you are

October 24, 2009 By

You have to watch this video first. It’ll be one of the most thought-provoking 40 minutes of your life:

Makebelieve Help, Old Butchers, and Figuring Out Who You Are (For Now) from Merlin Mann on Vimeo.

I’m scared. I’m deathly afraid actually. Remember the ebook I’m writing, “Discipline and Deflection”?

Well, I started off thinking, “I want to help people. I seem to have a knack for handling many small tasks, answering emails, replying to user queries, generating ad-hoc reports from databases. Stuff like that. And I still manage to write code, roll the applications out to production, and maintain legacy code. I should totally write something about handling interruptions!”

That went off to an immense spurt of creative energy. I couldn’t stop thinking about it. Maybe I could write that, what reference could I use to illustrate my point and so on. I would be jotting down notes on my paper pad. I would be typing in tidbits of inspiration on my iPhone if I’m travelling.

As I thought and planned and wrote and thought some more, I had this increasing feeling of “This is so lame! How could anyone possibly benefit from this? This doesn’t make sense!”

And I got scared. What the heck was I doing? How could I possibly think I’m good enough to teach anyone about handling interruptions?

So I changed course. I thought about it real hard, and hit upon the idea that I’m not really writing about handling interruptions per se, but about controlling one’s self. It’s about self-control. It’s about controlling the emotions you’re feeling, thoughts you’re having and actions you’re taking. It’s not about suppressing those emotions, nor feel guilty about having flighty fantasies, nor getting depressed over the things you’ve done. It’s about not reacting to your emotions, which govern your thoughts, which compel your actions.

It’s about self-control, about self-awareness, and about how to use that knowledge to better yourself, in math, in programming, in whatever you set your mind to do.

And I got really scared after that. Because I felt like I was becoming one of those fake self-help people Merlin was talking about in his video. Because that piece of work I have in my computer right now, that ebook I’m going to publish, has little to do with math. Or programming. The concepts’ relation to each other seem as weak as molecular bonds.

But I used them. I figured them out myself. And they worked for me. But that doesn’t make me an expert in any way. And so I’m afraid. Of sounding like I know what I’m doing. I don’t.

Mostly, I just intuit things to their conclusion. This seems to run counter to the logical processes that are math and programming. I use intuition and logical thinking in tandem and in equal parts to solve problems.

I was so scared that while writing this article, I had to get away from the keyboard, and since I was also hungry, I mixed up a protein shake to drink (it was about 11pm and I didn’t want to eat anything heavy). The act of mixing, drinking the shake, and washing up calmed me a little. Which is important.

Because…

Most of all, I’m scared because I have no idea how that piece of work is going to help you. I know you’re a smart person. Which adds to my fear. What can I possibly teach an intelligent person on how to stay calm, how to maintain discipline, how to follow through on the task at hand even with interruptions and distractions? Will that even help you in your work?

In any case, I’m still going to finish that ebook. Even if it doesn’t help you. Even if you think it’s lame. Even if you think that makes me a fake self-help guru.

Because I have a compulsion to finish it. I have to write it. It’s driving me insane.

I’m going to stop here. I know you probably have some really useful work you need to get done. Still, a comment or an email with your thoughts on the matter is very much appreciated. Thank you.

Filed Under: Curiosita Tagged With: ,

English Metric Units and Open XML

October 22, 2009 By

Emu
[image by blmurch]

In this article, you’ll find out how English Metric Units (or EMUs) are related to the Open XML format. So what are English Metric Units? They are … actually, I have no idea what they are. Here’s the best answer I could find on EMUs. And there’s the Open XML explanation on EMUs in Wikipedia.

I stumbled upon EMUs because I was trying to create an Excel spreadsheet using the Open XML format. The task require the addition of an image in one of the Excel sheets. You have no idea how much code I needed to write just to include one image. (I’ll tell you about that in another article. Let’s focus on EMUs here.)

Basically, there’s no unifying unit, no “one ring to bind them all”: centimetres, inches and points. So they used a new unit of measurement to represent the dimensions of an image. *sigh*

Anyway, while searching for how to convert pixels to EMUs, I stumbled upon 2 articles on StackOverflow: Pixel to Centimetre and Pixel to Point.

From the Wikipedia article, there are 914400 EMUs per inch, and there are 96 pixels to an inch. Therefore, I figured the pixel to EMU formula is

EMU = pixel * 914400 / 96

There’s a flaw, in that the dots per inch (DPI) may be different for different monitors. For example, there could be 72 pixels in an inch. The best I could do is to assume that, the image created with one monitor, will be used on another monitor with the same DPI. Thus:

EMU = pixel * 914400 / Resolution

Here’s some code to visualise that:

Bitmap bm = new Bitmap("yourimage.jpg");
DocumentFormat.OpenXml.Drawing.Extents extents = new DocumentFormat.OpenXml.Drawing.Extents();
extents.Cx = (long)bm.Width * (long)((float)914400 / bm.HorizontalResolution);
extents.Cy = (long)bm.Height * (long)((float)914400 / bm.VerticalResolution);

There, now you know how English Metric Units are related to Open XML formats.

There’s updated material and source code, together with more information on how to work with Open XML. Click here to find out more.

P.S. English Metric Units have no relation to emus. Other than their (unfortunate?) acronym being exactly the same as the name of the Dromaius novaehollandiae…

Filed Under: Curiosita Tagged With: , , , ,

Should you be a generalist or specialist?

October 19, 2009 By

The short answer is: be both.

That seems to cheat you of an interesting discussion, so let’s talk more on it. Let’s define the terms first. Generally speaking (that’s not a personal bias, that’s how the language is used…), a generalist is a person whose interests and skills are varied. A specialist is a person who’s very interested and/or skilled in 1 (maybe 2) area(s).

So why are specialists highly sought after? As a rough benchmark, let’s use Google Trends:
Generalist vs Specialist trend

One possible reason is that people feel safer going to a specialist for help. For example, people would rather see a lung specialist, or heart specialist, or kneecap specialist than a general practitioner. Even for small problems.

I’m not saying it’s wrong. It makes sense.

I’m saying, as the world grows more complex, so does its problems. As the complexity grows, it becomes harder to categorise those problems. Thus making it difficult to know who to consult.

Say the web application has some errors. Is it Javascript? Is it improperly formed HTML? Is it the CSS? Is it the database permission? Is the database down? Is the server down? Is the code wrong? And are you telling me you need to look for a Javascript expert, a web designer, a database administrator and a programmer in order to fix that problem?

The general consensus (there’s the word again) seems to be to focus on your strengths and correct your weaknesses as best as possible (or completely ignore them).

As the world’s problems grow more complex, I propose that the categories start to merge together. You don’t think of them as Javascript or CSS or database problems. You look at them as a web application problem. And you look for someone specialising in developing web applications.

So should you be a generalist or a specialist? I would say be both if you can. The world needs both. As Seth Godin says, specialise in being a generalist.

It feels like an intractable proposition. How do you know many things and know one thing very well at the same time? How do you stand still and move at the same time? How do you clench your fist and unclench your fist at the same time?

Well, don’t think of them as opposite sides of a solution. Think of them as the same solution.

Filed Under: Curiosita Tagged With: ,
« Older Posts