Skip navigation

Fast Fourier Transform and rgb2gray (again)

Note: My thesis is done. However, there are still some things which I find of interest to address here. Due to how our thesis was (mis)handled, I’m only finding the time to post about these things now.

Last time, I told you how we are porting all our Matlab/Octave code to Java. I wrote about a huge difference between Matlab and Octave’s implementation of rgb2gray. However, as it became apparent to me, my issues with rgb2gray are not quite done yet.

First a little background. Our project relies heavily on the Fast Fourier Transform, a numerical algorithm whose products I bet you encounter everyday though you probably are not aware of it. The 2D FFT is built-in with Octave, as expected for a language meant specifically for mathematical processing. The same, however, cannot be said for Java.

It’d be crazy for me to attempt to code it from scratch due to a number of reasons not the least of which is the fact that I don’t really have a solid training with numerical algorithms. So, after browsing through various libraries, we decided to use JTransforms, largely because we can see the source code for ourselves and it is natively in Java, in contrast to, say, FFTW, which has Java bindings but is natively in C. Plus, it does not have power-of-2 constraints, a common trait among various implementations of the FFT.

Now, the thing is, there seems to be quite a considerable offset between the FFT results of Octave1 and JTransforms; the kind of offset which you’d be so tempted to chalk up to floating-point handling differences though some part of your reason tells you it is too large to be so. The offset I was seeing ranged from 2 to 12 integer values.

As I admitted earlier, I don’t have any solid grounding with numerical algorithms. The way I see it, there are a number of possible culprits on why I’m not getting the results I should get. The FFT, after all, is a blanket term for a family of algorithms which all do the same thing, namely, apply the Fourier Transform to a discrete collection of values (i.e., vectors or matrices).

What I’ve Tried (Or, the scientific probable reason on why there is this offset, as discussed by my adviser)

Warning: Some equations ahead. I wouldn’t be delving too much into the equations and you should be able to understand my main point with just some basic algebra. But just so you know.

Consider this tutorial on the FFT.

It defines the 2D FFT as:

F[k,l] = \frac{1}{\sqrt{MN}}\sum_{n=0}^{N-1}\sum_{m=0}^{M-1}f[m,n]e^{-2\pi i(\frac{mk}{M}+\frac{nl}{N})} f[m,n]= \frac{1}{\sqrt{MN}}\sum_{l=0}^{N-1}\sum_{k=0}^{M-1}F[k,l]e^{2\pi i(\frac{mk}{M}+\frac{nl}{N})} 0 \leq m,k \leq M-1, 0 \leq n,l \leq N-1

where M and N is the number of samples in the x and y direction (or, for our particular problem, the dimensions of the image).

While it may seem interesting to find mutual recursion here, what my adviser told me to note is the constant at the beginning of the equations, \frac{1}{\sqrt{MN}}. According to him, depending on the implementation of the FFT we are using (remember what I told you above that Fast Fourier Transform is just a blanket term for a family of algorithms), the constant varies to either \frac{1}{\sqrt{MN}} or \frac{1}{MN}. It’s now just a matter of scaling the samples (the pixel values) by the appropriate constant to get the desired results.

The tutorial I linked to presents the following sample signal to demonstrate the FFT:

Sample Signal

which should evaluate to the following real and imaginary component respectively

FFT real

FFT imaginary

The following code listing directly translates the above example to Octave code:

x_real = zeros(8, 8);
x_real(2,3) = 70;
x_real(2,4) = 80;
x_real(2,5) = 90;
x_real(3,3) = 90;
x_real(3,4) = 100;
x_real(3,5) = 110;
x_real(4,3) = 110;
x_real(4,4) = 120;
x_real(4,5) = 130;
x_real(5,3) = 130;
x_real(5,4) = 140;
x_real(5,5) = 150
x_fft = fft2(x_real);
x_r = real(x_fft)
x_i = imag(x_fft)

Which results to the following output:

x_real =
 
     0     0     0     0     0     0     0     0
     0     0    70    80    90     0     0     0
     0     0    90   100   110     0     0     0
     0     0   110   120   130     0     0     0
     0     0   130   140   150     0     0     0
     0     0     0     0     0     0     0     0
     0     0     0     0     0     0     0     0
     0     0     0     0     0     0     0     0
 
