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

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

dp_matching.h
説明を見る。
1 //
2 // Copyright (c) 2003-2011, 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_DP_MATCHING_H__
35 #define __INCLUDE_DP_MATCHING_H__
36
37 #include <mist/mist.h>
38 #include <mist/config/color.h>
39 #include <vector>
40 #include <functional>
41
42
43 // mist名前空間の始まり
44 _MIST_BEGIN
45
46
47 namespace __dp__
48 {
49 // 要素間の2乗距離を返すファンクタ（インスタンスはコンストラクタのデフォルト引数となる）
50 template< typename Type >
51 struct square_error : public std::binary_function< Type, Type, double >
52 {
53 double operator( )( const Type &v0, const Type &v1 ) const
54 {
55 return ( static_cast< double >( v0 ) - v1 ) * ( static_cast< double >( v0 ) - v1 );
56 }
57 };
58
59 // 要素間の2乗距離を返すファンクタ（インスタンスはコンストラクタのデフォルト引数となる）
60 template< typename Type >
61 struct square_error< mist::rgb< Type > > : public std::binary_function< mist::rgb< Type >, mist::rgb< Type >, double >
62 {
63 double operator( )( const mist::rgb< Type > &v0, const mist::rgb< Type > &v1 ) const
64 {
65 return ( static_cast< double >( v0.r ) - v1.r ) * ( static_cast< double >( v0.r ) - v1.r ) + ( static_cast< double >( v0.g ) - v1.g ) * ( static_cast< double >( v0.g ) - v1.g ) + ( static_cast< double >( v0.b ) - v1.b ) * ( static_cast< double >( v0.b ) - v1.b );
66 }
67 };
68 }
69
70 // 対応付け結果を格納するための構造体
71 class dp_pair
72 {
73 size_t a_;
74 size_t b_;
75
76 public:
77
78 dp_pair( )
79 {
80 }
81
82 dp_pair( const size_t a, const size_t b ) : a_( a ), b_( b )
83 {
84 }
85
86 size_t a( ) const
87 {
88 return a_;
89 }
90
91 size_t b( ) const
92 {
93 return b_;
94 }
95 };
96
97 inline bool operator !=( const dp_pair &p0, const dp_pair &p1 )
98 {
99 return ( ( p0.a( ) != p1.a( ) ) || ( p0.b( ) != p1.b( ) ) );
100 }
101
102 inline std::ostream &operator <<( std::ostream &out, const dp_pair &in )
103 {
104 return ( out << "( " << in.a( ) << ", " << in.b( ) << " )" );
105 }
106
107
115
116
117
164 //1 #include <functional>
174 template< typename Value_type, typename Functor = __dp__::square_error< Value_type > >
175 class dp_matching
176 {
177 typedef typename Functor::result_type distance_type;
178
179 mist::array< Value_type > pattern_a_;
180 mist::array< Value_type > pattern_b_;
181 mist::array< dp_pair > path_;
182 distance_type distance_;
183 double weight_0_;
184 double weight_1_;
185 double weight_2_;
186 Functor func_;
187
188 distance_type __distance( const size_t i0, const size_t i1 ) const
189 {
190 return func_( pattern_a_[ i0 ], pattern_b_[ i1 ] );
191 }
192
193 void __find_path( )
194 {
195 mist::array2< distance_type > distance_array( pattern_a_.size( ), pattern_b_.size( ) );
196 mist::array2< size_t > path_array( pattern_a_.size( ), pattern_b_.size( ) );
197 distance_array( 0, 0 ) = __distance( 0, 0 );
198 for( size_t i = 1 ; i < distance_array.width( ) ; i ++ )
199 {
200 distance_array( i, 0 ) = static_cast< distance_type >( distance_array( i - 1, 0 ) + __distance( i, 0 ) * weight_0_ );
201 path_array( i, 0 ) = 0;
202 }
203 for( size_t j = 1 ; j < distance_array.height( ) ; j ++ )
204 {
205 distance_array( 0, j ) = static_cast< distance_type >( distance_array( 0, j - 1 ) + __distance( 0, j ) * weight_2_ );
206 path_array( 0, j ) = 2;
207 for( size_t i = 1 ; i < distance_array.width( ) ; i ++ )
208 {
209 const distance_type distance = __distance( i, j );
210 const distance_type distance_0 = static_cast< distance_type >( distance_array( i - 1, j ) + distance * weight_0_ );
211 const distance_type distance_1 = static_cast< distance_type >( distance_array( i - 1, j - 1 ) + distance * weight_1_ );
212 const distance_type distance_2 = static_cast< distance_type >( distance_array( i, j - 1 ) + distance * weight_2_ );
213 path_array( i, j ) = ( distance_0 < distance_1 ) ? ( ( distance_0 < distance_2 ) ? 0 : 2 ) : ( ( distance_1 < distance_2 ) ? 1 : 2 );
214 switch( path_array( i, j ) )
215 {
216 case 0:
217 distance_array( i, j ) = distance_0;
218 break;
219 case 1:
220 distance_array( i, j ) = distance_1;
221 break;
222 case 2:
223 distance_array( i, j ) = distance_2;
224 break;
225 default:
226 break;
227 }
228 }
229 }
230 distance_ = distance_array( distance_array.width( ) - 1, distance_array.height( ) - 1 );
231 std::vector< dp_pair > path;
232 path.reserve( pattern_a_.size( ) );
233 size_t mi = pattern_a_.size( ) - 1;
234 size_t mj = pattern_b_.size( ) - 1;
235 path.push_back( dp_pair( mi, mj ) );
236 while( dp_pair( mi, mj ) != dp_pair( 0, 0 ) )
237 {
238 switch( path_array( mi, mj ) )
239 {
240 case 0:
241 path.push_back( dp_pair( -- mi, mj ) );
242 break;
243 case 1:
244 path.push_back( dp_pair( -- mi, -- mj ) );
245 break;
246 case 2:
247 path.push_back( dp_pair( mi, -- mj ) );
248 break;
249 default:
250 break;
251 }
252 }
253 path_.resize( path.size( ) );
254 for( size_t i = 0 ; i < path_.size( ) ; i ++ )
255 {
256 path_[ i ] = path[ path_.size( ) - 1 - i ];
257 }
258 }
259
260 public:
261
271 dp_matching( const mist::array< Value_type > &pattern_a, const mist::array< Value_type > &pattern_b, const double weight_0, const double weight_1, const double weight_2, const Functor func = __dp__::square_error< Value_type >( ) )
272 : pattern_a_( pattern_a ), pattern_b_( pattern_b ), weight_0_( weight_0 ), weight_1_( weight_1 ), weight_2_( weight_2 ), func_( func )
273 {
274 __find_path( );
275 }
276
283 void weights( const double weight_0, const double weight_1, const double weight_2 )
284 {
285 weight_0_ = weight_0;
286 weight_1_ = weight_1;
287 weight_2_ = weight_2;
288 __find_path( );
289 }
290
295 const mist::array< dp_pair > &path( ) const
296 {
297 return path_;
298 }
299
304 size_t length( ) const
305 {
306 return path_.size( );
307 }
308
313 distance_type distance( ) const
314 {
315 return distance_;
316 }
317 };
318
319
321 // DPマッチンググループの終わり
322
323
324 // mist名前空間の終わり
325 _MIST_END
326
327
328 #endif // __INCLUDE_DP_MATCHING_H__
329