Radial Vector Image Processing in JavaScript

I’m a noob when it comes to image processing algorithms. But when I tried to do something in GIMP that I could not find the right button for, I decided to create an image processing algorithm myself. Maybe there is a much simpler solution to this and maybe you can do it with one click in Photoshop or GIMP, but I just could not find out how.

So here’s the deal: There is this pencil drawing I have photographed and cut out digitally, because there were other things in the background that I did not want to use:

The background is stripped from the image

I had to throw the original background away. Then I needed a new background and I wanted the background to have the same colorization as the foreground, especially as the outermost pixels of the foreground. So I tried to isolate the outermost regions of the remaining image:

The outermost regions of the remaining image

I now wanted to expand these colors radially from the remaining ribbon to the borders of the image, do something like this, but in a way that there won’t be any white pixels left in the image:

What we want to do

I decided to use Jimp for this, a JavaScript library for image processing. First of all, I loaded the source image two times, to obtain a buffer of the source and another buffer of the source that I can overwrite, to not mess with the original:

const readPromise1 = Jimp.read(FILENAME);
//read file again to obtain duplicate copy to overwrite
const readPromise2 = Jimp.read(FILENAME);

Promise.all([readPromise1, readPromise2])
  .then(([originalImage, newImage]) => {
    expand(originalImage, newImage);
    newImage.write(NEW_FILENAME);
  });

The function expand takes the original image, iterates from START_ANGLE to END_ANGLE in a pre-defined interval called STEP_IN_DEGREES. We will see how this works in a minute. For STEP_IN_DEGREES, I chose the value 0.02 to be sure that even in the corners, there won’t be any white pixel left. I came to this value by trial and error. For each step, the function expandPath is called. An angle of 0° results in a vector from the center to the right edge of the image, that is perpendicular to the right edge. An angle of 180° means the exact opposite direction.

const expand = (originalImage, newImage) => {
  const steps = Math.floor((END_ANGLE - START_ANGLE) / STEP_IN_DEGREES);

  console.log(steps + " steps");
  let s = 0;
  let degrees = START_ANGLE;
  while (degrees < END_ANGLE){
    expandPath(originalImage, newImage, degrees);
    s++;
    degrees += STEP_IN_DEGREES;

    if (s % 100 === 0){
      console.log(s + "/" + steps + " steps completed");
    }
  }
};

The function expandPath consists of two steps:

  1. Going from the center to the edge of the image and finding the first colored pixel on the given vector
  2. coloring the rest of the pixels in that vector

In order to find the first colored pixel in a vector, we need to determine which pixels are touched by this vector at all. For this I computed the line segment from the center to the edge. A line segment is defined by two points. In our case, the first point is always the center of the image, which is (width/2, height/2). The code for finding the corner point is inspired by https://math.stackexchange.com/a/2468068/441966.

const getLineSegmentFromCenterToBorder = (image, degrees) => {
  const width = image.bitmap.width;
  const height = image.bitmap.height;

  const x0 = width / 2;
  const y0 = height / 2;

  const angle = 2 * Math.PI * (degrees / 360);
  //Inspired by https://math.stackexchange.com/questions/2468060/find-x-y-coordinates-of-a-square-given-an-angle-alpha
  const s = width / 2;
  const x = Math.cos(angle);
  const y = Math.sin(angle);
  const M = Math.max(Math.abs(x), Math.abs(y));
  const x1 = s * x / M + x0;
  const y1 = s * y / M + y0;

  return {x0, y0, x1, y1};
};

Now that we have our line segment, we can get to the most fun part: Obtaining all the pixels that are touched by this line segment. How to do this? We can conceive of a pixel as a square with an edge length of 1. This is by the way what most image display software does when you zoom in on an image: The Pixels are displayed as squares. Pythagoras teaches us that the distance from the center of a pixel to one of its corners is 0.5 * SQRT(2).

Two line segments and the pixels they touch

Now we want to compute the (shortest) distance from the center of a pixel to the line segment, and this StackOverflow post provides the perfect JavaScript code to do this: https://stackoverflow.com/a/6853926/3890888

If the distance is smaller than 0.5 * SQRT(2), the pixel shall be touched by the vector. I am aware of the fact that some pixels are included even if the line does not touch the pixel surface, because we only consider the maximum and not the actual distance from the center of a pixel to its border, but the results are nevertheless acceptable to me.

Now that we have the pixels of our line segment, we just look for the first one that is not transparent, save ist color in a variable and set all the other pixels of that line segment to the same color. Done. Now we have the perfect background for the image:

The end result

Here’s the complete script I’ve used:

//expands paths from center of image

const Jimp = require("jimp");

const DISTANCE_PIXEL_MID_TO_CORNER = 0.5 * Math.SQRT2;
const FILENAME = "frame-to-expand.png";
const NEW_FILENAME = "new-image.png";
const STEP_IN_DEGREES = 0.02; //in degrees
const START_ANGLE = 0;
const END_ANGLE = 360;

