1 // This file is part of OpenCV project.
2 // It is subject to the license terms in the LICENSE file found in the top-level directory
3 // of this distribution and at http://opencv.org/license.html
4
5 #include "precomp.hpp"
6 #include "opencv2/core/mat.hpp"
7 #include "opencv2/core/types_c.h"
8
9 namespace cv {
10
11 template<typename T1, typename T2> void
convertData_(const void * _from,void * _to,int cn)12 convertData_(const void* _from, void* _to, int cn)
13 {
14 const T1* from = (const T1*)_from;
15 T2* to = (T2*)_to;
16 if( cn == 1 )
17 *to = saturate_cast<T2>(*from);
18 else
19 for( int i = 0; i < cn; i++ )
20 to[i] = saturate_cast<T2>(from[i]);
21 }
22
23 template<typename T1, typename T2> void
convertScaleData_(const void * _from,void * _to,int cn,double alpha,double beta)24 convertScaleData_(const void* _from, void* _to, int cn, double alpha, double beta)
25 {
26 const T1* from = (const T1*)_from;
27 T2* to = (T2*)_to;
28 if( cn == 1 )
29 *to = saturate_cast<T2>(*from*alpha + beta);
30 else
31 for( int i = 0; i < cn; i++ )
32 to[i] = saturate_cast<T2>(from[i]*alpha + beta);
33 }
34
35 typedef void (*ConvertData)(const void* from, void* to, int cn);
36 typedef void (*ConvertScaleData)(const void* from, void* to, int cn, double alpha, double beta);
37
getConvertElem(int fromType,int toType)38 static ConvertData getConvertElem(int fromType, int toType)
39 {
40 static ConvertData tab[][8] =
41 {{ convertData_<uchar, uchar>, convertData_<uchar, schar>,
42 convertData_<uchar, ushort>, convertData_<uchar, short>,
43 convertData_<uchar, int>, convertData_<uchar, float>,
44 convertData_<uchar, double>, 0 },
45
46 { convertData_<schar, uchar>, convertData_<schar, schar>,
47 convertData_<schar, ushort>, convertData_<schar, short>,
48 convertData_<schar, int>, convertData_<schar, float>,
49 convertData_<schar, double>, 0 },
50
51 { convertData_<ushort, uchar>, convertData_<ushort, schar>,
52 convertData_<ushort, ushort>, convertData_<ushort, short>,
53 convertData_<ushort, int>, convertData_<ushort, float>,
54 convertData_<ushort, double>, 0 },
55
56 { convertData_<short, uchar>, convertData_<short, schar>,
57 convertData_<short, ushort>, convertData_<short, short>,
58 convertData_<short, int>, convertData_<short, float>,
59 convertData_<short, double>, 0 },
60
61 { convertData_<int, uchar>, convertData_<int, schar>,
62 convertData_<int, ushort>, convertData_<int, short>,
63 convertData_<int, int>, convertData_<int, float>,
64 convertData_<int, double>, 0 },
65
66 { convertData_<float, uchar>, convertData_<float, schar>,
67 convertData_<float, ushort>, convertData_<float, short>,
68 convertData_<float, int>, convertData_<float, float>,
69 convertData_<float, double>, 0 },
70
71 { convertData_<double, uchar>, convertData_<double, schar>,
72 convertData_<double, ushort>, convertData_<double, short>,
73 convertData_<double, int>, convertData_<double, float>,
74 convertData_<double, double>, 0 },
75
76 { 0, 0, 0, 0, 0, 0, 0, 0 }};
77
78 ConvertData func = tab[CV_MAT_DEPTH(fromType)][CV_MAT_DEPTH(toType)];
79 CV_Assert( func != 0 );
80 return func;
81 }
82
getConvertScaleElem(int fromType,int toType)83 static ConvertScaleData getConvertScaleElem(int fromType, int toType)
84 {
85 static ConvertScaleData tab[][8] =
86 {{ convertScaleData_<uchar, uchar>, convertScaleData_<uchar, schar>,
87 convertScaleData_<uchar, ushort>, convertScaleData_<uchar, short>,
88 convertScaleData_<uchar, int>, convertScaleData_<uchar, float>,
89 convertScaleData_<uchar, double>, 0 },
90
91 { convertScaleData_<schar, uchar>, convertScaleData_<schar, schar>,
92 convertScaleData_<schar, ushort>, convertScaleData_<schar, short>,
93 convertScaleData_<schar, int>, convertScaleData_<schar, float>,
94 convertScaleData_<schar, double>, 0 },
95
96 { convertScaleData_<ushort, uchar>, convertScaleData_<ushort, schar>,
97 convertScaleData_<ushort, ushort>, convertScaleData_<ushort, short>,
98 convertScaleData_<ushort, int>, convertScaleData_<ushort, float>,
99 convertScaleData_<ushort, double>, 0 },
100
101 { convertScaleData_<short, uchar>, convertScaleData_<short, schar>,
102 convertScaleData_<short, ushort>, convertScaleData_<short, short>,
103 convertScaleData_<short, int>, convertScaleData_<short, float>,
104 convertScaleData_<short, double>, 0 },
105
106 { convertScaleData_<int, uchar>, convertScaleData_<int, schar>,
107 convertScaleData_<int, ushort>, convertScaleData_<int, short>,
108 convertScaleData_<int, int>, convertScaleData_<int, float>,
109 convertScaleData_<int, double>, 0 },
110
111 { convertScaleData_<float, uchar>, convertScaleData_<float, schar>,
112 convertScaleData_<float, ushort>, convertScaleData_<float, short>,
113 convertScaleData_<float, int>, convertScaleData_<float, float>,
114 convertScaleData_<float, double>, 0 },
115
116 { convertScaleData_<double, uchar>, convertScaleData_<double, schar>,
117 convertScaleData_<double, ushort>, convertScaleData_<double, short>,
118 convertScaleData_<double, int>, convertScaleData_<double, float>,
119 convertScaleData_<double, double>, 0 },
120
121 { 0, 0, 0, 0, 0, 0, 0, 0 }};
122
123 ConvertScaleData func = tab[CV_MAT_DEPTH(fromType)][CV_MAT_DEPTH(toType)];
124 CV_Assert( func != 0 );
125 return func;
126 }
127
128 enum { HASH_SIZE0 = 8 };
129
copyElem(const uchar * from,uchar * to,size_t elemSize)130 static inline void copyElem(const uchar* from, uchar* to, size_t elemSize)
131 {
132 size_t i;
133 for( i = 0; i + sizeof(int) <= elemSize; i += sizeof(int) )
134 *(int*)(to + i) = *(const int*)(from + i);
135 for( ; i < elemSize; i++ )
136 to[i] = from[i];
137 }
138
isZeroElem(const uchar * data,size_t elemSize)139 static inline bool isZeroElem(const uchar* data, size_t elemSize)
140 {
141 size_t i;
142 for( i = 0; i + sizeof(int) <= elemSize; i += sizeof(int) )
143 if( *(int*)(data + i) != 0 )
144 return false;
145 for( ; i < elemSize; i++ )
146 if( data[i] != 0 )
147 return false;
148 return true;
149 }
150
Hdr(int _dims,const int * _sizes,int _type)151 SparseMat::Hdr::Hdr( int _dims, const int* _sizes, int _type )
152 {
153 refcount = 1;
154
155 dims = _dims;
156 valueOffset = (int)alignSize(sizeof(SparseMat::Node) - MAX_DIM*sizeof(int) +
157 dims*sizeof(int), CV_ELEM_SIZE1(_type));
158 nodeSize = alignSize(valueOffset +
159 CV_ELEM_SIZE(_type), (int)sizeof(size_t));
160
161 int i;
162 for( i = 0; i < dims; i++ )
163 size[i] = _sizes[i];
164 for( ; i < CV_MAX_DIM; i++ )
165 size[i] = 0;
166 clear();
167 }
168
clear()169 void SparseMat::Hdr::clear()
170 {
171 hashtab.clear();
172 hashtab.resize(HASH_SIZE0);
173 pool.clear();
174 pool.resize(nodeSize);
175 nodeCount = freeList = 0;
176 }
177
178 ///////////////////////////// SparseMat /////////////////////////////
179
SparseMat()180 SparseMat::SparseMat()
181 : flags(MAGIC_VAL), hdr(0)
182 {}
183
SparseMat(int _dims,const int * _sizes,int _type)184 SparseMat::SparseMat(int _dims, const int* _sizes, int _type)
185 : flags(MAGIC_VAL), hdr(0)
186 {
187 create(_dims, _sizes, _type);
188 }
189
SparseMat(const SparseMat & m)190 SparseMat::SparseMat(const SparseMat& m)
191 : flags(m.flags), hdr(m.hdr)
192 {
193 addref();
194 }
195
~SparseMat()196 SparseMat::~SparseMat()
197 {
198 release();
199 }
200
operator =(const SparseMat & m)201 SparseMat& SparseMat::operator = (const SparseMat& m)
202 {
203 if( this != &m )
204 {
205 if( m.hdr )
206 CV_XADD(&m.hdr->refcount, 1);
207 release();
208 flags = m.flags;
209 hdr = m.hdr;
210 }
211 return *this;
212 }
213
operator =(const Mat & m)214 SparseMat& SparseMat::operator=(const Mat& m)
215 {
216 return (*this = SparseMat(m));
217 }
218
assignTo(SparseMat & m,int _type) const219 void SparseMat::assignTo(SparseMat& m, int _type) const
220 {
221 if( _type < 0 )
222 m = *this;
223 else
224 convertTo(m, _type);
225 }
226
addref()227 void SparseMat::addref()
228 {
229 if( hdr )
230 CV_XADD(&hdr->refcount, 1);
231 }
232
release()233 void SparseMat::release()
234 {
235 if( hdr && CV_XADD(&hdr->refcount, -1) == 1 )
236 delete hdr;
237 hdr = 0;
238 }
239
hash(int i0) const240 size_t SparseMat::hash(int i0) const
241 {
242 return (size_t)i0;
243 }
244
hash(int i0,int i1) const245 size_t SparseMat::hash(int i0, int i1) const
246 {
247 return (size_t)(unsigned)i0 * HASH_SCALE + (unsigned)i1;
248 }
249
hash(int i0,int i1,int i2) const250 size_t SparseMat::hash(int i0, int i1, int i2) const
251 {
252 return ((size_t)(unsigned)i0 * HASH_SCALE + (unsigned)i1) * HASH_SCALE + (unsigned)i2;
253 }
254
hash(const int * idx) const255 size_t SparseMat::hash(const int* idx) const
256 {
257 size_t h = (unsigned)idx[0];
258 if( !hdr )
259 return 0;
260 int d = hdr->dims;
261 for(int i = 1; i < d; i++ )
262 h = h * HASH_SCALE + (unsigned)idx[i];
263 return h;
264 }
265
266
SparseMat(const Mat & m)267 SparseMat::SparseMat(const Mat& m)
268 : flags(MAGIC_VAL), hdr(0)
269 {
270 create( m.dims, m.size, m.type() );
271
272 int i, idx[CV_MAX_DIM] = {0}, d = m.dims, lastSize = m.size[d - 1];
273 size_t esz = m.elemSize();
274 const uchar* dptr = m.ptr();
275
276 for(;;)
277 {
278 for( i = 0; i < lastSize; i++, dptr += esz )
279 {
280 if( isZeroElem(dptr, esz) )
281 continue;
282 idx[d-1] = i;
283 uchar* to = newNode(idx, hash(idx));
284 copyElem( dptr, to, esz );
285 }
286
287 for( i = d - 2; i >= 0; i-- )
288 {
289 dptr += m.step[i] - m.size[i+1]*m.step[i+1];
290 if( ++idx[i] < m.size[i] )
291 break;
292 idx[i] = 0;
293 }
294 if( i < 0 )
295 break;
296 }
297 }
298
create(int d,const int * _sizes,int _type)299 void SparseMat::create(int d, const int* _sizes, int _type)
300 {
301 CV_Assert( _sizes && 0 < d && d <= CV_MAX_DIM );
302 for( int i = 0; i < d; i++ )
303 CV_Assert( _sizes[i] > 0 );
304 _type = CV_MAT_TYPE(_type);
305 if( hdr && _type == type() && hdr->dims == d && hdr->refcount == 1 )
306 {
307 int i;
308 for( i = 0; i < d; i++ )
309 if( _sizes[i] != hdr->size[i] )
310 break;
311 if( i == d )
312 {
313 clear();
314 return;
315 }
316 }
317 int _sizes_backup[CV_MAX_DIM]; // #5991
318 if (hdr && _sizes == hdr->size)
319 {
320 for(int i = 0; i < d; i++ )
321 _sizes_backup[i] = _sizes[i];
322 _sizes = _sizes_backup;
323 }
324 release();
325 flags = MAGIC_VAL | _type;
326 hdr = new Hdr(d, _sizes, _type);
327 }
328
copyTo(SparseMat & m) const329 void SparseMat::copyTo( SparseMat& m ) const
330 {
331 if( hdr == m.hdr )
332 return;
333 if( !hdr )
334 {
335 m.release();
336 return;
337 }
338 m.create( hdr->dims, hdr->size, type() );
339 SparseMatConstIterator from = begin();
340 size_t N = nzcount(), esz = elemSize();
341
342 for( size_t i = 0; i < N; i++, ++from )
343 {
344 const Node* n = from.node();
345 uchar* to = m.newNode(n->idx, n->hashval);
346 copyElem( from.ptr, to, esz );
347 }
348 }
349
copyTo(Mat & m) const350 void SparseMat::copyTo( Mat& m ) const
351 {
352 CV_Assert( hdr );
353 int ndims = dims();
354 m.create( ndims, hdr->size, type() );
355 m = Scalar(0);
356
357 SparseMatConstIterator from = begin();
358 size_t N = nzcount(), esz = elemSize();
359
360 for( size_t i = 0; i < N; i++, ++from )
361 {
362 const Node* n = from.node();
363 copyElem( from.ptr, (ndims > 1 ? m.ptr(n->idx) : m.ptr(n->idx[0])), esz);
364 }
365 }
366
367
convertTo(SparseMat & m,int rtype,double alpha) const368 void SparseMat::convertTo( SparseMat& m, int rtype, double alpha ) const
369 {
370 int cn = channels();
371 if( rtype < 0 )
372 rtype = type();
373 rtype = CV_MAKETYPE(rtype, cn);
374 if( hdr == m.hdr && rtype != type() )
375 {
376 SparseMat temp;
377 convertTo(temp, rtype, alpha);
378 m = temp;
379 return;
380 }
381
382 CV_Assert(hdr != 0);
383 if( hdr != m.hdr )
384 m.create( hdr->dims, hdr->size, rtype );
385
386 SparseMatConstIterator from = begin();
387 size_t N = nzcount();
388
389 if( alpha == 1 )
390 {
391 ConvertData cvtfunc = getConvertElem(type(), rtype);
392 for( size_t i = 0; i < N; i++, ++from )
393 {
394 const Node* n = from.node();
395 uchar* to = hdr == m.hdr ? from.ptr : m.newNode(n->idx, n->hashval);
396 cvtfunc( from.ptr, to, cn );
397 }
398 }
399 else
400 {
401 ConvertScaleData cvtfunc = getConvertScaleElem(type(), rtype);
402 for( size_t i = 0; i < N; i++, ++from )
403 {
404 const Node* n = from.node();
405 uchar* to = hdr == m.hdr ? from.ptr : m.newNode(n->idx, n->hashval);
406 cvtfunc( from.ptr, to, cn, alpha, 0 );
407 }
408 }
409 }
410
411
convertTo(Mat & m,int rtype,double alpha,double beta) const412 void SparseMat::convertTo( Mat& m, int rtype, double alpha, double beta ) const
413 {
414 int cn = channels();
415 if( rtype < 0 )
416 rtype = type();
417 rtype = CV_MAKETYPE(rtype, cn);
418
419 CV_Assert( hdr );
420 m.create( dims(), hdr->size, rtype );
421 m = Scalar(beta);
422
423 SparseMatConstIterator from = begin();
424 size_t N = nzcount();
425
426 if( alpha == 1 && beta == 0 )
427 {
428 ConvertData cvtfunc = getConvertElem(type(), rtype);
429 for( size_t i = 0; i < N; i++, ++from )
430 {
431 const Node* n = from.node();
432 uchar* to = m.ptr(n->idx);
433 cvtfunc( from.ptr, to, cn );
434 }
435 }
436 else
437 {
438 ConvertScaleData cvtfunc = getConvertScaleElem(type(), rtype);
439 for( size_t i = 0; i < N; i++, ++from )
440 {
441 const Node* n = from.node();
442 uchar* to = m.ptr(n->idx);
443 cvtfunc( from.ptr, to, cn, alpha, beta );
444 }
445 }
446 }
447
clear()448 void SparseMat::clear()
449 {
450 if( hdr )
451 hdr->clear();
452 }
453
ptr(int i0,bool createMissing,size_t * hashval)454 uchar* SparseMat::ptr(int i0, bool createMissing, size_t* hashval)
455 {
456 CV_Assert( hdr && hdr->dims == 1 );
457 size_t h = hashval ? *hashval : hash(i0);
458 size_t hidx = h & (hdr->hashtab.size() - 1), nidx = hdr->hashtab[hidx];
459 uchar* pool = &hdr->pool[0];
460 while( nidx != 0 )
461 {
462 Node* elem = (Node*)(pool + nidx);
463 if( elem->hashval == h && elem->idx[0] == i0 )
464 return &value<uchar>(elem);
465 nidx = elem->next;
466 }
467
468 if( createMissing )
469 {
470 int idx[] = { i0 };
471 return newNode( idx, h );
472 }
473 return NULL;
474 }
475
ptr(int i0,int i1,bool createMissing,size_t * hashval)476 uchar* SparseMat::ptr(int i0, int i1, bool createMissing, size_t* hashval)
477 {
478 CV_Assert( hdr && hdr->dims == 2 );
479 size_t h = hashval ? *hashval : hash(i0, i1);
480 size_t hidx = h & (hdr->hashtab.size() - 1), nidx = hdr->hashtab[hidx];
481 uchar* pool = &hdr->pool[0];
482 while( nidx != 0 )
483 {
484 Node* elem = (Node*)(pool + nidx);
485 if( elem->hashval == h && elem->idx[0] == i0 && elem->idx[1] == i1 )
486 return &value<uchar>(elem);
487 nidx = elem->next;
488 }
489
490 if( createMissing )
491 {
492 int idx[] = { i0, i1 };
493 return newNode( idx, h );
494 }
495 return NULL;
496 }
497
ptr(int i0,int i1,int i2,bool createMissing,size_t * hashval)498 uchar* SparseMat::ptr(int i0, int i1, int i2, bool createMissing, size_t* hashval)
499 {
500 CV_Assert( hdr && hdr->dims == 3 );
501 size_t h = hashval ? *hashval : hash(i0, i1, i2);
502 size_t hidx = h & (hdr->hashtab.size() - 1), nidx = hdr->hashtab[hidx];
503 uchar* pool = &hdr->pool[0];
504 while( nidx != 0 )
505 {
506 Node* elem = (Node*)(pool + nidx);
507 if( elem->hashval == h && elem->idx[0] == i0 &&
508 elem->idx[1] == i1 && elem->idx[2] == i2 )
509 return &value<uchar>(elem);
510 nidx = elem->next;
511 }
512
513 if( createMissing )
514 {
515 int idx[] = { i0, i1, i2 };
516 return newNode( idx, h );
517 }
518 return NULL;
519 }
520
ptr(const int * idx,bool createMissing,size_t * hashval)521 uchar* SparseMat::ptr(const int* idx, bool createMissing, size_t* hashval)
522 {
523 CV_Assert( hdr );
524 int i, d = hdr->dims;
525 size_t h = hashval ? *hashval : hash(idx);
526 size_t hidx = h & (hdr->hashtab.size() - 1), nidx = hdr->hashtab[hidx];
527 uchar* pool = &hdr->pool[0];
528 while( nidx != 0 )
529 {
530 Node* elem = (Node*)(pool + nidx);
531 if( elem->hashval == h )
532 {
533 for( i = 0; i < d; i++ )
534 if( elem->idx[i] != idx[i] )
535 break;
536 if( i == d )
537 return &value<uchar>(elem);
538 }
539 nidx = elem->next;
540 }
541
542 return createMissing ? newNode(idx, h) : NULL;
543 }
544
erase(int i0,int i1,size_t * hashval)545 void SparseMat::erase(int i0, int i1, size_t* hashval)
546 {
547 CV_Assert( hdr && hdr->dims == 2 );
548 size_t h = hashval ? *hashval : hash(i0, i1);
549 size_t hidx = h & (hdr->hashtab.size() - 1), nidx = hdr->hashtab[hidx], previdx=0;
550 uchar* pool = &hdr->pool[0];
551 while( nidx != 0 )
552 {
553 Node* elem = (Node*)(pool + nidx);
554 if( elem->hashval == h && elem->idx[0] == i0 && elem->idx[1] == i1 )
555 break;
556 previdx = nidx;
557 nidx = elem->next;
558 }
559
560 if( nidx )
561 removeNode(hidx, nidx, previdx);
562 }
563
erase(int i0,int i1,int i2,size_t * hashval)564 void SparseMat::erase(int i0, int i1, int i2, size_t* hashval)
565 {
566 CV_Assert( hdr && hdr->dims == 3 );
567 size_t h = hashval ? *hashval : hash(i0, i1, i2);
568 size_t hidx = h & (hdr->hashtab.size() - 1), nidx = hdr->hashtab[hidx], previdx=0;
569 uchar* pool = &hdr->pool[0];
570 while( nidx != 0 )
571 {
572 Node* elem = (Node*)(pool + nidx);
573 if( elem->hashval == h && elem->idx[0] == i0 &&
574 elem->idx[1] == i1 && elem->idx[2] == i2 )
575 break;
576 previdx = nidx;
577 nidx = elem->next;
578 }
579
580 if( nidx )
581 removeNode(hidx, nidx, previdx);
582 }
583
erase(const int * idx,size_t * hashval)584 void SparseMat::erase(const int* idx, size_t* hashval)
585 {
586 CV_Assert( hdr );
587 int i, d = hdr->dims;
588 size_t h = hashval ? *hashval : hash(idx);
589 size_t hidx = h & (hdr->hashtab.size() - 1), nidx = hdr->hashtab[hidx], previdx=0;
590 uchar* pool = &hdr->pool[0];
591 while( nidx != 0 )
592 {
593 Node* elem = (Node*)(pool + nidx);
594 if( elem->hashval == h )
595 {
596 for( i = 0; i < d; i++ )
597 if( elem->idx[i] != idx[i] )
598 break;
599 if( i == d )
600 break;
601 }
602 previdx = nidx;
603 nidx = elem->next;
604 }
605
606 if( nidx )
607 removeNode(hidx, nidx, previdx);
608 }
609
resizeHashTab(size_t newsize)610 void SparseMat::resizeHashTab(size_t newsize)
611 {
612 newsize = std::max(newsize, (size_t)8);
613 if((newsize & (newsize-1)) != 0)
614 newsize = (size_t)1 << cvCeil(std::log((double)newsize)/CV_LOG2);
615
616 size_t hsize = hdr->hashtab.size();
617 std::vector<size_t> _newh(newsize);
618 size_t* newh = &_newh[0];
619 for( size_t i = 0; i < newsize; i++ )
620 newh[i] = 0;
621 uchar* pool = &hdr->pool[0];
622 for( size_t i = 0; i < hsize; i++ )
623 {
624 size_t nidx = hdr->hashtab[i];
625 while( nidx )
626 {
627 Node* elem = (Node*)(pool + nidx);
628 size_t next = elem->next;
629 size_t newhidx = elem->hashval & (newsize - 1);
630 elem->next = newh[newhidx];
631 newh[newhidx] = nidx;
632 nidx = next;
633 }
634 }
635 hdr->hashtab = _newh;
636 }
637
newNode(const int * idx,size_t hashval)638 uchar* SparseMat::newNode(const int* idx, size_t hashval)
639 {
640 const int HASH_MAX_FILL_FACTOR=3;
641 assert(hdr);
642 size_t hsize = hdr->hashtab.size();
643 if( ++hdr->nodeCount > hsize*HASH_MAX_FILL_FACTOR )
644 {
645 resizeHashTab(std::max(hsize*2, (size_t)8));
646 hsize = hdr->hashtab.size();
647 }
648
649 if( !hdr->freeList )
650 {
651 size_t i, nsz = hdr->nodeSize, psize = hdr->pool.size(),
652 newpsize = std::max(psize*3/2, 8*nsz);
653 newpsize = (newpsize/nsz)*nsz;
654 hdr->pool.resize(newpsize);
655 uchar* pool = &hdr->pool[0];
656 hdr->freeList = std::max(psize, nsz);
657 for( i = hdr->freeList; i < newpsize - nsz; i += nsz )
658 ((Node*)(pool + i))->next = i + nsz;
659 ((Node*)(pool + i))->next = 0;
660 }
661 size_t nidx = hdr->freeList;
662 Node* elem = (Node*)&hdr->pool[nidx];
663 hdr->freeList = elem->next;
664 elem->hashval = hashval;
665 size_t hidx = hashval & (hsize - 1);
666 elem->next = hdr->hashtab[hidx];
667 hdr->hashtab[hidx] = nidx;
668
669 int i, d = hdr->dims;
670 for( i = 0; i < d; i++ )
671 elem->idx[i] = idx[i];
672 size_t esz = elemSize();
673 uchar* p = &value<uchar>(elem);
674 if( esz == sizeof(float) )
675 *((float*)p) = 0.f;
676 else if( esz == sizeof(double) )
677 *((double*)p) = 0.;
678 else
679 memset(p, 0, esz);
680
681 return p;
682 }
683
684
removeNode(size_t hidx,size_t nidx,size_t previdx)685 void SparseMat::removeNode(size_t hidx, size_t nidx, size_t previdx)
686 {
687 Node* n = node(nidx);
688 if( previdx )
689 {
690 Node* prev = node(previdx);
691 prev->next = n->next;
692 }
693 else
694 hdr->hashtab[hidx] = n->next;
695 n->next = hdr->freeList;
696 hdr->freeList = nidx;
697 --hdr->nodeCount;
698 }
699
700 //
701 // Operations
702 //
norm(const SparseMat & src,int normType)703 double norm( const SparseMat& src, int normType )
704 {
705 CV_INSTRUMENT_REGION();
706
707 SparseMatConstIterator it = src.begin();
708
709 size_t i, N = src.nzcount();
710 normType &= NORM_TYPE_MASK;
711 int type = src.type();
712 double result = 0;
713
714 CV_Assert( normType == NORM_INF || normType == NORM_L1 || normType == NORM_L2 );
715
716 if( type == CV_32F )
717 {
718 if( normType == NORM_INF )
719 for( i = 0; i < N; i++, ++it )
720 {
721 CV_Assert(it.ptr);
722 result = std::max(result, std::abs((double)it.value<float>()));
723 }
724 else if( normType == NORM_L1 )
725 for( i = 0; i < N; i++, ++it )
726 {
727 CV_Assert(it.ptr);
728 result += std::abs(it.value<float>());
729 }
730 else
731 for( i = 0; i < N; i++, ++it )
732 {
733 CV_Assert(it.ptr);
734 double v = it.value<float>();
735 result += v*v;
736 }
737 }
738 else if( type == CV_64F )
739 {
740 if( normType == NORM_INF )
741 for( i = 0; i < N; i++, ++it )
742 {
743 CV_Assert(it.ptr);
744 result = std::max(result, std::abs(it.value<double>()));
745 }
746 else if( normType == NORM_L1 )
747 for( i = 0; i < N; i++, ++it )
748 {
749 CV_Assert(it.ptr);
750 result += std::abs(it.value<double>());
751 }
752 else
753 for( i = 0; i < N; i++, ++it )
754 {
755 CV_Assert(it.ptr);
756 double v = it.value<double>();
757 result += v*v;
758 }
759 }
760 else
761 CV_Error( CV_StsUnsupportedFormat, "Only 32f and 64f are supported" );
762
763 if( normType == NORM_L2 )
764 result = std::sqrt(result);
765 return result;
766 }
767
minMaxLoc(const SparseMat & src,double * _minval,double * _maxval,int * _minidx,int * _maxidx)768 void minMaxLoc( const SparseMat& src, double* _minval, double* _maxval, int* _minidx, int* _maxidx )
769 {
770 CV_INSTRUMENT_REGION();
771
772 SparseMatConstIterator it = src.begin();
773 size_t i, N = src.nzcount(), d = src.hdr ? src.hdr->dims : 0;
774 int type = src.type();
775 const int *minidx = 0, *maxidx = 0;
776
777 if( type == CV_32F )
778 {
779 float minval = FLT_MAX, maxval = -FLT_MAX;
780 for( i = 0; i < N; i++, ++it )
781 {
782 CV_Assert(it.ptr);
783 float v = it.value<float>();
784 if( v < minval )
785 {
786 minval = v;
787 minidx = it.node()->idx;
788 }
789 if( v > maxval )
790 {
791 maxval = v;
792 maxidx = it.node()->idx;
793 }
794 }
795 if( _minval )
796 *_minval = minval;
797 if( _maxval )
798 *_maxval = maxval;
799 }
800 else if( type == CV_64F )
801 {
802 double minval = DBL_MAX, maxval = -DBL_MAX;
803 for( i = 0; i < N; i++, ++it )
804 {
805 CV_Assert(it.ptr);
806 double v = it.value<double>();
807 if( v < minval )
808 {
809 minval = v;
810 minidx = it.node()->idx;
811 }
812 if( v > maxval )
813 {
814 maxval = v;
815 maxidx = it.node()->idx;
816 }
817 }
818 if( _minval )
819 *_minval = minval;
820 if( _maxval )
821 *_maxval = maxval;
822 }
823 else
824 CV_Error( CV_StsUnsupportedFormat, "Only 32f and 64f are supported" );
825
826 if( _minidx && minidx )
827 for( i = 0; i < d; i++ )
828 _minidx[i] = minidx[i];
829 if( _maxidx && maxidx )
830 for( i = 0; i < d; i++ )
831 _maxidx[i] = maxidx[i];
832 }
833
834
normalize(const SparseMat & src,SparseMat & dst,double a,int norm_type)835 void normalize( const SparseMat& src, SparseMat& dst, double a, int norm_type )
836 {
837 CV_INSTRUMENT_REGION();
838
839 double scale = 1;
840 if( norm_type == CV_L2 || norm_type == CV_L1 || norm_type == CV_C )
841 {
842 scale = norm( src, norm_type );
843 scale = scale > DBL_EPSILON ? a/scale : 0.;
844 }
845 else
846 CV_Error( CV_StsBadArg, "Unknown/unsupported norm type" );
847
848 src.convertTo( dst, -1, scale );
849 }
850
851 } // cv::
852
853 //
854 // C-API glue
855 //
cvCreateSparseMat(const cv::SparseMat & sm)856 CvSparseMat* cvCreateSparseMat(const cv::SparseMat& sm)
857 {
858 if( !sm.hdr || sm.hdr->dims > (int)cv::SparseMat::MAX_DIM)
859 return 0;
860
861 CvSparseMat* m = cvCreateSparseMat(sm.hdr->dims, sm.hdr->size, sm.type());
862
863 cv::SparseMatConstIterator from = sm.begin();
864 size_t i, N = sm.nzcount(), esz = sm.elemSize();
865
866 for( i = 0; i < N; i++, ++from )
867 {
868 const cv::SparseMat::Node* n = from.node();
869 uchar* to = cvPtrND(m, n->idx, 0, -2, 0);
870 cv::copyElem(from.ptr, to, esz);
871 }
872 return m;
873 }
874
copyToSparseMat(cv::SparseMat & m) const875 void CvSparseMat::copyToSparseMat(cv::SparseMat& m) const
876 {
877 m.create( dims, &size[0], type );
878
879 CvSparseMatIterator it;
880 CvSparseNode* n = cvInitSparseMatIterator(this, &it);
881 size_t esz = m.elemSize();
882
883 for( ; n != 0; n = cvGetNextSparseNode(&it) )
884 {
885 const int* idx = CV_NODE_IDX(this, n);
886 uchar* to = m.newNode(idx, m.hash(idx));
887 cv::copyElem((const uchar*)CV_NODE_VAL(this, n), to, esz);
888 }
889 }
890