Image processing apparatus for correcting distortion of image and image shooting apparatus for correcting distortion of shot image

The present invention relates to an image processing apparatus and an image shooting apparatus which easily correct distortion of an image, such as trapezoidal distortion.

With advancement of digital cameras and cost reduction of storage type memories, studies have been made on applications in which digital cameras are not only used to shoot scenes and persons, but also shoot documents, such as papers and name cards, or what is written on a blackboard or so in a meeting, and digitally save those images in a personal computer or so for management.

In shooting a sheet using such a digital camera, the quadrangle of the sheet is deformed into a trapezoid. There is an image shooting system which corrects such trapezoidal distortion or keystone distortion. When a macrolens, a wide-angle lens or the like is used, the shape of a sheet is distorted into a barrel shape as shown in Fig. 13 due to the characteristics of those lenses. To acquire a high-quality image, such distortion should be corrected.

Various distortion correction methods are available to correct distortion originated from the lens characteristic. For example, because the distortion is generally distortion that is determined at the time of designing the lens, one possible method is to acquire points of an image having distortion which correspond to pixel coordinates of an ideal distortion-free image beforehand from the relationship between the pixel coordinates of the ideal distortion-free image and the pixel coordinates of the image having distortion, and acquire pixel data through interpolation or the like from the values of surrounding pixels.

This method however should perform pixel interpolation or so both in image extraction and projection correction and thus requires an interpolation operation twice. This increases degradation of an acquired image. When distortion is originated from the lens characteristic, correction should be carried out for each pixel, increasing the number of operations for correction, so that the overall processing takes time.

The present invention has been made to overcome the conventional problems, and aims at providing an image processing apparatus (25) which corrects distortion of an image, and comprises a shot-image acquisition section (32; S13 to S15) which acquires a shot image of a subject to be shot, including a shooting target image which is an image portion corresponding to the subject to be shot; a reduced-image acquisition section (33; S19, S31) which acquires a reduced image that is the shot image with a reduced resolution; a distortion information acquisition section (34; S19, S31 to S35) which acquires distortion information indicative of distortion of the shooting target image based on the reduced image; a projection parameter acquisition section (35; S21) which acquires a projection parameter for converting the shooting target image to an ideal distortion-free image based on the distortion information; and a projection transformation section (36; S51 to S59) which produces a projection-transformed image by performing projection transformation on the shot image using the projection parameter.

The invention can easily correct distortion of an image, such as trapezoidal distortion. As an image shooting apparatus equipped with an image shooting capability can acquire a shooting target image free of distortion, such as linear distortion originated from a shooting angle or distortion originated from the lens characteristic, by performing the processing on a shot image acquired by shooting a subject to be shot. <ul id="ul0001" list-style="none" compact="compact"><li>FIG. 1 is an explanatory diagram showing the structure of a digital camera according to one embodiment of the invention;</li><li>FIGS. 2A and 2B are diagrams for explaining the functions of the digital camera shown in FIG. 1, FIG. 2A showing a distorted shot image while FIG. 2B shows an ideal image after correction as if it were taken from the front;</li><li>FIG. 3 is a block diagram showing the structure of the digital camera shown in FIG. 1;</li><li>FIG. 4 is a flowchart illustrating a shooting process which is executed by the digital camera shown in FIG. 1;</li><li>FIGS. 5A to 5C are explanatory diagrams of a contour acquisition process of acquiring the contour of a subject to be shot which is executed by an image processing apparatus shown in FIG. 2, FIG. 5A showing the image of an original deformed like a barrel by the distortion of an image-taking lens section, while FIG. 5B shows a reduced image undergone distortion correction and FIG. 5C shows an edge binary image;</li><li>FIG. 6A and 6B are explanatory diagrams of Hough transformation;</li><li>FIGS. 7A to 7D are explanatory diagrams of Hough transformation for a deformed line, FIG. 7A showing Hough transformation for a distorted line while FIGS. 7B to 7D respectively show projection histograms to s1, s2 and s3 axes shown in FIG. 7A;</li><li>FIG. 8A and 8B are explanatory diagrams of a scheme of reducing an inspection angle in Hough transformation;</li><li>FIG. 9 is a flowchart illustrating the contents of a process of acquiring the contour of a subject to be shot which is executed by the image processing apparatus shown in FIG. 3;</li><li>FIG. 10 is a flowchart illustrating the contents of a quadrangle candidate selecting process which is executed by the image processing apparatus shown in FIG. 3;</li><li>FIG. 11 is an explanatory diagram of affine transformation;</li><li>FIG. 12 is a flowchart illustrating the contents of a projection transformation process based on affine transformation, which is executed by the image processing apparatus shown in FIG. 3; and</li><li>FIG. 13 is an explanatory diagram showing a distorted image.</li></ul>

An image shooting apparatus according to one embodiment of the invention will be described below with reference to the accompanying drawings.

In the following description of the embodiment, an image shooting apparatus will be described as a digital camera.

FIG. 1 shows the structure of a digital camera 1 according to the embodiment.

The digital camera 1 according to the embodiment shoots the contents described on the sheet of an original 2, corrects trapezoidal distortion or keystone distortion of the image of a subject to be shot (hereinafter referred to as "shooting target") or the image of the including the original 2, and generates an ideal image as shown in FIG. 2B, as if taken from the front, from a shot image as shown in FIG. 2A acquired by image shooting. The digital camera 1 has an image shooting lens section 11, a liquid crystal monitor 12 and a shutter button 13.

The image shooting lens section 11 has a lens or so for condensing light, and condenses light from the original 2 or so.

