#ifndef frb_analyze_H #define frb_analyze_H /* Prototypes and definitions for {frb_analyze.c} */ /* Last edited on 2005-01-16 14:12:35 by stolfi */ /* Copyright © 2005 Universidade Estadual de Campinas. See note at end of file. */ #include #include #include #include #include #include #include #include #include #include #include /* A /curve/ is a string of points of {R^2}, possibly circular. A /signal/ is a list of real values. A /segment/ is a substring of a curve. A /candidate/ is a pair of segments. */ typedef struct frb_options_t { /* Candidate set data: */ char *rawCandSet; /* Filename of input (raw) cands (minus ".can" extension). */ char *refCandSet; /* Filename of output (refined) cands (minus ".can" extension). */ /* Data for individual candidates: */ char *rawCandDir; /* Top level directory for output raw candidate files, or NULL. */ char *refCandDir; /* Top level directory for output refined candidate data. */ /* Curve data: */ char *curveDir; /* Top-level directory for fragment data. */ char *curveName; /* Name of curve files (minus ".flc" extension). */ int band; /* Nominal relative band width for file names. */ double origStep; /* Nominal sampling step length for band 1 (mm). */ double curveScale; /* Scale factor to apply to all curves. */ /* Candidate normalization parameters: */ int maxCands; /* Number of candidates to consider. */ double maxShift; /* Max shift to try in re-alignment (pixels). */ int nSamples; /* Num samples to use in each candidate. */ bool posFormula; /* TRUE uses the always-positive formula. */ bool cosWindow; /* TRUE uses cosine windowing before Fourier transform. */ double sampleErr; /* Intrinsic standard deviation of samples. */ } frb_options_t; /* Maximum quantization {unit} for output files {= 2^24}. */ #define FRB_MAX_SCALED (256.0*256.0*256.0) /* Coordinate quantization unit for curve files. */ #define FRB_UNIT_FOR_COORD ((25.4/300)/16.0) /* Quantization unit for shape files. */ #define FRB_UNIT_FOR_SHAPE (FRB_UNIT_FOR_COORD/4.0) /* Max relative difference between signal norm and Fourier norm: */ #define FRB_MAX_NORM_MISMATCH (1.0e-14) /* FALSE uses the recursive shape, TRUE uses the double integral of curvature */ #define FRB_DBL_INT_SHAPE (TRUE) typedef frb_signal_t frb_transform_t; /* An {frb_transform_t} is a Sine transform of a shape function. If the original signal {s} had samples {s[0..ns-1]}, then the transform {F} has coefficients {F[0..ns-2]} where {F[p]} has frequency {p+1} over the doubled period {2*ns}. */ typedef frb_signal_t frb_spectrum_t; /* An {frb_spectrum_t} contains the power spectrum of a signal. If the original signal {s} had samples {s[0..ns-1]}, then the spectrum {F} has coefficients {F[0..ns-2]} where {F[p]} has frequency {p+1} over the doubled period {2*ns}. */ /* INTERNAL PROTOTYPES */ 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. */ ); /* Takes a set of candidates {cd}. Writes the two curves of each candidate and their shape functions to disk, to the directory "{dir}/{NNNNNN}" where {NNNNNN} is the candidate's index {k}, starting from 0. The file names are "{TAG}.{EXT}" where {TAG} is "a" or "b", and {EXT} is ".flc" for {frb_curve_t}, ".fsh" for shape functions. */ 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, /* Top directory for output files of refined 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. */ ); /* Takes a set of candidates {cd}, standardizes them to {ns} samples, computes the corresponding signals {a,b,m,d}, and returns the Fourier transforms and power spectra of all those signals Standardization includes realigning them by shifting at most {maxShift} steps, and trimming the two segments to exactly {ns} samples each. The signal {m} is the mean {(a+b)/2}, and {d} is the difference signal {b-a}. Candidates that are too short are discarded; returns in {refCandNum} the number of accepted candidates. The two curves of each accepted candidate, after realignment and trimming, are written to disk, together with the four signals, transforms, and corresponding power spectra. All files pertaining to the same candidate are written to the directory "{dir}/{NNNNNN}" where {NNNNNN} is the candidate's index {k} among the accepted ones, in "%06d" format, starting from 0. The file names are "{TAG}.{EXT}" where {TAG} is "a", "b", "m", or "d", and {EXT} is ".flc" for {frb_curve_t}, ".fsh" for shape functions, ".fft" for Fourier transforms, and ".fpw" for unfolded power spectra. The Fourier transforms of the {a,b,m,d} signals for candidate {k} are returned in the arrays {SS[2*k],SS[2*k+1],MM[k],DD[k]}. Since the array {SS} contains both the {a} and {b} signals, it contains {2*refCandNum} transforms. The other arrays have {refCandNum} transforms each. The procedure allocates storage for the elements of the transforms. Then computes and returns the corresponding shape functions {sa,sb}, Storage for the signals {sa,sb,sm,sd} is allocated by the procedure. */ frb_candidate_t frb_standardize_candidate ( frb_candidate_t *cand, /* The original candidate. */ frb_curve_read_data_t **cvd, /* Data for relevant curves. */ 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. */ ); /* Let {a,b} be the two curves that constitute candidate {cand}. This procedure rotates and translates curve {a} so as to optimize the match with curve {b}. Then it extracts two matching segments of prescribed length from the two segments, and returns them as a candidate. If there aren't enough samples in the candidate, returns an trivial candidate with only one sample. */ 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}. */ ); /* Given two curves {a,b} from a candidate, and the coresponding sample matching {mt}, identifies the best sub-candidate whose two segments have exactly {nSteps+1} samples. More precisely, returns the two indices {ia,ib} such that the average square difference between the shapes sub-segment {a[ia-h..ia+h]} with {b[ib-h..ib+h} minimizes the, where {h = nSteps/2}. (Note that {nSteps} must be even). The centers {ia,ib} are always some pair {ma,mb} from the matching {mt} shifted by at most {maxAdjust} steps, i.e. {ia = ma + floor(s/2)}, {ib = mb - ceil(s/2)}, where {abs(s) <= maxAdjust}. However the matching itself is not used when comparing two sub-candidates; instead, the points are paired one-by-one. This policy is justified by the observation that the shape functions will be computed independently in the fragment reassembly procedure. */ 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 ); /* Evaluates the discrepancy between the shape functions of segments {a[ac-h..ac+h]} and {b[bc-h..bc+h]}, where {h=nSteps/2}, and {ac,bc} are {aMid,bMid} shifted by {shift} steps. More precisely {ac = aMid + floor(shift/2)} and {bc = bMid - ceil(shift/2)}. If the mean squared difference between those two shape functions is less than {d2Best}, updates {d2Best}, saves {shift} in {shiftBest}, and saves {(ac,bc)} in {ctrBest}. Otherwise leaves those variables alone. */ 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). */ ); /* Writes the curve {c} to disk, as "{outDir}/{cvTag}.flc". The comment text will be {candCmt} plus "side = {cvTag}". Also returns in {*s} its shape function. Storage for the shape function is allocated by this procedure. */ 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. */ ); /* Writes to disk the signal {s}. If {F} is not NULL, computes the Fourier transform {F} of the given signal {s} and its power spectrum (not returned), and writes them to disk, too. The file names are "{outDir}/{sTag}.{EXT}" where {EXT} is ".fsh" for the signal itself, ".fft" for its Fourier transform, and ".fpw" for its power spectrum. The comment text will be {candCmt} followed by "signal = "{sTag}" ({explanation})", plus "fourier transform" or "power spectrum" as applicable. */ frb_signal_t frb_shape_from_curve(frb_curve_t *c, double L); /* Converts an open 2D curve {c} into a sequence {s} of samples that can be used as a periodic "signal" in the Hartley-Shannon theorem. Assumes that the total curve length is {L} and that the samples are equally spaced along the curve. If {FRB_DRBL_INT_SHAPE} is TRUE, uses the double integral of curvature as signal, else uses the recursive formula from Helena's thesis. */ frb_signal_t frb_shape_recursive(frb_curve_t *c, double L); /* Converts an open 2D curve {c} into a sequence {s} of samples that can be used as a periodic "signal" in the Hartley-Shannon theorem. Assumes that the total curve length is {L} and that the samples are equally spaced along the curve. Ignores the Z component of the input samples. Uses the recursive algorithm given in HCGL's thesis. */ frb_signal_t frb_shape_dbl_int_curv(frb_curve_t *c, double L); /* Converts an open curve {c} into a sequence {s} of samples that can be used as a periodic "signal" in the Hartley-Shannon theorem. Assumes that the total curve length is {L} and that the samples are equally spaced along the curve. Ignores the Z component of the input samples. Uses the double integral of the curvature function {\kappa(t)}, with integration weights chosen so that {s} begins and ends with zero. */ void frb_lsq_norm_open_shape(frb_signal_t *s); /* Normalizes the shape function {s} of some open curve, by subtracting its least-squares affine approximation. */ void frb_ete_norm_open_shape(frb_signal_t *s); /* Normalizes the shape function {s} of some open curve, by subtracting the end-to-end straight line. */ frb_match_t frb_get_matching ( frb_candidate_t *cand ); /* Obtains a non-null matching for the candidate {cand}. It is either {cand}'s built-in matching, or the ``most perfect'' one. */ double frb_mean_diff_sqr (frb_signal_t *sa, frb_signal_t *sb); /* Returns the average distance (squared) between coresponding samples of the two signals (which must have the same length). */ int frb_midpoint (frb_match_t *mt, int i, int j); /* Finds an index {k} such that {s[k]} is approximately {(s[i]+s[j])/2} where {s[r] = (mt[r][0] + mt[r][1])}. */ double frb_curve_length (frb_curve_t *c); /* Compute the lenngth of the curve {c}, interpreted as a polynomial. */ double frb_select_curve_unit (frb_curve_t *a, double maxScaled); /* Selects a suitable quantization unit for the curve {a}. The unit will be a power of two, not smaller than {1/maxScaled} (which itself must be a power of two).*/ double frb_select_signal_unit (frb_signal_t *s, double maxScaled); /* Selects a suitable quantization unit for the signal {s}. The unit will be a power of two, not smaller than {1/maxScaled} (which itself must be a power of two).*/ void frb_avg_transforms ( frb_transform_t *FF, int nft, int fmax, frb_transform_t *avgF ); /* Given a list {FF[0..nft-1]} of {frb_transform_t}s, all of them with {fmax} coefficients, stores in {avgF[i]} the average of {FF[0..nft-1][i]}. */ void frb_var_transforms ( frb_transform_t *FF, frb_transform_t *avgF, int nft, int fmax, frb_transform_t *varF ); /* Given a vector {FF[0..nft-1]} of {frb_transform_t}s, all of them with {fmax} coefficients, and their sample-wise average {avgF}, stores in each {varF[i]} the variance of {FF[0..nft-1][i]}. */ void frb_zero_mean_var_transforms ( frb_transform_t *FF, int nft, int fmax, double extraVar, /* Intrinsic quantization error in each sample. */ frb_transform_t *varF ); /* Given a vector {FF[0..nft-1]} of {frb_transform_t}s, all of them with {fmax} coefficients, stores in each {varF[i]} the variance of {FF[0..nft-1][i]}. Assumes that the means are all zeros. Also adds {extraVar} to each coeff, e.g. to account for quantization noise. */ frb_signal_t frb_signal_mean (frb_signal_t *a, frb_signal_t *b); /* Computes the average {(a+b)/2}of two signals {a,b}. */ frb_signal_t frb_signal_diff (frb_signal_t *a, frb_signal_t *b); /* Computes the difference {b-a} of two signals {a,b}. */ double frb_angle_PQR(r3_t *a, r3_t *b, r3_t *c); /* Computes the signed external angle between the vectors {b-a} and {c-b}. Assumes that the three points lie on the plane {Z==0}. */ frb_candidate_t frb_make_sub_cand(frb_candidate_t *cand, i2_t ctr, int nSteps); /* Returns a sub-candidate of {cand} with two segments of length {nSteps} centered on samples {ctr[0]} and {ctr[1]}. (relative to the ends of {cand}). If {ctr = (0,0)}, returns an {Empty} candidate. */ char *frb_signal_comment (char *sTag); /* Returns an explanation for the signal, based on its {sTag} ("a", "b", "m", or "d"). */ void frb_check_power_preservation(frb_signal_t *s, frb_transform_t *F); /* Checks Parseval's theorem on a signal {s} and its Fourier transform {F}: */ char *frb_ref_cand_file_comments (char *oldCmt, double maxShift, int nSamples); /* Creates a comment text for the standardized candidate file created by {frb_refine_candidates}. */ char *frb_raw_cand_comment ( char *rawCandSetCmt, int rawIndex, frb_candidate_t *rawCand, frb_curve_read_data_t **cvd, int ncv ); /* Creates a comment text for all files derived from a given raw candidate. Argument {rawCand} is the candidate; {rawCandNum} is its index in the raw candidate file. The {rawCandSetCmt} is the comment text read from the raw candidate's file. The curve data table {cvd[0..ncv-1]} is used to obtain data on the candidate's curves. */ char *frb_raw_ref_cand_comment ( char *candSetCmt, int rawCandNum, frb_candidate_t *rawCand, int refCandNum, frb_candidate_t *refCand, frb_curve_read_data_t **cvd, int ncv ); /* Creates a comment text for all files derived from a given refined candidate. Arguments {rawCand} and {refCand} are the candidate respectively before and after realignment and trimming; {rawCandNum} and {refCandNum} are their indices in the raw and refined candidate sets, respectively. The {refCandSetCmt} is the comment text for the refined candidate set. The curve data table {cvd[0..ncv-1]} is used to obtain data on the candidate's curves. */ char *frb_cand_comment ( int candNum, frb_candidate_t *cand, frb_curve_read_data_t **cvd, int ncv ); /* Creates a comment text describing the essential parameters for the two segments of a candidate {cand}, namely: the curve index, the starting sample, the sample count, and the reversal falg. Argument {candNum} should be the index of {cand} in some candidate set. The curve data table {cvd[0..ncv-1]} is used to obtain data on the candidate's curves. */ double *frb_compute_curve_lengths(frb_curve_read_data_t **cvd, int ncv); /* Returns a vector of {length} such that {legth[i]} is the total length of the curve {cvd[i].c}. */ void frb_compute_fourier_stats ( frb_transform_t *FF, /* A bunch of Fourier transforms. */ int nft, /* Number of transforms given. */ int fmax, /* Number of coeffs per transform. */ double extraVar, /* Extra quant. variance to assume in each coefficient. */ frb_transform_t *avgF, /* (OUT) Coeff-wise average of input transforms. */ frb_transform_t *var, /* (OUT) Coeff-wise variance of input transforms. */ char *outDir, /* Directory where to put the files. */ char *sTag /* Which set of transforms ("ab", "m", "d"). */ ); /* Estimates the average and variance of each coefficient over a set of Fourier transforms {FF[0..nft-1]}. All the given transfors must have the same number of coefficients {fmax}, except for signals with zero elements, which are ignored. The variances are computed assuming that the true average of each coeff is 0.0. The variance of each coefficient is incremented with the variance {extraVar}, e.g. to account for quantization error. Also writes the estimated means and variances to the file "{outDir}/{sTag}.ftv" */ frb_options_t *frb_get_options(int argc, char **argv); /* Parses the command line options. */ #endif /* 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 */