Claims:
1. A method for labelling connected components in an image, the method comprising:
receiving, by a data buffer unit (110), a row marker, data stream of binary data serially row by row and a clock, wherein the row marker signifies start of a present row;
storing, by the data buffer unit (110), the received binary data row by row;
compressing, by a run segment extractor unit (120), the received binary data to form plurality of run segments in each row of the received binary data, wherein each run segment is a memory structure comprising at least one parameter selected from: start of each run segment (start), end of each run segment (end), count of each run segment (count), address of next run segment in the present row (*next), address of a run segment falling in a label same as the label of each run segment (*nextl) and address of the label each run segment is associated with (labeladdr);
determining, by a connectivity testing unit (130), connectivity between each run segment in the present row and a previous row; and
performing, by a labelling logic and measurement extractor unit (140), at least one of labelling the present row and resolving labels of the previous row based on the determined connectivity between each run segment in the present row and the previous row.

2. The method as claimed in claim 1, further comprising: detecting, by the labelling logic and measurement extractor unit (140), end of each label and performing one of extracting features and reconstructing image based on each label.

3. The method as claimed in claim 1, wherein compressing, by the run segment extractor unit (120), the received binary data to form the plurality of run segments comprises:
forming plurality of row segments, wherein each row segment is a memory structure comprising at least one parameter selected from: identity of each row (RowId), address of a first run segment in each row (*start) and number of run segments in each row (count);
forming plurality of label segments, wherein each label segment is a memory structure comprising at least one parameter selected from: identity of each label (LabelId), address of a first run segment associated to each label (*start), address of a last run segment associated to each label (*end) and number of run segments associated to each label (count); and
forming plurality of buffers for detecting end of each label, wherein the buffers are two arrays including a present buffer comprising labels present in the present row and a previous buffer comprising labels present in the previous row, wherein each label of the present buffer is compared to each label of the previous buffer and end of each label is detected.

4. The method as claimed in claim 3, wherein compressing, by the run segment extractor unit (120), the received binary data to form the plurality of run segments further comprises:
considering each row as the present row, setting the row id of each row segment corresponding to the present row and setting the count of each row segment;
considering each column of the present row;
determining whether a column number corresponding to each column of the present row is less than a predetermined number;
determining whether the binary data in each column of the present row is binary one in response to determining that the column number corresponding to each column is less than the predetermined number;
setting start of each run segment as the column number in response to determining that the binary data in each column of the present row is binary one;
determining whether the binary data in each column of the present row is binary one and the column number corresponding to each column is less than the predetermined number; and
incrementing the column number in response to determining that the binary data in each column of the present row is binary one and the column number corresponding to each column is less than the predetermined number.

5. The method as claimed in claim 4, wherein in response to determining that the binary data in each column of the present row is not equal to binary one and the column number corresponding to each column is not less than the predetermined number, the method comprises performing, by the run segment extractor unit (120), the following steps:
setting end of each run segment as the column number of each column where the binary data is binary one and setting count of each run segment based on the start of each run segment and the end of each run segment;
determining whether the count of each run segment is greater than one;
moving to next run segment based on the address of next run segment present in each run segment and incrementing the count of each row segment corresponding to the present row by one, in response to determining that the count of each run segment is greater than one;
incrementing the column number of the present row by one; and
determining whether the column number corresponding to each column is less than the predetermined number.

6. The method as claimed in claim 5, wherein in response to determining that the count of each run segment is not greater than one, the method comprises performing, by the run segment extractor unit (120), the following steps:
incrementing the column number of the present row by one; and
determining whether the column number corresponding to each column is less than the predetermined number.

7. The method as claimed in claim 4, wherein in response to determining that the binary data in each column of the present row is not equal to binary one, the method comprises performing, by the run segment extractor unit (120), the following steps:
incrementing the column number of the present row by one; and
determining whether the column number corresponding to each column is less than the predetermined number.

8. The method as claimed in claim 4, wherein in response to determining that the column number corresponding to each column is not less than the predetermined number, the method comprises:
incrementing, by the run segment extractor unit (120), a row number of the received binary data;
considering each row corresponding to the incremented row number as the present row, setting the row id of each row segment corresponding to the present row and setting the count of each row segment; and
considering each column of the present row.

9. The method as claimed in claim 1, wherein performing, by the labelling logic and measurement extractor unit (140), at least one of labelling the present row and resolving labels of the previous row based on the determined connectivity between each run segment in the present row and the previous row comprises:
determining whether the count of each row segment corresponding to the present row is zero; and
updating the present buffer with null in response to determining that the count of each row segment corresponding to the present row is zero.

