DIRECTORY Complex, Basics USING [LowHalf], Real USING [RoundI], Centerline; CenterlineImpl: CEDAR PROGRAM IMPORTS Complex, Basics, Real EXPORTS Centerline = BEGIN OPEN Centerline; NarrowToNat: PROC [n: INT] RETURNS [NAT] = BEGIN IF n<0 THEN n_0; IF n>LAST[NAT] THEN n_LAST[NAT]; RETURN[Basics.LowHalf[n]]; END; 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.RoundI[line], Real.RoundI[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.RoundI[a.y]-d.pieceLine][Real.RoundI[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.RoundI[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. æCenterlineImpl.mesa Michael Plass August 3, 1982 2:41 pm Last Edited by: Stone, November 27, 1984 3:56:37 pm PST 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) Êî˜Jšœ™Jšœ%™%J™7J˜Jšœ¬™¬JšœZ™ZJšœŠ™ŠJ˜šÏk ˜ J˜Jšœœ ˜Jšœœ ˜J˜ J˜—šœœ˜Jšœ˜Jšœ ˜Jš œ ˜—J˜J˜š Ïn œœœœœ˜*Jš˜Jšœœ˜Jš œœœœœœ˜ Jšœ˜Jšœ˜J˜—Jšœ/™/Jšœ œ˜Jš œ œœœœ˜0Jšœœœ ˜šœ œœ˜Jšœœœœ ˜7Jšœœ˜#Jšœ œ˜J˜—šžœœœ˜-Jš˜Jšœ œ ˜šœœœ˜šœœœ˜š œœœœ œ˜[Jšœ!˜%Jšœ ˜ —Jšœ˜—Jšœ˜—J˜J˜Jšœ˜J˜—šž œœ ˜Jš˜J˜$Jš œœœœ$œ˜Jšœœœ˜ Jš œœœœ œ˜FJš œœœœ&œ˜Lšœœœ˜ ˜˜-J˜)—J˜/—Jšœ˜—J˜Jšœ˜—Jšœ˜J˜—šžœœœœ˜=JšœÏc9˜?Jšœ)™)Jšœ œ ˜J˜J˜J˜3šœ˜J˜ Jšœ˜ —J˜Jšœ˜J˜—š ž œœ œœ œ˜TJšœŸ2˜9Jšœ œ ˜šœ˜šœœœ)˜7Jšœœ,˜6Jšœ˜"——J˜\Jšœ˜J˜—šžœœœœ˜0Jšœœ$˜+J˜—Jšœ œ ˜Jšœœ œG˜aJ˜š žœœœœœ˜0Jš˜J˜Jšœœœ˜Jšœœœ˜Jšœ˜ Jšœ˜J˜—šž œœœœ˜9Jšœœ˜Jšœ œ ˜Jšœœ ˜!J˜šž œœœœ˜7Jšœœ˜ Jšœœœœœœœ˜Hš œœœœ˜OJš˜Jšœœ˜ Jšœœœœ˜*J˜Jšœ˜—Jšœœ˜Jšœ˜J˜—J˜Jšœœ ˜'J˜šœœœ˜Jšœœ ˜šœœœ˜Jšœœ˜%Jšœ˜—J˜—šœ/˜3J˜—Jšœœ˜1J˜J˜šœœ œ˜!šœ1˜3Jšœ5˜5Jšœ ˜—Jšœ˜ —šœ˜Jšœœ˜ Jšœœ˜Jšœœ ˜J˜J˜Jš œœœ,œœ ˜MJšœœ˜šœœ œ˜!šœ˜Jš˜J˜/Jšœœ˜#Jšœ œ"˜5Jšœœ˜"Jšœ˜—Jšœ˜—Jšœ œœœ˜-Jšœœœ˜Jšœ œœ˜J˜J˜Jšœ˜ —Jšœ œ˜J˜J˜—J˜J˜J˜Jšœ˜J˜—…—~R