JPH0594533A - Device for extracting run - Google Patents

Abstract

(57) [Abstract] [Purpose] To realize a run extraction device that can extract black runs in image data at high speed and is easy to integrate. A first conversion table 103 for converting input image data in units of a plurality of pixels by focusing on the number of white runs included therein, and a second conversion table for converting the converted data into data for extracting black runs. 104 and circuit means 105 to 109 for obtaining the start point coordinates and the end point coordinates of the black run using the converted data, and the second conversion table is classified by the number of white runs included in one unit of image data. Each type is divided into a plurality of tables, and only necessary information determined by the corresponding type is stored in each table.

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to image processing such as character recognition, and more particularly to a run extraction device for extracting runs from binary image data at high speed.

[0002]

2. Description of the Related Art Conventionally, when a run (a continuous portion of black pixels or white pixels) is extracted from binary image data, a raster scan of the image is performed line by line to start a black run (a continuous portion of black pixels). The method of detecting the end point was common. More specifically, the image data is fetched from a memory, secondary storage, or an external device such as a scanner, but in any case, the unit of data transfer is not one pixel but a plurality of pixels. For example, one pixel is represented by 1 bit, and data is fetched in units of 1 byte, that is, 8 pixels. Then, for such image data captured in units of a plurality of pixels, black and white of the pixel is determined bit by bit in the raster scan direction, and a change point from a white pixel to a black pixel and a change point from a black pixel to a white pixel are detected. The black run is extracted by repeating the processing.

[0003]

However, since the processing time is long because the black-and-white judgment is performed in units of one pixel, and the processing flow is complicated because the black-and-white change of the preceding and succeeding pixels is judged, the run extraction is not performed. There is a problem that speeding up is difficult and the device configuration or software becomes complicated.

In order to solve the above problems, an object of the present invention is to perform run extraction processing at high speed by incorporating image data in units of a plurality of pixels by using run extraction processing as a simple process mainly based on table lookup. It is possible to provide a run extraction device that is capable of easily integrating a processing circuit including a table for run extraction.

[0005]

According to the first aspect of the present invention, a run extraction device converts input image data in units of a plurality of pixels by focusing on the number of white runs included therein. A table, a second conversion table for converting the conversion data by the first conversion table into data for extracting a black run, and a start point coordinate and an end point coordinate of the black run using the conversion data by the second conversion table Circuit means, and the second conversion table is divided into a plurality of tables according to types classified according to the number of white runs included in one unit of image data, and the division table has necessary information determined by the corresponding type. It is configured to remember only.

According to the invention of claim 2, in the invention of claim 1, the conversion data by the first conversion table includes information of a type in which the input image data is classified according to the number of white runs included therein and the input image data. And the address information corresponding to the pattern, the conversion data by the second conversion table is information on the lengths of the black run at the start position and the black run at the end position of the input image data. It is assumed to include information on the positions of the start point and the end point of the black run in which the front and back of the image data are sandwiched by white runs.

According to the invention of claim 3, in the invention of claim 2, the second conversion table includes a decoder for selectively operating the plurality of division tables according to the type information in the conversion data of the first conversion table. , A plurality of division tables are assigned with overlapping addresses.

According to the invention of claim 4, in the invention of claim 2, the information of the start point position and the end point position of the black run in the conversion data of the first conversion table is based on the start position coordinates of the input image data. Offset, the circuit means includes a run length counter for holding the length information of the black run, a coordinate holding counter for holding the start position coordinates of the input image data, and an arithmetic circuit, and the value of each counter. And the operation using the conversion data of the second conversion table is performed by the operation circuit to obtain the coordinates of the start point and the end point of the black run.

