Add distance transform functionality

[harshitpant1]

Description

Adds Distance Transform functionality to GIL, using algorithms which run in linear time in the worst case.

References

Precise Euclidean distance transform - http://www.theoryofcomputing.org/articles/v008a019/v008a019.pdf

Manhattan and chessboard distance transforms - Principles of Digital Image Processing - core Techniques by Wilhelm Burger, Mark J.Burge.

Approximate Euclidean distance transform - http://www.cmm.mines-paristech.fr/~marcoteg/cv/publi_pdf/MM_refs/1986_Borgefors_distance.pdf

Tasklist

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

[harshitpant1]

Aside from the first wikipedia test, all other test have been verified with openCV.

import numpy as np
import cv2 as cv

################################################################################################
# test_chessboard_uint16_t_input_uint8_t_output_distance_from_on_pixels

img2 = np.array([[255,   0, 255, 255, 255, 255, 255],
                 [255, 255, 255, 255, 255, 255, 255],
                 [255, 255, 255, 255, 255, 255, 255],
                 [255, 255, 255, 255, 255, 255, 255],
                 [255, 255, 255,   0, 255, 255, 255],
                 [255, 255, 255, 255, 255, 255, 255],
                 [255, 255, 255, 255, 255, 255, 255]], dtype = np.uint8)

#/ 8 bit (16 bit tested in gil) image used which is inverted to test distance from on pixels

test2_chessboard_three = cv.distanceTransform(img2, cv.DIST_C,cv.DIST_MASK_3)
print("\n test2_chessboard mask size 3: ")
print(test2_chessboard_three)

################################################################################################
# test_euclidean_approx_and_manhattan_uint8_t_input_float32_t_output_distance_from_off_pixels

img3 = np.array([
 [255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255],
 [255,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0, 255],
 [255,   0, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,   0, 255],
 [255,   0, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,   0, 255],
 [255,   0, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,   0, 255],
 [255,   0, 255, 255, 255,   0,   0,   0,   0,   0, 255, 255, 255,   0, 255],
 [255,   0, 255, 255, 255,   0, 255, 255, 255,   0, 255, 255, 255,   0, 255],
 [255,   0, 255, 255, 255,   0, 255, 255, 255,   0, 255, 255, 255,   0, 255],
 [255,   0, 255, 255, 255,   0, 255, 255, 255,   0, 255, 255, 255,   0, 255],
 [255,   0, 255, 255, 255,   0,   0,   0,   0,   0, 255, 255, 255,   0, 255],
 [255,   0, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,   0, 255],
 [255,   0, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,   0, 255],
 [255,   0, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,   0, 255],
 [255,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0, 255],
 [255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255]], dtype = np.uint8)

test3_euclidean_five = cv.distanceTransform(img3, cv.DIST_L2,cv.DIST_MASK_5)
print("\n test3_euclidean approx mask size 5: ")
print(test3_euclidean_five)

test3_manhattan_five = cv.distanceTransform(img3, cv.DIST_L1,cv.DIST_MASK_5)
print("\n test3_manhattan approx mask size 5: ")
print(test3_manhattan_five)

################################################################################################
# test_all_uint8_t_input_float32_t_ouptut_distance_from_off_pixels
img4 = np.array([
 [255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255],
 [255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 0, 255, 255, 255, 255],
 [255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255],
 [255, 255, 0, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255],
 [255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255],
 [255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255],
 [255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255],
 [255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255],
 [255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255],
 [255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255],
 [255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255],
 [255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255],
 [255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255],
 [255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255],
 [255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 0]], dtype = np.uint8)

test4_precise_euclidean = cv.distanceTransform(img4, cv.DIST_L2,cv.DIST_MASK_PRECISE)
print("\n test4_ Precise Euclidean: ")
print(test4_precise_euclidean)

test4_euclidean_three = cv.distanceTransform(img4, cv.DIST_L2,cv.DIST_MASK_3)
print("\n test4_ Euclidean Approximation mask size 3 \n")
print(test4_euclidean_three)

test4_euclidean_five = cv.distanceTransform(img4, cv.DIST_L2,cv.DIST_MASK_5)
print("\n test4_ Euclidean Approximation mask size 5: ")
print(test4_euclidean_five)

test4_manhattan_three = cv.distanceTransform(img4, cv.DIST_L1,cv.DIST_MASK_3)
print("\n test4_ manhattan mask size 3: ")
print(test4_manhattan_three)

test4_manhattan_five = cv.distanceTransform(img4, cv.DIST_L1,cv.DIST_MASK_5)
print("\n test4_ manhattan mask size 5: ")
print(test4_manhattan_five)

test4_chessboard_three = cv.distanceTransform(img4, cv.DIST_C,cv.DIST_MASK_3)
print("\n test4_chessboard mask size 3: ")
print(test4_chessboard_three)

test4_chessboard_five = cv.distanceTransform(img4, cv.DIST_C,cv.DIST_MASK_5)
print("\n test4_chessboard mask size 3: ")
print(test4_chessboard_five)

[codecov[bot]]

Codecov Report

Merging #594 (8c12da2) into develop (bbdce36) will increase coverage by 0.69%. The diff coverage is 100.00%.

:exclamation: Current head 8c12da2 differs from pull request most recent head bd907af. Consider uploading reports for the commit bd907af to get more accurate results

@@             Coverage Diff             @@
##           develop     #594      +/-   ##
===========================================
+ Coverage    78.72%   79.41%   +0.69%     
===========================================
Files          118      119       +1     
Lines         5034     5204     +170     
===========================================
+ Hits          3963     4133     +170     
Misses        1071     1071              

[harshitpant1]

As you might have noticed at some places (especially in the test file) reformatting should have been done after using clang-format, but I had a feeling to keep things as they are after they have been automatically formatted.

Let me know about your preferences on this.

Note that the second last commit has proper manual formatting.

[mloskot]

It is fine to try format any new code using the .clang-format that we are discussing as part of https://github.com/boostorg/gil/pull/596