CenterlineImpl.mesa
Copyright © 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).
DIRECTORY
Complex,
Real USING [Round],
Centerline;
CenterlineImpl: CEDAR PROGRAM
IMPORTS Complex, Real
EXPORTS Centerline =
BEGIN OPEN Centerline;
Here is a cache of a part of the blurred image.
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
The piece is centered around (pixel,line)
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.