According to the invention of claim 5, in the invention of claim 4, the circuit means provides the information of the length of the black run at the start position of the input image data to the run regardless of the type of the input image data. A first process of adding to the value of the length counter is performed. When the input image data is of a type that does not include a white run, the process for the input image data is terminated after the first process, and the input image data becomes 1 When the type includes more than one white run, the value of the run length counter is 0.
Otherwise, the second process of obtaining and outputting the coordinates of the start point and the end point of one black run is performed. When the input image data is of a type including only one white run, the second process is performed after the second process. A third processing step of setting information on the length of the black run at the end position of the input image data in the run length counter is performed, the processing for the input image data is completed, and the input image data has two or more white lines. For types that include runs,
The fourth process of obtaining the coordinates of the start point and the end point of the black run sandwiched by white runs in the front and back of the input image is returned a number of times determined by the type of the input image data, and then the third process is performed to perform the input. The configuration is such that the processing on the image data is terminated.

According to the sixth aspect of the present invention, the run extraction device includes an image memory for storing image data, and a black pixel search unit for reading the image data of each line from the image memory and detecting the position of the first black pixel. A work memory for storing the position searched by the black pixel searching unit; and a run extracting unit having the configuration according to any one of claims 1 to 5, and the run extracting unit will perform processing. The run extraction process for the current line is started from the image data including the position for the current line stored in the work memory.

[0011]

As described above, according to the invention described in claims 1 to 5, the image data is fetched in a unit of a plurality of pixels and is converted by the first conversion table while paying attention to the number of white runs in the input image data. Further, since the second conversion table is used to convert the data into data for black run extraction and the start / end coordinates of the black run are obtained using this conversion data, the speed of black run extraction is facilitated, As can be seen most clearly from the description of item 5, the processing algorithm can be simplified, and as is most apparent from the description of claim 4, the device configuration can be simple.

As described in detail in connection with the embodiments,
When the input image data is classified according to the number of white runs included in the input image data, the information that needs to be provided as the conversion data of the second conversion table for the input image data increases or decreases. Therefore, if the second conversion table is divided into a plurality of tables according to the classified types as shown in claim 1 and only necessary information determined by the type corresponding to each divided table is stored, the second conversion table is obtained. It is possible to reduce the size of the ROM required to implement the above, which makes it easy to integrate the second conversion table with the circuit means. Further, as is clear from the description of claim 2, the number of bits of the conversion data of the first conversion table can be made far smaller than the number of bits of the conversion data of the second conversion table. In particular, with the configuration described in claim 3, the number of bits of the address information in the conversion data of the second conversion table is minimized as compared with the case where separate addresses are assigned to the respective division tables of the first conversion table. be able to. This is the number of input pins required for connecting the second conversion table and the LSI when the first conversion table and the circuit means are integrated as one LSI and the second conversion table is an external circuit. It means that you can reduce it. This increase in the number of pins is a major cause of large-sized LSIs and increased costs. As described above, according to the present invention, the run extracting apparatus can be easily integrated, as compared with the configuration in which the image data conversion table is a single table.

In a document image or the like, the ratio of white pixels is extremely large, and when the image data is processed in 1-byte units, it is not rare that the ratio of bytes of white pixels in all bits exceeds 90%. In many images, the number of bytes from the beginning of the line to the appearance of the first black pixel is very large in many cases. According to the invention of claim 6, the search for the position of the black pixel at the head of each line and the run extraction process are performed in parallel, and the run extraction process is performed for the image data after the byte including the black pixel at the head of each line. By starting the processing, the processing time for a line in which white pixels are continuous from the beginning can be shortened, and the run extraction processing can be further speeded up.

[0014]

BEST MODE FOR CARRYING OUT THE INVENTION An embodiment of the present invention will be described below. Here, it is assumed that image data is 1 bit / pixel and run extraction is performed with 1 byte (8 bits) as a processing unit.

The overall construction of this run extracting apparatus is as shown in FIG. 1, and among the constituent elements, for example, a broken line frame 10 is used.
Those inside 0 are integrated as one LSI package. The memory 111 can be integrated together depending on the required memory amount, and conversely, the memory address management unit 110 can be an external circuit. However, in order to utilize the advantages of the present invention, the image data interface unit 102 and the first conversion table 103 should be external circuits.

