JP3883993B2 - Image processing apparatus, method, and program - Google Patents

Description

  The present invention relates to an image processing apparatus, method, and program for detecting a specific shape such as a straight line or an arc included in a contour shape as preprocessing when the contour shape of an input image is functionalized.

  Advances in information technology have made remarkable progress in the technical fields that handle images such as desktop publishing (DTP), television broadcasting, and books, and the need for higher definition and beauty is also increasing. In addition, with the spread of personal computers and various devices surrounding them, digital images have become higher in definition and higher in processing speed. In particular, image compression, enlargement / reduction, and the like represented by JPEG, GIF, PNG, etc. The progress of image conversion technology is remarkable.

  However, pixel encoding methods represented by these general JPEG, GIF, and PNG have proposed a function encoding method because image quality deteriorates, for example, jaggy noise occurs during enlargement. Research has been conducted on a method of automatically converting a pixel-encoded image into a function-encoded image by tracking the contour of the image and approximating it (see, for example, Patent Document 1).

For example, images such as characters, illustrations, and logo marks can be functionalized with high accuracy by a fluency function system. In the fluency information theory, the signal space is categorized using a parameter m based on the continuous differentiability indicating the standard of signal smoothness. The m-th order fluency function is composed of a (m-1) th order piecewise polynomial that can be continuously differentiated only (m-2) times. In the image function approximation, the contour line is approximated using a function of a type depending on its shape. The fluency functions of m = 2, m = 3, and m = ∞ are used to represent a straight line, a free curve, and an arc, respectively.
Japanese Patent Laying-Open No. 2001-51670 (page 5-13, FIG. 1-11)

  By the way, in the method disclosed in Patent Document 1 described above, as a pre-processing for functionalizing the shape of the contour line, a portion that is clearly determined as a straight line is detected as a straight line section, and is determined as such a straight line. When the portions are adjacent to each other, a process for extending the straight section by combining these adjacent portions is performed. In this way, when a short straight line section that constitutes a part of the contour line is extended and the error between the contour line shape and the straight line is small, the straight line section is gradually extended. If there is a short section, even if the surrounding area is a straight section, the whole is not judged as one straight section, and it is easy to detect a long section of a single shape because it is susceptible to errors. There was a problem. The longer the section of a single shape that is detected, the more advantageous in determining an approximate function that is performed thereafter from the viewpoint of reducing the amount of data. In addition to detecting a straight section, there is a similar problem when detecting an arc section.

  The present invention was created in view of the above points, and an object thereof is to provide an image processing apparatus, method, and program capable of detecting a long section of a single shape included in a pixel column. It is in.

  In order to solve the above-described problems, an image processing apparatus of the present invention includes an image input unit that inputs an image, a segment extraction unit that extracts a plurality of segments indicating the shape of an image input by the image input unit, Function section detection that detects the section corresponding to the approximate function by reducing the segment length for the segment extracted by the segment extraction means, using the start and end points of this segment as the initial state until the error falls below the reference value Means.

  Further, the image processing method of the present invention includes a first step of inputting an image, a second step of extracting a plurality of segments indicating the shape of the input image, and the extracted segment. And a third step of detecting a section corresponding to the approximate function by reducing the segment length until the error becomes equal to or less than the reference value with the start point and end point of the segment as an initial state.

  The image processing program according to the present invention includes a computer, an image input unit that inputs an image, a segment extraction unit that extracts a plurality of segments indicating the shape of an image input by the image input unit, and a segment extraction unit. With respect to the extracted segment, with the start and end points of this segment as the initial state, the segment length is decreased until the error becomes equal to or smaller than the reference value, and the segment is made to function as a function section detecting unit that detects a section corresponding to the approximate function. .

  In this manner, since the segment corresponding to the approximate function is detected by gradually shortening the segment until the error is reduced with the entire segment as an initial state for each segment indicating the shape of the image, the short corresponding to the approximate function Compared to the case where the section is gradually extended after detecting the section, it is possible to detect a long section having a single shape corresponding to the approximate function.

  In addition, the above-described segment extraction unit includes a junction point extraction unit that extracts a junction point included in the pixel column corresponding to the contour line of the image, and a plurality of pixel columns with the junction point extracted by the junction point extraction unit as a boundary. It is desirable to have segment dividing means for dividing into segments. Thereby, the section corresponding to the approximate function included in the contour line of the image can be detected in the longest possible state.

  Moreover, it is desirable that the junction point extraction unit described above extracts pixels corresponding to obvious corner points as junction points based on the arrangement of pixels before and after. By extracting only apparent corner points as joint points, it is possible to prevent a long section of a single shape from being erroneously divided due to an inappropriate joint point setting position.

  Moreover, it is desirable that the approximate function for which section detection is performed by the above-described function section detection means is a straight line. Thereby, it is possible to detect a long straight line portion included in the shape of the image. Further, it is desirable that the approximate function for which the section detection is performed by the above-described function section detecting means is a circular arc. As a result, a long arc portion included in the shape of the image can be detected.

  In addition, the approximation functions for which section detection is performed by the above-described function section detection means are straight lines and arcs, and for each of a plurality of segments, section detection corresponding to the straight lines and section detection corresponding to the arcs are performed separately. Is desirable. Accordingly, it is possible to detect a long straight line portion and a long arc portion included in the shape of the image, and it is possible to perform an optimum functionalization process using each detection result. In particular, it further includes a functionalization processing means for performing functionalization processing by applying an arc, a straight line, and a free curve in the order of the arc, straight line, and the portion other than the arc and the straight line detected by the above-described function section detection means. Is desirable. As a result, by performing function processing by giving priority to arcs and straight lines over free curves, it is possible to further reduce the amount of data by function processing. Further, it is preferable that the functionalization processing unit described above performs the functionalization processing by giving priority to the circular arc when the common pixel is included in the circular arc and the straight line detected by the functional section detection unit. Since an arc can also be expressed as a collection of short straight lines, it is possible to perform highly accurate function processing by giving priority to the arc.

  The function section detecting means described above sets all or part of the segments as detection candidates, and if the error between this detection candidate and the straight line connecting the start point and the end point exceeds the reference value, the detection candidate is selected. On the contrary, when the error is equal to or smaller than the reference value, it is desirable to detect the finally determined detection candidate as a section corresponding to a straight line by lengthening the detection candidate. As a result, it is possible to gradually narrow down the straight line portion included in the segment and detect the longest straight line portion that can be finally detected.

  The above-described function section detection means sets all or part of the segments as detection candidates, and the error between the detection candidate and the arc passing through the start point, end point, and other intermediate points exceeds the reference value. In this case, it is desirable to detect the detection candidate finally determined as a section corresponding to the arc by shortening the detection candidate and conversely increasing the detection candidate when the error is equal to or less than the reference value. As a result, it is possible to gradually narrow down the arc part included in the segment and detect the arc part of the maximum length that can be finally detected.

  Further, it is desirable that the above-described function section detecting means lengthens or shortens the detection candidate by L / 2, where L is the length of the detection candidate so far. Thereby, it is possible to reduce the number of times of changing the length of the detection candidate until the straight line portion or the arc portion is finally detected, and the time required for detecting the straight portion or the arc portion can be shortened.

  Further, it is desirable that the above-described function section detecting means calculates an average value e1 of the square of the distance between each pixel constituting the detection candidate and the approximate function to be detected as an error. By evaluating the magnitude of the error based on the mean square error e1, it is possible to reduce the influence of noise generated in image reading or the like.

  Further, it is desirable that the above-described function section detecting means calculates the maximum value e2 of the square of the distance between each pixel constituting the detection candidate and the approximate function to be detected as an error together with the average value e1. The longer the straight line portion or arc portion to be detected, the smaller the mean square error e1 even if there is a local singular shape that does not match the shape of these approximate functions, so this singular shape portion is ignored. It becomes easy to perform functionalization processing. However, since the maximum square error e2 is taken into account, the local singular shape is not ignored, and highly accurate functionalization processing can be performed.

  Hereinafter, an image processing apparatus according to an embodiment to which the present invention is applied will be described in detail with reference to the drawings.

  FIG. 1 is a diagram illustrating a configuration of an image processing apparatus according to an embodiment. As shown in FIG. 1, the image processing apparatus according to this embodiment includes an image processing calculation unit 100, a scanner 200, a keyboard 210, a mouse 212, a display device 220, and a printer 230.

  The scanner 200 optically reads a subject such as a logo mark and generates a monochrome binary image. The generated binary image is input to the image processing calculation unit 100. The keyboard 210 and the mouse 212 are used by the user to give various operation instructions to the image processing calculation unit 100. For example, an operation instruction for image capture using the scanner 200, a calculation start instruction for subsequent functionalization processing, a restoration instruction from the functionalized image data to the original image, an enlargement magnification at the time of restoration, and the like are displayed on the keyboard 210. Or using the mouse 212.

  The display device 220 displays various operation screens, results of restoring the original image using the captured image and the functionalized image data, and the like. The printer 230 prints the restored original image with a predetermined magnification on paper of a predetermined size.

  The image processing calculation unit 100 performs a functionalization process on the input image and performs a process of generating an image based on the functionalized data. For this purpose, the image processing calculation unit 100 includes an image storage unit 110, a pixel row tracking unit 120, a joint point extraction unit 130, a segment division unit 140, a straight line detection unit 150, an arc detection unit 160, a functionalization processing unit 170, and an output. An image generation unit 180 is provided. The image processing arithmetic unit 100 can be realized by a computer having a CPU, a ROM, a RAM, and a hard disk device, and an image processing program stored in the ROM, RAM, or hard disk device is executed by the CPU. The functions of the pixel row tracking unit 120, the junction point extraction unit 130, the segment division unit 140, the straight line detection unit 150, the arc detection unit 160, the functionalization processing unit 170, and the output image generation unit 180 are realized. The image storage unit 110 is realized mainly by a hard disk device.

  The image storage unit 110 stores image data corresponding to an original image read using the scanner 200, intermediate data necessary for performing functionalization processing, functionalized data obtained by the functionalization processing, and the like. .

  The pixel column tracking unit 120 performs tracking processing on the pixel columns that form the contour line of the input image. For example, the process of extracting the contour line is performed on the input image after the binarization process. When a multi-valued image is input instead of a binarized input image, the binarization process may be performed as a pre-process for the pixel column tracking process. Further, when a color image is input, binarization processing may be performed after being separated into RGB color components, and the subsequent processing may be performed for each color component.

