INTERFACE PZLRChain;

(* Sequences (possibly periodic) of LONGs --- times, labels, curvatures, etc. *)
(* Last edited on 1999-11-15 00:03:41 by hcgl *)

IMPORT Rd, Wr;
IMPORT PZMatch, PZSegment, PZCandidate;
FROM PZTypes IMPORT LONG, LONGS, INT, NAT, BOOL, BOOLS;

TYPE 
  T = LONGS;
   (*
      A "PZLRChain.T" is a sequence,open or closed, of arbitrary LONG
      values.  If closed, the elements may be samples from a periodic
      function, or from the integral of a periodic function.  *)

(* BASIC MANIPULATION *)

(*
  The "DoXXX" procedures below are analogous to the "XXX" 
  procedures, except that the result is returned in an array
  provided by the client (which must have the correct size). *)

PROCEDURE Trim(READONLY c: T; start, length: NAT): REF T;
PROCEDURE DoTrim(READONLY c: T; start, length: NAT; VAR x: T);
  (*
    Returns a new chain that is a copy of elements from "c[start]"
    to "c[start+length-1]".  Assumes the chain is periodic, i.e.
    "c[i+n]=c[i]" for all "i", where "n=NUMBER(c)". *)
 
PROCEDURE Reverse(VAR c: T);
  (*
    Reverses the chain back-to-front. *)

PROCEDURE Complement(VAR c: T);
  (*
    Reverses the chain back-to-front and negates all elements. *)

PROCEDURE ExtractSegment(READONLY c: T; s: PZSegment.T; curvature: BOOL): REF T;
PROCEDURE DoExtractSegment(READONLY c: T; s: PZSegment.T; curvature: BOOL; VAR x: T);
  (*
    Extracts the specified segment of curve "c", assumed periodic.

    If "s.rev" is TRUE, also reverses it; in that case, if "curvature" is 
    TRUE, also negates all elements. *)

(* INTEGRAL-PERIODIC FUNCTIONS *)

(*
  The procedures in this section interpret a chain "c" as 
  a continuous function "c(x)" that is the integral of some 
  non-negative periodic function "f(x)" with period "m = NUMBER(c)".
  
  Specifically, the procedures assume that 
    
    (1) "c[i]" is the integral of "f(x)" from an arbitrary
        parameter "x = x0" to parameter "x = i"; 

    (2) "stride" is the integral of "f(x)" over a whole period, 
        so that "c(x + m) = f(x) + stride", for any "x"; and

    (3) "f(x)" is linear between successive integer values of 
        the argument "x".
*)

PROCEDURE Delta(READONLY c: T; stride: LONG; ini, fin: INT): LONG;
  (*
    Returns "c(fin) - c(ini)", where the chain "c" is implicitly extended
    as explained above. *)

PROCEDURE ValueFromArg(READONLY c: T; stride: LONG; x: LONG): LONG; 
  (*
    Returns "c(x)"; that is, a value "y" such that
    "c[floor(x)] <= y <= c[ceiling(x)]", interpolating linearly
    between these two points.  The chain "c" is implicitly 
    extended as explained above. *)

PROCEDURE ArgFromValue(READONLY c: T; stride: LONG; y: LONG): LONG; 
  (* 
    Returns a fractional argument "x" such that "c(x) = y";
    that is, such that "c[floor(x)] <= y <= c[ceiling(x)]",
    with linear interpolation between these two points.
    The chain "c" is implicitly extended as explained above. *)
    
PROCEDURE ValuesFromArgs(
    READONLY c: T; 
    stride: LONG; 
    READONLY x: LONGS;
    VAR y: LONGS;
  );
  (*
    Sets "y[i] := ValueFromArg(c, stride, x[i])" for all "i". *)

PROCEDURE ArgsFromValues(
    READONLY c: T; 
    stride: LONG; 
    READONLY y: LONGS;
    VAR x: LONGS;
  ); 
  (* 
    Sets "x[i]" to "ArgFromValue(c, stride, y[i])" for every i,
    but faster if "y" is sorted. *)
    
PROCEDURE ValueFromValue(
    READONLY a: T; aStride: LONG; 
    READONLY b: T; bStride: LONG; 
    ya: LONG;
  ): LONG; 
  (*
    Finds the value "yb" of function "b(x)" for an argument "x" such that
    the function "a(x)" has value "ya". The chains "a" and "b" 
    are implicitly extended as explained above. *)

PROCEDURE ArgFromArg(
    READONLY a: T; aStride: LONG; 
    READONLY b: T; bStride: LONG;
    xa: LONG;
  ): LONG; 
  (*
    Finds an argument "xb" such that "b(xb) = a(xa)", where
    "xa" is given. The chains "a" and "b" are implicitly extended as 
    explained above. *)
    

