Method of labeling image data and device for the same using temporary labels having a concentration relationship

• US 5,602,940 A
• Filed: 09/29/1995
• Issued: 02/11/1997
• Est. Priority Date: 04/09/1993
• Status: Expired due to Term

• Current Assignee: Renesas Electronics Corporation
• Original Assignee: Mitsubishi Denki Kabushiki Kaisha (Mitsubishi Electric Corporation)
• Inventors: Kawai, Hiroyuki, Inoue, Yoshitsugu
• Primary Examiner(s): JOHNS, ANDREW W
• Application Number:
  US08/539,151
• Time in Patent Office: 501 Days
• Field of Search: 395/60, 395/62, 395/133, 382/180, 382/203, 382/204, 382/205, 382/286
• US Class Current: 382/180
• CPC Class Codes: G06T 7/11 Region-based segmentation

Abstract

When a leading end of a run on an upper row in a binary mask which performs raster scan over a binary image is detected, a run label which was assigned to the same run when scanning a row preceding the current row by one row is read out, and label diversion destination data is read from a concatenation table using the read run label as an address. A temporary label is determined by comparing a concatenated label, which indicates the minimum label value of the runs prior to the run on the upper row of which leading end is detected and adjacent to the run existing on the run on the lower row of the binary mask, with the diversion destination data read from the concatenation table. If one of them is 0, the other label data is issued as the temporary label. If both of them are 0, a new label is issued as the temporary label. If the compared label values are different from each and are not 0, the smaller label value is written into the concatenation table using the larger label value as the address. In the labeling process for a binary image data, a frequency of assignment of multiple labels to the same object is reduced, and thereby a load in a label integrating process is reduced.

Claims

1. A labeling method for labeling a run in a binary image through scanning of said binary image with a unit mask formed of a local image region consisting of binary image bilevel data of pixels continuously adjoining to each other on said binary image and arranged in P rows and Q columns, comprising the steps of:

carrying out a search in a row adjacent to a row containing a reference run including a reference pixel in said unit mask, so as to search an adjacent run adjoining to said reference run, provisionally assigning a run label to said reference run in accordance with a result of said search, and storing said provisionally assigned run label at a trailing end of said reference run in a memory;

when said unit mask region extracts said reference run as an adjacent run, referring to said provisionally assigned run label stored in said memory, propagating said provisionally assigned run label to a new reference run for provisionally assigning a run label to said new reference run and determining a label for said reference run which is detected as said adjacent run; and

if said run label propagated to said new reference run is different from a run label of a new adjacent run adjoining to said new reference run, storing at an address, which is equal to one of label values of the different two labels, in a concatenation table the other label value of the different two labels for storing a concatenation relationship between runs in said concatenation relationship;

wherein

said step of determining a label for said reference run includes the steps of, referring to said concatenation table using a run label which is referred to upon detection of a leading end of said adjacent run, and determining both of said label of said adjacent run and the label of said reference run concatenated to said adjacent run in accordance with referred contents of said concatenation table and said referred run label.

2. A labeling circuit comprising:

binary mask producing means for receiving a binary image data series obtained by raster-scan of a binary image and producing a binary mask by extracting a binary image bilevel pixel data P(i, j) at a position of an ith row and a jth column in said binary image and binary image bilevel pixel data P(i-1, j), P(i-1, j-1), P(i-1, j-2), P(i, j-2) and P(i, j-1) adjacent to said binary image bilevel pixel data P(i, j), said binary mask consisting of the bilevel pixel data P(i, j), P(i-1, j), P(i-1, j-1), P(i-1, j-2), P(i, j-1) and P(i, j-2);

run label storing means for storing, as a run label of a reference run, one label representing labels assigned to one or more adjacent run on a (i-1)th row adjacent to said reference run to which said binary image bilevel pixel data belongs;

run label storage control means responsive to said binary mask supplied from said mask producing means for detecting a trailing end of said reference run and responsive to detection of said trailing end to store said run label assigned to said reference run in said run label storing means;

concatenated label storing means for storing and supplying, as a concatenated label, the newest label among labels assigned to one or more adjacent runs existing in a column preceding the jth column in a raster-scanning order when a plurality of adjacent runs exist;

integrated label feeding means for feeding two labels when said two labels are detected to be different from each other and are assigned to a common region in said binary image;

integration processing means including a concatenation table, and receiving the two labels sent from said integrated label feeding means to write one of said two labels, which is selected as a temporary label of said reference run, at an address in said concatenation table, said address being equal in value to the nonselected label of said two labels;

run label read control means responsive to said binary mask outputted from said mask producing means for detecting a leading end of said adjacent run, and also responsive to detection of said leading end to read said run label, which was stored when said adjacent run was said reference run, from said run label storing means, and, using the read run label as an address, to read data from said concatenation table;

