Editing cers-distance

This edit will create a new revision.

Your details (optional)

Name

Email (won’t be displayed; might be used for Gravatar)

URL

Test case details

Title *

Published (uncheck if you want to fiddle around before making the page public)

Description (in case you feel further explanation is needed)(Markdown syntax is allowed)

Are you a spammer? (just answer the question)

Preparation code

Preparation code HTML (this will be inserted in the <body> of a valid HTML5 document in standards mode) (useful when testing DOM operations or including libraries)

Include JavaScript libraries as follows: <script src="//cdn.ext/library.js"></script>

Define setup for all tests (variables, functions, arrays or other objects that will be used in the tests) (runs before each clocked test loop, outside of the timed code region) (e.g. define local test variables, reset global variables, clear canvas, etc.) (see FAQ)

/*
 * =============================================================================
 *
 * D I S T A N C E   T R A N S F O R M   R O U T I N E S
 *
 * $Revision: 1.4 $ $Date: 2009/03/29 04:10:18 $
 *
 * ANIMAL - ANIMAL IMage Processing LibrarY
 * Copyright (C) 2002,2003  Ricardo Fabbri <rfabbri@if.sc.usp.br>
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 * 
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 * 
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 * =============================================================================
 */

Array.prototype.set = function set(arr, offset) {
    var o=offset||0,i;
    for (i=0; i<arr.length; i++)
        this[i] = arr[i];
}

Array.prototype.subarray = Array.prototype.slice;
if (typeof Float64Array != "undefined") {
  if (typeof Float64Array.prototype.subarray != "function") {
    Float64Array.prototype.subarray = Float64Array.prototype.slice;
  }
}

// this is the image class, emulating ImgPUInt32 from Animal
function ImgPUInt32(im, c, r) {
    try {
        this.data = Float64Array(im);
        this.lut = Float64Array(r+1);
    } catch (e) {
        this.data = im;
        this.lut = Array(r+1);
    }
    this.cols = c;
    this.rows = r;
    this.isbinary = true;

// initiate lut - one too many, to aid slice later
    var i;
    for (i=0; i<=r; i++) {
        this.lut[i] = i*c;
    }
    this.log = false;
}

// 1st step vertical erosions for Lotufo-Zampirolli EDT
ImgPUInt32.prototype.edt_lz_step1_vertical = function edt_lz_step1_vertical() {
    var r,c,b;

for (c=0; c < this.cols; c++) {
        b=1;
        for (r=1; r<this.rows; r++)
            if ((this.data[c+this.lut[r]]) > (this.data[c+this.lut[r-1]]) + b) {
                (this.data[c+this.lut[r]]) = (this.data[c+this.lut[r-1]]) + b;
            b += 2;
         } else
            b = 1;
      b=1;
      for (r=this.rows-2; r >= 0; r--) {
         if ((this.data[c+this.lut[r]]) > (this.data[c+this.lut[r+1]]) + b) {
            (this.data[c+this.lut[r]]) = (this.data[c+this.lut[r+1]]) + b;
            b += 2;
         } else
            b = 1;
      }
    }
    return true;
}

ImgPUInt32.prototype.debug = function debug() {
    var i,o,str="<table border='1'>";
    for (i=0; i<this.rows; i++) {
        str+="<tr>";
        for (o=0; o<this.cols; o++)
            str+= "<td>"+this.data[i*this.rows+o]+"</td>";
        str += "</tr>";
    }
    str += "</table>";
    try {
        $("body").append(str);
    } catch (e) {
        document.write(str);
    }
}

ImgPUInt32.prototype.edt_meijster_2D_from_1D = function edt_meijster_2D_from_1D() {
    function meijster_f(x,i, val){ return ( ( (x) - (i))*((x) - (i) ) + (val) ) };

var rows=this.rows, r,
        cols=this.cols, u,
        q, w, s, t;
    var img_row, row_copy;
    var MAX = -1 >>> 1;

try {
        s = Float64Array(cols);
        t = Float64Array(cols);
        row_copy = Float64Array(cols);
    } catch (e) {
        s = Array(cols);
        t = Array(cols);
        row_copy = Array(cols);
    }
    for (r=0; r<rows; r++) {
        img_row = this.lut[r];
        q = s[0] = t[0] = 0;
        for (u = 1; u < cols; ++u) {
            var im_r_u = this.data[u+img_row];
            while (q != -1
                && meijster_f(t[q],s[q],this.data[s[q]+img_row]) > meijster_f(t[q],u,im_r_u) 
            ) {
                --q;
            }

if (q == -1) {
                q = 0; s[0] = u;
            } else { // FIXME this line might need to be understood
                var tmp = ( (u*u - (s[q]*s[q]) + this.data[u+img_row] - this.data[s[q]+img_row]) / (2*(u - s[q])) );
                if (tmp < 0)
                    tmp = MAX+tmp+1;
                w = 1 + parseInt(tmp) ;
                if (w < cols) {
                    ++q;
                    s[q] = u;
                    t[q] = w;
                }
            }
        }
        row_copy = this.data.subarray(this.lut[r], this.lut[r+1]);

for (u = cols-1; u != -1; --u) {
            this.data[u+img_row] = meijster_f(u,s[q], row_copy[s[q]]);
            if (u == t[q]) {
                --q;
                if (q<0)
                    q = MAX+q+1;
            }
        }
    }

return true;
}

/*
 * PAPER
 *    A. Meijster, J.B.T.M. Roerdink, and W.H. Hesselink "A General Algorithm
 *    for Computing Distance Transforms in Linear Time",
 *    proc. of 5th Int. Conf. Mathematical Morphology and its Applications to
 *    Image and Signal Processing, 2000
 */

ImgPUInt32.prototype.edt_meijster2000 = function edt_meijster2000() {
    var i,r=this.rows,c=this.cols;
    var stat;
    var MAX = -1 >>> 1;
    var infty = MAX - r*r - c*c;
    var FG=1;

if (this.log) this.debug();

for (i=0; i < r*c; i++)
        if (this.data[i] == FG)
            this.data[i] = infty;

// Vertical columnwise EDT
    stat = this.edt_lz_step1_vertical();
   // Lotufo's 1D EDT is equivalent to Meijster's scans 1 and 2.
   // What really matters is the 2nd stage.

if (this.log) this.debug();
    stat = this.edt_meijster_2D_from_1D();

if (this.log) this.debug();
    this.isbinary = false;
    return true;
}

const rows = 500;
const cols = 500;
var data = Array(rows*cols);
for (i=0; i<cols*rows; i++)
  if (i>=cols*rows/2 && i%cols<cols/2)
    data[i] = 1;
  else
    data[i] = 0;

Define teardown for all tests (runs after each clocked test loop, outside of the timed code region) (see FAQ)

Code snippets to compare

Test 1

Title

Async (check if this is an asynchronous test)

Code

var data = Array(rows*cols);
for (i=0; i<cols*rows; i++)
  if (i>=cols*rows/2 && i%cols<cols/2)
    data[i] = 1;
  else
    data[i] = 0;
var im = new ImgPUInt32(data, rows, cols);
im.log = false;
im.edt_meijster2000();

Test 2

Title

Async (check if this is an asynchronous test)

Code

var data = Array(rows*cols);
for (i=0; i<cols*rows; i++)
  if (i>=cols*rows/2 && i%cols<cols/2)
    data[i] = 0;
  else
    data[i] = 1;
var im = new ImgPUInt32(data, rows, cols);
im.log = false;
im.edt_meijster2000();