JPH03224070A - Image line thinning device - Google Patents

Abstract

PURPOSE:To secure the continuation of a line at a dividing boundary by storing an image to be processed in an image memory after dividing the image and then integrating these divided images after thinning the lines for each divided image. CONSTITUTION:An image memory 7 stores the image data outputted from an image dividing means 1 as the data including the information which shows whether a relevant picture element is tracked or not for each picture element and the information showing the relevant picture element is scheduled to be deleted or not. When the image lines are thinned, an image tracking part 3 decided whether the contour black picture element under tracking is deleted or not and sets a deletion schedule flag to the picture element to be deleted in a tracking mode. Even if a tracked black picture element to be deleted is included in a window used for tracking and deletion of the contour black picture element, this black picture element is confirmed in the window. Then a picture element deleting means 4 deletes the scheduled picture element after all contour black picture elements are tracked. Thus the coincidence is always secured between the line thinning results of an image at a margin part of each divided image. Then the line continuation is secured at a dividing boundary.

Description

[Detailed Description of the Invention] [Summary] This invention relates to an image thinning device that thins a line graphic image such as a figure or character, particularly an image thinning device that thins each divided image of a large line graphic image. , an object of the present invention is to provide an image thinning device that ensures continuity of lines at dividing boundaries in an image obtained by dividing a processed image and storing it in an image memory, thinning each divided image, and integrating the divided images, If the size of the storage device that stores image data and the size of the image data to be processed stored in the storage device is equal to or larger than a set value, the image data to be processed is divided into at least two images having mutually overlapping parts near the dividing boundary. an image dividing means that divides the image data output from the image dividing means, and information indicating for each pixel whether the pixel has been tracked or not and information indicating whether the pixel is scheduled to be deleted. an image memory for storing image data as image data; an untracked pixel discovering means for discovering black pixels on the outline of an untracked image on the image memory; and a pixel discovered by the untracked pixel discovering means as a starting point. an image tracking means for tracking outline black pixels of an image and writing information indicating pixels scheduled to be deleted and information indicating traced pixels not to be deleted on the image memory; and information on the pixels scheduled to be deleted on the image memory. and a divided image integrating means that deletes the overlapping portion of the image data on the image memory and stores the same in the storage device.

[Industrial Application Field] The present invention relates to an image thinning device that thins line images such as figures and characters, and particularly relates to an image thinning device that divides a large line image and thins each divided image. Regarding equipment.

In recent years, various drawings etc. are input into a computer and CAD,
When using data in a CAM system, it is common to first input it as polygonal line data that is easy to handle for a computer. In this case, the black pixels of the current image data are thinned to obtain polygonal line data (vectorized data).

By the way, vectorizing a large drawing requires a large amount of memory. For example, an AO size drawing is 400 dp
White with a density of i (dot per 1nch)
Reading in binary black requires approximately 32MB (megabytes) of memory. Therefore, if it is necessary to store a plurality of drawings, a very large amount of memory is required, leading to an increase in the size and cost of the device. Therefore, in order to be able to process large images with a work memory that has a walking capacity, the image stored in a storage device such as a magnetic disk is divided, and each divided image is stored in the work memory to perform line thinning processing. An improved image thinning device that can perform this process reliably is being realized, but since the continuity of lines in the thinned image may not be ensured when integrating divided images, an improved line thinning device that can perform this integration reliably is being developed. It is hoped that this will be realized.

[Conventional technology]

FIG. 8 is a schematic block diagram of a conventional image thinning device, and the thinning process performed by this image thinning device will be explained with reference to FIG. 9.

The storage device 6 is specifically a large-capacity storage medium such as a magnetic disk, and includes a to-be-processed image storage area 61 in which an image to be thinned is stored and a thinning area in which an image after the thinning process is stored. It consists of an image storage area 62. In the processed image storage area 61, for example, a black pixel has a value of "1", and a white pixel has a value of "0".
Binarized image data is stored.

Reference numeral 22 denotes an image memory that serves as a work memory for performing thinning processing on the image to be processed, and when the image to be processed is larger than the set size (at least larger than the storage capacity of the image memory 22), The image dividing means 1 divides the image to be processed into sizes that can be stored in the image memory 22. The divided images are then sent to the image memory 22 one screen at a time.

At this time, several pixels along the dividing border line are removed from the margin area (
Overlapping parts) are added.

