/* Analyzes the mutual information content in a set of "true" candidates. */ /* Last edited on 2005-01-16 14:11:42 by stolfi */ /* Copyright © 2005 Universidade Estadual de Campinas. See note at end of file. */ #define PROG_NAME "frb_analyze" #define PROG_VERSION "1.0" #define PROG_USAGE \ PROG_NAME " \\\n" \ " -rawCandSet NAME [ -maxCands NUMBER ] \\\n" \ " -refCandSet FILE \\\n" \ " -refCandDir DIR \\\n" \ " -curveDir DIR -curveName NAME \\\n" \ " -band NUM \\\n" \ " -origStep NUM \n" \ " -nSamples NUM [ -maxShift NUM ] \\\n" \ " -sampleErr NUM \\\n" \ " [ -posFormula ] [ -cosWindow ]" #define _GNU_SOURCE #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include int main(int argc, char**argv) { /* Reads a list of presumably "TRUE" candidates. From each candidate, if large enough, extracts a sub-candidate with specified number of steps. Each sub-candidate is shifted so as to minimize the mean square distance between samples, after a crude realignment. For each candidate, converts each curve segment into a signal (the "shape function"). Then computes the mean and difference of the two signals for each candidate, and the Fourier transforms of these signals. Then computes the average and variance of each Fourier coefficient, over all candidates. Finally computes the information contents for each frequency, and the combined information per frequency band. */ /* Parse command-line arguments: */ frb_options_t *o = frb_get_options(argc, argv); int ns = o->nSamples; /* Number of samples in curves ({= 2^m+1}). */ int nr = ns - 1; /* Basic period before doubling ({= 2^m}). */ /* Read input candidates: */ frb_candidate_read_data_t rawCandData; { char *fileName = NULL; asprintf(&fileName, "%s.can", o->rawCandSet); FILE *rd = open_read(fileName); rawCandData = frb_candidate_read(rd); fclose(rd); free(fileName); fileName = NULL; } frb_candidate_vec_t *rawCand = &(rawCandData.c); /* Read curves needed by those candidates: */ bool_vec_t needed = frb_candidate_curves_used(rawCand); frb_curve_read_data_t **curveData; double unitMaxPos; /* Maximum quantization unit for positions. */ int ncv; { frb_curve_list_read_data_t cvAllData = frb_curve_list_read ( o->curveDir, o->curveName, /* scale */ o->curveScale, /* sel */ &needed, /* headerOnly */ FALSE, /* centralize */ FALSE ); curveData = cvAllData.sgData; ncv = cvAllData.ncv; unitMaxPos = cvAllData.unitMax; } /* Create the raw chain files, if so requested: */ if (o->rawCandDir != NULL) { frb_split_raw_candidates ( &rawCandData, curveData, ncv, o->rawCandDir ); } /* Process candidates, extract signals, return Fourier transforms: */ frb_transform_t *SS, *MM, *DD; int nsg; /* Number of candidates accepted = number of signals. */ frb_refine_candidates ( &rawCandData, curveData, ncv, o->refCandDir, o->refCandSet, o->maxShift, ns, o->cosWindow, &SS, &MM, &DD, &nsg ); /* Compute quantization noise expected in {a,b} signals and FTs. */ /* Assumes that the scale of shape functions is the same as that of curves. */ double extraVar = o->sampleErr*o->sampleErr; /* Intrinsic sample variance. */ /* Compute average and variance of each Fourier coeff of each signal: */ int fmax = nr-1; /* Nonzero coeffs range from freq {f=1} to {f=fmax}. */ frb_transform_t avgS = frb_signal_new(fmax); frb_zero_signal(&avgS); frb_transform_t varS = frb_signal_new(fmax); frb_zero_signal(&varS); frb_transform_t avgM = frb_signal_new(fmax); frb_zero_signal(&avgM); frb_transform_t varM = frb_signal_new(fmax); frb_zero_signal(&varM); frb_transform_t avgD = frb_signal_new(fmax); frb_zero_signal(&avgD); frb_transform_t varD = frb_signal_new(fmax); frb_zero_signal(&varD); frb_compute_fourier_stats ( SS, 2*nsg, fmax, extraVar, &avgS, &varS, o->refCandDir, "ab" ); frb_compute_fourier_stats ( MM, nsg, fmax, extraVar/2, &avgM, &varM, o->refCandDir, "m" ); frb_compute_fourier_stats ( DD, nsg, fmax, extraVar*2, &avgD, &varD, o->refCandDir, "d" ); /* Compute the information content of each Fourier coefficient: */ /* Note that coef of index {p} is a sinusoid of freq {f = p+1} over {2*nr}. */ frb_transform_t info = frb_signal_new(fmax); double step = o->origStep*o->band; /* Sampling step for these curves. */ double L = nr*step; /* Nominal candidate length (mm) */ { char *coefFileName = NULL; asprintf(&coefFileName, "%s.ifc", o->refCandSet); FILE *wr = open_write(coefFileName); int p; for (p = 0; p < fmax; p++) { int f = p+1; /* Frequency. */ double lambda = ((double)2*L)/((double)f); /* Information quantity per coefficient */ if (o->posFormula) { /* Aternative formula (biased, never negative): */ double X = varM.el[p]/varD.el[p]; double Y = varD.el[p]/varM.el[p]; double Arg = X + 0.5 + Y/16; info.el[p] = log(Arg)/log(2.0)/2; } else { /* Original formula (less bias, may be negative): */ double Num = varS.el[p]*varS.el[p]; double Den = varM.el[p]*varD.el[p]; double Arg = Num/Den; info.el[p] = log(Arg)/log(2.0)/2; } fprintf ( wr, "%5d %5d %8.3f %+14.6f %18.10f %+14.6f %18.10f %+14.6f %18.10f %7.4f %7.4f\n", p, f, lambda, avgS.el[p], varS.el[p], avgM.el[p], varM.el[p], avgD.el[p], varD.el[p], info.el[p], info.el[p]/L ); } fclose(wr); free(coefFileName); coefFileName = NULL; } /* Compute total information contents: */ double itot = 0.0; int p; for (p = 0; p < fmax; p++) { itot += info.el[p]; } fprintf(stderr, "total information = %8.5f\n", itot); /* Compute the information content for each frequency band: */ { char *bandFileName = NULL; asprintf(&bandFileName, "%s.ibd", o->refCandSet); FILE *wr = open_write(bandFileName); int flo = 1; int fhi = 1; while (flo <= fmax) { double lambda_lo = 2*L/flo; double lambda_hi = 2*L/fhi; /* Add information for freqs in {flo..fhi}: */ double infobd = 0.0; int f; for (f = flo; f <= fhi; f++) { infobd += info.el[f-1]; } fprintf ( wr, "%5d %5d %8.3f %8.3f %7.4f %7.5f\n", flo, fhi, lambda_lo, lambda_hi, infobd, infobd/L ); flo = fhi + 1; fhi = 2*flo - 1; if (fhi > fmax) { fhi = fmax; } } fclose(wr); free(bandFileName); bandFileName = NULL; } free(info.el); fprintf(stderr, "\n\ndone.\n"); return 0; } void frb_split_raw_candidates ( frb_candidate_read_data_t *cd, /* Candidate data. */ frb_curve_read_data_t **cvd, /* Data for each curve. */ int ncv, /* Number of curves. */ char *rawCandDir /* Directory for output files of raw candidates. */ ) { int rawCandNum = cd->c.nel; char *rawCandSetCmt = cd->cmt; int rawIndex; for (rawIndex = 0; rawIndex < rawCandNum; rawIndex++) { fprintf(stderr, "-----------------------------------\n"); fprintf(stderr, "splitting input candidate %06d\n", rawIndex); frb_candidate_t *rawCand = &(cd->c.el[rawIndex]); /* Directory for candidate-related data: */ char *candDir = NULL; asprintf(&candDir, "%s/%06d", rawCandDir, rawIndex); /* Comment for candidate files: */ char *candCmt = frb_raw_cand_comment ( rawCandSetCmt, rawIndex, rawCand, cvd, ncv); /* Make sure that the candidate's directory exists: */ if ((mkdir(candDir, 0777) < 0) && (errno != EEXIST)) { perror(candDir); exit(1); } /* Extracts the segment as open curves {a,b}: */ frb_segment_t *aSeg = &(rawCand->seg[0]); frb_curve_read_data_t *cvda = cvd[aSeg->cvx]; frb_curve_t a = frb_curve_extract_segment(&(cvda->c), aSeg); frb_segment_t *bSeg = &(rawCand->seg[1]); frb_curve_read_data_t *cvdb = cvd[bSeg->cvx]; frb_curve_t b = frb_curve_extract_segment(&(cvdb->c), bSeg); /* Save curves {a,b} to disk, extract signals {sa,sb}: */ frb_signal_t sa, sb; frb_process_curve(&a, candDir, "a", candCmt, &sa); frb_process_curve(&b, candDir, "b", candCmt, &sb); free(a.el); free(b.el); /* Save signals {sa,sb} to disk: */ frb_process_signal(&sa, candDir, "a", candCmt, FALSE, NULL); frb_process_signal(&sb, candDir, "b", candCmt, FALSE, NULL); free(sa.el); free(sb.el); free(candDir); free(candCmt); } fprintf(stderr, "-----------------------------------\n"); fprintf(stderr, "\n"); } /* Set to TRUE to get a printout of all su-candidates tested. */ static bool debug_align = FALSE; void frb_refine_candidates ( frb_candidate_read_data_t *cd, /* Candidate data. */ frb_curve_read_data_t **cvd, /* Data for each curve. */ int ncv, /* Number of curves. */ char *refCandDir, /* Directory for output files of candidates. */ char *refName, /* Filename for output candidate set (minus ".can"). */ double maxShift, /* Maximum rel displacement. */ int ns, /* Desired number of samples. */ bool cosWindow, /* TRUE uses cosine windowing before Fourier. */ frb_transform_t **SS, /* (OUT) Fourier transfs of all {a,b} shape fns. */ frb_transform_t **MM, /* (OUT) Fourier transfs of all mean signals {m}. */ frb_transform_t **DD, /* (OUT) Fourier transfs of all diff signals {d}. */ int *refCandNum /* (OUT) Number of candidates accepted. */ ) { int rawCandNum = cd->c.nel; affirm(((ns-1)&(ns-2)) == 0, "num samples must be 2^k + 1"); fprintf(stderr, "realigning candidates and trimming to %d samples (%d steps)\n", ns, ns-1); /* Create comment text for all standardized candidates. */ char *rawCandSetCmt = cd->cmt; char *refCandSetCmt = frb_ref_cand_file_comments(rawCandSetCmt, maxShift, ns); /* Allocate candidate vectors (to be trimmed later): */ frb_candidate_vec_t refCands = frb_candidate_vec_new(rawCandNum); int ref_to_raw[rawCandNum]; /* {refIndex} - to - {rawIndex} map */ int refIndex = 0; int rawIndex; double *cvLength = frb_compute_curve_lengths(cvd, ncv); for (rawIndex = 0; rawIndex < rawCandNum; rawIndex++) { fprintf(stderr, "-----------------------------------\n"); fprintf(stderr, "processing input candidate %06d\n", rawIndex); frb_candidate_t *rawCand = &(cd->c.el[rawIndex]); /* Trim and align candidate to required size: */ frb_candidate_t refCand = frb_standardize_candidate ( rawCand, cvd, ncv, cvLength, maxShift, ns ); if (refCand.seg[0].ns <= 0) { fprintf(stderr, "input candidate discarded\n"); } else { fprintf(stderr, "creating output candidate %06d\n", refIndex); refCands.el[refIndex] = refCand; ref_to_raw[refIndex] = rawIndex; refIndex++; } } fprintf(stderr, "-----------------------------------\n"); fprintf(stderr, "\n"); /* Write new candidates to disk: */ (*refCandNum) = refIndex; frb_candidate_vec_trim(&refCands, *refCandNum); char *fileName = NULL; asprintf(&fileName, "%s.can", refName); FILE *wr = open_write(fileName); frb_candidate_write(wr, refCandSetCmt, &refCands, cd->lambda); fclose(wr); free(fileName); fileName = NULL; (*SS) = (frb_transform_t *) notnull(malloc(2*(*refCandNum)*sizeof(frb_transform_t)), "no mem"); (*MM) = (frb_transform_t *) notnull(malloc((*refCandNum)*sizeof(frb_transform_t)), "no mem"); (*DD) = (frb_transform_t *) notnull(malloc((*refCandNum)*sizeof(frb_transform_t)), "no mem"); /* Extract signals and Fourier transforms from new candidates: */ for (refIndex = 0; refIndex < *refCandNum; refIndex++) { fprintf(stderr, "-----------------------------------\n"); fprintf(stderr, "processing output candidate %06d\n", refIndex); frb_candidate_t *refCand = &(refCands.el[refIndex]); /* Recover corresponding input candidate: */ rawIndex = ref_to_raw[refIndex]; frb_candidate_t *rawCand = &(cd->c.el[rawIndex]); /* Directory for candidate-related data: */ char *candDir = NULL; asprintf(&candDir, "%s/%06d", refCandDir, refIndex); char *candCmt = frb_raw_ref_cand_comment ( refCandSetCmt, rawIndex, rawCand, refIndex, refCand, cvd, ncv); /* Make sure that the candidate's directory exists: */ if ((mkdir(candDir, 0777) < 0) && (errno != EEXIST)) { perror(candDir); exit(1); } /* Extract segments as open curves {a,b}: */ frb_segment_t *aSeg = &(refCand->seg[0]); frb_curve_read_data_t *cvda = cvd[aSeg->cvx]; frb_curve_t a = frb_curve_extract_segment(&(cvda->c), aSeg); frb_segment_t *bSeg = &(refCand->seg[1]); frb_curve_read_data_t *cvdb = cvd[bSeg->cvx]; frb_curve_t b = frb_curve_extract_segment(&(cvdb->c), bSeg); affirm(aSeg->ns == bSeg->ns, "sample count mismatch"); /* Save curves {a,b} to disk, extract signals {sa,sb}: */ frb_signal_t sa, sb; frb_process_curve(&a, candDir, "a", candCmt, &sa); frb_process_curve(&b, candDir, "b", candCmt, &sb); free(a.el); free(b.el); /* Compute mean signal {sm} and difference signal {sd}: */ frb_signal_t sm = frb_signal_mean(&sa, &sb); frb_signal_t sd = frb_signal_diff(&sa, &sb); /* Save signals to disk, compute Fourier transforms and spectra: */ { frb_transform_t *Ai = &((*SS)[2*refIndex]); frb_process_signal(&sa, candDir, "a", candCmt, cosWindow, Ai); frb_transform_t *Bi = &((*SS)[2*refIndex+1]); frb_process_signal(&sb, candDir, "b", candCmt, cosWindow, Bi); frb_transform_t *Mi = &((*MM)[refIndex]); frb_process_signal(&sm, candDir, "m", candCmt, cosWindow, Mi); frb_transform_t *Di = &((*DD)[refIndex]); frb_process_signal(&sd, candDir, "d", candCmt, cosWindow, Di); } free(sa.el); free(sb.el); free(sm.el); free(sd.el); free(candDir); } fprintf(stderr, "-----------------------------------\n"); fprintf(stderr, "\n"); free(refCandSetCmt); for (refIndex = 0; refIndex < refCands.nel; refIndex++) { frb_match_packed_t *pm = refCands.el[refIndex].pm; if (pm != NULL) { free(pm->steps); free(pm); } } free(refCands.el); } frb_candidate_t frb_standardize_candidate ( frb_candidate_t *cand, /* The original candidate. */ frb_curve_read_data_t **cvd, /* All shape functions. */ int ncv, /* Number of curves. */ double *cvLength, /* {cvLangth[i]} is length of {cvd[i].c}. */ double maxShift, /* Maximum rel displacement. */ int ns /* Desired number of samples. */ ) { /* The two matched segments: */ frb_segment_t aSeg = cand->seg[0]; frb_segment_t bSeg = cand->seg[1]; /* The corresponding curves: */ frb_curve_read_data_t *cda = cvd[aSeg.cvx]; frb_curve_read_data_t *cdb = cvd[bSeg.cvx]; /* Total samples in the two curves: */ int ma = cda->c.nel; int mb = cdb->c.nel; /* Samples in the two segments: */ int rna = aSeg.ns; int rnb = bSeg.ns; /* Step size in each curve: */ double aStep = cvLength[aSeg.cvx] / ((double)ma); double bStep = cvLength[bSeg.cvx] / ((double)mb); /* Extra samples needed on each segment for shift adjustment: */ int aEx = (int)ceil(maxShift/2.0 / aStep); int bEx = (int)ceil(maxShift/2.0 / bStep); /* Number of samples in each segment after extenstion: */ int na = rna + 2*aEx; if (na > ma) { na = ma; } int nb = rnb + 2*bEx; if (nb > mb) { nb = mb; } /* Number of samples to extend on both ends: */ int aStretch = (na - rna) / 2; int bStretch = (nb - rnb) / 2; int extra[2] = { aStretch, bStretch }; /* Expanded candidate: */ frb_candidate_t eCand = frb_candidate_expand(cand, extra, extra); /* Expanded curve segments: */ frb_curve_t ca = frb_curve_extract_segment(&(cda->c), &(eCand.seg[0])); frb_curve_t cb = frb_curve_extract_segment(&(cdb->c), &(eCand.seg[1])); frb_match_t mt = frb_get_matching(&eCand); double step = (aStep + bStep) / 2.0; int maxAdjust = (int)ceil(maxShift / step); i2_t ctr = frb_select_sub_segments(&ca, &cb, &mt, ns-1, maxAdjust); return frb_make_sub_cand(cand, ctr, ns-1); } i2_t frb_select_sub_segments ( frb_curve_t *a, /* The first curve, reversed as needed. */ frb_curve_t *b, /* The second curve, reversed as needed. */ frb_match_t *mt, /* The matching between {a} and {b} samples. */ int nSteps, /* Number of sampling steps in output. */ int maxAdjust /* Max number of steps to shift {b} rel to {a}. */ ) { /* Valid index ranges into {mt}: */ int iMin = 0; int iMax = mt->nel - 1; fprintf(stderr, "max shift = %d\n", maxAdjust); /* Matched sections of the two segments: */ int aMin = mt->el[iMin].c[0], aMax = mt->el[iMax].c[0]; int bMin = mt->el[iMin].c[1], bMax = mt->el[iMax].c[1]; if (debug_align) { fprintf(stderr, "# matched = a[%d..%d]--b[%d..%d]", aMin, aMax, bMin, bMax); } affirm(nSteps % 2 == 0 , "nSteps must be even"); int hSteps = nSteps / 2; int hStepsPlus = hSteps + (maxAdjust + 1) / 2; /* Find lowest viable matched pair {mt[iIni]} for the seg centers: */ int iIni = iMin; while ( (iIni <= iMax) && ( (mt->el[iIni].c[0] < mt->el[iMin].c[0] + hStepsPlus) || (mt->el[iIni].c[1] < mt->el[iMin].c[1] + hStepsPlus) ) ) { iIni++; } /* Find highest viable matched pair {mt[iFin]} for the seg centers: */ int iFin = iMax; while ( (iFin >= iIni) && ( (mt->el[iFin].c[0] > mt->el[iMax].c[0] - hStepsPlus) || (mt->el[iFin].c[1] > mt->el[iMax].c[1] - hStepsPlus) ) ) { iFin--; } /* Find best center pair {ctrBest} in {mt[iIni]..mt[iFin]}, plus shifts: */ i2_t ctrBest = (i2_t){{-1,-1}}; if ( iIni > iFin ) { fprintf(stderr, "candidate is too short\n"); } else { /* Convention: {maxAdjust = 0} implies no search at all - use middle piece. */ if (maxAdjust == 0) { int iMid = (iIni+iFin)/2; iIni = iFin = iMid; } /* Ranges for center samples of refined cand: */ int aIni = mt->el[iIni].c[0], aFin = mt->el[iFin].c[0]; int bIni = mt->el[iIni].c[1], bFin = mt->el[iFin].c[1]; if (debug_align) { fprintf(stderr, " searching in a[%d..%d]--b[%d..%d]\n", aIni, aFin, bIni, bFin); } int shiftBest = 0; double d2Best = INF; int cStep = 4; /* Step for coarse shift search: */ int im, shift; for (im = iIni; im <= iFin; im++) { int aMid = mt->el[im].c[0]; int bMid = mt->el[im].c[1]; /* Optimum for this choice of {aMid,bMid}: */ i2_t ctrBestLoc = (i2_t){{-1,-1}}; int shiftBestLoc = 0; double d2BestLoc = INF; /* Coarse search for best shift: */ for (shift = -maxAdjust; shift <= maxAdjust; shift++) { if ((shift % cStep) == 0) { frb_try_alignment ( a, aMid, b, bMid, shift, hSteps, &d2BestLoc, &ctrBestLoc, &shiftBestLoc ); } } assert(d2BestLoc < INF); /* Fine search for best shift: */ int ds; for (ds = -cStep+1; ds < cStep; ds++) { int shift = shiftBestLoc + ds; if ((shift >= -maxAdjust) && (shift <= maxAdjust)) { frb_try_alignment ( a, aMid, b, bMid, shift, hSteps, &d2Best, &ctrBest, &shiftBest ); } } } assert(d2Best < INF); fprintf(stderr, "best match = a[%d]--b[%d] shift = %3d dist = %8.3f\n", ctrBest.c[0], ctrBest.c[1], shiftBest, sqrt(d2Best) ); if (debug_align) { affirm(FALSE, "debug on - aborted"); } } return ctrBest; } void frb_try_alignment ( frb_curve_t *a, int aMid, frb_curve_t *b, int bMid, int shift, int nSteps, double *d2Best, i2_t *ctrBest, int *shiftBest ) { assert(nSteps % 2 == 0); int hSteps = nSteps / 2; int da = shift / 2; int db = shift - da; int aCtr = aMid + da, aIni = aCtr - hSteps, aFin = aCtr + hSteps; int bCtr = bMid - db, bIni = bCtr - hSteps, bFin = bCtr + hSteps; if ((aIni >= 0) && (aFin <= a->nel-1) && (bIni >= 0) && (bFin <= b->nel-1)) { if (debug_align) { fprintf(stderr, "# a[%d%+d]--b[%d%+d]", aMid, da, bMid, db); } frb_curve_t ca = frb_curve_trim(a, aIni, nSteps+1); double La = frb_curve_length(&ca); frb_signal_t sa = frb_shape_from_curve(&ca, La); free(ca.el); frb_curve_t cb = frb_curve_trim(b, bIni, nSteps+1); double Lb = frb_curve_length(&cb); frb_signal_t sb = frb_shape_from_curve(&cb, Lb); free(cb.el); double d2 = frb_mean_diff_sqr(&sa, &sb); free(sa.el); free(sb.el); if (debug_align) { fprintf(stderr, " dist = %8.3f\n", sqrt(d2)); } if (d2 < *d2Best) { *d2Best = d2; *shiftBest = shift; *ctrBest = (i2_t){{ aCtr, bCtr }}; } } } void frb_process_curve ( frb_curve_t *c, /* The curve. */ char *outDir, /* Output directory name. */ char *cvTag, /* Side tag ("a" or "b"). */ char *candCmt, /* Comment text of candidate. */ frb_signal_t *s /* (OUT) The corresponding signal (shape function). */ ) { char *cvCmt = NULL, *fileName = NULL; asprintf ( &cvCmt, "%s\n\nside = \"%s\"\n\nconverted to shape function", candCmt, cvTag ); asprintf(&fileName, "%s/%s.flc", outDir, cvTag); FILE *wr = open_write(fileName); r4x4_t M = frb_curve_normalization_matrix(c, FALSE); frb_curve_t e = frb_curve_map(c, &M); frb_curve_write(wr, cvCmt, &e, /* unit */ FRB_UNIT_FOR_COORD, 1.0); fclose(wr); free(fileName); fileName = NULL; free(cvCmt); free(e.el); double L = frb_curve_length(c); fprintf(stderr, "%s curve length = %.6f\n", cvTag, L); (*s) = frb_shape_from_curve(c, L); frb_ete_norm_open_shape(s); } /* Maximum allowed signal or transform value after quantization: */ #define MaxQuantVal (10000000.0) void frb_process_signal ( frb_signal_t *s, /* The signal. */ char *outDir, /* Output directory name. */ char *sTag, /* Signal tag ("a", "b", "d", or "m"). */ char *candCmt, /* Candidate's comments */ bool cosWindow, /* TRUE uses cosine windowing before Fourier. */ frb_transform_t *F /* (OUT) Fourier transform, or NULL. */ ) { int ns = s->nel; char *fileName = NULL; FILE *wr; char *sCmt = NULL; asprintf ( &sCmt, "%s\n\nsignal = \"%s\" (%s)", candCmt, sTag, frb_signal_comment(sTag) ); /* double unit = frb_select_signal_unit(s, 1024.0); */ /* Write the signal itself: */ asprintf(&fileName, "%s/%s.fsh", outDir, sTag); wr = open_write(fileName); double unitSignal = FRB_UNIT_FOR_SHAPE/2.0; frb_signal_write(wr, sCmt, s, /* stride */ 0.0, /* unit */ unitSignal); fclose(wr); free(fileName); fileName = NULL; /* Check whether it starts and ends at zero: */ /* fprintf(stderr, "s[0] = %18.10f s[ns-1] = %18.10f\n", s->el[0], s->el[ns-1]); */ /* Ensure that the num of samples is {2^k}: */ int nr = ns - 1; if (F != NULL) { /* Number of samples must be a power of 2 for FFT: */ demand((nr & (nr - 1)) == 0, "length is not 2^m"); /* Prepare samples for Fourier transform: */ int nx = 2*nr; frb_signal_t x = double_vec_new(nx); int i; /* Append a flipped copy of the signal. Assumes that {s[0]=s[nr]=0}. */ x.el[0] = 0.0; x.el[nr] = 0.0; for (i = 1; i < nr; i++) { x.el[i] = s->el[i]; x.el[nr+i] = -s->el[nr-i]; } if (cosWindow) { /* Apply cosine windowing: */ for (i = 0; i < nx; i++) { double theta = ((double)i)/((double)nx)*2*Pi; double wi = 0.5*(1 - cos(theta)); x.el[i] *= wi; } } /* Compute and write the Hartley-Fourier transform of {x}: */ double_vec_t X = double_vec_new(nx); frb_fourier_transform(&x, &X); frb_check_power_preservation(&x, &X); /* Extract significant DFT coeffs of original signal. */ int fmax = nr-1; /* Nonzero freqs range from 1 to {fmax}. */ (*F) = double_vec_new(fmax); /* Because of the flip-doubling, the Hartley-Fourier coeff {X[p]} should be the negative of its partner {X[nx-p]}, and both {X[0]} and {X[nx/2]} should be zero. We set {F[p]} to the coefficient of the sinusoidal component with frequency {f=p+1}. */ double seven = 0.0, sodd = 0.0; double even = X.el[0]; seven += even*even; int p; for (p = 0; p < fmax; p++) { int f = p+1; /* Frequency; */ double odd = (X.el[f]-X.el[nx-f])/2; even = (X.el[f]+X.el[nx-f])/2; F->el[p] = odd; seven += even*even; sodd += odd*odd; } even = X.el[nr]; seven += even*even; double eoratio = sqrt(seven/(sodd + 1.0e-200)); if (eoratio > FRB_MAX_NORM_MISMATCH) { fprintf(stderr, "coeff rms: even = %18.10f odd = %18.10f\n", sqrt(seven), sqrt(sodd) ); } /* Paranoid check: */ frb_check_power_preservation(s, F); /* Find the maximum Fourier coefficient and choose the quant unit: */ double maxFourier = 1.0e-100; for (p = 0; p < fmax; p++) { double Fp = fabs(F->el[p]); if (Fp > maxFourier) { maxFourier = Fp; } } double maxUnitFourier = maxFourier/(MaxQuantVal-1); double unitFourier = FRB_UNIT_FOR_SHAPE / sqrt(((double)nr)) / 10.0; if (unitFourier > maxUnitFourier) { unitFourier = maxUnitFourier; } /* Write the Fourier transform to disk: */ char *ftCmt = NULL; asprintf(&ftCmt, "%s\n\nflip-doubled Fourier transform", sCmt); asprintf(&fileName, "%s/%s.fft", outDir, sTag); wr = open_write(fileName); frb_signal_write(wr, ftCmt, F, /* stride */ 0.0, /* unit */ unitFourier); fclose(wr); free(fileName); fileName = NULL; /* Choose the quant unit for the power spectrum: */ double unitPower = (maxFourier*maxFourier)/(MaxQuantVal-1); /* Compute and write the power spectrum: */ frb_signal_t pwr; /* Valid frequencies range from 1 to {fmax} (freq 0 has no power): */ pwr = double_vec_new(fmax); for (p = 0; p < fmax; p++) { pwr.el[p] = F->el[p]*F->el[p]; } char *pwrCmt = NULL; asprintf(&pwrCmt, "%s\n\npower spectrum", ftCmt); asprintf(&fileName, "%s/%s.fpw", outDir, sTag); wr = open_write(fileName); frb_signal_write(wr, pwrCmt, &pwr, /* stride */ 0.0, /* unit */ unitPower); fclose(wr); free(fileName); fileName = NULL; free(pwr.el); free(x.el); free(X.el); free(ftCmt); free(pwrCmt); } free(sCmt); } frb_signal_t frb_shape_from_curve(frb_curve_t *c, double L) { if (FRB_DBL_INT_SHAPE) { return frb_shape_dbl_int_curv(c, L); } else { frb_shape_recursive(c, L); } } frb_signal_t frb_shape_recursive(frb_curve_t *c, double L) { /* The curve must be given as {ns} samples {c[0..ns-1]} uniformly spaced along the curve. The output signal is computed by the following algorithm: 0. If {ns==1} return the sequence {(0)}. 1. If {ns==2} return the sequence {(0,0)}. 2. Divide the curve into two curves {a[0..R-1]=c[0..R-1]} and {b[0..S-1]=c[R..ns-1]}, respectively with with {R = floor(ns/2)} and {S = ns-R} points. Let {r} be the split point, namely {r == c[R-1]}. 3. Convert the two curves recursively into signals {A[0..R-1]}, {B[0..S-1]}. 4. Let {u == c[0]} and {v == c[ns-1]} be the endpoints of the curve, and {theta} be the angle between the vectors {r-u} and {v-r}, measured CLOCKWISE. 5. Let {C[0..ns-1]} be a piecewise affine sequence with {C[0]=C[ns-1]=0} and {C[R-1]=L*theta*((R-1)/(ns-1))*((S-1)/(ns-1))}, where {L} is the total curve length. Add the {A} sequence to {C[0..R-1]}, and the {B} sequence to {C[R..ns-1]}. In step 4 the angle {theta} should include the correct number of full turns. The current implementation doesn't do that... */ int ns = c->nel; frb_signal_t s = frb_signal_new(ns); auto void frb_shape_rec(int i0, int i1, double L01); /* Converts the curve {c[i0..i1]} to signal {s[i0+1..i1-1]}, assuming {s[i0]} and {s[i1]} have been defined. */ void frb_shape_rec(int i0, int i1, double L01) { if (i0+1 <= i1-1) { int im = (i0 + i1) / 2; double h = - L01 * frb_angle_PQR(&(c->el[i0]), &(c->el[im]), &(c->el[i1])); s.el[im] = (s.el[i0] + s.el[i1])/2 + h/4.0; frb_shape_rec(i0,im,L01/2); frb_shape_rec(im,i1,L01/2); } } s.el[0] = 0; s.el[ns-1] = 0; frb_shape_rec(0,ns-1, L); return s; } frb_signal_t frb_shape_dbl_int_curv(frb_curve_t *c, double L) { int ns = c->nel; frb_signal_t s = frb_signal_new(ns); /* Compute the double integral of the curvature with 0 constants: */ if (ns < 1) { return s; } s.el[0] = 0; if (ns < 2) { return s; } s.el[1] = 0; double step = L/(ns-1); double sc = 0, ssc = 0; int i; for (i = 2; i < ns; i++) { double theta = frb_angle_PQR(&(c->el[i-2]), &(c->el[i-1]), &(c->el[i])); sc += theta; ssc += sc*step; s.el[i] = ssc; } /* Subtract affine interpolator of first to last sample: */ for (i = 1; i < ns-1; i++) { s.el[i] -= (i*ssc)/(ns-1); } s.el[ns-1] = 0; return s; } void frb_lsq_norm_open_shape(frb_signal_t *s) { int ns = s->nel; int i; /* Compute average {avg}: */ double sum = 0; for (i = 0; i < ns; i++) { sum += s->el[i]; } double avg = sum/ns; /* Compute slope {slp}: */ double N2 = ((double)ns)/2; double txx = 0, txy = 0; for (i = 0; i < ns; i++) { double xi = i - N2; double yi = s->el[i] - avg; txx += xi*xi; txy += xi*yi; } double slp = txy/txx; /* Subtract the affine approximation: */ for (i = 0; i < ns; i++) { double xi = i - N2; s->el[i] -= (slp*xi + avg); } } void frb_ete_norm_open_shape(frb_signal_t *s) { int ns = s->nel; /* Compute end-to-end slope {slp}: */ double DX = ((double)(ns-1))/2; double DY = s->el[ns-1] - s->el[0]; double slp = DY/DX; /* Subtract the affine approximation: */ int i; for (i = 0; i < ns; i++) { double xi = i; s->el[i] -= slp*xi; } } void frb_avg_transforms ( frb_transform_t *FF, int nft, int fmax, frb_transform_t *avgF ) { affirm(nft >= 1, "not enough signals"); affirm(avgF->nel == fmax, "bad average array length"); int isg, p; for (p = 0; p < fmax; p++) { avgF->el[p] = 0.0; } for (isg = 0; isg < nft; isg++) { frb_transform_t *Fi = &(FF[isg]); affirm(Fi->nel == fmax, "avg - inconsistent signal lengths"); for (p = 0; p < fmax; p++) { double v = Fi->el[p]; avgF->el[p] += v; } } for (p = 0; p < fmax; p++) { avgF->el[p] /= nft; } } void frb_var_transforms ( frb_transform_t *FF, frb_transform_t *avgF, int nft, int fmax, frb_transform_t *varF ) { affirm(nft >= 2, "not enough signals"); affirm(varF->nel == fmax, "bad variance array length "); affirm(avgF->nel == fmax, "bad average array length "); int isg, p; for (p = 0; p < fmax; p++) { varF->el[p] = 0.0; } for (isg = 0; isg < nft; isg++) { frb_transform_t *Fi = &(FF[isg]); affirm(Fi->nel == fmax, "var - inconsistent signal lengths"); for (p = 0; p < fmax; p++) { double v = Fi->el[p] - avgF->el[p]; varF->el[p] += v*v; } } for (p = 0; p < fmax; p++) { varF->el[p] /= (nft - 1); } } void frb_zero_mean_var_transforms ( frb_transform_t *FF, int nft, int fmax, double extraVar, frb_transform_t *varF ) { affirm(nft >= 2, "not enough signals"); affirm(varF->nel == fmax, "bad variance array length "); int isg, p; for (p = 0; p < fmax; p++) { varF->el[p] = 0.0; } for (isg = 0; isg < nft; isg++) { frb_transform_t *Fi = &(FF[isg]); affirm(Fi->nel == fmax, "var - inconsistent signal lengths"); for (p = 0; p < fmax; p++) { double v = Fi->el[p]; varF->el[p] += v*v; } } for (p = 0; p < fmax; p++) { varF->el[p] = varF->el[p]/nft + extraVar; } } frb_signal_t frb_signal_mean (frb_signal_t *a, frb_signal_t *b) { int ns = a->nel; affirm(ns == b->nel, "inconsistent lengths"); frb_signal_t m = frb_signal_new(ns); int i; for (i = 0; i <= ns-1; i++) { m.el[i] = (a->el[i] + b->el[i])/2; } return m; } frb_signal_t frb_signal_diff (frb_signal_t *a, frb_signal_t *b) { int ns = a->nel; frb_signal_t d = frb_signal_new(ns); affirm(b->nel == ns , "signal length mismatch"); int i; for (i = 0; i <= ns-1; i++) { d.el[i] = b->el[i] - a->el[i]; } return d; } int frb_midpoint (frb_match_t *mt, int i0, int i1) { int iMin, iMax; i2_t *p0 = &(mt->el[i0]), *p1 = &(mt->el[i1]); int sm = ((p0->c[0] + p0->c[1]) + (p1->c[0] + p1->c[1])) / 2; /* Binary search for {im} such that {s[im] = sm}. */ iMin = i0; iMax = i1; while (iMin < iMax) { int sMin = mt->el[iMin].c[0] + mt->el[iMin].c[1]; int sMax = mt->el[iMax].c[0] + mt->el[iMax].c[1]; double r = ((double)sm - sMin)/((double)sMax - sMin); int rf = (int)floor(r*((double)(iMax - iMin))); int im = iMin + rf; if (im >= iMax) { im = iMax-1; } int sk0 = mt->el[im].c[0] + mt->el[im].c[1]; int sk1 = mt->el[im+1].c[0] + mt->el[im+1].c[1]; affirm(sMin <= sm , "bug"); affirm(sMax >= sm , "bug"); if (sm < sk0) { iMax = im; } else if (sm > sk1) { iMin = im+1; } else if (sm - sk0 < sk1 - sm) { return im; } else { return im+1; } } affirm(iMin == iMax, "bug"); return iMin; } double frb_curve_length (frb_curve_t *c) { double s = 0.0; int i; for (i = 1; i < c->nel; i++) { s = s + r3_dist(&(c->el[i]), &(c->el[i-1])); } return s; } double frb_angle_PQR(r3_t *a, r3_t *b, r3_t *c) { affirm(a->c[2] == 0.0, "Z not zero"); affirm(b->c[2] == 0.0, "Z not zero"); affirm(c->c[2] == 0.0, "Z not zero"); r3_t u, v; r3_sub(b, a, &u); r3_sub(c, b, &v); double st = u.c[0]*v.c[1] - u.c[1]*v.c[0]; double ct = u.c[0]*v.c[0] + u.c[1]*v.c[1]; return atan2(st,ct); } frb_candidate_t frb_make_sub_cand(frb_candidate_t *cand, i2_t ctr, int nSteps) { fprintf(stderr, "making sub-candidate with %d steps\n", nSteps); affirm(nSteps % 2 == 0 , "nSteps must be even"); if ((ctr.c[0] < 0) || (ctr.c[1] < 0)) { return frb_candidate_empty; } int hSteps = nSteps / 2; frb_segment_t aSeg = cand->seg[0]; int aCtr = frb_segment_abs_index(ctr.c[0], &aSeg); int aIni = frb_imod(aCtr - hSteps, aSeg.tot); frb_segment_t bSeg = cand->seg[1]; int bCtr = frb_segment_abs_index(ctr.c[1], &bSeg); int bIni = frb_imod(bCtr - hSteps, bSeg.tot); aSeg.ini = aIni; aSeg.ns = nSteps + 1; bSeg.ini = bIni; bSeg.ns = nSteps + 1; return (frb_candidate_t) { /* seg */ {aSeg, bSeg}, /* mismatch */ 0.0, /* length */ 0.0, /* matchedLength */ 0.0, /* pm */ NULL }; } frb_match_t frb_get_matching ( frb_candidate_t *cand ) { if (cand->pm != NULL) { /* Return the original matching: */ return frb_match_unpack(cand->pm); } else { /* Create a "most perfect" matching for the two raw sequences: */ int n0 = cand->seg[0].ns, n1 = cand->seg[1].ns; return frb_match_most_perfect(n0, n1); } } double frb_mean_diff_sqr (frb_signal_t *sa, frb_signal_t *sb) { demand(sa->nel == sb->nel, "signal length mismatch"); double d2 = 0.0; int NS = sa->nel; int i; for (i = 0; i < NS; i++) { double di = sb->el[i] - sa->el[i]; d2 += di*di; } return d2/NS; } char *frb_signal_comment (char *sTag) { if (strcmp(sTag, "a") == 0) { return "first fragment's shape function"; } else if (strcmp(sTag, "b") == 0) { return "second fragment's shape function"; } else if (strcmp(sTag, "m") == 0) { return "average of the two shape functions"; } else if (strcmp(sTag, "d") == 0) { return "difference of the two shape functions"; } else { affirm(FALSE , "bug"); return ""; } } void frb_check_power_preservation(frb_signal_t *s, frb_transform_t *F) { double ss = 0.0, sF = 0.0; int i; for (i = 0; i < s->nel; i++) { ss = ss + s->el[i]*s->el[i]; } for (i = 0; i < F->nel; i++) { sF = sF + F->el[i]*F->el[i]; } double norm_s = sqrt(ss); double norm_F = sqrt(sF); double ratio = norm_s/norm_F; if (fmax(ratio - 1,1/ratio - 1) > FRB_MAX_NORM_MISMATCH) { fprintf(stderr, "norm(s) = %23.15e\n", norm_s); fprintf(stderr, "norm(F) = %23.15e\n", norm_F); fprintf(stderr, "ratio s/F = %23.15e\n", ratio); } } char *frb_ref_cand_file_comments (char *rawCandSetCmt, double maxShift, int nSamples) { char *newCmt = NULL; asprintf ( &newCmt, "%s\n\n" "%s\n" " maxShift = %8.3f pixels\n" " nSamples = %d\n", rawCandSetCmt, PROG_NAME, maxShift, nSamples ); return newCmt; } char *frb_raw_cand_comment ( char *rawCandSetCmt, int rawIndex, frb_candidate_t *rawCand, frb_curve_read_data_t **cvd, int ncv ) { /* Segment descriptions: */ char *rawCmt = frb_cand_comment(rawIndex, rawCand, cvd, ncv); char *cmt = NULL; asprintf ( &cmt, "Input candidate set:\n%s\nInput candidate:\n%s\n", rawCandSetCmt, rawCmt ); free(rawCmt); return cmt; } char *frb_raw_ref_cand_comment ( char *refCandSetCmt, int rawIndex, frb_candidate_t *rawCand, int refIndex, frb_candidate_t *refCand, frb_curve_read_data_t **cvd, int ncv ) { /* Segment descriptions: */ char *rawCmt = frb_cand_comment(rawIndex, rawCand, cvd, ncv); char *refCmt = frb_cand_comment(refIndex, refCand, cvd, ncv); char *cmt = NULL; asprintf ( &cmt, "Input candidate set:\n%s\nInput candidate:\n%sCandidate after realignment and trimming:\n%s", refCandSetCmt, rawCmt, refCmt ); free(rawCmt); free(refCmt); return cmt; } char *frb_cand_comment ( int candNum, frb_candidate_t *cand, frb_curve_read_data_t **cvd, int ncv ) { /* Segment descriptions: */ char *segCmt[2] = { NULL, NULL}; int j; for (j = 0; j < 2; j++) { frb_segment_t seg = cand->seg[j]; frb_curve_read_data_t *cvj = cvd[seg.cvx]; int fin = frb_imod(seg.ini + seg.ns - 1, seg.tot); int m = cvj->c.nel; double fm = ((double)m); double pci = ((double)seg.ini) / fm; double pcf = ((double)fin) / fm; double pc = ((double)seg.ns) / fm; asprintf ( &(segCmt[j]), " Segment [%d] from curve %4d%s\n" " %4d samples [%4d..%4d]\n" " %5.3f of the curve [%5.3f__%5.3f]\n", j, seg.cvx, (seg.rev ? " (reversed)" : ""), seg.ns, seg.ini, fin, pc, pci, pcf ); } /* Candidate description: */ char *cmt = NULL; asprintf ( &cmt, " Candidate index = %d\n%s%s", candNum, segCmt[0], segCmt[1] ); free(segCmt[0]); free(segCmt[1]); return cmt; } double *frb_compute_curve_lengths(frb_curve_read_data_t **cvd, int ncv) { double *length = malloc(ncv*sizeof(double)); int icv; for (icv = 0; icv < ncv; icv++) { if (cvd[icv] == NULL) { length[icv] = 0.0; } else { length[icv] = frb_curve_length(&(cvd[icv]->c)); } } return length; } void frb_compute_fourier_stats ( frb_transform_t *FF, /* A bunch of signals (or Fourier transforms). */ int nft, /* Number of signals given. */ int fmax, /* Number of elems per signal. */ double extraVar, /* Extra quant. variance to assume in each coefficient. */ frb_transform_t *avgF, /* (OUT) Elementwise average of input signals. */ frb_transform_t *varF, /* (OUT) Elementwise variance of input signals. */ char *outDir, /* Directory where to put the files. */ char *sTag /* Which set of signals ("ab", "m", "d"). */ ) { /* Compute average {avgF[0..fmax-1]} of all signals: */ frb_avg_transforms(FF, nft, fmax, avgF); /* Compute variance {var[0..fmax-1]} of all signals, assuming zero mean: */ frb_zero_mean_var_transforms(FF, nft, fmax, extraVar, varF); /* Write freq, observed average, and estimated variance of FT coef to disk: */ { char *estVarFileName = NULL; asprintf(&estVarFileName, "%s/%s.ftv", outDir, sTag); FILE *wr = open_write(estVarFileName); int p; for (p = 0; p < fmax; p++) { fprintf(wr, "%5d %+14.6f %18.10f\n", p+1, avgF->el[p], varF->el[p]); } fclose(wr); free(estVarFileName); } } double frb_select_curve_unit (frb_curve_t *a, double maxScaled) { double unit = 1.0/maxScaled; int i, r; for (i = 0; i < a->nel; i++) { for (r = 0; r < 3; r++) { double eps = abs(a->el[i].c[r])/maxScaled; while (unit < eps) { unit = 2.0*unit; } } } return unit; } double frb_select_signal_unit (frb_signal_t *s, double maxScaled) { double unit = 1.0/maxScaled; int i; for (i = 0; i < s->nel; i++) { double eps = abs(s->el[i])/maxScaled; while (unit < eps) { unit = 2.0*unit; } } return unit; } frb_options_t *frb_get_options(int argc, char **argv) { frb_options_t *o = malloc(sizeof(frb_options_t)); argparser_t *pp = argparser_new(stderr, argc, argv); argparser_set_usage(pp, PROG_USAGE); argparser_get_keyword(pp, "-rawCandSet"); o->rawCandSet = argparser_get_next(pp); if (argparser_keyword_present(pp, "-maxCands")) { o->maxCands = argparser_get_next_int(pp, 1, MAXINT); } else { o->maxCands = MAXINT; } if (argparser_keyword_present(pp, "-rawCandDir")) { o->rawCandDir = argparser_get_next(pp); } else { o->rawCandDir = NULL; } argparser_get_keyword(pp, "-refCandSet"); o->refCandSet = argparser_get_next(pp); argparser_get_keyword(pp, "-refCandDir"); o->refCandDir = argparser_get_next(pp); argparser_get_keyword(pp, "-curveDir"); o->curveDir = argparser_get_next(pp); argparser_get_keyword(pp, "-curveName"); o->curveName = argparser_get_next(pp); argparser_get_keyword(pp, "-band"); o->band = argparser_get_next_int(pp, 1, 4096); argparser_get_keyword(pp, "-origStep"); o->origStep = argparser_get_next_double(pp, 1.0e-6, 1.0); if (argparser_keyword_present(pp, "-curveScale")) { o->curveScale = argparser_get_next_double(pp, 1.0e-6, 1.0e6); } else { o->curveScale = 1.0; } argparser_get_keyword(pp, "-nSamples"); o->nSamples = argparser_get_next_int(pp, 1, MAXINT); if (argparser_keyword_present(pp, "-maxShift")) { o->maxShift = argparser_get_next_double(pp, 0.0, 1.0e6); } else { o->maxShift = 0.0; } o->posFormula = argparser_keyword_present(pp, "-posFormula"); o->cosWindow = argparser_keyword_present(pp, "-cosWindow"); argparser_get_keyword(pp, "-sampleErr"); o->sampleErr = argparser_get_next_double(pp, 0.0, 1.0e6); argparser_finish(pp); return o; } /* Copyright © 2005 Universidade Estadual de Campinas (UNICAMP). Authors: Helena C. G. Leitão and Jorge Stolfi. This file can be freely distributed, used, and modified, provided that this copyright and authorship notice is preserved, and that any modified versions are clearly marked as such. This software has NO WARRANTY of correctness or applicability for any purpose. Neither the authors nor their employers shall be held responsible for any losses or damages that may result from its use. */ /* COPYRIGHT AND AUTHORSHIP NOTICE Copyright © 2005 Universidade Estadual de Campinas (UNICAMP). Created by Helena C. G. Leitão and Jorge Stolfi in 1995--2005. This source file can be freely distributed, used, and modified, provided that this copyright and authorship notice is preserved in all copies, and that any modified versions of this file are clearly marked as such. This software has NO WARRANTY of correctness or applicability for any purpose. Neither the authors nor their employers shall be held responsible for any losses or damages that may result from its use. END OF NOTICE */