JPH0348981A - Closed area discriminating system - Google Patents

Abstract

PURPOSE:To shorten time for processing by providing an unreferred area information input part, taking out unreferred area information stored in a storing part, simultaneously checking reference and discriminating a closed area. CONSTITUTION:A processing start position inputted from an input terminal 37 is once stored in a storing part 35 and afterwards supplied to an input part 34. Based on unreferred information, a boundary adjacent coordinate extracting part 33 extracts boundary adjacent coordinates from the information, which are supplied from the input part 34, and outputs the coordinates from an output part 32. An unreferred area information extracting part 36 detects new information from the unreferred area information from the input part 34 and the extracted coordinates from the extracting part 33 and stores the new information in the storing part 35. These extracted unreferred area information are blocked vertically observing from a current processing row and when the plural information are generated in the same row, the coordinates are horizontally rearranged. Then, the information are stored. The input part 34 preferentially takes out the unreferred area information in a direction, where the rearrangement is not executed, and applies the information to the extracting part 33. Thus, the reference check of the information is simultaneously executed and it is not necessary to separately execute it, the time for processing can be shortened.

Description

DETAILED DESCRIPTION OF THE INVENTION [Industrial Application Field] The present invention relates to a closed area discrimination method for determining a closed area formed by one or more boundaries on a figure line by line.
For example, it is used in an image data processing device.

[Prior Art] A process in which an image data processing device is required to determine a closed area surrounded by one or more boundaries and output the closed area in the form of line-by-line data (line segment data). There is. For example, in the case of processing to fill a certain closed area with a certain specific color, it is necessary to determine the closed area.

A closed area discrimination method used in conventional filling processing will be described below. This method divides the reference area based on the unevenness of the closed area, stores the referenced area, and checks the stored referenced area as the area is divided into rows to avoid referencing the same area again. I have to.

The following description will be made assuming that the figure shown in FIG. 2 is the figure to be processed, and that the closed area surrounded by two large and small rectangular boundaries 1 and 2 is the area to be determined. Such a figure is
As shown in FIG. 3, the position between the integer values of each coordinate axis of the XY orthogonal coordinate system is defined as a pixel 3, and the value of each pixel 3 is expressed and defined as several bit data and stored in the image area.

The closed area to be determined is a certain pixel 4 within the closed area (Figure 2)
It is indicated by the coordinates of being given from the outside. Determination is performed by tracing the closed area line by line with this pixel 4 as the starting position.

FIG. 4 shows the processing procedure of this conventional method. Note that symbols (a) to (V) in FIG. 4(A) indicate the following processes (a) to (V).

(a) Each pixel is referenced from the starting position 4 in the left and right direction (horizontal direction parallel to the X coordinate axis) until boundary 1 or 2 appears (hereinafter referred to as row search).

The point where the row search starts is the search start point, the boundary that appears to the left from the search start point is the left boundary, the boundary that appears to the right from the search start point is the right boundary, and the X coordinate to the right of the left boundary is the left edge parameter coordinate. X1, the coordinates to the left of the right boundary are called right edge parameter coordinates X2.

Therefore, the left end parameter coordinate X1 is a value obtained by adding 1 to the left boundary X coordinate, and the right end parameter coordinate X2 is a value obtained by subtracting 1 from the right border X coordinate.

(b) The row below the starting position 4 where the row search was performed is set as an unreferenced area, and the Y coordinate of that row, the left end parameter coordinate X1, the right end parameter coordinate X2 in the row search including the start position, and the row from that row. Set the direction of row transition (up or down) as the 5th
It is stored in the storage unit shown in the figure (hereinafter referred to as an unreferenced stack).

(c) The result of the row search from starting position 4 is stored as a referenced area in the storage section shown in FIG. 6 (hereinafter referred to as referenced stack). Storage is performed for the Y coordinate, left end parameter coordinate X1, and right end parameter coordinate X2 of the row.

(d) In order to refer to the next row, let the Y coordinate point to the next row in the upward direction (decrease the Y coordinate value by 1). This is called upward row update.

(e) Set the left end parameter coordinate X1 obtained by the row search for the previous row as the search start point. A search is performed to determine whether the search start point is in any of the rals of all the leftmost parameter coordinates X1 and rightmost parameter coordinates X2 of the same row position stored in the referenced stack (Fig. 6). Referenced check).

