Recent posts

The DFT of an image: phase vs. magnitude


Posted by Diego Assencio on 2017.09.01 under Computer Science (Digital Signal Processing)

Let $X$ be an $M \times N$ matrix (a two-dimensional array) of complex numbers $x_{mn}$ for $m = 0, 1, \ldots, M - 1$ and $n = 0, 1, \ldots, N - 1$. The discrete Fourier transform of $X$ is another $M \times N$ matrix $\tilde{X}$ of complex numbers $\tilde{x}_{pq}$ such that: $$ \tilde{x}_{pq} = \sum_{m = 0}^{M - 1} \sum_{n = 0}^{N - 1} x_{mn} e^{-i2\pi pm/M} e^{-i2\pi qn/N} \label{post_81059bc883bd6156c2e83f83e2e38c2b_dft_2d} $$ for $p = 0, 1, \ldots, M - 1$ and $q = 0, 1, \ldots, N - 1$. The original matrix $X$ can be recovered from $\tilde{X}$ through its inverse discrete Fourier transform: $$ x_{mn} = \displaystyle\frac{1}{MN} \sum_{p = 0}^{M - 1} \sum_{q = 0}^{N - 1} \tilde{x}_{pq} e^{i2\pi pm/M} e^{i2\pi qn/N} $$ Since a grayscale image can be represented as a matrix whose elements are 8-bit integers representing pixel values ranging from $0$ (black) to $255$ (white), we can compute its DFT using equation \eqref{post_81059bc883bd6156c2e83f83e2e38c2b_dft_2d}. Interestingly, the magnitude of the DFT of such an image does not contain much information, but its phase does. To clarify what this means, let us define two $M \times N$ matrices $\tilde{X}_{\textrm{mag}}$ and $\tilde{X}_{\textrm{phase}}$ whose elements are given by: $$ \begin{eqnarray} (\tilde{X}_{\textrm{mag}})_{pq} &=& \left|\tilde{x}_{pq}\right| \label{post_81059bc883bd6156c2e83f83e2e38c2b_M}\\[5pt] (\tilde{X}_{\textrm{phase}})_{pq} &=& \tilde{x}_{pq} / \left|\tilde{x}_{pq}\right| \label{post_81059bc883bd6156c2e83f83e2e38c2b_P} \end{eqnarray} $$ Being a complex number, $\tilde{x}_{pq} = \rho_{pq} e^{i\phi_{pq}}$, where $\rho_{pq}$ is its magnitude and $\phi_{pq}$ is its phase. From equations \eqref{post_81059bc883bd6156c2e83f83e2e38c2b_M} and \eqref{post_81059bc883bd6156c2e83f83e2e38c2b_P}, we have that $(\tilde{X}_{\textrm{mag}})_{pq} = \rho_{pq}$ and $(\tilde{X}_{\textrm{phase}})_{pq} = e^{i\phi_{pq}}$, so the matrices $\tilde{X}_{\textrm{mag}}$ and $\tilde{X}_{\textrm{phase}}$ contain only magnitude and phase information of the elements of $\tilde{X}$ respectively.

If we compute the inverse DFTs of $\tilde{X}_{\textrm{mag}}$ and $\tilde{X}_{\textrm{phase}}$, what type of "images" will we recover? Our original image had only real values, but these inverse DFTs will in general not, so we will consider only their real components. Additionally, the pixel values of the resulting images will not necessarily fall within the closed interval $[0, 255]$, but we can clip the negative values (set them to zero) and rescale the nonnegative values to have them fall within this interval. An example of what the resulting images look like is shown on figure 1 (all figures in this post were generated using the script available here).

Fig. 1: An original image (left) and the images produced by computing the inverse DFTs of the magnitude (center) and phase (right) components of the original image's DFT.

