Speed up hamming distance for bit arrays

[ymtoo]

The current hamming_distance is slow for bit arrays

julia> b1 = bitrand(512)

julia> b2 = bitrand(512)

julia> @btime hamming_distance($b1, $b2) # before
  773.562 ns (2 allocations: 160 bytes)
0.501953125

as mean converts the bits to floating-point numbers, sums them, and then divides the total by the number of bits. We can replace mean(x) with sum(x)/length(x). If x is a bit array, sum(x::AbstractArray{Bool}) calls count(x) which is much faster than summing floating-point numbers.

julia> @btime hamming_distance($b1, $b2) # after
  47.614 ns (2 allocations: 160 bytes)
0.501953125

About 10x speedup on match_keypoints in the following example.

using ImageFeatures, TestImages, Images, ImageDraw, CoordinateTransformations, Rotations

img = testimage("lighthouse")
img1 = Gray.(img)
rot = recenter(RotMatrix(5pi/6), [size(img1)...] .÷ 2)  # a rotation around the center
tform = rot ∘ Translation(-50, -40)
img2 = warp(img1, tform, axes(img1))

features_1 = Features(fastcorners(img1, 12, 0.35))
features_2 = Features(fastcorners(img2, 12, 0.35))

brisk_params = BRISK()

desc_1, ret_features_1 = create_descriptor(img1, features_1, brisk_params)
desc_2, ret_features_2 = create_descriptor(img2, features_2, brisk_params)

# before
julia> @btime match_keypoints(Keypoints(ret_features_1), Keypoints(ret_features_2), desc_1, desc_2, 0.1)
  422.808 ms (1011294 allocations: 87.96 MiB)

# after 
julia> @btime match_keypoints(Keypoints(ret_features_1), Keypoints(ret_features_2), desc_1, desc_2, 0.1)
  30.256 ms (1011294 allocations: 87.96 MiB)

[timholy]

Another way it's potentially slow is because it allocates a temporary. Have you evaluated

sum((a, b) -> xor(a, b), zip(desc_1, desc_2)) / length(desc_1)

Another option would be to write out the loop; the above relies on a generator and we don't fully specialize generators (at least not yet). Writing it out as a loop is likely to be your fastest option, if you are really performance sensitive.

[ymtoo]

hamming_distance(desc_1, desc_2) = sum((a, b) -> xor(a, b), zip(desc_1, desc_2)) / length(desc_1)

throws an error

ERROR: MethodError: no method matching (::ImageFeatures.var"#115#116")(::Tuple{Bool, Bool})

Closest candidates are:
  (::ImageFeatures.var"#115#116")(::Any, ::Any)
   @ ImageFeatures ~/Projects/ImageFeatures.jl/src/core.jl:78

Stacktrace:
  [1] MappingRF
    @ ./reduce.jl:100 [inlined]
  [2] _foldl_impl
    @ ./reduce.jl:58 [inlined]
  [3] foldl_impl(op::Base.MappingRF{…}, nt::Base._InitialValue, itr::Base.Iterators.Zip{…})
    @ Base ./reduce.jl:48
  [4] mapfoldl_impl(f::ImageFeatures.var"#115#116", op::typeof(Base.add_sum), nt::Base._InitialValue, itr::Base.Iterators.Zip{…})
    @ Base ./reduce.jl:44
  [5] mapfoldl(f::Function, op::Function, itr::Base.Iterators.Zip{Tuple{BitVector, BitVector}}; init::Base._InitialValue)
    @ Base ./reduce.jl:175
  [6] mapfoldl
    @ ./reduce.jl:175 [inlined]
  [7] mapreduce
    @ ./reduce.jl:307 [inlined]
  [8] sum(f::Function, a::Base.Iterators.Zip{Tuple{BitVector, BitVector}})
    @ Base ./reduce.jl:535
  [9] hamming_distance(desc_1::BitVector, desc_2::BitVector)
    @ ImageFeatures ~/Projects/ImageFeatures.jl/src/core.jl:78
 [10] top-level scope
    @ REPL[25]:1
Some type information was truncated. Use `show(err)` to see complete types.

This

hamming_distance(desc_1, desc_2) = sum(ab -> xor(ab...), zip(desc_1, desc_2)) / length(desc_1)

works but it is slow as compared to sum(x)/length(x).

julia> @btime hamming_distance($b1, $b2)
  677.013 ns (0 allocations: 0 bytes)
0.54296875

[timholy]

Thanks for checking. There may be an even faster option, but let's go with this for now.

Thanks for the contribution!