temporary label determining means for detecting coincidence and noncoincidence between the label read from said concatenation table, and the concatenated label read from said concatenated label storing means, and for determining the run label of said reference run in accordance with a result of said detection, and determining and outputting the label of the binary image bilevel pixel data as a temporary label, said temporary label determining means including means for controlling the label feeding operation of said integrated label feeding means in accordance with a result of detection of said temporary label determining means said run label from said temporary label determining means supplied to said run label storing means and to said concatenated label storing means; and

new label counter means having an output selected as said temporary label and having contents changed by a unit value, when said temporary label determining means detects a new object in accordance with the result of detection by said temporary label determining means.

3. A labeling circuit comprising:

binary mask producing means for receiving a binary image data series obtained by raster-scan of a binary image and producing a binary mask of bilevel pixel data of two rows and two columns by extracting a binary image bilevel data P(i, j) at a position of an ith row and a jth column in said binary image as well as binary image bilevel data P(i-1, j-1), P(i-1, j) and P(i, j-1) adjacent to a position at said ith row and jth column;

run label storing means for storing, as a run label of a reference run, one label representing labels assigned to one or more adjacent runs on a (i-1)th row adjoining to said reference run to which a reference binary image bilevel data belongs;

run label storage control means responsive to said binary mask for detecting a trailing end of said reference run and also responsive to detection of said trailing end to store the run label assigned to said reference run in said run label storing means;

concatenated label storing means for storing, as a concatenated label, the newest label among labels of adjacent runs existing in columns preceding the jth column in a raster-scanning order if a plurality of adjacent runs exist;

integrated label feeding means for feeding two labels when said two labels are detected to be different from each other and be assigned to a common object region in said binary image;

integration processing means including a concatenation table and receiving the two labels sent from said integrated label feeding means and writing one of said two labels, which one is selected as a temporary label of said reference run, at an address in said concatenation table, said address being equal to the nonselected label between said two labels;

run label read control means responsive to said binary mask for detecting a leading end of said adjacent run, and also responsive to detection of said leading end for reading the run label, which was stored when said adjacent run was a reference run, from said run label storing means, and, using the read run label as an address, to read data from said concatenation table;

temporary label determining means for detecting coincidence and noncoincidence between the label read from said concatenation table and the concatenated label read from said concatenated label storing means, and for determining a run label of said reference run in accordance with a result of said detection, and determining and outputting the label of the binary image bilevel data as a temporary label, said temporary label determining means including means for controlling the label feeding operation of said integrated label feeding means in accordance with a result of detection of said temporary label determining means, said run label determined by said temporary label determining means being supplied to said run label storing means and said concatenated label storing means; and

new label counter means having an output selected as said temporary label and having a count changed by a unit value when said temporary label determining means detects a new object in accordance with the result of detection by said temporary label determining means.

4. A labeling circuit comprising:

mask producing means for receiving a binary image data series, which is obtained by raster-scan of a binary image, in synchronization with a clock signal, and producing a binary mask in two rows and three columns by extracting a binary image bilevel data P(i, j) at a position of an ith row and a jth column in said binary image as well as binary image bilevel data P(i-1, j), P(i-1, j-1), P(i-1, j-2), P(i, j-2) and P(i, j-1) of pixels adjacent to a pixel of said binary image data P(i, j);

run label storing means for storing as a run label of a reference run, one label representing labels assigned to one or more adjacent runs on a (i-1)th row adjacent to said reference run to which said binary image data belongs;

run label storage control means responsive to said binary mask for detecting a trailing and of said reference run and also responsive to detection of said trailing end for storing said run label assigned to said reference run in said run label storing means;

concatenated label storing means for storing, as a concatenated label, the newest label among labels assigned to adjacent runs existing in columns preceding the jth column in a raster-scanning order if a plurality of adjacent runs exist;

integrated label feeding means for feeding two labels when said two labels are detected to be different from each other and to be assigned respectively to two runs concatenated together;

integration processing means including a concatenation table and receiving the two labels sent from said integrated label feeding means and for writing one of said different two labels, which is selected as a temporary label of said reference run, at an address in said concatenation table, said address being equal in value to the nonselected label between said two labels;

run label read control means responsive to said binary mask outputted from said mask producing means for detecting a leading end of an adjacent run, and also responsive to detection of said leading end for reading the run label, which was stored when said adjacent run was scanned as said reference run, from said run label storing means, and for reading data from said concatenation table using the read run label as an address;

temporary label determining means for detecting coincidence and noncoincidence between the label read from said concatenation table by said run label read control means and the concatenated label read from said concatenated label storing means, and for determining a run label of said reference run in accordance with the result of detection, and determining and outputting, as a temporary label, the label of the binary image bilevel data, said temporary label determining means including means for controlling the label data feeding operation of said integrated label feeding means in accordance with the result of detection of said temporary label determining means, said run label of said temporary label determining means being supplied to said run label storing means and to said concatenated label storing means;