Note that, at this point in time, the search result for the graphic shown in FIG. 2 is not found. Therefore, the left end parameter coordinate X1 and the right end parameter coordinate X2 for the relevant gender are set as the search starting point from the left end parameter coordinate X1 in the previous row search.
is found and stored in the referenced stack.

(f> After that, the upward row update, referenced check, and row search are repeated. The area 11 shown in FIG. 4(B) is referred upward.

(g> When the reference to area 11 ends and you enter area 12, which opens upward when viewed from area 11, the entry point to area 13 is the line one line below the current line and the right end of the previous line. The parameter coordinate X2+2 and the right end parameter X2 of the current row are added to the unreferenced stack as the Y coordinate, left end parameter coordinate X1, and right end parameter coordinate X2 of the unreferenced stack, respectively.The direction is assumed to be downward.

Generally, when storing information on an unreferenced stack,
When the leftmost parameter coordinate after the row search (the leftmost parameter coordinate for the search row) Xl is smaller than the leftmost parameter coordinate before the row search (the leftmost parameter coordinate for the previous row, therefore the search starting point) Xl, and before the row search There are cases where the right end parameter coordinate (right end parameter coordinate for a thousand rows) X2 after the row search is far from the right end parameter coordinate (right end parameter coordinate for the previous row: called the search end point) X2. The diagram of FIG. 7 shows the conditions for storing information in the unreferenced stack and the contents of the stored information.

When moving from area 11 to area 12, condition (2) in FIG. 7 is applied and information is stored in the unreferenced stack.

(h) When the first row search of the new area 12 and the storage of information in the unreferenced stack are completed in this way, the current Y coordinate, leftmost parameter coordinate X1, and rightmost parameter coordinate X2 are stored in the referenced stack. to add.

(i> From then on, similarly to area 11, area 12 continues to be referred to upward.

(j) Such repeated processing is performed until this area 12 reaches a dead end. For the target row, if all boundary pixels are between the left end parameter coordinate X1 and the right end parameter coordinate X2 before the row search, it is determined that there is a dead end.

(l() When a certain area reaches a dead end, a set of Y coordinates, left end parameter coordinates X1, right end parameter coordinates X2, and row update direction are retrieved from the unreferenced stack as new region information. Retrieved information is removed from the unreferenced stack.

<'J) In the case of the figure in FIG. 2, this moves to the upper end of area 13. - In most cases when moving to the newest area, the leftmost parameter coordinate X1 is on the boundary. In this case, reference is made until a pixel other than the boundary appears to the right from the left end parameter coordinate x1 or until the right end parameter coordinate X2 is reached. If it is the former, a row search is performed using the position as the left end parameter coordinate X1, and if it is the latter, it is determined that the area is a dead end.

In the case of the figure in FIG. 2, the former is the case, so a row search is performed starting from the newly found leftmost parameter locus IIXI, and storage is performed in the referenced stack.

Note that when moving to a new area and the extracted left end parameter coordinate X1 is not a boundary, a normal row search is performed.

(m) Repeat row update, referenced check, and row search in area 13 downward. When the reference to area 13 ends and the area 14 is entered, condition (2) in FIG. 7 is applied and storage to the unreferenced stack is executed.

(n) When the storage in the unreferenced stack is completed, the Y coordinate, left end parameter coordinate X1, and right end parameter coordinate X2 for the first row of the area 14 are stored in the referenced stack.

(0) Update rows until area 14 reaches a dead end,
Referenced check and row search are repeated.

(p> When a dead end is reached, 1 is removed from the unreferenced stack.
The set of information is retrieved and moved to a new area 15.

(q> When a row search is performed on the first row of this area 15 (the bottom row of the area 15), the right end parameter coordinate X2 of this row is significantly different from the right end parameter coordinate X2 retrieved from the unreferenced stack, and as shown in FIG. Since condition (3) is not satisfied, the information is stored in the unreferenced stack.The row search result for this row is stored in the referenced stack.

(r) Sequentially refer to this area 15 upward.

(S) If you search for the line at the top of area 15, proceed to the next line (the line to which the start position belongs), and perform a referenced check (see process (e)), the search start point will be the line where the referenced area is located. Since it is between the leftmost parameter coordinate X1 and the rightmost parameter coordinate X2, treat this line as a dead end,
Does not perform row search.

In addition, the search results in the upper row of area 15 are processed as described above (
Since the row information stored in the unreferenced stack is satisfied in step (b), the stored information is deleted from the unreferenced stack in step (b).

(1) Since it is a dead end, extract the stored information of IMl from the unreferenced stack. In this case, the above process (n
) to retrieve the stored information. In this case, information related to the lower boundary of the small rectangular boundary is extracted.

(1) If a new left end parameter coordinate is found according to the retrieved information and a referenced check is performed as the search starting point, a dead end determination result is obtained.

(V) Then, an attempt is made to take out a set of information from the unreferenced stack, but at this time, since no information is stored, all processing ends.

[Problem H to be solved by the invention] However, in the closed region discrimination method described above, different row searches are performed if the same row is in different regions separated by boundaries, and A referenced check is required for each process, which increases the overall processing time.

In addition, both the unreferenced stack and the referenced stack were configured to take referenced checks into consideration, and the referenced stack was configured to separately store information for different row searches even for the same row. A stack with large storage capacity had to be used.

The present invention has been made in consideration of the above points, and it is an object of the present invention to provide a closed region discrimination method that has a stack configuration with a small storage capacity and can discriminate closed regions at high speed.

[Means for Solving the Problem] In order to solve the problem, in the present invention, a closed region surrounded by a boundary is extracted horizontally in units of rows, and the extracted rows are moved vertically. The closed region discrimination method that repeats the extraction process is composed of the following parts.

That is, the coordinates adjacent to the boundary are extracted based on unreferenced area information, and when there are multiple pieces of unreferenced area information on the same line, one or more coordinates adjacent to the boundary are extracted simultaneously based on these pieces of information. Based on the boundary adjacent coordinate extraction unit that outputs to the outside, and the extracted boundary adjacent coordinates and unreferenced area information used for extraction, unreferenced area information about the next line and previous line of the extracted line is extracted. The unreferenced area information extraction unit to extract and the extracted unreferenced area information are stored separately into those in the upper direction and those in the lower direction when viewed from the extraction line, and the extracted unreferenced area information is stored separately. On the one hand, there is an unreferenced area information storage unit that rearranges and stores the unreferenced area information based on horizontal coordinates when multiple pieces of unreferenced area information related to the same line occur, and unreferenced area information is stored from this unreferenced area information storage unit. It is extracted and given to the boundary adjacent coordinate extraction unit,
and an unreferenced area information input unit that preferentially extracts unreferenced area information in a direction in which the unreferenced area information storage unit does not perform rearrangement.

[Action Boundary adjacent coordinate extraction section extracts boundary adjacent coordinates based on unreferenced area information given from unreferenced area information input section. At this time, if there is a plurality of pieces of unreferenced area information on the same row, a plurality of border-adjacent coordinates are simultaneously extracted based on these pieces of unreferenced area information.

The boundary adjacent coordinates extracted in this manner are output to the outside and also provided to the unreferenced area information extraction section. The unreferenced area information extraction unit is also given unreferenced area information from the unreferenced area information input unit, and extracts unreferenced area information for the rows one row above and one row below the current one from this information. do.

The unreferenced area information extracted in this way is given to the unreferenced area information storage section, and the unreferenced area information storage section divides the unreferenced area information into unreferenced area information one line above and below the current processability. and stored separately. At this time, unreferenced area information in a direction other than the direction in which the unreferenced area information input section preferentially extracts unreferenced area information is rearranged and stored.

Among the unreferenced area information stored in this way, the unreferenced area information in the preferential direction is extracted by the unreferenced area information input unit and given to the boundary adjacent coordinate extraction unit, and the unreferenced area information in the preferential direction is If there is no area information, unreferenced area information in other directions is extracted and given to the boundary adjacent coordinate extraction unit, and the process proceeds to extraction processing of boundary adjacent coordinates for a new row.

[Example] Hereinafter, an example of the present invention will be described in detail with reference to the drawings.

Here, FIG. 1 is a block diagram showing an apparatus to which the closed area discrimination method of the embodiment is applied, and FIG. 8 is a block diagram showing an image data processing apparatus configured including the closed area discrimination apparatus.

However, in Figure 8, the image area (processing figure storage device)
22 stores graphic information in units of pixels as shown in FIG. 3 mentioned above. In other words, the horizontal direction is the X coordinate,
When the vertical direction is taken as the Y coordinate, a memory of several bits called a pixel is arranged at the intersection of the integer values of both coordinates, and graphic information is stored there. The closed area discriminating device 20 of this embodiment has the configuration shown in FIG. 1, and extracts pixel information from the image area 22 by giving the position of information to be inputted to the image area input device 21 using X and Y coordinates. In this embodiment, the X coordinate increases from left to right, and the Y coordinate increases from top to bottom.

When the closed region discriminating device 20 is given an overall processing start position from the outside, it performs discriminating processing as described later while appropriately extracting pixel data from the image area 22, and sequentially outputs the discriminating results.

As shown in FIG. 1, this closed area discriminator 20 provides coordinate values to an image area input device (not shown) via an output terminal 30, and receives coordinate values from the image area input device via an input terminal 31 in response to the coordinate values. a boundary adjacent coordinate extraction unit 33 that obtains coordinates adjacent to the boundary within the closed region for each row based on the pixel data obtained and outputs the coordinates to the outside via the output terminal 32;
, an input unit 34 that provides unreferenced area information for each row to the boundary adjacent coordinate extraction unit 33, a storage unit 35 that stores unreferenced area information, and an input unit 34 that provides unreferenced area information for each row to the boundary adjacent coordinate extraction unit 33; a storage unit 35 that stores unreferenced area information; and an unreferenced area information extraction unit 36 that extracts new unreferenced area information from the unreferenced area information.

The overall processing start position input from the outside via the input terminal 37 is sent to the unreferenced area information input unit 34 via the storage unit 35.
The boundary adjacent coordinate extraction unit 33 extracts the boundary adjacent coordinates and outputs them via the output terminal 32. The unreferenced area information extraction unit 36 detects new unreferenced area information from the unreferenced area information from the unreferenced area information input unit 34 and the extraction pressure from the boundary adjacent coordinate extraction unit 33, and stores it in the storage unit 35. let

From now on, the unreferenced area information input unit 34
The unreferenced area information stored in the unreferenced area information is extracted and provided to the boundary adjacent coordinate extraction section 33.

The detailed configuration of each part of the closed region discriminating device will be described below.

P'a-133 First, the detailed configuration of the boundary adjacent coordinate extraction section 33 will be explained.

FIG. 9 is a block diagram showing the detailed configuration of the boundary adjacent coordinate extraction section 33. As described above, this boundary adjacent coordinate extraction unit 33 extracts each boundary adjacent rod in the closed area adjacent to the left boundary and the right boundary, and the left boundary detection unit 41
, right boundary detection section 42 , right internal detection section 43 , input switching section 44 , output switching section 45 , and increment section 4
6 and a decrement section 47.

The left boundary detection section 41 receives pixel data from the image area input device 21 (FIG. 8) via a terminal 48b, and receives pixel data from the unreferenced area information input section 3 via an input terminal 48a.
The left boundary appearing on the left side from the starting point of the unreferenced area information given from 4 is detected, and this detected coordinate is converted to the left boundary adjacent coordinate via the increment unit 46 and externally sent via the output switching unit 45. , unreferenced area information extraction unit 3
6 and the unreferenced area information input unit 34.

The right boundary detection unit 42 detects the right boundary appearing on the right side from the starting point given from the input switching unit 44 while receiving pixel data from the image area input device 21 via the terminal 48c, and the detected coordinates are as follows. It is converted to the right boundary adjacent coordinates via the de-increment unit 47, and the external
Unreferenced area information extraction unit 36 and unreferenced area information input unit 3
given to 4.

Here, the reason why the right internal detection section 43, input switching section 44, and output switching section 45 are provided is that the left boundary adjacent coordinates and the right boundary adjacent coordinates obtained for the previous row (both of which constitute unreferenced area information In terms of current processability, it may be divided into two or more areas due to a new boundary, and in this embodiment, in this case, it is stored as an unreferenced area and processed. This is because they are trying to execute the process as is, rather than postponing it.

FIG. 10 shows an example where these functions effectively.

The right internal detection unit 43 is given the end point (adjacent coordinates of the right boundary of the previous row) from the unreferenced area information input unit 34 via the terminal 48d, and the right boundary detection unit 42 gives information about the current line. The right boundary coordinates of are given. The right side internal detection unit 43 detects whether the right boundary detected for the current processability is on the left based on the end point coordinates, and if it is on the left, the right side internal detection unit 43 detects a portion belonging to the closed area on the right side as well. While receiving pixel data from the image area input device 21 via the terminal 48e,
Reference pixels other than the border.

At this time, if the end point coordinates are reached or a pixel other than the boundary is on the right side of the end point, it is assumed that there is no newly decomposed area and the extraction process waits for the next start point coordinates.

On the other hand, if a pixel that does not have boundary information is found to the left of the end point coordinates, it is used as the left border adjacent coordinates (starting point coordinates).
This is applied to the right boundary detection unit 42 via the input switching unit 44 to detect a new right boundary in the right direction on the same row.

Note that the input switching unit 44 selects the information from the unreferenced area information input unit 34 as the starting point for the first right boundary detection, and selects the information from the unreferenced area information input unit 34 as the starting point for the second and subsequent detections. This is to select.

Further, the output switching unit 45 outputs the coordinates from the increment unit 46 as the left boundary adjacent coordinates for the first time, and selects the output of the right side internal detection unit 43 as the left boundary adjacent coordinates for the second and subsequent times. .

As a result, in the case of the example shown in FIG. 10, two line segment portions within the closed region are extracted through a series of processes without being registered in the unreferenced region.

The unreferenced area information extraction unit 36 at Sansho -+3 is the boundary adjacent coordinate extraction unit 3
3 and the unreferenced area information inputted from the unreferenced area information input unit 34.
This is to create new unreferenced area information for 5.

FIG. 11 is a chart showing storage conditions and storage information.

The storage conditions (I> and (I[)) indicate the storage conditions when sending a row in the opposite direction to the direction of change from the previous row to the current row, and the storage condition (I[I) This shows the storage conditions when a row is sent in the same direction (forward direction) as the direction of change from the row to the current row.In addition, in the case of this example, two or more sets of left and right boundaries are created by processing a certain row. Adjacent coordinates may be output, and processing for the next row may result in 2M or more starting and ending points.

The storage condition (I> means that the coordinates adjacent to the left border of the current line are the starting point (
This is a case in which it is two or more pixels to the left of the left border (adjacent coordinates) of the previous row. In this case, the current row (
Y) minus α (-1 when the direction of change from the previous row to the current row is upward; +1 when it is downward;
Therefore, the coordinates adjacent to the left boundary of the current line are obtained as the starting point coordinate x1, and the starting point coordinate minus 2 is obtained as the ending point coordinate x2, which are given to the storage unit 35. The storage itself is performed by the storage unit 35.

Storage condition NI) is that the coordinates adjacent to the right boundary of the current line are the end point (
This is a case where the right boundary adjacent coordinates of the current row are two or more pixels to the right of the right boundary adjacent coordinates of the previous row, and the right boundary adjacent coordinates of the current row are two or more pixels to the left of the next starting point. Note that if there is one starting point in the previous row, the coordinates of the right edge of the figure are used as the next starting point.

In this case, the storage Y coordinate value is the current row (Y) minus α (same as the storage condition (I>)), the start point coordinate X1 is the end point +2, and the end point coordinate X2 is the right border adjacent coordinate. is obtained and given to the storage section 35.

Storage condition (I[I> is for storing the left border adjacent coordinates and right border adjacent coordinates obtained for the current row as the start point coordinates and end point coordinates for processing the next row,
In order to move to the next row in the forward direction, the X coordinate value is set to the value representing the current row plus the above-mentioned α.

Although not shown in FIG. 11, at the start of all processing, an unreferenced area is extracted in the opposite direction using the left and right boundary adjacent coordinates as the start and end points.

FIG. 12 is an explanatory diagram of unreferenced areas extracted according to such storage conditions.

The boundaries between the previous row and the current row are pixels marked with diagonal lines. Therefore, the starting point is the X coordinate value of pixel 51, and the ending point is the X coordinate value of pixel 52.

This starting point and the left border adjacent pixel (coordinates) of the current line 53.5
5.56, the storage condition (I>) is applied and the unreferenced area in the ■ direction is extracted.

Also, the end point and the right border adjacent pixel (coordinates) of the current line 54.
55. Comparison with 57 and the right border adjacent pixel of the current row (
coordinates) 54, 55, 57 and the next starting point (maximum
By comparison with the coordinate values), the storage condition (II> is applied and the unreferenced area in the ■ direction is extracted.The storage condition (III
>, unreferenced areas in the ■, ■, and ■ directions are extracted.

Recording board 5 Next, the storage section 35 will be explained with reference to the drawings.

Here, FIG. 13 is a block diagram showing details of the storage unit 35 and the tal fM configuration, and FIG. 14 is an explanatory diagram showing the structure of the unreferenced area stack.

As shown in FIG. 13, this storage unit 35 includes an upper unreferenced area stack 61 and a lower unreferenced area stack 62.
, an upward board storage section 63 , a downward board storage section 64 , and a downward rearranging section 65 .

The unreferenced area information to be stored extracted by the unreferenced area information extraction unit 36 (see FIG. 11) is organized into those that extend upward and those that extend downward. The information is given to the upward board storage section 63 and stored therein, and the unreferenced area information in the downward direction is given to the downward board storage section 64 and stored therein.

Extraction processing for a certain line by the unreferenced area information extraction unit 36 using the unreferenced area information of the previous line and the boundary adjacent coordinates of the current line (in some cases, the process is performed on the entire line, and sometimes on a part of the line) When the unreferenced area information stack start point information and end point information stored in the temporary storage units 63 and 64 are transferred to the unreferenced area stack 61 via the reordering unit 65 or directly and 62, and stored together with the X coordinate value. Each of the unreferenced area stacks 61 and 62 is partitioned into rows, in which starting point and ending point information are arranged in descending order of starting point coordinates.

Note that in the temporary storage units 63 and 64, unreferenced areas are arranged in descending order of starting point and ending point coordinates X1 and There is no need for However, the order of the unreferenced area information remaining in the unreferenced area stack related to the same row from the previous transfer performed before this transfer and the unreferenced area information from this transfer is not necessarily in ascending order. However, if the X coordinate value of the unreferenced area information remaining in the unreferenced area stack matches the X coordinate value of the unreferenced area information transferred from the temporary storage unit, rearrangement is performed.

As shown in FIG. 13, the rearrangement unit 6 only in the downward direction
In this embodiment, the upper unreferenced area stack 61 is replaced with the lower unreferenced area stack 6.
2, the unreferenced area information input unit 34 extracts the unreferenced area information, and when transferring the unreferenced area information from the upward board storage unit 63 to the upward unreferenced area stack 61, This is because the unreferenced area information related to the above does not remain in the upper unreferenced area stack 61.

Note that the unreferenced area stacks 61 and 62 are first-in, last-out memories.

FIG. 15 shows a case where a plurality of pieces of unreferenced area information related to the same row are stored in the downward end referenced area stack 62. Furthermore, FIG. 16 shows the contents stored in the downward unreferenced area stack 62 on the assumption that the rearrangement unit 65 is omitted.

In the case of the figure in FIG. 15, when reference is made from the starting point of the overall process, unreferenced area information (YO, Xi) regarding the Y coordinate value YO below.

0, X2, 0') is the downward unreferenced area stack 62
is stored in Thereafter, the process proceeds sequentially in the directions of arrows ■ and ■, and when moving from arrow ■ to arrow ■, unreferenced area information (YO, Xl, 1, X2, 1) is stored in the downward unreferenced area stack 62. Ru. Similarly, unreferenced area information (YO, XI, 2, X2.2), (YO
,XI,3 ,X2,3 > and (YOlXi,4 ,
X2,4) is stored. In this case, if it is assumed that the reordering unit 65 does not function, the contents stored in the downward unreferenced area stack 62 will be as shown in FIG. 16.

Although the figures in Figure 15 are arranged in ascending order, they are not necessarily stored in descending order, and since the Y coordinate values are redundant and useless, they are stored in the same row as unreferenced area information that is already stored. Every time new unreferenced area information is generated, the reordering unit 65 performs reordering.

Rearrangement is performed when transitioning from arrow ■ to ■, when transitioning from arrow ■ to ■, when transitioning from arrow ■ to, and when transitioning from arrow ■ to ■. At this time, the rearrangement is performed using the temporary storage unit 64 and the downward unreferenced area stack 62.
Since both items are rearranged in descending order, the processing time is negligible.

In the case of this figure, when the processing according to the arrow ■ is completed, as shown by the arrow ■, the processing of a plurality of parts of the closed area on the same row is performed successively.

At the start of the overall process, information on the overall process start point is stored in the upper unreferenced area stack 61, and the process is started.

Showa t 34 Next, the unreferenced area information input section 34 will be explained in detail.

The unreferenced area information input unit 34 extracts unreferenced area information, performs merging processing of a plurality of unreferenced areas, determines the end of a line, and determines the end of all processing, and transfers the starting point information and ending point information to the boundary adjacent coordinate extraction unit 33 and is output to the unreferenced area information extraction unit 36.

(i) Retrieving unreferenced area information from the unreferenced area stack 61 or 62
(adjacent coordinates of the left and right boundaries) and delete the extracted unreferenced area information from the stack. This extraction method is such that if there is information stored in the upper unreferenced area stack 61, the information is extracted from the upper unreferenced area stack 61, and if there is no information in the upper unreferenced area stack 61, information is extracted from the lower unreferenced area stack 62. Take out.

(ii) Confluence determination The unreferenced area stack stores a plurality of pieces of unreferenced area information for the same line, and the unreferenced area information for the same line may be retrieved sequentially. In this case, by extracting boundary adjacent coordinates according to the previously extracted unreferenced area information, a portion of the closed area defined by the later unreferenced area information may also be detected.

Therefore, the section in the X direction defined by the unreferenced area information extracted from the unreferenced area stack is
If it lies between the adjacent coordinates of the left and right boundaries obtained in , the common part has already been referenced, so the part that has never been seen before is used as an unreferenced area.

That is, as a starting point, the extracted right boundary adjacent coordinates +
2 and use the right border adjacent coordinates from the stack as the end point.

(iii) Row end determination Since multiple pieces of unreferenced area information related to the same row are stored in the unreferenced area stacks 61 and 62 as described above,
When the YM target value appears from the unreferenced area stack 61 or 62, it means that all the unreferenced area information related to that row has been extracted (see FIG. 14). Therefore, when the Y coordinate value is obtained, an instruction is issued to the storage unit 35 to transfer and store the storage unreferenced area information in the temporary storage units 63 and 64 to the unreferenced area stacks 61 and 62. Also, extract border adjacent coordinates! The boundary adjacent coordinates given from $33 are calculated to prepare for the reference process for the new row.

(iv) Determination of completion of all processing When both the upper unreferenced region stack 61 and the lower end referenced region stack 62 are empty, all closed regions are not determined and the determination processing is terminated.

Next, a case will be described in which a closed region surrounded by large and small rectangular boundaries used in the description of the prior art is determined by the method of the embodiment.

FIG. 17 is an explanatory diagram in this case. In addition, in the figure (
a) to (k> correspond to the following processes.

(a) Extract and output boundary adjacent coordinates by referring to the left and right boundaries from the entire processing start position. When the entire process start position is input, the unreferenced area information for the line one line below is stored in the downward unreferenced area stack 62. Further, when the boundary adjacent coordinates have been extracted, unreferenced area information including these coordinates as information is stored in the upper unreferenced area stack 61.

(b) thus proceeding to the next row upward and being referenced from left to right.

(c) In the same way, sequentially refer upward.

(d) Since the space between adjacent coordinates of the left and right boundaries has expanded and there is a downward branch, the downward branch is stored in the downward unreferenced area stack 62.

Even in this case, there is an unreferenced area in the upward direction, so
From now on, the upward reference continues until a dead end is reached.

(e) At the stage when a dead end is reached, there is no stored information in the upper unreferenced area stack 61, so the entire lower unreferenced area stack 62 is taken out, and processing (d) is performed.
Reference is made downward based on the downward branch unreferenced area information stored in .

(f> When the line is one line below the start position of all processing, two unreferenced areas occur in the same line, so while rearranging the downward unreferenced area stack 62, the two areas are moved down at the same time. Reference to direction.

(g) When the line passes the bottom edge of the small rectangular boundary,
Both areas merge to form one area, and this merged area is stored in the downward unreferenced area stack 62.

(h) Also, the area at the bottom of the small rectangular boundary is stored in the upward unreferenced area stack 61.

(i> The unreferenced area stored in process (h) is referenced, but since it is on the boundary, it becomes a dead end.

(j> Unreferenced area information regarding the merging area stored in the downward unreferenced area stack 62 is retrieved and referenced. Such processing is continued until a dead end is reached.

(k) When the lower end of the large rectangular boundary is reached, both the upper and lower unreferenced area stacks 61 and 62 become empty, so the determination process ends here.

Differences for the Canine Blind Doctor According to the above-described embodiment, closed regions can be determined without performing a referenced check unlike the conventional method, so that the processing time can be significantly shortened.

Further, since a referenced check is not performed, there is no need to store referenced areas, and the capacity of the storage section can be reduced accordingly.

The method of establishing a coordinate system for a figure to be subjected to discrimination is not limited to that of the above embodiment.

The border adjacent coordinates for each row can be extracted based on the right border adjacent coordinates in addition to the left border adjacent coordinates of the previous row.

The priority direction does not need to be limited to the upward direction, and the downward direction may be given priority.

Although reference is made to the horizontal direction and the rows are changed in the vertical direction, the direction may be selected differently from the embodiment.

Note that in the claims, the direction of line transition is referred to as a vertical direction, and the direction of extraction processing within a line is referred to as a horizontal direction.

In the above description, intermediate coating in graphic processing has been shown as an example of the application of the present invention, but the present invention can also be applied to other applications. For example, it can be used for cutting out processing in graphic processing, shape extraction processing in pattern recognition, and searching for running water routes in flood simulations.

[Effects of the Invention] As described above, according to the present invention, after a plurality of unreferenced areas on the same line are added, those unreferenced areas are referenced at the same time. Since multiple unreferenced areas are not referenced separately, there is no need for a referenced check, which reduces processing time and saves the storage area for the previously required check. Can be omitted.

[Brief explanation of drawings]

Fig. 1 is a block diagram showing an embodiment of the closed region discrimination method according to the present invention, Fig. 2 is an explanatory diagram showing an input figure used to explain the discrimination of the conventional method, and Fig. 3 is a data structure of the input figure. 4 is an explanatory diagram showing the processing procedure of the conventional method, FIGS. 5 and 6 are diagrams showing the unreferenced stack and referenced stack, respectively, of the conventional method, and FIG. 7 is an explanatory diagram showing the processing procedure of the conventional method. A diagram showing the conditions for storing information in the reference stack; FIG. 8 is a block diagram showing the positioning of the closed region discriminating device according to the present invention in the image data processing device;
FIG. 9 is a block diagram showing the detailed configuration of the boundary adjacent coordinate extraction section of the above embodiment, FIG. 10 is an explanatory diagram for explaining the operation of the internal detection section on the right side thereof, and FIG. 11 is an unreferenced area of the above embodiment. Diagram showing the extraction processing method performed by the information extraction unit, 1st
FIG. 2 is an explanatory diagram showing an example of extraction processing performed by the unreferenced area information extraction section of the above embodiment, FIG. 13 is a block diagram showing the detailed configuration of the storage section of the above embodiment, and FIG. FIGS. 15 and 16 are diagrams showing the structure of a direction-unreferenced stack, respectively, are explanatory diagrams for explaining the necessity of a rearrangement section, and FIG. 17 is an explanatory diagram showing a processing example of the above embodiment. 33... Boundary adjacent coordinate extraction unit, 34... Unreferenced area information input unit, 35... Storage unit, 36... Unreferenced area information extraction unit.

Claims (1)

[Scope of Claims] A closed region discrimination method in which a closed region surrounded by a boundary is extracted in units of rows in the horizontal direction, and the extraction process is repeated by moving the extracted rows in the vertical direction, based on unreferenced region information. Boundary adjacent coordinate extraction that extracts boundary adjacent coordinates based on multiple pieces of unreferenced area information on the same line and simultaneously extracts one or more boundary adjacent coordinates based on these and outputs it to the outside. and unreferenced area information for extracting unreferenced area information about the next and previous rows of the current processing line based on the extracted boundary adjacent coordinates and the unreferenced area information used for extraction. The extracting unit stores the extracted unreferenced area information separately into those in the upper direction and the information in the lower direction from the current processing line, and stores the same information in either the upward direction or the downward direction. An unreferenced area information storage unit that rearranges and stores the unreferenced area information based on horizontal coordinates when a plurality of pieces of unreferenced area information related to a row occurs; and an unreferenced area information input unit for giving priority to unreferenced area information in a direction in which the unreferenced area information storage unit does not perform rearrangement, the unreferenced area information input unit being provided to the adjacent coordinate extraction unit. Closed region discrimination method.