The junction point extraction unit 130 extracts an apparent junction point from the pixel column obtained by the tracking by the pixel column tracking unit 120. Here, the junction point is a pixel in which the tendency of the pixel row changes before and after that. For example, the joint point extraction unit 130 extracts, as clear joint points, corner points where the front and rear contour lines are bent by a predetermined angle or more based on the digital curvature. Specifically, paying attention to one point P ₀ of the pixel row constituting the outline, points P ₁ and P ₂ separated by K pixels are set before and after that, and the line segment P ₀ P ₁ and the line segment P are set. Calculate the cosine C of the angle formed by ₀ P ₂ . When the calculated cosine C is a predetermined value (for example, −0.6) or more, this point of interest is extracted as a corner point, that is, an apparent joint point. By performing this calculation for all the pixel columns constituting the contour line, all obvious junction points included in the pixel column are extracted.

  In the above description, when the cosine C is −0.6 or more, the point of interest is determined to be a corner point. However, the threshold value (−0.6) for this determination may be changed as appropriate. When the input image is composed of thin lines as shown in the circuit diagram, the input image itself corresponds to the contour line, and the branch is included in the pixel column constituting the contour line. You may make it extract.

  The segment dividing unit 140 divides the pixel sequence tracked by the pixel sequence tracking unit 120 into a plurality of segments using the junction points extracted by the junction point extraction unit 130. The straight line detection unit 150 detects a straight line part included in each segment divided by the segment division unit 140. Similarly, the arc detector 160 detects an arc portion included in each segment divided by the segment divider 140. Since the detection of these straight line portions and arc portions is performed individually for all segments, they may be performed in parallel or separately before and after. The image processing apparatus according to the present embodiment is characterized in that the longest straight line portion or arc portion is directly detected without being extended by post-processing.

  The functionalization processing unit 170 performs functionalization processing using the detection results obtained by the straight line detection unit 150 and the arc detection unit 160 for each segment divided into a plurality of segments by the segment division unit 140. Specifically, any one of the functions of free curve, arc, and straight line is applied to the contour shape, and the function is processed. However, even if the arc or straight line part is slightly distorted, it feels unnatural and reduces the amount of data. From this point of view, if functionalization processing using these is possible, it is necessary to perform functionalization processing using arcs or straight lines in preference to free curves. Further, since the arc can be expressed by a collection of short straight lines, it is preferable to give priority to the arc over the straight lines. Therefore, when the straight line portion detected by the straight line detection unit 150 is included in the circular arc portion detected by the circular arc detection unit 160, the common pixel is functionalized using the circular arc. Pixels included in other straight line portions are functionalized using a straight line, and pixels not included in an arc or a straight line are functionalized using a free curve (for example, a quadratic curve).

  The output image generation unit 180 generates an original image using the functionalized data obtained by the functionalization processing unit 170. In this original image generation, the magnification can be designated, and an image obtained by enlarging the original image at the designated magnification is generated.

  The above-described scanner 200 is an image input unit, a joint point extraction unit 130, a segment division unit 140 is a segment extraction unit, a joint point extraction unit 130 is a joint point extraction unit, and a segment division unit 140 is a segment division unit. The unit 150 and the circular arc detection unit 160 correspond to the function section detection unit, and the functionalization processing unit 170 corresponds to the functionalization processing unit.

  The image processing apparatus according to the present embodiment has such a configuration, and the operation thereof will be described next.

  FIG. 2 is a flowchart showing an overall operation procedure of the image processing apparatus according to the present embodiment. When an image read using the scanner 200 is input (step 100), the image storage unit 110 stores the input image data.

  Next, the pixel column tracking unit 120 performs tracking on the pixel columns that form the contour line of the input image (step 101). Further, the junction point extraction unit 130 extracts an apparent junction point included in the tracked pixel column (step 102). The segment dividing unit 140 divides the pixel row constituting the contour line into a plurality of segments by the extracted joint points (step 103).

  Next, the straight line detection unit 150 takes out one segment divided by the segment division unit 140 and detects a straight line part included in this segment (step 104). Depending on the segment, there may be a case where no straight line portion is included at all, or a case where a plurality of segments are included in a discrete manner. When the straight line detection processing for one segment is completed, the straight line detection unit 150 determines whether or not the straight line detection processing has been completed for all the segments constituting the contour line (step 105). If there is a segment for which the straight line portion detection process is not performed, a negative determination is made, and the straight line portion detection process in step 104 is repeated for other unprocessed segments.

  Further, when the straight line portion detection processing is completed for all the segments constituting the contour line, an affirmative determination is made in the determination of step 105, and then the arc portion is detected for each segment in the same procedure. That is, the arc detection unit 160 takes out one segment divided by the segment division unit 140 and detects an arc part included in this segment (step 106). Depending on the segment, there may be a case where no arc portion is included or a plurality of segments are included discretely. When the arc detection unit 160 completes the arc part detection process for one segment, the arc detection unit 160 determines whether or not the arc part detection process has been completed for all segments constituting the contour line (step 107). If there is a segment for which the arc portion detection processing has not been performed, a negative determination is made, and the arc portion detection processing in step 106 is repeated for other unprocessed segments.

  In the above description, the straight line portion detection operation is performed in steps 104 and 105, and then the arc portion detection operation is performed in steps 106 and 107. However, these two types of detection operations may be performed in parallel. Alternatively, the order may be reversed.

  In this way, after the detection of the straight line portion and the arc portion is completed for all the segments constituting the contour line, the functionalization processing unit 170 performs functionalization processing (function approximation processing) for each divided segment ( Step 108). For example, first, a functioning process for applying an arc to each arc part detected by the arc detecting unit 160 and then applying a straight line to the straight line part detected by the straight line detecting unit 150 is performed. (If part or all of the straight line part is included in the arc part, priority is given to the function approximation by the arc for the range.) Finally, for pixel rows that do not fall within the arc part or the straight line part The functionalization process using a free curve is performed. The result of the functionalization process in this way is stored in the image storage unit 110 (step 109). The output image generation unit 180 performs processing for enlarging and restoring the original image at a predetermined magnification using the result of the functionalization processing. The image restored in this way is displayed on the screen of the display device 220 or printed on recording paper from the printer 230 (step 110).

  Next, details of the straight line detection operation performed by the straight line detection unit 150 will be described. 3, 4, and 5 are flowcharts showing details of the straight line detection operation performed by the straight line detection unit 150.

  First, the straight line detection unit 150 reads one segment (step 200), sets the start point and end point of the read segment as the start point and end point of the comparison line (step 201), and sets the adjustment value L to the segment. The length is set (step 202). Here, the “comparison straight line” is a straight line on which an error calculation is performed by comparing with a segment (detection candidate) whose start point and end point match. The “adjustment value L” is the length of increase / decrease when the length of the segment to be processed is increased / decreased according to the comparison result between the comparison line and the segment. Is changed. The segment length is set to 1 regardless of the distance between adjacent pixels regardless of the arrangement state of these pixels (without distinguishing between the case where the pixels are arranged vertically and the case where they are arranged obliquely). This is indicated by the number of constituent pixels.

  Next, the straight line detection unit 150 calculates a mean square error e1 and a maximum square error e2 between the comparison straight line and the segment (steps 203 and 204). Here, the mean square error e1 is a value obtained by dividing a total value obtained by squaring the length of a perpendicular line drawn from each pixel constituting the segment into a comparison line by the number of pixels of the segment. The maximum square error e2 is a maximum value obtained by squaring the length of a perpendicular line drawn from each pixel constituting a segment to a comparison line. Note that the order of calculation of the mean square error e1 and the maximum square error e2 may be either first or may be performed in parallel.

  Next, the straight line detector 150 determines whether or not the mean square error e1 is less than the reference value E1 and the maximum square error e2 is less than the reference value E2 (step 205). For example, E1 = 0.2 and E2 = 1.0 are set based on experimental evaluation. When these two conditions are satisfied, an affirmative determination is made, and then the straight line detection unit 150 stores and stores the above-described comparison line segment as the straight line candidate D in the image storage unit 110 (step 206). It is determined whether the end point of the comparison line matches the initial value of the segment end point (step 207). The initial value of the end point of the segment is the end point of the segment read in step 200, and coincides with the junction point when the contour line is divided. In the present embodiment, when the segment shape substantially matches the comparison straight line and both the mean square error e1 and the maximum square error e2 are small, the same determination process is repeated after the end point of the segment is extended. If the end point of the comparison straight line is the same as the initial value of the end point of the segment, such an end point cannot be extended. In such a case, after an affirmative determination is made, the straight line detection unit 150 determines that the straight line detection unit 150 The candidate D is stored as the detection straight line S (step 214). Thereby, the detection operation of the straight line portion with respect to the entire one segment read in step 200 is completed.

  If the comparison straight line end point does not match the segment end point initial value, a negative determination is made in step 207. Next, the straight line detection unit 150 halves the adjustment value L (step 208), and then determines whether or not the changed adjustment value L is equal to or less than a predetermined value (step 209). As described above, in the present embodiment, when the segment shape substantially matches the comparison line, the end point of the segment is extended, but the extension length (adjustment value L) increases as the number of extension increases. Each is reduced by half (step 208). Therefore, an affirmative determination is made in step 209 when the adjustment value L converges to a small value. Next, the straight line detection unit 150 stores the straight line candidate D as the detected straight line S (step 211). The straight line detection unit 150 sets the start point of the segment as the end point of the detection line S and the end point of the segment as the initial value (step 212), and then the length of the segment whose start point and end point are changed is a predetermined value. It is determined whether or not the following is true (step 213). This is a determination operation so as not to detect the straight line portion for a segment that is too short. When the segment length becomes too short, an affirmative determination is made, and the one read in step 200 is determined. The detection operation of the straight line portion with respect to the entire segment ends. On the other hand, if the segment length is longer than the predetermined value, a negative determination is made in the determination in step 213, and the operation returns to step 202 to repeat the operation of detecting a straight line portion for a new segment.

  If the adjusted value L after the change is larger than the predetermined value, a negative determination is made in the determination in step 209. Next, the straight line detection unit 150 sets the end point of the segment by the adjustment value L to the initial value side of the end point. (Step 210), the process returns to step 203, and the operations after the calculation of the mean square error e1 and the maximum square error e2 are repeated.

  Further, when the condition that “the mean square error e1 is less than the reference value E1 and the maximum square error e2 is less than the reference value E2” is not satisfied, that is, the mean square error e1 is greater than or equal to the reference value E1, or the maximum If the square error e2 is greater than or equal to the reference value E2, a negative determination is made in step 205. Next, the straight line detection unit 150 determines whether or not the segment length is equal to or less than a predetermined value (step 215). This determination is performed in order to determine whether or not to continue the detection of the straight line portion by further shortening the segment length. If the segment length is shorter than the predetermined value, an affirmative determination is made, and the straight line detection unit 150 shifts the segment start point by the adjustment value L to the end point side (step 216) and sets the segment end point to the initial value. (Step 217). In this way, if the comparison straight line and the segment gradually become shorter than the predetermined value without detecting the straight line part included in the segment, the remaining segment on the end point side of the segment here is used. After the new segment start point and end point are reset in order to newly detect the straight line portion, the process returns to step 202 to repeat the straight line portion detection operation.

  If the segment length is greater than the predetermined value, a negative determination is made in the determination in step 215. Next, the straight line detection unit 150 halves the adjustment value L (step 218), shifts the end point of the segment by the adjustment value L to the start point side, shortens the segment (step 219), and then proceeds to step 203. The operations after the calculation of the mean square error e1 and the maximum square error e2 are repeated.

  6 and 7 are diagrams illustrating a specific example of detection of a straight line portion. First, the straight line detection unit 150 compares the entire segment SG (0) divided by the segment division unit 140 and a comparison straight line passing through the start point S (0) and the end point E (0) of the segment SG (0). And whether or not both the mean square error e1 and the maximum square error e2 satisfy a predetermined condition (FIG. 6A).

  Since the condition is not satisfied in this example, after setting a new end point E (1) of the segment SG (1) shifted to the start point S (0) side by the adjustment value L set to half of the segment length. (Steps 218 and 219), the shortened segment SG (1) is compared with a new comparison line passing through the start point S (0) and the end point E (1) of the segment SG (1), and the mean square error is compared. It is examined whether both e1 and the maximum square error e2 satisfy a predetermined condition (FIG. 6B).

  In this example, these two conditions are satisfied. Next, a new end point E (2) of the segment SG (2) shifted to the end point E (0) side by the adjustment value L that has been further changed to a half value is set. After setting (steps 208 and 210), this slightly longer segment SG (2) is compared with a new comparison line passing through the start point S (0) and end point E (2) of this segment SG (2). Then, it is checked whether or not both the mean square error e1 and the maximum square error e2 satisfy a predetermined condition (FIG. 6C).

  In this way, the end point position of the segment is sequentially changed, and finally the comparison line having the longest start point S (0) is detected as the detection line S. After one detection straight line S is determined, the remaining part other than the detection straight line S is set as a new segment as a detection target (step 212), and the detection operation of the straight line part is repeated again.

  Note that when the straight line portion is not included in the vicinity of the start point S (0) of one segment SG (0) divided by the segment dividing unit 140 (FIG. 7A), how short the segment length is. However, both the mean square error e1 and the maximum square error e2 do not satisfy the predetermined condition. In such a case, a new segment having the start point S (1) shifted to the end point E (0) side is set (steps 216 and 217), and the detection operation of the straight line portion is repeated again (FIG. 7B). )).

  The arc portion detection operation performed by the arc detection unit 160 is basically the same as the above-described straight line detection operation, and will be described below by focusing on the differences.

  8, 9 and 10 are flowcharts showing details of an arc portion detection operation by the arc detection unit 160. The flow charts shown in these figures change the comparison straight line included in the flow charts shown in FIGS. 3 to 5 to the comparison arc, the straight line candidate D to the arc candidate D, the detection straight line S to the detection arc S, and the number of steps. The operating procedure itself is basically the same.

  Further, the calculation method of the mean square error e1 and the maximum square error e2 is different between the straight line and the arc. Specifically, an arc passing through three points including the start point and end point of the segment and the intermediate point is set as a comparison arc, and the difference between the radius of this arc and the distance from the center of the arc to the pixels constituting the segment is set. The mean square error e1 and the maximum square error e2 are calculated using the square.

  In order to improve the detection accuracy of arc detection, the following devices (1) to (3) are devised.

  (1) The three points when setting a comparative arc are basically the start point, end point, and middle point of the segment. However, if the center angle of the arc is 4π / 3 or more, the start point and end point are too close, and the approximate circle Will increase. Therefore, when the center angle of the arc is 4π / 3 or more, the comparison arc is set by the start point, the point where the center angle from the start point is 4π / 3, and the intermediate point between them.

  (2) The reference values E1 and E2 are changed according to the center angle of the comparative arc. For the comparative arc having a large central angle, the reference values E1 and E2 are increased to make the judgment criteria sweet.

  (3) A threshold value is provided for the center angle so that a comparative arc having a too small center angle is not set. For example, a comparative arc whose center angle is smaller than π / 2 is not set.

  FIGS. 11, 12, 13 and 14 are diagrams showing experimental results obtained by performing straight line detection and circular arc detection on a specific figure, and results using both the method of the present embodiment and the conventional method. It is shown. In the experiment, the image shown in FIG. 11 was used.

  12A and 12B show a straight line portion and an arc portion detected by the method of the present embodiment, respectively. “X” included in these drawings indicates the start point or end point of the detected straight line or arc. In FIG. 12A, a portion surrounded by a dotted line is detected as a straight line, but as a result, a portion approximated by a function as an arc according to the priority order is shown. For comparison, FIGS. 13A and 13B show a straight line portion and a circular arc portion detected using the conventional multistage extraction method, respectively. FIGS. 14A and 14B show a straight line portion and a circular arc portion detected by using a conventional DP (Dynamic Programming) method, respectively.

  As apparent from comparison between FIGS. 12 to 14, by using the method of the present embodiment, it has succeeded in detecting a longer linear portion and arc portion than the conventional method. Further, it can be seen that the straight line portion and the circular arc portion detected by the method of the present embodiment include the straight line portion and the circular arc portion detected by the conventional method. This is an algorithm in which the conventional method gradually extends the straight line and the arc segment from the starting point, whereas the method of the present embodiment gradually cuts the straight line and the arc segment from the maximum length of the segment pixel row. It seems to be because it is an algorithm.

  As described above, since the segment corresponding to the approximate function is detected by gradually shortening the segment until the error is reduced with the entire segment as an initial state for each segment indicating the contour shape of the image, the segment corresponds to the approximate function. It is possible to detect a long section of a single shape corresponding to the approximate function, compared to the case where this section is gradually extended after detecting a short section.

  In addition, the pixel column is divided into a plurality of segments by extracting pixels corresponding to obvious corner points as junction points based on the arrangement of the pixel columns constituting the contour line of the image before and after. By extracting only the corner points as joint points, it is possible to prevent a long section of a single shape from being erroneously divided because the joint point setting position is inappropriate.

  In addition, by adopting a straight line or an arc as an approximation function for performing section detection, it becomes possible to detect a long straight line part or an arc part included in the contour shape of the image.

  In addition, it is possible to detect both a long straight line part and a long arc part included in the shape of an image by separately performing a section detection corresponding to a straight line and a section detection corresponding to an arc for each of a plurality of segments. It becomes possible, and an optimal functionalization process using each detection result can be performed. In particular, arcs, straight lines, and free curves are applied in the order of arcs, straight lines, and portions other than these arcs and straight lines detected by the function section detection means described above, giving priority to arcs and straight lines over free curves. By performing the digitization process, it is possible to further reduce the data amount by the functionalization process. In addition, when the detected arc and the straight line overlap, it is possible to perform the functioning process with high accuracy by performing the functioning process by giving priority to the arc.

  In addition, all or a part of each divided segment is set as a detection candidate segment, and the error is detected when the error between the detection candidate segment and the straight line connecting the start point and end point exceeds the reference value. If the segment as a candidate is shortened, and the error is below the reference value, the final segment is detected by lengthening the segment as a candidate for detection. It becomes possible to detect the straight line portion of the maximum length that is finally narrowed down and detectable.

  In addition, all or a part of each divided segment is set as a detection candidate segment, and an error between the detection candidate segment and its starting point, end point, and an arc passing through these intermediate points sets a reference value. If it exceeds, the segment as the detection candidate is shortened.On the other hand, when the error is below the reference value, the segment as the detection candidate is lengthened to detect the final arc portion, thereby gradually becoming the segment. It becomes possible to detect the arc portion of the maximum length that can be finally detected by narrowing the included arc portion.

  In addition, the detection of the straight line portion or the circular arc portion is performed by increasing or decreasing the segment length by L / 2, where L is the length of the segment as the detection candidate so far. In particular, it is possible to reduce the number of times of changing the segment length until the linear portion or the arc portion is detected, and the time required for detecting the linear portion or the arc portion can be shortened.

  Further, by evaluating the magnitude of the error based on the mean square error e1, it is possible to reduce the influence of noise generated in image reading or the like. In addition, the longer the straight line portion or arc portion to be detected, the smaller the mean square error e1 even if there is a local singular shape that does not match the shape of these approximate functions. It is ignored and functionalization is easy to be performed. However, since the maximum square error e2 is taken into account, the local singular shape is not ignored, and highly accurate functionalization processing can be performed.

  In addition, this invention is not limited to the said embodiment, A various deformation | transformation implementation is possible within the range of the summary of this invention. In the above-described embodiment, image input is performed using the scanner 200. However, input is performed by using another input device (for example, a digital camera) or by reading image data stored on a magneto-optical disk or the like. Also good.

  In the above-described embodiment, no particular countermeasure is taken for noise generated during image reading or the like, but more accurate functionalization processing may be performed by taking noise countermeasures. For example, in the process of functionalization, an appropriate approximation function is selected while evaluating the error, but the functionalization process using a free curve is applied to pixel columns corresponding to sections with sufficiently short segment lengths. Is often performed. In such a case, when the curvature is different from the approximate function of the adjacent segment, the free curve portion is often noise. For this reason, when such a phenomenon occurs, the state of occurrence may be displayed on the screen of the display device 220, and the operator may be inquired as to whether or not a pixel corresponding to noise can be deleted.

  In the above-described embodiment, when the detected straight line and the arc overlap, the arc is prioritized and the functionalization process is performed. Therefore, the arc detection in steps 106 and 107 shown in FIG. In addition, the straight line detection in steps 104 and 105 may be performed for a section excluding a portion detected as an arc.