The liquid crystal monitor 12 displays an image taken inside via the image shooting lens section 11. The shutter button 13 is depressed when shooting the original 2. The digital camera 1 has a power switch, a mode switch an image adjustment key (not shown), and so forth in addition to the shutter button 13.

The power switch is used to power the digital camera 1 on or off. The mode switch is for setting an image shooting mode for shooting a subject, and a playback mode for reproducing shot images. The image adjusting key is operated when performing image processing.

As shown in FIG. 3, the digital camera 1 further includes an optical lens unit 21, an image sensor 22, a memory 23, a display unit 24, an image processing apparatus 25, an operation unit 26, a computer interface unit 27, an external memory IO unit 28, and a program code memory unit 29.

The optical lens unit 21 has the image shooting lens section 11 and a drive unit for the image shooting lens section 11, and forms an image by condensing light from the original 2 on the image sensor 22.

The image sensor 22 acquires the formed image as digital image data, and is comprised of a CCD or so. The image sensor 22 is controlled by a CPU 30. When the shutter button 13 is not depressed, the image sensor 22 generates digital image data with a low resolution for preview and sends the image data to the memory 23 regularly at intervals of 30 seconds or so. When the shutter button 13 is depressed, the image sensor 22 generates digital image data with a high resolution and sends the image data to the memory 23.

The memory 23 temporarily stores a low-resolution preview image, high-resolution image data or data of an original image to be undergone in the image processing apparatus 25 or image data after image processing. The memory 23 sends image data temporarily stored to the display unit 24 or the image processing apparatus 25.

The display unit 24 has the liquid crystal monitor 12 and displays an image on the liquid crystal monitor 12. The display unit 24 displays a low-resolution preview image or a high-resolution image, temporarily stored in the memory 23, on the liquid crystal monitor 12.

The image processing apparatus 25 performs image processing, such as compression of image data, correction of image distortion like keystone distortion, and image conversion, on image data temporarily stored in the memory 23.

The image processing apparatus 25 performs image processing on an image having keystone distortion as shown in FIG. 2A to generate an image which looks as if it were taken from the front as shown in FIG. 2B.

To correct keystone distortion of the image of the original, the image processing apparatus 25 extracts a quadrangle forming the contour of the image of the original from the distorted image of the original, and performs projection transformation of the image of the original. Performing such image processing, the image processing apparatus 25 acquires an assumed front image of the original 2.

More specifically, the image processing apparatus 25 mainly performs the following processes under the control of the CPU 30.

(1) Acquisition of the contour from a shot image

This process is to acquire the contour of the image of the original corresponding to the contour of the sheet of the original from a shot image acquired by shooting.

When the original is shot in a close range using a macrolens or a wide-angle lens in the optical lens unit 21, the image of the original is distorted like a barrel due to distortion of the image-taking lens section 11. The image processing apparatus 25 acquires the accurate contour of the image of the original by performing distortion correction even if the image has such distortion. The details of the process of acquiring the contour from a shot image will be discussed later.

(2) Image conversion (extraction, projection correction)

This image conversion process includes image extraction and projection correction. The image extraction extracts the contour (quadrangle) of the image of the original as a shooting target from a shot image.

The projection correction process performs projection transformation of the extracted image of the original using affine transformation to correct keystone distortion of the image of the original. The affine transformation is wide adapted in spatial conversion of an image. At the time of executing projection correction, the image processing apparatus 25 acquires corresponding points of the image of the original having distortion by correction corresponding to distortion correction.

(3) Image clearing

The image clearing process acquires an image with an excellent visibility by increasing the luminance, color correction, etc. on an image undergone image conversion.

To perform the image clearing process, the image processing apparatus 25 extracts image effect correcting parameters from an image undergone image conversion. The image effect correcting parameters are variables necessary in an image effect process, such as the maximum value, the minimum value or the peak value of the luminance histogram, and the peak value or the average value of a chromatic histogram. The image processing apparatus 25 performs the image clearing correcting process by converting the extracted image effect correcting parameters to values which make the image clear.

(4) Image compression

The image compression process compresses image data undergone the image clearing process.

The operation unit 26 acquires operation information of a user, such as the ON/OFF action of the power switch, and depression of the shutter button 13. The operation unit 26 sends the acquired operation information to the CPU 30.

The computer interface unit 27 operates as a USB storage class driver when the digital camera 1 is connected to a computer (not shown). Accordingly, when connected to the digital camera 1, the computer uses a memory card 31 as an external memory device for the computer.

The external memory IO unit 28 inputs and outputs image data or so to and from the memory card 31. The memory card 31 stores image data or so supplied from the external memory IO unit 28.

The program code memory unit 29 stores a program which is run by the CPU 30, and is comprised of a ROM or the like.

The CPU 30 controls the entire system according to the program stored in the program code memory unit 29. The memory 23 is also used as a work memory for the CPU 30.

When operation information is sent to the CPU 30 from the operation unit 26 as a result of depressing any of the switches and keys, the CPU 30 controls the image sensor 22, the memory 23, the display unit 24, the image processing apparatus 25 and so forth based on the operation information.

Specifically, when the mode switch is set to the shooting mode based on operation information from the operation unit 26 and the shutter button 13 is depressed halfway, the CPU 30 sets the individual sections of the image sensor 22, the memory 23, the display unit 24, the image processing apparatus 25, etc. to the shooting mode. Under the state, the CPU 30 sets the image sensor 22 to a preview mode, and when the shutter button 13 is further depressed, the CPU 30 sets the image sensor 22 to a high-resolution mode to read the high-resolution image of the shooting target. When the mode is set to the playback mode by the mode switch, the CPU 30 sets the individual sections to the playback mode.