FIG. 9(a) is a diagram showing an example of an image to be processed, and in this example, this is divided into upper and lower halves by a dividing boundary line indicated by a dashed line. In FIG. 9(a), the area between the two broken lines is the margin area, and the upper divided image shown in FIG. 9(b) is as follows:
Pixels in the margin portion below the dividing boundary line are added and sent to the image memory 22. This is because if you simply divide from the division boundary line as described below, black pixels near the division boundary line will be deleted due to thinning, and as a result, the connection of the divided parts may not be successful when integrating the divided images. This is to avoid this.

The untracked pixel finding means 2 searches for black pixels by scanning pixels from the upper left of the image stored in the image memory 22. When a black pixel is detected, the image tracking/deletion means 21 tracks the black pixel forming the outline of the image from the detected black pixel (■ in the figure). For the black pixel being tracked, the values of the surrounding 8 pixels are checked using a 3 x 3 window, and the combination of the values of the 8 pixels described above (the value ``1'', which is a black pixel, and the value ``0'', which is a white pixel) is determined. By referring to a table of 28=256 combinations of binary values, it is determined whether the pixel is to be deleted (set to a white pixel with the value "0") or not.

This contour tracing and deletion is repeated until there are no more black pixels to be deleted. If the image for which the thinning process has been completed is a divided image, the divided image integrating means 5 stores it in the thinning image storage area 62 of the storage device 6.

The above-described thinning process is executed for all divided images, and the thinned divided images are stored in the thinned image storage area 62 of the image memory 6. When storing, if another divided image that has undergone line thinning processing is stored, the divided image integrating means 5
deletes the pixels of the ground surface from the division boundary line from the margin part, integrates them, and stores them.

FIG. 9(C) is a diagram showing the state in which the thinning process of the divided image in FIG. 9(g)) has been completed, and FIG. It is a figure showing an image. Note that actually, after the thinning process for the upper divided image is completed, the thinning process for the lower divided image is performed next, but both are shown at the same time in this figure for the sake of explanation.

In the upper and lower divided images in FIG. 9(C), pixels in the margin portion have been deleted by thinning. However, since what was deleted was the other side of the dividing boundary line, the lines of the upper and lower thinned images are continuous during integration.

[Problem to be solved by the invention]

However, in the conventional image thinning device, pixels are deleted during contour tracing as described above. For this reason, if the order in which black pixels in the margin portion are tracked and deleted for each divided image is different, the deletion results may differ.

For example, when the image shown in Figure 10 is divided into upper and lower parts and subjected to line thinning processing, the starting point for tracing black outline pixels is as shown in Figure 11 (a
) In the upper divided image 1, the starting point is 1, and the 11th
This is the starting point 2 in the lower divided image 2 shown in Figure (b).

Therefore, if the outline black pixels are traced and deleted for each divided image, inside the area surrounded by the two-dot chain line in the margin part in FIGS. 11(a) and 11(b),
As shown by arrows and numbers (■ and ■ indicate which one is tracked first), in divided image 1, black contour pixels are tracked from the right side, while in divided image 2, black contour pixels are traced from the left side. .

Here, an example of deletion of outline black pixels for each image will be explained by showing the inside of the above-mentioned two-dot chain line in FIG. 13 for divided image 1 and FIG. 14 for divided image 2. For the purpose of explanation, we will use the first window of the 3x3 window as an example.
It is assumed that the central black pixel, which is the pixel being tracked, is deleted only in the case of the two types of patterns shown in FIGS. 2(a) and (b). (In actual thinning processing, there are many types of patterns to be deleted, and the patterns may change depending on the number of deletions, but this is simplified for the sake of explanation.) First, as shown in Figure 13, the divided image In case 1, Fig. 13(a) during right side tracking and Fig. 13(b) during left side tracking.
In , the 3×3 window matches the deletion pattern and the central pixel is deleted, so the deleted result is the 13th pixel.
The result will be as shown in Figure (C).

On the other hand, in the case of divided image 2 as shown in Figure 14, in Figures 14 (a) and (b) during left side tracking, the 3x3 window matches the deletion pattern and the central pixel is deleted. , the deleted result is as shown in FIG. 14(b).

If the thinning results differ in the margin area as in this example, the thinned screen may not connect smoothly when the divided images are combined, and the lines may not connect at the dividing boundaries, so correct vectorized data may not be obtained. The problem arose that it could not be done.

An object of the present invention is to provide an image thinning device that can ensure continuity of lines at division boundaries in an image obtained by dividing an image to be processed, storing it in an image memory, thinning each divided image, and integrating the divided images. shall be.

[Means to solve the problem]