It is a figure which shows the structure of the image processing apparatus of one Embodiment. 3 is a flowchart illustrating an overall operation procedure of the image processing apparatus according to the present exemplary embodiment. It is a flowchart which shows the detail of the detection operation of the straight line part by a straight line detection part. It is a flowchart which shows the detail of the detection operation of the straight line part by a straight line detection part. It is a flowchart which shows the detail of the detection operation of the straight line part by a straight line detection part. It is a figure which shows the specific example of a detection of a linear part. It is a figure which shows the specific example of a detection of a linear part. It is a flowchart which shows the detail of the detection operation | movement of the circular arc part by a circular arc detection part. It is a flowchart which shows the detail of the detection operation | movement of the circular arc part by a circular arc detection part. It is a flowchart which shows the detail of the detection operation | movement of the circular arc part by a circular arc detection part. It is a figure which shows the experimental result which performed the straight line detection and the circular arc detection with respect to the specific figure. It is a figure which shows the experimental result which performed the straight line detection and the circular arc detection with respect to the specific figure. It is a figure which shows the experimental result which performed the straight line detection and the circular arc detection with respect to the specific figure. It is a figure which shows the experimental result which performed the straight line detection and the circular arc detection with respect to the specific figure.

Explanation of symbols

DESCRIPTION OF SYMBOLS 100 Image processing calculating part 110 Image storage part 120 Pixel row tracking part 130 Joint point extraction part 140 Segment division part 150 Straight line detection part 160 Arc detection part 170 Functionalization processing part 180 Output image generation part 200 Scanner 210 Keyboard 212 Mouse 220 Display apparatus 230 Printer