When operation information indicating depression of the image adjusting key is sent from the operation unit 26, the CPU 30 controls the image processing apparatus 25 and other necessary sections in such a way as to adjust an image.

The CPU 30 writes data of a preview image and a high-resolution image in the memory card 31 and reads written image data from the memory card 31 via the external memory IO unit 28. The CPU 30 writes image data compressed in, for example, the JPEG format in the memory card 31.

At the time of temporarily storing image data in the memory 23, the CPU 30 writes data of a preview image and a high-resolution image in different memory areas. The CPU 30 writes image data in associated image files in the memory card 31. When writing image data into the memory card 31, the CPU 30 writes header information about the image data in a header information memory area in the associated image file.

The operation of the digital camera 1 according to the embodiment will be described next.

When a user powers on the digital camera 1, the CPU 30 acquires data of the program stored in the program code memory unit 29. When the user sets the mode to the shooting mode using the mode switch and depresses the shutter button 13, the operation unit 26 sends its operation information to the CPU 30. The CPU 30 receives the operation information, and the CPU 30, the image processing apparatus 25, etc. execute the shooting process according to a flowchart illustrated in FIG. 4.

The CPU 30 sets the image sensor 22 to the preview mode (step S11).

Based on the operation information sent from the the operation unit 26, the CPU 30 determines whether the shutter button 13 is depressed or not (step S12).

When it is determined that the shutter button 13 is depressed (YES at step S12), the CPU 30 changes the preview mode to the high-resolution mode and controls the image sensor 22 accordingly (step S13).

The CPU 30 writes data of the high-resolution image of a shooting target generated by the image sensor 22 in a memory area in the memory 23 different from a memory area where the preview image is written (step S14).

The CPU 30 determines whether reading of image data has been completed or not (step S15).

When it is determined that reading has not been completed (NO at step S15), the CPU 30 controls the image sensor 22 to continue reading image data.

When it is determined that every image data has been read and image transfer has been finished (YES at step S15), the CPU 30 generates a low-resolution preview image from the picked-up image (high-resolution image) and writes data of the preview image in the preview-image memory area in the memory 23 (step S16).

The CPU 30 controls the image processing apparatus 25 to generate compressed data of the shot image. (step S17).

The CPU 30 saves the compressed data in the memory card 31 via the external memory IO unit 28 (step S18).

Next, under the control of the CPU 30, the operation unit 26 acquires the contour of the image of the original which is the shooting target from the shot image according to a flowchart illustrated in FIG. 4 to be discussed later (step S19).

The CPU 30 determines whether the image processing apparatus 25 could acquire the contour of the shooting target or not (step S20).

When the CPU 30 has decided that acquisition has been done (YES at step S20), the image processing apparatus 25 creates a projection transformation image based on the acquired projection parameters (step S21).

When the image adjusting key of the operation unit 26 is depressed, the operation unit 26 sends their operation information to the CPU 30. The CPU 30 sends the operation information from the operation unit 26 to the image processing apparatus 25, which in turn performs adjustment of image transformation according to the sent operation information (step S22).

The image processing apparatus 25 extracts image effect correction parameters for the image clearing process (step S23), and executes the image clearing process (step S24).

The image processing apparatus 25 performs compression on image data which has undergone the image clearing process, thereby generating compressed data of the converted image (step S25).

The image processing apparatus 25 writes the generated compressed data of the converted image in the memory card 31 (step S26).

When it is determined that extraction of the contour of the shooting target has not been done (NO at step S20), on the other hand, the CPU 30 performs a warning process (step S27).

The CPU 30, etc. terminate the shooting process in the above manner. The CPU 30, etc. repetitively execute the shooting process unless the user operates some key to terminate the shooting process.

Next, the shooting process which is executed by the image processing apparatus 25 will be described.

(1) Acquisition of the contour from a shot image (process at step S19 in FIG. 4)

To acquire the contour of a shooting target from a shot image, the image processing apparatus 25 first generates a reduced image from the shot image acquired by shooting the shooting target, and acquires an edge binary image from the generated reduced image. The reason why the contour of the shooting target is acquired using a reduced image of the image of the shooting target, not the image of the shooting target itself, is because the precision of acquiring the contour need not be so high, so that the burden on the process can be made lighter by using a reduced image.

As shown in FIG. 5A, a shot image generally becomes an image distorted according to the lens characteristic of the image-taking lens section 11. To improve the precision of detecting extraction of the contour, the image processing apparatus 25 reduces a shot image while correcting distortion of an input image a distorted shot image as shown in FIG. 5A, thereby acquiring a distortion-corrected reduced image as shown in FIG. 5B.

Then, the image processing apparatus 25 acquires an edge binary image indicating the contour of the shot image as shown in FIG. 5C from the reduced image as shown in FIG. 5B. At the time of acquiring a reduced image, the image processing apparatus 25 also performs distortion correction of the input image this way. The following will describe the idea of acquiring a reduced image while performing distortion correction.

Let P(x, y) be an input image input to the image sensor 22 via the image-taking lens section 11 and xmax and ymax be its x-directional and y-direction image sizes, and suppose that a reduced image Q(m, n) which is 1/K of the input image is produced.

With (x', y') being a coordinate system free of distortion corresponding to the input image P(x, y), the relationship between the coordinate system (x', y') and the reduced image Q(m, n) is given by the following equation 1.<maths id="math0001" num="(1)"><math display="block"><mrow><mtext>x' = m x K</mtext><mspace linebreak="newline" /><mtext>y' = n x K</mtext></mrow></math><img file="EP1577832A2_D0001.tif" /></maths> where <ul id="ul0002" list-style="none" compact="compact"><li>x': the x coordinate of the coordinate system free of distortion corresponding to the coordinates Q (x, y) of the reduced image, and</li><li>y': the y coordinate of the coordinate system free of distortion corresponding to the coordinates Q(x, y) of the reduced image.</li></ul>