(* MAPPINGS BETWEEN TWO VERSIONS OF CURVES *)

(*
  The following procedures map sample indices and related objects
  (segments, candidates, matchings, etc.), relative to one or more
  curves, to the corresponding objects on different versions of the
  same curves (presumably filtered at different scales and/or
  resampled with different times).
  
  The procedures assume that corresponding points of two versions of
  the same curve have the same parameter "t".  They assume that sample
  "i" of each curve has parameter value "tOld[i]" or "tNew[i]",
  respectively; and that both versions are periodic, with same
  period "stride". *)

PROCEDURE MapSegment(
    READONLY sOld: PZSegment.T;
    READONLY tOld: T;
    READONLY tNew: T;
    stride: LONG;
  ): PZSegment.T;
  (*
    Maps a segment of a sampled chain to another version of the same
    chain. *)
  
PROCEDURE MapMatch(
    READONLY mOld: PZMatch.T;
    READONLY sOld: PZSegment.Pair;
    READONLY t0Old, t1Old: T;
    READONLY sNew: PZSegment.Pair;
    READONLY t0New, t1New: T;
    stride: ARRAY [0..1] OF LONG;
  ): REF PZMatch.T;
  (*
    Translates a partial matching "mOld", that defines a
    correspondence between two curves "cOld[0]", "cOld[1]", to a
    matching "mNew" between new versions "cNew[0]" and "cNew[1]" of
    those two curves.
    
    The input matching is assumed to be relative to segments "sOld[j]"
    of curve "cOld[j]", for "j=0,1".  The new matching will be
    relative to the segments "sNew[j]", and trimmed to fit inside
    them.
    
    Whenever a step of "mOld" skips several samples of the new curve,
    extra steps are inserted, by linear interpolation rounded to
    integers. *)
    

PROCEDURE MapPackedMatch(
    pm: REF PZMatch.PackedT;
    READONLY sOld: PZSegment.Pair;
    READONLY t0Old, t1Old: T;
    READONLY sNew: PZSegment.Pair;
    READONLY t0New, t1New: T;
    stride: ARRAY [0..1] OF LONG;
  ): REF PZMatch.PackedT;
  (*
    If "pm" is NIL, returns NIL; otherwise is equivalent
    to "MapMatch", in packed format. *)
  
PROCEDURE MapCandidate(
    READONLY cOld: PZCandidate.T;  (* Candidate on old curves. *)
    READONLY t0Old, t1Old: T;      (* Sampling times of old curves. *)
    READONLY t0New, t1New: T;      (* Sampling times of new curves. *)
    stride: ARRAY [0..1] OF LONG;  (* Period of "{t0Old,t1Old}" and "{t0New,t1New}". *)
    stepNew: ARRAY [0..1] OF LONG; (* Sampling step of new curves. *)
    extra: ARRAY [0..1] OF INT;    (* Extra steps to add to each end of each segment *)
  ): PZCandidate.T;
  (*
    Maps the candidate "cOld" from old curves to new curves.  Segment
    "j" is mapped to the new curves, then extended by "extra[j]" steps
    in both directions.  (If "extra[j]" is negative, the ends are trimmed 
    by that amount).  The matching "cOld.pm" is converted with
    "MapPackedMatch". *)
    
(* CHAIN MATCHING BY DYNAMIC PROGRAMMING *)
    
(*
  The procedures "FindBestMatch" and "RefineMatch" look for a 
  monotone matching "mt" (a "PZMatch.T") between two chains that 
  minimizes some measure of the distance between corresponding samples.

  See "PZMismatch" for the relevant concepts.  These procedures assume
  that the two chains are sampled at uniform intervals of given size
  "step".  Therefore, the metric "h(a,i1,i2)" is assumed to be
  "step*(i2-i1)".  The sample distance "d(a[r], b[s])" is simply the
  absolute difference "|a[r]-b[s]|".
    
  The procedures return in "length" the total length "Len(mt)" of the
  matching (average of the lengths of the two chain segments spanned
  by "mt").  They also return in "lengthMatched" the total length of
  the matching steps whose mean width "dist(S)" was strictly less than
  "maxDist".

  The procedures use internally a working array with "NUMBER(a)" rows
  and "NUMBER(b)" columns.  The client may optionally provide an array
  "rCost", at least this big, which will be automatically (re)
  allocated if omitted or too small. *)