10. The method as claimed in claim 9, wherein in response to determining that the count of each row segment corresponding to the present row is not zero, the method comprises performing, by the labelling logic and measurement extractor unit (140), the following steps:
determining whether the count of each row segment corresponding to the previous row is zero; and
giving new labels to each run segment in the present row and updating the present buffer with the new labels in response to determining that the count of each row segment corresponding to the previous row is zero.

11. The method as claimed in claim 10, wherein in response to determining that the count of each row segment corresponding to the previous row is not zero, the method comprises performing, by the labelling logic and measurement extractor unit (140), the following steps:
determining whether there is connectivity between each run segment in the present row and the previous row; and
giving new labels to each run segment in the present row and updating the present buffer with the new labels in response to determining that there is no connectivity between each run segment in the present row and previous row.

12. The method as claimed in claim 11, in response to determining that there is connectivity between each run segment in the present row and the previous row, the method comprises performing, by the labelling logic and measurement extractor unit (140), the following steps:
determining whether number of connectivities between each run segment in the present row and previous row is equal to one;
giving same label of each run segment in the previous row to each run segment in the present row, in response to determining that the number of connectivities between each run segment in the present row and previous row is equal to one;
updating at least one parameter of the label segment; and
update the present buffer with labels of the present row.

13. The method as claimed in claim 12, wherein in response to determining that the number of connectivities between each run segment in the present row and previous row is not equal to one, the method comprises performing, by the labelling logic and measurement extractor unit (140), the following steps:
resolving label id of the previous row by giving a minimum label among the labels in the previous row and giving each run segment in the present row the minimum label;
updating the at least one parameter of the label segment; and
update the present buffer with labels of the present row.

14. The method as claimed in claim 4, wherein the predetermined number is a number determining end of each row.

15. A system for labelling connected components in an image, the system comprising:
a data buffer unit (110) configured to: receive a row marker, data stream of binary data and a clock and store the received binary data row by row, wherein the row marker signifies start of a present row;
a run segment extractor unit (120) configured to: compress the received binary data to form plurality of run segments in each row of the received binary data, wherein each run segment is a memory structure comprising at least one parameter selected from: start of each run segment (start), end of each run segment (end), count of each run segment (count), address of next run segment in the present row (next), address of a run segment falling in a label same as the label of each run segment (nextl) and address of the label each run segment is associated with (labeladdr);
a connectivity testing unit (130) configured to: determine connectivity between each run segment in the present row and a previous row; and
a labelling logic and measurement extractor unit (140) configured to: perform at least one of labelling the present row and resolving labels of the previous row based on the determined connectivity between each run segment in the present row and the previous row.

16. The system as claimed in claim 15, wherein the labelling logic and measurement extractor unit (140) is further configured to detect end of each label and perform one of extracting features and reconstructing image based on each label.

17. The system as claimed in claim 15, wherein the data stream is received by the data buffer unit (110) serially row by row.
, Description:
FORM 2
THE PATENTS ACT, 1970
(39 of 1970)
&
THE PATENTS RULES, 2003
COMPLETE SPECIFICATION
(See section 10, rule 13)

“A METHOD AND SYSTEM FOR LABELLING CONNECTED COMPONENTS IN AN IMAGE”
By
BHARAT ELECTRONICS LIMITED
WITH ADDRESS: OUTER RING ROAD, NAGAVARA, BANGALORE 560045, KARNATAKA, INDIA

The following specification particularly describes the invention and the manner in which it is to be performed.

Field of the Invention

The present invention mainly relates to a field of image processing and more particularly, the present invention relates to a method and system for labelling connected components in an image.
Background of the invention

In present day we come across lot of applications where elements need to be segregated into groups or region depending on connectivity. Each of such group of data can be analysed further to extract their features. The method of connecting elements in regions or groups based on their connectivity is known as connected component labelling (CCL). Connected component labelling is a method in image processing and an essential step in almost every application dealing with object detection. It groups together pixels belonging to the same connected component (e.g., object).
Conventionally, in the connected component labelling depending on a set of rules like 4-component connectivity or 8-component connectivity, test is conducted on each element and the regions of continuity are found. Each separate region can be defined as one label. However, to establish connectivity in an image, 4 or 8 comparisons are needed for checking 4-component connectivity or 8-component connectivity.
The connected component labelling is used in various applications like computer vision, Video analytics, Machine learning, Radar Signal processing etc. Similar work is mentioned in one of the prior arts. However, conventional methods of the connected component labelling are not useful in real time applications. In conventional methods, the processing will happen once entire image is obtained. Therefore, for applications such as Radar target detection, conventional methods of the connected component labelling are not useful. During Radar signal processing/Radar target detection, data will be received row by row. So, the moment data is received, the data should be processed to see whether it is connected or not, which is not possible with existing methods.
Therefore, there is a need in the art with a method and system for labelling connected components in an image and to solve the above mentioned limitations.