new label counter means having an output selected as said temporary label and having a count changed by a unit value when said temporary label determining means detects a new object in accordance with the result of detection by said temporary label determining means; and

clock multiplying means for receiving said clock signal and producing a clock having a frequency being a product of a frequency of the received clock signal and a constant number, said mask producing means, said run label storage control means, said integrated label feeding means, said integration processing means, said run label read control means, and said temporary label determining means operating in response to said clock signal supplied from said clock multiplying means.

5. A labeling circuit comprising:

mask producing means for receiving a binary image data series, which is obtained by raster-scan of a binary image, in synchronization with a clock signal, and producing a binary mask in two rows and two columns by extracting a binary image bilevel data P(i, j) at a position of an ith row and a jth column in said binary image as well as binary image bilevel data P(i-1, j-1), P(i-1, j) and P(i, j-1) of pixels adjacent to a pixel of said binary image bilevel data P(i, j);

run label storing means for storing, as a run label of a reference run, one label representing labels assigned to one or more adjacent runs on a (i-1)th row adjacent to said reference run to which said binary image data bilevel belongs;

run label storage control means responsive to said binary mask supplied from said mask producing means for detecting a trailing end of said reference run and also responsive to detection of said trailing end for storing said run label assigned to said reference run in said run label storing means;

concatenated label storing means for storing, as a concatenated label, the newest label among labels assigned to adjacent runs existing in columns preceding the jth column in a raster-scanning order case if a plurality of adjacent runs exist;

integrated label feeding means for feeding two different labels when it is detected that said two different labels are assigned respectively to runs concatenated together in said binary image;

integration processing means including a concatenation table and receiving said two different labels sent from said integrated label feeding means and writing one of said two different labels, which is selected as a temporary label of said reference run, at an address in said concatenation table, said address being equal in value to nonselected label between said two different labels;

run label read control means responsive to said binary mask outputted from said mask producing means for detecting a leading end of said adjacent run, and also responsive to detection of said leading end for reading said run label, which was stored when said adjacent run was said reference run, from said run label storing means, and using said run label as an address, to read data from said concatenation table;

temporary label determining means for detecting coincidence of noncoincidence between the label read from said concatenation table by said run label read control means and a concatenated label read from said concatenated label storing means, and for determining a run label of said reference run in accordance with result of the detection, and determining said run label as a temporary label of the binary image bilevel data, said temporary label determining means including means for controlling label feeding operation of said integrated label feeding means in accordance with result of detection of said temporary label determining means, said run label determined by said temporary label determining means being supplied to said run label storing means and said concatenated label storing means;

new label counter means having an output selected as said temporary label and also having a count changed by a unit value when said temporary label determining means detects a new object in accordance with the result of detection by said temporary label determining means; and

clock multiplying means for receiving said clock signal and producing a clock having a frequency being a product of a frequency of the received clock signal and a constant number, said clock produced by said clock multiplying means providing timing of said mask producing means, said run label storage control means, said integrated label feeding means, said integration processing means, said label read control means and said temporary label determining means.

6. A labeling method in which an image data is scanned with a local image region to be labeled, comprising the steps of:

(a0) scanning said image data on a unit of said local image region consisting of bilevel pixel data and detecting a run and assigning a label to said run;

(a) where a plurality of labels are assigned to a common image region, selecting the smallest label value among said plurality of labels as a label to be propagated in a subsequent scanning operation;

(b) using the selected label value as data, using a nonselected label value as an address, and storing said label values in a form of a table;

(c) repeating said steps (a) and (b) to assign a temporary label to each image data;

(d) comparing in value a first address in said table with a first data stored at said first address;

(e) writing a new label value as storage contents to be stored at said first address into said table when the results of said comparison at said step (d) indicates that said first address is equal in value to said first data;

(f) storing a second data, which is stored at an address specified by said first data, at said first address of said table when the result of said comparison at said step (d) indicates that said first address is different in value from said first data; and

(g) successively and repetitively performing said steps (d), (e) and (f) starting from the minimum address of said table after completion of said step (c).

7. A labeling circuit for scanning an image data with a local image region and labeling each image data, comprising:

means for scanning said image data on a unit of said local image region consisting of bilevel pixel data, detecting a run on said image data, and assigning a label to said run;

label storing means for performing storage during scanning, when a plurality of labels are concatenated to a common image region, by using the smallest label value among said plurality of labels as a data to be stored and using a nonselected label value as an address;

first counter means for successively performing a count-up operation using a minimum label value of possible label values as an initial value;

comparing means for reading a first data in said label storing means using an output count of said first counter means as an address, and comparing said first data with said output count of said first counter means;

a second counter means for performing a count-up operation using the minimum value of said possible labels as an initial value;

means responsive to detection of coincidence by said comparing means for storing an output count of said second counter means in said label storing means using said output count of said first counter means as an address, and for incrementing said output count of said second counter means; and

means responsive to detection of noncoincidence by said comparing means for storing a second data stored at an address specified by said first data in said label storing means using said output count of said first counter means as an address.