PROCEDURE FindBestMatch(
    READONLY a: T;
    READONLY b: T;
    step: LONG;
    maxDistSqr: LONG;
    skipDistSqr: LONG;
    removeUnmatchedEnds: BOOL;
    VAR (*OUT*) mt: REF PZMatch.T;
    VAR (*OUT*) avgDisc: LONG;
    VAR (*OUT*) length: LONG;
    VAR (*OUT*) matchedLength: LONG; 
    VAR (*WORK*) rCost: REF PZMatch.CostMatrix;
  ); 
  (*
    Computes (by dynamic programming) a complete monotone matching
    "mt" between two open curves "a" and "b" that minimizes their
    integrated squared dicrepancy "IntgDiscSqr(mt)".
    
    The procedure returns in "avgDisc" the average discrepancy 
    (in the root mean square sense). 
    
    If "removeUnmatchedEnds" is true, the procedure removes any
    initial or final steps "s" whose distance "dist(s)" is equal to
    "maxDist".  Otherwise the matching "mt" will completely cover the
    two chains. *)
    
PROCEDURE RefineMatch(
    READONLY a: T;
    READONLY b: T;
    step: LONG;
    READONLY mtOld: PZMatch.T;
    maxAdjust: NAT;
    critDistSqr: LONG;
    maxDistSqr: LONG;
    skipDistSqr: LONG;
    VAR (*OUT*) mt: REF PZMatch.T;
    VAR (*OUT*) mismatch: LONG;
    VAR (*OUT*) length: LONG;
    VAR (*OUT*) matchedLength: LONG; 
    VAR (*OUT*) minAvgDist: LONGS;
    VAR (*WORK*) rCost: REF PZMatch.CostMatrix;
  ); 
  (*
    Finds (by bidirectional dynamic programming) a partial monotone
    matching "mt" between the polygonal chains "a" and "b", that is
    a refinement of an `input matching' "mtOld", and minimizes
    the mismatch "Mis(mt)".  
    
    See "PZMatch.Refine" for an explanation of the refinement concept,
    and the meaning of "mtOld" and "maxAdjust".  See "PZMatching.i3"
    for the definition of the mismatch "Mis(mt)" and the meaning of
    the parameters "critDistSqr" and "maxDistSqr".
    
    The value of "Mis(mt)" is returned in "mismatch".
    
    The procedure returns in "minAvgDist[K]", for "K" in
    "[0..na+nb-2]", the average width "Dist(mtK)" of the optimum match
    "mtK" among all matches with total step count "K".  (Note that, if
    the step count is fixed, the "critDist" term does not affect the
    optimality of the match.)  *)
  
(* INPUT/OUTPUT *)

PROCEDURE Write(wr: Wr.T; READONLY cmt: TEXT; READONLY c: T; stride: LONG; unit: LONG);
  (*
    Writes chain "c" to "wr", prefixed with comment "cmt" and the given "stride".
    The samples will be written as integer multiples of the given "unit". *)

TYPE
  ReadData = RECORD 
      cmt: TEXT;     (* Comments *)
      samples: NAT;  (* Number of samples in chain. *)
      c: REF T;      (* Times, values, etc. *)
      stride: LONG;  (* Period, total length, etc; 0 if not applicable. *)
      unit: LONG;    (* Unit used when recording the samples *)
    END; 
 
PROCEDURE Read(rd: Rd.T; headerOnly: BOOL): ReadData;
  (*
    Reads a chain from "rd".  If "headerOnly=TRUE", reads only the
    parameters, and leaves the "c" field as NIL. *)
    
TYPE
  ReadAllData = RECORD
      chain: REF ARRAY OF ReadData;
      unitMin: LONG;      (* Minimum quantization unit. *)
      unitMax: LONG;      (* Maximum quantization unit. *)
      cmt: TEXT;          (* Comment of first chain, if any. *)
    END;

PROCEDURE ReadAll(
    prefix: TEXT; 
    band: NAT;
    extension: TEXT;
    READONLY sel: BOOLS;
    headerOnly: BOOL;
    dir: TEXT := ".";
  ): ReadAllData;
  (*
    Reads a set of numbered chains, returns a "ReadAllData" record
    "r". Chain number "i" is read if and only if "sel[i] = TRUE", and
    its "ReadData" is stored in "r.chain[i]"; otherwise "r.chain[i] "
    is set to a record with null "c" field.
    
    The data is read from file "DDD/KKKK/PPPBBBEEE", where "DDD" is
    the directory "dir", "KKKK" is the curve number "k" (4 digits,
    zero padded), "PPP" is the given "prefix", "BBB" is the "band"
    number (3 digits, zero padded), and "EEE" is the given
    "extension".
    
    If "headerOnly" is TRUE, only the header of each file is read;
    the "c" fields are all set to NIL.
    
    The range of quantization "unit"s of the chains that were read is
    returned in "r.unitMin", "r.unitMax".  The comment of the first chain
    read, plus the call arguments, are stored in "r.cmt". *)
    

END PZLRChain.
(*
  Copyright © 2001 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 chall be held
  responsible for any losses or damages that may result from its use.
*)