It is assumed that in the embodiment the input image P(x, y) and the coordinate system (x', y') are given by the following equation 2.<maths id="math0002"><math display="block"><mrow><mtext>(</mtext><mtext mathvariant="italic">x,y</mtext><mtext>) = </mtext><mfrac><mrow><mtext>1- </mtext><mtext mathvariant="italic">k</mtext><mtext>(</mtext><mtext mathvariant="italic">r</mtext><mtext> / </mtext><mtext mathvariant="italic">R</mtext><mtext>)</mtext></mrow><mrow><mtext>1-</mtext><mtext mathvariant="italic">k</mtext></mrow></mfrac><mtext>(</mtext><mtext mathvariant="italic">x</mtext><mtext>',</mtext><mtext mathvariant="italic">y</mtext><mtext>')</mtext></mrow></math><img file="EP1577832A2_D0002.tif" /></maths><maths id="math0003" num="(2)"><math display="block"><mrow><msub><mrow><mtext>R = x</mtext></mrow><mrow><mtext>c</mtext></mrow></msub><msup><mrow><mtext>​</mtext></mrow><mrow><mtext>2</mtext></mrow></msup><msub><mrow><mtext>+ Y</mtext></mrow><mrow><mtext>c</mtext></mrow></msub><msup><mrow><mtext>​</mtext></mrow><mrow><mtext>2</mtext></mrow></msup><mspace linebreak="newline" /><msub><mrow><mtext>r = (x' - x</mtext></mrow><mrow><mtext>c</mtext></mrow></msub><msup><mrow><mtext>)</mtext></mrow><mrow><mtext>2</mtext></mrow></msup><msub><mrow><mtext> + (y' - y</mtext></mrow><mrow><mtext>c</mtext></mrow></msub><msup><mrow><mtext>)</mtext></mrow><mrow><mtext>2</mtext></mrow></msup></mrow></math><img file="EP1577832A2_D0003.tif" /></maths> where <ul id="ul0003" list-style="none" compact="compact"><li>x_c: x coordinate of the center of the image,</li><li>y_c: y coordinate of the center of the image, and</li><li>k: distortion coefficient which is determined by the lens.</li></ul>

Substituting m = 0 to xmax/K and n = 0 to ymax/K into the equations 1 and 2 in order, a reduced image q is acquired. The number of operations for the reduced image becomes 1/(K^2) with respect to the original image.

To acquire an edge binary image as shown in FIG. 5C, a filter for edge detection called a Roberts filter, for example, should be used on the distortion-corrected reduced image as shown in FIG. 5B. The Roberts filter acquires two filters Δ1 and Δ2 by weighing two 4-neighbor pixels and averaging them to thereby detect the edge of an image. The conversion using the Roberts filter is expressed by the following equation 3.<maths id="math0004"><img file="EP1577832A2_D0004.tif" /></maths> where <ul id="ul0004" list-style="none" compact="compact"><li>Pe(x, y): pixel value of coordinates (x, y) (after conversion)</li><li>f(x, y): pixel value of coordinates (x, y) (before conversion)</li></ul>

The image converted by the equation 3 is digitized according to the following equation 4.<maths id="math0005" num="(4)"><math display="block"><mrow><mtext>BW(x, y) = 1 (Pe(x, y) ≥ V_thresh)</mtext><mspace linebreak="newline" /><mtext>BW(x, y) = 0 (Pe(x, y) &lt; V_thresh)</mtext></mrow></math><img file="EP1577832A2_D0005.tif" /></maths> where <ul id="ul0005" list-style="none" compact="compact"><li>BW(x, y): edge binary image</li><li>V_thresh: preset threshold</li></ul>

The threshol V_thresh is a preset value which is memorized by the image processing apparatus 25.

To acquire the contour of the shooting target from a shot image, lines which form the contour of the shot image are acquired from the acquired edge binary image. The image processing apparatus 25 acquires the lines using Hough transformation.

The Hough transformation is a scheme of projecting image data of (X, Y) coordinates indicating a line L as shown in FIG. 6A onto a projection plane passing the center of the image and having an inclination θ to generate a projection histogram on the ρ axis of the projection plane. In other words, the Hough transformation projects points constituting a line on the X-Y plane as shown in FIG. 6A onto the ρ-θ plane as shown in FIG. 6B expressed by the following equation 5 to convert the points to the number of votes on the ρ-θ coordinate system.<maths id="math0006" num="(5)"><math display="block"><mrow><mtext>ρ = xcosθ + ysinθ</mtext></mrow></math><img file="EP1577832A2_D0006.tif" /></maths>

When the line L is deformed as shown in FIG. 7A, with votes given on the s1 axis, the s2 axis and the s3 axis, the projection histogram shows a distribution as shown in FIGS. 7B to 7D. Note that the s1 axis and the s3 axis are axes which are inclined respectively by angles +δ and -δ about the origin of the (X, Y) coordinate system with an angle θ1 of the s2 axis taken as a reference.

As shown in FIGS. 7B to 7D, while the number of votes on the s2 axis should have a peak by the original line L, the peak value on the s2 axis becomes lower than the peak values on the s1 axis and the s3 axis. The image processing apparatus 25 may detect a peak θ + δ or θ - δ and select a quadrangle candidate showing the wrong contour of the image of the original. According to the embodiment, distortion correction is executed at the time of generating a reduced image as mentioned above, distortion as shown in FIG. 7A does not occur and such a wrong contour of the original will not be extracted.

