Skip to content
Real-time image segmentation based on Kruskal's minimum-spanning-tree algorithm.
JavaScript HTML CSS
Branch: master
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
build add build folder to repo, to be able to deploy to gh-pages Sep 11, 2017
src update github ribbon Sep 11, 2017
.gitignore
LICENSE
README.md link to github pages in readme Sep 11, 2017
build.js add uglifyify Sep 11, 2017
package.json add uglifyify Sep 11, 2017
server.js refactor round 1; add readme.md Apr 8, 2017

README.md

Real-Time Image Segmentation

Image segmentation is the process of partitioning a digital image into multiple segments. This project deals with image segmentation of directly streamed video from a webcam in real-time.

Try the app: Real-Time Image Segmentation

The whole application runs in the browser. There is no communication with the server whatsoever (other than initial page load, of course).

Dependencies

  • Node.js
  • npm

How To Run and Develop

To build the project with watcher, and run local server over https, run:

npm start

If you just want to start a local https server, run:

node server

If you just need to build the project and start watcher:

node build

Buildig the project means creating folder build and placing in it all the neccessary files needed to run the project in browser.

Note: to use webcam API, page must be downloaded from secure server. (Hence the https server to be able to run and debug in local network).

About the Implementation

In order to maintain undistracted video streaming from the webcam, streaming is done in the main thread while segmentation is done in the background thread.

Image is converted to weighted graph. Pixels are represented by nodes and neighbor pixels are connected with an edge. Weights of the edges are determined by calculating similarity between pixels.

Next, segmentation is done by grouping similar pixels. Algorithm for grouping is similar to Kruskal's algorithm for finding minimum spanning tree. The difference is that every time when two sets are to be connected, a test for similarity between them is being done. Similarity test is done by subtracting average colors between sets and comparing the difference with the threshold. (Mahalanobis and Bhattacharyya distance have been tried here, but there was no obvious advantage and there was a great performance disadvantage of using those).

Union-find data structure is implemented by using typed array to achieve performance boost.

Overall complexity of the algorithm is O(n·α(n)), where n is a number of pixels, and α(n) is the inverse of the single-valued Ackermann function. Given that α(n)<4 for any practical value of n, we have amortized linear time complexity.

License

This software is released under the MIT license.

You can’t perform that action at this time.