@mshabunin Any thoughts about this?

Can you please comment why hitMap should be an external object rather than internal algorithm's part?

why?

getContour() was added significantly later that other methods (to simplify users code).

Perhaps it makes sense to move it itside. But need to avoid possible confusion about the strong sequence of called operations: apply => calculate => getContour (hitMap parameter requires to calculate that directly before getContour() call).

It seems for me that current approach with separated calcutateHitMap + getContour may help to build more flexible algorithm (i.e. with Ctrl+Z behavior to make a step back to previous algo state and rebuild the contour to different point).

Lets keep API simple for the first iteration.

Flexible and more optimized variant with partial map calculation can be added later. Currently it computes all paths even for 4K images which is slow enough.

Storing hitMap in Undo stack has own issues (memory usage)

Changed:

• removed hitMap in/out parameters. This map is stored as field of the class.
• renamed calcutateHitMap => buildMap (there is no hit terminology in the article).
• added const modified for the getContour method.

May we keep partial map calculation, since an interactive mode of this tool with no freezing is important for CVAT?

we keep partial map calculation

Partial calculation is not available yet (need to experiment with that first). Current implementation is full BFS internally (because task represented as Dynamic Programming (DP) problem).

Lets receive the feedback about the accuracy first.
There are several parameters which can be tuned. Also there is really poor color images support (cvtColor(BGR2GRAY) is not the best option).

Ok, get it. Thank you.

Also partial calculation can be implemented on Application side.

Idea:

• Image size is 1920 x 1080
• Start point is selected: x0, y0 = 800, 500
• Lets crop image to region near the point (x0 - 200, y0 - 200)-(x0 + 200, y0 + 200) = (600, 300)-(1000,700).
• Use this cropped image in tool

Pros:

• Result ROI will be 400x400 which works quite fast (< 500ms).

Cons:

• target points must be in this region
• possible paths outside of the region is not handled at all (possible paths should not left the region borders)
• recalculation for larger region requires computations from the scratch (it is hard to reuse existed results in practice)

JS demo code for the idea above (use "standalone" link from PR's description):

let src = cv.imread('canvasInput');
cv.resize(src, src, new cv.Size(2048, 2048));
cv.imshow('canvasOutput', src);
let searchSize = 200;
let tool = new cv.segmentation_IntelligentScissorsMB();
tool.setEdgeFeatureCannyParameters(32, 100);
tool.setGradientMagnitudeMaxLimit(200);
let roi = new cv.Rect(0, 0, src.cols, src.rows);
if (searchSize == 0) {
    tool.applyImage(src);
}
let hasMap = false;
let canvas = document.getElementById('canvasOutput');
canvas.addEventListener('click', e => {
    let startX = e.offsetX, startY = e.offsetY; console.log(startX, startY);
    if (startX < src.cols && startY < src.rows)
    {
        if (searchSize > 0) {
            roi.x = Math.max(0, startX - searchSize);
            roi.y = Math.max(0, startY - searchSize);
            roi.width = Math.min(src.cols, startX + searchSize) - roi.x;
            roi.height = Math.min(src.rows, startY + searchSize) - roi.y;
            console.log(roi);
            console.time('applyImage(roi)');
            tool.applyImage(src.roi(roi));
            console.timeEnd('applyImage(roi)');
        }
        console.time('buildMap');
        tool.buildMap(new cv.Point(startX - roi.x, startY - roi.y));
        console.timeEnd('buildMap');
        hasMap = true;
    }
    if (searchSize > 0) {
        let dst = src.clone();
        let color = new cv.Scalar(255, 0, 255, 255);  // RGBA
        cv.rectangle(dst, new cv.Point(roi.x, roi.y), new cv.Point(roi.x + roi.width, roi.y + roi.height), color, 1);
        cv.imshow('canvasOutput', dst);
        dst.delete();
    }
});
canvas.addEventListener('mousemove', e => {
    let x = e.offsetX, y = e.offsetY; //console.log(x, y);
    let dst = src.clone();
    if (searchSize > 0) {
        let color = new cv.Scalar(255, 0, 255, 255);  // RGBA
        cv.rectangle(dst, new cv.Point(roi.x, roi.y), new cv.Point(roi.x + roi.width, roi.y + roi.height), color, 1);
    }
    if (hasMap && x >= roi.x && x < roi.x + roi.width && y >= roi.y && y < roi.y + roi.height)
    {
        let contour = new cv.Mat();
        tool.getContour(new cv.Point(x - roi.x, y - roi.y), contour);
        let contours = new cv.MatVector();
        contours.push_back(contour);
        let color = new cv.Scalar(0, 255, 0, 255);  // RGBA
        let dst_roi = dst.roi(roi);
        cv.polylines(dst_roi, contours, false, color, 1, cv.LINE_8);
        contours.delete(); contour.delete(); dst_roi.delete();
    }
    cv.imshow('canvasOutput', dst);
    dst.delete();
});
canvas.addEventListener('dispose', e => {
    src.delete();
    tool.delete();
});

Use searchSize = 0 to rollback for whole image optimizations.

P.S. Check browser's "console" for time measurements (F12 hotkey)

Placeholder for naming discussion.

👍 for IntelligentScissorsMB1995. We already have such experience with background subtractors, in example. It will be much more easier to introduce a common IntelligentScissors later.

BTW, Maybe just IntelligentScissorsMB or IntelligentScissorsMB95?

IntelligentScissorsMB sounds good to me.

renamed to IntelligentScissorsMB