Objective of the invention

The main objective of the present invention is to provide a method and system for labelling connected components in an image, which uses only two numbers of comparisons per run segment to establish connectivity in the image.

Summary of the invention

An aspect of the present invention is to address the above-mentioned problems and/or disadvantages and to provide at least the advantages described below.
Accordingly, in one aspect of the present invention relates to a method for labelling connected components in an image, the method comprising: receiving, by a data buffer unit, a row marker, data stream of binary data serially row by row and a clock, wherein the row marker signifies start of a present row, storing, by the data buffer unit, the received binary data row by row, compressing, by a run segment extractor unit, the received binary data to form plurality of run segments in each row of the received binary data, wherein each run segment is a memory structure comprising at least one parameter selected from: start of each run segment (start), end of each run segment (end), count of each run segment (count), address of next run segment in the present row (*next), address of a run segment falling in a label same as the label of each run segment (*nextl) and address of the label each run segment is associated with (labeladdr), determining, by a connectivity testing unit, connectivity between each run segment in the present row and a previous row and performing, by a labelling logic and measurement extractor unit, at least one of labelling the present row and resolving labels of the previous row based on the determined connectivity between each run segment in the present row and the previous row.
Accordingly, another aspect of the present invention relates to a system of for labelling connected components in an image, the system comprising: a data buffer unit configured to: receive a row marker, data stream of binary data and a clock and store the received binary data row by row, wherein the row marker signifies start of a present row, a run segment extractor unit configured to: compress the received binary data to form plurality of run segments in each row of the received binary data, wherein each run segment is a memory structure comprising at least one parameter selected from: start of each run segment (start), end of each run segment (end), count of each run segment (count), address of next run segment in the present row (*next), address of a run segment falling in a label same as the label of each run segment (*nextl) and address of the label each run segment is associated with (labeladdr), a connectivity testing unit configured to: determine connectivity between each run segment in the present row and a previous row and a labelling logic and measurement extractor unit configured to: perform at least one of labelling the present row and resolving labels of the previous row based on the determined connectivity between each run segment in the present row and the previous row.
Other aspects, advantages, and salient features of the invention will become apparent to those skilled in the art from the following detailed description, which, taken in conjunction with the annexed drawings, discloses exemplary embodiments of the invention.

Brief description of the drawings
The above and other aspects, features, and advantages of certain exemplary embodiments of the present invention will be more apparent from the following description taken in conjunction with the accompanying drawings in which:
Figure 1 shows a block diagram of a system for labelling connected components in an image according to one embodiment of the present/proposed invention.
Figure 2 shows a flow diagram of a method for labelling connected components in an image, according to one embodiment of the present invention.
Figure 3 shows a flow diagram illustrating basic processes involved in connected component labelling in the image, according to one embodiment of the present invention.
Figure 4 is an example of how run segment structure is connected to each other, according to one embodiment of the present invention.
Figure 5 is an example of how run segment structure and ROW structure are arranged, according to one embodiment of the present invention.
Figure 6 shows a flow diagram of a method for formation of plurality of run segments, according to one embodiment of the present invention.
Figure 7 shows a flow diagram of a method for labelling the present row and resolving labels of the previous row, according to one embodiment.
Persons skilled in the art will appreciate that elements in the figures are illustrated for simplicity and clarity and may have not been drawn to scale. For example, the dimensions of some of the elements in the figure may be exaggerated relative to other elements to help to improve understanding of various exemplary embodiments of the present disclosure.
Throughout the drawings, it should be noted that like reference numbers are used to depict the same or similar elements, features, and structures.

Detailed description of the invention

