My Optical Music Recognition project is full of small challenges to overcome. Most of them originate just from the shitty OpenCV Java bindings, but occasionally I have to cope with my own design mistakes.

Problem

When I started this project, I’ve had absolutely no idea on what steps would the recognition algorithm have. Plain old EDD ™ (Experiment Driven Development). This lead to a messy GUI, a bunch of optional operations, and no failsafe execution mechanism. So I decided to create a nice step-based UI and put it on the backburner. Until now.

I started with a simple drawing of a tree of dependent operations. I quickly realized a simple N-ary tree implementation of Operation enums would suffice, but it seemed as an overkill at the same time. I would need an N-ary tree implementation, ideally with child-order preservation. Obviously I started looking for a lib, but quick google search turned up nothing. There seems to be no Java library with tree data structures of acceptable quality. And BTW no, you should not use javax.swing.tree for backend. That’s a misuse of a GUI utility. And I’m moving to JFX anyway.

Then I realized, that simply fixing the order of operations would simplify the whole process and the idea of a List-based, fixed-order pipeline was born.

Solution

The Java Enum was an obvious choice for storing the state of the algorithm execution process. However, what really saved the day was the ability to use enum values as parameters to other enums. This alone made a Tree obsolete, because all I needed was a dependency reference. Since enums are essentialy static classes, no dependency cycle problems arise. Thanks Java.

The next problem I had to take care of was the definition of operations’ order. To rely on natural Enum ordering is stupid (breakage on unthoughtful edit). But to add an integer parameter indicating the sequence index is even worse. I would have to keep track of uniqueness of the numbers and would have to rewrite the entire numbering on edit. So I simply put every item in a List and relied on the index ordering.

//Integer-based Enum ordering - Do NOT go this way, ever

public enum Operation {
    OPEN(0, null), BINARIZE(1, OPEN), DENOISE(2, BINARIZE);
  
    private final int orderIndex;
    private final Operation dependentOperation;
 
    private Operation(int index, Operation dependentOp) {
 ...

As for the actual dependency fail-safe mechanism, I simply check if the desired jump to another state is viable by comparing the indexes in the List:

• To ensure the fixed order of the pipeline: If the new state has a lower index than the current, it’s an illegal operation.
• To satisfy the dependency conditions: If the new state’s parent operation has a higher index than the current one, it obviously a too big of a leap.

/**
 * Algorithm steps.
 *
 * @author Martin Dindoffer
 */
public enum Operation {
    OPEN(null), BINARIZE(OPEN), DENOISE(BINARIZE), PROJECT_HISTOGRAMS(BINARIZE), CALCULATE_VERTICAL_LENGTHS(BINARIZE),
    HOUGH_TRANSFORM(CALCULATE_VERTICAL_LENGTHS), SKELETONIZE(HOUGH_TRANSFORM), FIND_POLYLINES(SKELETONIZE),
    FIND_STAFF_LINES(FIND_POLYLINES), REMOVE_STAFF_LINES(FIND_STAFF_LINES),
    DETECT_NOTE_HEADS(CALCULATE_VERTICAL_LENGTHS);

    /**
     * Operation that is needed to complete before this one.
     */
    private final Operation dependentOperation;

    public static final List<Operation> PIPELINE_ORDERING = generatePipeline();

    /**
     * Specifies the order of the algorithm steps in the recognition pipeline.
     *
     * @return pipeline of ordered operations
     */
    private static List<Operation> generatePipeline() {
        List<Operation> pipeline = new LinkedList<>();
        pipeline.add(OPEN);
        pipeline.add(BINARIZE);
        pipeline.add(DENOISE);
        pipeline.add(PROJECT_HISTOGRAMS);
        pipeline.add(CALCULATE_VERTICAL_LENGTHS);
        pipeline.add(HOUGH_TRANSFORM);
        pipeline.add(SKELETONIZE);
        pipeline.add(FIND_POLYLINES);
        pipeline.add(FIND_STAFF_LINES);
        pipeline.add(REMOVE_STAFF_LINES);
        pipeline.add(DETECT_NOTE_HEADS);
        return pipeline;
    }

    private Operation(Operation dependentOperation) {
        this.dependentOperation = dependentOperation;
    }

    public Operation getDependentOperation() {
        return dependentOperation;
    }

    /**
     * Decide whether this algorithm step can be executed directly after the given one.
     *
     * @param baseOperation starting (base) operation
     * @return true if the execution can be made, false otherwise
     */
    public boolean canExecuteAfter(Operation baseOperation) {
        if (PIPELINE_ORDERING.indexOf(this) <= PIPELINE_ORDERING.indexOf(baseOperation)) {
            return false; //can't move backwards in pipeline
        }
        if (PIPELINE_ORDERING.indexOf(baseOperation) < PIPELINE_ORDERING.indexOf(this.dependentOperation)) {
            return false; //can't skip needed operations
        }
        return true;
    }

    /**
     * Decide whether the given algorithm step / operation can be executed right after this one.
     *
     * @param desiredOperation algorithm step to move to
     * @return true if the execution can be made, false otherwise
     */
    public boolean canExecutionFollowTo(Operation desiredOperation) {
        return desiredOperation.canExecuteAfter(this);
    }
}

TL;DR

1. A fixed order pipeline can save a lot of trouble when designing algorithm flow.
2. Thanks to static nature of Enum values, one can do so much magic and doesn’t have to bother with object cycle dependencies.
3. Using enums and simple references is much more readable than implementing Tree hierarchies with complicated rules.
4. If you have to guarantee an order in Enumerations, use a static internal List, or similar structure to cope with future changes.