x_r =
 
   1.3200e+03  -7.9113e+02   8.0000e+01  -1.6887e+02   4.4000e+02  -1.6887e+02   8.0000e+01  -7.9113e+02
  -5.0485e+02  -9.0711e+01   2.2142e+02   1.0586e+02  -1.6828e+02   1.2721e+01  -2.6142e+02   6.8527e+02
   1.2000e+02   0.0000e+00  -4.0000e+01  -2.3431e+01   4.0000e+01   0.0000e+00   4.0000e+01  -1.3657e+02
  -3.3515e+02   1.3414e+02   2.1421e+01   5.0711e+01  -1.1172e+02   3.4731e+01  -6.1421e+01   2.6728e+02
   1.2000e+02  -6.8284e+01   0.0000e+00  -1.1716e+01   4.0000e+01  -1.1716e+01   0.0000e+00  -6.8284e+01
  -3.3515e+02   2.6728e+02  -6.1421e+01   3.4731e+01  -1.1172e+02   5.0711e+01   2.1421e+01   1.3414e+02
   1.2000e+02  -1.3657e+02   4.0000e+01   0.0000e+00   4.0000e+01  -2.3431e+01  -4.0000e+01   0.0000e+00
  -5.0485e+02   6.8527e+02  -2.6142e+02   1.2721e+01  -1.6828e+02   1.0586e+02   2.2142e+02  -9.0711e+01
 
x_i =
 
     0.00000  -711.12698   440.00000    88.87302     0.00000   -88.87302  -440.00000   711.12698
  -724.26407   713.55339  -216.56854    55.56349  -241.42136   134.14214   120.00000   158.99495
   120.00000  -136.56854    40.00000     0.00000    40.00000   -23.43146   -40.00000     0.00000
  -124.26407   255.56349  -120.00000    -6.44661   -41.42136    38.99495   103.43146  -105.85786
     0.00000   -68.28427    40.00000    11.71573     0.00000   -11.71573   -40.00000    68.28427
   124.26407   105.85786  -103.43146   -38.99495    41.42136     6.44661   120.00000  -255.56349
  -120.00000    -0.00000    40.00000    23.43146   -40.00000    -0.00000   -40.00000   136.56854
   724.26407  -158.99495  -120.00000  -134.14214   241.42136   -55.56349   216.56854  -713.55339

As evident, the results are very far from what our source says. However, dividing the sample (matrix x_r) by 8 (cf sample size) produces the results as given by our source.

Add the following line before calling fft2

x_real /= 8;

And we get,

 
x_r =
 
   165.00000   -98.89087    10.00000   -21.10913    55.00000   -21.10913    10.00000   -98.89087
   -63.10660   -11.33883    27.67767    13.23223   -21.03553     1.59010   -32.67767    85.65864
    15.00000     0.00000    -5.00000    -2.92893     5.00000     0.00000     5.00000   -17.07107
   -41.89340    16.76777     2.67767     6.33883   -13.96447     4.34136    -7.67767    33.40990
    15.00000    -8.53553     0.00000    -1.46447     5.00000    -1.46447     0.00000    -8.53553
   -41.89340    33.40990    -7.67767     4.34136   -13.96447     6.33883     2.67767    16.76777
    15.00000   -17.07107     5.00000     0.00000     5.00000    -2.92893    -5.00000     0.00000
   -63.10660    85.65864   -32.67767     1.59010   -21.03553    13.23223    27.67767   -11.33883
 
x_i =
 
    0.00000  -88.89087   55.00000   11.10913    0.00000  -11.10913  -55.00000   88.89087
  -90.53301   89.19417  -27.07107    6.94544  -30.17767   16.76777   15.00000   19.87437
   15.00000  -17.07107    5.00000    0.00000    5.00000   -2.92893   -5.00000    0.00000
  -15.53301   31.94544  -15.00000   -0.80583   -5.17767    4.87437   12.92893  -13.23223
    0.00000   -8.53553    5.00000    1.46447    0.00000   -1.46447   -5.00000    8.53553
   15.53301   13.23223  -12.92893   -4.87437    5.17767    0.80583   15.00000  -31.94544
  -15.00000   -0.00000    5.00000    2.92893   -5.00000   -0.00000   -5.00000   17.07107
   90.53301  -19.87437  -15.00000  -16.76777   30.17767   -6.94544   27.07107  -89.19417