The outline of the processing is as follows. From the image data source 101 (memory, secondary storage, scanner, etc.), the image data interface unit 102 reads the image data byte by byte and inputs it to the first conversion table 103.
Bit type information and 7-bit address information are output. With this type information and address information as input, from the second conversion table 104, pre-len (4 bits), pos
Each information of t-len (3 bits), run1, run2, run3 (3 bits for each starting point coordinate and 3 bits for ending point coordinate, total 6 bits) is output. The sequence controller 105
Based on the output information of the second conversion table 104 and the type information from the first conversion table 103, the adder 108,
The control of 109, the run length counter 107, and the coordinate holding counter 106 and the sequence of the entire process are controlled to output the start / end point information of the extracted run to the memory 111.
The run length counter 107 is for holding the length of the black run, and the coordinate holding counter 106 is for holding the coordinates of the head position of the image data currently being processed. The memory address management unit 110 controls the writing of run start / end point information in the memory 111 and manages the address in accordance with a write command from the sequence controller 105. Hereinafter, the processing content and the second conversion table 1
The configuration of 04 will be described in detail.

In the present embodiment, image data of 1 byte of processing unit, that is, 8 pixels is considered as a run pattern. There are 256 (= 2 ⁸ ) patterns, and they are classified into five types shown in (Table 1) according to the number of white runs that appear. That is, the first conversion table 103 outputs the type information according to this classification using the bit pattern of the input image data as the address information.

[Table 1]

The term "white run" means that the black run is interrupted there. If there is a white run before and after the black run in the image data of interest, the black run may be confirmed and registered as a black run. Such a black run will be called a definite run. Since the maximum number of confirmed runs that appear in 1-byte data is three, they are represented as run1, run2, and run3 in the order of appearance from the top of the image data.

The number of types of run patterns of 1-byte image data is 256. When arranged by type, the number of run patterns and the number of fixed runs are as shown in (Table 2).

[Table 2]

Further, since the image data is processed in 1-byte units, it is necessary to consider the continuous run relationship with the image data of the preceding and succeeding bytes. That is, as shown in FIG. 4, the current image data of interest (data surrounded by a solid line)
Starts with a black run (hatched portion), this black run may be a continuation of the black run of the image data processed immediately before (data surrounded by a broken line). Similarly, if the current image data ends with a black run, it may be continuous with the black run of the image data to be processed next. Regarding such black runs that are continuous with the black runs in the front and back image data, it is necessary to determine and register the continuous black runs before and after as one black run when the continuous range is confirmed. Therefore, as shown in FIG. 4, the pre-len and post-len information for defining the length of the black run at the start position of the image data and the length of the black run at the end position of the image data are defined. To do. However, pre-len = 0 when the image data starts with a white run, and post-len = 0 when the image data ends with a white run.

The second conversion table 2 has the structure shown in FIG. 201 is a ROM that stores conversion tables for type 0 and type 1, 202 is a ROM that stores a conversion table for type 2, 203 is a ROM that stores a conversion table for type 3, and 204 is a type 4 It is a ROM that stores a conversion table for. Each of these RO
The address information from the first conversion table 103 is input to M. 205 decodes the type information input from the first conversion table 103 to read the ROM 201, 202, 2
This is a decoder for generating enable signals for 03 and 204.

Since the number of types of run patterns of 1-byte image data is 256, the total number of entries in the second conversion table is 256, and 8-bit address information is basically required for the access. .. However, since the ROMs 201, 202, 203, and 204 are selected according to the type, the same address is assigned to each ROM in an overlapping manner, and the first conversion table 103 outputs 7-bit address information corresponding to the run pattern of image data for each type. The table contents are created so that However,
Since type 0 and type 1 are handled in the same way, address information of values 0 to 36 is output without making a distinction. Such a first conversion table is easily realized by using the ROM.

As can be seen in Table 2 above, type 0
The number of run patterns is 1 and the number of type 1 run patterns is 3
However, since the number of confirmed runs is 0 and they can be handled together in the run extraction process, the conversion table is grouped into one table on the ROM 201 and is 0.
To 36 addresses are assigned. Each entry of the conversion table (201) is composed of a 4-bit pre-len and a 3-bit post-len, a total of 7-bit information field.