8. A labeling method of scanning an image data in a bilevel image on a unit of a local image region consisting of bilevel image data and labeling each image data, comprising the steps of:

during the scanning operation, detecting a run in said bilevel image, and assigning a label to said run;

when a plurality of labels are assigned to a common image region during the scanning operation, assigning a temporary label to each of said image data by employing a label among said plurality of labels, which has a smallest label value, as a label value to be propagated in the subsequent scanning operation;

writing a data into a table using said employed label value as data to be written and using a nonselected label value as an address;

assigning a flag to each data stored in said table, said flag being initially set to a state indicative of an unprocessed state;

scanning an image data bearing a temporary label, and reading a first data including a label value and a flag from said table using the label assigned to the scanned image data;

when said flag of said first data indicates a processed state, outputting the label value of said first data as a final label value for the scanned image data;

when said flag of said first data indicates the unprocessed state, comparing in value the label of said first data with said first address;

when equality is found in said step of comparing, storing a second data having a new label value and said flag indicative of the processed state concatenated to each other, at said first address in said table, and outputting said new label value as the final label value; and

when inequality is found in said step of comparing storing a third data, which is stored at an address specified by said first data in said table, at said first address in said table, and outputting a label value of said third data as the final label value.

9. A labeling circuit for scanning a local image region in an image and producing a final label image from a temporary label image which is produced by assigning a temporary label to each image data in said image, comprising:

concatenation relationship storing means for performing storage by using a minimum label value as a write data and using a nonselected label value as an address when a plurality of labels are concatenated to a common image region during said scanning operation, and by linking a flag indicative of a processed and unprocessed state to each data to be stored and forming one data, said label of the minimum value being propagated in the subsequent scanning operation;

first reading means for receiving an image data bearing a temporary label, and reading a first data from said concatenation relationship storing means using the received inputted temporary label image data as an address;

register means for storing said first data read from said first reading means;

second reading means for reading a second data from said concatenation relationship storing means using said first data as an address;

comparing means for detecting coincidence and noncoincidence between the label value of said first data read by said first reading means and the temporary label value of said received image;

counter means for performing count-up using the minimum value of said temporary label as an initial value;

selecting means for selecting and outputting one of a count of said counter means, said first data stored in said register means and said second data;

decoding means for performing decoding of an output of said comparing means and a flag of said first data, and generating a signal for controlling the count-up operation of said counter means and a selecting operation of said selecting means, in accordance with the result of decoding, said decoding means including (i) means for generating a first control signal for controlling said selecting means to select said first data stored in said register means, when said flag is indicative of the processed state;

(ii) means for generating a second control signal, for controlling said selecting means to select said second data when said flag is indicative of the unprocessed state and an output of said coincidence detecting means is indicative of noncoincidence, (iii) means for generating a third control signal for controlling said selecting means to select an output count of said counter means, and a fourth control signal for updating the count of said counter means after the selecting operation of said selecting means, when said flag is indicative of the unprocessed state and the output of said coincidence detecting means is indicative of coincidence;

means for writing data outputted by said selecting means into said concatenation relationship storing means while setting a corresponding flag to the processed state, using the label value of said received temporary label image as an address; and

means for outputting the label value of said data outputted from said selecting means as a final label value.

10. The labeling circuit according to claim 9, further comprising frequency multiplying means for frequency-multiplying a clock signal which determines a cycle of application of said temporary label image data;

and

control means coupled to said frequency multiplying means for providing timings of operations of said first and second reading means, said comparing means, said decoding means, said selecting means, said writing means and said output means in response to a clock signal supplied from said frequency multiplying means.

11. A method of labeling a pixel in a binary image including a plurality of pixels each having a binary pixel data, comprising the steps of:

receiving a series of pixel data produced through raster-scanning of said binary image for producing a binary mask including a predetermined number of bilevel pixel data arranged in rows and columns and having an upper row scanning an adjacent run and a lower row scanning a reference run;

responsive to said binary mask, detecting a leading end of an adjacent run;

responsive to detection of the leading end of the adjacent run, reading a run label related to the adjacent run from a run label storage, said run label storage storing each run label for each reference run and supplying a corresponding run label when a reference run is scanned as an adjacent run;

accessing a concatenation table with the read out run label from the run label storage as an address for reading a corresponding data;

selecting a smallest run label among run labels related to adjacent runs adjoining to the reference run, and producing a concatenation data;

responsive to detection of leading end of the adjacent run, comparing said corresponding data from the concatenation table and the concatenation data and determining a temporary label according to the result of comparison;

according to a binary data value of a reference pixel in the reference run in said binary mask, selecting one of the temporary label and a predetermined constant value and outputting the selected one as a final temporary label; and

detecting a trailing end of the reference run, and responsive to the detection of the trailing end, storing said temporary label into said run label storage.