From figure 1, we can see that the inverse DFT of the magnitude matrix $\tilde{X}_{\textrm{mag}}$ produces a nearly black image, but the inverse DFT of the phase matrix $\tilde{X}_{\textrm{phase}}$ shows well-defined contours from the original image (if you cannot see them, try increasing the brightness of your screen or click on the figure to see a larger version of it). This indicates that the phase component of the image's DFT carries more information than the magnitude component. To better see this, we can apply histogram equalization to the images produced from the inverse DFTs. The results, shown in figure 2, serve as further confirmation of our hypothesis.

Fig. 2: An original image (left) and the images produced (after histogram equalization) by computing the inverse DFTs of the magnitude (center) and phase (right) components of the original image's DFT.

Comments (1) Direct link

Determining types deduced by the compiler in C++


Posted by Diego Assencio on 2017.08.23 under Programming (C/C++)

Suppose you are debugging a C++ program and need to know what is the type which the compiler deduces for a certain expression. There are many complicated ways of doing this, but in this post, I will show you a very simple trick which allows you to determine types directly at compile time.

The trick is this: declare a class template but do not define it, then attempt to instantiate this class template with the expression whose type you are trying to determine. Here is an example:

/* class template declaration (no definition available) */
template<typename T>
class ShowType;

int main()
{
    signed int x = 1;
    unsigned int y = 2;

    /* (signed int) + (unsigned int): what is the resulting type? */
    ShowType<decltype(x + y)> dummy;

    return 0;
}

In the code above, we are trying to determine the type deduced by the compiler when we add a signed int (x) and an unsigned int (y). This type is decltype(x + y). When the compiler attempts to create an instance of ShowType<decltype(x + y)>, it realizes this is not possible and indicates the problem with a very helpful error message:

error: aggregate ‘ShowType<unsigned int> dummy’ has incomplete type and cannot
be defined

In this message, the compiler (in my case, gcc) is telling us that it tried to create an instance of ShowType<unsigned int> but failed at it. Therefore, the type of the expression x + y is decltype(x + y) = unsigned int. This ŕesulting type comes directly from the integer addition rules specified in the C++ language.

Let's try a more interesting example. In C++, the type deduction rules for template parameters are complex. When in doubt, you can use the trick above to determine which type is deduced by the compiler for a certain template parameter:

/* class template declaration (no definition available) */
template<typename T>
class ShowType;

template<typename T>
void my_function(T x)
{
    ShowType<T> dummy;

    /* do something with x */
}

int main()
{
    const int x = 3;
    my_function(x);

    return 0;
}

One common doubt which developers often have regarding the type T on my_function is: will it be deduced to be int or const int? As it turns out, since we are passing x by value, the compiler will deduce T to be int:

error: ‘ShowType<int> dummy’ has incomplete type

As a final example, let's consider auto. The rules for auto type deduction are usually the same as the ones for template types, but auto type deduction assumes that initializing expressions such as {1,2,3} represent initializer lists. Let's show that in practice:

#include <initializer_list>

template<typename T>
class ShowType;

int main()
{
    auto x = {1,2,3};

    ShowType<decltype(x)> dummy;

    return 0;
}

The error message tells us what we expect:

error: aggregate ‘ShowType<std::initializer_list<int>> dummy’ has incomplete
type and cannot be defined

Notice that we need to pass an actual type (not an expression) to ShowType<T>, so in the examples above in which we wanted to determine the type of a certain expression (e.g. x + y), we needed to enclose the expression with decltype. On the second example, we already had the desired type T available on the definition of my_function, so we could use it directly.

Comments (0) Direct link

How to fix broken MathJax fonts on Linux


Posted by Diego Assencio on 2017.08.09 under Linux (General)

If you are using Linux and your MathJax fonts look ugly, and if you are certain that MathJax is correctly configured on the webpage you are accessing (e.g. by checking that things look fine on another device or browser), then your browser is probably selecting STIX fonts which are installed on your system instead of the ones offered by MathJax. The simplest way to solve this problem is by removing these STIX fonts. On Ubuntu/Debian, this can be done with the following command:

sudo apt remove fonts-stix

You can now see if this was the root cause of the problem by reloading the affected webpage with Ctrl+F5 (this will force your browser to bypass its cache).

Comments (0) Direct link