Contour Tracing: Suzuki-Abe style with non-binary images

[Ryan-Millard]

I'm currently working on #189 (see #219 and the branch). The algorithm is almost complete - I just need to record relationships between contours (hierarchy) and fix the subtle bug below.

For context, I’ve been following the Suzuki and Abe paper on contour tracing. Their algorithm is designed for binary images (pixels are either 0 or 1), but I’ve adapted it to improve performance for Img2Num's use case, which involves non-binary images.

Here’s the current state of the work:

• Original input (after K-Means preprocessing):

• Contour tracing output (each contour in a distinct color):

As you can see, the contours are roughly correct, but there are small inconsistencies. For example, there are tiny isolated pixels along some borders that shouldn’t be there. Here’s a closer look at one of these regions:

I’ve tried adjusting neighborhood checks and border-following logic, but the issue persists. I suspect it may be related to how I’m handling transitions between regions in non-binary images, but I haven’t been able to pinpoint the exact cause.

I don't think that the preprocessing is the problem, though. The image below shows that there are no strange artifacts in the same region as the above image has.

Other images for context

Original → K-Means → Contour Traced K-Means

Original → K-Means → Contour Traced K-Means

Original → K-Means → Contour Traced K-Means

---

@Krasner or @hjmillard, do you have any ideas or suggestions related to the contour tracing algorithm choice?

Is the bug likely an artifact of the preprocessing (K-Means clustering) or something inherent in my adaptation of Suzuki and Abe’s border-following approach for multi-valued images?

[Krasner]

@Ryan-Millard
Please review the following notebook. I suspect your issue might be coming from "mergeSmallRegions".
KMeans produces many small area regions that need to be efficiently merged into neighboring regions.

1. Starting from Kmeans segments I enumerate and characterize neighboring regions using floodfill. This lets me convert Kmeans clusters into unique regions.
2. I convert the region map into an adjancency graph. Each region becomes a Node that tracks which pixels in the image belong to it, it's area, and which regions are the immediate/bordering neighbors represents as edges
3. I search for all nodes with area < minArea and absorb the smallest neighbor. By absorbing a neighbor node, the current node appends it's pixels, area, and edges (neighbors of the neighbor are transferred over). This process is fast and only takes a few iteration until all nodes are at least minArea or greater
4. Since each node tracks which pixels belong to it, I can then convert the graph back into a region map which should be similar to the KMeans region map but with no small segments.
5. I can then begin to trace contours. I look for any border pixels ( those that have multiple regions in a 3x3 search grid ), for each region ID i track a set of contour pixels
6. These contour pixels come out unordered! I can sort the contours (more or less) by starting at any point and then searching for the nearest next contour point.

This is all in python but can be converted to C++. contours still have a few weird issues but are looking better. let me know your thoughts

kmeans_contour.ipynb

[Ryan-Millard]

@Krasner Thank you for your ongoing contributions to this repository. It's nice to have someone else to discuss these problems with.

[Krasner]

Thanks for the feedback. I'm working on implementing the graph based region merging in C++ right now. Once that's done I'll put a PR and then look back at the contour problem. You're right that hierarchy is important.

[Ryan-Millard]

That sounds good.

I'll create a Jupyter Notebook for the contour tracing so the logic can be refined more easily.

Have you looked into Extract and Merge or are you putting that on hold for now?

Also, I found that we can use C++ in Jupyter Notebooks. Do you think it would be worthwhile if I set up something like a Docker container to allow us to use both python and C++ in Jupyter Notebooks? I'm considering a dev container to make onboarding for newcomers smoother. It would also help for documentation because they can be converted to Markdown.

[Krasner]

Yeah I'll put EAM on hold for now. mine/ chatgpt's implementation isn't working correctly so it's going to take me a while to understand why...
Some kind of test environment for the C++ code would be great! I've thought about doing that too.. not necessarily via jupyter.
But having something like wasm/modules/image/test/main.cpp and then a Makefile to compile for various simple tests would be very useful. You may need to write some kind of scaffolding to load and display images - we're not relying on opencv which has a lot of these functions built in.

[Ryan-Millard]

Okay. #205 proposes a full restructuring of the entire repository and I think that would be a good time to set it up. I was going to wait until we had the function that maps contours to SVGs, but it might be better foe me to get it done sooner.

I'll make a Python wrapper so we can display it nicely in Jupyter Notebooks.

[Krasner]

Put in PR #222 but i still see similar contour problems - so probably the issue is with the contour tracing method... will have to review that

[Krasner]

or maybe it's fixed... hard to tell. had a bug on my end which is now resolved

[Ryan-Millard]

It's definitely with the contours I'm doing. I somehow don't record the borders of the image, and I only realised that when I tried to make an SVG out of it to understand it.😂

[Krasner]

So now that the contour finding pr is merged, we should move away from using the imageTracer SVG library, because we don't actually use our computed contours for anything...

[Ryan-Millard]

Yes. That was the plan I've had for a while because imagetracerjs sometimes leaves holes in the SVGs.

[Ryan-Millard]

The SVG issue I'm about to work on will replace that library.

[Krasner]

Looking forward to seeing SVGs with our contours :)

[Ryan-Millard]

It'll be coming soon - I've just been a bit busy recently.

[Ryan-Millard]

Thank you @Krasner. Your work on this was great!