loicland / cut-pursuit

C++ implementation for the cut pursuit algorithm, with Matlab interfaces
MIT License
77 stars 24 forks source link

How to apply the L0 cut-pursuit to 2D images? #32

Open ruomingzhai opened 2 years ago

ruomingzhai commented 2 years ago

As demonstrated in your paper, this algorithm can be applied to images like the famous lena.png. However, I can not figure it out how to organize the 2D images into graph with edges for your algorithm. Could you give me some instructions or example codes for it? Looking forward to hearing from you!

ruomingzhai commented 2 years ago

Furthermore, I have tried build 2D graph using its pixel coordinates, but the results is not good. The number of partitions are all one which means it did not partition at all. I am not sure whether it resulted from the 2D graph or just the inappropriate regularization value, i.e., λ. Hope to get advice from you. Thank you very much!

loicland commented 2 years ago

Dear Ruomingzhai,

you just need to build a graph connecting adjacent pixels. For example for a 3x3 image with the following pixel indices:

0 1 2
3 4 5
6 7 8

then the source / target edge can be as follow:

source 0 0 1 1 2 3 3 4 4 5 6 7
target 3 1 4 2 5 6 4 7 5 8 7 8

This is for a 4-neighborhood (Von Neumann's), which tends to produce some squarish contours that are not so nice. You will get better looking results with Moore's 8-neighborhood (adding diagonal edges).

In which case, you should use the Cauchy-Crofton formula to weight the edges:

See this paper to better understand why.

All in all, generating the pixel adjacency graph should be a pretty basic python function.

ruomingzhai commented 2 years ago

Dear loicland,

Thank you for your detailed instruction.

I constructed the graph with 8-neighborhod in this 512 x 512 image and iteratively run it with reg_strength from 0.01 to 0.8 with a step=0.01. As you said, the edge weights is 1 for horizontal and vertical edges and 1/sqrt(2) for diagonal edges, but it still gets only one component. I wonder if there are other parameters in "libcp.cutpursuit" need to be adjusted.

0

Below is a screenshot of the pixel graph image And the edge weights is 1/distances , i.e., 1 or 1/sqrt(2) image

loicland commented 2 years ago

You can check this other repo of mine:

https://github.com/loicland/img2svg

which uses L0 cut pursuit (the parallel implementation) combined with a vectorizing step.

This should answer a lot of your questions.

ruomingzhai commented 2 years ago

Thank you! It works on your project img2svg!