Image inversion is the altering of intensities or colors of an image from normal form to an opposite representation.
An inverted image could be interpreted as a digital version of image negatives. After inversion, every color takes the exact opposite one (I know this
Image inversion is the altering of intensities or colors of an image from normal form to an opposite representation.
An inverted image could be interpreted as a digital version of image negatives. After inversion, every color takes the exact opposite one (I know this terminology is not that scientific, but it’s useful as a conceptual information). Let’s put this in more scientific terms. A positive image should be defined as a normal, original RGB or gray image. A negative image denotes a tonal inversion of a positive image, in which light areas appear dark and dark areas appear light. In negative images, a color reversing is also achieved, such that the red areas appear cyan, greens appear magenta, and blues appear yellow. In simpler sense, for the grayscale case, a black and white image, using 0 for black and 255 for white, a near-black pixel value of 5 will be converted to 250, or near-white.
Image inversion is one of the easiest techniques in image processing. Therefore, it’s very applicable to demonstrations of performance, acceleration, and optimization. Many of the state of the art image processing libraries such as OpenCV, Gandalf, VXL etc., perform this operation as fast as possible, even though some more accelerations using parallel hardware are possible.
In this article, I will demonstrate three implementations of image inversion: a basic implementation, an optimized one (in C level), and an optimized one using enhanced instructions of modern CPUs (for our case, SSE2).
The code uses OpenCV, not for the implementation of the algorithms, but only for reading the image and displaying it. So, if you don’t know how to use or configure it, please refer to the OpenCV documentation, or simply: http://opencv.willowgarage.com/wiki/VisualC%2B%2B.
For every pixel I(x,y), the inversion mapping is defined by Y(x,y)=255-I(x,y). For color images, the exact same formula is applied for all three channels (R,G,B). In computer language, this is Y(x,y)=~I(x,y). Here is how the basic algorithm looks like:
for (;i!=src->imageSize; i++)
Image inversion is the same as inverting every bit of the pixel value. 1->0 and 0->1. In short, it’s not an operation. Many modern processors have registers composed of 32 (we don’t care about 64 bit machines right now). Because bit inversion is independent of data size, we should acquire data as big as our register size, to fully utilize the registers. That’s why we represent a byte image as an integer pointer, which has four times smaller size. In other words:
Sizeof(uchar) * imagesize = sizeof(int) * imagesize/4
This way, we could gain up to 3x speed.
The goal of loop unwinding is to increase the program's speed by reducing (or eliminating) the "end of loop" test on each iteration. Loops can be re-written as a sequence of independent statements which eliminates the loop controller overhead. Significant gains can be realized if the speed gained (by eliminating the "end of loop" test) offsets the performance reduction caused by the increased size of the program. Furthermore, if the statements in the loop are independent of each other, statements that occur earlier in the loop do not affect statements that follow them, and the statements can be executed in parallel. (Wikipedia)
Here is a simple loop unrolling example:
A procedure in a computer program is to delete 100 items from a collection. This is accomplished by means of a
for-loop which calls the function
for (int x = 0; x < 100; x++)
If this part of the program is to be optimized, and the overhead of the loop requires significant resources compared to that for
delete(x), loop unwinding can be used to speed it up. This will result in an optimized code fragment like:
for (int x = 0; x < 100; x += 5)
As a result of this modification, the new program has to make only twenty loops, instead of a hundred. There are now a fifth as many jumps and conditional branches that need to be taken, which over many iterations would be a great improvement in the loop administration time. The final algorithm for processing one row looks like:
for( ; i <= step1 - 16; i += 16 )
const int* src1i=(const int*)(src1+i);
int t0 = ~(src1i);
int t1 = ~(src1i);
int t2 = ~(src1i);
int t3 = ~(src1i);
SSE2 Integer Instructions
Because we process the data using an int pointer, we could make use of SSE2 integer arithmetic. This way, we could process four
int values at the same time. Discussion of the SSE2 entire architecture is not the aim of this article. If you are not sure how to use them, please refer to web sites like:
(I am sorry; I don’t know a great SSE tutorial on the web.)
To implement inversion using SSE2, we should take the optimized inversion code and convert it into SSE2. However, as far as I know, SSE2 doesn’t have a direct NOT instruction. Instead, we make use of the
pandn (pac