The contents of the quadrangle candidate selecting process for the image of an original will be discussed below.

To select a quadrangle candidate for the image of an original, lines are acquired based on the peak values detected through the Hough transformation and are then combined to produce a quadrangle candidate.

When the angle θ at the coordinates (x, y) of each point is changed from 0 to 360 degrees through the Hough transformation, the same line is expressed by one point on the ρ-θ plane. It is therefore possible to determine that the ρ-θ coordinates which have a large number of votes can be considered as a line. At this time, the number of votes becomes the number of pixels on the line and can thus be considered as the length of the line and can be eliminated from candidates for the line.

At the time of performing Hough transformation, the processing speed can be improved by reducing the number of points of an inspection target and the number of angles θ. According to the scheme using Hough transformation, the greater the number of points of an inspection target and the number of angles θ become, the slower the processing speed becomes. To avoid the drop of the processing speed, an edge image is reduced at the time of edge detection by thinning data on the coordinates of the points of the inspection target in both the X- and Y-axial directions at given intervals. This can reduce the number of points of the inspection target.

The number of inspection angles can be reduced further by the following method.

Let us consider the coordinate system where the center of an edge image which is an inspection target is the origin. As ρ takes a negative value, if the angle θ is measured within the range of 0° ≤ θ &lt; 180°, ρ becomes negative within the remaining range of 180° ≤ θ &lt; 0°.

When the center of the shooting target is positioned near the center of the image, however, the individual sides of the shooting target (quadrangle) to be actually shot are present on up and down and right and left. In this case, it is more efficient to measure the number of votes on the ρ-θ plane within the range given by the following equation as shown in FIGS. 8A and 8B than to inspect them within the range of 0° ≤ θ &lt; 180°.

Upper and lower sides

45° ≤ θ &lt; 135° (or 225° ≤ θ &lt; 315°)    at this time, sinθ: 0.707 → 1 → 0.707,       cosθ: 0.707 → 0 → -0.707

Right and left sides

135° ≤ θ &lt; 225° (or 315° ≤ θ &lt; 45°)    at this time, sinθ: 0.707 → 1 → -0.707,       cosθ: -0.707 → -1 → -0.707

The upper and lower sides or the right and left sides can be specified depending on whether the value of ρ is positive or negative. When the center of the shooting target is positioned near the center of the image, as apparent from the above, the sides constituting the contour can be selected more efficiently.

Lines which form the quadrangle of the contour of the image of the shooting target are specified from those lines which are detected through Hough transformation.

In general, the outermost quadrangle in the shooting target may be specified as the contour of the shooting target. The aforementioned maximum area can be specified by specifying the upper and lower sides and right and left sides to those with the maximum absolute values |ρ| of ρ. Sorting the absolute values |ρ| in size order, the order is determined as the priority order of line candidates.

When four lines of the quadrangle are selected, their points of intersection are then acquired. The xy coordinates at which the four lines of the quadrangle intersect one another are computed by converting lines expressed by the ρ-θ system to lines of the (x, y) coordinate system.

As the acquired coordinates are the coordinates (m, n) of a reduced image, the coordinate values, if multiplied by K, correspond to the coordinates (x, y) of the original image. Let the coordinates of the four vertices of the quadrangle acquired in that manner be (x0, y0), (x1, y1), (x2, y2) and (x3, y3).

Based on the concept, the image processing apparatus 25 executes the process of acquiring the contour of the shooting target according to the flowchart illustrated in FIG. 9.

The image processing apparatus 25 acquires a reduced image Q from the shot image by sequentially substituting m = 0 to xmax/K and n = 0 to ymax/K in the equations 1 and 2 (step S31).

The image processing apparatus 25 performs an arithmetic operation using the Roberts filter expressed by the equation 3, and acquires an edge binary image by digitizing the reduced image according to the equation 4 (step S32).

The image processing apparatus 25 performs Hough transformation on the acquired edge binary image according to the equation 5 to detect lines forming the edge binary image (step S33).

The image processing apparatus 25 selects quadrangle candidates by combining the detected lines (step S34). The image processing apparatus 25 executes the process of selecting the quadrangle candidates according to the flowchart illustrated in FIG. 10.

That is, the image processing apparatus acquires a plurality of coordinates which have a large number of votes in the range of 45° ≤ θ &lt; 135° as candidates for lines forming the upper and lower sides (step S41).

Likewise, the image processing apparatus acquires a plurality of coordinates which have a large number of votes in the range of 135° ≤ θ &lt; 225° as candidates for lines forming the right and left sides (step S42).

The image processing apparatus 25 sets the degrees of priority of those candidates in the X-axial direction and the candidates in the Y-axial direction the signs of whose ρ values differ in order from a descending order (step S43).

The image processing apparatus 25 selects the upper and lower and right and left sides which have the maximum values of ρ as the most likely candidates (step S44).

The image processing apparatus 25 writes the vertex coordinates of the selected quadrangle candidate (step S35 in FIG. 9). The quadrangle candidate is selected this way. (2) Image conversion (process at step S21 in FIG. 4)

To begin with, projection transformation will be described.

As shown in FIG. 11, let p(x, y) and P(u, v) be the original image to be subjected to extraction and projection correction and before projection transformation and a projection-transformed image after projection transformation, respectively, the original image p(x, y) and the projection-transformed image P(u, v) are associated with each other by the affine transformation equation. In FIG. 11, (x, y) indicates the pixel position of the original image p(x, y), and (u, v) indicates the pixel position of the projection-transformed image P(u, v).

The image processing apparatus 25 acquires affine parameters by associating the vertex coordinates (x0, y0), (x1, y1), (x2, y2) and (x3, y3) of the quadrangle candidate for the image of the original acquired by the process of selecting the quadrangle candidate for the image of the original with elements of the matrix of the general equation of the affine transformation.

