prittt / YACCLAB

YACCLAB: Yet Another Connected Components Labeling Benchmark
BSD 3-Clause "New" or "Revised" License
203 stars 37 forks source link

HCS algorithm #33

Closed martinweihrauch closed 2 years ago

martinweihrauch commented 2 years ago

Hi, do you also have an implementation of this algorithm (HCS): https://link.springer.com/article/10.1007/s11554-015-0499-1

Best regards

Martin

prittt commented 2 years ago

Dear @martinweihrauch,

the original HCS algorithm has been proposed in L. He, Y. Chao, K. Suzuki. "A run-based two-scan labeling algorithm." IEEE Transactions on Image Processing, 2008. and is available in YACCLAB under the name RBTS (Run-Based Two Scan algorithm). Specifically, it is implemented within "labeling_he_2008.h" file.

The HCS algorithm you linked introduces the Euler number calculation to RBTS. If you also need this feature, it should require just minor code changes to RBTS implementation. In case, feel free to pull request your code.

Hope this helps.

Federico

martinweihrauch commented 2 years ago

Thank you!! Is there any algorithm you would recommend to me for the purpose of a) get the number connected components and b) get the number of holes (eg Euler) ?

martinweihrauch commented 2 years ago

Plus: Could someone here maybe help me to write some small example code, with which I can a) read a PBM file (http://netpbm.sourceforge.net/doc/pbm.html) and b) just get the number of connected components and b) get the Euler number ?

I am an oncologist and want to use that to analyze cancer images and find cancer faster in our patients!

Thank you very much Martin

prittt commented 2 years ago

Dear @martinweihrauch,

I suggest you to use the OpenCV library that already allows you to read images in PBM format and calculate connected components (and their statistics) with our fastest algorithm Spaghetti labeling:

Bolelli, F., Allegretti, S., Baraldi, L., & Grana, C. (2019). Spaghetti labeling: Directed acyclic graphs for block-based connected components labeling. IEEE Transactions on Image Processing, 29, 1999-2012.

Bolelli F, Allegretti S, Grana C. One DAG to Rule Them All. IEEE Trans Pattern Anal Mach Intell. 2021 Jan 28;PP. doi: 10.1109/TPAMI.2021.3055337. Epub ahead of print. PMID: 33507865.

The only thing that is missing in OpenCV (as far as I know) is the calculation of the Euler number.

Federico

martinweihrauch commented 2 years ago

Ok, again: thank you very much!! Last question: do you have any hint how to calculate the Euler number?

prittt commented 2 years ago

It's extremely inefficient, but you can use the contour hierarchy if you don't want to implement the RBTS variation (HCS) or other algorithms by yourself. e.g.: https://stackoverflow.com/a/55539732/7364941

If you found the YACCLAB repository helpful don't miss to leave a star 😉.