The following description with reference to the accompanying plots/drawings is provided to assist in a comprehensive understanding of exemplary embodiments of the invention as defined by the claims and their equivalents. It includes various specific details to assist in that understanding but these are to be regarded as merely exemplary. Accordingly, those of ordinary skill in the art will recognize that various changes and modifications of the embodiments described herein can be made without departing from the scope and spirit of the invention. In addition, descriptions of well-known functions and constructions are omitted for clarity and conciseness.
The terms and words used in the following description and claims are not limited to the bibliographical meanings but are merely used by the inventor to enable a clear and consistent understanding of the invention. Accordingly, it should be apparent to those skilled in the art that the following description of exemplary embodiments of the present invention are provided for illustration purpose only and not for the purpose of limiting the invention as defined by the appended claims and their equivalents.
It is to be understood that the singular forms “a,” “an,” and “the” include plural referents unless the context clearly dictates otherwise. Thus, for example, reference to “a component surface” includes reference to one or more of such surfaces.
By the term “substantially” it is meant that the recited characteristic, parameter, or value need not be achieved exactly, but that deviations or variations, including for example, tolerances, measurement error, measurement accuracy limitations and other factors known to those of skill in the art, may occur in amounts that do not preclude the effect the characteristic was intended to provide.
Figures discussed below, and the various embodiments used to describe the principles of the present disclosure in this patent document are by way of illustration only and should not be construed in any way that would limit the scope of the disclosure. Those skilled in the art will understand that the principles of the present disclosure may be implemented in any suitably arranged system. The terms used to describe various embodiments are exemplary. It should be understood that these are provided to merely aid the understanding of the description, and that their use and definitions in no way limit the scope of the invention. Terms first, second, and the like are used to differentiate between objects having the same terminology and are in no way intended to represent a chronological order, unless where explicitly stated otherwise. A set is defined as a non-empty set including at least one element.
The present invention mainly relates to a field of image processing. More particularly, the present invention relates to a method and system for labelling connected components in an image.
The present invention relates to image processing, and more specifically to methods of data clustering in an image based on connectivity with its neighbours. The present invention is run based and labeling can start as soon as single each row fed. The method compares only edges of each segment to test 8-component connectivity, which brings down number of comparisons to just two per segment. A segment is a run of 1s. The invention provides unique label only to components that are strictly connected, thus even when the targets are of irregular shapes and are nearby, no two disconnected targets would be merged.
The main objective of the present invention is to provide a method and system for labelling connected components in the image, which uses only two numbers of comparisons per run segment to establish connectivity in the image.
The present invention provides a method for labelling hit-map clusters for Radar target detections and the present invention is evolved keeping requirements of Radar target detection in consideration. The connected component labelling is used in various applications like Computer Vision, Video analytics, whereas the present invention mainly focuses on constraints faced in Radar. The present invention stands valid for all other applications where similar techniques are employed. In addition to this, the present invention provides a novel methodology for better utilization of resources in terms of computation and memory.
The present invention describes a method to cluster connected components in binary data which can be arranged in a form of the image. The present method first encodes run-based data segments and stores this to memory and then utilizes this memory to resolve connectivity. The present invention uses only two numbers of comparisons per run segment to establish connectivity compared to 4 or 8 comparisons needed for checking 4 or 8 connectivity.
Figure 1 shows a block diagram of a system for labelling connected components in an image according to one embodiment of the present/proposed invention. Figure 1 shows the overall system block diagram. The system receives row marker, data stream and clock as input and gives out labels and required features as output. The system comprises: a data buffer unit 110, a run segment extractor unit 120, a connectivity testing unit 130 and a labelling logic and measurement extractor unit 140. The data buffer unit 110 receives the row marker, data stream of binary data and the clock and store the received binary data row by row. The row marker signifies start of a present row. The data stream is received by the data buffer unit 110 serially row by row. The data is sampled from data stream using the clock input. The sampled binary data is stored into the data buffer unit 110 and is used to extract run segments. That is, the run segment extractor unit 120 compresses the received binary data to form plurality of run segments in each row of the received binary data. The compressed data is further used for connectivity testing and label extraction. The connectivity testing unit 130 determines connectivity between each run segment in the present row and a previous row. The labelling logic and measurement extractor unit 140 performs at least one of labelling the present row and resolving labels of the previous row based on the determined connectivity between each run segment in the present row and the previous row. The labelling logic and measurement extractor unit 140 further detects end of each label and performs one of extracting features and reconstructing image based on each label. That is, labels with information about its members and features extracted from the labels are the outputs from the system as shown in Figure 1. For example, the output from the system depends on various applications/requirements.
In an embodiment, the output can be given out as the image by reconstructing through a chain of each label and decompressing run segments.
In an embodiment, if the requirement is, for example, geometric centre or centroids based on any other formulas, that can also be done/achieved by traversing through the label.
The present invention provides unique label only to components that are strictly connected, thus even when targets are of irregular shapes and are nearby, no two disconnected targets would be merged.
Figure 2 shows a flow diagram of a method for labelling connected components in an image, according to one embodiment of the present invention. Referring to Figure 2, at step 210, the method comprises receiving the row marker, data stream of binary data serially row by row and the clock by the data buffer unit 110. The row marker signifies start of the present row. At step 220, the method comprises storing the received binary data row by row by the data buffer unit 110. At step 230, the method comprises compressing the received binary data to form plurality of run segments in each row of the received binary data by the run segment extractor unit 120. Each run segment is a memory structure comprising at least one parameter selected from: start of each run segment (start), end of each run segment (end), count of each run segment (count), address of next run segment in the present row (*next), address of a run segment falling in a label same as the label of each run segment (*nextl) and address of the label each run segment is associated with (labeladdr). At step 240, the method comprises determining connectivity between each run segment in the present row and the previous row by the connectivity testing unit 130. At step 250, the method comprises performing at least one of labelling the present row and resolving labels of the previous row based on the determined connectivity between each run segment in the present row and the previous row by the labelling logic and measurement extractor unit 140.
Figure 3 shows a flow diagram illustrating basic processes involved in connected component labelling in the image, according to one embodiment of the present invention. In the present invention, at step 310, the data stream of binary data is received by the data buffer unit 110 serially row by row. For example, the binary data is taken serially with row demarcation. The row marker, received by the data buffer unit 110, signifies start of the present row. The received binary data is stored by the data buffer unit 110 row by row. In connected component labelling process of the present invention, the run segment extractor unit 120 go through the received binary data to form run segments. i.e., at step 320, the run segment extractor unit 120 compresses the received binary data to form plurality of run segments in each row of the received binary data.
At step 330, the connectivity between each run segment in the present row and the previous row is determined by the connectivity testing unit 130. At steps 330 and 340, at least one of labelling the present row and resolving labels of the previous row is done by the labelling logic and measurement extractor unit 140, based on the determined connectivity between each run segment in the present row and the previous row.
At step 340, end of each label is detected by the labelling logic and measurement extractor unit 140. The labelling logic and measurement extractor unit 140 further performs one of extracting features and reconstructing image based on each label.
In an embodiment, in the method for labelling connected components in the image, the labels with information about its members and the required features extracted from the labels are the outputs. The output depends on applications such as computer vision, video analytics, machine learning, radar signal processing and the like. Further, the present invention stands valid for all other applications where similar techniques where employed.
In an embodiment, the output of the connected component labelling can be given out as the image by reconstructing through chain of each label and decompressing run segments.
In an embodiment, if requirement is, for example, geometric centre or centroids based on any other formulas, that can also be done by the traversing through the label. The present invention provides the method for labelling connected components in the image, in which parameters like centroids can be calculated at the end of label.
In an embodiment, the present invention provides the method to label binary data as an entire image.
In an embodiment, the present invention provides the method to label when data needs to connect to form circular images.
Figure 4 is an example of how run segment structure is connected to each other, according to one embodiment of the present invention. In the present invention, the binary data is taken serially with row demarcation. This binary data is stored in the form of run segments. Each run segment is a memory structure comprising at least one parameter. That is, run segment contains the following contents: start, end, count, address to next run segment (*next), address to next run segment falling in same label (*nextl), address of the label it is assigned with. Here in run segment count is not mandatory as this can be derived from start and end. Also, in run segment other parameters like average squared average or any other parameter can be added depending on the application requirement. An example of interconnections between run segments is shown in Figure 4.
Figure 5 is an example of how run segment structure and ROW structure are arranged, according to one embodiment of the present invention. In the present invention, the run segment extractor unit 120 compresses the received binary data to form the plurality of run segments, wherein the method comprises: forming plurality of row segments, forming plurality of label segments and forming plurality of buffers for detecting end of each label.
Therefore, the next structure involved in the labelling procedure/the connected component labelling process is row structure. Row structure contains the row id/ RowId, address of first run segment in that particular row and number of run segments in the row. For example, each row segment is a memory structure comprising at least one parameter selected from: identity of each row (RowId), address of the first run segment in each row (*start) and number of run segments in each row (count).
The third structure involved in the present invention is Label structure, it contains label id/ LabelId, address of the first run segment added into the label, address of the last run segment added into the label, the number of run segments in the label. Each Label is kept in continuous memory so that labels can be accessed easily. For example, each label segment is a memory structure comprising at least one parameter selected from: identity of each label (LabelId), address of the first run segment associated to each label (*start), address of the last run segment associated to each label (*end) and number of run segments associated to each label (count).
The next memory involved is the buffers for deciding end of the label. It is simply two arrays of memory with first element storing the number of labels present in buffer. The first buffer is used to store labels present in present row and the second buffer contains the labels present in previous row. More specifically, the buffers are two arrays including a present buffer comprising labels present in the present row and a previous buffer comprising labels present in the previous row, wherein each label of the present buffer is compared to each label of the previous buffer and end of each label is detected.
Whenever the label is assigned to run segment in the present row, either a new or continuation of old label, the buffer or array, for example, the present buffer is updated. When processing of the row is completed, the present buffer is compared with that of the previous buffer. The previous buffer is nothing but present buffer of the previous row. When comparing if it is found that the label present in the previous buffer is not present in the present buffer, it is concluded, that particular label is ended.
Figure 6 shows a flow diagram of a method for formation of plurality of run segments, according to one embodiment of the present invention. One of the main processes in the labelling procedure/connected component labelling is going through the received binary data to form run segments. That is, how the run segment extractor unit 120, compresses the received binary data to form the plurality of run segments is explained using Figure 6. Figure 6 describes how the binary data is encoded in memory.
Consider an example, where H represents number of rows in the received binary data and W represents number of elements in one row. Number of elements in the row need not be fixed. Here, for example/for flexibility in explanation, W is considered as the number of elements in one row.
At steps 612 and 614, each row is considered as the present row, the row id of each row segment is set corresponding to the present row and the count of each row segment is set. For example, to form run segments in row, first ROW structure corresponding to ROW is initialized i.e., ROW.id is set as . ROW.count is set to zero.
At steps 614 and 616, each column of the present row is considered and determine whether a column number corresponding to each column of the present row is less than a predetermined number. For example, consider that, j is the index corresponding to elements in the row.
At step 616, in response to determining that the column number corresponding to each column is not less than the predetermined number, the run segment extractor unit 120 increments a row number of the received binary data, considers each row corresponding to the incremented row number as the present row and sets the row id of each row segment corresponding to the present row and sets the count of each row segment and considers each column of the present row. For example, i is incremented.
At step 618, determine whether the binary data in each column of the present row is binary one in response to determining that the column number corresponding to each column is less than the predetermined number. For example, in every row, Data(j) is tested for 1.
At step 620, set start of each run segment as the column number in response to determining that the binary data in each column of the present row is binary one. For example, if data(j) is found equal to 1 then the is set as j.
In an embodiment, at step 618, in response to determining that the binary data in each column of the present row is not equal to binary one, the run segment extractor unit 120 increments the column number of the present row by one and determines whether the column number corresponding to each column is less than the predetermined number. For example, j is incremented until data(j) is equal to 1.
At step 622, determine whether the binary data in each column of the present row is binary one and the column number corresponding to each column is less than the predetermined number.
At step 624, increment the column number in response to determining that the binary data in each column of the present row is binary one and the column number corresponding to each column is less than the predetermined number. For example, once data(j) is found equal to 1, j is incremented until data(j) is no longer equal to 1 or if j is equal to W.
At step 622, in response to determining that the binary data in each column of the present row is not equal to binary one and the column number corresponding to each column is not less than the predetermined number, the run segment extractor unit 120 sets end of each run segment as the column number of each column where the binary data is binary one and sets count of each run segment based on the start of each run segment and the end of each run segment as shown in step 626. For example, at the exit of the connected component labelling process, is set as j. is updated as . Further, the run segment extractor unit 120 determines whether the count of each run segment is greater than one, moves to next run segment based on the address of next run segment present in each run segment and increments the count of each row segment corresponding to the present row by one, in response to determining that the count of each run segment is greater than one as shown in steps 628 and 630. For example, if is found greater than 1, then is either allocated with a new memory for with size of Run segment structure. The memory can be pre-allocated and one of the unused memory block can be assigned to . is incremented and is assigned the new allocated memory, that is . Further, the run segment extractor unit 120 increments the column number of the present row by one and determines whether the column number corresponding to each column is less than the predetermined number.
At step 628, in response to determining that the count of each run segment is not greater than one, the run segment extractor unit 120 increments the column number of the present row by one and determines whether the column number corresponding to each column is less than the predetermined number. For example, if is less than 1, then j is incremented, and this process is repeated until j reaches W or end of the row.
In the present invention, the predetermined number is a number determining end of each row. For example/for flexibility in explanation, W is considered as the predetermined number i.e., number of elements in one row.
Figure 7 shows a flow diagram of a method for labelling the present row and resolving labels of the previous row, according to one embodiment. Figure 7 describes how label is resolved. The labelling logic and measurement extractor unit 140, performs at least one of labelling the present row and resolving labels of the previous row based on the determined connectivity between each run segment in the present row and the previous row. In the Figure 7, Row 2 represents the present row and Row 1 represents the previous row.
At step 712, the labelling logic and measurement extractor unit 140 determines whether the count of each row segment corresponding to the present row is zero. At step 714, the labelling logic and measurement extractor unit 140 updates the present buffer with null in response to determining that the count of each row segment corresponding to the present row is zero.
At step 712, in response to determining that the count of each row segment corresponding to the present row is not zero, the labelling logic and measurement extractor unit 140 determines whether the count of each row segment corresponding to the previous row is zero and gives new labels to each run segment in the present row and updates the present buffer with the new labels in response to determining that the count of each row segment corresponding to the previous row is zero as shown in steps 716 and 718. For example, the labelling process can begin as soon as the first row is encoded into structure and ROW structure is filled. While labelling, the first row is given distinct labels. Creation of new label is done by allocating a memory for a label structure. It can be allocated on the go or taken from a previously allocated memory. First the label id is updated in . the label id begins with 1. label id is incremented as soon as each new label is created. Next is the . whenever a new label is created it is due to presence of run segment which cannot be assigned onto any other label. So, the first 's address which led to the cause of creation of new label is stored in . now is also updated with same address. the count is updated as one. The is updated with address of the label structure it is assigned. In the first row, every is assigned new labels. From the second row onwards, run segments from the previous row can be used to test for connectivity.
At steps 720 and 722, in response to determining that the count of each row segment corresponding to the previous row is not zero, the labelling logic and measurement extractor unit 140 determines whether there is connectivity between each run segment in the present row and the previous row and gives new labels to each run segment in the present row and updates the present buffer with the new labels in response to determining that there is no connectivity between each run segment in the present row and previous row as shown in step 724.
At step 722, in response to determining that there is connectivity between each run segment in the present row and the previous row, the labelling logic and measurement extractor unit 140 determines whether number of connectivities between each run segment in the present row and previous row is equal to one, gives same label of each run segment in the previous row to each run segment in the present row, in response to determining that the number of connectivities between each run segment in the present row and previous row is equal to one, updates at least one parameter of the label segment and updates the present buffer with labels of the present row as shown in steps 726 and 728.
At step 726, in response to determining that the number of connectivities between each run segment in the present row and previous row is not equal to one, the labelling logic and measurement extractor unit 140 resolves label id of the previous row by giving a minimum label among the labels in the previous row and giving each run segment in the present row the minimum label, updates the at least one parameter of the label segment and updates the present buffer with labels of the present row as shown in step 730.
For example, in the present invention, in the first row, every run segment is assigned new labels. From the second row onwards, run segments from the previous row can be used to test for connectivity. Here, each run segment in the present row is compared with each labelled one in previous row. The connectivity is tested as follows, let be run segment from previous row and be run segment from present row.

