Euclidean minimum spanning tree

This plugin calculates and draws an euclidean minimum spanning tree from a set of selection points. Coordinates of the EMST are available in “Results” table. The algorithm is based on:

1) 2D Delaunay Triangulation (DT) with incremental site insertion written by Paul Chew
2) JgraphT 0.9.0 under LPGL and EPL
3) Delaunay/Voronopi plugin written by Johannes Schindelin: the current plugin was inspired by Johannes' plugin but with some changes. The EMST is a sub-tree of Delaunay triangulation. Therefore the original points selection are used to create Delaunay triangulation. Corresponding edges are injected in the JGraphT code and MST is requested.


From a picture containing selection points, you are requested to choose:
1) The color of the edges
2) Approximate number of points (requested to optimized internal HashMap Java algorithm)
3) If you want corresponding edges coordinates
4) If you want a skeletonized EMST (Thomas Boudier's suggestion). It is possible to call the plugin from a macro as follows:
run(“EMST”, “color=Yellow approximate=500 export create”);


Two different outputs can be obtained from the same EMST: 1) one is an overlay added to the original picture which contains the selection points. 2) The second one is a binary picture representing one skeleton without loop which can be analyzed immediately with the plugin Analyze Skeleton


Simply download e_mst2.jar to the Plugins folder of ImageJ, restart ImageJ and use the “EMST” command in the Plugins menu.


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 the programs; if not, write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA


Free software: but please refer to Paul Chew and JgraphT 0.9.0 website which are the bases of the current plugin.


Gilbert Bigras, Cross Cancer Institute, University of Alberta, Edmonton Canada (


First release: October 19, 2014

Second release: November 16, 2014 (Addition of Skeletonized EMST) after Thomas Boudier feedback

plugin/morphology/euclidean_minimum_spanning_tree/start.txt · Last modified: 2014/11/17 08:32 by gilbertbigras
Back to top
CC Attribution-Noncommercial-Share Alike 3.0 Unported = chi`s home Valid CSS Driven by DokuWiki do yourself a favour and use a real browser - get firefox!! Recent changes RSS feed Valid XHTML 1.0