JP2004030430A - Image processing method and image processing apparatus - Google Patents

Abstract

[PROBLEMS] It is difficult to perform rectangular cutout processing with high accuracy in an environment with much noise.
In an image obtained by binarizing an original image, a histogram of the number of black pixels in the horizontal and vertical directions is created, and the histogram is approximated by a trapezoid to indicate a range of a rectangular area in the binary image. Detect vertex coordinates. Then, by detecting the inclination direction of the rectangular area within the existence range, the rectangular area can be detected from the binary image with high accuracy.
[Selection diagram] FIG.

Description

[0001]
TECHNICAL FIELD OF THE INVENTION
The present invention relates to an image processing method and an image processing apparatus, and more particularly to an image processing method and an image processing apparatus for detecting a rectangular image.
[0002]
[Prior art]
Conventionally, various algorithms have been proposed for detecting and cutting out a rectangular area from an original image. For example, Japanese Patent Application Laid-Open No. 8-23737 describes a technique for extracting a contour and then searching for a rectangular area by searching for a portion where the contour forms a straight line.
[0003]
[Problems to be solved by the invention]
However, according to the conventional rectangle extraction algorithm, it is difficult to detect a straight line portion of a rectangular outline and detect a single rectangle by associating four straight lines in a noisy environment. . Therefore, it is difficult to perform accurate clipping, and the precision of the clipping result is not sufficient.
[0004]
SUMMARY An advantage of some aspects of the invention is to provide an image processing method and an image processing apparatus capable of detecting a rectangular area with high accuracy even in a noisy environment.
[0005]
[Means for Solving the Problems]
As one technique for achieving the above object, the image processing method of the present invention includes the following steps.
[0006]
That is, an image processing method for detecting a rectangular region from an image, wherein in a binarized image of an original image, a histogram creation step of creating a histogram of the number of black pixels in the horizontal and vertical directions, and a trapezoidal approximation of the histogram And a tilt direction detecting step of detecting a tilt direction of the rectangular area within the range of the rectangular area in the binary image. I do.
[0007]
The method further includes a labeling step of labeling the binary image, wherein the histogram creation step creates a histogram of the number of labeled pixels.
[0008]
BEST MODE FOR CARRYING OUT THE INVENTION
Hereinafter, an embodiment of the present invention will be described in detail with reference to the drawings.
[0009]
<First embodiment>
● System configuration
FIG. 1 is a block diagram showing a configuration of a computer system on which the present invention is executed. Reference numeral 101 denotes a CPU, which controls the entire system. A keyboard 102 is used together with a mouse 102a to input data to the system. A display device 103 includes a CRT, a liquid crystal, and the like. A ROM 104 and a RAM 105 constitute a storage device of the system and store programs executed by the system and data used by the system. 106 is a hard disk drive (HDD) and 107 is a floppy disk drive (FDD), which constitutes an external storage device used for the file system of the system. 108 is a printer.
[0010]
Reference numeral 109 denotes a network I / F, which is connected to a LAN or a WAN. Via the I / F 109, data files such as computer programs and digital images can be exchanged with other computer systems. The programs and data are recorded on the hard disk 106 or directly expanded on the RAM 105 and executed.
[0011]
Reference numeral 110 denotes an image scanner which can read a photograph or printed matter on a document table and take it into the RAM 105 as multi-valued digital image data.
[0012]
● Rectangular image overview
FIG. 2 shows an example of a binarized image captured from the image scanner 110. The rectangles in the figure indicate rectangular original images such as photographs (hereinafter, referred to as rectangular images), and the three ellipses indicate noise. Although the noise is simplified in FIG. 1 for the sake of explanation, the size and shape of the actual noise are undefined, and the number of noises is often several hundred to several thousand. In addition, the binarization of the image uses a well-known simple binarization method by comparison with a predetermined threshold value, and a detailed description is omitted here.
[0013]
The image shown in FIG. 2 is stored on the RAM 105 as a bitmap of W pixels wide and H pixels high. It is assumed that each pixel has a depth of 1 byte, and a black pixel is indicated by a value of 255 and a white pixel is indicated by a value of 0. The bitmap on the RAM 105 can be accessed as a two-dimensional array, and the i-th pixel in the horizontal direction and the j-th pixel in the vertical direction starting from the upper left of the bitmap are denoted as buf (i, j). In this embodiment, the coordinates of the region where the rectangular image exists are specified from the bitmap by the following method.
[0014]
● Histogram creation
FIG. 3 is a diagram showing a state of a histogram in which black pixels are counted in the horizontal direction when an ideal state in which no noise is present in the binary image shown in FIG. 2 is assumed. , The lower part shows an example of a histogram. According to the figure, it is understood that the histogram has a substantially trapezoidal shape corresponding to the four vertices of the rectangle of the binary image. Since the actual binary image contains noise, the histogram is not completely trapezoidal, but sufficient information for specifying the position of the vertex in the horizontal direction can be obtained from the trapezoidal shape of the histogram. it can.
[0015]
FIG. 4 is a flowchart showing the histogram creation processing shown in FIG. Hereinafter, an array for storing the histogram data is represented by hist ().
[0016]
First, in steps S401 and S402, a value 0 is substituted for each of the variables x, y, and in step S403, a value 0 is substituted for the variable hist (x).
[0017]
Then, in step S404, the pixel buf (x, y) on the bitmap is compared with the value 255, and if they are different, the process proceeds to step S406. If they are equal, the process proceeds to step S405 to increment hist (x) by one. Proceed to step S406.
[0018]
In step S406, the variable y is incremented by one, and then in step S407, y is compared with the height H of the bitmap. If y and H are different, the process returns to step S404, but if they are equal, the process proceeds to step S408, where the variable x is incremented by 1 and x is compared with the bitmap width W in step S409. If x and W are different, the process returns to step S402, but if they are equal, the process ends.
[0019]
● Vertex detection processing
Through the above processing, an array hist () of a histogram in which black pixels are counted is obtained. This histogram has a trapezoidal shape surrounded by the X axis and three straight lines as shown in FIG. In the present embodiment, in this trapezoid, a position where the left side intersects the X axis is a, a position where the left side intersects the upper base is b, a position where the right side intersects the upper base is c, and a position where the right side intersects the X axis is d.
[0020]
Here, a method of obtaining the positions a and b by analyzing the left side of the trapezoid represented by the histogram will be described with reference to the flowchart of FIG.
[0021]
First, in step S501, a peak point P at which hist (x) is maximized is detected. In the histogram shown in FIG. 3, there is a peak with a height of 800 at a position around X = 400. Next, in step S502, a point F that is half the height of the peak is detected in the forward direction of the point P. In the histogram shown in FIG. 3, positions around X = 100 correspond to the point F. In step S503, a point F0 having a height of 1/4 of the peak in the forward direction of the point F is detected. Further, in step S504, a point F1 having a height of 3/4 of the peak in the backward direction of the point F is detected. Is detected.
[0022]
Next, in step S505, a straight line L as shown in FIG. 3 is obtained by performing linear approximation for all points of F0 ≦ X ≦ F1 using a well-known regression analysis. In step S506, a point at which the straight line L intersects the X axis is calculated, and this point is obtained as a. In step S507, a point at which the straight line L is 98% of the height of the peak P is calculated, and this point is obtained as b. This is to correct the peak P to 98% in consideration of the fact that the peak P includes a noise component and thus appears more than the actual peak. The example in which the search for the peak P is performed in the forward direction to obtain the points a and b has been described with reference to the flowchart illustrated in FIG. 5, but the search for the points c and d is similarly performed by performing the search in the backward direction for the peak P. Can be obtained.
[0023]
Also, the above description is about the detection of the vertex position in the horizontal direction. However, it is possible to detect the vertex position in the vertical direction by applying the exactly same method by inverting the vertical axis and the horizontal axis in the above description. It is. As a result, as shown in FIG. 6, four coordinate values in the vertical and horizontal directions surrounding the rectangle, that is, eight variables (ax, bx, cx, dx, ay, by, cy, dy) can be obtained as vertex candidates. it can.
[0024]
Here, the above eight variables are uniquely determined from the rectangle, but conversely, the rectangle cannot be determined from the eight variables. That is, as shown in FIG. 7, as a rectangle based on eight variables, four kinds of vertex coordinates can be considered depending on the skew direction (hereinafter, skew mode), but it is not possible to determine which one of them is. . In FIG. 7, a special case (not shown) in which the rectangle is completely horizontal is mode 0, and the four skew modes are modes 1, 2, -1, and -2, respectively. Since a histogram having the same shape is generated from the images shown in these modes, it is necessary to determine the skew mode by a method other than the histogram.
[0025]
● Skew mode judgment
Hereinafter, the skew mode determination processing in the present embodiment will be described in detail.
[0026]
FIG. 6 described above corresponds to the state of mode 1 shown in FIG. 7. However, when the number of black pixels existing inside the two triangular areas shown by oblique lines in FIG. Since the halftone dot portion is not included, the counting result of the black pixels is considered to be zero. Hereinafter, the hatched area shown in FIG. 6 is referred to as a mode 1 template. Similarly, in the other modes shown in FIG. 7, two triangular regions existing above the rectangle are used as templates for each mode.
[0027]
Here, as shown in FIG. 8, when a template of mode 2 (hatched portion in the figure) is applied to a rectangular image (dotted portion in the diagram) which is actually mode 1, the rectangular portion protrudes inside the template. Therefore, the result of counting the number of black pixels does not become zero. In the present embodiment, the rectangular skew mode is determined using this characteristic.
[0028]
Specifically, the number of black pixels in the case where the template in the four modes is applied to the rectangular image to be determined is counted, and the template with the smallest counting result is determined as the skew mode of the image. . That is, it is assumed that the case where the degree of entry into the template is the smallest is the degree of skew that the rectangular image most closely approximates. Of course, it is also possible to count the black pixels existing outside the template, and determine the skew mode based on the template having the largest counting result.
[0029]
By the above processing, the coordinates of the four vertices of the rectangular area in the binary image can be specified. Therefore, based on this information, a well-known skew correction and image cutout processing are performed on the original image, so that a rectangular photographic image arranged on the image scanner 110 can be cut out, for example.
[0030]
It is desirable to use a simple interpolation method (nearest neighbor method) or a linear interpolation method (bilinear method) as the above-described known skew correction processing. The former is superior in speed, and the latter is superior in image quality. You can use them appropriately.
[0031]
As described above, according to the present embodiment, a rectangular area can be accurately detected even in an environment with much noise.
[0032]
If the rectangular area is a perfect rectangle, as an ideal histogram, the right and left hypotenuses should exhibit an ideal trapezoid. That is, the distance between a and b shown in FIG. 3 may not be equal to the distance between cd. In such a case, trapezoidal approximation is performed in accordance with data obtained from the hypotenuse that is considered to be less affected by noise. Specifically, for the right and left hypotenuses, the accuracy of the linear approximation (square error between the straight line and the actual data) by regression analysis is compared, and the one with the smaller error may be adopted.
[0033]
Similarly, a rectangle connecting four vertices obtained as a result of rectangle detection may not necessarily be a rectangle due to the influence of noise, and adjacent sides may not be orthogonal. Even in such a case, the accuracy of the rectangle detection can be improved by performing correction so that the rectangle becomes a rectangle based on the data considered to be less affected by noise.
[0034]
<Second embodiment>
Hereinafter, a second embodiment according to the present invention will be described. Note that the system configuration in the second embodiment is the same as in the above-described first embodiment, and a description thereof will not be repeated.
[0035]
In the first embodiment described above, the case where one rectangular area exists in the image has been described. As such a situation, for example, scanning is performed in a state where one photograph is not necessarily placed horizontally on the platen of the image scanner 110, and then skew correction and image cutout are automatically performed. A process of extracting an image is assumed.
[0036]
However, since the platen of a general flat head scanner can place a document of about A4 size, a plurality of general photographs (so-called L size) can be placed at a time. Accordingly, if such a plurality of photographic images can be read by one scan and only a rectangular region indicating the photographic image can be cut out from the obtained image, the scanning operation can be made more efficient.
[0037]
Therefore, the second embodiment is characterized in that a plurality of rectangular images are detected from one image.
[0038]
Hereinafter, a process of detecting a plurality of rectangular images in the second embodiment will be described with reference to FIG. The left part of FIG. 9 shows a binarized image when two photographs are arranged apart in the sub-scanning direction (longitudinal direction in the figure) of the document table, and the right part of FIG. 9 shows the binarized image. 7 shows a state of a histogram in the sub-scanning direction. As can be seen from the figure, when a plurality of photographs are arranged apart from each other, a plurality of trapezoids appear in the histogram. Therefore, in the second embodiment, by referring to this histogram, the image is divided into two between these trapezoids, that is, at the position indicated by the dashed line L in FIG. Then, a rectangular image can be detected in each of the divided areas by the method described in the first embodiment.
[0039]
Although FIG. 9 illustrates the case where a plurality of photographs are arranged apart in the sub-scanning direction, the same applies when the plurality of photographs are arranged apart in the main scanning direction (short direction in the drawing). By creating a histogram of, the image can be cut in the main scanning direction and each rectangular image can be extracted.
[0040]
As described above, according to the second embodiment, a plurality of rectangular images can be detected from one image.
[0041]
<Third embodiment>
Hereinafter, a third embodiment according to the present invention will be described. Note that the system configuration in the third embodiment is the same as in the above-described first embodiment, and a description thereof will not be repeated.
[0042]
The third embodiment is characterized in that the effect of noise is eliminated by performing an ideal labeling process on a binary image as shown in FIG. 2 and the rectangular image is detected with higher accuracy. .
[0043]
Here, the ideal labeling process in the binary image shown in FIG. 2 is based on the connection between black pixels, for example, by giving a pixel value of 1 to all the pixels included in the upper rectangular object, The pixel value 2 is given to all the pixels included in the object. That is, a label is not given to a minute noise portion, and the pixel value is kept at 255.
[0044]
● Overview of labeling process
Hereinafter, a labeling method for realizing the ideal labeling will be described in detail.
[0045]
FIG. 10 is a diagram for explaining a method of searching for a block corresponding to the upper left portion including the upper rectangular object in FIG. 2 and serving as a starting point of the filling process in the third embodiment.
[0046]
First, as shown in FIG. 10, the entire bitmap of W pixels × H pixels shown in FIG. 2 is divided into blocks of w pixels × h pixels, and the block (block) is occupied entirely by black pixels having a value of 255 ( Hereinafter, this is referred to as a “black block”) in the direction of the arrow in the figure. The block indicated by the black rectangle in FIG. 3 is the found black block.
[0047]
In the third embodiment, high-speed labeling is realized by filling an area where a found black block and a black pixel are connected. FIG. 11 shows and describes a flowchart of the entire labeling process in the third embodiment.
[0048]
First, in step S1401, a value 1 is substituted for a variable c, and in step S1402, a black block search is performed. The details of the black block search process will be described later.
[0049]
Next, in step S1403, it is determined whether a black block has been found. If found, the process proceeds to step S1404, but if not found, the process ends.
[0050]
In step S1404, the black pixel connection area is painted with the label c with the found black block as a starting point. The details of the painting process will be described later.
[0051]
In step S1405, the variable c is incremented by one, and the process returns to step S1402, and the above processing is repeated.
[0052]
As a result of this processing, labels 1, 2,..., C can be given only to objects having a size larger than a predetermined value.
[0053]
● Black block search processing
Hereinafter, the details of the black block search processing shown in step S1402 of FIG. 11 will be described with reference to the flowchart of FIG.
[0054]
First, in steps S1501 to S1504, variables y, x, j, and i are each initialized with a value of 0. In step S1505, it is determined whether or not buf (x + i, y + j) is 255 indicating a black pixel. If it is 255, the process proceeds to step S1506. If it is not 255, the process proceeds to step S1510.
[0055]
In step S1506, the variable i is incremented by the value 1, and in step S1507, if i is equal to w indicating the block width, the flow advances to step S1508; otherwise, the flow advances to step S1505.
[0056]
In step S1508, the variable j is incremented by the value 1, and in step S1509, if j is equal to h indicating the block height, the process ends. At this time, a w × h pixel block having (x, y) as the upper left starting point Detected as a black block. If j is different from h, the process returns to step S1504.
[0057]
In step S1510, w is added to x. If x is equal to or larger than W indicating the image width in step S1511, the process advances to step S1512; otherwise, the process returns to step S1503.
[0058]
In step S1512, h is added to y. If y is equal to or more than H indicating the image height in step S1513, the process ends, and at this time, it is determined that there is no black block. If y is less than H, the process returns to step S1502.
[0059]
By the above processing, a black block of w pixels × h pixels is detected from the binary image of W pixels × H pixels.
[0060]
● Filling process of connected area
Hereinafter, the details of the connection area filling processing shown in step S1404 of FIG. 11 will be described with reference to a flowchart of FIG.
[0061]
Note that various methods are known as the object filling process, and any of the filling methods may be used in the third embodiment. Therefore, the basic method will be described here, and it is assumed that the object has a simple shape that is outwardly convex for simplification of the description.
[0062]
As a result of the above-described black block search processing, a block starting from (x, y) at the upper left is detected as a black block as shown in FIG. Therefore, in the filling process according to the third embodiment, an area connected by black pixels is filled with a label c starting from ((x + w) / 2, (y + h) / 2) which is the center point of the black block. That is, the pixel value having the value 255 is replaced with the value c.
[0063]
Specifically, first, in step S601, for a scanning line including the center point ((x + w) / 2, (y + h) / 2) of the black block, the black connected portion on the scanning line is painted out with the label c. That is, a line segment connecting the left end (x0, y + h / 2) and the right end (x1, y + h / 2) of the scanning line in the object including the black block shown in FIG. 14 (the line segment cutting the object in the horizontal direction in FIG. 14) ) Is filled with the label c. The line connecting (x0, y + h / 2) and (x1, y + h / 2) is hereinafter referred to as a connected line, and the details of the painting process will be described later.
[0064]
Then, in step S602, the black connecting part below the connecting line is painted out, and in step S603, the black connecting part above the connecting line is painted out. The details of the painting process in steps S602 and S603 will be described later.
[0065]
As a result of this processing, the area connected by the black blocks and the black pixels can be filled with the label c.
[0066]
● Filling connection line
Hereinafter, the details of the connection line segment filling process shown in step S601 of FIG. 13 will be described with reference to the flowchart of FIG. For the sake of simplicity, it is assumed that the center point ((x + w) / 2, (y + h) / 2) of the black block, which is the starting point of the processing, is indicated by coordinates (X, Y). That is, X = (x + w) / 2 and Y = (y + h) / 2.
[0067]
First, X is substituted for a variable i in step S801, and i is decremented by 1 in step S802. Then, in step S803, it is determined whether or not buf (i, Y) is equal to the value 255. If the values are different, the process proceeds to step S804, but if they are equal, the process returns to step S802 to further decrement i.
[0068]
In step S804, the value i + 1 is stored in the variable x0, and in step S805, X is substituted for the variable i. Then, in step S806, i is incremented by the value 1, and in step S807, it is determined whether or not buf (i, Y) is equal to the value 255. If the values are equal, the process proceeds to step S808. Increment further.
[0069]
In step S808, the value i-1 is stored in the variable x1, in step S809, the value x0 is substituted for the variable i, and in step S810, c is substituted for buf (i, Y). Then, i is incremented by 1 in step S811, and if i is larger than x1 in step S812, the process ends. If not, the process returns to step S810.
[0070]
With this processing, the x-coordinates at both ends of the connected line segment can be stored in the variables x0 and x1, and the connected line segment can be painted out with the label c.
[0071]
● Bottom (upper) fill processing from connected lines
Hereinafter, the details of the filling process of the black connecting portion below the connecting line segment shown in step S602 of FIG. 13 will be described with reference to the flowchart of FIG. In this case, Y = y + h / 2, and therefore, the black connecting portion below the connecting line connecting (x0, Y) and (x1, Y) is painted out with the label c.
[0072]
First, the variable Y is incremented by 1 in step S901, and x0 is substituted for the variable i in step S902. Then, in step S903, it is determined whether or not buf (i, Y) is equal to the value 255. If they are different, the process proceeds to step S904, and if they are equal, the process proceeds to step S906.
[0073]
In step S904, i is incremented by the value 1, and in step S905, if i is greater than x1, the process ends. If not, the process returns to step S903.
[0074]
In step S906, i is substituted for X, and in step S907, a horizontal line, that is, a connected line segment on the scanning line is painted starting from (X, Y). Note that the painting process on the scanning line is shown in the flowchart of FIG. 15, and a detailed description thereof will be omitted here.
[0075]
Note that the filling process of the black connected portion above the connected line segment shown in step S603 of FIG. 13 is basically the same as the downward filling process shown in the flowchart of FIG. In the above, Y may be decremented instead of incremented, and similar processing may be performed for other steps.
[0076]
According to the labeling process described above, labeling can be performed only for an object including a black block of a predetermined size, that is, an object having an area equal to or larger than the predetermined size. Therefore, a label is not attached to a minute noise area, and high-speed labeling can be performed.
[0077]
● Rectangle detection after labeling
By the above labeling process, in the two-dimensional array of buf () shown in FIG. 2, the pixel value 1 as the label 1 is included in the lower rectangular object for all the pixels included in the upper rectangular object in FIG. The pixel value 2 as the label 2 is stored for all the pixels to be processed, the pixel value 255 is stored for the black pixels in the other minute noise portions, and the value 0 is stored for the white pixels on the background.
[0078]
In the third embodiment, the position (vertex coordinates) of a rectangular object is determined for each label area. That is, the image after labeling is subjected to the rectangle detection processing described in the first and second embodiments. Specifically, in the histogram creation flowchart shown in FIG. 4 described above, the comparison target of buf () shown in step S404 is changed from the value 255 indicating a black pixel to a label value (1 or 2 in this case). Good. As a result, the areas of label 1 and label 2 are detected as rectangles.
[0079]
Although the case where two rectangles are included has been described as an example, the above-described labeling process can be performed on a binary image including an arbitrary number of rectangles, and the rectangle detection process can be performed for each label. Needless to say, there is.
[0080]
As described above, according to the third embodiment, the effect of noise can be eliminated by performing ideal labeling processing on a binary image, and a rectangular image can be detected with higher accuracy.
[0081]
<Fourth embodiment>
Hereinafter, a fourth embodiment according to the present invention will be described. Note that the system configuration in the fourth embodiment is the same as in the above-described first embodiment, and a description thereof will not be repeated.
[0082]
In the above-described third embodiment, when searching for a black block from a binary image, first, the entire binary image is divided into blocks, and then it is checked whether or not each block is entirely black pixels. However, other methods are also applicable as a method of searching for a black block. For example, in the fourth embodiment, a method of continuously changing the upper left coordinates of a block in a binary image will be described. According to this method, although the calculation load increases, the detection performance of the black block can be improved.
[0083]
FIG. 17 is a diagram illustrating a manner of searching for a black block in a rectangular object in the fourth embodiment. According to the drawing, it can be seen that the starting point (x, y) of the search in the fourth embodiment is located outside the block boundary shown in FIG. 10 in the third embodiment.
[0084]
FIG. 18 shows a flowchart of a black block search process according to the fourth embodiment, which will be described in detail.
[0085]
First, in steps S1101 to S1104, variables y, x, j, and i are each initialized with a value of 0. In step S1105, it is determined whether or not buf (x + i, y + j) is 255 indicating a black pixel. If it is 255, the process proceeds to step S1106. If it is not 255, the process proceeds to step S1110.
[0086]
In step S1106, the variable i is incremented by the value 1. In step S1107, if i is equal to w indicating the block width, the flow advances to step S1108; otherwise, the flow advances to step S1105.
[0087]
In step S1108, the variable j is incremented by the value 1, and in step S1109, if j is equal to h indicating the block height, the process ends. At this time, a w × h pixel block having (x, y) as the upper left starting point is Detected as a black block. If j is different from h, the process returns to step S1104.
[0088]
In step S1110, i + 1 is added to x. Here, even if x is simply incremented by the value 1, exactly the same result is finally obtained. However, by adding i + 1, wasteful search can be omitted and the processing can be speeded up.
[0089]
If x is equal to or more than W indicating the image width in step S1111, the process proceeds to step S1112; otherwise, the process returns to step S1103.
[0090]
In step S1112, y is incremented by a value of 1. In step S1113, if y is equal to H indicating the image height, the process ends. At this time, it is determined that there is no black block. If y is not equal to H, the process returns to step S1102.
[0091]
By the above processing, a black block of w pixels × h pixels is detected from the binary image of W pixels × H pixels. Thereafter, similarly to the above-described third embodiment, the black pixel connection area can be filled and the rectangle detection processing can be performed.
[0092]
As described above, according to the fourth embodiment, a black block having a predetermined size can be detected with higher accuracy. Therefore, labeling of only valid objects can be performed with higher accuracy, and thus more accurate rectangle detection can be performed.
[0093]
According to the above-described third and fourth embodiments, the determination condition of the black block is that all the pixels in the block are black pixels. However, for example, depending on the state of noise, white pixels may be included in the black area. In some cases. Therefore, in the present invention, for example, the number of black pixels in a block may be counted, and if this count exceeds a predetermined threshold, it may be determined that the block is a black block.
[0094]
Further, the black block to be searched does not necessarily have to be rectangular, and may be, for example, a polygon such as a hexagon, a circle or an ellipse, or be selectable according to the assumed shape of the object. You may.
[0095]
The size of the search block is not limited to one predetermined size. For example, the search may be started from a large block size, and if no object is found, the size may be gradually reduced and the search may be repeated. As a result, it is possible to avoid a risk that an object smaller than expected is erroneously recognized as noise and ignored.
[0096]
[Other embodiments]
The present invention can be applied to a system including a plurality of devices (for example, a host computer, an interface device, a reader, a printer, etc.), but may be a device including one device (for example, a copying machine, a facsimile machine, etc.). May be applied.
[0097]
Further, an object of the present invention is to provide a storage medium storing a program code of software for realizing the functions of the above-described embodiments to a system or an apparatus, and a computer (or CPU or MPU) of the system or apparatus to store the storage medium. Needless to say, this can also be achieved by reading out and executing the program code stored in the.
[0098]
In this case, the program code itself read from the storage medium realizes the function of the above-described embodiment, and the storage medium storing the program code constitutes the present invention.
[0099]
As a storage medium for supplying the program code, for example, a floppy disk, a hard disk, an optical disk, a magneto-optical disk, a CD-ROM, a CD-R, a magnetic tape, a nonvolatile memory card, a ROM, and the like can be used.
[0100]
When the computer executes the readout program code, not only the functions of the above-described embodiments are realized, but also an OS (Operating System) running on the computer based on the instruction of the program code. It goes without saying that a case where a part of the actual processing is performed and the function of the above-described embodiment is realized by the processing is also included.
[0101]
Further, after the program code read from the storage medium is written into a memory provided on a function expansion board inserted into the computer or a function expansion unit connected to the computer, the function expansion is performed based on the instruction of the program code. It goes without saying that a CPU or the like provided in the board or the function expansion unit performs part or all of the actual processing, and the processing realizes the functions of the above-described embodiments.
[0102]
【The invention's effect】
As described above, according to the present invention, a rectangular area can be detected with high accuracy even in a noisy environment.
[Brief description of the drawings]
FIG. 1 is a block diagram illustrating a schematic configuration of an image processing system according to an embodiment of the present invention.
FIG. 2 is a diagram illustrating an example of a binary image to be detected in the present embodiment.
FIG. 3 is a diagram illustrating an example of a horizontal histogram of the number of black pixels in the embodiment.
FIG. 4 is a flowchart illustrating a histogram calculation process according to the embodiment.
FIG. 5 is a flowchart illustrating a trapezoidal approximation method of a histogram according to the present embodiment.
FIG. 6 is a diagram illustrating an example of detection coordinates of a rectangular image according to the present embodiment.
FIG. 7 is a diagram illustrating four skew modes in the embodiment.
FIG. 8 is a diagram for explaining the principle of skew mode determination in the embodiment.
FIG. 9 is a diagram illustrating a state of a histogram when a plurality of photographs are arranged in the second embodiment.
FIG. 10 is a diagram for explaining a black block search method according to a third embodiment.
FIG. 11 is a flowchart illustrating an outline of a labeling process in a third embodiment.
FIG. 12 is a flowchart illustrating a black block search process according to the third embodiment.
FIG. 13 is a flowchart illustrating a painting process according to the third embodiment.
FIG. 14 is a diagram illustrating a method for painting a connected line segment according to the third embodiment.
FIG. 15 is a flowchart illustrating a connection line segment filling process according to the third embodiment.
FIG. 16 is a flowchart illustrating a process of painting a region below a connected line segment according to the third embodiment.
FIG. 17 is a diagram for explaining a black block search method according to the fourth embodiment.
FIG. 18 is a flowchart illustrating a black block search process according to the fourth embodiment.
[Explanation of symbols]
101 CPU
102 keyboard
102a mouse
103 Display
104 ROM
105 RAM
106 Hard Disk
107 floppy disk
108 Printer
109 Network I / F
110 Image Scanner