Which, at last, agrees with our source.

The Blooper (or, the actual and embarassing reason why JTransforms FFT is not coinciding with Octave FFT)

In my first post about rgb2gray, I mentioned that I was taking the floor of the average of the RGB components of a pixel (or, in Java code, just perform integer division as the resulting precision loss is tantamount to floor). Big mistake. Octave does not merely floor values. It rounds off values.

In code, so there be no misunderstandings,

public static int[][] rgb2gray(BufferedImage bi) {
  int heightLimit = bi.getHeight();
  int widthLimit = bi.getWidth();
  int[][] converted = new int[heightLimit][widthLimit];
 
  for (int height = 0; height < heightLimit; height++) {
    for (int width = 0; width < widthLimit; width++) {
      Color c = new Color(bi.getRGB(width, height) & 0x00ffffff);
      float rgbSum = c.getRed() + c.getGreen() + c.getBlue();
      float ave = (rgbSum / 3f);
      float diff = ave % 1f;
      int iave = diff < 0.5f ? (int) ave : (int) (ave + 1);
      converted[height][width] = iave;
    }
  }
 
  return converted;
}

The moral of this long story? If two supposedly-similar functions are returning different outputs, check that the inputs are exactly the same before jumping to any wild conclusions.

  1. I’d like to note here that, according to the help file, Octave’s FFT is based on FFTW [↩]

SQL Bloopers I*

*’Cause I have a feeling there’s more to come

I just spent an hour or so figuring out why a long SQL query is returning 0 rows. Long as in,

SELECT books.isbn, title, lastname, firstname, publishername
FROM books
INNER JOIN authored ON books.isbn = authored.isbn
INNER JOIN bookpersons ON authored.personid = bookpersons.personid
INNER JOIN published ON published.isbn = books.isbn
INNER JOIN publishers ON published.publisherid = publishers.publisherid
WHERE title = "Brave New World";

I was already looking into derived relations and subqueries until I realized that tables published and publishers are empty.

I’m calling it a day. So much for populating published and publishers and testing if my query works. Haaaayyyy… OTL

Fixing “Local Only” or “Limited Connectivity” in Vista

Just putting this up here so I can describe the specifics of my case better…

Sometimes, Vista’s tells you that your WiFi connection’s status is “Limited” or “Local Only”. While most of the time this is solvable by resetting/going nearer to the router, I just had a peculiar case of this annoying problem.

So, today I logged in to Vista after so long. It was detecting our home WiFi with no problem but I can’t seem to load webpages on my browser. The connection seems to drop off as soon as I request for data. The longest I got a connection to last was just enough for me to log-in to GMail. I ruled out that this is a problem with my service provider as Ubuntu connects to the net just fine.

As far as I can tell, the connection is fine upon starting Windows but fails the moment I request for data. The connection cannot be reset after it fails so, to test new theories, I need to restart Windows (annoying!). I tried to ping to check when the connection drops and I only got as far as two replies before I got a request timeout.

Searching around, I found out that the problem is with Vista’s IPv6 connectivity. For some reason, if you have this enabled, Vista will have trouble connecting to pre-IPv6 (read: old) routers.

Here’s how to disable IPv6 in Vista (YouTube):

As the video suggests, you may need to wait for Vista to refresh. There was a considerable waiting time for my Vista to refresh and, as Vista isn’t exactly known for being responsive, I suggest you just restart after disabling IPv6.

A Difference Between Matlab and Octave