Affine transformation from the projection-transformed image P(u, v) to be acquired to the original image p(x, y) is given by the following equation 7.<maths id="math0007" num="(7)"><math display="block"><mrow><mtext mathvariant="italic">x</mtext><mtext> = </mtext><mfrac><mrow><mtext mathvariant="italic">x</mtext><mtext>'</mtext></mrow><mrow><mtext mathvariant="italic">z</mtext><mtext>'</mtext></mrow></mfrac><mtext> = </mtext><mfrac><mrow><msub><mrow><mtext mathvariant="italic">a</mtext></mrow><mrow><mtext>11</mtext></mrow></msub><mtext mathvariant="italic">u</mtext><mtext>+</mtext><msub><mrow><mtext mathvariant="italic">a</mtext></mrow><mrow><mtext>21</mtext></mrow></msub><mtext mathvariant="italic">v</mtext><mtext>+</mtext><msub><mrow><mtext mathvariant="italic">a</mtext></mrow><mrow><mtext>31</mtext></mrow></msub></mrow><mrow><msub><mrow><mtext mathvariant="italic">a</mtext></mrow><mrow><mtext>13</mtext></mrow></msub><mtext mathvariant="italic">u</mtext><mtext>+</mtext><msub><mrow><mtext mathvariant="italic">a</mtext></mrow><mrow><mtext>23</mtext></mrow></msub><mtext mathvariant="italic">v</mtext><mtext>+</mtext><msub><mrow><mtext mathvariant="italic">a</mtext></mrow><mrow><mtext>33</mtext></mrow></msub></mrow></mfrac><mspace linebreak="newline" /><mtext mathvariant="italic">y</mtext><mtext> = </mtext><mfrac><mrow><mtext mathvariant="italic">y</mtext><mtext>'</mtext></mrow><mrow><mtext mathvariant="italic">z</mtext><mtext>'</mtext></mrow></mfrac><mtext> = </mtext><mfrac><mrow><msub><mrow><mtext mathvariant="italic">a</mtext></mrow><mrow><mtext>12</mtext></mrow></msub><mtext mathvariant="italic">u</mtext><mtext>+</mtext><msub><mrow><mtext mathvariant="italic">a</mtext></mrow><mrow><mtext>22</mtext></mrow></msub><mtext mathvariant="italic">v</mtext><mtext>+</mtext><msub><mrow><mtext mathvariant="italic">a</mtext></mrow><mrow><mtext>32</mtext></mrow></msub></mrow><mrow><msub><mrow><mtext mathvariant="italic">a</mtext></mrow><mrow><mtext>13</mtext></mrow></msub><mtext mathvariant="italic">u</mtext><mtext>+</mtext><msub><mrow><mtext mathvariant="italic">a</mtext></mrow><mrow><mtext>23</mtext></mrow></msub><mtext mathvariant="italic">v</mtext><mtext>+</mtext><msub><mrow><mtext mathvariant="italic">a</mtext></mrow><mrow><mtext>33</mtext></mrow></msub></mrow></mfrac></mrow></math><img file="EP1577832A2_D0007.tif" /></maths>

In the equation 7, the affine parameters are given by the following equation 8.<maths id="math0008"><img file="EP1577832A2_D0008.tif" /></maths> where α and β are given by the following equation 9.<maths id="math0009" num="(9)"><math display="block"><mrow><mtext>α = </mtext><mfrac><mrow><mtext>(x0-x1+x2-x3)·(y3-y2)-(x3-x2)·(y0-y1+y2 -y3)</mtext></mrow><mrow><mtext>(x1-x2)·(y3-y2)-(x3-x2)(y1-y2)</mtext></mrow></mfrac><mspace linebreak="newline" /><mtext>β = </mtext><mfrac><mrow><mtext>(x1-x2)·(y0-y1+y2-y3)-(x0-x1+x2-x3)-(y1-y2)</mtext></mrow><mrow><mtext>(x1-x2)·(y3-y2)-(x3-x2) (y1-y2)</mtext></mrow></mfrac></mrow></math><img file="EP1577832A2_D0009.tif" /></maths>

The projection-transformed image P(u, v) can be acquired from the original image p(x, y) based on the equations 7 to 9. Further, the image processing apparatus 25 performs distortion correction in addition to extraction and projection transformation.

To execute distortion correction, first, the pixel positions of the original image p(x, y) corresponding to the pixel positions of the projection-transformed image P(u, v) are acquired. In acquiring the projection-transformed image P(u, v), it is convenient to acquire the pixel positions (x, y) of the original image p(x, y) corresponding to the pixel positions (u, v) of the projection-transformed image P(u, v) by using inverse transformation A of the affine transformation Af, rather than acquiring the pixel positions (u, v) of the projection-transformed image P(u, v) corresponding to the pixel positions (x, y) of the original image p(x, y) using the affine transformation Af, as shown in FIG. 11.

