[GSOC] Vectorization of bitmaps

[ankit-kumar-dwivedi]

I'm Ankit Dwivedi a CSE Student. I'm a contributor at Synfig. I was a part of NjackWOC 18 at Synfig.
I would like to work for the project https://synfig-docs-dev.readthedocs.io/en/latest/gsoc/2019/ideas.html#vectorization-of-bitmaps
As this is something I personally feel is an important feature that Synfig must-have. Even when I'm working for graphic design I encounter a situation where I have to vectorize the raster image to increase the quality and reduce the size.
On my initial research, I found that potrace can be a good option. Inkscape uses potrace to convert the raster image to vector and I have tried that feature. I would love to have any suggestions and comments from the project mentor @blackwarthog and @morevnaproject
Hope to have an exciting summer 😊

--

Watch the progress here - https://github.com/ankit-kumar-dwivedi/synfig/commits/vectorization
Watch milestone board here - https://github.com/synfig/synfig/milestone/5

[morevnaproject]

Just want to put a project description here:

Allow to convert bitmap images to vector data with a single command, through integration with Potrace (http://potrace.sourceforge.net/).
Alternative - instead of Potrace, use an algorithm of vectorization from OpenToonz (https://opentoonz.readthedocs.io/ja/latest/drawing_animation_levels.html#converting-raster-drawings-to-vectors), which works better.

From my point of view, the vectorization algorithm of OpenToonz works better, because it identifies separate lines and outputs strokes (result = many separate Outline Layers). This is good for further editing vectorized image.

Demo - https://youtu.be/QkpeR72fOzY

The Potrace tool outputs singles region layer (result = single Region Layer), which is not very comfortable for editing. On the other hand, I believe integration with Potrace might be easier to implement (but I might be wrong).

[ankit-kumar-dwivedi]

The Potrace tool outputs singles region layer (result = single Region Layer), which is not very comfortable for editing. On the other hand, I believe integration with Potrace might be easier to implement (but I might be wrong).

Well.. yes it seems easy to integrate potrace with synfig that's because it is documented and being used by several other projects. However, on trying myself, I found opentoonz is better and have more accuracy and options.
On finding about the algorithm they use I was unable to directly find any algorithm mentioned anywhere which they use for the raster to vector conversion. Sadly I found no developer documentation for opentoonz :( This means I need to analyze the process and identify the necessary steps which are required so I will let you know after I investigate further.

@morevnaproject Also can you please let me know how much work to be done before gsoc start? I am asking this in regards to point no 2 under the gsoc application faq.

Show evidence of past experience or achievements related to the proposal.

What is the priority of this project?
I hope I have not chosen the least priority project 😓

[morevnaproject]

On finding about the algorithm they use I was unable to directly find any algorithm mentioned anywhere which they use for the raster to vector conversion. Sadly I found no developer documentation for opentoonz :( This means I need to analyze the process and identify the necessary steps which are required so I will let you know after I investigate further.

git grep "Convert to Vectors" in opentoonz sources dir gives me:

...
toonz/sources/toonz/mainwindow.cpp:  createMenuLevelAction(MI_ConvertToVectors, tr("Convert to Vectors..."), "");
...

So, name of the action is MI_ConvertToVectors. So I did git grep MI_ConvertToVectors and got this:

stuff/profiles/layouts/rooms/Default/menubar_template.xml:    <command>MI_ConvertToVectors</command>
stuff/profiles/layouts/rooms/StudioGhibli/menubar_template.xml:    <command>MI_ConvertToVectors</command>
stuff/profiles/layouts/rooms/StudioGhibli/room4_menubar.xml:    <command>MI_ConvertToVectors</command>
stuff/profiles/layouts/shortcuts/defopentoonz.ini:MI_ConvertToVectors=
stuff/profiles/layouts/shortcuts/otadobe.ini:MI_ConvertToVectors=
stuff/profiles/layouts/shortcuts/otharmony.ini:MI_ConvertToVectors=
stuff/profiles/layouts/shortcuts/otretas.ini:MI_ConvertToVectors=
toonz/sources/toonz/castselection.cpp:    // enableCommand(m_browser, MI_ConvertToVectors, &CastBrowser::vectorize);
toonz/sources/toonz/castviewer.cpp:  // MI_ConvertToVectors se sono stati selezionati solo livelli non vettoriali
toonz/sources/toonz/castviewer.cpp:    menu->addAction(cm->getAction(MI_ConvertToVectors));
toonz/sources/toonz/mainwindow.cpp:  createMenuLevelAction(MI_ConvertToVectors, tr("Convert to Vectors..."), "");
toonz/sources/toonz/menubar.cpp:  addMenuItem(levelsMenu, MI_ConvertToVectors);
toonz/sources/toonz/menubar.cpp:  addMenuItem(levelMenu, MI_ConvertToVectors);
toonz/sources/toonz/menubarcommandids.h:#define MI_ConvertToVectors "MI_ConvertToVectors"
toonz/sources/toonz/vectorizerpopup.cpp:    MI_ConvertToVectors);

So, I believe it is good to start looking in toonz/sources/toonz/vectorizerpopup.cpp.

Also can you please let me know how much work to be done before gsoc start? I am asking this in regards to point no 2 under the gsoc application faq - "Show evidence of past experience or achievements related to the proposal."

About achievements related to proposal I would like to see the following:

• One feature, which is related to adding a new item in Layer's right-click menu. I think "Edit in External Tool" Options #516 is a very good candidate for that.
• If we will choose to go with OpenToonz, then I ask you to describe in your project proposal the main logic of vectorization code. This shouldn't be a detailed description - just show me an understanding where (in which files/functions) the main logic is coded. ^__^

What is the priority of this project?
I hope I have not chosen the least priority project

The priority of project doesn't plays any role when we choosing who will participate in our GSoC activities. When choosing students we are looking at:

• How many code contributions student has done to Synfig.
• How complex those contributions are.
• How many of his/her contributions are related to his proposal (or does he/she has a previous experience with related topics).

Also other things we consider:

• If contributor has experience with other projects.
• Personal motivation of the student.

[ankit-kumar-dwivedi]

@morevnaproject I have few things to ask regarding opentoonz codebase should I ask here or mail you?

[morevnaproject]

@ankit-kumar-dwivedi It's better to ask here. It's possible @blackwarthog might want to join our discussion. ^__^

[ankit-kumar-dwivedi]

@morevnaproject okay
I needed to ask that the function doVectorize (which is calling vCore.vectorize(..some args..) where the actual thing is happening)
is responsible for raster to vector which is defined in vectorizerpopup.h/cpp
https://github.com/ankit-kumar-dwivedi/opentoonz/blob/bcc4cf8c2922ff7de541d6eb715f6ff3dde63f86/toonz/sources/toonz/vectorizerpopup.cpp#L212-L226

and is called in
https://github.com/ankit-kumar-dwivedi/opentoonz/blob/bcc4cf8c2922ff7de541d6eb715f6ff3dde63f86/toonz/sources/toonz/vectorizerpopup.cpp#L304

which in turn is called in run()

then why?? start() is called and not run() when convert button is pressed 😕
https://github.com/ankit-kumar-dwivedi/opentoonz/blob/bcc4cf8c2922ff7de541d6eb715f6ff3dde63f86/toonz/sources/toonz/vectorizerpopup.cpp#L970

EDIT : I guess it is related to multithreading, in java also there is run() and start() function I have done multithreading in java not C++ but it's quite similar I guess.

[morevnaproject]

then why?? start() is called and not run() when convert button is pressed

As you can see from https://github.com/ankit-kumar-dwivedi/opentoonz/blob/bcc4cf8c2922ff7de541d6eb715f6ff3dde63f86/toonz/sources/toonz/vectorizerpopup.h#L265 Vectorizer class is based on QThread class.

From QT documentation - https://doc.qt.io/qt-5/qthread.html#start -

void QThread::start(QThread::Priority priority = InheritPriority)
Begins execution of the thread by calling run().

^__^

[ankit-kumar-dwivedi]

@morevnaproject As I got your mail so I verified that there is a crash in case of using the outlinevectorizer method.

To compare "opentoonz" and "opentoonz morevna" I installed both on same Windows 10.

Also, I used the same file. On converting to vector( outlinevectorizer ) using "opentoonz" it ran successfully, however, "opentoonz morevna" crashed. So I can confirm the crash is only in morevna edition and not on original opentoonz :/
I am comparing both codebase to know what is the possible reason. Is morevna edition using the tnewoutlinevectorizer.cpp ? The crash was supposed to fix by opentoonz/pull/2057

[morevnaproject]

I am comparing both codebase to know what is the possible reason. Is morevna edition using the tnewoutlinevectorizer.cpp ? The crash was supposed to fix by opentoonz/pull/2057

@ankit-kumar-dwivedi The fix of opentoonz/opentoonz#2057 is included into Morevna Edition 1.3.

Please consider, that OpenToonz Morevna Edition doesn't includes all features/fixes of official OpenToonz 1.3. Actually, OpenToonz Morevna Edition 1.3 has only features of official OpenToonz 1.2.1 + our additions (Assistants, Color selector, etc.). This might be the reason why this happens.

[ankit-kumar-dwivedi]

@morevnaproject I have mailed you my pre proposal please suggest any changes and let me know your thoughts on it (^_^)

[ankit-kumar-dwivedi]

@morevnaproject this feature is intended to be only for gui?

[morevnaproject]

Yes!

[ankit-kumar-dwivedi]

@morevnaproject the configuration input dialog for opentoonz(centerline) looks like this

Are we going to create the same options dialog or there are some changes required?

And in the centerline algorithm, the first step in processing anti-aliased images so I am starting with the pre-processing part when the layer is anti-aliased.
see toonz/sources/toonzlib/Naa2TlvConverter.cpp
Will push the changes on a new branch in my repository.
Will keep you updated on what I am working on [^_^]

[morevnaproject]

Are we going to create the same options dialog or there are some changes required?

Yes, let's go with the same options. ^__^

As understand, the preview area at the bottom could take additional time to implement, so you can skip it for now. It can be added later.

[ankit-kumar-dwivedi]

As understand, the preview area at the bottom could take additional time to implement, so you can skip it for now. It can be added later.

Okay @morevnaproject [^_^]

[ankit-kumar-dwivedi]

@morevnaproject can I use OpenGL for anti-aliasing?
As I don't think it's a good idea to re-implemet something which we already have in some library synfig is already using

[morevnaproject]

Can you please let me know which part of code you would like to apply it? Synfig already has some algorithms for anti-aliasing...
@blackwarthog

[ankit-kumar-dwivedi]

I would like to use multisample anti-aliasing or MSAA

Synfig already has some algorithms for anti-aliasing...

I would love to know about it more please tell me where it is?

[morevnaproject]

@ankit-kumar-dwivedi I do not understand, why you need to apply anti-aliasing if your image is already anti-aliased. By quick reading OpenToonz code I've got an impression that it does exactly opposite - it converts anti aliased image to image with reduced color palette. Am I wrong here? ^__^

[ankit-kumar-dwivedi]

@morevnaproject is it ??? 😱
But the variable definition said if it is non-antialiased
Please see the attached screenshot

So I thought if I will anti-alias the image that pre processing will not be needed. Also I thought Naa2TlvConverter means Non-Anti Aliased to toonzlevel converter.
The code inside the Naa2Tlvconverter looks to me like it is performing anti-aliasing.
Note: Sorry for not being active have some submissions lined up will be regular after wednesday

[ankit-kumar-dwivedi]

@ankit-kumar-dwivedi I do not understand, why you need to apply anti-aliasing if your image is already anti-aliased. By quick reading OpenToonz code I've got an impression that it does exactly opposite - it converts anti aliased image to image with reduced color palette. Am I wrong here? ^__^

@morevnaproject Please see my previous comment.
Should I proceed with anti-aliasing thing?

Yes, let's go with the same options. ^__^

As understand, the preview area at the bottom could take additional time to implement, so you can skip it for now. It can be added later.

While you have a look at this I am working on the input dialog box for the time being.

PS: Will be regular from today. All submissions done pheww!!

[morevnaproject]

The code you referenced in #735 (comment) is depends on value of m_naaSource variable.

The value of m_naaSource variable is corresponding to "Enable ink recognition" option in Vectorization dialog -

By enabling this option user says to vectorizer: "my image have limited set of colors with no antialiasing on their borders, please try to recognize them as inks".

In this case vectorizer tries to convert the image to ToonzRasterImage layer (level) type. This layer type is different from plain RasterImage layer type, as it has limited palette. Palette is defined in layer itself. During conversion it applies "palette" provided as input to vectorizer. So, it is possible that colors can be reduced even more at this stage.

When conversion to ToonzRasterImage is done, it converts it back to RasterImage - so we get an non-antialiased image with colors from "palette".

This is how I understand this part of code. ^__^

Since this part is executed only when "Enable ink recognition" option is enabled, I suggest to skip this part for now and continue as if this option is always False.

[ankit-kumar-dwivedi]

In this case vectorizer tries to convert the image to ToonzRasterImage layer (level) type. This layer type is different from plain RasterImage layer type, as it has limited palette. Palette is defined in layer itself. During conversion it applies "palette" provided as input to vectorizer. So, it is possible that colors can be reduced even more at this stage.

When conversion to ToonzRasterImage is done, it converts it back to RasterImage - so we get an non-antialiased image with colors from "palette".

This is how I understand this part of code. ^__^

@morevnaproject Thank you for explaining it so nicely (^_^)

Since this part is executed only when "Enable ink recognition" option is enabled, I suggest to skip this part for now and continue as if this option is always False.

Okay I assume this is false
for the time being, I am not displaying this option in the input dialog

Have a look at input dialog (image below)

@morevnaproject does this looks good to you?

[ankit-kumar-dwivedi]

@morevnaproject I have my semester exams from Monday so I won't be available during that period.
I have made the input dialog and also created vectorize option on right click on the bitmap layer.
As this anti aliasing thing I was not sure about so I thought utilizing time and started to work on GUI in the meantime.
So when I'll be back I'll start with polygonize function which takes thickeness and despeckling config from the input dialog for getting polygon Contours.
PS: Let me know if there is something to change in the input dialog.

[morevnaproject]

Okay I assume this is false
for the time being, I am not displaying this option in the input dialog

Right. ^__^

About the input dialog: I suggest to keep all options horizontally, like this:

(Hint: I have used Glade3 for making a quick UI mockup ^__^).

[ankit-kumar-dwivedi]

About the input dialog: I suggest to keep all options horizontally, like this:

Okay

(Hint: I have used Glade3 for making a quick UI mockup ^__^).

Great! I'll try my hands on Glade3. This is really going make the task easy! Thanks [^_^]

[morevnaproject]

Yes, your image doesn't include transparent areas, so there are no effect. The problem of different values is (probably) somewhere else.

In any case, I am absolutely happy to see the result of test you did here! - #735 (comment) ^__^

[ankit-kumar-dwivedi]

@morevnaproject Toonz uses a function named setOverallPartials() to know the display partial progress as the progress bar animation. Do you want me to keep that function?

[morevnaproject]

It would be nice to have progressbar so user can see how the process is going. But this is not critical at the moment. I suggest to add it after you get vectorization working.

[ankit-kumar-dwivedi]

The problem of different values is (probably) somewhere else.

@morevnaproject You will be glad to know this is fixed :)
also, can you or @blackwarthog help me understand what is this frame in the following lines of code.
https://github.com/morevnaproject/opentoonz/blob/ac3067fb0cdbdcbc4f7fca959cf0d6c212586fb4/toonz/sources/toonzlib/vectorizerparameters.cpp#L234

[ankit-kumar-dwivedi]

@morevnaproject just making sure you have read it :)

also, can you or @blackwarthog help me understand what is this frame in the following lines of code.
https://github.com/morevnaproject/opentoonz/blob/ac3067fb0cdbdcbc4f7fca959cf0d6c212586fb4/toonz/sources/toonzlib/vectorizerparameters.cpp#L234

[ankit-kumar-dwivedi]

@morevnaproject is there any submission format for the evaluation?

[ankit-kumar-dwivedi]

@morevnaproject I found that weight in the line https://github.com/morevnaproject/opentoonz/blob/ac3067fb0cdbdcbc4f7fca959cf0d6c212586fb4/toonz/sources/toonz/vectorizerpopup.cpp#L366
is actually frame which is passed to centerlineconfiguration. Is this frame same as the frame in image below??

If yes then what will be the synfig equivalent of frame?

Also according to Toonz documentation

Thickness Calibration Start: and End: calibrates the vector stroke thickness defined according to the Threshold value; a low value will reduce the stroke thickness preserving its integrity. A different value inserted in the Start / End field determines an animation of the thickness along the length of the level.

Then why are they using frame to calculate the thickness ratio?
I apprciate any pointer @blackwarthog @ice0

[morevnaproject]

@ankit-kumar-dwivedi Hi! Let's take a look at this formula from https://github.com/morevnaproject/opentoonz/blob/ac3067fb0cdbdcbc4f7fca959cf0d6c212586fb4/toonz/sources/toonzlib/vectorizerparameters.cpp#L234 -

conf.m_thicknessRatio = (1 - frame) * m_cThicknessRatioFirst + frame * m_cThicknessRatioLast

The meaning of this formula is to take a value from [0;1] segment and find its relative position on another segment [m_cThicknessRatioFirst; m_cThicknessRatioLast].

frame is a value from [0;1] segment. This is confirmed by code that you referenced -
https://github.com/morevnaproject/opentoonz/blob/ac3067fb0cdbdcbc4f7fca959cf0d6c212586fb4/toonz/sources/toonz/vectorizerpopup.cpp#L364-L366

Thickness Calibration Start: and End: calibrates the vector stroke thickness ...; ... A different value inserted in the Start / End field determines an animation of the thickness along the length of the level.

The last sentence is important. Actually I was not aware that Start / End fields has that meaning.
I have made some tests - yes, it actually allows to "animate" stroke width when vectorization is done for a sequence of images.

I will keep thinking on that and will post more.

[morevnaproject]

is there any submission format for the evaluation?

As I understand from https://google.github.io/gsocguides/mentor/evaluations:
The evaluation guidelines should be provided online by Google at specified times with deadlines.

[morevnaproject]

Examples of the questions that may be asked during evaluations - https://developers.google.com/open-source/gsoc/help/evaluations

[ankit-kumar-dwivedi]

The last sentence is important. Actually, I was not aware that Start / End fields have that meaning.
I have made some tests - yes, it actually allows to "animate" stroke width when vectorization is done for a sequence of images.

I will keep thinking on that and will post more.

Okay @morevnaproject I will be testing the skeletonizer output today and will start working on
Next step - organizeGraphs(skeletons, globals);

The raw skeleton data obtained from StraightSkeletonizer class need to be grouped in joints and sequences before proceeding further

Now need to start thinking how to represent the output that is because the steps after organizeGraphs(skeletons, globals); involves TStroke and TVectorImageP

[morevnaproject]

can you or @blackwarthog help me understand what is this frame in the following lines of code.
https://github.com/morevnaproject/opentoonz/blob/ac3067fb0cdbdcbc4f7fca959cf0d6c212586fb4/toonz/sources/toonzlib/vectorizerparameters.cpp#L234

Okay, here is how I understood it. The frame variable in this function is a frame number from timeline. But it is represented by value from [0; 1] range, where 0 is first frame of all selected frames and 1 is last frame.

This is done in two steps:

(1) - frame number transformed into value from [0;1] range. See lines here - https://github.com/morevnaproject/opentoonz/blob/ac3067fb0cdbdcbc4f7fca959cf0d6c212586fb4/toonz/sources/toonz/vectorizerpopup.cpp#L336-L337 - and here - https://github.com/morevnaproject/opentoonz/blob/ac3067fb0cdbdcbc4f7fca959cf0d6c212586fb4/toonz/sources/toonz/vectorizerpopup.cpp#L362-L363

(2) Then this value is passed to VectorizerParameters::getCenterlineConfiguration function and it calculates thickness multiplier that should be applied at current frame - https://github.com/morevnaproject/opentoonz/blob/ac3067fb0cdbdcbc4f7fca959cf0d6c212586fb4/toonz/sources/toonzlib/vectorizerparameters.cpp#L233-L234

This way, when user has multiple frames selected for vectorization, the thickness can be animated.

So, after we understood the meaning of this functionality, let's answer the question - do we need that in Synfig?

No.

In Synfig we can control (and animate) outline thickness using Outline Grow parameter of group - https://wiki.synfig.org/Group_Layer#Outline_Grow_Parameter

So, it' is ok to assume that conf.m_thicknessRatio variable always = 1.0 (at https://github.com/morevnaproject/opentoonz/blob/ac3067fb0cdbdcbc4f7fca959cf0d6c212586fb4/toonz/sources/toonzlib/vectorizerparameters.cpp#L233-L234 ).

[ankit-kumar-dwivedi]

As it is inconvenient to keep track of every step and some important comments can be lost which contain steps that are currently not top priority but should be implemented later on.

Hence it is better to keep track from milestone now.

So let me brief you about the algorithm for centerlinevectorization from Toonz and where I am

• step-1 If the source is a full-color non-antialiased image so this needs to be processed
  this is currently not implemented see here

• step 2 - centerlinepolygonizer
  Extracts a polygonal, minimal yet faithful representation of image contours
  Contours polygons (see here )

• step 3 - centerlineskeletonizer
  The process of skeletonization reduces all objects in an image to lines, without changing the essential structure of the image. (see here)

Further steps are following and have their own issue in the milestone

• step 4 - organizeGraphs
  The raw skeleton data obtained from StraightSkeletonizer class need to be grouped in joints and sequences before proceding further (In progress)

• step 5
  Take samples of image colors to associate each sequence to its corresponding palette color

• step 6
  Converts each forward or single Sequence of the image in its corresponding Stroke.

• step 7
  Take samples of image colors to associate each stroke to its corresponding palette color.

• step 8
  copy/apply the strokes to an empty vector image and return the vector image after further adjustments

• Further misc adjustments