Since the number of type 2 run patterns is 126, the number of entries in the conversion table is 126. This conversion table is placed in the ROM 202 and is assigned addresses 0 to 125. Fixed run number is 1
Therefore, each entry consists of pre-len and post-len fields and a 6-bit field for start / end information of run1. The start / end point information of run 1 is the start point coordinates and the end point coordinates, which are each represented by 3 bits as an offset from the beginning of the image data as shown in FIG. This also applies to run2 and run3.

Since the number of type 3 run patterns is 84, the conversion table is placed in the ROM 203 as a table having 84 entries and addresses 0 to 83 are assigned. Since the number of confirmed runs is 2, a 6-bit field for start / end point information of run2 is added to each entry. Similarly, the conversion table for type 4 has nine entries, is placed in ROM 204, and is assigned addresses 0-8. Each entry is run3
A 6-bit field is added to the start / end point information to make it the longest.

As described above, the second conversion table is divided according to the types having different fixed runs, and the field for the unnecessary fixed run is deleted from each entry, thereby reducing the required ROM size. it can. 256 of the second conversion table 104 without distinguishing the type
The ROM size required is 2682 bits (= (1 + 36) * 6 * 2 + 126 * 6 * 2 + 84 * 6 * 1) less than the ROM size required for the same entry field structure. It becomes 3718 bits. The ROM size obtained by adding the required ROM size of 2560 bits (= 10 * 256) to the first conversion table 103 is also 6278 bits, which is required when the first conversion table 103 and the second conversion table 104 are realized as one table. The ROM size can be smaller than the ROM size of 7168 bits (= (3 + 4 + 3 + ((3 * 2) * 3)) * 256).

Since the conversion table is divided into the first conversion table 103 and the second conversion table 104 and the ROM size required for the second conversion table 104 is reduced in this way, the first conversion table 103 is used as an external circuit. , Second
The conversion table 104 has the same LS as other processing circuits.
It becomes easy to integrate it as I. In the case of further integration, it is extremely important to suppress the increase in the number of input / output pins, but the number of input information bits from the first conversion table 103 to the second conversion table 104 is as small as 10 bits. Assigning duplicate addresses to the divided tables of the second conversion table also contributes to the reduction of this bit number by 1 bit. Therefore, the first conversion table 10
Even if 3 is attached externally, the problem of the number of pins of the LSI can be avoided.

Incidentally, if the first conversion table 103 and the second conversion table 104 are the same table, it may be difficult in terms of ROM size to integrate them as the same LSI as other processing circuits. However, if the table is externally attached even if this is the case, 28 bits of information must be input from the table to the LSI of another processing circuit, and the number of input pins of the LSI becomes extremely large, which makes the LSI larger. It is not preferable because of cost increase.
As is clear from the comparison, the run extraction processing apparatus according to the present invention is much easier to integrate.

Next, the run extraction processing will be described step by step. A schematic flow of the processing is as shown in FIG. Before the processing for one line in the raster scan direction is started, the run length counter 107 and the coordinate holding counter 106 are reset (process 301), and then 1-byte image data is fetched from the image data interface unit 102 (process 302).

A table is drawn based on this image data (referred to as current data) (process 303). That is, from the first conversion table 103 to which the current data is input, the type information of the current data and the second conversion table 105
The address information for pulling is output. In the second conversion table 104, the enable signal for one of the ROMs 201, 202, 203, or 204 of the table corresponding to the type indicated by the type information becomes active, and only that ROM becomes effective, and is designated by the address information. The information of the registered entry is output.

The sequence controller 105 causes the adder 108 to add the value of pre-len output from the second conversion table 104 and the value of the run length counter 107, and holds the result value in the run length counter 107. (Process 304). If the type of the current data is 0, the run is not registered, the process immediately proceeds to step 309, the coordinate holding counter is incremented by 8, and then the process returns to step 302 to start the process of the next image data.

If the current data starts with a white run,
Since the value of pre-len is 0, the value of the run length counter 107 does not change even after addition, but when the immediately preceding data ends with a black run, the length of that black run (the value of post-len for the immediately preceding data ) Is the run-length counter 10
The value is 7, which is other than 0. On the other hand, when the immediately preceding data ends with a white run, the run length counter value after addition is 0.

