Search code examples
javascriptnode.jsimage-processingsharpconnected-components

How to detect the number of disconnected regions in a PNG using Javascript?

How to detect that there are (for example) 3 disconnected regions within the PNG below? Is there a technique or library someone could kindly refer me to? Not sure how to even start with this one. I'm thinking maybe there exists a function in an image processing library that will decompose a PNG into an array of buffers for each image region detected.

Thanks!

PNG with disconnected regions

Solution

  • This tutorial seems to do what you need, but in Python:

    https://www.geeksforgeeks.org/how-to-detect-shapes-in-images-in-python-using-opencv/

    You can try to copy the code and parts of the logic from that Python code and use this question (and answer) as a foundation:

    How to access data from findContours() in opencv js

    Here is another SO question that can be helpful in how to work with contours:

    mask after finding shape's contour

    However, this approach assumes you are running Node JS, not a browser JS.

    Please let me know if this helps.

    UPDATE:

    I had some spare time and thought trying the approach I suggested in my answer would be nice.

    Here we go - a non-optimized implementation of the algorithm that searches for shapes by filling them with different colors.

    Comment out the line await delay(1); to see it running at full-speed without animation.

    <html>

<head>
  <style>

  </style>
</head>

<body>
  <canvas width="800" height="600"></canvas>
  <script>
    const canvas = document.querySelector('canvas');
    const ctx = canvas.getContext('2d');

    const delay = (msec) => {
      return new Promise((resolve) => {
        setTimeout(resolve, msec);
      });
    };

    const getPixel = (x, y) => {
      const pixel = ctx.getImageData(x, y, 1, 1);
      return [pixel.data[0], pixel.data[1], pixel.data[2], pixel.data[3]];
    }

    const setPixel = (x, y, rgba) => {
      const pixel = ctx.getImageData(x, y, 1, 1);
      pixel.data[0] = rgba[0];
      pixel.data[1] = rgba[1];
      pixel.data[2] = rgba[2];
      ctx.putImageData(pixel, x, y);
    }

    const fillShape = async(shape) => {
      while (pos = shape.queue.pop()) {
        let pixel = getPixel(pos.x, pos.y);
        if (!isBackground(pixel) && !isScanned(pixel)) {
          setPixel(pos.x, pos.y, [255, 0, 0]);

          if (pos.x < shape.bounds.x1) {
            shape.bounds.x1 = pos.x;
          }
          if (pos.x > shape.bounds.x2) {
            shape.bounds.x2 = pos.x;
          }
          if (pos.y < shape.bounds.y1) {
            shape.bounds.y1 = pos.y;
          }
          if (pos.y > shape.bounds.y2) {
            shape.bounds.y2 = pos.y;
          }

          if (pos.x - 1 >= 0) {
            shape.queue.push({
              x: pos.x - 1,
              y: pos.y
            });
          }
          if (pos.x + 1 < img.width) {
            shape.queue.push({
              x: pos.x + 1,
              y: pos.y
            });
          }
          if (pos.y - 1 >= 0) {
            shape.queue.push({
              x: pos.x,
              y: pos.y - 1
            });
          }
          if (pos.y + 1 < img.height) {
            shape.queue.push({
              x: pos.x,
              y: pos.y + 1
            });
          }

          await delay(1);
        }
      }
    };

    const isBackground = (pixel) => {
      return pixel[0] === 255 && pixel[1] === 255 && pixel[1] === 255;
    }

    const isScanned = (pixel) => {
      return pixel[0] === 255 && pixel[1] === 0 && pixel[2] === 0;
    }

    const detectShapes = async() => {
      const shapes = [];
      for (let y = 0; y < img.height; y++) {
        for (let x = 0; x < img.width; x++) {
          const pixel = getPixel(x, y);
          if (!isBackground(pixel) && !isScanned(pixel)) {
            const shape = {
              bounds: {
                x1: 999999,
                y1: 999999,
                x2: -1,
                y2: -1,
              },
              queue: [],
            };
            shape.queue.push({
              x,
              y
            });
            await fillShape(shape);
            shapes.push(shape);
          }
        }
      }
      return shapes;
    };

    const img = new Image();
    img.crossOrigin = "Anonymous";
    //img.src = "shapes.png";
    img.src = "data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAWAAAADuCAYAAAAHrN1QAAAACXBIWXMAAA7EAAAOxAGVKw4bAAAAPHRFWHRDb21tZW50AHhyOmQ6REFHQlU0Nk95aG86MTIsajo2NTUzMTYxNjQ5NDg0NDI5MDYzLHQ6MjQwNDA4MDR2VTdVAAAFBmlUWHRYTUw6Y29tLmFkb2JlLnhtcAAAAAAAPHg6eG1wbWV0YSB4bWxuczp4PSdhZG9iZTpuczptZXRhLyc+CiAgICAgICAgPHJkZjpSREYgeG1sbnM6cmRmPSdodHRwOi8vd3d3LnczLm9yZy8xOTk5LzAyLzIyLXJkZi1zeW50YXgtbnMjJz4KCiAgICAgICAgPHJkZjpEZXNjcmlwdGlvbiByZGY6YWJvdXQ9JycKICAgICAgICB4bWxuczpkYz0naHR0cDovL3B1cmwub3JnL2RjL2VsZW1lbnRzLzEuMS8nPgogICAgICAgIDxkYzp0aXRsZT4KICAgICAgICA8cmRmOkFsdD4KICAgICAgICA8cmRmOmxpIHhtbDpsYW5nPSd4LWRlZmF1bHQnPkNvcHkgb2YgQWRoZXNpdmUgTWlzY2hpZWYgSG9tZXBhZ2UgVGlsZXMgLSA0NjwvcmRmOmxpPgogICAgICAgIDwvcmRmOkFsdD4KICAgICAgICA8L2RjOnRpdGxlPgogICAgICAgIDwvcmRmOkRlc2NyaXB0aW9uPgoKICAgICAgICA8cmRmOkRlc2NyaXB0aW9uIHJkZjphYm91dD0nJwogICAgICAgIHhtbG5zOkF0dHJpYj0naHR0cDovL25zLmF0dHJpYnV0aW9uLmNvbS9hZHMvMS4wLyc+CiAgICAgICAgPEF0dHJpYjpBZHM+CiAgICAgICAgPHJkZjpTZXE+CiAgICAgICAgPHJkZjpsaSByZGY6cGFyc2VUeXBlPSdSZXNvdXJjZSc+CiAgICAgICAgPEF0dHJpYjpDcmVhdGVkPjIwMjQtMDQtMDg8L0F0dHJpYjpDcmVhdGVkPgogICAgICAgIDxBdHRyaWI6RXh0SWQ+MTJjZTQ0OWEtNTY0My00YWFiLWExNWEtMWQ3MjVjY2ExY2JlPC9BdHRyaWI6RXh0SWQ+CiAgICAgICAgPEF0dHJpYjpGYklkPjUyNTI2NTkxNDE3OTU4MDwvQXR0cmliOkZiSWQ+CiAgICAgICAgPEF0dHJpYjpUb3VjaFR5cGU+MjwvQXR0cmliOlRvdWNoVHlwZT4KICAgICAgICA8L3JkZjpsaT4KICAgICAgICA8L3JkZjpTZXE+CiAgICAgICAgPC9BdHRyaWI6QWRzPgogICAgICAgIDwvcmRmOkRlc2NyaXB0aW9uPgoKICAgICAgICA8cmRmOkRlc2NyaXB0aW9uIHJkZjphYm91dD0nJwogICAgICAgIHhtbG5zOnBkZj0naHR0cDovL25zLmFkb2JlLmNvbS9wZGYvMS4zLyc+CiAgICAgICAgPHBkZjpBdXRob3I+VGVvZG9yYSBNaXNjb3Y8L3BkZjpBdXRob3I+CiAgICAgICAgPC9yZGY6RGVzY3JpcHRpb24+CgogICAgICAgIDxyZGY6RGVzY3JpcHRpb24gcmRmOmFib3V0PScnCiAgICAgICAgeG1sbnM6eG1wPSdodHRwOi8vbnMuYWRvYmUuY29tL3hhcC8xLjAvJz4KICAgICAgICA8eG1wOkNyZWF0b3JUb29sPkNhbnZhPC94bXA6Q3JlYXRvclRvb2w+CiAgICAgICAgPC9yZGY6RGVzY3JpcHRpb24+CiAgICAgICAgCiAgICAgICAgPC9yZGY6UkRGPgogICAgICAgIDwveDp4bXBtZXRhPqDU8FYAABQ0SURBVHic7d15dFxnecfx38xII3kkWbIseZFkW47jxK5JwmLHoaSccCilLAmULrQUCoct3SilpSchB0hoICV16jaFsiQECCE0DWFNUg7d28CJfWyO3QRvseNI1mpZu7WMZrv9w1GiypLuSJqZ9973/X7+hBP7kaX56s6d594b8TzPEwCg5KKmBwAAVxFgADCEAAOAIQQYAAwhwABgCAEGAEMIMAAYQoABwBACDACGEGAAMIQAA4AhBBgADCHAAGAIAQYAQwgwABhCgAHAEAIMAIYQYAAwhAADgCEEGAAMIcAAYAgBBgBDCDAAGEKAAcAQAgwAhhBgADCkzPQAABaWyXnqmkzrzERKvcm0xjM5jWezyuQ8ZT0p63mKRiKKRqRYJKJELKpELKq6eEwbE3FtSsRVUx4z/WVgDgQYCJDhVFYHBsd1YGhcJ85P6cxESt2TKWW95f25q8pj2lh1IcYvX5XQ1fVV2lpdoUgkUpjBsSQRz/OW+a0FsFSe5+nQ8KR+1DOifQPjOn4+qVK9IOvjMV1dX6Xr1tTo9WtXcpRsAAEGDDg+mtSj3cN6rGdEXZNp0+MoHo3oNY01ur65Vq9prFFFjI+HSoEAAyXSOZHSD5+P7jPnp0yPM6/qsqhev3albmiu0zWrqxTjNEXREGCgyHqSad13ul8PdwxpIpszPc6i7FyV0I1bGnVdYzXni4uAAC9S1vOUydnzTxaJSPEobzeL4fTYlO45fU4/6BpROuQvs8trKnXjlga9cX2tyghxwRDgPLSNT+nbHUN6on9Mx0eTCtcxjL+GijJdvSqhNzXV6nVrVyrKC2xZhlNZ3fVMrx4+M2Tdz8rlNRX6+Pb1emVDtelRrECAF9CXTOvuk316pHNo2WtAYXFZdYU+tn29fqmRF9hiZT1PD7YP6u6TfRpJZ02PU1RvWLdSN29fp+YVcdOjhBoBnsfPRyb1wYPt6pvKmB7FiD/c0qiPXL5WHAvnZ9/AuG4/2q0TAf5wrdAqohHduKVRH7ykQZVsTSwJAZ7D0ZFJvXN/m0Yzdh/F+Hn/JQ26eds602MEWtbz9A+nzulzJ/tKtr8bNFfUrtDdL9ugjQmOhheLAM8yks7qLT85pc4A7GYGwd6rWnRDc53pMQKpL5nWRw53av/guOlRjKspi+rTVzTrTetrTY8SKrxvmOWuE73Ed4bbj/ZoMOXmaZiF/Fffeb3piVPE93nnMzl9+FCHPv50l5IhW7UziQDP0JdM65HOYdNjBMpQOqsH2wdNjxEo97cN6AMH2zVk+QdtS/FQx5Detb9NQ/zSzgsBnuHxnlGlLdrxLZTvdA6JM1UX7ttw1/Fe3X60x9nzvfk4NDyhtz/5nHp4J+mLAM/w0/4x0yMEUudkOhD3KzAp43m66akufel0v+lRQuH0+JR+68nTOnk+aXqUQCPAM5zgh2VeHRMp0yMYk8zm9Ec/O6PvdnF6ajF6kmn9zr7n9LMhzpPPhwDPMJzmvNV8hh0935nzPP354U79e99506OE0nA6qw8caNexUQ5u5kKAZ3DlarelcPFzbc+TbjvSrR+fHTU9SqiNZnJ6/4E2dTr8Lmo+BBiYx90nz+pbZ4ZMj2GFs1MZvecA2xGzEWBgDt9qH9TnT50zPYZV2sZTeu+Bdk1kXHw/NTcCDMxycHBcnzrabXoMKz09Mqlbnu4yPUZgEGBghqFURn96uIPPA4rosZ4RPXSGi3skAgy8wPOkj/5vp3qTnKcsts8c62FHWAQYeMH9bf3673NcjFMKk1lPHzrUEbpHNBUaAQYknTqf1J3Hz5oewymnxqa053iv6TGMIsCApFuP9IT+uW1h9OCZQaevQCXAcN7jPSPcVtKQnCd9/OkuZ2/2RIDhtLFMVn91zO23waYdGp7U97tGTI9hBAGG0z5/8px6k27f6S0I7jzRqzEHHwFGgOGsvmRa97cPmB4DkvqnMvqKg7f6JMBw1lfbBrgBf4A80D6oScfW0ggwnDSazuofuRorUEbSWT3c4dbNjwgwnPTN9gGNc1OYwLnvdL8yDr0rIcBwzmQ2p/vbOPoNou5kWo92u/PkEQIM5/yoZ0QD3Jc2sB5w6CncBBjOebTbzZ3TsHhqZFKnx6ZMj1ESBBhOGUhlePp1CDzW48YvSQIMp/ywa9jJ59uFzfc6h+TCR3EEGE7h9EM4dEymdXhowvQYRUeA4YxzU2k9NTJpegzk6d8ceBo1AYYz9g9wx7Mw2efAHeoIMJzxBE+7CJUjI5PWXyxDgOEMF46obJLxpINDdn/PCDCc0DmRUtckt50Mm32WnzYiwHDCQQc+UbfRkwQYCL9TY+4+dyzMnh2bsvpxRQQYTjg9ljI9ApZgMptT35S99+0gwHBC+4Qb9xaw0XPj9v7yJMCwXtbz1Gbxi9h2beP2/vIkwLDe2WRaUw7d5Ns2HRP2bq8QYFhvIOXe03ZtMpAiwEBo2X41le1SFr97IcCwXtKxJ+3aZsLi7x8BhvVsfgG7gCNgIMQ4Ag63CYtPIRFgWI8j4HBLcyUcEF6JGD/mYVYWiZgeoWj4yYT1KglwqFWV2fv9s/crA57HEXC4xaMcAQOhVW3xEZQLbP4Fau9XBjyvwuIXsAtWWPz9s/crA57XWFFmegQsQ125vd8/Agzrra0oU4XF5xFttyFRbnqEoiHAsF4kElFrVdz0GFii1qoK0yMUDQGGEzYl7H0R226zxb88CTCcYPOL2GbVZVGtsfgcPgGeIcZpwnmF/Qfl0mqOgMOotapCEa6Ec8PK8pjpEQKrJuT/Nrvqq0yPgCXYuSpheoSiIsAzbLH4ZP9ytawI9yfRLYm4mkP+Nbhot+W/OAnwDLtX2/3NXqq1lWXamAj/OVTbX8y2icj+dy4EeIa3NNXxDzKHtzbVKWrBeTh+wYbLtppK1cXDferLD72ZoSUR1/VNtabHCJTKaETval1teoyC4Ag4XFz4hUmAZ7l5+zrVW/5bdzE+um2d1lXace60JRHX9ppK02MgT7+8dqXpEYqOAM/SWFGuv33pBpVz6are3FSr91hy9Dvthmbe4YRBy4py7a63ewNCIsBzelVDtb78io1W3wbPz1ub63TXlS2mxyi46znPHwpvbqqzev93Gj+L83h1Y41+cO0WXdtQbXqUklodL9PtL2nSXVe1qMzCdwHrKsv1i459T8Po15rrTI9QEvZe41cAm6sq9PWrW7VvYFwPnRnUE/1jGklnTY9VcLGItGPlCl3fVKvf3lhv9f1XJen6plr9pH/M9BiYx5W1K7TFkSsXI55n8SNHi2AwlVnSY7If7hjSF549V4SJLthWU6m/uapl0c/PikUiaqgoc+qc92Q2p+v+8xkNpDKmR8Ec7ryyWb/essr0GCVBgEvgwfZB3Xqku+h/z85VCd23a5Oqytji8POFU33a+0yf6TEwS1Nluf7jususPP01F7vfawZAqeIrSQeHJvS+A+0az9h3mqTQ3rlptWp4VlzgvO+SBmfiKxHgoiplfKcR4fysLI/pnZvsWrELu9XxMr19gxunHqYR4CJ56Ezp4zuNCOfn3a2rVenQ0VbQvbu1XpWWfwA8m1tfbYl8u2NIn/i5mfhOI8L+GirK9N7NDabHgC48t+/3LLvoJx8EuMC+3TGkW57uUhA+2STC/v7g0kZrLrUOs5u2r1O1gx8eE+ACClJ8pxHhha2IRXXL9nWmx3Da7voqXb/ezUvECXCBBDG+04jwwt64vpY7pRkSjUif3LHeicuO50KACyDI8Z1GhBd26471KnM0Aib97sZ6Xe7wHeoI8DKFIb7TiPD8Lqup1E3b1poewymXVlfo5m1un/4hwMsQpvhOI8Lze09rg17nwD1og2BFLKLPvWyDKhxbO5vN7a9+GcIY32lEeG6RiPTZK5vVxMM7i+62HU3a6vCph2kEeAnCHN9pRHhuteUx7b2qRTFOBxfN25rrnLnZjh8CvEg2xHfadIQns4u/u5vNdtZX6dMvaTY9hpVeVrdCt+1oMj1GYBDgRbApvtMODk3oAweJ8Gy/uWGVPrx1jekxrHJpdYXu2blJCW6C9AL+JfJkY3yn7RsYJ8Jz+NDWNXrHxnrTY1hhXWWZvrprk1bFeQbETAQ4DzbHdxoRntttO9brV9iMWJaVZVHdu7NVTSvipkcJHALsw4X4TiPCF4tGItr70ha9Zk2N6VFCqbY8pnt3tWr7SjYe5sITMRbgUnxnumZ1le7ducn6Z8MtRibn6ZNHuvVwx5DpUULjwmmHVl3Gutm8CPA8XI3vNCJ8MU/S3hNn9cUiPtvPFlurK/TVXa1az071ggjwHFyP7zQiPLcH2gf0l0d6nP/5mM/LVyV0zys2qo4P3HwR4FmI7/9HhOf2xLnz+rPDnRpKcyHLTO/YWK9btq9z7skWS0WAZ3ikY0gfI74XuWZ1le7bucn56/Zn60um9ZHDndo/OG56FONqyqK644pmvcHR+/ouFa+oGQ4NTxDfObSNT2mYI72LrKks1zd2t+pPtq6Ry1cuX1G7Qt9/1RbiuwQcAc+Q8zzd8nSXHukcNj1KYKyrLNODuzdrU1WF6VECbd/AuD51pFsnx6ZMj1IyFdGI3n9Jg/740jUq5+GmS0KAZyHCLyK+i5PJefpG+4D+/mSfxjJ271Jf11itT+5o0sYEF1csBwGeAxEmvsvRP5XRZ4/36vtd9v38bEzE9YlfWM+FKQVCgOfhcoSJb2EcG03q3tPn9HjPiLIhf5Vtrorrg5c06i3NdYpzuqFgCPACXIww8S28jomU7nuuX490DCmZC9fL7aq6Ffr9LY167ZoaRXlmXsERYB8uRZj4FtdAKqN/OjOoR7tHAv1hXVUsqtetW6m3b1ilXTwtuqgIcB5ciHBjRZkeuob4lsrR0Un9sGtEj/UMqzeZMT2OyiIRvbqxWjc01em1a2u48KZECHCebI5wY0WZvrl7s7ZUE99Sy3mejowm9dP+Mf2kf0w/G5pQukSnKTYl4rq2oVqvaqjWK1dXqaY8VpK/Fy8iwItgY4SJb7BMZnPaPzCuJwfGdfx8UmcmUuqeTC37Q7y68pg2VcXVmohrV32Vrm2oVgsrZMYR4EWyKcLENxwyOU9dk2mdmUipN5nWeCan8WxWmZynrCdlPU/RSETRiBSLRJSIRZWIRVUXj2ljIq5NiThHtwFFgJfAhggTX8A8zrQvQTQS0R1XNOs3WupMj7IkxBcIBgK8RGGNMPEFgoMAL0PYIkx8gWAhwMsUlggT34vx6QdMI8AFEPQIE9+LDUxldNNTnabHgOMIcIEENcLEd257TpzVd7uGtX+Ap1nAHAJcQEGLMPGd25GRSX2n88Lj5T9zrEc5zkXAEAJcYNMRvqHJ7ONZiO/87jjW+8Kjp46OJvWdEO9zI9wIcBFEIxHtuarFWISJ7/x+3Dt60UM095zo1ViGZ96h9AhwkcQMRZj4zm8qm9Mdx3ou+t8HU1l98dQ5AxPBdQS4iEodYeK7sK+1DahrMj3v/9c5kSrxRHAdAS6yUkWY+C5sYCqjLz07/1FuKufpr0/0lnAigACXRLEjTHz97Tlx1vdJxf/cM8paGkqKAJdIsSJMfP3NXDvzw1oaSokAl1ChI0x88zNz7czP0dGkvmfh4+QRTAS4xAoVYeKbn7nWzvxcOF3BWhqKjwAbsNwIE9/8zLd25qd/KsNaGkqCABuy1AgT3/wttHaWz3/LWhqKjQAbtNgIE9/8+a2d+WEtDaVAgA3LN8L18Zi+fnUr8c3T3mf81878sJaGYiPAAeAX4fp4TA/s3qzLaypLPFk4HRmZ1MMd+a2d+WEtDcVEgANivggT38VbzNqZH9bSUEwEOEBmR5j4Lt6/LmHtzA9raSiWiOfx/iposp6nPcfP6m0tdbqM+OZtKpvTr/7PSXUscfNhITde0qC/2Lau4H8u3EaAYY0vPXtOd504W5Q/Ox6N6F9evVUtiXhR/ny4iVMQsMJy1878pHKe9hQp7nAXAYYVCrF25ufxnhHW0lBQBBihV8i1Mz+spaGQCDBCr5BrZ35YS0MhEWCEWjHWzvzsZS0NBUKAEVpLvdvZcp3lbmkoEAKM0Ppa20BRdn7z/bu5WxqWiwAjlIq9duaHtTQUAgFGKJVi7cwPa2lYLgKM0Cnl2pkf1tKwHAQYoVPKtTM/rKVhOQgwQsXE2pkf1tKwVAQYoWFq7cwPa2lYKgKM0DC5duaHtTQsBQFGKJheO/PDWhqWggAjFIKwdubn8Z4RHRqaMD0GQoQAI/CCtHbm59Yj3aylIW8EGIEXpLUzP6ylYTEIMAItiGtnfvaeOKvJbLBPlyAYCDACayqb053He02PsWispSFfBBiB9bW2AbWFdLXrK8/1s5YGXwQYgRT0tTM/rKUhHwQYgfR3J4O/duaHtTT4IcAInDCtnflhLQ0LIcAInDuO9SprSbNYS8NCCDACJYxrZ35YS8N8CDACI6xrZ35YS8N8CDACI8xrZ35YS8NcCDACIexrZ35YS8NcCDACwYa1Mz+spWE2AgzjbFo78/Opo6yl4UUEGMbZtHbm5+cjrKXhRQQYRtm4duaHtTRMI8Awxta1Mz9npzL6ssUfOCJ/BBjG2Lx25uee06ylgQDDENvXzvywlgaJAMMQF9bO/LCWBgKMknNp7cwPa2luI8AoOZfWzvywluY2AoyScnHtzA9rae4iwCiZVM5zcu3MD2tp7op4HiegUBqj6awOD/Oh01zi0YiuWV1tegyUGAEGAEM4BQEAhhBgADCEAAOAIQQYAAwhwABgCAEGAEMIMAAYQoABwBACDACGEGAAMIQAA4AhBBgADCHAAGAIAQYAQwgwABhCgAHAEAIMAIYQYAAwhAADgCEEGAAMIcAAYAgBBgBDCDAAGEKAAcAQAgwAhhBgADCEAAOAIQQYAAwhwABgyP8BV6makU/LD00AAAAASUVORK5CYII=";
    img.addEventListener('load', async() => {
      console.log(img.width, img.height);
      canvas.width = img.width;
      canvas.height = img.height;
      ctx.drawImage(img, 0, 0);

      const shapes = await detectShapes();
      shapes.forEach((shape) => {
        ctx.beginPath();
        ctx.rect(shape.bounds.x1, shape.bounds.y1, shape.bounds.x2 - shape.bounds.x1, shape.bounds.y2 - shape.bounds.y1);
        ctx.stroke();
      });
    });
  </script>
</body>

</html>