12. The method according to claim 11, wherein said step of producing a concatenation data includes the step of latching the temporary label data in response to the detection of the leading end of the adjacent run to produce said concatenation data.

13. The method according to claim 11 wherein said step of determining a temporary label includes the steps of,

when said corresponding data from the table and said concatenation data are equal in value to each other, issuing a new label as said temporary label, said new label being produced by a counter,

when said corresponding data is equal in value to zero and said concatenation label is different in value from zero, issuing said concatenation data as said temporary label,

when said corresponding data is different in value from zero and said concatenation data is equal in value to zero, issuing said corresponding data as said temporary label,

when said corresponding data and said concatenation data each are different in value from zero and said corresponding data is equal in value to said concatenation data, issuing either of said corresponding data and said concatenation data as said temporary label, and

when said corresponding data and said concatenation label each are different in value from zero and said corresponding data is different in value from said concatenation label, issuing said corresponding data and said concatenation label whichever is smaller in value as said temporary label.

14. The method according to claim 11, further comprising the steps of,

according to said corresponding data and said concatenation label, determining whether divergence of labels occurs, and

when the divergence occurs, writing data selected as said temporary label of said corresponding data and said concatenation label into said concatenation table at an address specified by the other one out of said corresponding data and said concatenation label, and wherein a smaller one of said corresponding data and said concatenation table is selected and issued as said temporary data when said divergence occurs.

15. The method according to claim 14, wherein said divergence of labels is detected to occur when said corresponding data and said concatenation table are different in value from each other and from zero.

16. The method according to claim 11, further comprising the steps of detecting an interruption of the adjacent run and the reference run responsive to said binary mask, and

responsive to the detection of interruption, resetting said concatenation label to a predetermined initial value.

17. A method of labeling a pixel in a binary image including a plurality of pixels each having a binary pixel data, comprising the steps of:

receiving a series of pixel data produced through raster-scanning of said binary image for producing a binary mask including a predetermined number of pixel data arranged in rows and columns and having an upper row scanning an adjacent run and a lower row scanning a reference run;

responsive to said binary mask, detecting a leading end of an adjacent run;

responsive to detection of the leading end of the adjacent run, reading a run label related to the adjacent run from a run label storage, said run label storage storing each run label for each reference run and supplying a corresponding run label when a reference run is scanned as an adjacent run;

accessing a concatenation table with the read out run label from the run label storage as an address for reading a corresponding data;

selecting a smallest run label among run labels related to adjacent runs adjoining to the reference run, and producing a concatenation data;

responsive to detection of leading end of the adjacent run, comparing said corresponding data from the concatenation table and the concatenation data and determining a temporary label according to the result of comparison;

according to a binary data value of a reference pixel in the reference run in said binary mask, selecting one of the temporary label and a predetermined constant value and outputting the selected one as a final temporary label; and

detecting a trailing end of the reference run, and responsive to the detection of the trailing end, storing said temporary label into said run label storage;

(a) initializing both a temporary label counter and a final label counter to initial counts,

(b) accessing said concatenation table with a count of said temporary label counter as an address for reading a first corresponding storage content therefrom,

(c) comparing the count of said temporary label counter with the first corresponding storage content,

(d) when the result of comparison in said step (c) indicates noncoincident, accessing said concatenation table with the corresponding storage content as an address for reading a second corresponding storage content therefrom, and

(e) writing said second corresponding storage content into said concatenation table with the count of said temporary label counter as an address.

18. The method according to claim 17, wherein said step (a) includes the step of initializing the counts of the temporary label counter and the final label counter to a count equal in value to a minimal label value.

19. The method according to claim 17, further comprising the steps of incrementing the count of said temporary counter, and repeating the steps (b) through (e).

20. The method according to claim 17, further comprising the step of writing data equal to the count of said final label counter into said concatenation table with said first concatenation table with said first corresponding storage content as an address when the result of comparison in said step (c) indicates coincident.

21. The method according to claim 20, wherein said step of writing includes the step of incrementing the count of said final label counter in response to the detection of coincidence in said step (c) and then accessing said concatenation table with the incremented count as an address.

22. The method according to claim 20, further comprising the step of supplying the data equal to the count of said final label counter as a final label data in parallel with the writing thereof into said concatenation table.

23. The method according to claim 20, wherein said first corresponding storage content includes a label data indicating a label and an analysis flag indicating that said label data has been processed, and wherein said step of writing includes the step of setting the analysis flag into a state that said label data has been processed.

24. The method according to claim 17, further comprising the step of inhibiting updating of the count of said final label counter when the result of comparison in said step (b) indicates noncoincident.

25. The method according to claim 17, further comprising the step of supplying said second corresponding storage content as a final label data in parallel with said step (e) of writing.

