Connected Components 1 - The naïve approach
Channel: Kevin's Mathematical Musings
Date: 2021-06-14

Connected components labeling in image processing is the process of identifying contiguous patches of pixels and assigning labels to them. It's a special case of finding the connected components in a graph, or of tracking disjoint sets over a series of UNION operations.

This episode derives a basic specification of a connected-components
algorithm. The next episode will explore how the algorithm is optimized for adequate peformance.


00:00 Introduction
02:23 The connected components problem
03:54 Other names for the problem
05:44 Connected components and image segmentation
08:29 The Union-Find data structure
10:02 Running the naïve Union-Find algorithm
12:33 Next up: Making Union-Find practical




IMAGES

"Cartoon mouse"
OpenClipArt user 'gmad'
https://openclipart.org/detail/189839
CC0, https://creativecommons.org/
    publicdomain/zero/1.0/

"Piece of cheese"
OpenClipArt user 'Chrisdesign'
https://openclipart.org/detail/166638
CC0, https://creativecommons.org/
    publicdomain/zero/1.0/

MUSIC

"Long Stroll" Kevin MacLeod (incompetech.com)
Licensed under Creative Commons: By Attribution 4.0 License
http://creativecommons.org/licenses/by/4.0/