In order to solve the above problems, the image thinning device of the present invention includes: a storage device 6 that stores image data; and, when the size of the image data to be processed stored in the storage device 6 is larger than a set value, an image dividing means 1 for dividing the image data to be processed into at least two images having mutually overlapping parts near the dividing boundary; An image memory 7 that stores image data as image data having information indicating whether it has been tracked or not and information indicating whether it is scheduled to be deleted; and black pixels at the outline of the image that is not tracked on the image memory 7. An untracked pixel discovering means 2 detects the pixel detected by the untracked pixel discovering means 2, and traces the outline black pixel of the image using the pixel discovered by the untracked pixel discovering means 2 as a starting point, and detects information indicating the pixel to be deleted and information indicating the pixel that has been tracked and deleted. an image tracking means 3 for writing information indicating pixels to be deleted on the image memory 7; a pixel deletion means 4 for deleting pixels having information to be deleted on the image memory 7; The image forming apparatus is configured to include divided image integrating means 5 for deleting the overlapping portions of data and storing the data in the storage device 6.

[Effect]

That is, in the image thinning device of the present invention, the image memory 6, which serves as a work memory for image processing, stores information for each pixel indicating whether the pixel has been tracked or not, and information indicating whether the pixel is scheduled to be deleted. It shall have information indicating. When thinning the image on this image memory 6, the image tracking unit determines whether the contour black pixel being tracked is to be deleted or not. Since it only sets a flag and does not immediately delete it, even if there is a black pixel scheduled for deletion that has already been tracked within a 3x3 window used to track outline black pixels and determine whether to delete them. This is determined as a black pixel within the window. After tracing all the outline black pixels, the pixel deletion means 4 deletes the pixels to be deleted.

Therefore, even if the order of tracking by the pixel tracking means 4 is different, the black pixels to be deleted will be the same, so the thinning results of the images in the margins of each divided image will always match, and the thinning images will be the result of the integration. It also continues smoothly.

〔Example〕

FIG. 2 is a block diagram showing the configuration of an embodiment of the present invention.

In the figure, the same parts as in FIGS. 1 and 8 are given the same reference numerals. Reference numeral 10 denotes an image processing device that performs image dividing and thinning processing; an image dividing unit 11 that divides the image to be processed and stores it in the image memory 7 when the size of the image to be processed is larger than the storage capacity of the image memory 7; Untracked image finding unit 1 that scans the memory 7 to find untracked black contour images
2. A pixel tracking unit 13 that tracks the contour image and stores the tracked pixels as tracked pixels and deletion candidate pixels in the image memory 7, deletes pixels that are deletion candidates, and resets the traced flag of the traced pixel. image deletion unit 14,
It is composed of an image integrating section 15 that integrates the divided images on which the thinning process has been completed, and a control section 16 that controls a series of divided thinning processes of the main image dividing and thinning apparatus.

FIG. 3 is a diagram showing the pixel representation of the image memory 7, and in this embodiment, each pixel has 3 bits of information. As shown in Figure 3 (a), this is a white/black determination bit that has a value of ``0'' if it is a black pixel and a value of ``1'' if it is a white pixel, and a bit that indicates that the pixel has already been tracked. A tracked flag determines whether the pixel is to be deleted, and a deletion schedule instruction flag indicates that the pixel is scheduled to be deleted.

Expressing this for each pixel state, as shown in Figure 3(b), in the case of a white pixel, all bits have the value ゛0゛, and the third
As shown in Figure (C), in the case of an untracked black pixel, the white/black determination bit has a value of "1" and the other bits have a value of "0".

In addition, as shown in FIG. 3(d), black pixels that have been tracked and will not be deleted have the white/black determination bit set to the value ``1'' and the deletion schedule instruction flag set to the value ``0''. Since the deletion schedule instruction flag also takes the value '1', all bits take the value '1' as shown in FIG. 3(e).

Hereinafter, the details of the operation of one embodiment of the image dividing and thinning apparatus of the present invention will be explained based on the flowchart of FIG. Note that the image to be processed is the image shown in FIG. 10 as in the prior art described above.

(1) When the image data amount of the processed image stored in the processed image storage area 61 in the storage device 6 is larger than the storage capacity of the image memory 7, the image dividing unit 11 The image is divided by determining how much margin should be taken for pixels around the dividing boundary, and one screen of the divided image is stored in the image memory 7. When there is no need to divide the image to be processed, the image to be processed is stored in the image memory 6 as it is.

In FIG. 10, which is an example of dividing an image into two, the upper divided image 1 is stored first.