Claims (29)

An image processing method for detecting a rectangular area from an image, comprising:
A histogram creation step of creating a histogram of the number of black pixels in the horizontal and vertical directions in an image obtained by binarizing the original image;
A rectangular range detecting step of detecting the existence range of a rectangular region in the binary image by approximating the histogram with a trapezoid;
An inclination direction detecting step of detecting an inclination direction of the rectangular area in the existence range;
An image processing method comprising: In the rectangular range detecting step,
Performing a trapezoidal approximation for each of the histograms in the horizontal and vertical directions of the binary image,
2. The image processing method according to claim 1, wherein an existence range of a rectangular area is detected in each of the horizontal and vertical directions of the binary image. 3. The image processing method according to claim 2, wherein in the rectangular range detection step, a plurality of vertex coordinate candidates for the rectangular area are detected. 4. The image processing method according to claim 3, wherein in the rectangular range detecting step, the vertex coordinates of the approximated trapezoid are detected as a plurality of vertex coordinate candidates for the rectangular area. 5. The image processing method according to claim 4, wherein in the tilt direction detecting step, coordinates of four vertices are specified from a plurality of vertex coordinate candidates of the rectangular area. In the tilt direction detecting step,
Based on a plurality of vertex coordinate candidates for the rectangular area, assuming a plurality of inclination directions of the rectangular area,
For a rectangular area indicated by each of the plurality of tilt directions, the number of black pixels existing outside the rectangular area is counted,
By specifying one inclination direction based on each counting result,
6. The image processing method according to claim 5, wherein coordinates of the four vertices are specified. In the tilt direction detecting step,
Based on a plurality of vertex coordinate candidates for the rectangular area, assuming a plurality of inclination directions of the rectangular area,
For a rectangular area indicated by each of the plurality of tilt directions, the number of black pixels existing inside the rectangular area is counted,
By specifying one inclination direction based on each counting result,
6. The image processing method according to claim 5, wherein coordinates of the four vertices are specified. 6. The image processing method according to claim 5, further comprising a skew correction step of performing skew correction on a rectangular area determined by the coordinates of the four vertices detected in the tilt direction detecting step. 9. The image processing method according to claim 8, wherein in the skew correction step, interpolation is performed by a bilinear method. 9. The image processing method according to claim 8, wherein in the skew correction step, interpolation is performed by a nearest neighbor method. The image processing method according to claim 1, wherein in the rectangular range detecting step, the histogram is approximated by a trapezoid, assuming that the rectangular area is rectangular. The image processing method according to claim 11, wherein the rectangular area is an area indicating a photographic image. 2. The image processing method according to claim 1, further comprising a binarization step of binarizing a multi-valued original image to obtain the binary image. 14. The image processing method according to claim 13, wherein the original image is an image in which one photographic image is arranged. When the original image is an image in which a plurality of photographic images are arranged at positions separated in the main scanning direction,
14. The image processing apparatus according to claim 13, wherein, in the histogram creating step, the binary image is divided for each of the photographic images in the main scanning direction, and the histogram is created for each of the divided binary images. Method. When the original image is an image in which a plurality of photographic images are arranged at positions separated in the sub-scanning direction,
14. The image processing apparatus according to claim 13, wherein, in the histogram creating step, the binary image is divided in the sub-scanning direction for each of the photographic images, and the histogram is created for each of the divided binary images. Method. A labeling step of labeling the binary image;
2. The image processing method according to claim 1, wherein in the histogram creating step, a histogram of the number of labeled pixels is created. The labeling step includes:
In the binary image, a black block detecting step of detecting, as a black block, a block of a predetermined size in which the number of black pixels inside the binary image is equal to or more than a predetermined ratio, and connecting the block within the detected black block and the black block. A labeling step of replacing black pixels with a predetermined label value,
18. The image processing method according to claim 17, comprising: 19. The image processing method according to claim 18, wherein, in the black block detection step, a block whose inside is entirely composed of black pixels is detected as the black block. The black block detection step includes:
A dividing step of dividing the entire binary image into blocks of the predetermined size;
A determining step of determining whether or not each block is a black block;
19. The image processing method according to claim 18, comprising: In the black block detection step,
19. The image processing method according to claim 18, wherein a black block is detected by sequentially shifting a position of the block of the predetermined size in the binary image. 19. The black block detecting step, wherein when a black book having the predetermined size is not detected in the binary image, a black block having a size smaller than the predetermined size is detected. Image processing method. The labeling step comprises:
A reference labeling step of replacing a reference line in the black block with the label value;
An upper labeling step of replacing black pixels connected above the reference line with the label value,
A lower labeling step of replacing black pixels connected below the reference line with the label value,
19. The image processing method according to claim 18, comprising: 19. The image processing method according to claim 18, wherein the black block is a rectangle. 19. The image processing method according to claim 18, wherein the black block is a polygon. 19. The image processing method according to claim 18, wherein the black block is circular. An image processing device for detecting a rectangular area from an image,
Histogram creation means for creating a histogram of the number of black pixels in the horizontal and vertical directions in an image obtained by binarizing the original image;
Rectangular range detection means for detecting the existence range of a rectangular region in the binary image by approximating the histogram with a trapezoid;
An inclination direction detecting means for detecting an inclination direction of the rectangular area within the existence range,
An image processing apparatus comprising: An image processing program for detecting a rectangular area from an image,
In a binarized image of the original image, a code of a histogram creating step of creating a histogram of the number of black pixels in the horizontal and vertical directions,
A code for a rectangular range detecting step of detecting the existence range of the rectangular region in the binary image by trapezoidal approximation of the histogram;
In the existence range, code of a tilt direction detecting step of detecting a tilt direction of the rectangular area,
A computer-readable program, comprising: A recording medium on which the program according to claim 28 is recorded.

Images