Add higher order kernel support for Sobel operator

[meshtag]

Description

This pull request intends to automate the process of kernel generation for higher order Sobel derivatives. Generated kernels were cross checked with opencv, test cases have been provided for comparing the obtained kernels with opencv kernels upto 6th order sobel derivative (13x13 dimensional). I used the following piece of code for obtaining opencv kernels.

import numpy as np
import cv2

# In variable name "sobelnx", n denotes dimensions of the nxn kernel which is to be obtained while "x" signifies that the 
# derivative was calculated in horizontal direction. Similar terminology is used for derivative kernels with respect to the vertical
# direction. 

sobel5x = cv2.getDerivKernels(0, 1, 5)
sobel7x = cv2.getDerivKernels(0, 1, 7)
sobel9x = cv2.getDerivKernels(0, 1, 9)
sobel11x = cv2.getDerivKernels(0, 1, 11)
sobel13x = cv2.getDerivKernels(0, 1, 13)

sobel5y = cv2.getDerivKernels(1, 0, 5)
sobel7y = cv2.getDerivKernels(1, 0, 7)
sobel9y = cv2.getDerivKernels(1, 0, 9)
sobel11y = cv2.getDerivKernels(1, 0, 11)
sobel13y = cv2.getDerivKernels(1, 0, 13)

print(np.outer(sobel5x[0], sobel5x[1]))
print(np.outer(sobel7x[0], sobel7x[1]))
print(np.outer(sobel9x[0], sobel9x[1]))
print(np.outer(sobel11x[0], sobel11x[1]))
print(np.outer(sobel13x[0], sobel13x[1]))

print(np.outer(sobel5y[0], sobel5y[1]))
print(np.outer(sobel7y[0], sobel7y[1]))
print(np.outer(sobel9y[0], sobel9y[1]))
print(np.outer(sobel11y[0], sobel11y[1]))
print(np.outer(sobel13y[0], sobel13y[1]))

I have kept the upper limit for dimensions of generated kernel as 31x31 (15th order sobel derivative), I think this limit can be further extended depending upon the execution time taken by other processes of the algorithm apart from kernel generation.

References

https://stackoverflow.com/a/10032882/14958679

Tasklist

• [x] Add test case(s)
• [x] Ensure all CI builds pass
• [ ] Review and approve

[meshtag]

@mloskot , I have my mid-semester examinations in next week and I don't think I will be able to invest time . I will probably be back again on 27-28 th February once they are over. For this reason , I am converting this pull request to draft. Apologies for not doing this earlier. PS : I will have to dig in for checking what exactly is going wrong with builds since it is working fine on my system. I intend to do that with a clear and calm mind after my mid-terms. Apologies again for the delay.

[mloskot]

@meshtag No need to apologise. We're all volunteers here. Good luck with your exams.

[codecov[bot]]

Codecov Report

Merging #562 (155de1c) into develop (0c0fe1a) will increase coverage by 1.27%. The diff coverage is 97.59%.

@@             Coverage Diff             @@
##           develop     #562      +/-   ##
===========================================
+ Coverage    77.81%   79.08%   +1.27%     
===========================================
  Files          110      118       +8     
  Lines         4367     5101     +734     
===========================================
+ Hits          3398     4034     +636     
- Misses         969     1067      +98     

[lpranam]

will have a look tonight :)

[meshtag]

Thanks @mloskot for the approval. I was wondering whether we should increase the upper bound for dimensions of the obtained kernel. The current upper bound for dimensions is 31x31(15th order derivative), I believe this can be fairly extended.

[simmplecoder]

@meshtag there is a way to improve performance by using associativity property of convolution.

Lets say you have some base kernel k and you want to raise it to power p, the easiest way is:

p * p * p *p * ... k times.

What I'm proposing will make log(p) convolutions instead by recursively multiplying results from previous steps:

r(p) = r(p / 2) * r(p / 2) where * is convolution.

You could use this to get to the closest power of two that is not greater than the target.

[simmplecoder]

@meshtag I believe it should also be possible to use some container like std::vector, use gil::interleaved_view or similar, use already existing convolution on image views, then just put the resulting container inside a gil kernel. That way we might have less code duplication and when the optimizations arrive from GSoC this functionality will automatically benefit from it. Perhaps even std::move it inside, so no copying will take place.

If there are changes like padding required for it to work, perhaps we should fix the image view convolution instead? What do you think (@mloskot @lpranam )?

[meshtag]

@simmplecoder , Regarding your first comment, Great Idea ! I can simply use logarithm with base 2 for implementing it (will be implemented probably in my next commit).

Regarding the second comment, I think the major issue in generalizing convolution implementation for vectors as well as image views is the difference in their methods used for accessing individual elements. Moreover, we require a data structure whose size can vary efficiently during runtime , one option is to use dynamic image views but I am not sure if they would perform better than STL vector which is currently used , please do share your opinion on this .

[mloskot]

@simmplecoder The optimisation ideas are interesting, but unless they are trivial, I don't mind if those are developed after the merge, in separate PRs.

[meshtag]

@simmplecoder , I have implemented changes suggested by you for improving performance. Please do give it a look when you get time.

[meshtag]

error: toolset gcc initialization: error: version '8' requested but 'g++-8' not found and version '7.5.0' of default 'g++' does not match error: initialized from /home/runner/work/gil/boost-root/tools/build/src/build/toolset.jam:44: in toolset.using from module toolset /home/runner/work/gil/boost-root/tools/build/src/build-system.jam:543: in process-explicit-toolset-requests from module build-> > system /home/runner/work/gil/boost-root/tools/build/src/build-system.jam:610: in load from module build-system /home/runner/work/gil/boost-root/tools/build/src/kernel/modules.jam:295: in import from module modules /home/runner/work/gil/boost-root/tools/build/src/kernel/bootstrap.jam:139: in boost-build from module /home/runner/work/gil/boost-root/boost-build.jam:17: in module scope from module

@mloskot , I encountered above error in this build and I am rather suspicious, is this related to changes made by me?

[mloskot]

I encountered above error in this build and I am rather suspicious, is this related to changes made by me?

This failure does not seem to be related to any of your changes in this PR. Something is fishy in the CI infrastructure and I will try to look into that tonight.

[meshtag]

@mloskot @lpranam , I think this PR was accidentally closed, can you please reopen it.

[meshtag]

I am working to add support for specifying desired Sobel derivative as well as desired dimensions of the derivative kernel. This will help users to gain more control on the process. Since it will be more feature complete with extra test cases and will have some changes in logic/process, documentation as well as API, I would prefer creating a new PR for it(Please keep this one closed). Will that be fine?

[mloskot]

Sorry, my commit auto-closed this PR by accident.

Yes, the feature completeness sounds good,must have tests and ideally with docs.