1// Boost.GIL (Generic Image Library) - tests
2//
3// Copyright 2020 Olzhas Zhumabek <anonymous.from.applecity@gmail.com>
4//
5// Use, modification and distribution are subject to the Boost Software License,
6// Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
7// http://www.boost.org/LICENSE_1_0.txt)
8//
9#ifndef BOOST_GIL_EXTENSION_IMAGE_PROCESSING_HOUGH_TRANSFORM_HPP
10#define BOOST_GIL_EXTENSION_IMAGE_PROCESSING_HOUGH_TRANSFORM_HPP
11
12#include <boost/gil/extension/image_processing/hough_parameter.hpp>
13#include <boost/gil/extension/rasterization/circle.hpp>
14
15#include <algorithm>
16#include <cmath>
17#include <cstddef>
18#include <iterator>
19#include <vector>
20
21namespace boost { namespace gil {
22/// \defgroup HoughTransform
23/// \brief A family of shape detectors that are specified by equation
24///
25/// Hough transform is a method of mapping (voting) an object which can be described by
26/// equation to single point in accumulator array (also called parameter space).
27/// Each set pixel in edge map votes for every shape it can be part of.
28/// Circle and ellipse transforms are very costly to brute force, while
29/// non-brute-forcing algorithms tend to gamble on probabilities.
30
31/// \ingroup HoughTransform
32/// \brief Vote for best fit of a line in parameter space
33///
34/// The input must be an edge map with grayscale pixels. Be aware of overflow inside
35/// accumulator array. The theta parameter is best computed through factory function
36/// provided in hough_parameter.hpp
37template <typename InputView, typename OutputView>
38void hough_line_transform(InputView const& input_view, OutputView const& accumulator_array,
39 hough_parameter<double> const& theta,
40 hough_parameter<std::ptrdiff_t> const& radius)
41{
42 std::ptrdiff_t r_lower_bound = radius.start_point;
43 std::ptrdiff_t r_upper_bound = r_lower_bound + radius.step_size * (radius.step_count - 1);
44
45 for (std::ptrdiff_t y = 0; y < input_view.height(); ++y)
46 {
47 for (std::ptrdiff_t x = 0; x < input_view.width(); ++x)
48 {
49 if (!input_view(x, y)[0])
50 {
51 continue;
52 }
53
54 for (std::size_t theta_index = 0; theta_index < theta.step_count; ++theta_index)
55 {
56 double theta_current =
57 theta.start_point + theta.step_size * static_cast<double>(theta_index);
58 std::ptrdiff_t current_r =
59 std::llround(x: static_cast<double>(x) * std::cos(x: theta_current) +
60 static_cast<double>(y) * std::sin(x: theta_current));
61 if (current_r < r_lower_bound || current_r > r_upper_bound)
62 {
63 continue;
64 }
65 std::size_t r_index = static_cast<std::size_t>(
66 std::llround(x: (current_r - radius.start_point) / radius.step_size));
67 // one more safety guard to not get out of bounds
68 if (r_index < radius.step_count)
69 {
70 accumulator_array(theta_index, r_index)[0] += 1;
71 }
72 }
73 }
74 }
75}
76
77/// \ingroup HoughTransform
78/// \brief Vote for best fit of a circle in parameter space according to rasterizer
79///
80/// The input must be an edge map with grayscale pixels. Be aware of overflow inside
81/// accumulator array. Rasterizer is used to rasterize a circle for voting. The circle
82/// then is translated for every origin (x, y) in x y parameter space. For available
83/// circle rasterizers, please look at rasterization/circle.hpp
84template <typename ImageView, typename ForwardIterator, typename Rasterizer>
85void hough_circle_transform_brute(ImageView const& input,
86 hough_parameter<std::ptrdiff_t> const& radius_parameter,
87 hough_parameter<std::ptrdiff_t> const& x_parameter,
88 hough_parameter<std::ptrdiff_t> const& y_parameter,
89 ForwardIterator d_first, Rasterizer rasterizer)
90{
91 for (std::size_t radius_index = 0; radius_index < radius_parameter.step_count; ++radius_index)
92 {
93 const auto radius = radius_parameter.start_point +
94 radius_parameter.step_size * static_cast<std::ptrdiff_t>(radius_index);
95 Rasterizer rasterizer{point_t{}, radius};
96 std::vector<point_t> circle_points(rasterizer.point_count());
97 rasterizer(circle_points.begin());
98 // sort by scanline to improve cache coherence for row major images
99 std::sort(circle_points.begin(), circle_points.end(),
100 [](point_t const& lhs, point_t const& rhs) { return lhs.y < rhs.y; });
101 const auto translate = [](std::vector<point_t>& points, point_t offset) {
102 std::transform(points.begin(), points.end(), points.begin(), [offset](point_t point) {
103 return point_t(point.x + offset.x, point.y + offset.y);
104 });
105 };
106
107 // in case somebody passes iterator to likes of std::vector<bool>
108 typename std::iterator_traits<ForwardIterator>::reference current_image = *d_first;
109
110 // the algorithm has to traverse over parameter space and look at input, instead
111 // of vice versa, as otherwise it will call translate too many times, as input
112 // is usually bigger than the coordinate portion of parameter space.
113 // This might cause extensive cache misses
114 for (std::size_t x_index = 0; x_index < x_parameter.step_count; ++x_index)
115 {
116 for (std::size_t y_index = 0; y_index < y_parameter.step_count; ++y_index)
117 {
118 const std::ptrdiff_t x = x_parameter.start_point + x_index * x_parameter.step_size;
119 const std::ptrdiff_t y = y_parameter.start_point + y_index * y_parameter.step_size;
120
121 auto translated_circle = circle_points;
122 translate(translated_circle, {x, y});
123 for (const auto& point : translated_circle)
124 {
125 if (input(point))
126 {
127 ++current_image(x_index, y_index)[0];
128 }
129 }
130 }
131 }
132 ++d_first;
133 }
134}
135
136}} // namespace boost::gil
137
138#endif
139

source code of boost/libs/gil/include/boost/gil/extension/image_processing/hough_transform.hpp