

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.

  z  
CenterlineImpl.mesa
Copyright ╙ 1985, 1992 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)
Э╩∙  ХNewlineDelimiter
Ц(cedarcode) styleЩ codeЪЬЩKЪЬ	╧eЬ6ЩBKЪЬ%Щ%KЩ7KЩ"KЩ,ЧKШ KЪЬмЩмKЪЬZЩZKЪЬКЩКKШ Ъ╧k	Ш	KШKЪЬЮЬ	ШKШЧKШ KЪ╨blЬЮЬЮШKЪЮЬШKЪЮЬШKЪЮЬ
ЮШKШ KЪЬ/Щ/KЩ KЪЬЮЬШKЪ	ЬЮЬЮЬЮЬЮЬШ0KЪЬЮЬЮЬ	ШЪЬ	ЮЬЮЬШKЪЬЮЬЮЬЮЬШ7KЪЬЮЬШ#KЪЬЮЬШKШKШ ЧЪ╧nЬЮЬЮЬШ-KЪЮШKЪЬ
ЮЬ	ШЪЮЬЮЬЮЬЮШЪЮЬЮЬЮЬЮШЪ	ЬЮЬЮЬЮЬ	ЮЬШ[KЪЮЬ!Ш%KЪЮЬ	ШЧKЪЮЬШЧKЪЮЬШЧKШKШKЪЮЬШKШ ЧЪа	ЬЮЬШKЪЮШKШ$KЪ
ЮЬЮЬЮЬЮЬ$ЮЬШJЪЮЬЮЬЮЬЮШ KЪ
ЮЬЮЬЮЬЮЬ ЮЬШFKЪ
ЮЬЮЬЮЬЮЬ&ЮЬШLЪЮЬЮЬЮЬЮШ ШШ-KШ)ЧKШ/ЧKЪЮЬШЧKШKЪЮЬШЧKЪЮЬШKШ ЧЪаЬЮЬЮЬЮЬШ=KЪЮЬ╧c9Ш?KЪЬ)Щ)KЪЬ
ЮЬ	ШKШKШKШ1ЪЮЬЮШKШKЪЮЬШ	ЧKШKЪЮЬШKШ ЧЪаЬЮЬЮЬЮЬЮЬЮЬШTKЪЮЬб2Ш9KЪЬ
ЮЬ	ШЪЮЬШЪЮЬЮЬЮЬ)Ш7KЪЮЬЮЬ,Ш6KЪЮЬШ"ЧЧKШZKЪЮЬШKШ ЧЪ
аЬЮЬЮЬЮЬЮЬШ0KЪЬЮЬ$Ш+KШ ЧKЪЬЮЬШKЪЬЮЬЮЬ	ЮЬ;ШaKШ Ъ
аЬЮЬЮЬЮЬЮЬШ0KЪЮШKШKЪЮЬЮЬЮЬШKЪЮЬЮЬЮЬШKЪЮЬШKЪЮЬШKШ ЧЪа
ЬЮЬЮЬЮЬШ9KЪЬЮЬШKЪЬ
ЮЬ	ШKЪЬЮЬШ!KЪЬЮЬШЪ
аЬЮЬЮЬЮЬЮЬШ7KЪЮЬЮЬШKЪЮЬЮЬЮЬЮЬЮЬЮЬЮЬШHЪ	ЮЬЮЬЮЬЮЬЮШOKЪЮШKЪЬЮЬШ KЪЮЬЮЬЮЬЮЬШ*KШKЪЮЬШЧKЪЮЬЮЬШKЪЮЬШKШ ЧKЪЬЮЬШKЪЬЮЬШ'KШ ЪЮЬЮЬЮЬШKЪЬЮЬ
ШЪЮЬЮЬЮЬЮШKЪЬЮЬШ%KЪЮЬШЧKШЧЪЮЬ/Ш3KШ ЧKЪЬЮЬШ0KШKШЪЮЬЮЬЮЬШ!ЪЮЬ1Ш3KЪЬ5Ш5KЪЮЬШЧKЪЮЬШ	ЧЪЮЬЮШKЪЬЮЬШ
KЪЬЮЬШKЪЬЮЬШKЪЬЮЬШKШKЪ
ЮЬЮЬЮЬ,ЮЬЮЬ	ШMKЪЮЬЮЬШЪЮЬЮЬЮЬШ!ЪЮЬЮШKЪЮШKЪЬЮЬ!Ш/KЪЬЮЬШ#KЪЮЬЮЬ"Ш5KЪЮЬЮЬШ"KЪЮЬШЧKЪЮЬШЧKЪЬЮЬЮЬЮЬШ-KЪЮЬЮЬЮЬШKЪЮЬЮЬЮЬШKШKШKЪЮЬШ	ЧKЪЮЬЮЬШKШKШ ЧKШ KШ KШ KЪЮЬШKШ Ч ЕЧ    ╥  E  