Three-valued-image connected components

Question

Algorithms that label connected components on binary images (background/foreground) are widely available (say, in OpenCV) and discussed at length in the literature. I would however want to label components in an image that has three values (background/foreground1/foreground2). I can obviously use an algorithm for binary images twice, changing the background/foreground definition, but I was wondering if there is some algorithm specifically developed for the three-value case. I guess there could be a significant speed benefit. Lots of searching did not lead me anywhere. Does anybody have any lead?

Answer 1

The ImageMagick implementation of "connected components" tells you the average colour of each blob it detects.

Let's make a sample image:

magick -size 400x230 xc:black +antialias          \
  -fill red     -draw "rectangle 10,10 110,110"   \
  -fill lime    -draw "rectangle 120,10 220,110"  \
  -fill blue    -draw "rectangle 10,120 110,220"  \
  -fill cyan    -draw "rectangle 120,120 220,220" \
  -fill magenta -draw "circle 300,115 300,185"    \
  image.png

And now find the connected components:

magick image.png \
  -define connected-components:verbose=true        \
  -connected-components 8 -auto-level output.png

Output

Objects (id: bounding-box centroid area mean-color):
  0: 400x230+0+0 252.3,113.7 35607 srgb(0,0,0)         # black background
  3: 141x141+230+45 300.0,115.0 15589 srgb(255,0,255)  # cyan square
  1: 101x101+10+10 60.0,60.0 10201 srgb(255,0,0)       # red square 
  2: 101x101+120+10 170.0,60.0 10201 srgb(0,255,0)     # green square
  4: 101x101+10+120 60.0,170.0 10201 srgb(0,0,255)     # blue square
  5: 101x101+120+120 170.0,170.0 10201 srgb(0,255,255) # magenta circle

Answer 2

For images you want to segment into more than just 2 types of levels or regions (foreground and background), a traditional watershed algorithm may be what you need. Watershed can be used for 3+ "levels."

OpenCV supports watershed.

https://docs.opencv.org/4.x/d3/db4/tutorial_py_watershed.html

The Wikipedia entry is useful, but could lead you down rabbit holes that aren't immediately relevant to the problem you want to solve

https://en.wikipedia.org/wiki/Watershed_(image_processing)

Also check out flood fill algorithms, which might be more suitable in some cases.

https://en.wikipedia.org/wiki/Flood_fill

That's a short answer to supplement @Mark Setchell's elegant demo of ImageMagick. So now for the long-winded answer (TL;DR for many readers) to provide context for other algorithms you could explore.

The algorithm you need depends on the type of images you want to process, the accuracy / robustness / usefulness of the result, and how much time you can devote to it.

Image segmentation is a long-standing problem still actively being studied. For certain classes of images there are relatively simple algorithms that can be considered very robust when bundled into well-designed software.

More recently, techniques that employ machine learning do a good job of providing segmentation for natural images, for determining the most object-y objects in an image, and so on. I would not recommend learning those techniques until after you have a good grounding in traditional techniques.

I'd strongly urge you to try to implement a watershed algorithm yourself even if it takes a few days. You don't need to use your algorithm forever, but getting your hands (and brain) dirty will help a lot when you use watershed algorithms in the future.

OpenCV is most useful when you know how the underlying algorithms work. If you're not only familiar with an algorithm, then OpenCV code can be quite hard to puzzle out. If you've implemented a watershed algorithm, you'll know why OpenCV functions have certain parameters. Based on your own experience implementing watershed to test on your image set(s), you may also find yourself wishing OpenCV made additional parameters available.

ImageMagick is a great tool, and is worth the investment of time if you'll be spending time manipulating images and testing ideas.

ImageJ is another long-lived tool that implements traditional image processing algorithms.

Photoshop and GIMP (a free alternative) implement lots of image processing algorithms with user-semi-friendly interfaces. Once you identify a tool that works, you should be able to figure out the name(s) of the underlying algorithm(s).

And not that you asked, but since your question--a good one!--leads to a progression of learning, I'd suggest investigating segmentation algorithms in a particular order. At each step you'd spend at least a few hours trying to implement the algorithm yourself in the programming language you know best. Then you could compare your algorithm with OpenCV, ImageMagick, etc.

Try to implement these--just "understanding" them from textbooks or documentation pages isn't as useful.

1. Histogram of pixel values in 2D (grayscale) or 3D (color) or more dimensions.
2. Manually binarization
3. Flood fill
4. Watershed and/or segmentation into N discrete classes based on pixel values and connectedness
5. Otsu binarization
6. Connected components (a.k.a. blob finding) using 4- and 8-connectedness
7. Image processing kernels
8. "Edge images" using edge-finding kernels (e.g. Sobel, Canny, ...)
9. Polygonalization and polygon simplification
10. Computational geometry (e.g. fast point-in-polygon calculation)
11. Generalized statistical approaches to image processing (not gonna go into detail here)
12. Canned machine learning libraries
13. Your first machine learning model (AFTER you've seen what they can do)

The algorithms above can lead you to study interesting stuff:

Histograms --> Otsu binarization, K-means, statistical measures of entropy, ...

Edges, polygons, and computational geometry --> applications for maps, video games, etc., etc., etc.

Good luck!