In the process 304, if the type of the current data is other than 0, the pre-len value is added to the run length counter 107, and the process proceeds to the process 305.

In process 305, the sequence controller 105 does nothing if the value of the run length counter 107 is 0, and proceeds to process 310 when the type of the current data is 1.

On the other hand, when the value of the run length counter 107 is not 0, the adder 108 is made to perform subtraction (complement addition) for subtracting the run length counter value from the pre-len value, and the result value and the value of the coordinate holding register 106. By causing the adder 109 to perform addition with, the start point coordinates of one black run (this may be continued from the previous data) are obtained, and this is registered (stored) in the memory 111,
In addition, the value of the coordinate holding counter 106 and the pre-len value are added by the adder 109 to obtain the end point coordinates of the black run, and this is registered in the memory 111. At this time, by instructing the memory address management unit 110 to register one run, the registered address of the start / end point coordinate information is appropriately controlled. Then, if the type of the current data is 1, the process proceeds to step 310, and if the type is 2, 3 or 4, the process proceeds to step 306.

In process 306, the sequence controller 105 receives the ru input from the second conversion table 104.
The start point coordinate value and the end point coordinate value of n1 (both are the start position of the current data, that is, an offset with respect to the value of the coordinate holding counter 106) and the value of the coordinate holding counter 106 are added by the adder 109, and The coordinates of the start point and end point of the first fixed run are calculated and stored in memory 1
Register at 11. Then, if the current data is type 2, there is no other definite run, so the process proceeds to step 310, but if the type is 3 or 4, the process proceeds to step 306.

If the type of the current data is 3, processing 30
In 7, the start and end coordinate values of run2 and the coordinate holding counter 1
The value of 06 is added to calculate the start and end coordinates of the second confirmed run in the current data, which is registered in the memory 111, and the process proceeds to step 310. When the type of the current data is 4, after registering the second fixed run in process 307, the process proceeds to process 308, and the start and end coordinate values of the third fixed run are added by the start and end coordinate values of run3 and the value of the coordinate holding counter 106. The point coordinates are calculated and registered in the memory 111, after which the process proceeds to step 310.

In process 310, post-l of the current data
The value of en is passed through adder 108 to run length counter 3
Load to 10. Then, the process returns to the process 309, the coordinate holding counter 106 is incremented, and the subsequent image data is processed.

Run extraction will be described using the image data shown in FIG. 6 as an example. When the data D1 becomes the current data, since it is type 1, the process proceeds to step 305, but since pre-len is 0, the process returns to step 302 via steps 310 and 309. The same applies when the next data D2 becomes the current data, but the value of post-len remains in the run length counter 107. When the next data D3 becomes the current data, the black run R1 continued from the immediately preceding data D2 is extracted and registered in the process 305, and the length of the black run continuing to the end, that is, the value of post-len is the run length counter. Remain at 107. When the next data D4 becomes the current data, since it is of type 0, the value of pre-len is simply added to the value of the run length counter 107 in process 304. When the next data D5 becomes the current data, the black run R2 continued from the data D3 is registered in the process 305, and then the process 3
At 06, the confirmed run R3 will be registered.

As is apparent from the above description, categorizing the image data according to the number of appearances of white runs brings benefits such as ROM size reduction of the conversion table, but further increases processing efficiency and simplifies the algorithm. There are benefits in terms of conversion. That is, the appearance of the white run means that the black run is interrupted there, and the run registration process is required. The run registration process required by the type classified by the number of appearances of the white run. You can almost determine the number of times. There is an exception to this, that is, the image data of interest starts with a white run and the previous image data ends with a white run, or the image data of interest ends with a black run. Even if there are such exceptions, by performing unnecessary skip control of run registration processing according to the type of image data, it is possible to easily realize efficient run extraction processing that uniformly handles various run patterns. ..

Incidentally, as in the present embodiment, it is preferable to assign the same address to the type-specific table of the second conversion table, because there is an advantage that the number of input / output pins when the second conversion table is made into an LSI can be reduced. It is also permissible to assign different addresses to the table.

