Intelligent scissors

[mattmagic149]

Hey,

I am trying to extend the polygon and polyline tool to snap to a contour. This would make the annotation process for objects with a strong gradient more efficient. I am planning to implement a variation of "Intelligent Scissors for Image Composition" by Eric N. Mortensen & William A. Barrett.

For this purpose I'd need access to the click event when adding/editing a point while in creation mode for polygons/polylines, as well as the gradient information of the image.
The later one I could pre-compute or calculate it once the "magnetic mode" is activated.

Does anyone have a hint for me which parts of the engine are crucial to achieve this?

Cheers,

Matt

[bsekachev]

@mattmagic149 Hi Matt,

Your proposal looks like good.
You can add event listener when a poly shape is being drawn.
Please, refer to: engine -> shapeCreator.js -> ShapeCreatorView class -> _createPolyEvents() method.
Two events are responsible for new point: drawstart (for a first point) and drawpoint (for other points).
Keep in mind that there is also the event in order to cancel last drawn point: undopoint.
Similar way in case when poly shapes are being editing.
engine -> polyshapeEditor.js -> PolyshapeEditorView class -> _startEdit() method.

It would be fine if you make the functionality like external library which can be attached to CVAT.
Also we found some javascript implementation here. It can be used for development.

[mattmagic149]

Hey thanks for the quick response.
Having a solution which is a third party app would be great. I think a toolbox for different segmentation tools (all which are producing polygon like shapes) would be helpful.

How would you start the development to make it a third party tool?
I was thinking about inheriting from the current shapeCreatorView and override the _createPolyEvents() method. Next detach the current viewer and subscribe the new viewer.
Is there a better way to achieve this?

Cheers,
Matt

[nmanovic]

Hi Matt,

I believe first step is to create a JS library which implements necessary algorithms. It will be quite trivial to integrate after that into CVAT. We will help with that for sure.

[mattmagic149]

Hi nmanovic,

yes you are right that the first step should be the algorithmic implementation.
However, since there are multiple implementations around I was more worrying about the integration part.
There is also an livewire implementation in python which should be fairly easy to translate to JS. Furthermore, I have an understanding of the algorithms to implement them, but I definitely need help on the integration.

[nmanovic]

Matt,

but I definitely need help on the integration.

We will help for sure. Don't worry. We will glad to add something like that. UI part is going to be redesigned. Thus just need your algorithm with a clear example how to use it (interface). After that we will advise what is the best way to integrate it.

[mattmagic149]

Nikita,

thanks for your offer. The implementation would look similar to this:

def on_mouse_click(event):
    
    # start_point is the last point the user added by click
    if start_point is None:
        start_point = (int(event.ydata), int(event.xdata))
        
    else:
        end_point = (int(event.ydata), int(event.xdata))
        
        # calculate the least costly path given by the shortest path algorithm
        # graph ist the cost from pixel to pixel calculated from the image gradient
        # path contains all pixel coordinates from start to end
        # remove points that lie on a line.
        path = shortest_path(graph, start_point, end_point, length_penalty=length_penalty)

        # add those points to the polygon
        plt.plot(np.array(path)[:,1], np.array(path)[:,0], c='r')
        plt.draw()
        start_point = end_point

def on_mouse_move(event):
    end_point = (int(event.ydata), int(event.xdata))
    
    # same as above
    # points are not added to the polygon yet.
    # visualize the path from the last point the user added to the mouse pointer
    path = shortest_path(graph, start_point, end_point, length_penalty=length_penalty)
    
    global current_path
    if current_path is not None:
        current_path.pop(0).remove()

    # show the path in the player
    current_path = plt.plot(np.array(path)[:,1], np.array(path)[:,0], c='r')
    plt.draw()

In essense I need to calculate a cost graph based on the image gradient.
This could be done once the magnetic tool is activated or a new image is loaded to the player.
A callback to a user click is needed to update the polygon by all intermediate supporting points plus the users click.
For the user to see which path/contour in the image is taken another callback for the mouse move is required.

Let me know if you need additional information.

Cheers,
Matt

[rsnk96]

This magnetic lasso / intelligent scissors would be a very useful feature to have. It could possibly be implemented by changing what happens when we press Shift (in this line)

A good reference pseudo-code is in the Wikipedia page for livewire

There are also a couple of JS implementations that could be used for reference in addition to what has already been linked:

1. https://github.com/Chronos-Sk/intelligent-scissors-js
2. https://github.com/liangmicha/mithack2/blob/f6da2c257550591b9fbcd85d52fc5c876fea4565/image_viewer/src/math/scissors.js

[dkurt]

@rsnk96, Hi! We already started development on intelligent scissors algorithm based on paper in issue's description. Please keep in touch on this issue.

[nmanovic]

@rsnk96 , don't hesitate to contact @dkurt if you want to participate in the development process. They want to implement the algorithm for OpenCV library on C++. After that they are going to port it to OpenCV.js

[rsnk96]

@dkurt let me know if I can help in any way. There is an implementation available in C here

[benhoff]

There's a $100 bounty on this issue if anyone is interested.
https://www.bountysource.com/issues/70724425-intelligent-scissors