Claims (27)

An image input means for inputting an image;
Segment extraction means for extracting a plurality of segments indicating the shape of the image input by the image input means;
For the segment extracted by the segment extractor, the segment start point and end point are set to the initial state, the segment length is decreased until the error falls below the reference value, and the sections corresponding to the arc and the straight line are detected. Function interval detecting means for performing,
The function section detecting means sets all or a part of the segment as a detection candidate, and when an error between the detection candidate and an arc or straight line passing through the start point and the end point exceeds the reference value, the detection is performed. When the candidate is shortened and, conversely, when the error is equal to or less than the reference value, the detection candidate finally determined by increasing the detection candidate is detected as a section corresponding to an arc or a straight line, The adjustment value L, which is the length of increase / decrease when increasing / decreasing the length of the detection candidate, is initially set to half the length of the segment, and the adjustment value L for the second and subsequent increases / decreases is set to 1/2 of the previous time. the image processing apparatus according to claim that you set. In claim 1,
The segment extraction means includes
A junction point extracting means for extracting a junction point included in a pixel column corresponding to the contour line of the image;
Segment dividing means for dividing the pixel row into the plurality of segments with the joint point extracted by the joint point extracting means as a boundary;
An image processing apparatus comprising: In claim 2,
The said junction point extraction means extracts the pixel corresponded to an obvious corner point as said junction point based on the arrangement | positioning before and behind the said pixel row | line | column. In any one of Claims 1-3,
The function section detecting means separately performs section detection corresponding to a straight line and section detection corresponding to an arc for each of the plurality of segments. In claim 4 ,
It further comprises functionalization processing means for performing functionalization processing by applying an arc, a straight line, and a free curve in the order of the arc, the straight line, and the portion other than the arc and the straight line detected by the function section detection means, An image processing apparatus. In claim 5 ,
The image processing apparatus according to claim 1, wherein the functionalization processing unit prioritizes the arc to perform the functionalization processing when a common pixel is included in the arc and the straight line detected by the function section detection unit.   In any one of Claims 1-6,
  The function section detecting means, when detecting a section corresponding to an arc, calculates an error between the detection section and an arc passing through the start point and end point of the detection candidate and other intermediate points. Processing equipment. In any one of Claims 1-7 ,