FIG. 7 is a block diagram showing another embodiment of the present invention. The image memory 401 is a memory for accumulating image data taken in from a scanner or the like, and the black pixel search unit 402 reads the image data from the image memory 401, searches for the top black pixel for each line, and reads the top of the black pixels. The position (x, y) is output. Work memory 403
Is a memory for storing the black pixel start position and the y coordinate of the last line for which the black pixel search is completed.
Also accessed from 04. The run extraction unit 404 is shown in FIG.
The circuit shown in FIG. 1 has the configuration in which the source 101 and the memory 111 are removed (therefore, in the following description, the reference numerals in FIG. 1 are used as appropriate). However, there is a slight difference in control of the sequence controller 105 as described later. Reference numeral 405 is a run data buffer for buffering the extracted run data. This run data buffer 405 has two lines, and one of them is used by alternately switching such that the run data of the previous line is output from the other while the run data buffer 405 is used for buffering the run data of the line currently being processed. To be done. The run data buffer 405 corresponds to the memory 111 in FIG.

Next, the operation will be described. Black pixel search unit 402
Reads the image data from the image memory 401,
The position of the head black pixel is searched for each line, and the head position (x, y) of the head black pixel is written in the work memory 403. The image data in the image memory 401 is
This is binary data in which an original image of X × Y pixels is main-scanned from left to right and sub-scanned from top to bottom. Further, the black pixel start position (x, y) indicates coordinates in which the upper left corner of the image is the origin and the x coordinate increases in the right direction and the y coordinate increases in the lower direction. If no black pixel is found by checking one line (X / 8 bytes), the black pixel head position is not written for that line. Also, when the processing of one line is completed, the y coordinate of the processed line is set to the work memory 403.
Write to the fixed area of.

The run extracting section 404 operates simultaneously with the black pixel searching section 402. The sequence controller 105 of the run extraction unit 404 reads the y-coordinate written in the fixed area of the work memory 403, and checks whether or not the black pixel search for the line which is about to start processing is completed. When the black pixel search is completed, the sequence coat roller 105 starts the run extraction for the current line. However, the x coordinate of the black pixel start position of the current line is read from the work memory 403, and the reading of the image data of the current line is started from the maximum multiple of 8 addresses that does not exceed this position. Further, at the start of the processing, the head position (x) of the first read data is initialized in the coordinate holding counter 106. That is, in the process 301 of FIG. 3, instead of resetting the coordinate holding counter 106, the head position of 1 byte including the head black pixel of the current line is initialized. The processing contents after this are as shown in FIG. If the black pixel start position of the current line is cleared, that is, if no black pixel is found, the current line is not processed and the next line is entered.

In most of the image data, all 8 bits are white pixels, and the ratio thereof often exceeds 90%. The run extraction unit 404 also reads image data, performs data conversion by table lookup, adds the run length counter 107 and pre-len, and holds the coordinate holding counter 106.
The work of incrementing is repeated, but such work is actually required for the data after the head pixel of each line, and when the processing is started from the head of each line, it is before the head black pixel. In the section, the coordinate holding counter 106 is simply incremented. Therefore,
As in the present embodiment, if the head black pixel search process on the line and the run extraction process are performed in parallel and the run extraction process is started from the byte including the head black pixel, the process is performed from the head of each line. By comparison, it is clear that the run extraction time is significantly shortened.

[0046]

As described above in detail, according to the present invention as set forth in claims 1 to 5, image data is fetched in a unit of a plurality of pixels, and this is processed by a simple process centered on table lookup. In addition, black run extraction can be performed at high speed with a simple device configuration. Further, the conversion table is divided into a first conversion table and a second conversion table, and the second conversion table is divided into a plurality of tables according to the types classified according to the number of white runs in the input image data, and each divided table is supported. By storing only the necessary information determined by the type, and by assigning overlapping addresses to the plurality of division tables of the second conversion table, the second conversion table is integrated with other circuit means, It becomes easy to use the 1 conversion table as an external circuit. According to the invention described in claim 6, since the run extraction processing in byte units is not performed from the head of each line to the portion where the first black pixel is present, run extraction can be further speeded up. Therefore, it is possible to achieve the effect that the black run in the image data can be extracted at high speed, the structure thereof is simple, and the run extracting device which is easily integrated can be realized.

