B. Kegl
The Java Implementation of
the Principal Graph Algorithm
The program generates the skeleton
graph of handwritten characters by using the Principal Graph
Algorithm. The software can be run as an applet, or as an standalone application by downloading
the Java classes (zip), and executing the PrincipalCurve.SkeletonizationGUI
class. If you want to experiment with your own data, you have
to download and run the program as an application.
For the most serious, the source code (zip)
is also available It is free for non-commercial use, and you can apply
it to your data, modify it, and integrate it
into another program as long as you notify me beforehand. I am not responsible for any
implications from the use of this software.
User's manual
Data
- You can download 1000 hand-written
digits by using the "Template -> Built-in templates..." menu. You can also access
other data sets by downloading them from here.
- You can load and download
templates by using the "Template -> Load template..." and "Template ->
Download template..." menus, respectively. You have
to specify the name of a bitmap file that contains the width
and height of the image in the first line, then the pixels
(0=white, 1=black) separated by white spaces. See some examples
here.
If
there is a file called pgraph.dta in
the same directory as the template bitmap, it will be loaded and used as an initial
skeleton graph. It must contain one or several curves in the following
format. Each line contains one point, and coordinates
of points are separated by a space. Curves are then created by
connecting consecutive points. Equal points will be
unified to create a graph.
- You can save templates and
skeleton graphs by using the "Template -> Save data..." menu. The template will be saved under
the specified name while the skeleton graph will be saved in the same
directory as pgraph.dta.
- You can initialize the skeleton
graph manually by choosing the "Principal graph ->
Initialize graph..." menu. You can draw a curve in the current using the following "extended
xfig polyline
protocol".
- Start a new curve by a left click, add
new vertices by left clicks, and finish the single curve
with a middle click.
- Repeat the procedure for additional
curves, and finish the set of curves with a right click.
Any two vertices within a distance of two pixels will be
unified.
- To clear the canvas,
simply finish with a right click, and start drawing a new set of curves.
- If you want to see the
coordinates of the added vertices, turn on the "Coordinate
balloon"
checkbox.
- Press "Done" when the curve is ready.
Running
- You can run the entire algorithm by
clicking on the "Start" button. You can go step by step by using the "Initialize" , "Fit & smooth" , and "Restructure" buttons. You can stop
the fitting-and-smoothing loop by using the "Stop" button.
- You can adjust the parameters of
the algorithm by choosing the "Principal graph ->
Parameters..."
menu. The role of most of the parameters are
described here, here and here. The following is a short
summary.
- The "penalty
coefficient"
determines the trade-off between "closeness" to the data and
"smoothness" of the curve. The
larger the coefficient, the smoother the curve is.
- The "length penalty
coefficient at end segments" determines how much we penalize the
length of end-segments compared to the angle penalty at inner segments. The
larger the coefficient, the shorter the end-segments are.
- The "optimization
threshold"
determines when the fitting-and-smoothing loop would stop optimizing the
curve. The larger
the threshold, the faster the algorithm is.
- "Tau_branch" specifies the threshold under
which short branches are cut in the restructuring step.
- "Tau_loop" specifies the threshold under
which small loops will be eliminated in the restructuring step.
- "Tau_filter" is the parameter of the
polygonal approximation algorithm used in the restructuring step to
filter line-vertices. The smaller the parameter, the more vertices will
be kept.
- "Eps_star3" specifies the threshold under
which two close star3-vertices will be merged in the restructuring step.
- The initialization step can be sped up by
turning on the "Change resolution before initialization" checkbox. The new resolution
on the X axis then can be set by using the "X resolution" scrollbar. The resolution on
the Y axis will be determined automatically.
Display (appearance)
- The center panel
displays the template and the skeleton graph generated by algorithm. The initial
colors are:
You can modify
the sizes, colors and types of the points
and the curves by choosing the "Appearance -> Colors
& sizes..."
menu.
- Choose the "Appearance ->
Pack" menu if
you want to equalize the horizontal and vertical scales
after resizing the window. (If your window is too small, you might have to
click twice.)
- You can save the displayed image
directly into a postscript file by choosing the "Template
-> Save image..." menu. The properties of the postscript
image are determined by the colors, sizes, and
types of the points and curves. Other properties can be set in
the upcoming dialog.
Known bugs
- Under SunOS and Solaris,
Netscape 3.x and and 4.x seem to have problems
with the applet. Try Netscape
2.x. The standalone application runs fine.
- Under Windows 98,
Internet Explorer seems to run the applet much faster than Netscape.
- Under Linux you need at
least Java 1.1.