26. The method according to claim 17, wherein each of storage contents in said concatenation table includes a label data indicating a label and an analysis flag indicating whether the label data has been processed, and wherein said method further comprises, after the step (b), the steps of determining whether an analysis flag indicates that the first corresponding storage content has been processed, proceeding to the step (c) of comparing when said analysis flags indicates that the first corresponding storage content is unprocessed, and issuing a label data in said first corresponding storage content as a final label data when said analysis flag indicates that the first corresponding storage content has been processed.

27. The method according to claim 26, wherein said step (e) of writing includes the step of setting an analysis flag on the second corresponding storage content into a state indicating that the second corresponding storage content is processed.

28. A method of labeling a pixel in a binary image including a plurality of pixels each having a binary pixel data, comprising the steps of:

receiving a series of pixel data produced through raster-scanning of said binary image for producing a binary mask including a predetermined number of bilevel pixel data arranged in rows and columns and having an upper row scanning an adjacent run and a lower row scanning a reference run;

responsive to said binary mask, detecting a leading end of an adjacent run;

responsive to detection of the leading end of the adjacent run, reading a run label related to the adjacent run from a run label storage, said run label storage storing each run label for each reference run and supplying a corresponding run label when a reference run is scanned as an adjacent run;

accessing a concatenation table with the read out run label from the run label storage as an address for reading a corresponding data;

selecting a smallest run label among run labels related to adjacent runs adjoining to the reference run, and producing a concatenation data;

responsive to detection of leading end of the adjacent run, comparing said corresponding data from the concatenation table and the concatenation data and determining a temporary label according to the result of comparison;

according to a binary data value of a reference pixel in the reference run in said binary mask, selecting one of the temporary label and a predetermined constant value and outputting the selected one as a final temporary label; and

detecting a trailing end of the reference run, and responsive to the detection of the trailing end, storing said temporary label into said run label storage,

wherein said step of producing a binary mask includes the step of producing a binary mask including pixel data arranged in two rows and two columns.

29. A method for producing a final label for respective runs in a binary image through use of a concatenation table storing data each indicating concatenation destination run with run labels temporarily assigned to respective runs as addresses, comprising the steps of:

(a) initializing a temporary label counter and a final label counter to initial counts,

(b) accessing said concatenation label with a count of said temporary counter as an address for reading out a first corresponding data therefrom;

(c) comparing in value a count of said temporary label counter and said first corresponding data; and

(d) according to the result of comparison in said step of comparing, determining a final label value to be written into said concatenation table at the address specified by the count of the temporary label counter, and writing the final label value onto said concatenation table at said address.

30. The method according to claim 29, wherein said step of determining includes the step of selecting a count of said final label counter as said final label value when the result of comparison indicates that the count of the temporary label counter is equal in value to said first corresponding data.

31. The method according to claim 30, wherein said step of writing includes the step of incrementing the count of said final label counter for writing.

32. The method according to claim 29, wherein said step of determining includes when said result of comparison indicates coincidence, the steps of accessing said concatenation table with said first corresponding data as an address and reading a second corresponding data therefrom, and selecting the second corresponding data as the final label value.

33. The method according to claim 29, further comprising the step of outputting said final label value in parallel with the writing of said final label value into said concatenation table.

34. The method according to claim 29, wherein said concatenation table further stores analysis flags for the respective data stored therein, each of said analysis flag indicating whether a corresponding data is processed, and wherein said method further includes the steps of,

in said step (b) of accessing, reading out an analysis flag corresponding to said first corresponding data,

responsive to the analysis flag read out indicating that the first corresponding data has been processed, supplying said first corresponding data as the final label.

35. The method according to claim 34, further comprising the steps of,

responsive to said analysis flag indicating that the first corresponding data has been processed, disabling the step (c) of comparing, and incrementing the count of said temporary label counter to proceed to the step (b) of accessing.

36. The method according to claim 34, further comprising the steps of,

responsive to the analysis flag indicating that the first corresponding data is unprocessed, proceeding to the step (c) of comparing, and setting said analysis flag into a state indicating that a corresponding data is processed for writing simultaneously with said step (d) of writing.

37. An apparatus for labeling a pixel in an image including a plurality of pixels each having a bilevel pixel data, comprising:

binary mask producing means receiving a series of pixel data produced through raster-scanning of said image for producing a binary mask consisting of a predetermined number of bilevel pixel data arranged in rows and columns and having an upper row scanning an adjacent run and a lower row scanning a reference run;

run label storage means for storing run labels for respective adjacent runs;

run label read control means responsive to said binary mask for detecting a leading end of an adjacent run and responsive to the detection of the leading end of the adjacent run for reading a corresponding run label related to said adjacent run from said run label storage means;

concatenation storage means for storing run labels related to adjacent runs adjoining to a reference run and supplying a smallest run label as a concatenation data;

a concatenation table storing data representing concatenation relationship among runs on said image;

accessing means for accessing said concatenation table with the run label read from said run label storage means as an address for reading a corresponding data therefrom;

