INTERFACE PZSymbolChain; (* Discretized curvature graphs *) IMPORT Rd, Wr; IMPORT PZSymbol, PZMatch; TYPE Symbol = PZSymbol.T; T = ARRAY OF Symbol; CostMatrix = PZMatch.CostMatrix; PROCEDURE Write( wr :Wr.T; cmt: TEXT; READONLY c: T; length: LONGREAL; epsilon, delta: LONGREAL; ); (* Writes a coded curvature chain "c" and the encoding parameters "idealStep", "epsilon", "delta" to "wr". *) TYPE ReadData = RECORD cmt: TEXT; samples: CARDINAL; length: LONGREAL; epsilon, delta: LONGREAL; c: REF T; END; PROCEDURE Read(rd :Rd.T; headerOnly: BOOLEAN := FALSE): ReadData; (* Reads a coded curvature chain and associated encoding parameters from "rd". If "headerOnly=TRUE", reads only the parameters, and leaves the "c" field as NIL. *) PROCEDURE ReadAll( puzzle: TEXT; band: CARDINAL; extension: TEXT; READONLY sel: ARRAY OF BOOLEAN; headerOnly: BOOLEAN := FALSE; ): REF ARRAY OF ReadData; (* Returns a vector "r" such that "r[k]" is the ReadData for curve "k", if "sel[k] = TRUE". Otherwise "r[k]" is an empty data record. The data is read from file "KKKK/NNN-KKKK-fBBBEEE", where "NNN" is the "puzzle" name, "KKKK" is the curve number "k" (4 digits, zero padded), "BBB" is the "band" number (3 digits, zero padded), and "eee" is the given "extension". If "headerOnly" is TRUE, reads only the parameters, and leaves the "c" field as NIL. *) PROCEDURE Match( READONLY a: T; READONLY b: T; maxDist: LONGREAL; removeUnmatchedEnds: BOOLEAN; VAR (*OUT*) avgCost: LONGREAL; VAR (*OUT*) nMatched: CARDINAL; VAR (*OUT*) match: REF PZMatch.T; ); (* Finds (by dynamic programming) a minimum-cost monotone matching "match" between the chains "a" and "b". The chains are interpreted as graphs of curvature (or some other attribute of a curve) as a function of some common parameter, sampled at equally spaced steps, and quantized into "PZSymbol.T" values. Each step of one graph is matched either to one step or to a single sample of the opposite chain. Specifically, the sample "a[match[k][0]]" is paired with sample "b[match[k][1]]", for all "k"; and "match[k]" increases by either 0 or 1 in each coordinate. The cost of matching a step to a single sample is "maxDist/2", irrespective of the corresponding sample values. The cost of matching two steps is basically the root mean square value of "a(t) - b(t)", where "a(t)" and "b(t)" interpolate linearly between the two corresponding samples. However, a penalty term is added whenever a chain value "a[k]" or "b[k]" is less than "minValue". Also, the distance is clipped to a maximum of "maxDist" in any case. The average cost "avgCost" of the matching is then the root mean square of those individual step costs. The procedure returns in "nMatched" the number of steps whose cost is strictly less than its maximum cost". *) PROCEDURE OutMatch( READONLY a: T; READONLY b: T; loc: LONGREAL; align: LONGREAL; maxShift: LONGREAL; maxDist: LONGREAL; cutDist: LONGREAL; step: LONGREAL; minChainSteps: CARDINAL; VAR (*OUT*) mismatch: LONGREAL; VAR (*OUT*) nMatched: CARDINAL; VAR (*OUT*) match: REF PZMatch.T; VAR (*OUT*) xCenter, yCenter: CARDINAL; VAR (*OUT*) minAvgDist: REF ARRAY OF LONGREAL; VAR (*WORK*) XYCost: REF CostMatrix; ); (* Finds (by bidirectional dynamic programming) a minimum-mismatch monotone matching "match" between the chains "a" and "b". The chains are interpreted as graphs of curvature (or some other attribute of a curve) as a function of some common parameter, sampled at equally spaced steps, and quantized into "PZSymbol.T" values. Each step of one chain is matched either to one step or to a single sample of the opposite chain. Specifically, the sample "a[match[k][0]]" is paired with sample "b[match[k][1]]", for all "k"; and "match[k]" increases by either 0 or 1 in each coordinate. We will denote by "totChainSteps" the total number of steps in the matched portion of the two chains, that is "(match[m-1][0]-match[0][0]) + (match[m-1][1]-match[0][1])". The match will include exactly one `central' pair "match[kc]=(ia,ib)" with "ia+ib = ROUND(loc)". The difference "ia-ib", called the `alignment' of the match, will be approximately "align"; the "maxShift" parameter specifies the maximum amount by which the two quantities are allowed to differ. (The procedure will fail if "loc" and "align" are outside the obvious bounds). The cost of matching a step to a single sample is "maxDist^2/2", irrespective of the corresponding sample values. The cost of matching two steps is the mean square value of "a(t) - b(t)", where "a(t)" and "b(t)" interpolate linearly between the two corresponding samples.. Also, the step cost is clipped to a maximum of "maxDist^2" in any case. The `mismatch' of a match is defined as "intgCostSqr - totLength*cutDist^2" where "intgCostSqr" is the sum of the step costs (each clipped to "maxDist^2" as explained above) times the step size "step"; and "totLength" is the mean length of the matched curves, i.e. "step * totChainSteps/2". However, if "totChainSteps" is less than "minChainSteps", the mismatch is "+oo" by definition. The procedure also returns in "nMatched" the number of steps whose cost is strictly less than "maxDist^2". The procedure also returns in "minAvgDist[k]", for "k" in "[0..na+nb-2]", the square root of the average step cost, over all matches with "totChainSteps = k". This table can be used to choose suitable values for the "cutDist" parameter. The parameters "xCenter", "yCenter", and "XYCost" are as in "PZMatch.OutMatch". *) PROCEDURE Trim(READONLY c: T; start, length: CARDINAL): REF 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 ReverseAndComplement(VAR c: T); (* Reverses the chain back-to-front and negates all elements. *) END PZSymbolChain.