Scribd
Upload
107 views15 pages

The Connected Components Algorithm: Also The Hole Counting Algorithm & Shape Detection by Mikhail Koryak

The document describes the connected components algorithm and two related algorithms: 1) The connected components algorithm extracts regions from an image by labeling sets of connected pixels with the same intensity values. It requires 4 passes over the image to label and group connected pixels. 2) Shape detection can be done using a structural element like a circular mask. The ratio of pixels covered vs uncovered by the mask on an object determines if it is a square or rectangle. 3) The "magical" hole counting algorithm from the 1970s counts holes in binary images using only 2 bytes of memory. It detects two types of corners in a single pass to calculate the number of objects based on external vs internal corners.

Uploaded by

Gabriel Humpire
Copyright
© Attribution Non-Commercial (BY-NC)
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
107 views15 pages

The Connected Components Algorithm: Also The Hole Counting Algorithm & Shape Detection by Mikhail Koryak

The document describes the connected components algorithm and two related algorithms: 1) The connected components algorithm extracts regions from an image by labeling sets of connected pixels with the same intensity values. It requires 4 passes over the image to label and group connected pixels. 2) Shape detection can be done using a structural element like a circular mask. The ratio of pixels covered vs uncovered by the mask on an object determines if it is a square or rectangle. 3) The "magical" hole counting algorithm from the 1970s counts holes in binary images using only 2 bytes of memory. It detects two types of corners in a single pass to calculate the number of objects based on external vs internal corners.

Uploaded by

Gabriel Humpire
Copyright
© Attribution Non-Commercial (BY-NC)
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 15

The Connected Components

Algorithm

Also the hole counting algorithm & Shape


detection

By Mikhail Koryak
Introduction: Connected Components

„ Connected Components
algorithm is used to extract
“regions” from an image.
‰ A region in an image is a
set of pixels with similar
intensity values which are Original Image
neighbors to each other.
„ Once the regions are
extracted they are labeled
with different
numbers/colors.

Regions extracted with CC


Connected Components: Algorithm

„ 4 passes over the image are required for


processing.
‰ 1st pass: label all pixels that are connected to
their neighbors.
‰ 2nd pass: with new labels in place, re-label all
pixels that have neighbors with a different
label.
‰ 3rd pass: run the union find algorithm on the
labels to connect multiple neighboring labels
into one label
‰ 4th pass: create a structure array containing all
the detected components
Connected Components: 1st pass

„ Label all pixels connected to their neighbors.

‰ Output of this operation will look like this:


‰ Different labels are different gray levels
Connected Components: 2nd pass

„ We now must connect labels which are


neighboring each other
‰ We do not do it directly on the image, instead we
create a table and modify that
‰ We initialize a 1D array where the length equals
the number of labels, and where the value of each
element is its index.
‰ As we pass over the image, and we find that label
J neighbors label K, we set label_array(J) = K.
Connected Components: 3rd pass

„ Now in order to combine all the neighboring


labels in the image into one, we run the union
find algorithm on the label_array.
‰ Because of the transitivity of the label_array we know
that if array(i) = array(j) and array(j) = array(k) then
array(i) = array(k)
Connected Components: 4th pass

„ We can now use the label_array in conjunction


with the image to find any pixel’s label using
this formula:
‰ New_pixel_value = label_array(pixel)
‰ After all pixels are reassigned, we can easily collect
different components into a structure array.

Æ
Shape detection using a structural element

„ Goal:
‰ Given an image with square and rectangular
blocks, to detect which blocks are square and
which are rectangular
„ Constraints:
‰ A structural element must be used for detection,
not distances
‰ Detection must be translation and rotation
invariant
Shape detection using a structural element

„ What is a structural element?


‰ It’s a mask which you apply to an image.
‰ Theoretically you should be able to apply a square
mask to a square and if its fully covered then you
know it is a square.
„ What is rotation / translation invariance?
‰ Translation = object can be anywhere on the
screen
‰ Rotation = object can be rotated in any direction,
or not at all
Shape detection using a structural element:
Algorithm
„ I chose to use a circular mask because it is
rotation invariant in itself.
„ First the center of the object is found by
taking the average of all the object’s pixels
‰ We can find the pixels from the CC algorithm
„ A circle mask is “grown” inside of the object
until it “touches” a background pixel
„ A ratio of the area covered by the mask
versus the area not covered by the mask is
taken
Shape detection using a structural element:
Algorithm continued

„ We know what the ratio is if the object


is a square
‰ (3.1415 * r^2) / (4 * r^2) = 0.7853
‰ Anything drastically higher than this ratio
must be a rectangle
Shape detection using a structural element:
Conclusion

„ After squares and rectangles have been


detected they can be displayed in different
colors.

Æ
The “magical” hole counting algorithm

„ Back in the 70s in factories some people


needed to count the number of holes in some
parts, if the number was wrong the part was
defected
„ The restrictions were:
‰ All images are binary (white background, black
objects)
‰ The algorithm must be fast
‰ Not more then 2 bytes of ram must be used to
count objects in any size image.
The “magical” hole counting algorithm

„ Some crazy pot smoking programmers from the 70s


got together and came up with this:
‰ Holes will be counted in 1 pass over the image, only 4 pixels
at a time have to be in memory
‰ 2 types of corners are defined:
‰ The image is scanned from top to bottom, left to right for
these masks, and their totals kelp in memory
‰ Number of object = (number of external corners – number of
internal corners) / 4
‰ Feel free to figure out why this works
The end

You might also like