To acquire the pixel positions of the original image p(x, y) corresponding to the pixel positions (u, v) of the projection-transformed image P(u, v), affine parameters given by the equation 8 are used. It is to be noted however that the pixel positions (x, y) are the pixel positions of a distortion-free image or an image undergone distortion correction, so that the original image p(x, y) are replaced with an image p1(x', y') to set an image before distortion correction to p(x, y). With the replacement done, the equation 7 is rewritten to be the following equation 10.<maths id="math0010" num="(10)"><math display="block"><mrow><mtext mathvariant="italic">x</mtext><mtext>' = </mtext><mfrac><mrow><mtext mathvariant="italic">x</mtext><mtext>"</mtext></mrow><mrow><mtext mathvariant="italic">z</mtext><mtext>"</mtext></mrow></mfrac><mtext> = </mtext><mfrac><mrow><msub><mrow><mtext mathvariant="italic">a</mtext></mrow><mrow><mtext>11</mtext></mrow></msub><mtext mathvariant="italic">u</mtext><mtext>+</mtext><msub><mrow><mtext mathvariant="italic">a</mtext></mrow><mrow><mtext>21</mtext></mrow></msub><mtext mathvariant="italic">v</mtext><mtext>+</mtext><msub><mrow><mtext mathvariant="italic">a</mtext></mrow><mrow><mtext>31</mtext></mrow></msub></mrow><mrow><msub><mrow><mtext mathvariant="italic">a</mtext></mrow><mrow><mtext>13</mtext></mrow></msub><mtext mathvariant="italic">u</mtext><mtext>+</mtext><msub><mrow><mtext mathvariant="italic">a</mtext></mrow><mrow><mtext mathvariant="italic">23</mtext></mrow></msub><mtext mathvariant="italic">v</mtext><mtext>+</mtext><msub><mrow><mtext mathvariant="italic">a</mtext></mrow><mrow><mtext>33</mtext></mrow></msub></mrow></mfrac><mspace linebreak="newline" /><mtext mathvariant="italic">y</mtext><mtext>'= </mtext><mfrac><mrow><mtext mathvariant="italic">y</mtext><mtext>"</mtext></mrow><mrow><mtext mathvariant="italic">z</mtext><mtext>"</mtext></mrow></mfrac><mtext> = </mtext><mfrac><mrow><msub><mrow><mtext mathvariant="italic">a</mtext></mrow><mrow><mtext>12</mtext></mrow></msub><mtext mathvariant="italic">u</mtext><mtext>+</mtext><msub><mrow><mtext mathvariant="italic">a</mtext></mrow><mrow><mtext>22</mtext></mrow></msub><mtext mathvariant="italic">v</mtext><mtext>+</mtext><msub><mrow><mtext mathvariant="italic">a</mtext></mrow><mrow><mtext>32</mtext></mrow></msub></mrow><mrow><msub><mrow><mtext mathvariant="italic">a</mtext></mrow><mrow><mtext>13</mtext></mrow></msub><mtext mathvariant="italic">u</mtext><mtext>+</mtext><msub><mrow><mtext mathvariant="italic">a</mtext></mrow><mrow><mtext>23</mtext></mrow></msub><mtext mathvariant="italic">v</mtext><mtext>+</mtext><msub><mrow><mtext mathvariant="italic">a</mtext></mrow><mrow><mtext>33</mtext></mrow></msub></mrow></mfrac></mrow></math><img file="EP1577832A2_D0010.tif" /></maths> where <ul id="ul0006" list-style="none" compact="compact"><li>(x", y", z"): coordinates of the image P without distortion</li><li>(x', y'): coordinates of the image p without distortion.</li></ul>

The image p1(x', y') is associated with the image p(x, y) before distortion correction by the relational equation 2. Using the equation 2, therefore, individual coordinates (x, y) of the corresponding image p(x, y) before distortion correction can be acquired from the coordinate positions (x', y') of the image p1(x', y') while performing correction corresponding to distortion correction which has been executed when having generated the reduced image.

The pixel values x, y of the points p(x, y) of the original image corresponding to the individual pixels of the projection-transformed image P(u, v) acquired this way should not necessarily be an integer. In this respect, a bilinear scheme should be used as the interpolation method. The bilinear-based interpolation is to acquire the pixel values of the coordinates (x, y) of one image or the original image (projection-transformed image p) corresponding to the pixel values of the coordinates (u, v) of the other image (image P) from the pixel values of the surrounding four points p(X, Y), p(X+1,Y), p(X, Y+1) and p(X+1, Y+1) as the pixel values of the coordinates (u, v) of the other image, as given by the following equation 11.<maths id="math0011" num="(11)"><math display="block"><mrow><mtext>P(u, v) = (1 - kx)*(1 - ky)*p(X, Y) + kx*(1 - ky)*p (X+1, Y)</mtext><mspace linebreak="newline" /><mtext>+ (1 - kx)*ky*p(X, Y+1) + kx*ky*p(X+1, Y+1)</mtext></mrow></math><img file="EP1577832A2_D0011.tif" /></maths> where with p(x, y) being the coordinates of the point p of one image, <ul id="ul0007" list-style="none" compact="compact"><li>kx: the value equal to or smaller than a decimal point of x</li><li>ky: the value equal to or smaller than a decimal point of y</li><li>X: integer portion (x)</li><li>Y: integer portion (y).</li></ul>

Based on the concept, the image processing apparatus 25 executes the projection transformation process based on affine transformation according to the flowchart illustrated in FIG. 12. Let the coordinates u, v indicating the pixel positions (u, v) of the projection-transformed image P(u, v) be 0 ≤ u ≤ umax and 0 ≤ v ≤ vmax, respectively.

The image processing apparatus 25 initializes the coordinate u of the projection-transformed image P(u, v) to 0 (step S51).

The image processing apparatus 25 initializes the coordinate v of the projection-transformed image P(u, v) to 0 (step S52).

The image processing apparatus 25 acquires the pixel positions (x', y') of the image p1(x', y') by substituting the pixel positions (u, v) of the projection-transformed image P(u, v) in the equation 10 (step S53).

The image processing apparatus 25 performs correction on the acquired pixel positions (x', y') of the image p1(x', y') according to the equation 2 to acquire the pixel positions (x, y) of the image p(x, y) (step S54).

The image processing apparatus 25 performs bilinear-based interpolation according to the equation 11 using the projection-transformed image P(u, v) and the image p(x, y) to acquire the pixel values of the projection-transformed image P(u, v) (step S55).

The image processing apparatus 25 increments the coordinate v of the projection-transformed image P(u, v) by 1 (step S56).

The image processing apparatus 25 compares the coordinate v of the projection-transformed image P(u, v) with the maximum value vmax, and determines whether the coordinate v of the projection-transformed image P(u, v) becomes equal to or greater than the maximum value vmax (step S57).

When it is determined that the coordinate v is less than the maximum value vmax (NO at step S57), the image processing apparatus 25 executes steps S53 to S56 again.

When it is determined that the coordinate v has reached the maximum value vmax (YES at step S57) through the repetitive execution of steps S53 to S56, the image processing apparatus 25 increments the coordinate u of the projection-transformed image P(u, v) by 1 (step S58).

The image processing apparatus 25 compares the coordinate u with the maximum value umax, and determines whether the coordinate u becomes equal to or greater than the maximum value umax (step S59).

When it is determined that the coordinate u is less than the maximum value umax (NO at step S59), the image processing apparatus 25 executes steps S52 to S58 again.

When it is determined that the coordinate u has reached the maximum value umax (YES at step S59) through the repetitive execution of steps S52 to S58, the image processing apparatus 25 terminates the image converting process.

If the pixel values of the projection-transformed image P(u, v) can be acquired this way, the projection-transformed image P(u, v) can be acquired from the image p(x, y) before distortion correction.

According to the embodiment, as described above, distortion correction is not executed over the entire original image, but distortion correction is executed at the time of generating a reduced image to acquire the contour of the image of an original. Therefore, the amount of computation for distortion correction becomes smaller, making it possible to shorten the operation time.

When a reduced image is generated by reducing an image input to the digital camera 1 to 1/K, for example, the number of operations for that distortion correction becomes 1/(K^2) which is extremely small.

Because the correlation between the image p(x, y) before distortion correction and the projection-transformed image P(u, v) is acquired through correction corresponding to distortion correction at the time of executing the projection transformation process based on affine transformation, the projection-transformed image P(u, v) can be acquired accurately from the image p(x, y) before distortion correction.

Various modes are possible in working out the invention which is not limited to the above-described embodiment.

For example, the image processing apparatus 25 may reduce an image according to the display image, not an image input to the digital camera 1. Even when the input image to the digital camera 1 has an image size of four million pixels, for example, if the display image for a computer has an image size of 1024 x 768 = 80,000 pixels, the image processing apparatus 25 can reduce the image of 800,000 pixels to 1/K according to the image size of the display image for the computer. This scheme can further reduce the number of operations for distortion correction to about 1/5 as compared with the case where an image with four million pixels is reduced to 1/K. Even when a sheet of A4 size (297 x 210 mm) is shot, the sufficient contour extraction precision should normally have as high a resolution as 1 to 2 mm. Therefore, a reduced image even with a size of 320 x 240 can sufficient achieve the precision. In this case, data can be reduced to 1/52.

In the embodiment, the digital camera 1 is equipped with the image processing apparatus 25. However, an image shooting apparatus may comprise a computer in addition to the digital camera 1, and the computer may have the image processing apparatus 25 having the aforementioned functions, so that the computer is connected to the digital camera 1. In this modification, a general-purpose digital camera can be used for the digital camera 1.

The image processing apparatus 25 according to the embodiment should not necessarily be used in an image shooting apparatus, but can be constructed in such a way as to a computer is provided with the functions of the image processing apparatus of the embodiment, so that the computer can store images to be subjected to distortion correction and correction of keystone distortion and can execute the image processing on the stored images without using the digital camera 1.

Programs which allow a computer to execute the above-described processes may be stored in a computer-readable recording medium, such as a flexible disk, CD-ROM (Compact Disk Read-Only Memory) or DVD (Digital Versatile Disk), and delivered and installed in the computer so that the computer may operate as the individual means mentioned above or execute the above-described steps. The programs may be stored in a disk unit or the like installed in a server on the Internet, so that the programs may be downloaded to a computer by way of carrier waves on which the programs are multiplexed.

In the embodiment, linear distortion such as keystone distortion and rotational distortion which occurs according to a shooting angle at the time of shooting a subject to be Shot is corrected by affine transformation. However, any other projection transformation than affine transformation may be used as long as such projection transformation can correct such linear distortion. Further, projection transformation which cannot precisely correct linear distortion but can correct it approximately may be used. The subject to be shot may not be a sheet on which an original text is written but may be a building, etc. Not only a subject to be shot having a rectangular shape but also a subject to be shot having an arbitrary shape can be treated by the present invention, as long as the shape is known beforehand. Also in this case, a projection parameter can be acquired by comparing the shape of the subject to be shot with a shape acquired from a shot image of the subject to be shot. A projection parameter may be acquired not by acquiring a shot image showing the entire shape of the subject to be shot but by acquiring some distorted points of the subject to be shot.

In the embodiment, distortion correction according to a characteristic of a lens is performed at the time of acquiring a reduced image by reducing a shot image. At the same time of reduction, distortion correction for a distortion whose occurrence is anticipated before shooting due to a factor other than a lens characteristic may be performed at the same time of reduction.

Various embodiments and changes may be made thereunto without departing from the broad spirit and scope of the invention. The above-described embodiment is intended to illustrate the present invention, not to limit the scope of the present invention,. The scope of the present invention is shown by the attached claims rather than the embodiment. Various modifications made within the meaning of an equivalent of the claims of the invention and within the claims are to be regarded to be in the scope of the present invention.