Leptonica  1.82.0
Image processing and image analysis suite
dnafunc1.c
Go to the documentation of this file.
1 /*====================================================================*
2  - Copyright (C) 2001 Leptonica. All rights reserved.
3  -
4  - Redistribution and use in source and binary forms, with or without
5  - modification, are permitted provided that the following conditions
6  - are met:
7  - 1. Redistributions of source code must retain the above copyright
8  - notice, this list of conditions and the following disclaimer.
9  - 2. Redistributions in binary form must reproduce the above
10  - copyright notice, this list of conditions and the following
11  - disclaimer in the documentation and/or other materials
12  - provided with the distribution.
13  -
14  - THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
15  - ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
16  - LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
17  - A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL ANY
18  - CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
19  - EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
20  - PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
21  - PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
22  - OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
23  - NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
24  - SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
25  *====================================================================*/
26 
77 #ifdef HAVE_CONFIG_H
78 #include <config_auto.h>
79 #endif /* HAVE_CONFIG_H */
80 
81 #include "allheaders.h"
82 
83 /*----------------------------------------------------------------------*
84  * Rearrangements *
85  *----------------------------------------------------------------------*/
102 l_ok
104  L_DNA *das,
105  l_int32 istart,
106  l_int32 iend)
107 {
108 l_int32 n, i;
109 l_float64 val;
110 
111  PROCNAME("l_dnaJoin");
112 
113  if (!dad)
114  return ERROR_INT("dad not defined", procName, 1);
115  if (!das)
116  return 0;
117 
118  if (istart < 0)
119  istart = 0;
120  n = l_dnaGetCount(das);
121  if (iend < 0 || iend >= n)
122  iend = n - 1;
123  if (istart > iend)
124  return ERROR_INT("istart > iend; nothing to add", procName, 1);
125 
126  for (i = istart; i <= iend; i++) {
127  l_dnaGetDValue(das, i, &val);
128  if (l_dnaAddNumber(dad, val) == 1) {
129  L_ERROR("failed to add double at i = %d\n", procName, i);
130  return 1;
131  }
132 
133  }
134  return 0;
135 }
136 
137 
151 L_DNA *
153 {
154 l_int32 i, nalloc;
155 L_DNA *da, *dad;
156 L_DNA **array;
157 
158  PROCNAME("l_dnaaFlattenToDna");
159 
160  if (!daa)
161  return (L_DNA *)ERROR_PTR("daa not defined", procName, NULL);
162 
163  nalloc = daa->nalloc;
164  array = daa->dna;
165  dad = l_dnaCreate(0);
166  for (i = 0; i < nalloc; i++) {
167  da = array[i];
168  if (!da) continue;
169  l_dnaJoin(dad, da, 0, -1);
170  }
171 
172  return dad;
173 }
174 
175 
184 L_DNA *
186  l_int32 first,
187  l_int32 last)
188 {
189 l_int32 n, i;
190 l_float64 dval;
191 L_DNA *dad;
192 
193  PROCNAME("l_dnaSelectRange");
194 
195  if (!das)
196  return (L_DNA *)ERROR_PTR("das not defined", procName, NULL);
197  if ((n = l_dnaGetCount(das)) == 0) {
198  L_WARNING("das is empty\n", procName);
199  return l_dnaCopy(das);
200  }
201  first = L_MAX(0, first);
202  if (last < 0) last = n - 1;
203  if (first >= n)
204  return (L_DNA *)ERROR_PTR("invalid first", procName, NULL);
205  if (last >= n) {
206  L_WARNING("last = %d is beyond max index = %d; adjusting\n",
207  procName, last, n - 1);
208  last = n - 1;
209  }
210  if (first > last)
211  return (L_DNA *)ERROR_PTR("first > last", procName, NULL);
212 
213  dad = l_dnaCreate(last - first + 1);
214  for (i = first; i <= last; i++) {
215  l_dnaGetDValue(das, i, &dval);
216  l_dnaAddNumber(dad, dval);
217  }
218  return dad;
219 }
220 
221 
222 /*----------------------------------------------------------------------*
223  * Conversion between numa and dna *
224  *----------------------------------------------------------------------*/
231 NUMA *
233 {
234 l_int32 i, n;
235 l_float64 val;
236 NUMA *na;
237 
238  PROCNAME("l_dnaConvertToNuma");
239 
240  if (!da)
241  return (NUMA *)ERROR_PTR("da not defined", procName, NULL);
242 
243  n = l_dnaGetCount(da);
244  na = numaCreate(n);
245  for (i = 0; i < n; i++) {
246  l_dnaGetDValue(da, i, &val);
247  numaAddNumber(na, val);
248  }
249  return na;
250 }
251 
252 
259 L_DNA *
261 {
262 l_int32 i, n;
263 l_float32 val;
264 L_DNA *da;
265 
266  PROCNAME("numaConvertToDna");
267 
268  if (!na)
269  return (L_DNA *)ERROR_PTR("na not defined", procName, NULL);
270 
271  n = numaGetCount(na);
272  da = l_dnaCreate(n);
273  for (i = 0; i < n; i++) {
274  numaGetFValue(na, i, &val);
275  l_dnaAddNumber(da, val);
276  }
277  return da;
278 }
279 
280 
281 /*----------------------------------------------------------------------*
282  * Conversion from pix data to dna *
283  *----------------------------------------------------------------------*/
295 L_DNA *
297 {
298 l_int32 i, j, w, h, wpl;
299 l_uint32 *data, *line;
300 L_DNA *da;
301 
302  PROCNAME("pixConvertDataToDna");
303 
304  if (!pix)
305  return (L_DNA *)ERROR_PTR("pix not defined", procName, NULL);
306  if (pixGetDepth(pix) != 32)
307  return (L_DNA *)ERROR_PTR("pix not 32 bpp", procName, NULL);
308 
309  pixGetDimensions(pix, &w, &h, NULL);
310  data = pixGetData(pix);
311  wpl = pixGetWpl(pix);
312  da = l_dnaCreate(w * h);
313  for (i = 0; i < h; i++) {
314  line = data + i * wpl;
315  for (j = 0; j < w; j++)
316  l_dnaAddNumber(da, (l_float64)line[j]);
317  }
318  return da;
319 }
320 
321 
322 /*----------------------------------------------------------------------*
323  * Set operations using aset (rbtree) *
324  *----------------------------------------------------------------------*/
331 L_ASET *
333 {
334 l_int32 i, n;
335 l_float64 val;
336 L_ASET *set;
337 RB_TYPE key;
338 
339  PROCNAME("l_asetCreateFromDna");
340 
341  if (!da)
342  return (L_ASET *)ERROR_PTR("da not defined", procName, NULL);
343 
344  set = l_asetCreate(L_FLOAT_TYPE);
345  n = l_dnaGetCount(da);
346  for (i = 0; i < n; i++) {
347  l_dnaGetDValue(da, i, &val);
348  key.ftype = val;
349  l_asetInsert(set, key);
350  }
351 
352  return set;
353 }
354 
355 
363 l_ok
365  L_DNA **pdad)
366 {
367 l_int32 i, n;
368 l_float64 val;
369 L_DNA *dad;
370 L_ASET *set;
371 RB_TYPE key;
372 
373  PROCNAME("l_dnaRemoveDupsByAset");
374 
375  if (!pdad)
376  return ERROR_INT("&dad not defined", procName, 1);
377  *pdad = NULL;
378  if (!das)
379  return ERROR_INT("das not defined", procName, 1);
380 
381  set = l_asetCreate(L_FLOAT_TYPE);
382  dad = l_dnaCreate(0);
383  *pdad = dad;
384  n = l_dnaGetCount(das);
385  for (i = 0; i < n; i++) {
386  l_dnaGetDValue(das, i, &val);
387  key.ftype = val;
388  if (!l_asetFind(set, key)) {
389  l_dnaAddNumber(dad, val);
390  l_asetInsert(set, key);
391  }
392  }
393 
394  l_asetDestroy(&set);
395  return 0;
396 }
397 
398 
415 l_ok
417  L_DNA *da2,
418  L_DNA **pdad)
419 {
420 L_DNA *da3;
421 
422  PROCNAME("l_dnaUnionByAset");
423 
424  if (!pdad)
425  return ERROR_INT("&dad not defined", procName, 1);
426  if (!da1)
427  return ERROR_INT("da1 not defined", procName, 1);
428  if (!da2)
429  return ERROR_INT("da2 not defined", procName, 1);
430 
431  /* Join */
432  da3 = l_dnaCopy(da1);
433  if (l_dnaJoin(da3, da2, 0, -1) == 1) {
434  l_dnaDestroy(&da3);
435  return ERROR_INT("join failed for da3", procName, 1);
436  }
437 
438  /* Eliminate duplicates */
439  l_dnaRemoveDupsByAset(da3, pdad);
440  l_dnaDestroy(&da3);
441  return 0;
442 }
443 
444 
461 l_ok
463  L_DNA *da2,
464  L_DNA **pdad)
465 {
466 l_int32 n1, n2, i, n;
467 l_float64 val;
468 L_ASET *set1, *set2;
469 RB_TYPE key;
470 L_DNA *da_small, *da_big, *dad;
471 
472  PROCNAME("l_dnaIntersectionByAset");
473 
474  if (!pdad)
475  return ERROR_INT("&dad not defined", procName, 1);
476  *pdad = NULL;
477  if (!da1)
478  return ERROR_INT("&da1 not defined", procName, 1);
479  if (!da2)
480  return ERROR_INT("&da2 not defined", procName, 1);
481 
482  /* Put the elements of the largest array into a set */
483  n1 = l_dnaGetCount(da1);
484  n2 = l_dnaGetCount(da2);
485  da_small = (n1 < n2) ? da1 : da2; /* do not destroy da_small */
486  da_big = (n1 < n2) ? da2 : da1; /* do not destroy da_big */
487  set1 = l_asetCreateFromDna(da_big);
488 
489  /* Build up the intersection of doubles */
490  dad = l_dnaCreate(0);
491  *pdad = dad;
492  n = l_dnaGetCount(da_small);
493  set2 = l_asetCreate(L_FLOAT_TYPE);
494  for (i = 0; i < n; i++) {
495  l_dnaGetDValue(da_small, i, &val);
496  key.ftype = val;
497  if (l_asetFind(set1, key) && !l_asetFind(set2, key)) {
498  l_dnaAddNumber(dad, val);
499  l_asetInsert(set2, key);
500  }
501  }
502 
503  l_asetDestroy(&set1);
504  l_asetDestroy(&set2);
505  return 0;
506 }
507 
508 
509 /*--------------------------------------------------------------------------*
510  * Hashmap operations *
511  *--------------------------------------------------------------------------*/
525 L_HASHMAP *
527 {
528 l_int32 i, n;
529 l_uint64 key;
530 l_float64 dval;
531 L_HASHITEM *hitem;
532 L_HASHMAP *hmap;
533 
534  PROCNAME("l_hmapCreateFromDna");
535 
536  if (!da)
537  return (L_HASHMAP *)ERROR_PTR("da not defined", procName, NULL);
538 
539  n = l_dnaGetCount(da);
540  hmap = l_hmapCreate(0, 0);
541  for (i = 0; i < n; i++) {
542  l_dnaGetDValue(da, i, &dval);
543  l_hashFloat64ToUint64(dval, &key);
544  hitem = l_hmapLookup(hmap, key, i, L_HMAP_CREATE);
545  }
546  return hmap;
547 }
548 
549 
564 l_ok
566  L_DNA **pdad,
567  L_HASHMAP **phmap)
568 {
569 l_int32 i, tabsize;
570 l_uint64 key;
571 l_float64 dval;
572 L_DNA *dad;
573 L_HASHITEM *hitem;
574 L_HASHMAP *hmap;
575 
576  PROCNAME("l_dnaRemoveDupsByHmap");
577 
578  if (phmap) *phmap = NULL;
579  if (!pdad)
580  return ERROR_INT("&dad not defined", procName, 1);
581  *pdad = NULL;
582  if (!das)
583  return ERROR_INT("das not defined", procName, 1);
584 
585  /* Traverse the hashtable lists */
586  if ((hmap = l_hmapCreateFromDna(das)) == NULL)
587  return ERROR_INT("hmap not made", procName, 1);
588  dad = l_dnaCreate(0);
589  *pdad = dad;
590  tabsize = hmap->tabsize;
591  for (i = 0; i < tabsize; i++) {
592  hitem = hmap->hashtab[i];
593  while (hitem) {
594  l_dnaGetDValue(das, hitem->val, &dval);
595  l_dnaAddNumber(dad, dval);
596  hitem = hitem->next;
597  }
598  }
599 
600  if (phmap)
601  *phmap = hmap;
602  else
603  l_hmapDestroy(&hmap);
604  return 0;
605 }
606 
607 
621 l_ok
623  L_DNA *da2,
624  L_DNA **pdad)
625 {
626 L_DNA *da3;
627 
628  PROCNAME("l_dnaUnionByHmap");
629 
630  if (!pdad)
631  return ERROR_INT("&dad not defined", procName, 1);
632  *pdad = NULL;
633  if (!da1)
634  return ERROR_INT("da1 not defined", procName, 1);
635  if (!da2)
636  return ERROR_INT("da2 not defined", procName, 1);
637 
638  da3 = l_dnaCopy(da1);
639  if (l_dnaJoin(da3, da2, 0, -1) == 1) {
640  l_dnaDestroy(&da3);
641  return ERROR_INT("da3 join failed", procName, 1);
642  }
643  l_dnaRemoveDupsByHmap(da3, pdad, NULL);
644  l_dnaDestroy(&da3);
645  return 0;
646 }
647 
648 
663 l_ok
665  L_DNA *da2,
666  L_DNA **pdad)
667 {
668 l_int32 i, n1, n2, n;
669 l_uint64 key;
670 l_float64 dval;
671 L_DNA *da_small, *da_big, *dad;
672 L_HASHITEM *hitem;
673 L_HASHMAP *hmap;
674 
675  PROCNAME("l_dnaIntersectionByHmap");
676 
677  if (!pdad)
678  return ERROR_INT("&dad not defined", procName, 1);
679  *pdad = NULL;
680  if (!da1)
681  return ERROR_INT("da1 not defined", procName, 1);
682  if (!da2)
683  return ERROR_INT("da2 not defined", procName, 1);
684 
685  /* Make a hashmap for the elements of the biggest array */
686  n1 = l_dnaGetCount(da1);
687  n2 = l_dnaGetCount(da2);
688  da_small = (n1 < n2) ? da1 : da2; /* do not destroy da_small */
689  da_big = (n1 < n2) ? da2 : da1; /* do not destroy da_big */
690  if ((hmap = l_hmapCreateFromDna(da_big)) == NULL)
691  return ERROR_INT("hmap not made", procName, 1);
692 
693  /* Go through the smallest array, doing a lookup of its dval into
694  * the big array hashmap. If an hitem is returned, check the count.
695  * If the count is 0, ignore; otherwise, add the dval to the
696  * output dad and set the count in the hitem to 0, indicating
697  * that the dval has already been added. */
698  dad = l_dnaCreate(0);
699  *pdad = dad;
700  n = l_dnaGetCount(da_small);
701  for (i = 0; i < n; i++) {
702  l_dnaGetDValue(da_small, i, &dval);
703  l_hashFloat64ToUint64(dval, &key);
704  hitem = l_hmapLookup(hmap, key, i, L_HMAP_CHECK);
705  if (!hitem || hitem->count == 0)
706  continue;
707  l_dnaAddNumber(dad, dval);
708  hitem->count = 0;
709  }
710  l_hmapDestroy(&hmap);
711  return 0;
712 }
713 
714 
729 l_ok
731  L_DNA **pdav,
732  L_DNA **pdac)
733 {
734 l_int32 i, tabsize;
735 l_float64 dval;
736 L_DNA *dac, *dav;
737 L_HASHITEM *hitem;
738 L_HASHMAP *hmap;
739 
740  PROCNAME("l_dnaMakeHistoByHmap");
741 
742  if (pdav) *pdav = NULL;
743  if (pdac) *pdac = NULL;
744  if (!das)
745  return ERROR_INT("das not defined", procName, 1);
746  if (!pdav)
747  return ERROR_INT("&dav not defined", procName, 1);
748  if (!pdac)
749  return ERROR_INT("&dac not defined", procName, 1);
750 
751  /* Traverse the hashtable lists */
752  if ((hmap = l_hmapCreateFromDna(das)) == NULL)
753  return ERROR_INT("hmap not made", procName, 1);
754  dav = l_dnaCreate(0);
755  *pdav = dav;
756  dac = l_dnaCreate(0);
757  *pdac = dac;
758  tabsize = hmap->tabsize;
759  for (i = 0; i < tabsize; i++) {
760  hitem = hmap->hashtab[i];
761  while (hitem) {
762  l_dnaGetDValue(das, hitem->val, &dval);
763  l_dnaAddNumber(dav, dval);
764  l_dnaAddNumber(dac, hitem->count);
765  hitem = hitem->next;
766  }
767  }
768 
769  l_hmapDestroy(&hmap);
770  return 0;
771 }
772 
773 
774 /*----------------------------------------------------------------------*
775  * Miscellaneous operations *
776  *----------------------------------------------------------------------*/
784 L_DNA *
786 {
787 l_int32 i, n, prev, cur;
788 L_DNA *dad;
789 
790  PROCNAME("l_dnaDiffAdjValues");
791 
792  if (!das)
793  return (L_DNA *)ERROR_PTR("das not defined", procName, NULL);
794  n = l_dnaGetCount(das);
795  dad = l_dnaCreate(n - 1);
796  prev = 0;
797  for (i = 1; i < n; i++) {
798  l_dnaGetIValue(das, i, &cur);
799  l_dnaAddNumber(dad, cur - prev);
800  prev = cur;
801  }
802  return dad;
803 }
804 
L_DNA * l_dnaCreate(l_int32 n)
l_dnaCreate()
Definition: dnabasic.c:180
l_ok l_dnaGetIValue(L_DNA *da, l_int32 index, l_int32 *pival)
l_dnaGetIValue()
Definition: dnabasic.c:727
l_ok l_dnaAddNumber(L_DNA *da, l_float64 val)
l_dnaAddNumber()
Definition: dnabasic.c:448
l_ok l_dnaGetDValue(L_DNA *da, l_int32 index, l_float64 *pval)
l_dnaGetDValue()
Definition: dnabasic.c:692
void l_dnaDestroy(L_DNA **pda)
l_dnaDestroy()
Definition: dnabasic.c:332
L_DNA * l_dnaCopy(L_DNA *da)
l_dnaCopy()
Definition: dnabasic.c:369
l_int32 l_dnaGetCount(L_DNA *da)
l_dnaGetCount()
Definition: dnabasic.c:631
L_DNA * l_dnaSelectRange(L_DNA *das, l_int32 first, l_int32 last)
l_dnaSelectRange()
Definition: dnafunc1.c:185
l_ok l_dnaUnionByAset(L_DNA *da1, L_DNA *da2, L_DNA **pdad)
l_dnaUnionByAset()
Definition: dnafunc1.c:416
l_ok l_dnaUnionByHmap(L_DNA *da1, L_DNA *da2, L_DNA **pdad)
l_dnaUnionByHmap()
Definition: dnafunc1.c:622
NUMA * l_dnaConvertToNuma(L_DNA *da)
l_dnaConvertToNuma()
Definition: dnafunc1.c:232
L_ASET * l_asetCreateFromDna(L_DNA *da)
l_asetCreateFromDna()
Definition: dnafunc1.c:332
L_DNA * l_dnaDiffAdjValues(L_DNA *das)
l_dnaDiffAdjValues()
Definition: dnafunc1.c:785
l_ok l_dnaJoin(L_DNA *dad, L_DNA *das, l_int32 istart, l_int32 iend)
l_dnaJoin()
Definition: dnafunc1.c:103
l_ok l_dnaMakeHistoByHmap(L_DNA *das, L_DNA **pdav, L_DNA **pdac)
l_dnaMakeHistoByHmap()
Definition: dnafunc1.c:730
l_ok l_dnaRemoveDupsByHmap(L_DNA *das, L_DNA **pdad, L_HASHMAP **phmap)
l_dnaRemoveDupsByHmap()
Definition: dnafunc1.c:565
L_DNA * numaConvertToDna(NUMA *na)
numaConvertToDna
Definition: dnafunc1.c:260
L_DNA * l_dnaaFlattenToDna(L_DNAA *daa)
l_dnaaFlattenToDna()
Definition: dnafunc1.c:152
l_ok l_dnaRemoveDupsByAset(L_DNA *das, L_DNA **pdad)
l_dnaRemoveDupsByAset()
Definition: dnafunc1.c:364
l_ok l_dnaIntersectionByAset(L_DNA *da1, L_DNA *da2, L_DNA **pdad)
l_dnaIntersectionByAset()
Definition: dnafunc1.c:462
l_ok l_dnaIntersectionByHmap(L_DNA *da1, L_DNA *da2, L_DNA **pdad)
l_dnaIntersectionByHmap()
Definition: dnafunc1.c:664
L_DNA * pixConvertDataToDna(PIX *pix)
pixConvertDataToDna()
Definition: dnafunc1.c:296
L_HASHMAP * l_hmapCreateFromDna(L_DNA *da)
l_hmapCreateFromDna()
Definition: dnafunc1.c:526
l_ok numaAddNumber(NUMA *na, l_float32 val)
numaAddNumber()
Definition: numabasic.c:478
l_ok numaGetFValue(NUMA *na, l_int32 index, l_float32 *pval)
numaGetFValue()
Definition: numabasic.c:719
NUMA * numaCreate(l_int32 n)
numaCreate()
Definition: numabasic.c:194
l_int32 numaGetCount(NUMA *na)
numaGetCount()
Definition: numabasic.c:658
l_uint32 * pixGetData(PIX *pix)
pixGetData()
Definition: pix1.c:1763
l_ok pixGetDimensions(const PIX *pix, l_int32 *pw, l_int32 *ph, l_int32 *pd)
pixGetDimensions()
Definition: pix1.c:1113
Definition: array.h:95
Definition: array.h:107
l_int32 nalloc
Definition: array.h:108
struct L_Dna ** dna
Definition: array.h:110
l_uint64 val
Definition: hashmap.h:117
l_int32 count
Definition: hashmap.h:118
struct L_Hashitem * next
Definition: hashmap.h:119
struct L_Hashitem ** hashtab
Definition: hashmap.h:106
l_int32 tabsize
Definition: hashmap.h:107
Definition: array.h:71
Definition: pix.h:139
Definition: rbtree.h:62
l_ok l_hashFloat64ToUint64(l_float64 val, l_uint64 *phash)
l_hashFloat64ToUint64()
Definition: utils1.c:837