The function section detecting means calculates an average value e1 of a square of a distance between each pixel constituting the detection candidate and the approximate function to be detected as the error. In claim 8 ,
The function section detecting means calculates, as the error, the maximum value e2 of the square of the distance between each pixel constituting the detection candidate and the approximate function to be detected together with the average value e1. Processing equipment. A first step of inputting an image;
A second step of extracting a plurality of segments indicating the shape of the input image;
With respect to the extracted segment, the segment start point and the end point are set as initial states, the segment length is decreased until the error becomes equal to or less than the reference value, and a section corresponding to each of the arc and the straight line is detected. includes a step, the,
In the third step, all or a part of the segment is set as a detection candidate, and when an error between the detection candidate and an arc or straight line passing through the start point and the end point exceeds the reference value, the detection is performed. When the candidate is shortened and, conversely, when the error is equal to or less than the reference value, the detection candidate finally determined by increasing the detection candidate is detected as a section corresponding to an arc or a straight line, The adjustment value L, which is the length of increase / decrease when increasing / decreasing the length of the detection candidate, is initially set to half the length of the segment, and the adjustment value L for the second and subsequent increases / decreases is set to 1/2 of the previous time. an image processing method characterized that you set. In claim 10 ,
The second step includes
A fourth step of extracting a junction point included in a pixel row corresponding to the contour line of the image;
A fifth step of dividing the pixel column into the plurality of segments with the extracted joint point as a boundary;
An image processing method comprising: In claim 11 ,
In the image processing method according to the fourth step, pixels corresponding to apparent corner points are extracted as the junction points based on the arrangement of the pixel rows before and after. In any one of Claims 10-12 ,
In the third step, for each of the plurality of segments, section detection corresponding to a straight line and section detection corresponding to an arc are separately performed. In claim 13 ,
The method further includes a sixth step of performing functionalization processing by applying an arc, a straight line, and a free curve in the order of the arc, the straight line, and the arc and the straight line other than the straight line detected in the third step, respectively. Image processing method. In claim 14 ,
The sixth step is an image processing method characterized in that when a common pixel is included in the arc and the straight line detected in the third step, the arc is given priority and the functionalization process is performed. In any one of Claims 10-15,
The third step calculates an error between the detection section and an arc passing through the start point, end point, and other intermediate points of the detection candidate when detecting a section corresponding to the arc. Processing method. In any one of Claims 10-16 ,
In the third step, an average value e1 of a square of the distance between each pixel constituting the detection candidate and the approximate function to be detected is calculated as the error. In claim 17 ,
In the third step, the maximum value e2 of the square of the distance between each pixel constituting the detection candidate and the approximate function to be detected is calculated as the error together with the average value e1. Processing method. Computer
An image input means for inputting an image;
Segment extraction means for extracting a plurality of segments indicating the shape of the image input by the image input means;
For the segment extracted by the segment extractor, the segment start point and end point are set to the initial state, the segment length is decreased until the error falls below the reference value, and the sections corresponding to the arc and the straight line are detected. Function interval detecting means for
An image processing program for causing and,
The function section detecting means sets all or a part of the segment as a detection candidate, and when an error between the detection candidate and an arc or straight line passing through the start point and the end point exceeds the reference value, the detection is performed. When the candidate is shortened and, conversely, when the error is equal to or less than the reference value, the detection candidate finally determined by increasing the detection candidate is detected as a section corresponding to an arc or a straight line, The adjustment value L, which is the length of increase / decrease when increasing / decreasing the length of the detection candidate, is initially set to half the length of the segment, and the adjustment value L for the second and subsequent increases / decreases is set to 1/2 of the previous time. An image processing program to set. In claim 19 ,
The segment extraction means includes
A junction point extracting means for extracting a junction point included in a pixel column corresponding to the contour line of the image;
Segment dividing means for dividing the pixel row into the plurality of segments with the joint point extracted by the joint point extracting means as a boundary;
An image processing program comprising: In claim 20 ,
The image processing program characterized in that the junction point extraction means extracts pixels corresponding to obvious corner points as the junction points based on the front and rear arrangement of the pixel row. In any one of Claims 19-21 ,
The image processing program characterized in that the function section detecting means separately performs section detection corresponding to a straight line and section detection corresponding to an arc for each of the plurality of segments. In claim 22 ,
The computer further functions as functionalization processing means for performing functionalization processing by applying arcs, straight lines, and free curves in the order of arcs, straight lines, and portions other than these arcs and straight lines detected by the function section detection means. An image processing program for making In claim 23 ,
An image processing program characterized in that the functionalization processing means prioritizes a circular arc and performs functionalization processing when a common pixel is included in the arc and the straight line detected by the function section detection means.   In any one of Claims 19-24,
  The function section detecting means, when detecting a section corresponding to an arc, calculates an error between the detection section and an arc passing through the start point and end point of the detection candidate and other intermediate points. Processing program. In any one of Claims 19-25 ,
The function section detecting means calculates an average value e1 of the square of the distance between each pixel constituting the detection candidate and the approximate function to be detected as the error. In claim 26 ,
The function section detecting means calculates the maximum value e2 of the square of the distance between each pixel constituting the detection candidate and the approximate function to be detected as the error together with the average value e1. Processing program.

Images