DIRECTORY Complex, Real USING [Round], Centerline; CenterlineImpl: CEDAR PROGRAM IMPORTS Complex, Real EXPORTS Centerline = BEGIN OPEN Centerline; pieceSize: NAT = 100; BlurredLine: TYPE = ARRAY [0..pieceSize) OF NAT; Data: TYPE = REF DataRec; DataRec: TYPE = RECORD [ blurredPiece: ARRAY [0..pieceSize) OF REF BlurredLine, pieceLine, piecePixel: INTEGER _ 0, blurriness: NAT _ 0 ]; GetPiece: PROC [h: Handle, line,pixel: INT] = BEGIN d: Data _ NARROW[h.data]; FOR i:NAT IN [0..pieceSize) DO FOR j:NAT IN [0..pieceSize) DO d.blurredPiece[i][j] _ 8*(IF i+line IN [h.startY..h.endY] AND j+pixel IN [h.startX..h.endX] THEN h.get[h.client, line+i, pixel+j] ELSE h.maxV); ENDLOOP; ENDLOOP; d.pieceLine _ line; d.piecePixel _ pixel; END; BlurPiece: PROC[d: Data] = BEGIN prevline,line,nextline: BlurredLine; FOR j:NAT IN [0..pieceSize) DO prevline[j] _ d.blurredPiece[0][j] ENDLOOP; FOR i:NAT IN [1..pieceSize-1) DO FOR j:NAT IN [0..pieceSize) DO line[j] _ d.blurredPiece[i][j] ENDLOOP; FOR j:NAT IN [0..pieceSize) DO nextline[j] _ d.blurredPiece[i+1][j] ENDLOOP; FOR j:NAT IN [1..pieceSize-1) DO d.blurredPiece[i][j] _ ( prevline[j-1] + prevline[j] + prevline[j+1] + line[j-1] + line[j] + line[j+1] + nextline[j-1] + nextline[j] + nextline[j+1])/9; ENDLOOP; prevline _ line; ENDLOOP; END; GetBlurredPiece: PROC[h: Handle, pixel,line: REAL, b: NAT] = BEGIN -- x and y are in screen coordinates, b is the blurriness d: Data _ NARROW[h.data]; line _ line - pieceSize/2; pixel _ pixel - pieceSize/2; GetPiece[h, Real.Round[line], Real.Round[pixel]]; THROUGH [1..b] DO BlurPiece[d]; ENDLOOP; d.blurriness _ b; END; BlurredSample: PROC [h: Handle, a: Complex.VEC, b: NAT] RETURNS [intensity: REAL] = BEGIN -- a is in screen coordinates, b is the blurriness d: Data _ NARROW[h.data]; IF b # d.blurriness OR NOT (a.y IN [d.pieceLine+b..pieceSize+d.pieceLine-b) AND a.x IN [d.piecePixel+b..pieceSize+d.piecePixel-b)) THEN GetBlurredPiece[h,a.x,a.y,b]; intensity _ d.blurredPiece[Real.Round[a.y]-d.pieceLine][Real.Round[a.x]-d.piecePixel]/8.0; END; DistSqr: PROC[a,b: Complex.VEC] RETURNS [REAL] = {RETURN[Complex.SqrAbs[Complex.Sub[a,b]]]}; Direction: TYPE = [0..8); delta: ARRAY Direction OF Complex.VEC = [[1,0],[1,1],[0,1],[-1,1],[-1,0],[-1,-1],[0,-1],[1,-1]]; AwayFrom: PROC[i,j: INTEGER] RETURNS [BOOLEAN] = BEGIN i _ i-j; WHILE i<-2 DO i_i+8 ENDLOOP; WHILE i>5 DO i_i-8 ENDLOOP; RETURN[i>2]; END; CurveTrace: PUBLIC PROC[h: Handle, x1,y1,x2,y2: REAL] = { b: NAT; d: Data _ NARROW[h.data]; closestApproach: REAL _ 10.0E+20; stopper: Complex.VEC; CloseEnough: PROC [a: Complex.VEC] RETURNS [BOOLEAN] = BEGIN OPEN a; IF MAX[ABS[a.x-stopper.x],ABS[a.y-stopper.y]] <= .001 THEN RETURN[TRUE]; IF x IN [x2-h.width/2..x2+h.width/2] AND y IN [y2-h.width/2..y2+h.width/2] THEN BEGIN dSqr: REAL _ DistSqr[a,[x2,y2]]; IF dSqr>closestApproach THEN RETURN[TRUE]; closestApproach _ dSqr; END; RETURN[FALSE]; END; current: Complex.VEC; cameFrom: Direction _ FIRST[Direction]; IF d=NIL THEN { d_ NEW[DataRec]; FOR i:NAT IN [0..pieceSize) DO d.blurredPiece[i] _ NEW[BlurredLine]; ENDLOOP; } ELSE d.pieceLine _ d.piecePixel _ d.blurriness _ 0; b _ Real.Round[MIN[pieceSize/2.0 - 1, h.width]]; current _ [x1,y1]; stopper _ [x2,y2]; FOR d: Direction IN Direction DO IF DistSqr[[x2,y2],Complex.Add[current,delta[d]]] > DistSqr[[x2,y2],Complex.Add[current,delta[cameFrom]]] THEN cameFrom _ d ENDLOOP; UNTIL CloseEnough[current] DO i:NAT _ 0; high: REAL _ 0; low: REAL _ 1000000; new: Complex.VEC; newd: Direction; IF i>=b THEN IF h.newPoint[h.client, current.x, current.y] THEN GOTO aborted; IF i=b THEN stopper _ current; FOR d: Direction IN Direction DO IF AwayFrom[cameFrom,d] THEN BEGIN p: Complex.VEC _ Complex.Add[current,delta[d]]; value: REAL _ BlurredSample[h,p,b]; IF value < low THEN {new _ p; low _ value; newd _ d}; IF value > high THEN high _ value; END; ENDLOOP; cameFrom _ IF newd<4 THEN newd+4 ELSE newd-4; IF high-low < .1 THEN EXIT; IF low > h.t THEN EXIT; current _ new; i _ i+1; ENDLOOP; EXITS aborted => NULL; }; END. tCenterlineImpl.mesa Copyright c 1985 by Xerox Corporation. All rights reserved. Michael Plass August 3, 1982 2:41 pm Last Edited by: Stone, November 27, 1984 3:56:37 pm PST Bier, July 21, 1987 2:04:14 pm PDT Doug Wyatt, September 5, 1985 2:44:48 pm PDT This provides an alternative method for getting a sampled curve from an image, appropriate if the image consists of a line drawing. The basic idea is to first blur the image so that the backround just reaches the center of lines of the desired width, and then to trace out the 'valley' thus defined. .csamp x y w => intensity. Returns the intensity of the blurred image at the given point. .ctrace x1 y1 x2 y2 w t n => . Traces a curve. The expected line width is w. The trace will start at (x1,y1), and will end somewhere. One possible end condition is that the trace comes close to (x2,y2) or (x1,y1), another is that n points have been sampled. A third possibility is that the sampled value exceeds the threshold t. The trace starts out in the approximate direction of (x2,y2). Here is a cache of a part of the blurred image. The piece is centered around (pixel,line) ΚΡ˜codešœ™Kšœ Οmœ1™