OLD | NEW |
(Empty) | |
| 1 /* |
| 2 * edtaa3() |
| 3 * |
| 4 * Sweep-and-update Euclidean distance transform of an |
| 5 * image. Positive pixels are treated as object pixels, |
| 6 * zero or negative pixels are treated as background. |
| 7 * An attempt is made to treat antialiased edges correctly. |
| 8 * The input image must have pixels in the range [0,1], |
| 9 * and the antialiased image should be a box-filter |
| 10 * sampling of the ideal, crisp edge. |
| 11 * If the antialias region is more than 1 pixel wide, |
| 12 * the result from this transform will be inaccurate. |
| 13 * |
| 14 * By Stefan Gustavson (stefan.gustavson@gmail.com). |
| 15 * |
| 16 * Originally written in 1994, based on a verbal |
| 17 * description of the SSED8 algorithm published in the |
| 18 * PhD dissertation of Ingemar Ragnemalm. This is his |
| 19 * algorithm, I only implemented it in C. |
| 20 * |
| 21 * Updated in 2004 to treat border pixels correctly, |
| 22 * and cleaned up the code to improve readability. |
| 23 * |
| 24 * Updated in 2009 to handle anti-aliased edges. |
| 25 * |
| 26 * Updated in 2011 to avoid a corner case infinite loop. |
| 27 * |
| 28 * Updated 2012 to change license from LGPL to MIT. |
| 29 */ |
| 30 |
| 31 /* |
| 32 Copyright (C) 2009-2012 Stefan Gustavson (stefan.gustavson@gmail.com) |
| 33 The code in this file is distributed under the MIT license: |
| 34 |
| 35 Permission is hereby granted, free of charge, to any person obtaining a copy |
| 36 of this software and associated documentation files (the "Software"), to deal |
| 37 in the Software without restriction, including without limitation the rights |
| 38 to use, copy, modify, merge, publish, distribute, sublicense, and/or sell |
| 39 copies of the Software, and to permit persons to whom the Software is |
| 40 furnished to do so, subject to the following conditions: |
| 41 |
| 42 The above copyright notice and this permission notice shall be included in |
| 43 all copies or substantial portions of the Software. |
| 44 |
| 45 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR |
| 46 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, |
| 47 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE |
| 48 AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER |
| 49 LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, |
| 50 OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN |
| 51 THE SOFTWARE. |
| 52 */ |
| 53 |
| 54 #include "edtaa3.h" |
| 55 |
| 56 #include <math.h> |
| 57 |
| 58 #if EDTAA_UNSIGNED_CHAR_INPUT |
| 59 #define IMG(i) ((double)(img[i] & 0xff)/256.0) |
| 60 #else |
| 61 #define IMG(i) (img[i]) |
| 62 #endif |
| 63 |
| 64 /* |
| 65 * Compute the local gradient at edge pixels using convolution filters. |
| 66 * The gradient is computed only at edge pixels. At other places in the |
| 67 * image, it is never used, and it's mostly zero anyway. |
| 68 */ |
| 69 void computegradient(EdtaaImageType *img, int w, int h, double *gx, double *gy) |
| 70 { |
| 71 int i,j,k; |
| 72 double glength; |
| 73 #define SQRT2 1.4142136 |
| 74 for(i = 1; i < h-1; i++) { // Avoid edges where the kernels would spill over |
| 75 for(j = 1; j < w-1; j++) { |
| 76 k = i*w + j; |
| 77 if((IMG(k)>0.0) && (IMG(k)<1.0)) { // Compute gradient for edge pixe
ls only |
| 78 gx[k] = -IMG(k-w-1) - SQRT2*IMG(k-1) - IMG(k+w-1) + IMG(k-w+1) +
SQRT2*IMG(k+1) + IMG(k+w+1); |
| 79 gy[k] = -IMG(k-w-1) - SQRT2*IMG(k-w) - IMG(k+w-1) + IMG(k-w+1) +
SQRT2*IMG(k+w) + IMG(k+w+1); |
| 80 glength = gx[k]*gx[k] + gy[k]*gy[k]; |
| 81 if(glength > 0.0) { // Avoid division by zero |
| 82 glength = sqrt(glength); |
| 83 gx[k]=gx[k]/glength; |
| 84 gy[k]=gy[k]/glength; |
| 85 } |
| 86 } |
| 87 } |
| 88 } |
| 89 // TODO: Compute reasonable values for gx, gy also around the image edges. |
| 90 // (These are zero now, which reduces the accuracy for a 1-pixel wide region |
| 91 // around the image edge.) 2x2 kernels would be suitable for this. |
| 92 } |
| 93 |
| 94 /* |
| 95 * A somewhat tricky function to approximate the distance to an edge in a |
| 96 * certain pixel, with consideration to either the local gradient (gx,gy) |
| 97 * or the direction to the pixel (dx,dy) and the pixel greyscale value a. |
| 98 * The latter alternative, using (dx,dy), is the metric used by edtaa2(). |
| 99 * Using a local estimate of the edge gradient (gx,gy) yields much better |
| 100 * accuracy at and near edges, and reduces the error even at distant pixels |
| 101 * provided that the gradient direction is accurately estimated. |
| 102 */ |
| 103 static double edgedf(double gx, double gy, double a) |
| 104 { |
| 105 double df, glength, temp, a1; |
| 106 |
| 107 if ((gx == 0) || (gy == 0)) { // Either A) gu or gv are zero, or B) both |
| 108 df = 0.5-a; // Linear approximation is A) correct or B) a fair guess |
| 109 } else { |
| 110 glength = sqrt(gx*gx + gy*gy); |
| 111 if(glength>0) { |
| 112 gx = gx/glength; |
| 113 gy = gy/glength; |
| 114 } |
| 115 /* Everything is symmetric wrt sign and transposition, |
| 116 * so move to first octant (gx>=0, gy>=0, gx>=gy) to |
| 117 * avoid handling all possible edge directions. |
| 118 */ |
| 119 gx = fabs(gx); |
| 120 gy = fabs(gy); |
| 121 if(gx<gy) { |
| 122 temp = gx; |
| 123 gx = gy; |
| 124 gy = temp; |
| 125 } |
| 126 a1 = 0.5*gy/gx; |
| 127 if (a < a1) { // 0 <= a < a1 |
| 128 df = 0.5*(gx + gy) - sqrt(2.0*gx*gy*a); |
| 129 } else if (a < (1.0-a1)) { // a1 <= a <= 1-a1 |
| 130 df = (0.5-a)*gx; |
| 131 } else { // 1-a1 < a <= 1 |
| 132 df = -0.5*(gx + gy) + sqrt(2.0*gx*gy*(1.0-a)); |
| 133 } |
| 134 } |
| 135 return df; |
| 136 } |
| 137 |
| 138 static double distaa3(EdtaaImageType *img, double *gximg, double *gyimg, int w,
int c, int xc, int yc, int xi, int yi) |
| 139 { |
| 140 double di, df, dx, dy, gx, gy, a; |
| 141 int closest; |
| 142 |
| 143 closest = c-xc-yc*w; // Index to the edge pixel pointed to from c |
| 144 a = IMG(closest); // Grayscale value at the edge pixel |
| 145 gx = gximg[closest]; // X gradient component at the edge pixel |
| 146 gy = gyimg[closest]; // Y gradient component at the edge pixel |
| 147 |
| 148 if(a > 1.0) a = 1.0; |
| 149 if(a < 0.0) a = 0.0; // Clip grayscale values outside the range [0,1] |
| 150 if(a == 0.0) return 1000000.0; // Not an object pixel, return "very far" ("don
't know yet") |
| 151 |
| 152 dx = (double)xi; |
| 153 dy = (double)yi; |
| 154 di = sqrt(dx*dx + dy*dy); // Length of integer vector, like a traditional EDT |
| 155 if(di==0) { // Use local gradient only at edges |
| 156 // Estimate based on local gradient only |
| 157 df = edgedf(gx, gy, a); |
| 158 } else { |
| 159 // Estimate gradient based on direction to edge (accurate for large di) |
| 160 df = edgedf(dx, dy, a); |
| 161 } |
| 162 return di + df; // Same metric as edtaa2, except at edges (where di=0) |
| 163 } |
| 164 |
| 165 // Shorthand macro: add ubiquitous parameters dist, gx, gy, img and w and call d
istaa3() |
| 166 #define DISTAA(c,xc,yc,xi,yi) (distaa3(img, gx, gy, w, c, xc, yc, xi, yi)) |
| 167 |
| 168 void edtaa3(EdtaaImageType *img, double *gx, double *gy, int w, int h, short *di
stx, short *disty, double *dist) |
| 169 { |
| 170 int x, y, i, c; |
| 171 int offset_u, offset_ur, offset_r, offset_rd, |
| 172 offset_d, offset_dl, offset_l, offset_lu; |
| 173 double olddist, newdist; |
| 174 int cdistx, cdisty, newdistx, newdisty; |
| 175 int changed; |
| 176 double epsilon = 1e-3; |
| 177 double a; |
| 178 |
| 179 /* Initialize index offsets for the current image width */ |
| 180 offset_u = -w; |
| 181 offset_ur = -w+1; |
| 182 offset_r = 1; |
| 183 offset_rd = w+1; |
| 184 offset_d = w; |
| 185 offset_dl = w-1; |
| 186 offset_l = -1; |
| 187 offset_lu = -w-1; |
| 188 |
| 189 /* Initialize the distance images */ |
| 190 for(i=0; i<w*h; i++) { |
| 191 distx[i] = 0; // At first, all pixels point to |
| 192 disty[i] = 0; // themselves as the closest known. |
| 193 a = IMG(i); |
| 194 if(a <= 0.0) |
| 195 { |
| 196 dist[i]= 1000000.0; // Big value, means "not set yet" |
| 197 } |
| 198 else if (a<1.0) { |
| 199 dist[i] = edgedf(gx[i], gy[i], a); // Gradient-assisted estimate |
| 200 } |
| 201 else { |
| 202 dist[i]= 0.0; // Inside the object |
| 203 } |
| 204 } |
| 205 |
| 206 /* Perform the transformation */ |
| 207 do |
| 208 { |
| 209 changed = 0; |
| 210 |
| 211 /* Scan rows, except first row */ |
| 212 for(y=1; y<h; y++) |
| 213 { |
| 214 |
| 215 /* move index to leftmost pixel of current row */ |
| 216 i = y*w; |
| 217 |
| 218 /* scan right, propagate distances from above & left */ |
| 219 |
| 220 /* Leftmost pixel is special, has no left neighbors */ |
| 221 olddist = dist[i]; |
| 222 if(olddist > 0) // If non-zero distance or not set yet |
| 223 { |
| 224 c = i + offset_u; // Index of candidate for testing |
| 225 cdistx = distx[c]; |
| 226 cdisty = disty[c]; |
| 227 newdistx = cdistx; |
| 228 newdisty = cdisty+1; |
| 229 newdist = DISTAA(c, cdistx, cdisty, newdistx, newdisty); |
| 230 if(newdist < olddist-epsilon) |
| 231 { |
| 232 distx[i]=newdistx; |
| 233 disty[i]=newdisty; |
| 234 dist[i]=newdist; |
| 235 olddist=newdist; |
| 236 changed = 1; |
| 237 } |
| 238 |
| 239 c = i+offset_ur; |
| 240 cdistx = distx[c]; |
| 241 cdisty = disty[c]; |
| 242 newdistx = cdistx-1; |
| 243 newdisty = cdisty+1; |
| 244 newdist = DISTAA(c, cdistx, cdisty, newdistx, newdisty); |
| 245 if(newdist < olddist-epsilon) |
| 246 { |
| 247 distx[i]=newdistx; |
| 248 disty[i]=newdisty; |
| 249 dist[i]=newdist; |
| 250 changed = 1; |
| 251 } |
| 252 } |
| 253 i++; |
| 254 |
| 255 /* Middle pixels have all neighbors */ |
| 256 for(x=1; x<w-1; x++, i++) |
| 257 { |
| 258 olddist = dist[i]; |
| 259 if(olddist <= 0) continue; // No need to update further |
| 260 |
| 261 c = i+offset_l; |
| 262 cdistx = distx[c]; |
| 263 cdisty = disty[c]; |
| 264 newdistx = cdistx+1; |
| 265 newdisty = cdisty; |
| 266 newdist = DISTAA(c, cdistx, cdisty, newdistx, newdisty); |
| 267 if(newdist < olddist-epsilon) |
| 268 { |
| 269 distx[i]=newdistx; |
| 270 disty[i]=newdisty; |
| 271 dist[i]=newdist; |
| 272 olddist=newdist; |
| 273 changed = 1; |
| 274 } |
| 275 |
| 276 c = i+offset_lu; |
| 277 cdistx = distx[c]; |
| 278 cdisty = disty[c]; |
| 279 newdistx = cdistx+1; |
| 280 newdisty = cdisty+1; |
| 281 newdist = DISTAA(c, cdistx, cdisty, newdistx, newdisty); |
| 282 if(newdist < olddist-epsilon) |
| 283 { |
| 284 distx[i]=newdistx; |
| 285 disty[i]=newdisty; |
| 286 dist[i]=newdist; |
| 287 olddist=newdist; |
| 288 changed = 1; |
| 289 } |
| 290 |
| 291 c = i+offset_u; |
| 292 cdistx = distx[c]; |
| 293 cdisty = disty[c]; |
| 294 newdistx = cdistx; |
| 295 newdisty = cdisty+1; |
| 296 newdist = DISTAA(c, cdistx, cdisty, newdistx, newdisty); |
| 297 if(newdist < olddist-epsilon) |
| 298 { |
| 299 distx[i]=newdistx; |
| 300 disty[i]=newdisty; |
| 301 dist[i]=newdist; |
| 302 olddist=newdist; |
| 303 changed = 1; |
| 304 } |
| 305 |
| 306 c = i+offset_ur; |
| 307 cdistx = distx[c]; |
| 308 cdisty = disty[c]; |
| 309 newdistx = cdistx-1; |
| 310 newdisty = cdisty+1; |
| 311 newdist = DISTAA(c, cdistx, cdisty, newdistx, newdisty); |
| 312 if(newdist < olddist-epsilon) |
| 313 { |
| 314 distx[i]=newdistx; |
| 315 disty[i]=newdisty; |
| 316 dist[i]=newdist; |
| 317 changed = 1; |
| 318 } |
| 319 } |
| 320 |
| 321 /* Rightmost pixel of row is special, has no right neighbors */ |
| 322 olddist = dist[i]; |
| 323 if(olddist > 0) // If not already zero distance |
| 324 { |
| 325 c = i+offset_l; |
| 326 cdistx = distx[c]; |
| 327 cdisty = disty[c]; |
| 328 newdistx = cdistx+1; |
| 329 newdisty = cdisty; |
| 330 newdist = DISTAA(c, cdistx, cdisty, newdistx, newdisty); |
| 331 if(newdist < olddist-epsilon) |
| 332 { |
| 333 distx[i]=newdistx; |
| 334 disty[i]=newdisty; |
| 335 dist[i]=newdist; |
| 336 olddist=newdist; |
| 337 changed = 1; |
| 338 } |
| 339 |
| 340 c = i+offset_lu; |
| 341 cdistx = distx[c]; |
| 342 cdisty = disty[c]; |
| 343 newdistx = cdistx+1; |
| 344 newdisty = cdisty+1; |
| 345 newdist = DISTAA(c, cdistx, cdisty, newdistx, newdisty); |
| 346 if(newdist < olddist-epsilon) |
| 347 { |
| 348 distx[i]=newdistx; |
| 349 disty[i]=newdisty; |
| 350 dist[i]=newdist; |
| 351 olddist=newdist; |
| 352 changed = 1; |
| 353 } |
| 354 |
| 355 c = i+offset_u; |
| 356 cdistx = distx[c]; |
| 357 cdisty = disty[c]; |
| 358 newdistx = cdistx; |
| 359 newdisty = cdisty+1; |
| 360 newdist = DISTAA(c, cdistx, cdisty, newdistx, newdisty); |
| 361 if(newdist < olddist-epsilon) |
| 362 { |
| 363 distx[i]=newdistx; |
| 364 disty[i]=newdisty; |
| 365 dist[i]=newdist; |
| 366 changed = 1; |
| 367 } |
| 368 } |
| 369 |
| 370 /* Move index to second rightmost pixel of current row. */ |
| 371 /* Rightmost pixel is skipped, it has no right neighbor. */ |
| 372 i = y*w + w-2; |
| 373 |
| 374 /* scan left, propagate distance from right */ |
| 375 for(x=w-2; x>=0; x--, i--) |
| 376 { |
| 377 olddist = dist[i]; |
| 378 if(olddist <= 0) continue; // Already zero distance |
| 379 |
| 380 c = i+offset_r; |
| 381 cdistx = distx[c]; |
| 382 cdisty = disty[c]; |
| 383 newdistx = cdistx-1; |
| 384 newdisty = cdisty; |
| 385 newdist = DISTAA(c, cdistx, cdisty, newdistx, newdisty); |
| 386 if(newdist < olddist-epsilon) |
| 387 { |
| 388 distx[i]=newdistx; |
| 389 disty[i]=newdisty; |
| 390 dist[i]=newdist; |
| 391 changed = 1; |
| 392 } |
| 393 } |
| 394 } |
| 395 |
| 396 /* Scan rows in reverse order, except last row */ |
| 397 for(y=h-2; y>=0; y--) |
| 398 { |
| 399 /* move index to rightmost pixel of current row */ |
| 400 i = y*w + w-1; |
| 401 |
| 402 /* Scan left, propagate distances from below & right */ |
| 403 |
| 404 /* Rightmost pixel is special, has no right neighbors */ |
| 405 olddist = dist[i]; |
| 406 if(olddist > 0) // If not already zero distance |
| 407 { |
| 408 c = i+offset_d; |
| 409 cdistx = distx[c]; |
| 410 cdisty = disty[c]; |
| 411 newdistx = cdistx; |
| 412 newdisty = cdisty-1; |
| 413 newdist = DISTAA(c, cdistx, cdisty, newdistx, newdisty); |
| 414 if(newdist < olddist-epsilon) |
| 415 { |
| 416 distx[i]=newdistx; |
| 417 disty[i]=newdisty; |
| 418 dist[i]=newdist; |
| 419 olddist=newdist; |
| 420 changed = 1; |
| 421 } |
| 422 |
| 423 c = i+offset_dl; |
| 424 cdistx = distx[c]; |
| 425 cdisty = disty[c]; |
| 426 newdistx = cdistx+1; |
| 427 newdisty = cdisty-1; |
| 428 newdist = DISTAA(c, cdistx, cdisty, newdistx, newdisty); |
| 429 if(newdist < olddist-epsilon) |
| 430 { |
| 431 distx[i]=newdistx; |
| 432 disty[i]=newdisty; |
| 433 dist[i]=newdist; |
| 434 changed = 1; |
| 435 } |
| 436 } |
| 437 i--; |
| 438 |
| 439 /* Middle pixels have all neighbors */ |
| 440 for(x=w-2; x>0; x--, i--) |
| 441 { |
| 442 olddist = dist[i]; |
| 443 if(olddist <= 0) continue; // Already zero distance |
| 444 |
| 445 c = i+offset_r; |
| 446 cdistx = distx[c]; |
| 447 cdisty = disty[c]; |
| 448 newdistx = cdistx-1; |
| 449 newdisty = cdisty; |
| 450 newdist = DISTAA(c, cdistx, cdisty, newdistx, newdisty); |
| 451 if(newdist < olddist-epsilon) |
| 452 { |
| 453 distx[i]=newdistx; |
| 454 disty[i]=newdisty; |
| 455 dist[i]=newdist; |
| 456 olddist=newdist; |
| 457 changed = 1; |
| 458 } |
| 459 |
| 460 c = i+offset_rd; |
| 461 cdistx = distx[c]; |
| 462 cdisty = disty[c]; |
| 463 newdistx = cdistx-1; |
| 464 newdisty = cdisty-1; |
| 465 newdist = DISTAA(c, cdistx, cdisty, newdistx, newdisty); |
| 466 if(newdist < olddist-epsilon) |
| 467 { |
| 468 distx[i]=newdistx; |
| 469 disty[i]=newdisty; |
| 470 dist[i]=newdist; |
| 471 olddist=newdist; |
| 472 changed = 1; |
| 473 } |
| 474 |
| 475 c = i+offset_d; |
| 476 cdistx = distx[c]; |
| 477 cdisty = disty[c]; |
| 478 newdistx = cdistx; |
| 479 newdisty = cdisty-1; |
| 480 newdist = DISTAA(c, cdistx, cdisty, newdistx, newdisty); |
| 481 if(newdist < olddist-epsilon) |
| 482 { |
| 483 distx[i]=newdistx; |
| 484 disty[i]=newdisty; |
| 485 dist[i]=newdist; |
| 486 olddist=newdist; |
| 487 changed = 1; |
| 488 } |
| 489 |
| 490 c = i+offset_dl; |
| 491 cdistx = distx[c]; |
| 492 cdisty = disty[c]; |
| 493 newdistx = cdistx+1; |
| 494 newdisty = cdisty-1; |
| 495 newdist = DISTAA(c, cdistx, cdisty, newdistx, newdisty); |
| 496 if(newdist < olddist-epsilon) |
| 497 { |
| 498 distx[i]=newdistx; |
| 499 disty[i]=newdisty; |
| 500 dist[i]=newdist; |
| 501 changed = 1; |
| 502 } |
| 503 } |
| 504 /* Leftmost pixel is special, has no left neighbors */ |
| 505 olddist = dist[i]; |
| 506 if(olddist > 0) // If not already zero distance |
| 507 { |
| 508 c = i+offset_r; |
| 509 cdistx = distx[c]; |
| 510 cdisty = disty[c]; |
| 511 newdistx = cdistx-1; |
| 512 newdisty = cdisty; |
| 513 newdist = DISTAA(c, cdistx, cdisty, newdistx, newdisty); |
| 514 if(newdist < olddist-epsilon) |
| 515 { |
| 516 distx[i]=newdistx; |
| 517 disty[i]=newdisty; |
| 518 dist[i]=newdist; |
| 519 olddist=newdist; |
| 520 changed = 1; |
| 521 } |
| 522 |
| 523 c = i+offset_rd; |
| 524 cdistx = distx[c]; |
| 525 cdisty = disty[c]; |
| 526 newdistx = cdistx-1; |
| 527 newdisty = cdisty-1; |
| 528 newdist = DISTAA(c, cdistx, cdisty, newdistx, newdisty); |
| 529 if(newdist < olddist-epsilon) |
| 530 { |
| 531 distx[i]=newdistx; |
| 532 disty[i]=newdisty; |
| 533 dist[i]=newdist; |
| 534 olddist=newdist; |
| 535 changed = 1; |
| 536 } |
| 537 |
| 538 c = i+offset_d; |
| 539 cdistx = distx[c]; |
| 540 cdisty = disty[c]; |
| 541 newdistx = cdistx; |
| 542 newdisty = cdisty-1; |
| 543 newdist = DISTAA(c, cdistx, cdisty, newdistx, newdisty); |
| 544 if(newdist < olddist-epsilon) |
| 545 { |
| 546 distx[i]=newdistx; |
| 547 disty[i]=newdisty; |
| 548 dist[i]=newdist; |
| 549 changed = 1; |
| 550 } |
| 551 } |
| 552 |
| 553 /* Move index to second leftmost pixel of current row. */ |
| 554 /* Leftmost pixel is skipped, it has no left neighbor. */ |
| 555 i = y*w + 1; |
| 556 for(x=1; x<w; x++, i++) |
| 557 { |
| 558 /* scan right, propagate distance from left */ |
| 559 olddist = dist[i]; |
| 560 if(olddist <= 0) continue; // Already zero distance |
| 561 |
| 562 c = i+offset_l; |
| 563 cdistx = distx[c]; |
| 564 cdisty = disty[c]; |
| 565 newdistx = cdistx+1; |
| 566 newdisty = cdisty; |
| 567 newdist = DISTAA(c, cdistx, cdisty, newdistx, newdisty); |
| 568 if(newdist < olddist-epsilon) |
| 569 { |
| 570 distx[i]=newdistx; |
| 571 disty[i]=newdisty; |
| 572 dist[i]=newdist; |
| 573 changed = 1; |
| 574 } |
| 575 } |
| 576 } |
| 577 } |
| 578 while(changed); // Sweep until no more updates are made |
| 579 |
| 580 /* The transformation is completed. */ |
| 581 |
| 582 } |
OLD | NEW |