Due to the nature of the algorithms we are testing for our thesis, we had to “prototype” the procedures in Matlab so that we can easily modify parameters and test variables. However, since Matlab is expensive and we are a university that does not tolerate piracy ;), we used GNU Octave, a FOSS equivalent of Matlab (think Mono for C#).

We are done with the algorithm-prototyping part and we are now porting our Matlab code to Java, since this thesis is meant to be used by scientists, with a GUI and all that comes with standard software.  A big part of this task is in coding the functions that are built-in in Matlab; remember that Matlab is meant specially for mathematical purposes (it is a portmanteau of Matrix Laboratory) while Java is more general purpose, closer to metal, if you will.

For the past few days, I’ve been trying to implement the Matlab function rgb2gray which, as the name suggests, converts an RGB-colored image to grayscale. Now, there are a lot of ways to convert an image to grayscale but getting a grayscale isn’t the main point here. Getting it the way Matlab/Octave does is essential so that we can recreate in Java the recognition accuracy we achieved in Octave. We will be manipulating these pixel values after all.

So, I looked into Matlab’s documentation of rgb2gray and found that, for a given RGB pixel, it gets the the corresponding grayscale value by the following weighted sum:

0.2989 * R + 0.5870 * G + 0.1140 * B

(Or something close to those constants/giving the same priority over the RGB components. That is, green most weighted, followed by red, and then blue. This priority reflects the sensitivity of the human eye to these colors. See Luma (video).)

I then ran some tests on Octave to verify the docs:

octave3.2:1> four = imread("four.JPG");
octave3.2:2> four(1,1,1) # The red component of the first pixel of four.JPG
ans = 159
octave3.2:3> four(1,1,2) # The green component of the first pixel of four.JPG
ans = 125
octave3.2:4> four(1,1,3) # The blue component of the first pixel of four.JPG
ans = 64
octave3.2:5> grayval = 0.2989 * 159 + 0.5870 * 125 + 0.1140 * 64
grayval =  128.20

So, the grayscale equivalent of the first pixel of four.JPG will have the value floor(128.20)=128. Sure enough, when I encoded the procedure in Java, the first pixel of the grayscaled four.JPG has the value 127—close enough taking into account the possible differences in how Java and Octave handle floating point computation.

But wait, there’s more…

octave3.2:6> fourgray = rgb2gray(four);
octave3.2:7> fourgray(1,1)
ans = 116

The value of the first pixel of four.JPG after rgb2gray is 116! Now that’s something no amount of discrepancy in floating-point handling can account for. Besides, hasn’t Octave itself computed a value close to Java’s 127 when done manually?

That’s when I realized that Octave may not be an exact port/clone of Matlab after all. I decided to Google “rgb2gray octave” and, sure enough, the documentation of Octave at SourceForge points to a departure from Matlab’s implementation:

Function File: gray = rgb2gray (rgb)
…
If the input is an RGB image, the conversion to a gray image is computed as the mean value of the color channels.

And verifying the docs…

octave3.2:8> floor((159 + 125 + 64)/3)
ans =  116

Problem solved.

I’m pretty sure that this isn’t the only difference between Matlab and Octave. The next time I encounter another one, I’ll try to document it here, time permitting.

BONUS: My encounters with Octave so far gives credence to this but I have yet to verify this thoroughly. It seems that Matlab/Octave loops through matrices (arrays of at least two dimensions, in Java/C-speak) column-major order. This isn’t exactly difficult to do in Java/C but Java/C programmers are more used to traversing multidimensional arrays in row-major order, since this should result to less page faults and therefore faster code. Still, for some computations, the order with which you traverse a matrix matters a lot. Be careful there.

Google Analytics Frustration

Several weeks ago, Google rolled out (read forced) its new UI for Google Analytics to all users. I’m really not quite comfortable with large-scale UI changes so, for the first few times I used it, the first thing I did was to click the “Old Version” link at the upper left. But eventually, I got tired doing that so I conceded to learning my way around the new UI. It seems like it’s here to stay anyway so my attachment to the past is rather futile.

I initially found the new UI too alienating. Unlike the UI changes Google has been rolling out for its other products (GMail, Docs, Reader, etc.) the change for Analytics seems too drastic in my opinion. Its greeting page is very uninformative, compared to the old one. See for yourself.

Old UI (retrieved via the only good thing in Analytics’ new UI—the “Old Version” link)

Old Analytics welcome page - NICE

It's informative at first glance. You get a quick overview of the statistics for your website.

New UI

New Analytics welcome page - CRAP

New welcome page. Useless. Needs two clicks from here to anything useful/informative.

(I’m sorry that you have to see my obviously-dummy account test.skytreader.net. I promise to explain after several paragraphs.)

I actually gave Google some benefit of the doubt for their new UI. For one, I don’t really do anything with the statistics of my websites beyond vain ego-feeding. Maybe, just maybe, the new UI is meant for those who actually design their pages based on statistics, those who decide on a hue of blue based on the number of hits it generates. Beyond this post at the Google Analytics help forums (hey was that just posted yesterday?), I haven’t found anyone else frustrated by the new UI.

But aside from the two-hits-before-any-info complaint I already have above, here are a few more of Google’s UI decisions which frustrates me.

(1) “Make this version default” (see new welcome page image above)
What? Make what version default? If by “this” you mean this horrifying version which, by behavior, is already the default, then I’m totally confused as to the necessity of displaying this link. I haven’t dared click on this, in case more horror pops up.

Related (but not really Analytics): I remember seeing this way back but it’s minor and a bit cute if you ask me. A quick Google search for “google what is more than everything” returns nothing (even search is crap now?). If anyone finds the original complainant, I’ll be more than happy to link back. Pardon my shaky brush.

Google search side bar

Google, Google, seriously, what is more than everything?

(2) So, how do I add a new account/profile again?
It’s easy to track a new website in the old UI. You see, when you select an account, you get to your profiles list which has this nifty link at the lower left

The closest I get to my profiles list in the new UI is this.

Profiles in the new UI

Where to now, Google?

But hey, the keen reader will point out, you managed to add your obviously-dummy test.skytreader.net. You should’ve found a way to add one.

I honestly don’t remember how I did that. I think I clicked the cogwheel icon at the far right of the new welcome page. I was taken to a page which, for all I remember, was something in between a settings panel and a help panel. But hey, at least I managed. Google gets some points for that.

(3) And now, I explain my dummy
For quite some time now, I’ve noticed that hits to {kode.play();} has decreased. Nothing surprising about that, as I’ve noticed that hits to {kode.play();} tends to oscillate. The hits usually come from searches for terms like “solvability of the n-puzzle“, “n-puzzle“, “install opencv” (or “install opencv ubuntu“), and hey, even Azeus-related search terms. The hits come from countries like USA to India and I’ve come to believe that those who are searching are (CS?) students assigned to/encountering these problems.

But this time the hits dipped drastically. So, I decided to poke around the internals of my site to verify that there’s nothing wrong on my part.

(Warning: Techie talk ahead)

To install Analytics on your website, you typically insert some lines of JavaScript code somewhere in your site. Google advises that you put it before the closing head tag. I’ve always done that being that two of the three sites I track were built from the ground-up by me. However, when I put up {kode.play();}, whose base code came from WordPress, I had to put my tracking code in my theme’s footer.php (a PHP include file, hence it loads for all my pages).

Sometime ago, the WordPress theme I am using updated, erasing my little tweaks on its files. The CSS-related tweaks was easily spotted and remedied but I didn’t know that the tracking code I inserted in my footer.php was also erased, and hence Analytics can’t collect statistics for my site.

What frustrates me is that Analytics didn’t tell me that it isn’t receiving any tracking data from my site. To be fair, even when I switch to the old UI, Analytics doesn’t report anything unusual for {kode.play();}. Here’s when I decided to add my dummy profile, test.skytreader.net.

And I found out, to my further ire, that it seems that the new UI really has no facility to tell you if your site is sending tracking data or not. Or if it has, it is very well hidden, kudos Google. At least the old UI will show me this for test.skytreader.net:

Analytics reporting that my dummy profile isn't sending data, as it should

I still have to find the equivalent of this exclamation mark in the new UI.

Well, that’s what prompted me to do this rant. I don’t usually rant especially when I know just how difficult doing something is. But Google, I really expected better from you.

Lesson learned: When using Analytics in WordPress, skip copy pasting the JavaScript. WordPress has various plug-ins for Google Analytics tracking. I’ll be trying out the one made by Kevin Sylvestre.