Loss of data during the Inverse-FFT of an Image

Question

I am using the following code to convert a Bitmap to Complex and vice versa.

Even though those were directly copied from Accord.NET framework, while testing these static methods, I have discovered that, repeated use of these static methods cause 'data-loss'. As a result, the end output/result becomes distorted.

public partial class ImageDataConverter
{
    #region private static Complex[,] FromBitmapData(BitmapData bmpData)
    private static Complex[,] ToComplex(BitmapData bmpData)
    {
        Complex[,] comp = null;

        if (bmpData.PixelFormat == PixelFormat.Format8bppIndexed)
        {
            int width = bmpData.Width;
            int height = bmpData.Height;
            int offset = bmpData.Stride - (width * 1);//1 === 1 byte per pixel.

            if ((!Tools.IsPowerOf2(width)) || (!Tools.IsPowerOf2(height)))
            {
                throw new Exception("Imager width and height should be n of 2.");
            }

            comp = new Complex[width, height];

            unsafe
            {
                byte* src = (byte*)bmpData.Scan0.ToPointer();

                for (int y = 0; y < height; y++)
                {
                    for (int x = 0; x < width; x++, src++)
                    {
                        comp[y, x] = new Complex((float)*src / 255,
                                                    comp[y, x].Imaginary);
                    }
                    src += offset;
                }
            }
        }
        else
        {
            throw new Exception("EightBppIndexedImageRequired");
        }

        return comp;
    }
    #endregion

    public static Complex[,] ToComplex(Bitmap bmp)
    {
        Complex[,] comp = null;

        if (bmp.PixelFormat == PixelFormat.Format8bppIndexed)
        {
            BitmapData bmpData = bmp.LockBits(  new Rectangle(0, 0, bmp.Width, bmp.Height),
                                                ImageLockMode.ReadOnly,
                                                PixelFormat.Format8bppIndexed);
            try
            {
                comp = ToComplex(bmpData);
            }
            finally
            {
                bmp.UnlockBits(bmpData);
            }
        }
        else
        {
            throw new Exception("EightBppIndexedImageRequired");
        }

        return comp;
    }

    public static Bitmap ToBitmap(Complex[,] image, bool fourierTransformed)
    {
        int width = image.GetLength(0);
        int height = image.GetLength(1);

        Bitmap bmp = Imager.CreateGrayscaleImage(width, height);

        BitmapData bmpData = bmp.LockBits(
            new Rectangle(0, 0, width, height),
            ImageLockMode.ReadWrite,
            PixelFormat.Format8bppIndexed);

        int offset = bmpData.Stride - width;
        double scale = (fourierTransformed) ? Math.Sqrt(width * height) : 1;

        unsafe
        {
            byte* address = (byte*)bmpData.Scan0.ToPointer();

            for (int y = 0; y < height; y++)
            {
                for (int x = 0; x < width; x++, address++)
                {
                    double min = System.Math.Min(255, image[y, x].Magnitude * scale * 255);

                    *address = (byte)System.Math.Max(0, min);
                }
                address += offset;
            }
        }

        bmp.UnlockBits(bmpData);

        return bmp;
    }
}

(The DotNetFiddle link of the complete source code)

(ImageDataConverter)

Output:

As you can see, FFT is working correctly, but, I-FFT isn't.

That is because bitmap to complex and vice versa isn't working as expected.

What could be done to correct the ToComplex() and ToBitmap() functions so that they don't loss data?

Answer 1

I do not code in C# so handle this answer with extreme prejudice!

Just from a quick look I spotted few problems:

1. ToComplex()

   Is converting BMP into 2D complex matrix. When you are converting you are leaving imaginary part unchanged, but at the start of the same function you have:

   Complex[,] complex2D = null;
   complex2D = new Complex[width, height];
   

   So the imaginary parts are either undefined or zero depends on your complex class constructor. This means you are missing half of the data needed for reconstruction !!! You should restore the original complex matrix from 2 images one for real and second for imaginary part of the result.

2. ToBitmap()

   You are saving magnitude which is I think sqrt( Re*Re + Im*Im ) so it is power spectrum not the original complex values and so you can not reconstruct back... You should store Re,Im in 2 separate images.

3. 8bit per pixel

   That is not much and can cause significant round off errors after FFT/IFFT so reconstruction can be really distorted.

[Edit1] Remedy

There are more options to repair this for example:

1. use floating complex matrix for computations and bitmap only for visualization.

   This is the safest way because you avoid additional conversion round offs. This approach has the best precision. But you need to rewrite your DIP/CV algorithms to support complex domain matrices instead of bitmaps which require not small amount of work.

