How to use SIFT algorithm with a color inverted image

Question

For example I have two images, where first one is a regular and second one with a color inversion (I mean 255 - pixel color value).

I've applied SIFT algorithm to both of them using OpenCV and Lowe paper, so now I have key points and descriptors of each image.

KeyPoints positions do match, but KeyPoints orientations and Descriptors values do not, because of color inversion.

I'm curious do anybody try to solve such a problem?

---

In addition here are the gradients example:

I'm using OpenCV C++ implementation using this tutorial and modules/nonfree/src/sift.cpp file. In addition I've made the following method to look at gradients:

void MINE::showKeypoints(cv::Mat image, std::vector<cv::KeyPoint> keypoints, string number)
{
    cv::Mat img;
    image.copyTo(img);

    for(int i=0;i<(int)keypoints.size();i++)
    {
        cv::KeyPoint kp = keypoints[i];

        cv::line(img, cv::Point2f(kp.pt.x ,kp.pt.y), cv::Point2f(kp.pt.x ,kp.pt.y), CV_RGB(255,0,0), 4);
        cv::line(img, cv::Point2f(kp.pt.x ,kp.pt.y), cv::Point2f(kp.pt.x+kp.size*cos(kp.angle),kp.pt.y+kp.size*sin(kp.angle)), CV_RGB(255,255,0), 1);
    }
    cv::imshow (str, img);
}

Example of the gradients.

As you can see gradients of inverted and original images are not opposite

Stony

Can't you just invert the colors of the second? :D – Swimming

no, the point is to make SIFt invariant to color inversion, I know that it is possible to change the 8 bin histogram to 4 bin adding first 4 bins to second 4 bins and changing last 4 with zeros, but it should be something else. – Stony

Answer 1

If you negate the input image then the gradients will have opposite directions (G <- -G).

You need to remind that SIFT descriptors are basically histogram of gradient orientations:

Since the gradient is negated on the inverted image we obtain:

• 0th arrow => 4th arrow
• 1st arrow => 5th arrow
• 2nd arrow => 6th arrow
• 3th arrow => 7th arrow

In other words if you consider the first 8-bins histogram (there are 4x4 such histograms in total), and if you denote a, b, etc the related SIFT descriptors components, we have:

• original image: [a, b, c, d, e, f, g, h]
• inverted image: [e, f, g, h, a, b, c, d]

So you can convert the inverted image SIFT descriptor by swapping the components by 4-sized packs.

Pseudo-algorithm:

# `sift` is the 128-sized array that represents the descriptor
NCELLS = 16
NORI   = 8

0.upto(NCELLS - 1) do |cell|
  offset = cell * NORI
  offset.upto(offset + NORI/2 - 1) do |i|
    sift.swap!(i, i + NORI/2)
  end
end

---

Here's how to verify this with vlfeat:

1. Negate the default image: convert -negate default.pgm negate.pgm
2. Extract keypoints on default image: ./sift --frames default.pgm
3. Select the first keypoint: tail -n 1 default.frame > kpt.frame
4. Describe it with the default image: ./sift --descriptors --read-frames kpt.frame default.pgm
5. Describe it with the negated image: ./sift --descriptors --read-frames kpt.frame negate.pgm
6. Format both descriptors with 4 components per line (see below)

Then visualize the output with e.g. diff -u or opendiff: the lines are swapped 2-by-2 as expected.

cat default.descr | ruby -e\
'STDIN.read.split(" ").each_slice(4) {|s| p s}'\
> default.out

cat negate.descr | ruby -e\
'STDIN.read.split(" ").each_slice(4) {|s| p s}'\
> negate.out

Fifield

thanks for the explanation, but as you can see here i.sstatic.net/XRfdh.png gradients are not absolutely opposite – Stony

See the edit for a step-by-step check with vlfeat SIFT implementation. – Fifield

I don't understand what do you mean by "the edit". I'm using OpenCV implementation, I understand how it works but still don't understand why the gradients should have opposite direction (as shown in screenshot) – Stony

I mean I have edited my answer to include a step-by-step verification with vlfeat software (see above). – Fifield

I'm sorry, but I'm not common with ruby, I've edited my answer with C++ implementation – Stony

Feel free to forget Ruby that I've used to illustrate the pseudo-algorithm. Instead I've used vlfeat's SIFT C implementation and tools to verify things (you should definitely give it a try!). You should try to describe the same keypoint(s) on both images and output the descriptors. – Fifield

alright, I'll try, just for curiosity will the gradients be opposite? :) – Stony

Answer 2

deltheil's answer is correct, but we could easily change the order of 16 by 8 descriptor elements without changing gradient's direction (basically it is the same, but more simple for the implementation)

For example we have 2x4 descriptor,

original was:

[a,b
c,d
e,f
g,h]

inverted will be:

[g,h
e,f
c,d
a,b]

Stony