- メインページ
- モジュール
- ネームスペース
- データ構造
- ファイル

- ファイル一覧
- グローバル

hough.h
1 //
2 // Copyright (c) 2003-2011, Shuichirou Kitou, MIST Project, Nagoya University
3 // All rights reserved.
4 //
5 // Redistribution and use in source and binary forms, with or without modification,
6 // are permitted provided that the following conditions are met:
7 //
8 // 1. Redistributions of source code must retain the above copyright notice,
9 // this list of conditions and the following disclaimer.
10 //
11 // 2. Redistributions in binary form must reproduce the above copyright notice,
12 // this list of conditions and the following disclaimer in the documentation
13 // and/or other materials provided with the distribution.
14 //
15 // 3. Neither the name of the Nagoya University nor the names of its contributors
16 // may be used to endorse or promote products derived from this software
17 // without specific prior written permission.
18 //
19 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR
20 // IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
21 // FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
22 // CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
23 // DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
24 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER
25 // IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF
26 // THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27 //
28
33
34 #ifndef __INCLUDE_MIST_HOUGH__
35 #define __INCLUDE_MIST_HOUGH__
36
37 #ifndef __INCLUDE_MIST_H__
38 #include "mist.h"
39 #endif
40
41 #include <complex>
42 #include <map>
43 #include <vector>
44 #include <algorithm>
45 #include <cmath>
46
47 // mist名前空間の始まり
48 _MIST_BEGIN
49
50 namespace __hough_detail__
51 {
52 typedef std::multimap< size_t, std::complex< int >, std::greater< size_t > > hough_counter;
53
54 // 三角関数計算の高速化のため、あらかじめテーブルを作成する
55 class trigonometric_table
56 {
57 public:
58 typedef size_t size_type;
59
60 private:
61 size_type size_;
62 array< double > cos_table_;
63 array< double > sin_table_;
64
65 public:
66 double sin( size_type angle ) const { return( sin_table_[ angle ] ); }
67 double cos( size_type angle ) const { return( cos_table_[ angle ] ); }
68 size_type size( ) const { return( size_ ); }
69
70 public:
71 trigonometric_table( double rho_resolution, double theta_resolution )
72 : size_( static_cast< size_type >( std::fabs( 3.1415926535897932384626433832795 / theta_resolution ) + 0.5 ) ), cos_table_( size_ ), sin_table_( size_ )
73 {
74 const double rho_inverse = 1.0 / rho_resolution;
75 double angle = 0.0;
76
77 for( size_type i = 0 ; i < size_ ; angle += theta_resolution, i++ )
78 {
79 sin_table_[ i ] = std::sin( angle ) * rho_inverse;
80 cos_table_[ i ] = std::cos( angle ) * rho_inverse;
81 }
82 }
83
84 ~trigonometric_table( )
85 {
86 }
87 };
88
89 class accumulator
90 {
91 public:
92 typedef array2< size_t > data_type;
93 typedef data_type::size_type size_type;
94 typedef data_type::difference_type difference_type;
95
96 private:
97 data_type data_;
98
99 public:
100 accumulator( size_type rho_size, size_type angle_size ) : data_( angle_size + 2, rho_size + 2 ) // 外周1ずつ広い平面を用意する。isPeakCell()で注目Pixelの上下左右をアクセスするため、1Pixelずつ大きくしておく
101 {
102 }
103
104 ~accumulator( )
105 {
106 }
107
108 void count_up( difference_type rho, size_type angle )
109 {
110 this->operator ()( static_cast< difference_type >( rho + ( get_rho_size( ) - 1 ) / 2 ), angle ) ++;
111 }
112
113 void convert_to_counter( hough_counter &c, size_type threshold ) const
114 {
115 int rho_size = static_cast< int >( get_rho_size( ) );
116 size_type angle_size = get_angle_size( );
117
118 #ifdef _OPENMP
119 #pragma omp parallel for schedule( guided )
120 #endif
121 for( int rho = 0 ; rho < rho_size ; ++rho )
122 {
123 for( size_type angle = 0 ; angle < angle_size ; ++angle )
124 {
125 size_type count = at( rho, angle );
126
127 if( ( count > threshold ) && is_peak_cell( rho, angle ) )
128 {
129 #ifdef _OPENMP
130 #pragma omp critical
131 #endif
132 {
133 c.insert( std::make_pair( count, std::complex< int >( rho - ( rho_size - 1 ) / 2, angle ) ) );
134 }
135 }
136 }
137 }
138 }
139
140 private:
141 size_type & operator ()( size_type rho, size_type angle )
142 {
143 return( data_( angle + 1, rho + 1 ) );
144 }
145
146 size_type operator ()( size_type rho, size_type angle ) const
147 {
148 return( data_( angle + 1, rho + 1 ) );
149 }
150
151 size_type & at( size_type rho, size_type angle )
152 {
153 return( this->operator ()( rho, angle ) );
154 }
155
156 size_type at( size_type rho, size_type angle ) const
157 {
158 return( this->operator ()( rho, angle ) );
159 }
160
161 size_type get_rho_size( ) const
162 {
163 return( data_.size2( ) - 2 );
164 }
165
166 size_type get_angle_size( ) const
167 {
168 return( data_.size1( ) - 2 );
169 }
170
171 bool is_peak_cell( size_type rho, size_type angle ) const
172 {
173 size_type level = at( rho, angle );
174
175 return( level > at( rho - 1, angle ) &&
176 level >= at( rho + 1, angle ) &&
177 level > at( rho, angle - 1 ) &&
178 level >= at( rho, angle + 1 ) );
179 }
180 };
181
182 template < class T, class Allocator, class FUNCTOR >
183 accumulator hough_transform( const array2< T, Allocator >& input, double rho_resolution, const trigonometric_table & table, FUNCTOR f )
184 {
185 typedef typename array2< T, Allocator >::size_type size_type;
186 typedef typename array2< T, Allocator >::difference_type difference_type;
187 typedef typename array2< T, Allocator >::value_type value_type;
188
189 const size_type angle_size = table.size( );
190 const size_type rho_size = static_cast< size_type >( ( ( input.width( ) + input.height( ) ) * 2 + 1 ) / rho_resolution );
191
192 accumulator accumulator( rho_size, angle_size );
193
194 int height = static_cast< int >( input.height( ) );
195
196 #ifdef _OPENMP
197 #pragma omp parallel for schedule( guided )
198 #endif
199 for( int j = 0 ; j < height ; j++ )
200 {
201 for( size_type i = 0 ; i < input.width( ) ; i++ )
202 {
203 if( f( input( i, j ) ) )
204 {
205 #ifdef _OPENMP
206 #pragma omp critical
207 #endif
208 for( size_type angle = 0 ; angle < angle_size ; ++angle )
209 {
210 difference_type rho = static_cast< difference_type >( i * table.cos( angle ) + j * table.sin( angle ) + 0.5 );
211 accumulator.count_up( rho, angle );
212 }
213 }
214 }
215 }
216
217 return( accumulator );
218 }
219
220 template < template < typename, typename > class LINES, class TT, class AAllocator >
221 void hough_inverse( const hough_counter & counter, LINES< TT, AAllocator > &lines, double rho_resolution, double theta_resolution, size_t max_lines )
222 {
223 typedef typename LINES< TT, AAllocator >::value_type value_type;
224
225 lines.clear( );
226
227 for( hough_counter::const_iterator ite = counter.begin( ) ; ite != counter.end( ) && lines.size( ) < max_lines ; ++ite )
228 {
229 double rho = ite->second.real( ) * rho_resolution;
230 double theta = ite->second.imag( ) * theta_resolution;
231 lines.push_back( value_type( rho, theta ) );
232 }
233 }
234
235 class foreground_evaluator
236 {
237 public:
238 template < class T >
239 bool operator ()( const T &val ) const
240 {
241 return( val != T( ) );
242 }
243 };
244
245 class background_evaluator
246 {
247 public:
248 template < class T >
249 bool operator ()( const T &val ) const
250 {
251 return( val == T( ) );
252 }
253 };
254 } // namespace __hough_detail__
255
256
264
265
267 namespace line
268 {
282 template < class T, class Allocator, template < typename, typename > class LINES, class TT, class AAllocator, class FUNCTOR >
283 bool hough_transform( const array2< T, Allocator >& input, LINES< TT, AAllocator > &lines, std::size_t max_lines, double rho_resolution, double theta_resolution, size_t threshold, FUNCTOR value_functor )
284 {
285 //三角関数テーブルを作成
286 __hough_detail__::trigonometric_table table = __hough_detail__::trigonometric_table( rho_resolution, theta_resolution );
287
288 // Hough変換...ρ-θ平面をつくる
289 __hough_detail__::accumulator accumulator = __hough_detail__::hough_transform( input, rho_resolution, table, value_functor );
290
291 // ρ-θ平面でCountの多いものから順に取り出す
292 __hough_detail__::hough_counter counter;
293 accumulator.convert_to_counter( counter, threshold );
294
295 // 逆Hough変換
296 __hough_detail__::hough_inverse( counter, lines, rho_resolution, theta_resolution, max_lines );
297
298 return( !lines.empty( ) );
299 }
300
313 template < class T, class Allocator, template < typename, typename > class LINES, class TT, class AAllocator >
314 bool hough_transform( const array2< T, Allocator >& input, LINES< TT, AAllocator > &lines, std::size_t max_lines, double rho_resolution = 1.0, double theta_resolution = 3.1415926535897932384626433832795 / 360.0, size_t threshold = 100 )
315 {
316 return( hough_transform( input, lines, max_lines, rho_resolution, theta_resolution, threshold, __hough_detail__::foreground_evaluator( ) ) );
317 }
318 }
319
321 // ハフ変換グループの終わり
322
323 // mist名前空間の終わり
324 _MIST_END
325
326 #endif // __INCLUDE_MIST_HOUGH__
327