2. rewrite your conversions to support real and imaginary part images

   Your conversion is really bad as it does not store/restore Real and Imaginary parts as it should and also it does not account for negative values (at least I do not see it instead they are cut down to zero which is WRONG). I would rewrite the conversion to this:

   // conversion scales
   float Re_ofset=256.0,Re_scale=512.0/255.0;
   float Im_ofset=256.0,Im_scale=512.0/255.0;
   
   private static Complex[,] ToComplex(BitmapData bmpRe,BitmapData bmpIm)
    {
    //...
    byte* srcRe = (byte*)bmpRe.Scan0.ToPointer();
    byte* srcIm = (byte*)bmpIm.Scan0.ToPointer();
    complex c = new Complex(0.0,0.0);
    // for each line
    for (int y = 0; y < height; y++)
     {
     // for each pixel
     for (int x = 0; x < width; x++, src++)
      {
      complex2D[y, x] = c;
      c.Real      = (float)*(srcRe*Re_scale)-Re_ofset;
      c.Imaginary = (float)*(srcIm*Im_scale)-Im_ofset;
      }
     src += offset;
     }         
    //...
    }
   public static Bitmap ToBitmapRe(Complex[,] complex2D)
    {
    //...
    float Re = (complex2D[y, x].Real+Re_ofset)/Re_scale;
    Re = min(Re,255.0);
    Re = max(Re,  0.0);
    *address = (byte)Re;
    //...
    }
   public static Bitmap ToBitmapIm(Complex[,] complex2D)
    {
    //...
    float Im = (complex2D[y, x].Imaginary+Im_ofset)/Im_scale;
    Re = min(Im,255.0);
    Re = max(Im,  0.0);
    *address = (byte)Im;
    //...
    }
   

   Where:

   Re_ofset = min(complex2D[,].Real);
   Im_ofset = min(complex2D[,].Imaginary);
   Re_scale = (max(complex2D[,].Real     )-min(complex2D[,].Real     ))/255.0;
   Im_scale = (max(complex2D[,].Imaginary)-min(complex2D[,].Imaginary))/255.0;
   

   or cover bigger interval then the complex matrix values.

   You can also encode both Real and Imaginary parts to single image for example first half of image could be Real and next the Imaginary part. In that case you do not need to change the function headers nor names at all .. but you would need to handle the images as 2 joined squares each with different meaning ...

   You can also use RGB images where R = Real, B = Imaginary or any other encoding that suites you.

[Edit2] some examples to make my points more clear

1. example of approach #1

   The image is in form of floating point 2D complex matrix and the images are created only for visualization. There is little rounding error this way. The values are not normalized so the range is <0.0,255.0> per pixel/cell at first but after transforms and scaling it could change greatly.

   

   As you can see I added scaling so all pixels are multiplied by 315 to actually see anything because the FFT output values are small except of few cells. But only for visualization the complex matrix is unchanged.

2. example of approach #2

   Well as I mentioned before you do not handle negative values, normalize values to range <0,1> and back by scaling and rounding off and using only 8 bits per pixel to store the sub results. I tried to simulate that with my code and here is what I got (using complex domain instead of wrongly used power spectrum like you did). Here C++ source only as an template example as you do not have the functions and classes behind it:

   transform t;
   cplx_2D  c;
   rgb2i(bmp0);
   c.ld(bmp0,bmp0);
   null_im(c);
   c.mul(1.0/255.0);
   
   c.mul(255.0); c.st(bmp0,bmp1); c.ld(bmp0,bmp1); i2iii(bmp0); i2iii(bmp1); c.mul(1.0/255.0);
   bmp0->SaveToFile("_out0_Re.bmp");
   bmp1->SaveToFile("_out0_Im.bmp");
   
   t. DFFT(c,c);
   c.wrap();
   
   c.mul(255.0); c.st(bmp0,bmp1); c.ld(bmp0,bmp1); i2iii(bmp0); i2iii(bmp1); c.mul(1.0/255.0);
   bmp0->SaveToFile("_out1_Re.bmp");
   bmp1->SaveToFile("_out1_Im.bmp");
   
   c.wrap();
   t.iDFFT(c,c);
   
   c.mul(255.0); c.st(bmp0,bmp1); c.ld(bmp0,bmp1); i2iii(bmp0); i2iii(bmp1); c.mul(1.0/255.0);
   bmp0->SaveToFile("_out2_Re.bmp");
   bmp1->SaveToFile("_out2_Im.bmp");
   

   And here the sub results:

   

   As you can see after the DFFT and wrap the image is really dark and most of the values are rounded off. So the result after unwrap and IDFFT is really pure.

   Here some explanations to code:

   • c.st(bmpre,bmpim) is the same as your ToBitmap
   • c.ld(bmpre,bmpim) is the same as your ToComplex
   • c.mul(scale) multiplies complex matrix c by scale
   • rgb2i converts RGB to grayscale intensity <0,255>
   • i2iii converts grayscale intensity ro grayscale RGB image

Answer 2

I'm not really good in this puzzles but double check this dividing.

comp[y, x] = new Complex((float)*src / 255, comp[y, x].Imaginary);

You can loose precision as it is described here Complex class definition in Remarks section. May be this happens in your case. Hope this helps.