determination means responsive to detection of the leading end of said adjacent run for comparing said corresponding data from said concatenation table and said concatenation data from said concatenation storage means and determining a temporary label and a run label for the reference run according to the result of comparison, said run label determined by said determination means being supplied to said run label storage means and said concatenation storage means; and

temporary label feeding means responsive to a data value of a reference pixel in the reference run in said binary mask for selecting one of data indicating said temporary label from said determination means and a predetermined constant data as a final temporary label for external outputting.

38. The apparatus according to claim 37, further comprising run label storage control means responsive to said binary mask for detecting a trailing end of said reference run and responsive to detection of said trailing end for storing said temporary label into said run label storage means as a run label for said reference run, said temporary label being equal to said run label for said reference run.

39. The apparatus according to claim 38, wherein said run label storage means supplies the run label when said reference run is scanned as an adjacent run by said binary mask.

40. The apparatus according to claim 37, wherein said run label storage means comprises a first-in first-out type memory.

41. The apparatus according to claim 37, wherein said concatenation storage means comprises a latch responsive to detection of the leading end of the adjacent run for latching and outputting the data indicating said temporary label as said concatenation data.

42. The apparatus according to claim 41, wherein said concatenation storage means includes means responsive to said binary mask for detecting an interruption of the reference run and the adjacent run to reset said latch.

43. The apparatus according to claim 37, further comprising divergence detecting means responsive to said corresponding data and said concatenation data for detecting whether a divergence of labels occurs,

means responsive to said divergence detecting means detecting that the divergence occurs for writing a smaller one of said corresponding data and said concatenation data into said concatenation table with a larger one of said corresponding data and said concatenation data as an address.

44. The apparatus according to claim 43, wherein said divergence detecting means detects the occurrence of divergence when said corresponding data and said concatenation data each are different from zero and said corresponding data is different in value from said concatenation data.

45. An apparatus for labeling a pixel in an image including a plurality of pixels each having a binary pixel data, comprising:

binary mask producing means receiving a series of pixel data produced through raster-scanning of said image for producing a binary mask including a predetermined number of pixel data arranged in rows and columns and having an upper row scanning an adjacent run and a lower row scanning a reference run;

run label storage means for storing run labels for respective adjacent runs;

run label read control means responsive to said binary mask for detecting a leading end of an adjacent run and responsive to the detection of the leading end of the adjacent run for reading a corresponding run label related to said adjacent run from said run label storage means;

concatenation storage means for storing run labels related to adjacent runs adjoining to a reference run and supplying a smallest run label as a concatenation data;

a concatenation table storing data representing concatenation relationship among runs on said image;

accessing means for accessing said concatenation table with the run label read from said run label storage means as an address for reading a corresponding data therefrom;

determination means responsive to detection of the leading end of said adjacent run for comparing said corresponding data from said concatenation table and said concatenation data from said concatenation storage means and determining a temporary label and a run label for the reference run according to the result of comparison; and

a temporary label feeding means responsive to a data value of a reference pixel in the reference run in said binary mask for selecting one of data indicating said temporary label from said determination means and a predetermined constant data as a final temporary label for external outputting wherein said determination includes,

a new label counter for supplying a count,

first means for detecting that said corresponding data from said concatenation table is equal in value to said concatenation data for selecting and issuing the count of said new label counter as said temporary label,

second means for detecting that said corresponding data is zero and said concatenation data is different from zero to select and issue said concatenation data as said temporary label,

third means for detecting that said corresponding data is different from zero and said concatenation data is different from zero to select and issue said corresponding data as said temporary data,

fourth means detecting that said corresponding data and said concatenation data each are different from zero and said corresponding data is equal in value to said concatenation data to select and issue either of said corresponding data and said concatenation data as said temporary data, and

fifth means for detecting that said corresponding data and said concatenation data each are different from zero and said corresponding data is different in value from said concatenation data to select and issue the corresponding data and said concatenation data whichever is smaller as said temporary data.

46. An apparatus for labeling a pixel in an image including a plurality of pixels each having a binary pixel data, comprising:

binary mask producing means receiving a series of pixel data produced through raster-scanning of said image for producing a binary mask including a predetermined number of pixel data arranged in rows and columns and having an upper row scanning an adjacent run and a lower row scanning a reference run;

run label storage means for storing run labels for respective adjacent runs;

run label read control means responsive to said binary mask for detecting a leading end of an adjacent run and responsive to the detection of the leading end of the adjacent run for reading a corresponding run label related to said adjacent run from said run label storage means;

concatenation storage means for storing run labels related to adjacent runs adjoining to a reference run and supplying a smallest run label as a concatenation data;

a concatenation table storing data representing concatenation relationship among runs on said image;

accessing means for accessing said concatenation table with the run label read from said run label storage means as an address for reading a corresponding data therefrom;

determination means responsive to detection of the leading end of said adjacent run for comparing said corresponding data from said concatenation table and said concatenation data from said concatenation storage means and determining a temporary label and a run label for the reference run according to the result of comparison; and

