.md

Final submission report for GSoC 2021

Details

Name	Prathamesh Tagore
Organization	Boost C++ Libraries
Mentors	Pranam Lashkari, Olzhas Zhumabek
Project Title	Boost.GIL : 2D convolution and correlation
Project page	https://github.com/boostorg/gil/projects/9

Project Description

• Align 2D convolution implementation with 1D convolution implementation in Boost GIL and obtain subsequent optimization in performance.
• Add support for all pre-existing boundary options namely
  1. Extend Zero (Assume all extrapolated pixels as zero pixels -> 000|abcde|000).
  2. Extend Constant (Assign the value of nearest boundary pixel to all extrapolated pixels -> aaa|abcde|eee).
  3. Extend Padded (Assume a subimage view is passed to the algorithm and fill extrapolated pixels with values from original parent view -> pqr|abcde|xyz).
  4. Output Zero (Do not perform extrapolation, instead assign boundary pixels of destination image as zero).
  5. Output Ignore (Do not perform extrapolation, instead assign boundary pixels of source image to destination image).
• Provide a mechanism to deal with separable convolution.
• Complement all novel features with tests and documentation.

Summary of work done

• 2D convolution implementation was completely aligned with its 1D counterpart. APIs for both implementations are consistent and offer suitable functionalities.
• 2D support for all pre-existing boundary options was added. Additionally, an extra boundary option(extend_reflection) was proposed for both 1D and 2D convolution implementations. To summarize, following are the supported methods of boundary extrapolation :
  1. Extend Zero (Assume all extrapolated pixels as zero pixels -> 000|abcde|000).
  2. Extend Constant (Assign the value of nearest boundary pixel to all extrapolated pixels -> aaa|abcde|eee).
  3. Extend Padded (Assume a subimage view is passed to the algorithm and fill extrapolated pixels with values from original parent view -> pqr|abcde|xyz).
  4. Extend Reflection (Assign the reflection of boundary pixels to extrapolated pixels -> cba|abcde|edc).
  5. Output Zero (Do not perform extrapolation, instead assign zero to boundary pixels of destination image.)
  6. Output Ignore (Do not perform extrapolation, instead assign boundary pixels of source image to destination image's boundary).
• A custom algorithm was written for handling spatial separable convolution in GIL and was interfaced with 2D convolution API. The algorithm detects whether a 2D kernel is spatially separable and returns separated kernels if the input kernel is separable.
• Tests were written for all boundary options along with separable convolution. I have used OpenCv to verify the correctness of novel implementation. To summarise, the algorithm is verified by 650 tests created by considering all possible positions of anchor point with all possible boundary options for a non-separable 5x5 kernel. 50 tests were written separately for verifying separable correlation. All novel functions for 2D convolution and correlation are provided with documentation.
• Performance was improved by implementing a better temporal access pattern for the algorithm. Though this improvement provides a considerable betterment in performance, it can still be improved by using generic vectorization. Since hardware specific vectorization would restrict our users, we decided to work on a generic implementation of vectorization containing support for all common architectures in post GSoC period. Current implementation is designed by keeping this in mind and we can very easily modify it to incorporate above mentioned modification.
• Additionally, documentation and tests were added for pre-existing 1D convolution implementation.

Discussion and updates

• I have reported my weekly updates on every Monday during all 10 weeks of GSoC coding period. These reports are available in this thread on Boost GIL mailing list.
• Our discussions regarding optimization decisions are documented in this thread on Boost GIL mailing list.
• Apart from this, I have sent individual emails to share my updates in community bonding period on Boost GIL mailing list. They can be found here :
  • Community bonding period week 1
  • Community bonding period week 2
  • Community bonding period week 3

List of opened issues :

• #608 Add "Reflection" option for boundary handling in 1D correlation.
• #609 Add separate implementation of 2D correlation
• #610 Provide more boundary options in 2D convolution
• #623 kernel_2d_fixed giving false assertion errors

List of opened pull requests :

• #611 Add remaining pieces of documentation in convolve.hpp
• #612 Add tests for checking boundary options in 1D convolution
• #613 Add reflection option for boundary handling in 1D correlation
• #624 Improved 2D convolution and correlation

List of separate contributions to the project :

• #585 Add rasterizer support for ellipse
• #541 Added all standard morphological transformations
• #562 Add higher order kernel support for Sobel operator
• #581 Port TuttleOFX extension : pattern
• #582 Port TuttleOFX extension : shrink
• #583 Port TuttleOFX extension : aligned
• #560 Fix sphinx installation link in docs readme

Conclusion :

All goals mentioned in the proposal were fulfilled. Additionally, an extra feature, tests and documentation were added for the 1D convolution API.

Working on this project has been a really great experience for me. I have learned a lot in these past 10 weeks which would help me in all of my future endeavours. I thank my mentors Pranam Lashkari and Olzhas Zhumabek for their constant guidance and support. I would also like to thank Mateusz Łoskot for his guidance. Finally, I am grateful to Google for providing such a wonderful oppurtunity to all open source student developers around the globe.