Table 1
From the above Table 1, connectivity test can be chosen depending on 4-component or 8-component connectivity.
Invalid labels: When two run segments having different labelids are merged, both run segment in question is assigned to a single labelid. The label with smallest labelid is chosen to be preserved and the other labelid is discarded. Such discarded labelids are considered invalid labels. Further, when a label needs to be marked invalid, the count of the corresponding label segment is made zero and the labelid is marked with the labelid of the label which was chosen to be preserved.
Further, in the present invention, if two run segments are found to be connected then the is checked for validity. That is, if two run segments are connected, then LabelId/labelid of the run segment in the previous row is checked for validity. Validity of the label is checked by looking at the count value of the label segment. That is, validity is tested by looking at the (number of run segments associated to each label) is greater than zero or not. If found zero, the label is invalid, otherwise the label is valid. If the label is found invalid, the label corresponding to the labelid assigned to the invalid label is checked, where the labelid of the invalid label is the identity of the label to which its contents were merged earlier. That is, if found invalid, then the label corresponding to in the sequence of the label is checked. It is done until a valid label is reached. Once the valid label is reached the new run segment in the present row is added into (address of a last run segment associated to each label). The run segment pointed by is taken and is updated with address of the new run segment and is assigned the address of the new run segment. The is also updated.
As shown in steps 726 and 730, while comparing if it is found that a run segment in present row is connected to two or more run segment in previous row and it is found that they both have separate labels, then the labels are merged into label with minimum label id. The start of the labels with non-minimum labelid is attached to the end of label with minimum label ids and the label id which are non-minimum are updated to minimum labelid that is the labelid to which it is merged. All other set of values in the non-minimum label is reset.
Whenever a label is assigned to run segment in present row, either a new or continuation of old label, a buffer or array let's say present buffer is updated. When processing of a row is completed, the buffer is compared with that of the previous buffer. Previous buffer is nothing but present buffer of the previous row. When comparing if it is found that a label present in previous buffer is not present in present buffer, it is concluded that that particular label is ended and that label parameters can be calculated or used by traversing through the to .
The output of the method for labelling connected components depends on the application. It can be given out as the image by reconstructing through the chain of each label and decompressing run segments. If the requirement is geometric centre or centroids based on any other formulas, that can also be achieved/done by the traversing through the label.
The present invention discloses the method for labelling connected components in binary data where the method compresses binary data, compressed into segments based on runs which is a continuous occurrence. The method for connectivity test, according to the present invention, which is done only on the start and end of these runs to reduce number of comparisons. The method in which labels can be identified on the go and can be resolved. The method in which the features like centroids can be calculated at the end of the label.
The present invention discloses the method to label connected component on binary data which consists of the method to label binary data as an entire image, the method to label when the data is received in serial manner row by row, the method to label when the data needs to connect to form circular images.
The present invention discloses the method to label connected component on binary data consisting of run encoding the data in row-wise manner, checking connectivity and resolving labels and construction of label map, computation of parameters and reconstruction of each label and efficient memory utilization.
The method to label connected component, where data is received serially with start of row marking and is converted into a segment of runs, where each run segment contains a memory structure containing parameters like start of run, end of run, address of next run segment in the same row, address of run segment falling in the same label and address of label the run segment is associated with. Each row segment is a memory structure to store row id, address of the first run segment in each row and number of run segments in that row. Each label segment is a memory structure consisting of Id of label, number of run segments associated to that label, address of first run segment associated to that label, address of last run segment associated to label.
The present invention discloses the method where the test for connectivity check is decided depending on 4-component connectivity or 8-component connectivity, where the test for connectivity uses least number of comparisons.
The present invention discloses the system consisting of memory/buffer to store present available labels and past labels, wherein the system detects end of a label as and when the processing goes, and the past and present buffers are compared to detect end of the label. Further, the system computes parameters without having to traverse data.
The present invention discloses the method suitable for applications like radar target detection where the method detects labels with complex shapes where only requirement to fall in label is connection only with m pixels where m is decided by 4 connectivity or 8 connectivity and configurability with row miss that is ability to continue labelling even when data for n number of rows where n is input to the system.
Figures are merely representational and are not drawn to scale. Certain portions thereof may be exaggerated, while others may be minimized. Figures illustrate various embodiments of the invention that can be understood and appropriately carried out by those of ordinary skill in the art.
In the foregoing detailed description of embodiments of the invention, various features are grouped together in a single embodiment for the purpose of streamlining the disclosure. This device or unit or arrangement of disclosure is not to be interpreted as reflecting an intention that the claimed embodiments of the invention require more features than are expressly recited in each claim. Rather, as the following claims reflect, inventive subject matter lies in less than all features of a single disclosed embodiment. Thus, the following claims are hereby incorporated into the detailed description of embodiments of the invention, with each claim standing on its own as a separate embodiment.
It is understood that the above description is intended to be illustrative, and not restrictive. It is intended to cover all alternatives, modifications and equivalents as may be included within the spirit and scope of the invention as defined in the appended claims. Many other embodiments will be apparent to those of skill in the art upon reviewing the above description. The scope of the invention should, therefore, be determined with reference to the appended claims, along with the full scope of equivalents to which such claims are entitled. In the appended claims, the terms “including” and “in which” are used as the plain-English equivalents of the respective terms “comprising” and “wherein,” respectively.