|7.3.11. Connected Component Analysis
elementary routines for performing a connected component (CC) analysis
on images. The basic procedure consists in:
- Creating a new
CCAnalyzer object for a given image
- Extracting the runs using method
- Extracting the connected components using method
There are a few other methods for performing various cleanup on the runs
and on the CCs. There is also a method for reconstructing the image from
the cleaned CCs.
Another trick: There is a matrix named ubcut
in the CCAnalyzer object. Every pixel
set in this matrix will force the RUN and CC code to ignore connexity on
certain pixels. For instance, you can force arbitrary cuts by setting
the pixels of a 4-connex line in this matrix. This has to be done before
the call to run-analysis .
-- Leon Bottou 9/96
Class for connected component analysis.
|188.8.131.52. (new CCAnalyzer grayimage)
Class CCanalyzer holds all the information necessary for the connected
component analysis of an image grayimage
|184.108.40.206. (==> ccanalizer run-analysis threshold)
Computes a run length representation of the binary image obtained by
thresholdind the gray image ubmatrix2d
at threshold thres . The run
information is stored into slot runs
of the CCAnalizer object.
Each line of matrix runs is a 4-vector
containing the following information:
- At index
(RUN-Y) : The Y coordinate of the run.
- At index (RUN-X1) : The X
coordinate of the first pixel of the run.
- At index (RUN-X2) : The X
coordinate of the last pixel of the run.
- At index (RUN-ID) : The ID of the
blob this run belongs to. The blob information is filled by the CA
This function breaks runs on each non zero pixel of the image located in
slot ubcut of
ccanalyzer . The default value is all zeroes.
This function returns t on success.
|220.127.116.11. (==> ccanalyzer cc-analysis)
Perform the connected component analysis of the image represented by the
runs matrix contained in the ccanalyzer
object. This algorithm usually considers 8-connexity. This is altered
when the cut image ubcuts contains a
non zero value indicating a forced cut.
The results are stored in the cc descriptor matrix
ccdesc of the object. Each line of this matrix represent a
connected component (CC).
- At index
(CC-NRUN) : The number of runs in the CC.
- At index (CC-FRUN) : The index of
the first run of the CC in the CC ordered run matrix
ccruns stored in the object.
- At index (CC-NPIX) : The number
of non background pixels in the CC.
- At index (CC-WPIX) : The sum of
the pixel values (gray level) of the CC. These values are initially
zero. Use function cc-measure-gray to
compute these values.
- At indices (CC-LEFT) ,
(CC-TOP) , (CC-RIGHT) and
(CC-BOTTOM) : The boundign box of the CC.
This function returns t on success.
You may postprocess the returned CC with
cc-measure-gray , cc-remove-specs
, and other functions in this file.
|18.104.22.168. (==> ccanalyzer remove-long-runs maxlen)
This function removes the runs whose length is longer than
maxlen . Long runs are sometimes good indicator for
underlines. Note that nothing is changed in the image. You must use
reconstruct-from-cc for that.
|22.214.171.124. (==> ccanalyzer reconstruct-from-runs)
Reconstruct matrix ubimg from the run
representation. This code saves the gray level information already
present in ubimg . It just sets all
pixels not included in a run to zero.
|126.96.36.199. (==> ccanalyzer cc-measure-gray)
Compute the average gray level of each CC and store it at index
(CC-WPIX) of the CC descriptor matrix
|188.8.131.52. (==> ccanalyzer remove-small-cc minpix mingray minweight)
Remove small connected components
- whose size is less than
- or whose average gray level is less than
- or whose summed gray level is less than
Note that nothing is changed in the image or the run matrix. You must
use reconstruct-from-cc for that.
|184.108.40.206. (==> ccanalyzer reconstruct-from-cc)
Reconstruct matrix ubimg from the
connected components in ccdesc . This
code saves the gray level information already present in
ubimg . It just sets all pixels not included in a run to
|220.127.116.11. (==> ccanalyzer overlay-cc ccid ccimg originx originy)
Overlays connected component ccid into
ubyte matrix ccimg . Matrix
ccimg is assumed to have its top left corner at position
originx originy in the
intial image. Connected components that do not fit matrix
ccimg are silently clipped. Returns t
when something was drawn.
|18.104.22.168. (==> ccanalyzer draw-cc x y)
Draws image at location x
y by painting each connected component with a random color.
Unfortunately, random colors are sometimes too close. [INTERPRETED ONLY]
|22.214.171.124. (==> ccanalyzer pick-cc x y)
returns the index of the connected component that contains the point
x , y , or -1 if no
component contains the point.
|126.96.36.199. (==> ccanalyzer image-height)
returns height of image on which CCA is performed
|188.8.131.52. (==> ccanalyzer image-width)
returns width of image on which CCA is performed
|184.108.40.206. (==> ccanalyzer run-histo histo hosto offset)
compute histogram of runs. histo is an
N by P matrix, and hosto an N vector.
this method will accumulate the histogram of run lengths for each scan
line between offset and
offset +N-1. on output, elements i, j of histo will be
incremented by the number of runs on line i-
offset that are of length j. element i of
hosto will incremented by the number of runs on scanline i-
offset that are larger or equal to P.
|220.127.116.11. (==> ccanalyzer bbox-histo histo)
computes 2D histogram of bounding box heights and width and increment 2D
matrix histo by it. Element i, j of
histo will be incremented by the number of CC whose bounding
box is of height i and of width j.
|18.104.22.168. (==> ccanalyzer ccbottoms thres)
return a matrix with x and y of horixontal center of bottom of each CC.
CCs whose number of black pixels are smaller than
thres are ignored.
|22.214.171.124. (==> CCAnalyzer get-cc-fltim cc-id cc-fltim cc-com cc-off)
((-int-) cc-id) : index of the cc
((-idx2- (-flt-)) cc-fltim) : image in float
((-idx1- (-flt-)) cc-com) : center of mass, in float [X,Y]
((-idx1- (-int-)) cc-off) : offset [X,Y]
ADDED: Patrick Haffner, July 97
Given the index of a CC, returns:
1) the corresponding gray level float image, dilated (WITH OFFSET)
2) the center of mass of the bitmap (WITHOUT OFFSET)
3) the offset used to align the float image to the upper right corner.
WARNING: fltim expands all the edges of the bounding box
by 1 pixel, UNLESS this cannot be done because we hit the
global image border.