CODEWITHSUNDEEP
calgorithmimage
Boaz Tirosh
Boaz Tirosh

Reputation: 153

Looking for the fastest algorithm (implementing in C) for image manipulation

I have a square matrix (n*n) of chars, and i want to flip the image.

I'm looking to do it in the fastest time possible (don't mind the ram at all at the moment).

The obvious choice will be to just copy the matrix line by line, but i think there is a better way. ideas?

Upvotes: 1

Views: 2319

Answers (4)

Henrique Diomede
Henrique Diomede

Reputation: 1

If you are going to walk through all your matrix, it's highly recommended to use an unidimensional array to represent your matrix because nested fors are very expensive.

Upvotes: 0

Mark Wilkins
Mark Wilkins

Reputation: 41252

Solution 1 - Swap Pointers

Depending on the representation of the data (and assuming each character represents a "pixel"_, it could potentially be accomplished just by swapping pointers around. For example, if it is defined as:

char *matrix[N];

Where each "row" (or "column" depending on the definition) is then dynamically allocated, you could swap pointers. Do this (but in a loop ... I'm just showing the idea of a single swap):

char* tmp = matrix[0];
matrix[0] = matrix[N-1];
matrix[N-1] = tmp;

Depending on the layout, the representation could be rows or columns.

Solution 2 - Don't Move/Swap Anything

Depending on how the data is rendered, the fastest method might not be to flip the data at all. Just display it in a different order. For example, instead of this:

for ( r = 0; r < N; r++ )
   for ( c = 0; c < N; c++ )
      displayMe( r, c, matrix[r][c] );

Do this (or something like it):

for ( r = 0; r < N; r++ )
   for ( c = 0; c < N; c++ )
      displayMe( r, c, matrix[N - r - 1][c] );

Upvotes: 2

spearson
spearson

Reputation: 1016

If what you are actually looking for is a matrix transpose (rotation of 90 degrees) look at Transpose a 2D array

Upvotes: 0

R.. GitHub STOP HELPING ICE
R.. GitHub STOP HELPING ICE

Reputation: 215397

Flipping vertically is pretty easy to do fast: Just allocate an extra temp line and use memcpy to swap entire lines at a time between the top and bottom of the image/matrix.

Flipping horizontally is hard to speed up unless you want to write assembly, and the optimal solution is going to be very cpu-dependent.

Upvotes: 4

Related Questions