A question about a bit-exact implementation of SIFT

[Yoshio Kato]

Hi everyone,

My name is Yoshio Kato. I'm interested in the project for "Better SIFT in the main repository" and I have a question about it.

One of the expected outcome is "Convert it to bit-exact implementation that does not use floating-point operations", but what does "bit-exact implementation" means?  Is there a reference implementation?

I would appreciate it if anyone could reply to me.

Best Regards,

Kato

[Виталий Тузов]

Hi Kato,

At the the moment SIFT use floating-point for intermediate data representation that could cause different results on different platforms due to different precision of specific hardware floating point math implementations on different platforms. Especially if these platforms are capable of math operation fusing. That lead to different results of the same algorithm on different platforms and make debugging a real pain because even optimization level of your compiler could affect output of the code.

The main idea behind bit-exactness is to avoid using of floating point wherever possible and to implement all floating point operations via integer math based software implementation to ensure the result will be exactly the same up to the least significant bit on each and every platform regardless of hardware and software configuration.

To sum up AFAIK there is no reference implementation for bit-exact SIFT, however any reasonably precise implementation could be considered as a reference since it produce stable result quite close to the result of existing floating-point implementation.

Best regards,

Vitaly

[Yoshio Kato]

Hi Vitaly,

Thank you for replying. I hear that changing the order of add operations will also cause different results, so it will be difficult to distinguish which code is non-reproducible...

I will read the source code more deeply.

Best regards,

Kato

2020年3月11日水曜日 1時06分18秒 UTC+9 Виталий Тузов:

[Vadim Pisarevsky]

Hello Kato, Vitaly,

just to add to Vitaly's response. Essentially, SIFT keypoint detector performs a set of Gaussian blur operations to construct scale-space representation of the processed image followed by non-maxima suppression in this 3D scale-space (scale-x-y).

We can try to implement this algorithm in fixed-point arithmetics, so that we get absolutely the same results on every platform. Several years ago I tried to implement SIFT keypoint detector using 16-bit fixed-point arithmetic, but that version produced worse results (less keypoints, worse stability etc.). Maybe this attempt should be repeated using 32-bit fixed-point arithmetic or mixed 16-32-bit fixed-point arithmetics.

Computing the SIFT descriptors in fixed-point arithmetics is another task. Maybe for now we should stick to FP32 for the descriptors. However, since we will be refactoring SIFT anyway to moving it from opencv_contrib to opencv, I would like to add an option to output 8-bit descriptors instead of 32-bit floating-point, i.e. the descriptor could be made 128-element vector of 8-bit numbers, not 128-element vector of 32-bit floating-point numbers. This is what David Lowe used in his paper. 8-bit descriptors take less space and should probably faster to compare than 32-bit floating-point descriptors.

Regards,

Vadim

[Yoshio Kato]

Hello Vadim, Vitaly,

Thank you for your advice. I wrote a draft proposal for this project. Could you give me some feedback?

https://docs.google.com/document/d/1D1s8NqIWntTiAxwj9D5mSDnA7J-RYlLF91lpkWJtDgk/edit?usp=sharing

Regards,

Kato

2020年3月12日木曜日 1時40分22秒 UTC+9 Vadim Pisarevsky:

[Vadim Pisarevsky]

Hello,

the proposal is good, but lacks some depth, I think.

The big part of the proposal is the detailed schedule. It's too detailed to be relevant, but at least it shows that you have thought a bit about the tasks that need to be accomplished.

Please, expand the resume part: you did not specify how many years you studied in the University. It would be nice if you specify some programming  projects, to the level of details what is allowed, on which you have been working. I mean professional projects, student projects, your hobby projects.

Here is a small assignment for you, solution for which you are welcome to include to your application, to make it more comprehensive:

as a part of this project, we want to put A-SIFT from a sample Python script into OpenCV itself (C++ implementation) and make it parallel. One common problem with parallel implementation of various algorithms is regression testing. We want to make the results of parallel A-SIFT deterministic, regardless on the number of processing threads. Basically, the results should always be the same as the sequential version of A-SIFT would produce. Please, think of how it can be done. No need to write C++ code, just describe the algorithm in words or in pseudo-code.

Regards,

Vadim

[Yoshio Kato]

Hello,

We want to make the results of parallel A-SIFT deterministic, regardless on the number of processing threads. 

In the Python implementation, the code is already parallelized by using multiprocess.Pool and I think that code is deterministic if the float operations are deterministic because "imap" function will not shuffle the order of input parameters.  So I am going to use that code as reference and implement it by using cv::parallel_for_ and assign the index of cv::Range to the order of input affine parameters.

Should I optimize that loop more? (for example, there are same GaussianBlur operations at affine_skew() in different processes)

Regards,

Kato

2020年3月24日火曜日 19時53分05秒 UTC+9 Vadim Pisarevsky:

[Vadim Pisarevsky]

Hello,

you are right! The whole set of transformations to perform is prepared and is then split by threads.

Ok, the problem is solved then, just need to convert it accurately to C++ and implement regression tests. For ASIFT threading of each single SIFT invocation is not necessarily, however when SIFT is used as standalone algorithm outside of ASIFT, threading may be useful. GaussianBlur are not the same, of course, they are applied to images that are distorted in different ways. If you suggest to swap GaussianBlur() and warpAffine() - it will definitely produce different results and maybe not very good results. So I suggest to keep the scheme of the Python implementation.

Ok, so please, extend your proposal a bit, add more information about yourself and more information of what you are going to do. The exact schedule, like "this week I'm going to do this, next week I'm going to do that" is not as important as the list of items (with some explanation for each one).

Regards,

Vadim