(2) The untracked pixel discovery unit 12 discovers untracked contour black pixels in each divided portion. That is, each row is scanned from the upper left pixel of the image with the X direction (horizontal direction) as the main scanning direction, and black pixels that have not been tracked, that is, the tracked flag has a value of 0° and the white/black determination bit is A pixel with a value of "1" is found. This pixel becomes the starting point for tracing the outline of a black pixel. In the example of divided image 1 in FIG. 11(a), starting point 1 is found.

The black pixel tracking unit 13 tracks contour black pixels starting from the black pixel at the starting point 1 found first in (2) above. In this embodiment, since the outline is tracked in a counterclockwise direction, black pixels are initially tracked in a downward direction.

The black pixel to be tracked can be determined in the tracking direction by referring to the values of the 8 pixels surrounding the pixel to be tracked (whether it is a black pixel or a white pixel "0") using a 3 x 3 window. and whether or not to delete the black pixel.

In the tracking process, the tracking direction is always kept in mind, and scanning is performed so that, for example, the right-hand direction in the traveling direction is always a black pixel.

Also, the possible combinations of the values of the surrounding 8 pixels are 2”=2
There are 56 combinations, and it is determined which of the following processes will be performed based on this combination.

The black pixel currently being tracked is considered to have been tracked and the tracked flag is set to the value "1".For the black pixel scheduled to be deleted based on the following logic, the deletion schedule instruction flag is set to the value "1".

FIG. 5 shows an example in which the contour tracing of the region within the dashed-two dotted line in FIGS. 13 and 14 is performed once using the image dividing and thinning apparatus of this embodiment. Furthermore, the black pixel in the center of the 3×3 window is scheduled for deletion when it matches the pattern shown in FIGS. 12(a) and 12(b).

This 3×3 window refers only to the values of the white/black determination bits of the surrounding eight pixels. Since the deletion scheduled flag is not related to the pattern of this 3×3 window, black pixels scheduled to be deleted are handled in the same way as untracked pixels and tracked pixels that are not deleted. Therefore, even if the tracking order is different in both divided images 1 and 2, the 3×3
Since the arrangement of black pixels in the window is the same, the tracking results are as shown in Figure 5 (Q)), and the state in which the pixels to be deleted are deleted after the -th tracking is completed is shown in Figure 5 (C). It will be as shown.

Note that if it is the outermost pixel of the divided image and the surrounding eight pixels cannot be removed, the above process is performed with the non-existing pixel as a white pixel (value 0°).

(4) When the process (3) is completed for one black pixel contour, that is, when the black pixel tracking completes one round to the starting black pixel, the untracked pixel discovery unit 12 detects the untracked contour black pixel in the above (2) ), the outline black pixel is tracked using the found untracked pixel as a starting point, and the process (3) above is performed. In the example of divided image 1 in FIG. 11(a), starting point 1
When the scanning of the outline black pixels starting from 1 is completed, this starting point 1
The untracked contour black pixels are scanned from the black pixels of .

(5) If a new untracked pixel is not found, the pixel deletion unit 14 deletes the black pixel for which deletion was instructed in (3) above and makes it a white pixel, and the black pixel that has already been tracked is tracked. Reset the completed flag.

Specifically, the pixel deletion unit 14 scans the divided image to search for a pixel whose tracked flag has a value of ``1'', sets the tracked flag to a value of ``0'' for the found pixel, and deletes the value of the pixel. When the deletion schedule instruction flag has the value "1", the deletion schedule instruction flag and the white/black determination bit are each set to the value "0".

Further, after the above scanning is completed, if there is no pixel whose deletion schedule instruction flag has the value "0" during scanning, the image deletion unit 14 sends the divided image integration unit 15 and the control unit 16 to terminate the thinning process. Notify.

(6) If the thinning process has not yet been completed, repeat the process described above (
2) to 5) are performed for tracking and deleting the contour black pixels.

Furthermore, if the deletion pattern of the 3×3 window changes depending on the number of tracking deletion processes, the image deletion unit changes this.

FIG. 6(a) shows a state in which the tracking and deletion processing of contour black pixels has been completed several times in divided image 1, and the line thinning processing has ended because there are no pixels to be deleted in the final tracking. There is.

(7) The divided images that have undergone the thinning processing up to (6) above are read out from the image memory 7 by the image storage section 15 and stored in the thinned image storage area 62.

In this case, pixels in the margin portion set for each divided image are discarded and stored.

(8) If there is a divided image that has not been subjected to line thinning processing, perform the line thinning processing shown in (2) to 7) above.

The process ends when all divided images are subjected to line thinning processing and stored in the thinned image storage area.