[Brief description of drawings]

FIG. 1 is a block diagram showing an overall configuration of a run extraction device according to the present invention.

FIG. 2 is a block diagram showing a configuration of a second conversion table.

FIG. 3 is a flowchart showing an outline of run extraction processing.

FIG. 4 is an explanatory diagram of length information of a black run at a start position or an end position of input image data.

FIG. 5 is an explanatory diagram of start / end point position information of a confirmed run in an input image.

FIG. 6 is an explanatory diagram of an example of an image data string for explaining black run extraction processing.

FIG. 7 is a block diagram showing the configuration of another embodiment of the present invention.

[Explanation of symbols]

 101 Source of Image Data 102 Image Data Interface Unit 103 First Conversion Table 104 Second Conversion Table 105 Sequence Controller 106 Coordinate Holding Counter 107 Run Length Counter 108 Adder 109 Adder 110 Memory Address Management Unit 111 Memory 401 Image Memory 402 Black Pixel Search unit 403 Work memory 404 Run extraction unit 405 Run data buffer

Claims (6)

[Claims] 1. A run extracting apparatus for inputting image data in units of a plurality of pixels, extracting a black run, and outputting the start point coordinates and the end point coordinates thereof, paying attention to the number of white runs included in the input image data. A first conversion table for conversion, a second conversion table for converting the conversion data by the first conversion table into data for extracting a black run, and a start point coordinate of the black run by using the conversion data by the second conversion table And a circuit means for obtaining end point coordinates, and the second conversion table is divided into a plurality of tables according to types classified by the number of white runs included in one unit of image data. A run extraction device characterized by being configured to store only necessary information determined by 2. The conversion data according to the first conversion table includes information of a type in which input image data is classified according to the number of white runs included therein, and address information corresponding to a pattern of the input image data. The conversion data by the 2 conversion table includes information on the lengths of the black run at the start position and the black run at the end position of the input image data, and the black run in which the front and rear of the input image data are sandwiched by white runs. The run extraction device according to claim 1, further comprising information on the positions of the start point and the end point of the run. 3. The second conversion table includes a decoder which selectively operates the plurality of division tables according to type information in the conversion data of the first conversion table,
The run extracting apparatus according to claim 2, wherein the plurality of division tables are assigned with overlapping addresses. 4. The information of the starting point position and the ending point position of the black run in the conversion data of the first conversion table is an offset based on the start position coordinates of the input image data, and the circuit means sets the length of the black run. Including a run-length counter for holding information on the size of the input image, a coordinate holding counter for holding the starting position coordinates of the input image data, and an arithmetic circuit. The values of the respective counters and the conversion data of the second conversion table are used. 3. The run extracting apparatus according to claim 2, wherein the coordinates of the start point and the end point of the black run are obtained by performing the calculation by the calculation circuit. 5. The circuit means performs a first process of adding information on the length of a black run at the start position of the input image data to the value of the run length counter regardless of the type of the input image data. When the input image data is of a type that does not include white runs, the process for the input image data is terminated after the first process, and when the input image data is of a type that includes one or more white runs, If the value of the length counter is other than 0, the second processing of obtaining and outputting the coordinates of the start point and the end point of one black run is performed. When the input image data is of a type including only one white run, After the second processing, the third processing step of setting the information of the length of the black run at the end position of the input image data in the run length counter is performed, and the processing for the input image data is finished, Is a type including two or more white runs, a fourth process for obtaining the coordinates of the start point and the end point of the black run in which the front and back of the input image are sandwiched by white runs is determined by the type of the input image data. After returning the number of times, the third
The run extracting apparatus according to claim 4, wherein the process is performed and the process for the input image data is ended. 6. An image memory for storing image data, a black pixel search unit for detecting the first black pixel position by reading the image data of each line from the image memory, and a position searched by the black pixel search unit. And a run extraction unit having the configuration according to any one of claims 1 to 5, wherein the run extraction unit performs the run extraction process of the current line to be processed by the run extraction unit. A run extraction apparatus starting from image data including a position with respect to the current line stored in a work memory.