Fast inversion of an axis of 3D data stored in a 1D array

Question

I have a large dataset that represents a 3D image (approx 100,000,000 pixels). I want to invert the pixels along the 'z' axis of the image. My data is stored in a byte array where the data is ordered x, y, z (i.e [] = { (x=0,y,z=0), (x=1,y=0,z=0), (x=2,y=0,z=0) ...)

I can easily sort them using the following code, however I am looking to reduce computation time where possible (currently reporting around 7 seconds). I am considering using an array 'sort' function, but am not sure how to handle the indexing.

Here is my current code:

private int GetIndex(Image _image, int _x, int _y, int _z)
{
    return (_z * _image.Size.X * _image.Size.Y) + (_y * _image.Size.X) + _x;;
}

private void InvertZ(Image _image)
{
    for (int z = 0; z < _image.Size.Z/2; z++)
    {
        for (int y = 0; y < _image.Size.Y; y++)
        {
            for (int x = 0; x < _image.Size.X; x++)
            {
                int srcIndex = GetIndex(_image, x, y, z);
                int destIndex = GetIndex(_image, x, y, _image.Size.Z - z - 1);

                byte src = _image.Buffer[srcIndex];
                byte dest = _image.Buffer[destIndex];

                _image.Buffer[srcIndex] = dest;
                _image.Buffer[destIndex] = src;
            }
        }
    }
}

Just a simple question. Why make changes or copy to a new array at all? what if you read the array in a modifyed way instead? do you often modify? — Thomas Andreè Wang, Jan 11 '16 at 06:33

krames · Accepted Answer · 2016-01-11T06:33:28.060

One solution is to copy each frame. Reduces the number of iterations drastically.

    private void InvertZ(Image _image)
    {            
        int frameSize = _image.Size.X * _image.Size.Y;
        byte[] temp = new byte[frameSize];

        for (int z = 0; z < _image.Size.Z / 2; z++)
        {
            int inverseZ = _image.Size.Z - z - 1;

            Array.Copy(_image.Buffer, z * frameSize, temp, 0, frameSize);
            Array.Copy(_image.Buffer, inverseZ * frameSize, _image.Buffer, z * frameSize, frameSize);
            Array.Copy(temp, 0, _image.Buffer, inverseZ  * frameSize, frameSize);
        }
    }

Runtime approx < 18 ms compared to 3175 ms.

Although I've posted my own answer, this solution is faster than mine due to the usage of a (presumable highly optimized) block copy operations, so you've got my vote. — Ivan Stoev, Jan 11 '16 at 12:29

score 0 · Answer 2 · edited May 23 '17 at 10:27

This might be faster that your one loop solution even if it uses several loops, one for each axis.

There are 2 major speed enhancements (very common algorithm enhancements within image processing).

The Image is converted to a array for quick legwork
The index become partly precomputed within the the loops making sure the you calculate as much as possible as few times as possible. (no more use of the built-in thing in Image which is nice for one and another pixel but not suitable for the whole map)

I usually only do this work on 2d so the z axis is just added. it might be faster having it as the last loop. (fringe example running in 2d if y is before x then you loose about 30-40% speed because of the way memory/cache is built Src this happens at 3d as well (that's why I placed the z (levels/pages at the front))

Here is the code I would base my solution on.

private void InvertZ(Image _image)
{            
    byte[] array =imageToByteArray(_image);
    int pageSize = _Image.Size.Y * _Image.Size.X;
    for (int z = 0; z < _image.Size.Z/2; z++)
    {
        int level = z * pageSize;
        int dstLevel = (_image.Size.Z - z - 1) * pageSize;
        for (int x = 0; x < _image.Size.X; x++)
        {
            int Row = x*_Image.Size.Y;
            int RowOnLevel = level + Row ;
            int dstRowOnLevel = dstLevel + xRow;
            for (int y = 0; y < _image.Size.Y; y++)
            {
                int srcIndex = RowOnLevel + y;
                int destIndex = dstRowOnLevel + y;

                byte tmpDest = array[destIndex];
                array[destIndex] = array[srcIndex];
                array[srcIndex] = tmpDest;
            }
        }
    }
    return byteArrayToImage(array);
}

public Image byteArrayToImage(byte[] byteArrayIn)
{
    MemoryStream ms = new MemoryStream(byteArrayIn);
    Image returnImage = Image.FromStream(ms);
    return returnImage;
}

public byte[] imageToByteArray(System.Drawing.Image imageIn)
{
    MemoryStream ms = new MemoryStream();
    imageIn.Save(ms,System.Drawing.Imaging.ImageFormat.Gif);
    return  ms.ToArray();
}

Ivan Stoev · Answer 3 · 2016-01-11T07:14:19.477

You can use the fact that the array layout is like this

Z     Length
====  ======
[0]   x * y
[1]   x * y
[2]   x * y
...
[z-1] x * y

This allows us to greatly reduce index calculations. We can use a variation of the classic O(N) reverse algorithm like this

static void InvertZ(Image _image)
{            
    int len = _image.Size.X * _image.Size.Y;
    for (int lo = 0, hi = (_image.Size.Z - 1) * len; lo < hi; lo += len, hi -= len)
        for (int i = 0; i < len; i++)
            Swap(ref _image.Buffer[lo + i], ref _image.Buffer[hi + i]);
}

static void Swap<T>(ref T a, ref T b) { var c = a; a = b; b = c; }

Fast inversion of an axis of 3D data stored in a 1D array

3 Answers3