Divided image 2 in FIG. 11(C) is also subjected to line thinning processing using the same processing method, resulting in the state shown in FIG. Stored. This stored and integrated image is shown in FIG.

In the example in Figure 6, the black pixels within the dashed-double line area are deleted from the periphery, but if a sufficient margin is set aside to accommodate this black pixel degeneration, it will be possible to solve the problem as explained in (3) above. Since the black pixels near the dividing boundary line of each divided image match, the continuity of the dividing boundary line is ensured when the images are integrated.

In this embodiment, it is assumed that each pixel has 3 bits of data, but in reality there are three types of black pixels (untracked black pixels, black pixels that have been tracked and are scheduled to be deleted, and black pixels that have been tracked and are not to be deleted). ), and since there is only one type of white pixel that is not tracked, the data required for each pixel may be 2 bits that can represent four types of states. Furthermore, the logic for tracking and determining the pixel to be deleted is not limited to the method used for a 3×3 window, and may be based on another logic such as using a window of other size.

〔Effect of the invention〕

As explained above, according to the present invention, even if large image data is divided and stored in the work memory and lines are thinned for each divided image, continuity of the lines is ensured at the division boundaries when integrated. Therefore, it is possible to realize an image thinning device that can reliably thin large image data to obtain hectorized data.

[Brief explanation of drawings]

Fig. 1 is a diagram showing the principle configuration of the present invention, Fig. 2 is a block diagram showing the structure of an embodiment of the present invention, Fig. 3 is a diagram showing an example of pixel expression on the divided image memory, and Fig. 4 is a diagram showing the main structure of the present invention. Flowchart showing the operation of one embodiment of the invention. FIG. 5 is a diagram showing a state in which the outline of a part of a divided image is traced according to one embodiment. FIG. 6 is a state in which thinning of the divided image in FIG. 11 is completed. , FIG. 7 is a diagram showing a state in which the divided images in FIG. 6 are integrated, FIG. 8 is a schematic configuration diagram showing a conventional image thinning device, and FIG. 9 is an image thinning process according to a conventional technique. Figure 10 is a diagram showing an example of an image to be processed, Figure 11 is a diagram showing a state in which the image to be processed is divided, and Figure 12 is a diagram showing an example of a 3x3 window in which pixels being tracked are deleted. A diagram showing an example of a pattern. FIG. 13 is a diagram showing a state in which the contour of a part of divided image 1 is traced using the conventional technique. FIG. 14 is a diagram showing a state in which the contour of a part of divided image 2 is traced by the conventional technique. It is. In the figure, 1... image dividing means, 2... untracked pixel finding means, 3... pixel tracking means, 4... pixel deletion means, 5... divided image integrating means, 6... Storage device, 7... Image memory. Structure and illustration of the embodiment of the present invention 17 Old/77 Figures 1 - Revision/Residue flag 11 Deletion schedule instruction flag' (1:j) Pixel expression Bilt 2 Hijiru 1hi 1. To○ Pi・, To2 Hi℃, To I L=7 To O L:, To2 and soup 1 bit O Bi °l To 2 Bi・Juice IL゛ Juice 0 Divided picture 1 elephant memory 70 picture expression An example of Σ is an opening diagram showing ○○○○○○○ (α) Divided image t (b) 1 image in division 2 - ``Door 1 J Isuzu Ding elephant st, R combination L7 == down jri mai, I must show the gl of the engraved drawing ○ Figure black drawing umbrella delete Σ ding 1''t Figure (U) ntlMiii 1 (b) TeTori image 2 The input image and the input image are divided into two parts.

Claims (1)

[Claims] A storage device (6) for storing image data; and if the size of the image data to be processed stored in the storage device (6) is equal to or larger than a set value, the image data to be processed is separated by a dividing boundary. at least two having portions that overlap each other in the vicinity
an image dividing means (1) for dividing into two images, and image data output from the image dividing means (1),
an image memory (7) that stores each pixel as image data having information indicating whether the pixel has been tracked or not and information indicating whether the pixel is scheduled to be deleted; and the image memory (7). untracked pixel discovery means (2) for discovering black pixels on the outline of the image that are not tracked above, and tracking black pixels on the outline of the image using the pixel discovered by the above untracked pixel discovery means (2) as a starting point an image tracking means (3) for writing into the image memory (7) information indicating pixels scheduled to be deleted and information indicating pixels that have been tracked and will not be deleted; pixel deletion means (4) for deleting pixels having information; and divided image integration means (4) for deleting the overlapping portions of the image data on the image memory (7) and storing the same in the storage device (6). 5) An image thinning device comprising: