example-apps/PDD/pcb-defect-detection/data/lib_coco/common/maskApi.c

   1 /**************************************************************************
   2 * Microsoft COCO Toolbox.      version 2.0
   3 * Data, paper, and tutorials available at:  http://mscoco.org/
   4 * Code written by Piotr Dollar and Tsung-Yi Lin, 2015.
   5 * Licensed under the Simplified BSD License [see coco/license.txt]
   6 **************************************************************************/
   7 #include "maskApi.h"
   8 #include <math.h>
   9 #include <stdlib.h>
  10
  11 uint umin( uint a, uint b ) { return (a<b) ? a : b; }
  12 uint umax( uint a, uint b ) { return (a>b) ? a : b; }
  13
  14 void rleInit( RLE *R, siz h, siz w, siz m, uint *cnts ) {
  15   R->h=h; R->w=w; R->m=m; R->cnts=(m==0)?0:malloc(sizeof(uint)*m);
  16   siz j; if(cnts) for(j=0; j<m; j++) R->cnts[j]=cnts[j];
  17 }
  18
  19 void rleFree( RLE *R ) {
  20   free(R->cnts); R->cnts=0;
  21 }
  22
  23 void rlesInit( RLE **R, siz n ) {
  24   siz i; *R = (RLE*) malloc(sizeof(RLE)*n);
  25   for(i=0; i<n; i++) rleInit((*R)+i,0,0,0,0);
  26 }
  27
  28 void rlesFree( RLE **R, siz n ) {
  29   siz i; for(i=0; i<n; i++) rleFree((*R)+i); free(*R); *R=0;
  30 }
  31
  32 void rleEncode( RLE *R, const byte *M, siz h, siz w, siz n ) {
  33   siz i, j, k, a=w*h; uint c, *cnts; byte p;
  34   cnts = malloc(sizeof(uint)*(a+1));
  35   for(i=0; i<n; i++) {
  36     const byte *T=M+a*i; k=0; p=0; c=0;
  37     for(j=0; j<a; j++) { if(T[j]!=p) { cnts[k++]=c; c=0; p=T[j]; } c++; }
  38     cnts[k++]=c; rleInit(R+i,h,w,k,cnts);
  39   }
  40   free(cnts);
  41 }
  42
  43 void rleDecode( const RLE *R, byte *M, siz n ) {
  44   siz i, j, k; for( i=0; i<n; i++ ) {
  45     byte v=0; for( j=0; j<R[i].m; j++ ) {
  46       for( k=0; k<R[i].cnts[j]; k++ ) *(M++)=v; v=!v; }}
  47 }
  48
  49 void rleMerge( const RLE *R, RLE *M, siz n, int intersect ) {
  50   uint *cnts, c, ca, cb, cc, ct; int v, va, vb, vp;
  51   siz i, a, b, h=R[0].h, w=R[0].w, m=R[0].m; RLE A, B;
  52   if(n==0) { rleInit(M,0,0,0,0); return; }
  53   if(n==1) { rleInit(M,h,w,m,R[0].cnts); return; }
  54   cnts = malloc(sizeof(uint)*(h*w+1));
  55   for( a=0; a<m; a++ ) cnts[a]=R[0].cnts[a];
  56   for( i=1; i<n; i++ ) {
  57     B=R[i]; if(B.h!=h||B.w!=w) { h=w=m=0; break; }
  58     rleInit(&A,h,w,m,cnts); ca=A.cnts[0]; cb=B.cnts[0];
  59     v=va=vb=0; m=0; a=b=1; cc=0; ct=1;
  60     while( ct>0 ) {
  61       c=umin(ca,cb); cc+=c; ct=0;
  62       ca-=c; if(!ca && a<A.m) { ca=A.cnts[a++]; va=!va; } ct+=ca;
  63       cb-=c; if(!cb && b<B.m) { cb=B.cnts[b++]; vb=!vb; } ct+=cb;
  64       vp=v; if(intersect) v=va&&vb; else v=va||vb;
  65       if( v!=vp||ct==0 ) { cnts[m++]=cc; cc=0; }
  66     }
  67     rleFree(&A);
  68   }
  69   rleInit(M,h,w,m,cnts); free(cnts);
  70 }
  71
  72 void rleArea( const RLE *R, siz n, uint *a ) {
  73   siz i, j; for( i=0; i<n; i++ ) {
  74     a[i]=0; for( j=1; j<R[i].m; j+=2 ) a[i]+=R[i].cnts[j]; }
  75 }
  76
  77 void rleIou( RLE *dt, RLE *gt, siz m, siz n, byte *iscrowd, double *o ) {
  78   siz g, d; BB db, gb; int crowd;
  79   db=malloc(sizeof(double)*m*4); rleToBbox(dt,db,m);
  80   gb=malloc(sizeof(double)*n*4); rleToBbox(gt,gb,n);
  81   bbIou(db,gb,m,n,iscrowd,o); free(db); free(gb);
  82   for( g=0; g<n; g++ ) for( d=0; d<m; d++ ) if(o[g*m+d]>0) {
  83     crowd=iscrowd!=NULL && iscrowd[g];
  84     if(dt[d].h!=gt[g].h || dt[d].w!=gt[g].w) { o[g*m+d]=-1; continue; }
  85     siz ka, kb, a, b; uint c, ca, cb, ct, i, u; int va, vb;
  86     ca=dt[d].cnts[0]; ka=dt[d].m; va=vb=0;
  87     cb=gt[g].cnts[0]; kb=gt[g].m; a=b=1; i=u=0; ct=1;
  88     while( ct>0 ) {
  89       c=umin(ca,cb); if(va||vb) { u+=c; if(va&&vb) i+=c; } ct=0;
  90       ca-=c; if(!ca && a<ka) { ca=dt[d].cnts[a++]; va=!va; } ct+=ca;
  91       cb-=c; if(!cb && b<kb) { cb=gt[g].cnts[b++]; vb=!vb; } ct+=cb;
  92     }
  93     if(i==0) u=1; else if(crowd) rleArea(dt+d,1,&u);
  94     o[g*m+d] = (double)i/(double)u;
  95   }
  96 }
  97
  98 void rleNms( RLE *dt, siz n, uint *keep, double thr ) {
  99   siz i, j; double u;
 100   for( i=0; i<n; i++ ) keep[i]=1;
 101   for( i=0; i<n; i++ ) if(keep[i]) {
 102     for( j=i+1; j<n; j++ ) if(keep[j]) {
 103       rleIou(dt+i,dt+j,1,1,0,&u);
 104       if(u>thr) keep[j]=0;
 105     }
 106   }
 107 }
 108
 109 void bbIou( BB dt, BB gt, siz m, siz n, byte *iscrowd, double *o ) {
 110   double h, w, i, u, ga, da; siz g, d; int crowd;
 111   for( g=0; g<n; g++ ) {
 112     BB G=gt+g*4; ga=G[2]*G[3]; crowd=iscrowd!=NULL && iscrowd[g];
 113     for( d=0; d<m; d++ ) {
 114       BB D=dt+d*4; da=D[2]*D[3]; o[g*m+d]=0;
 115       w=fmin(D[2]+D[0],G[2]+G[0])-fmax(D[0],G[0]); if(w<=0) continue;
 116       h=fmin(D[3]+D[1],G[3]+G[1])-fmax(D[1],G[1]); if(h<=0) continue;
 117       i=w*h; u = crowd ? da : da+ga-i; o[g*m+d]=i/u;
 118     }
 119   }
 120 }
 121
 122 void bbNms( BB dt, siz n, uint *keep, double thr ) {
 123   siz i, j; double u;
 124   for( i=0; i<n; i++ ) keep[i]=1;
 125   for( i=0; i<n; i++ ) if(keep[i]) {
 126     for( j=i+1; j<n; j++ ) if(keep[j]) {
 127       bbIou(dt+i*4,dt+j*4,1,1,0,&u);
 128       if(u>thr) keep[j]=0;
 129     }
 130   }
 131 }
 132
 133 void rleToBbox( const RLE *R, BB bb, siz n ) {
 134   siz i; for( i=0; i<n; i++ ) {
 135     uint h, w, x, y, xs, ys, xe, ye, cc, t; siz j, m;
 136     h=(uint)R[i].h; w=(uint)R[i].w; m=R[i].m;
 137     m=((siz)(m/2))*2; xs=w; ys=h; xe=ye=0; cc=0;
 138     if(m==0) { bb[4*i+0]=bb[4*i+1]=bb[4*i+2]=bb[4*i+3]=0; continue; }
 139     for( j=0; j<m; j++ ) {
 140       cc+=R[i].cnts[j]; t=cc-j%2; y=t%h; x=(t-y)/h;
 141       xs=umin(xs,x); xe=umax(xe,x); ys=umin(ys,y); ye=umax(ye,y);
 142     }
 143     bb[4*i+0]=xs; bb[4*i+2]=xe-xs+1;
 144     bb[4*i+1]=ys; bb[4*i+3]=ye-ys+1;
 145   }
 146 }
 147
 148 void rleFrBbox( RLE *R, const BB bb, siz h, siz w, siz n ) {
 149   siz i; for( i=0; i<n; i++ ) {
 150     double xs=bb[4*i+0], xe=xs+bb[4*i+2];
 151     double ys=bb[4*i+1], ye=ys+bb[4*i+3];
 152     double xy[8] = {xs,ys,xs,ye,xe,ye,xe,ys};
 153     rleFrPoly( R+i, xy, 4, h, w );
 154   }
 155 }
 156
 157 int uintCompare(const void *a, const void *b) {
 158   uint c=*((uint*)a), d=*((uint*)b); return c>d?1:c<d?-1:0;
 159 }
 160
 161 void rleFrPoly( RLE *R, const double *xy, siz k, siz h, siz w ) {
 162   /* upsample and get discrete points densely along entire boundary */
 163   siz j, m=0; double scale=5; int *x, *y, *u, *v; uint *a, *b;
 164   x=malloc(sizeof(int)*(k+1)); y=malloc(sizeof(int)*(k+1));
 165   for(j=0; j<k; j++) x[j]=(int)(scale*xy[j*2+0]+.5); x[k]=x[0];
 166   for(j=0; j<k; j++) y[j]=(int)(scale*xy[j*2+1]+.5); y[k]=y[0];
 167   for(j=0; j<k; j++) m+=umax(abs(x[j]-x[j+1]),abs(y[j]-y[j+1]))+1;
 168   u=malloc(sizeof(int)*m); v=malloc(sizeof(int)*m); m=0;
 169   for( j=0; j<k; j++ ) {
 170     int xs=x[j], xe=x[j+1], ys=y[j], ye=y[j+1], dx, dy, t, d;
 171     int flip; double s; dx=abs(xe-xs); dy=abs(ys-ye);
 172     flip = (dx>=dy && xs>xe) || (dx<dy && ys>ye);
 173     if(flip) { t=xs; xs=xe; xe=t; t=ys; ys=ye; ye=t; }
 174     s = dx>=dy ? (double)(ye-ys)/dx : (double)(xe-xs)/dy;
 175     if(dx>=dy) for( d=0; d<=dx; d++ ) {
 176       t=flip?dx-d:d; u[m]=t+xs; v[m]=(int)(ys+s*t+.5); m++;
 177     } else for( d=0; d<=dy; d++ ) {
 178       t=flip?dy-d:d; v[m]=t+ys; u[m]=(int)(xs+s*t+.5); m++;
 179     }
 180   }
 181   /* get points along y-boundary and downsample */
 182   free(x); free(y); k=m; m=0; double xd, yd;
 183   x=malloc(sizeof(int)*k); y=malloc(sizeof(int)*k);
 184   for( j=1; j<k; j++ ) if(u[j]!=u[j-1]) {
 185     xd=(double)(u[j]<u[j-1]?u[j]:u[j]-1); xd=(xd+.5)/scale-.5;
 186     if( floor(xd)!=xd || xd<0 || xd>w-1 ) continue;
 187     yd=(double)(v[j]<v[j-1]?v[j]:v[j-1]); yd=(yd+.5)/scale-.5;
 188     if(yd<0) yd=0; else if(yd>h) yd=h; yd=ceil(yd);
 189     x[m]=(int) xd; y[m]=(int) yd; m++;
 190   }
 191   /* compute rle encoding given y-boundary points */
 192   k=m; a=malloc(sizeof(uint)*(k+1));
 193   for( j=0; j<k; j++ ) a[j]=(uint)(x[j]*(int)(h)+y[j]);
 194   a[k++]=(uint)(h*w); free(u); free(v); free(x); free(y);
 195   qsort(a,k,sizeof(uint),uintCompare); uint p=0;
 196   for( j=0; j<k; j++ ) { uint t=a[j]; a[j]-=p; p=t; }
 197   b=malloc(sizeof(uint)*k); j=m=0; b[m++]=a[j++];
 198   while(j<k) if(a[j]>0) b[m++]=a[j++]; else {
 199     j++; if(j<k) b[m-1]+=a[j++]; }
 200   rleInit(R,h,w,m,b); free(a); free(b);
 201 }
 202
 203 char* rleToString( const RLE *R ) {
 204   /* Similar to LEB128 but using 6 bits/char and ascii chars 48-111. */
 205   siz i, m=R->m, p=0; long x; int more;
 206   char *s=malloc(sizeof(char)*m*6);
 207   for( i=0; i<m; i++ ) {
 208     x=(long) R->cnts[i]; if(i>2) x-=(long) R->cnts[i-2]; more=1;
 209     while( more ) {
 210       char c=x & 0x1f; x >>= 5; more=(c & 0x10) ? x!=-1 : x!=0;
 211       if(more) c |= 0x20; c+=48; s[p++]=c;
 212     }
 213   }
 214   s[p]=0; return s;
 215 }
 216
 217 void rleFrString( RLE *R, char *s, siz h, siz w ) {
 218   siz m=0, p=0, k; long x; int more; uint *cnts;
 219   while( s[m] ) m++; cnts=malloc(sizeof(uint)*m); m=0;
 220   while( s[p] ) {
 221     x=0; k=0; more=1;
 222     while( more ) {
 223       char c=s[p]-48; x |= (c & 0x1f) << 5*k;
 224       more = c & 0x20; p++; k++;
 225       if(!more && (c & 0x10)) x |= -1 << 5*k;
 226     }
 227     if(m>2) x+=(long) cnts[m-2]; cnts[m++]=(uint) x;
 228   }
 229   rleInit(R,h,w,m,cnts); free(cnts);
 230 }