Browse Prior Art Database

Cluster Edit Algorithm

IP.com Disclosure Number: IPCOM000077083D
Original Publication Date: 1972-Jun-01
Included in the Prior Art Database: 2005-Feb-24
Document File: 3 page(s) / 41K

Publishing Venue

IBM

Related People

Ricard, JH: AUTHOR

Abstract

The objective of the cluster edit algorithm is to flag horizontally or vertically contiguous matrix points having the same polarity value. Starting with any point (Xm, Yn, P1) as an input to the cluster edit algorithm, all points which are in the same cluster as Xm, Yn and which are of the same polarity value P1 may be flagged to accomplish such things as (a) removal of a specified cluster of background or character points; (b) removal of all clusters of background or character points below a certain threshold size; (c) determination of a cluster size; and (d) determination of whether two points lie in the same cluster.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 53% of the total text.

Page 1 of 3

Cluster Edit Algorithm

The objective of the cluster edit algorithm is to flag horizontally or vertically contiguous matrix points having the same polarity value. Starting with any point (Xm, Yn, P1) as an input to the cluster edit algorithm, all points which are in the same cluster as Xm, Yn and which are of the same polarity value P1 may be flagged to accomplish such things as (a) removal of a specified cluster of background or character points; (b) removal of all clusters of background or character points below a certain threshold size; (c) determination of a cluster size; and (d) determination of whether two points lie in the same cluster.

Referring to the flow chart and the 10 x 10 matrix, the objective will be to flag all of the matrix points in the cluster I to the right of the diagonally placed broken line. The X's in the matrix represent points of a 1 polarity value. The input (X, Y, P) pointer is of a 1 polarity value and is located at coordinate (3, 3).

The 1st, 2nd, 3rd, 4th, 5th and 6th points, since they are contiguous and all have the same polarity are on the cluster and will be flagged. The flagging may be diagrammatically represented by simply drawing a line through the flagged points.

Next, it is necessary to test which points that are adjacent to the already flagged points have the same polarity. Start by going to the extreme left at coordinate (1, 3) and going upward. The 1st through 5th points have nothing adjacent to any of them in the same one value polarity in an upward direction. The 6th point does have an adjacent one value polarity, and accordingly, it is flagged. From this point at coordinate (6, 2) a search to the left reveals no contiguous points. Next a look up, and there is no point in the cluster. Next, to the right to find four contiguous points in row 2.

These are flagged. Of the four points just flagged, none except the last one at coordinate (9, 2) has a contiguous point above it. Accordingly, the point at coordinate (9, 1) is flagged and used as a new base point.

Having reached an edge of the cluster because the point at coordinate (9, 1) has no contiguous point to the left, above or to the right, the next search is down two to coordinate (9, 3) where this point is flagged. This...