a temporary label feeding means responsive to a data value of a reference pixel in the reference run in said binary mask for selecting one of data indicating said temporary label from said determination means and a predetermined constant data as a final temporary label for external outputting;

a temporary label counter for supplying a count,

a final label counter for supplying a count,

first accessing means for accessing to said concatenation table with the count of said temporary counter as an address to read a first corresponding data therefrom,

coincidence detecting means for detecting coincidence n value between the count of said temporary label counter and said first corresponding data,

second accessing means responsive to said coincidence detecting means detecting non-coincidence for accessing said concatenation table with the first corresponding data as an address for reading a second corresponding data therefrom, and

write control means responsive to said coincidence detecting means detecting noncoincidence for writing said second corresponding data into said concatenation table with said count of said temporary label counter as an address.

47. The apparatus according to claim 46, wherein said coincidence detecting means includes means for incrementing the count of said final label counter.

48. The apparatus according to claim 46, wherein said write control means further includes means responsive to said coincidence detecting means detecting coincidence for writing the count of said final label counter into said concatenation table with said count of said temporary label counter as an address.

49. The apparatus according to claim 48, wherein said write control means writes said first corresponding data after the count of said final label counter is incremented in response to detection of coincidence by said coincidence detecting means.

50. The apparatus according to claim 48, further comprising output means for supplying said count of the final label counter as a final label value.

51. The apparatus according to claim 46, further comprising means for initializing said temporary label counter and said final label counter to an initial count equal in value to a minimum label value.

52. The apparatus according to claim 46, further comprising means for incrementing the count of said temporary label counter after the writing into said concatenation table by said write control means.

53. The apparatus according to claim 46, wherein said concatenation table stores analysis flags for the respective data, each of said analysis flag indicating whether a corresponding data has been processed, and wherein said first accessing means for reading a corresponding analysis flag simultaneously with the reading of said first corresponding data, and wherein said apparatus further comprising flag decode means responsive to said corresponding analysis flag indicating that the first corresponding data has been processed for supplying said first corresponding data as a final label value and for inhibiting said coincidence detecting means, said second accessing means and said write control means from operating.

54. The apparatus according to claim 53, wherein said flag decode means includes means responsive to said corresponding analysis flag means indicating that the first corresponding data has been unprocessed for enabling said coincidence detecting means, said second accessing means and said write control means.

55. The apparatus according to claim 46, further comprising output means for supplying said second corresponding data as a final label in parallel with writing operation of said write control means.

56. An apparatus for producing a final label for respective runs in a binary image through use of a concatenation table storing data each indicating concatenation destination run with run labels temporarily assigned to respective runs as addresses, comprising;

a temporary label counter for supplying a count,

a final label counter for supplying a count,

first accessing means for accessing to said concatenation table with the count of said temporary counter as an address to read a first corresponding data therefrom,

coincidence detecting means for detecting coincidence in value between the count of said temporary label counter and said first corresponding data,

second accessing means responsive to said coincidence detecting means detecting non-coincidence for accessing said concatenation table with the first corresponding data as an address for reading a second corresponding data therefrom, and

write control means responsive to said coincidence detecting means detecting noncoincidence for writing said second corresponding data into said concatenation table with said count of said temporary label counter as an address.

57. The apparatus according to claim 56, wherein said coincidence detecting means includes means for incrementing the count of said final label counter.

58. The apparatus according to claim 56, wherein said write control means further includes means responsive to said coincidence detecting means detecting coincidence for writing the count of said final label counter into said concatenation table with said count of said temporary label counter as an address.

59. The apparatus according to claim 58, wherein said write control means writes said first corresponding data after the count of said final label counter is incremented in response to detection of coincidence by said coincidence detecting means.

60. The apparatus according to claim 58, further comprising output means for supplying said count of the final label counter as a final label value.

61. The apparatus according to claim 56, further comprising means for initializing said temporary label counter and said final label counter to an initial count equal in value to a minimum label value.

62. The apparatus according to claim 56, further comprising means for incrementing the count of said temporary label counter after the writing into said concatenation table by said write control means.

63. The apparatus according to claim 56, wherein said concatenation table stores analysis flags for the respective data, each of said analysis flag indicating whether a corresponding data has been processed, and wherein said first accessing means includes means for reading a corresponding analysis flag simultaneously with the reading of said first corresponding data, and wherein said apparatus further comprises flag decode means responsive to said corresponding analysis flag indicating that the first corresponding data has been processed for supplying said first corresponding data as a final label value and for inhibiting said coincidence detecting means, said second accessing means and said write control means from operating.

64. The apparatus according to claim 63, wherein said flag decode means includes means responsive to said corresponding analysis flag means indicating that the first corresponding data has been unprocessed for enabling said coincidence detecting means, said second accessing means and said write control means.

65. The apparatus according to claim 56, further comprising output means for supplying said second corresponding data as a final label in parallel with writing operation of said write control means.