const getLineSegmentFromCenterToBorder = (image, degrees) => {
  const width = image.bitmap.width;
  const height = image.bitmap.height;

  const x0 = width / 2;
  const y0 = height / 2;

  const angle = 2 * Math.PI * (degrees / 360);
  //Inspired by https://math.stackexchange.com/questions/2468060/find-x-y-coordinates-of-a-square-given-an-angle-alpha
  const s = width / 2;
  const x = Math.cos(angle);
  const y = Math.sin(angle);
  const M = Math.max(Math.abs(x), Math.abs(y));
  const x1 = s * x / M + x0;
  const y1 = s * y / M + y0;

  return {x0, y0, x1, y1};
};


//from https://stackoverflow.com/a/6853926/3890888
function pDistance(x, y, x1, y1, x2, y2) {

  const A = x - x1;
  const B = y - y1;
  const C = x2 - x1;
  const D = y2 - y1;

  const dot = A * C + B * D;
  const lenSQ = C * C + D * D;
  let param = -1;
  if (lenSQ !== 0) //in case of 0 length line
    param = dot / lenSQ;

  let xx, yy;

  if (param < 0) {
    xx = x1;
    yy = y1;
  }
  else if (param > 1) {
    xx = x2;
    yy = y2;
  }
  else {
    xx = x1 + param * C;
    yy = y1 + param * D;
  }

  const dx = x - xx;
  const dy = y - yy;
  return Math.sqrt(dx * dx + dy * dy);
}


const getAllPixelsOfLineSegment = (image, lineSegment) => {
  const width = image.bitmap.width;
  const height = image.bitmap.height;

  const pixelsOfLineSegment = [];

  for(let x = 0; x < width; x++){
    for (let y = 0; y < height; y++){
      if (pDistance(x, y, lineSegment.x0, lineSegment.y0, lineSegment.x1, lineSegment.y1) <= DISTANCE_PIXEL_MID_TO_CORNER){
        pixelsOfLineSegment.push({x, y});
      }
    }
  }

  return pixelsOfLineSegment;
};

const findFirstColoredPixel = (image, degrees) => {
  //console.log("Degrees: " + degrees);
  const lineSegment = getLineSegmentFromCenterToBorder(image, degrees);
  const pixelsOfLineSegment = getAllPixelsOfLineSegment(image, lineSegment);
  //const borderPixel = pixelsOfLineSegment[pixelsOfLineSegment.length - 1];
  //console.log("Border pixel: ", borderPixel);
  for (let p = 0; p < pixelsOfLineSegment.length; p++){
    const pixel = pixelsOfLineSegment[p];
    const pixelColor = Jimp.intToRGBA(image.getPixelColor(pixel.x, pixel.y));
    if (pixelColor.a === 255){
      //console.log(pixel.x, pixel.y, pixelColor, "Deg:", degrees, "PixOfLine:", pixelsOfLineSegment.length);
      return {pixel, pixelColor, pixelsOfLineSegment};
    }
  }

  return {pixel: null, pixelColor: null, pixelsOfLineSegment};
};


const expandFromPixelToBorder = (image, pixel, pixelColor, pixelsOfLineSegment) => {
  pixelsOfLineSegment.forEach(pixelOfLineSegment => {
    const intColor = Jimp.rgbaToInt(
      pixelColor.r,
      pixelColor.g,
      pixelColor.b,
      pixelColor.a
    );
    image.setPixelColor(intColor, pixelOfLineSegment.x, pixelOfLineSegment.y);
  });
};


const expandPath = (originalImage, newImage, degrees) => {
  const {pixel, pixelColor, pixelsOfLineSegment} = findFirstColoredPixel(originalImage, degrees);
  if (pixel){
    expandFromPixelToBorder(newImage, pixel, pixelColor, pixelsOfLineSegment);
  } else {
    console.log("Not expanded. No pixel found! Degrees = " + degrees);
  }
};

const expand = (originalImage, newImage) => {
  const steps = Math.floor((END_ANGLE - START_ANGLE) / STEP_IN_DEGREES);

  console.log(steps + " steps");
  let s = 0;
  let degrees = START_ANGLE;
  while (degrees < END_ANGLE){
    expandPath(originalImage, newImage, degrees);
    s++;
    degrees += STEP_IN_DEGREES;

    if (s % 100 === 0){
      console.log(s + "/" + steps + " steps completed");
    }
  }
};

const readPromise1 = Jimp.read(FILENAME);
//read file again to obtain duplicate copy to overwrite
const readPromise2 = Jimp.read(FILENAME);

Promise.all([readPromise1, readPromise2])
  .then(([originalImage, newImage]) => {
    console.log(
      "Dimensions: " + originalImage.bitmap.width + "x" + originalImage.bitmap.height
    );
    expand(originalImage, newImage);
    newImage.write(NEW_FILENAME);
  });

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.