Multiple image area detection in a digital image

A method for detecting an image area in a digital image includes identifying in the digital image a first image region indicative of a background area and a second image region indicative of the image area, computing gradient values using the pixel values of the digital image, defining a list of strokes based on the gradient values, merging the list of strokes, defining a list of corners using the list of strokes, and defining an image area rectangle delimiting the image area using the list of corners and the list of strokes. The image area rectangle can be used to define a binding box for extracting the image area from the digital image. The method enables the automatic detection of multiple image areas in a digital image. Moreover, the method implements a robust algorithm for image area detection such that even imperfect image areas can be detected without errors.

BACKGROUND OF THE INVENTION

1. Field of the Invention

The invention relates to image processing, and more particularly to a method for detecting multiple image areas in a digital image.

2. Description of the Related Art

With the advent of digital cameras and scanners, digital photography is becoming more popular and accessible to consumers. Digital images are often created either by capturing a scene using a digital camera or digitizing a traditional film-based photograph using a scanner. Digital photography has many advantages over the traditional film-based photography. One particular advantage is that digital images can be easily manipulated or edited for better presentation. Furthermore, the digital images can be readily distributed over electronic media such as the internet or electronic mail.

When a scanner is used to create a digital image from a film-based photograph, often the user has to scan in each photograph separately because most scanners treat each scan page as one picture. If multiple photographs are scanned in at the same time, the entire scan page is treated as one image and individual photographs cannot be readily separated into individual image files. Because the scan process can be very slow, often up to a few minutes per scan page, it is very time consuming to scan a large number of photographs individually. Because film-based photographs are usually 3″ by 5″ or 4″ by 6″ and because the scan page is typically large enough to accommodate more than one such photographs, it is desirable to scan multiple photographs at a time to speed up the scanning process.

Presently, when a scanned image is created including multiple photographs, the individual photographs can be extracted using commonly available photo editing tools. Often, the process requires the user to manually extract each photograph from the scanned image to generate separate image files for each individual photograph. Such manual cropping may be a complicated and time consuming process in itself. Furthermore, most photo editing tools may limit the crop area to a certain shape, such as an upright rectangular binding box. In that case, the user must ensure that the photographs are aligned properly on the scanner before scanning so that individual photographs will fit properly inside the cropping rectangle.

A scanner with batch scan capability allowing the user to scan multiple images in one scan job has been introduced. It is desirable to provide a method for automatically detecting and extracting individual photographs from a digital image containing multiple photographs. Such algorithm should be able to perform such automatic detection effectively so that manual intervention is entirely eliminated.

SUMMARY OF THE INVENTION

According to one embodiment of the present invention, a method for detecting an image area in a digital image including the image area and a background area is disclosed. The digital image is represented as a two-dimensional array of pixel values. The method includes identifying in the digital image a first image region indicative of the background area and a second image region indicative of the image area, and computing gradient values using the pixel values for pixel locations in the digital image associated with a boundary between the first image region and the second image region.

The method further includes defining a list of strokes based on the gradient values. Each stroke is a line segment having a start pixel location and an end pixel location. Each stroke is derived from a region of pixel locations having non-zero gradient values of the same sign. Pixel locations to a first side of each stroke are in the second image region and pixel locations to a second side of each stroke are in the first image region.

The method further includes merging the list of strokes. In operation, a first stroke and a second stroke in the list of strokes are merged when the first and second strokes are collinear and a start pixel location of one of the first and second strokes is near an end pixel location of the other one of the first and second strokes.

The method then includes defining a list of corners using the list of strokes. Each corner is a pixel location of an intersection of a third stroke and a fourth stroke. The third stroke and the fourth stroke form a corner when the third stroke is perpendicular to the fourth stroke, the third and fourth strokes are arranged in a third direction, and a start pixel location of one of the third and fourth strokes is close to an end pixel location of the other one of the third and fourth strokes.

Lastly, the method includes defining an image area rectangle delimiting the image area using the list of corners and the list of strokes. The image area rectangle is defined based on one or more corners fitting a predefined corner configuration and one or more strokes associated with the corners. The strokes forms at least a portion of a perimeter of the image area rectangle.

In the present disclosure, like objects which appear in more than one figure are provided with like reference numerals.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS

In accordance with the principles of the present invention, a method for detecting an image area in a digital image including the image area and a background area and defining an image area rectangle delimiting the image area is disclosed. The image area detection method uses gradient information of the digital image to define strokes and corners which are used, in turn, to define the image area rectangle. The image area rectangle can be used to define a binding box for extracting the image area from the digital image so that the image area can be made into an individual image file. The method of the present invention enables automatic detection of multiple image areas in a digital image, thereby alleviating the need for the time-consuming task of manually cropping multiple image areas. More importantly, the method of the present invention implements a robust algorithm for image area detection such that even imperfect image areas can be detected without errors. The image area detection method of the present invention can consistently provides accurate and reliable image detection results, despite the conditions of the digital image.

The image area detection method of the present invention operates on a digital image which is typically represented as a two-dimensional array of pixel values. If the digital image is a color image, each pixel value typically consists of three pixel values representing the three primary colors (such as red, green, blue). The digital image can be generated in any number of ways, such as by a digital camera or a scanner. The digital image can be stored in any conventional digital image format, such as TIFF, JPEG and Bitmap (.bmp) formats. In the preferred embodiment of the present invention, the digital image is stored in the Bitmap format. Techniques for converting TIFF or JPEG image files to Bitmap format are well known in the art of image processing. The size and resolution of the digital image may vary depending on the application which created the image. In the case of a letter size digital image created by a scanner with a 300 dpi resolution, the digital image can be approximately 2200 pixels wide by 3000 pixels long.

The image area detection method of the present invention operates on a digital image including one or more image areas. The image areas may contain with a variety of image content, such as photographs, drawings and text (e.g. a business card). The algorithm implemented in the image area detection method is designed to be very robust so as to detect image areas presented under a variety of conditions. For instance, an image area can be positioned askew relative to the orientation of the digital image. The image area may include slant edges and thus is not a proper rectangular area. Specifically, the robustness of the algorithm allows even imperfect image areas to be detected. In the present description, an imperfect image area is an image area without distinct or complete boundaries. Missing boundaries can occur when an image area is white in color near one or more boundaries of the image area. Imperfect image areas also include image areas where one image area overlaps another image area. As long as sufficient areas of the overlapped image areas are exposed, the method of the present invention can still operate to define the boundary of each overlapped image area.

In the present embodiment, the image area detection method is able to detect an imperfect image area if the following two limitations are met. First, if an image area is positioned askew, the image area should not be positioned more than 30 degrees askew relative to the digital image. This limitation is imposed to ensure that the gradient calculation process can determine a primary orientation (horizontal or vertical) of the boundary of the image area, as will be explained in more detail below. Second, two image areas cannot be positioned too close to each other. In one embodiment, the space between the image areas should be larger than 1 to 2 percent of the width or height of the digital image. For example, if the digital image is 2000×3000 pixels, the space between the image areas should be more than 20 pixels. This limitation is imposed because in the image area detection method, the digital image is resized to an image having a lower resolution to enhance the processing efficiency. A gap between two image areas that is too small may become indistinguishable in the resized lower-resolution image.

The image area detection method of the present invention generates as output a list of coordinates defining image area rectangles where each rectangle delineates the boundary of an image area. In the preferred embodiment, the image area rectangle is defined by the coordinates of the pixel locations of the rectangle's four corners. In the present description, a rectangle includes a parallelogram with the adjacent sides of unequal length or all fours sides of equal length (i.e., a square).

The image area detection method of the present invention has numerous applications in image processing. One application where the method of the present invention can be particularly useful is the detection of multiple photographs in a scanned image. As mentioned above, the scanning of a page of document (a scan job) can be a very slow process. Therefore, scanning of multiple photographs can be very time consuming if each photograph has to be scanned separately. In accordance with the present invention, a user may scan multiple photographs at each scan job and use the image area detection method of the present invention to automatically detect and extract the individual photographs. In this manner, the method of the present invention can greatly improve the user experience by reducing the time needed to scan a large number of photographs.

FIG. 1is an exemplary scanned digital image including multiple image areas. Referring toFIG. 1, digital image10is generated in one scan job by placing various image objects (photographs and a business card) on a scanner. As a result of the scanning process, digital image10is created as a letter size image containing four image areas12-15on a background area which is typically white. Digital image10may have a resolution of 2000 pixels by 3000 pixels.

Digital image10is provided to illustrate the various conditions under which a digital image can be created. InFIG. 1, image area12is a photograph and is placed upright and in a proper orientation with respect to the boundary of digital image10. On the other hand, image areas13and14are two other photographs that are placed askew and do not align with the boundaries of digital image10. Because of the misalign orientation, image areas13and14are typically difficult to extract using conventional image editing tools. Image area14includes an additional imperfection in that the photograph has a cropped edge (edge14a) and thus the image area is not a perfect rectangle. Finally, image area15is a business card having a white background color similar to the background color of digital image10. Consequently, in the scanning process, one or more boundaries of the business card may not be detected or may not be distinguishable from the background of digital image10. As shown inFIG. 1, the top and left edges of image area15are almost indistinguishable from the background of digital image10. Although digital image10is described as a scanned image in the present description, digital image10is representative of any digital image generated using any means presently known or to be developed.

FIG. 2illustrates the digital image ofFIG. 1with image area rectangles defined using the image area detection method according to one embodiment of the present invention. After the operation of the image area detection method of the present invention, four image area rectangles22-25delimiting the boundaries of image areas12-15are generated.FIG. 2illustrates the robustness of the image area detection method of the present invention. An image area rectangle can be defined when an image area is upright (image area rectangle22) or when an image area is askew (image area rectangle23). An image area rectangle can be defined even when one of the edges of the image area is not straight (such as image area rectangle24). Lastly, an image area rectangle can be defined even when one or more boundaries of an image area are missing (such as image area rectangle25). The image area detection method of the present invention will now be described in detail with reference toFIGS. 3-29.

Method Overview

FIG. 3is a flowchart illustrating an image area detection method100according to one embodiment of the present invention. First, an overview of the image area detection method will be provided. The operation of each step in the method will be described in more detail below.

Method100begins with an algorithm initialization process102which receives as input a digital image file101. In the present description, digital image file101contains digital image10ofFIG. 1in bitmap format. Algorithm initialization process102generates a resized image132which is a reduced resolution image of digital image10. Resized image132is used as a proxy for digital image10in all of the subsequent steps of method100.

Method100proceeds with a region segmentation process104which operates to segment resized image132into image area region or background area region. The result of process104is a gray-scale image file134containing the segmentation information.

Then, method100performs a gradient calculation process106. Gradient measures the amount of change in pixel values at a pixel location. Gradient values in both the horizontal and vertical directions are computed. Large image gradients usually occur throughout an image area. However, the gradient values of interest are those that are located at or near the boundary of the image area region and the background area region. The gradient values at or near the boundary of the image area region and the background area region can be used as an indicator of the edges of the image areas. Process106generates an x-Gradient image file136aand a y-Gradient image file136b.

Having obtained the gradient information, method100proceeds to a stroke detection process108for defining a set of strokes demarcating the boundary of the image area region and the background area region of resized image132. In the present description, a stroke is a line segment with a start point and an end point. The start point and end point can be expressed as coordinates of pixel locations in resized image132. A further constraint is imposed on the definition of a stroke to ensure that all strokes conform to the same orientation. Thus, in the present description, a stroke is defined such that when viewed from the start point to the end point, pixel locations on the left side of a stroke are located in the image area region while pixel locations on the right side of the stroke are located in the background area region. Process108generates a list of strokes138defined by the pixel locations of the start and end points of each stroke.

Next, a stroke merge process110is performed to attempt to merge as many of the strokes defined in process108as possible. Specifically, two strokes are merged when they are collinear and the start point of one is near the end point of another. The merging of strokes are carried out so that, as much as possible, each stroke is made to demarcate one edge of an image area. The result of process110is an updated list of strokes140.

Next, using the strokes defined in process110, method100proceeds to a corner detection process112. A corner is defined as a pixel location where two strokes are perpendicular to each other, are oriented in a counter-clockwise manner and have start/end points which are sufficiently close. Process112defines a list of corners142which are used as possible vertexes of the image area rectangles to be defined.

Finally, having defined a list of strokes140and a list of corners142, method100now proceeds to a rectangle detection process114. Process114uses the locations of the corners and the strokes associated with each corner to determine possible configurations of an image area rectangle. After an image area rectangle with the best likelihood value has been selected, the corners and strokes associated with that image area rectangle are removed from the lists. Method100repeats process114until all image area rectangles have been detected (step116). Process114generates a list of image area rectangles144defined by the pixel locations of each rectangle's vertexes.

At the conclusion of rectangle detection process114, method100performs a algorithm cleanup process118which, among other things, resizes the image area rectangles to the image size of the original digital image10. Thus, process118generates a list of resized image area rectangles146defining the boundary of image areas in digital image10as shown in FIG.2. The list of image area rectangles146can used by any image editing tool to extract each individual image area from digital image10so that each individual image area becomes its own image file.

The steps in method100will now be described in detail.

Algorithm Initialization

FIG. 4is a flowchart illustrating the algorithm initialization process of the image area detection method according to one embodiment of the present invention. Referring toFIG. 4, algorithm initialization process102includes two steps. First, at step202, data structure used by method100is initialized. The specific data structure used at each of the steps in method100will be described with reference to each respective step in method100. When method100is implemented in software, initialization of data structure can be implemented using conventional software techniques.

Then, at step204, digital image10defined by digital image file101is resized to a resized image132having reduced resolution. As described above, most digital images, such as scanned digital image10, can include a few thousand or more pixels in width and in height. To reduce the computational burden and improve the processing efficiency in subsequent steps of method100, digital image10is resized to a resized image having reduced resolution. In one embodiment, the resized image has a resolution of 256×256 pixels to 512×512 pixels. The reduced resolution can be obtained by averaging between a neighborhood of pixels, such as a 2×2, 4×4 or 8×8 neighborhood of pixels. Resized image132having lower image resolution than digital image10is shown in FIG.5. In the present embodiment, resized image132has a resolution of 282×390 pixels, reduced from digital image10which has a resolution of 2261×3122 pixels.

Region Segmentation

In a scanned image such as digital image10, the image generally consists of a bright background area whose color is very close to white. An image area within digital image10, containing photographs or other images, is generally not entirely white in color. By using this heuristic, an image area can be defined as an area containing non-white pixel values. Accordingly, at region segmentation process104, resized image132can be segmented into a background area region and an image area region based on the color of each pixel location.

FIG. 6is a flowchart illustrating the region segmentation process of the image area detection method according to one embodiment of the present invention. First, at step210, a gray-scale image file134for storing the segmentation result is initialized. Gray-scale image file134has the same size (282×390 pixels) as resized image132and each pixel location in gray-scale image file134is represented by one color value only (typically one byte of data or 8-bit). Each pixel location in image file134corresponds to the respective pixel location in resized image132and thus image file134is used as a flag to mark the result of the segmentation process for each pixel location in resized image132.

Region segmentation process104operates on resized image132. At step211, a first pixel in resized image132is selected as the current pixel. Note that in the present description, all image files, including resized image132, are stored in the bitmap format so that pixel values are stored in a traversal order of lower-left corner to upper right corner in the digital image, which pixel traversal order will be used throughout the present description.

At step212, the color pixel value for the current pixel is retrieved from resized image132. In the present description, the term “color pixel value” refers to the pixel value of a color pixel including pixel values for the three primary color components. In most applications, the three primary color components are red, green and blue. Each color pixel value can be expressed in 8-bit or more. A color pixel is white in color when the pixel values of the three color components are each at its maximum value (i.e., 255 for an 8-bit pixel value). On the other hand, a color pixel is black in color when the pixel values for the three color components are each zero. In the present description, an 8-bit pixel value is assumed.

At step214, the color pixel value of the current pixel is compared with a predefined threshold value to determine if the current pixel is white in color. For an 8-bit pixel value, a threshold of 190 or larger can be used to segregate the white pixels from the other color pixels. In operation, at step214, the pixel value for each color component (red, green and blue) is individually compared with the threshold value. If the pixel values of all three color components are greater than the threshold value, then the current pixel is classified as a white color pixel (step216). The result is recorded in gray-scale image file134by setting the pixel value for the current pixel in gray-scale image file134to255. If the pixel values for any one of the three color components is less than the threshold value, then the current pixel is classified as a black color pixel (step218). The result is recorded in gray-scale image file134by setting the pixel value for the current pixel in gray-scale image file134to 0.

Process104continues by selecting the next pixel as the current pixel (step220). As long as there are pixels to be processed, steps212to220will be repeated to classify each pixel location as either white or black, corresponding to either the background area or the image area respectively. When all the pixels in resized image132have been processed (step222), region segmentation process104is completed (step224) and gray-scale image file134containing the segmentation information is created.

FIG. 7illustrates the gray-scale image file134generated as a result of the operation of the region segmentation step on resized image132. Referring toFIG. 7, white area in gray-scale image file134represents potential background area in digital image10while black area in gray-scale image file134represents potential image areas. For example, image areas containing the three photographs in digital image10are marked as black in image file134. The image area containing the business card is identified as white because the business card is white in color itself. As can be seen in the following description, the image area detection method of the present invention is capable of detecting an image area even though the image area contains substantially white color.

Gradient Calculation

Referring toFIG. 3, after identifying the background area region and the image area region of resized image32in process104, method100proceeds to gradient calculation process106to compute gradient values for each pixel location in resized image132.FIG. 8is a flowchart illustrating the gradient calculation process of the image area detection method according to one embodiment of the present invention.

Image gradient measures the degree of change in pixel values at a given pixel location in an image. A large gradient value indicates a large change in color or brightness in the image. Therefore, gradient information can be used to identify the boundaries between a background area and an image area because such boundaries are characterized by significant color changes. In image processing art, boundaries of large gradient changes are referred to as “edges.” Image gradient, and thus image edges, can occur in both the horizontal or the vertical direction. In accordance with the present invention, gradient values are computed for detecting horizontal and vertical image edges in resized image132. These edges are used as evidence of boundaries between image areas and the background area.

In addition to the boundaries between image areas and the background area, texture and contents inside an image area (such as a photograph) can generate large image gradient, and consequently, a large number of edges. The large number of edges within an image area can obscure the actual boundaries the image area detection method is trying to identify. Therefore, in accordance with the present invention, the gradient information is used in conjunction with the segmentation information previously determined so that only gradient information that are indicative of potential boundaries between an image area and a background area are retained. Gradient information that occurs within a potential image area are discarded. In this manner, the method of the present invention can provide a robust image area detection result.

Note that an image gradient occurring in the horizontal direction generates an edge which is in the vertical direction, and vice versa. In the following description, the term “x-Grad” is used to refer to gradient values in the horizontal direction and thus represents edges that are in the vertical direction (y-Edge). On the other hand, the term “y-Grad” is used to refer to gradient values in the vertical direction and thus represents edges that are in the horizontal direction (x-Edge).

Referring toFIG. 8, gradient calculation process106begins by creating two image files for storing the result of the calculation (step230). Specifically, an x-Gradient image file136afor storing gradient values in the horizontal direction and a y-Gradient image file136bfor storing gradient values in the vertical direction are created. Image files136aand136bare each a gray-scale image file in the bitmap format. Thus, each pixel location in each of image files136aand136bcontains one-byte of data indicative of the gradient values computed. At step232, all values in image files136aand136bare initialized to zero. Therefore, any pixel location without significant gradient will appear as black color in the x-Gradient or y-Gradient image files.

At step234, gradient calculation process106begins a loop to step through all rows of pixel values in resized image132except the bottommost and topmost rows of pixels. At each row, step236begins a loop to step through all columns of pixel values in resized image132except the leftmost and the rightmost columns. Gradient calculation are not carried at the perimeter of resized image132because, by definition, there is no image gradient at these perimeter pixel locations.

At step238, the current pixel is selected. The gradient value in the vertical direction (y-Grad) for the current pixel is computed (step240). A gradient value is computed for each of the color components (red, green and blue) of the current pixel. In the present embodiment, the gradient value is computed based on the pixel values of the two neighboring pixels of the current pixel. The following equation is used to compute the gradient value in the vertical direction:Gy⁡(x,y)=I⁡(x,y+1)-I⁡(x,y-1)2,Eq.  (1)
where Gy(x,y) is the y-Grad value for the current pixel having a coordinate of (x,y), and I(x,y) represents the pixel value for a specific color at a coordinate of (x,y). Thus, to compute the y-Grad value, the pixel values for the pixel above and the pixel below the current pixel are used. Referring to Equation (1), the gradient value thus computed is a signed value. Specifically, a positive gradient value results if the change is from a lighter color to a darker color (e.g., from white to black) from top to bottom. Meanwhile, a negative gradient value results if the change is from a darker color to a lighter color (e.g., from black to white) from top to bottom. Therefore, the sign of the gradient value can be used to indicate the direction of the color change in the image.

At step240, Equation (1) is used to compute y-Grad values for the red, green and blue color components of the current pixel. The largest gradient value among the three color gradient values is selected as the y-Grad value (step242). In the present embodiment, the largest gradient value is obtained by comparing the absolute value of the three color gradient values.

Gradient calculation process106then proceeds to compute the horizontal gradient value (x-Grad) for the current pixel (step244). Similar to step240, a gradient value is computed for each of the color components (red, green and blue) of the current pixel. The following equation is used to compute the gradient value in the horizontal direction:Gx⁡(x,y)=I⁡(x+1,y)-I⁡(x-1,y)2,Eq.  (2)
where Gx(x,y) is the x-Grad value for the current pixel having a coordinate of (x,y), and I(x,y) represents the pixel value for a specific color at a coordinate of (x,y). To compute the x-Grad value, the pixel values for the pixel to the right and to the left of the current pixel are used. Similar to the y-Grad value, the x-Grad value is a signed value where a positive gradient value indicates changes from a lighter color area to a darker color area from right to left. A negative gradient value indicates changes from a darker color area to a lighter color area from right to left.

At step244, Equation (2) is used to compute x-Grad values for the red, green and blue color components of the current pixel. The largest gradient value among the three color gradient values is selected as the x-Grad value (step246). In the present embodiment, the largest gradient value is obtained by comparing the absolute value of the three color gradient values.

While the current pixel can have image gradient in both the horizontal and vertical direction, process106selects the stronger gradient value in either one of the two directions as the correct gradient orientation for the current pixel (step248). In the present embodiment, the selection process is as follows. If the absolute value of the x-Grad value is greater than the absolute value of the y-Grad value, then the x-Grad value is selected and the y-Grad value is set to zero. On the other hand, if the absolute value of the x-Grad value is less than the absolute value of the y-Grad value, then the y-Grad value is selected and the x-Grad value is set to zero.

As described above, large gradient values occur at the boundaries of an image area and the background area and also occur frequently within an image area. Process106uses the segmentation information obtained in process104advantageously to discard gradient values that are within an image area and thus do not contribute to the detection of the image area boundaries. At step250, process106determines if the current pixel is in or near the background area region as defined by the segmentation result in gray-scale image file134. In the present embodiment, a pixel is “in or near” the background area region if the pixel is in the background area region of image file134or if the pixel is in the image area region of image file134but is only one pixel away from the background area region. In one embodiment, step250is implemented by extracting the segmentation results of an 3×3 neighborhood of pixels surrounding the current pixel. If any one of the pixels in the 3×3 neighborhood of pixels is white (i.e., segmentation result is 255), then the current pixel is considered to be “near” the background area region. If none of the pixels in the 3×3 neighborhood of pixels is white, the current pixel is not in or near the background area region. Therefore, the gradient value computed for the current pixel is discarded and process106continues at step256.

If the current pixel is in or near the background area region, then process106continues to step252where the selected gradient value (either x-Grad or y-Grad) is compared with a threshold value. The threshold value is selected so that only significant gradient information is stored. Step252operates to eliminate small gradient values resulted from minor image texture or color changes. In the present embodiment, a threshold value of 12 (in terms of an 8-bit pixel intensity value) is used. By applying a threshold value in the gradient calculation process, process106can effectively eliminate false image edges and retain most of the true image edges associated with the boundaries of image areas and the background area.

If the selected gradient value is greater than the threshold value, the selected gradient value (either x-Grad or y-Grad) is stored in the respective x-Gradient or y-Gradient image file (step254). Otherwise, the gradient value is not stored.

Process106continues with the next pixel in the next column of the current row of pixels (step256). If all the pixels in the current row has been processed, process106continues with the next pixel in the next row (step258) until all the pixels, except those at the perimeters, in resized image132have been processed.

Gradient Calculation process106generates x-Gradient image file136acontaining the horizontal gradient information and y-Gradient image file136bcontaining the vertical gradient information.FIGS. 9aand9billustrate the x-Gradient image file and the y-Gradient image file corresponding to the resized image of FIG.5. As described above, horizontal gradient information is evidence of vertical image edges while vertical gradient information is evidence of horizontal image edges. Thus, inFIG. 9a, the x-gradient values result in vertical lines indicative of vertical image edges between the image areas and the background area. On the other hand, inFIG. 9b, the y-gradient values result in horizontal lines indicative of horizontal image edges between the image areas and the background area. The vertical and horizontal gradient values computed in gradient calculation process106are strong evidence of boundaries between image areas and the background area.

As shown inFIGS. 9aand9b, each pixel location in resized image132is represented either by a vertical edge (white color inFIG. 9a) or a horizontal edge (white color inFIG. 9b) or an non-edge (black color inFIGS. 9aand9b). Also, the brightness level of the image edges inFIGS. 9aand9bindicates the direction of the image gradient. Recall that the gradient value is a signed value. A positive value indicates a gradient from a light color (e.g. the background) to a dark color (e.g. an image area) from top to bottom or from right to left. A negative value indicates a gradient from a dark color (e.g. an image area) to a light color (e.g. the background) from top to bottom or from right to left. Because images inFIGS. 9aand9bdisplay the absolute value of the gradient values, absolute values of negative gradient values are generally greater than positive gradient values and thus appear brighter inFIGS. 9aand9b. Therefore, the bright edges inFIGS. 9aand9brepresent the bottom or left boundaries of the image areas while the darker edges represent the top or right boundaries of the image areas.

Stroke Detection

Returning again toFIG. 3, after gradient calculation process106, method100proceeds to stroke detection process108. Stroke detection process108operates to define a set of strokes based on the gradient information computed in process106. The strokes thus defined represent the boundaries between the image areas and the background area in resized image132.

As described above, a stroke is a line segment with a start point and an end point. The start point and end point are expressed as coordinates of pixel locations in resized image132. A further constraint is imposed on the definition of a stroke to ensure that all strokes conform to the same orientation. Thus, in the present description, a stroke is defined such that when viewed from the start point to the end point, pixel locations on the left side of a stroke are located in an image area region while pixel locations on the right side of the stroke are located in the background area region. Thus, when a number of strokes traces the boundary of an image area, the strokes will be aligned in a counter-clockwise direction.

Referring toFIGS. 9aand9b, the gradient values provide evidence of image edges in resized image132. However, these image edges formed many disjointed regions. For example, in the dotted-line box260inFIG. 9a, the gradient values computed include several disjointed edge areas. These individual edge areas actually form the left boundary of image area12containing a photograph. Stroke detection process108operates to detect these disjointed edge areas and group the appropriate edge areas into a line segment. A stroke thus formed is indicative of a boundary between an image area and the background. A set of strokes thus defined are used in subsequent steps for defining an image area rectangle surrounding each image area.

FIG. 10is a flowchart illustrating the stroke detection process of the image area detection method according to one embodiment of the present invention. Referring toFIG. 10, at step302, an 1-bit image file in bitmap format, called pFlag image file, is created. pFlag image file is the same size as resized image132. pFlag image file is used to store a flag, referred herein as pFlag, for identifying whether a particular pixel in resized image132has been traced. The tracing operation will be explained in more detail below. In the present embodiment, pFlag has a value of “1” if the pixel has been traced and a value of “0” if the pixel has not yet been traced. At step304, the pFlag image file is initialized to zero, indicating that all the pixels have not been traced.

At step306, stroke detection process108begins a loop from the bottom-left pixel, having coordinate (0,0) in bitmap format, to the top-right pixel, having coordinate (xmax, ymax) which is (281,389) in the present embodiment. At step308, the current pixel is selected.

At step309, process108determines whether the current pixel has already been traced by accessing the corresponding pFlag in the pFlag image file. If the current pixel has been traced, then the subsequent steps are skipped and process108proceeds to select the next pixel as current pixel (step324). If the current pixel has not been traced, process108proceeds to step310where the y-Grad value for the current pixel is retrieved and determined if the y-Grad value is non-zero. In stroke detection process108, only pixel locations with non-zero gradient values are of interest for stroke formation because these are the pixel locations of potential boundaries. A zero gradient value (shown as black areas inFIGS. 9aand9b) represents an non-edge pixel location and thus has no relevancy in the stroke formation process. If the current pixel has a zero y-gradient value, process108proceeds to determine if the current pixel has a non-zero x-Grad value (step314). If both the x-Grad and the y-Grad values are zero, the current pixel is an non-edge pixel and process108proceeds to the next pixel (step324).

Recall that in the gradient calculation process, a non-zero gradient pixel either has an x-gradient value or a y-gradient value but not both. So when the current pixel has a non-zero gradient value, process108will either continue at step312to trace a region defining a horizontal stroke (non-zero y-gradient) or continue at step316to trace a region defining a vertical stroke (non-zero x-gradient). As a result of steps310and314, only pixels with non-zero gradient values inFIGS. 9aand9bare subjected to tracing.FIG. 15is an image of the pFlag image file illustrating the pixel locations which have been traced in stroke detection process108. As shown inFIG. 15, only the vertical and horizontal edges inFIGS. 9aand9bare traced.

Steps312and316use the same Trace Region process330illustrated by the flowchart in FIG.11. The operation of Trace Region process330will be described in more detail below. For the purpose of the present description, it is sufficed to state that the Trace Region process generates as output definition of a cluster of pixels, also referred to as a “region” of pixels, having the same gradient direction The cluster of pixels is indicative of a potential stroke and is typically in the shape of a line segment.

After the Trace Region process (step312or316), the area of the region of pixels is computed and compared with an area threshold value (step318). The area threshold value is applied to eliminate fractional regions that are too small to constitute a meaningful stroke. In the present embodiment, an area threshold of 16 pixels is used. If the region of pixels is not greater than the area threshold, process108proceeds to the next pixel (step324).

If the region of pixels identified by the Trace Region process is large enough, then a Stroke Fitting process320is performed to fit a line through the region of pixels. The Stroke Fitting process320is illustrated in the flow chart in FIG.14and will be described in more detail below. The Stroke Fitting process320generates the definition for a stroke including pixel coordinates of the start and end points. The stroke definition is stored in a stroke queue (step322). Process108then proceeds to repeat steps308to322on the next pixel (step324).

After the completion of the loop (steps306to324), process108has operated on all of the pixels in resized image132and has formed a list of strokes delimiting boundaries of image areas and background area.FIG. 16is an image illustrating the multiple strokes detected and defined by stroke detection process108. Note that even though the strokes appear to be connected inFIG. 16, this is merely an artifact of the illustrated image. The strokes inFIG. 16may not be connected to each other. For example, at the top right corner, two strokes (stroke1and stroke2) are defined and are disjointed from each other.FIG. 16merely illustrates that strokes indicative of boundaries in resized image132have been successfully defined.

Returning toFIG. 10, a step326is performed to sort the list of strokes. In the present embodiment, the strokes are sorted by length so that the longest stroke is listed before the shorter strokes. As will become apparent in the description below, the sorting step is performed to enhance the efficiency of a subsequent depth-first searching step because the longer strokes are more likely candidates for forming correct image area rectangles.

Attention will now turn to the Trace Region process and the stroke fitting process used in stroke detection process108.

Stroke Detection—Trace Region

FIG. 11is a flowchart illustrating the Trace Region process according to one embodiment of the present invention. Trace Region process330operates on a current pixel which has been identified as having a non-zero gradient value either in the horizontal or the vertical direction. In the follow description, the gradient values refer to the gradient values in a direction in which the current pixel has a non-zero value. For example, when the current pixel has a non-zero gradient value in the horizontal direction (x-gradient), then all gradient values referred to in the Trace Region process are gradient values in the horizontal direction.

At step332, the current pixel is set as the starting point of the tracing operation. At step334, a data structure “Region” is initialized. Data Structure Region will be used to store the pixel locations which are to be grouped in one cluster by the Trace Region process330.

At step336, the sign of the gradient value of the current pixel is retrieved. The sign is either positive (denoted as “1” in the present embodiment) or negative (denoted as “−1” in the present embodiment). Then Trace Region process330proceeds to trace a scan line for defining the first scanline of the Region (step338). Step338uses a Trace a ScanLine process360illustrated in FIG.12. In the present description, a scanline is defined as a line in a row of pixels having a starting coordinate x1and an end coordinate x2. In the present embodiment, a Region is defined by one or more scanlines. Thus, the cluster of pixels forming a Region is defined by a one or more of adjacent scanlines of various length.

Referring toFIG. 12which is a flowchart illustrating Trace a ScanLine process360according to one embodiment of the present invention, process360starts by tracing the pixel to the left of the current pixel (step362). The sign of the gradient value for the left pixel is retrieved and compared with the sign of the current pixel (step364). Note that the left pixel can have a sign of +1, −1 or 0 (if the gradient value is zero). If the left pixel has the same sign as the current pixel, process360repeats step362to trace another pixel to the left of the previously traced pixel. The tracing process continues so as to capture all of the pixels to the left of the current pixel that have the same gradient sign as the current pixel. When the tracing process encounters a pixel to the left that does not have the same sign, process360proceeds to trace pixels to the right of the current pixel (step366). The sign of the gradient value of the pixel to the right of the current pixel is retrieved and compared with the sign of the current pixel (step368). If the sign is the same, the tracing process continues to the right until a pixel with a different sign is encountered. As a result, a scanline consisting of the leftmost to the rightmost pixels with the same sign as the current pixel is defined (step370).

Returning toFIG. 11, Trace a ScanLine process360is used to trace the first scanline for the current pixel (step338). The pixel locations on the scanline are marked as traced by setting the corresponding pFlag in the pFlag image files as described above (step340). The scanline is then added to the Region (step342). Having defined the first scanline on which the current pixel lies, Trace Region process330begins a loop operation (steps344to352) for tracing rows above and below the first scanline so that a cluster of pixels having the same gradient sign can be grouped into the same Region. In fact, the loop operation (steps344to352) in process330is an iterative process where each time a new scanline is traced and added to the Region, that new scanline will be subjected to the loop operation so as to trace even more rows above and below the new scanline to determine if additional rows should be included in the cluster of pixels.

Referring toFIG. 11, step344begins a loop for all scanlines defined in the Region. At step346, a current scanline is selected. Then, a Trace Down step348is carried out followed by a Trace Up step350. Trace Down step348and Trace Up step350can both potentially define and add more scanlines in the Region. If so, the loop operation will continue with the next scanline (step352) until all of the scanlines have been traced up and down once.

Trace Down step348and Trace Up step350both use a Trace Up/Down process372illustrated in the flowchart of FIG.13. Referring toFIG. 13, at step374, Trace Up/Down process372starts by selecting a pixel either one row up or down from the start coordinate x1of the current scan line. The sign of the gradient value of that pixel is retrieved (step376). Process372then determines whether the pixel has been traced by checking the pFlag and whether the pixel has the same sign as the current pixel (step378). Note that the sign of the current pixel is determined in step336of Trace Region process330(FIG.11). If the pixel has either been traced already or does not have the same gradient sign, Trace Up/Down process372terminates. On the other hand, if the pixel has not been traced and has the same sign as the current pixel, Trace Up/Down process372proceeds to trace a scan line (step380) using Trace a ScanLine process360of FIG.12. After a scanline is defined, the pixels associated with the scanline are marked as traced by setting the corresponding pFlag in the pFlag image file (step382). The new scanline is then added to the Region (step384).

In summary, Trace Region process330operates to define a cluster of pixels having the same gradient sign. The cluster of pixels forms a Region which is subsequently used by Stroke Fitting process320for forming a stroke defined by the cluster of pixels.

FIG. 14is a flowchart illustrating the Stroke Fitting process according to one embodiment of the present invention. The basic operation of Stroke Fitting process320is to fit a line segment to the cluster of pixels (the Region) defined in the Trace Region step (step312or316) of stroke detection process108. Stroke Fitting process320starts by selecting a current region to be fitted (step390).

Any techniques for fitting a set of data points to a straight line, referred to as linear regression, can be used in the Stroke Fitting process of the present invention. In the present embodiment, a least mean square linear regression algorithm is used to fit the cluster of pixels to a stroke. Line fitting algorithms are generally described in “Numerical Recipes in C: The Art of Scientific Computing,” by Numeric Recipes Software, Cambridge University Press, 1992.

Furthermore, in accordance with the present embodiment, to improve the accuracy of the linear regression, the data points (the pixel locations) are weighted by the gradient values. Specifically, the gradient value (the weight) plays a role in defining the uncertainty measurement, σi, for ensuring that a good fit can be derived. Since a large gradient value is a strong indication of an edge, weighing the pixel locations with the corresponding gradient values can assure that pixel locations with large gradient values will contribute more to the line fitting computation while pixel locations with small gradient values will contribute less to the line fitting computation.

Thus, at step392, each pixel value in the cluster of pixels is weighted with its associated gradient value. Then, a line fitting process is performed to fit the cluster of pixels to a line (step394).

Having fitted a line through the Region, the start point and the end point of the stroke can be computed (step396). The start and end points of the stroke is defined based on the sign of the gradient value defining the current pixel. Note that the start point of a stroke is defined so that, when viewing from the start point to the end point, all the pixels on the left are dark colors. Thus, if a current pixel has a negative horizontal gradient value, the stroke would be a vertical stroke pointing downward since the dark region should be on the left of the start point.

In this manner, Stroke Fitting process320defines a stroke having a start point and an end point.

Stroke Merge

Referring again toFIG. 16illustrating the set of strokes defined for resized image132, stroke detection process108may yield strokes that are disjointed due to the content of the image areas. Thus, after the set of strokes is defined, a stroke merge process110(FIG. 3) is performed to attempt to merge as many of the strokes as possible using a set of constraints. Specifically, if two strokes are collinear and have start/end points which are sufficiently close, the two strokes are merged as one stroke.

FIGS. 17aand17bare flowcharts illustrating the stroke merge process of the image area detection method according to one embodiment of the present invention. Referring toFIG. 17a, at step400, the count of strokes is obtained. Then, at step402, a merged flag file for the stroke queue is created and the merged flag is initialized. The merged flag is used to indicate whether a stroke in the stroke queue has been merged.

At step404, stroke merge process110begins a loop on a stroke PS1which steps from the first stroke to the last stroke. At step406, stroke merge process110determines if stroke PS1has been merged already by checking the merged flag. If stroke PS1has been merged, process110continues to select the next stroke as stroke PS1(step438inFIG. 17b). If stroke PS1has not been merged, the coordinates of stroke PS1are retrieved (step408).

Then, stroke merge process110begins a second loop on a stroke PS2which steps from the stroke after the current PS1stroke to the last stroke (step410). That is, for every stroke PS1, stroke PS2steps through all other strokes following stroke PS1. Stroke PS2is checked to determine if it has been merged (step412). If stroke PS2has been merged, process110continues by selecting the next stroke PS2(step430). If stroke PS2has not been merged already, then stroke merge process110proceeds to determine if stroke PS2can be merged with stroke PS1.

At step416, stroke merge process110determines if strokes PS1and PS2are collinear. The process for determining collinearity is illustrated in FIG.18and will be described in more detail below. Basically, step416determines if stroke PS1and stroke PS2lie approximately on the same straight line. If stroke PS1and stroke PS2are not collinear, then process100selects the next stroke PS2(step430).

If stroke PS1and stroke PS2are determined to be collinear, stroke merge process110proceeds to determine if the start/end points of the two strokes are sufficiently close (steps418-428). If stroke PS1and stroke PS2are collinear, there are two possible configurations for the two strokes: either PS1is before PS2or PS1is after PS2. These two configurations are tested by steps418and424, respectively. The two stroke configurations are shown by the pictorial inserts adjacent steps418and424.

Referring to step418, process110determines if the end point of PS1is close to the start point of PS2. In the present embodiment, the closeness is measured by the distance between PS1end point and PS2start point. The distance has to be smaller than a predefined threshold. In one embodiment, a threshold of 4 pixels is used. Thus, the end point of PS1is close to the start point of PS2if these two points are separated by less than or equal to 4 pixels. If the end point of PS1is close to the start point of PS2, then the two strokes are merged (step420). The merging operation is carried out by setting the end point of stroke PS1to be the end point of PS2. The merged flag for stroke PS2is set (step422) so that stroke PS2can be taken out of the stroke merge process. Process110then proceeds to step432(FIG. 17b).

Step418tests the first PS1/PS2configuration. If strokes PS1, PS2fail the first configuration, process110continues by testing the second PS1/PS2configuration. Thus, at step424, process110determines if the start point of PS1is close to the end point of PS2. The same threshold applied above in step418can be applied here. Thus, the start point of PS1is close to the end point of PS2if the two points are separated by less than or equal to 4 pixels. If the two strokes are close, then PS1and PS2are merged (step426). In this case, the merging is carried out by setting the start point of PS1to be the start point of PS2. The merged flag for stroke PS2is set at step428. The process continues at step432(FIG. 17b).

If stroke PS1and stroke PS2are not sufficiently close (step424), process110continues by selecting the next stroke as stroke PS2(step430).

Referring now toFIG. 17b, after the loop on stroke PS2has stepped through all the relevant strokes, process110continues by determining if any merging has been carried out on stroke PS1(step432). If stroke PS1has been merged, then process110retains stroke PS1as the current PS1stroke (step434) and repeats steps410to430to determine if the newly merged stroke PS1can be merged with yet another stroke. If after the operation of the PS2loop, no merging has been carried out on stroke PS1, then the loop on stroke PS1advances to the next stroke in the stroke queue (step436). Steps404to438are repeated to determine if the new stroke PS1can be merged with another stroke in the stroke queue.

At the conclusion of step438, all the strokes have been processed and, if possible, merged. Stroke merge process110then proceeds with optional data structure administration steps. In the preset embodiment, a loop including steps440to446is used to step through the strokes in the stroke queue and remove any stroke which has been merged into another stroke (step444). The stroke queue can then be updated (step448) to include only strokes which have merged with other strokes and strokes which cannot be merged with any other strokes. Once again, the strokes are sorted in order by length (step450) with the longest stroke listed first.

FIG. 19is an image illustrating the set of strokes inFIG. 16after the stroke merge process.FIG. 19illustrates the updated list of strokes140. The stroke merge process is able to define longer strokes spanning substantially the entire length of each boundary in the resized image.

Discussion is now turned to the collinearity determination step416inFIG. 17a.FIG. 18is a flowchart illustrating the collinearity determination step according to one embodiment of the present invention. Referring toFIG. 18, at step452, the length of each of stroke PS1and stroke PS2is determined. At step454, stroke A is set to be the longer of stroke PS1and stroke PS2while stroke B is set to be the shorter of the two. Collinearity is then measured by extending the line segment of stroke A, the longer stroke, and computing the vertical distance from the start/end points of stroke B to the line segment representing stroke A. The computation is illustrated in the pictorial insert adjacent step456in FIG.18.

Collinearity exists if the vertical distance from both the start point and the end point of stroke B to stroke A is less than or equal to a threshold (steps456and458). In the present embodiment, a threshold of 1.5 to 2 pixels is used. If conditions in steps456and458are met, collinearity determination step416returns a value indicating that stroke PS1and PS2are collinear (step460). Otherwise, collinearity determination step416returns a value indicating that stroke PS1and PS2are not collinear (step462).

In this manner, collinearity of two strokes are determined to indicate whether the two strokes are candidate for merging.

Corner Detection

Returning toFIG. 3, method100has now defined a set of strokes and have refined the stroke definition by merging as many of the strokes as possible. Method100proceeds with a corner detection process112where a list of corners are defined. In the present description, corners are potential vertexes of the image area rectangle to be defined in method100.

In the present embodiment, a corner is defined as a pixel location where two strokes are perpendicular to each other, are oriented in a counter-clockwise manner and where a start point of one is sufficiently close to an end point of the other.FIG. 22illustrates two strokes PS1and PS2which are candidates for forming a corner. If strokes PS1and PS2meet the constraints stated above, an intersection of the two strokes is computed as a candidate corner. Because not all stroke intersections are reasonable corners, the corner detection process calculates a corner likelihood value for each intersection to determine if the stroke intersection should be considered as a real corner.

The counter-clockwise orientation constraint is related to the definition of a stroke used in the present embodiment. Recall that a stroke is defined so that when viewed from its start point to the end point, the left side is a potential image area and the right side is potential background area. Therefore, when a group of strokes forms an image area rectangle and encloses an image area, the strokes will line up in a counter-clockwise manner. For example, when a stroke A is in a vertical direction pointing upward, the left side of stroke A is a potential image area while the right side of stroke A is a potential background area. Thus, another stroke B which can be grouped with stroke A to form a rectangle should have its end point close to the start point of stroke A, or stroke B should have its start point close to the end point of stroke A. In either case, the orientation of the two strokes are in a counter-clockwise manner.

FIG. 20is a flowchart illustrating the corner detection process of the image area detection method according to one embodiment of the present invention. Referring toFIG. 20, corner detection process112begins with a first loop on a stroke PS1stepping through all the strokes in the updated stroke queue (step480). A stroke in the updated stroke queue is retrieved as stroke PS1(step482). Then, a second loop is established on a stroke PS2stepping through all the strokes in the updated stroke queue (step484). Process112first determines if stroke PS2is the same stroke as stroke PS1(step486). If so, process112skips to select another stroke for stroke PS2(step496). If strokes PS1and PS2are not the same, stroke PS2is retrieved from the updated stroke queue (step488).

At step490, stroke PS1and stroke PS2are tested to determine if the two strokes meet the perpendicular constraint. In the present embodiment, perpendicularity is determined by computing the angle between strokes PS1and PS2and then computing the cosine of the angle. The absolute value of the cosine of the angle between strokes PS1and PS2is compared with an angle threshold value to determine if the two strokes are perpendicular. The threshold value can be selected to be zero or near zero since cosine of a 90° angle is zero. In the present embodiment, a threshold value of 0.05 used. If the absolute value of the cosine of the angle be strokes PS1and PS2is less than the angle threshold, the two strokes are deemed perpendicular. Otherwise, the two strokes are not perpendicular and thus are not candidate for corner formation. Process112continues with selecting the next PS2stroke for corner detection (step496).

If stroke PS1and stroke PS2meet the perpendicular constraint, an intersection of the two strokes is calculated (step491). The coordinate of the pixel location of the intersection is derived. Then, process112continues by calculating the corner likelihood of the current intersection (step492). The corner likelihood calculation process is illustrated in the flowcharts inFIGS. 21aand21b. Details of the corner likelihood calculation process will be described below. In brief, the corner likelihood calculation process determines whether strokes PS1and PS2are in the correct orientation (counter-clockwise). If the two strokes are in the correct orientation, a corner likelihood value is computed based on the distance between the start/end points of the two strokes. In the present embodiment, the corner likelihood value is a value between 0 and 1.

At step494, process112determines if the corner likelihood value computed for strokes PS1and PS2is greater than a predefined threshold value. In the present embodiment, the threshold value is 0.75. Thus, an intersection with a corner likelihood of less than 0.75 is not considered a good candidate for a corner and the intersection is discarded. Process112then continues with the next PS2stroke (step496). If the corner likelihood value computed for strokes PS1and PS2is equal to or greater than the threshold value, the intersection computed in step491is considered to be a valid corner and the intersection is added to the list of corners (step495). In the present embodiment, the threshold value is selected to be a value not very close to the maximum likelihood value. This is because image content and noise may cause two strokes to be separated even when their intersection represents a corner. Therefore, the threshold value is selected to be more forgiving to include corners formed by strokes which meet the perpendicular and orientation constraints but are not very close to each other.

Process112continues by stepping through all the PS2strokes (step496). Then, process112selects the next PS1stroke (step498) and repeats steps482to496for the next PS1stroke until all of the strokes in the updated stroke queue have been processed.

Referring toFIG. 22, two strokes, PS1and PS2, meeting the constraints for a corner formation are shown. First, PS1and PS2are perpendicular to each other. Second, PS1and PS2are arranged in a counter-clockwise orientation. Third, the end point of PS1is sufficiently close to the start point of PS2. Therefore, an intersection, marked by an “X” inFIG. 22, of stroke PS1and stroke PS2is stored as a corner in the list of corners.

FIG. 23is an image depicting the result of the corner detection step operating on the merged strokes of FIG.19. InFIG. 23, a number of corners are defined. These corners are strong evidence of the vertexes of image areas in the resized image.

Discussion is now turned to the corner likelihood calculation process (step492of FIG.20).

Corner Detection—Corner Likelihood Calculation

FIGS. 21aand21bare flowcharts illustrating the corner likelihood calculation process according to one embodiment of the present invention. Corner likelihood calculation process492receives as input stroke PS1and stroke PS2which have been determined to be perpendicular. An intersection of the two strokes has also been computed. In accordance with the present embodiment, the corner detection process assumes that when two strokes are in the correct orientation (counter-clockwise manner), the two strokes are configured as shown in the pictorial insert inFIG. 21aadjacent step502. That is, it is assumed that stroke PS1is following by stroke PS2at the potential corner where the corner is formed near the end point of PS1and the start point of PS2.

Corner likelihood calculation process starts by testing whether strokes PS1and PS2are in the correct orientation using the stroke configuration given above. If the strokes are correctly oriented (i.e., in a counter-clockwise manner), a corner likelihood value based on the closeness of the start/end points of the two strokes is computed. Referring toFIG. 21a, steps500to530are used to test the stroke configuration. Finally, referring toFIG. 21b, steps532to546are used to compute the corner likelihood value.

Referring toFIG. 21a, at step500, process492calculates a distance Dist11which is the vertical distance from the start point of stroke PS1to stroke PS2. In the present embodiment, when a stroke is viewed from the start point to the end point, vertical distances on the left side of the stroke is given a positive value while vertical distances on the right side of the stroke is given a negative value. Thus, if strokes PS1and PS2are in the correct orientation as shown in the insert, distance Dist11should be a positive value. If Dist11is a negative value (step502), then stroke PS1is located on the right side of stroke PS2which does not result in a correct orientation. Thus, the corner likelihood value is set to zero (step504).

At step506, process492calculates a distance Dist12which is the vertical distance from the end point of stroke PS1to stroke PS2. Again, if distance Dist12is a negative value (step508), strokes PS1and PS2are not in the correction orientation and the corner likelihood value is set to zero (step510).

At step512, distance Dist11is compared with distance Dist12. If stroke PS1and stroke PS2are oriented in the correct sequence, distance Dist11should be greater than Dist12. Thus, if Dist11is less than Dist12, the strokes are not in the correct sequence and the corner likelihood value is set to zero (step514).

At step516, process492calculates a distance Dist21which is the vertical distance from the start point of stroke PS2to stroke PS1. If strokes PS1and PS2are in the correct orientation, then distance Dist21should be a positive value. If Dist21is a negative value (step518), then stroke PS2is located on the right side of stroke PS1which does not result in a correct orientation. Thus, the corner likelihood value is set to zero (step520).

At step522, process492calculates a distance Dist22which is the vertical distance from the end point of stroke PS2to stroke PS1. Again, if distance Dist22is a negative value (step524), then strokes PS1and PS2are not in the correction orientation and the corner likelihood value is set to zero (step526).

At step528, distance Dist21is compared with distance Dist22. If stroke PS1and stroke PS2are oriented in the correct sequence, the distance Dist21should be less than Dist22. Thus, if Dist21is greater than Dist22, the strokes are not in the correct sequence and the corner likelihood value is set to zero (step530).

In accordance with the present invention, in determining whether Dist11, Dist12, Dist21and Dist22(steps502,508,518and524) are each a negative value, the distance values are compared with a small negative threshold value. The use of a small negative threshold value instead of zero in these determination step ensures that only strokes which are not aligned in the correct orientation are discarded for corner formation purpose. Often, noise or image content in the resize image may cause an end point of one stroke to slightly exceed the start point of another stroke, resulting in a negative distance value, even though the two strokes are true corners of an image area.

Turning now toFIG. 21bfor the calculation of the corner likelihood value when strokes PS1and PS2are found to be in the correct orientation. At step532, a first likelihood value, likelihood1, is calculated as follows:Likelihood1=1-(Dist12Dist11).
At step534, a second likelihood value, likelihood2, is calculated as follows:Likelihood2=1-(Dist21Dist22).
Likelihood1and likelihood2values measure how close the start points and end points of strokes PS1and PS2are. The closer the respective start/end point pair, the larger the likelihood value. At step536, the corner likelihood value is chosen to be the minimum of likelihood1and likelihood2.

Because the corner likelihood value should be between 0 and 1, if the computed corner likelihood value is greater than 1 (step538), the corner likelihood value is set to 1 (step540). Also, if the computed corner likelihood value is less than 0 (step542), the corner likelihood value is set to 0 (step544). The corner likelihood value for stroke PS1and PS2is thus computed and the value is returned to corner detection process112for further processing (step546).

Rectangle Detection

Referring back toFIG. 3, having defined a list of strokes140and a list of corners142, method100now proceeds to construct image area rectangles using the strokes and corners as the building blocks. Each operation of rectangle detection step114detects one rectangle with the best likelihood value. When a rectangle is detected, the corners and strokes associated with that rectangle are removed from the respective lists. Specifically, when a rectangle is detected, all corners and strokes that lie on the perimeter of the rectangle and inside the rectangle are removed. Method100thus repeats step114until all image area rectangles are detected (step116). In one embodiment, all image area rectangles are detected when there are no more corners left in the list of corners.

In the present description, an image area rectangle is constructed by four or less corners and one or more strokes. Each side of the image area rectangle is constructed by one or more strokes. Using these guidelines, a set of corner configurations can be defined to cover all possible positions of corners for the formation of image area rectangles.FIG. 25illustrates several exemplary corner configurations. Rectangle580illustrates the numbering convention used in the present description. The four corners of a rectangle are referred to in a counter-clockwise manner starting from the lower left corner. Thus, a corner configuration is denoted as Config_xyzw where x is the corner position0, y is the corner position1, z is the corner position2and w is the corner position3. A value of “1” in a corner configuration indicates the presence of a corner at that position while a value of “0” indicates the lack of a corner.

FIG. 25illustrates three exemplary corner configurations. Rectangle582is a configuration with one corner only (denoted as Config_1000). Where a configuration has only one corner, the corner is always positioned at corner position0. Rectangle584is a configuration with three corners occupying corner positions0,1and3. Based on the order of the corners, two corner configurations can be defined for rectangle584. Config_1101adenotes a configuration where the corners are in the order of0-1-3. Config_1101bdenotes a configuration where the corners are in the order of0-3-1. Rectangle586is a configuration of four corners, denoted as Config_1111.

In the present embodiment, a set of 12 corner configurations is defined to cover all possible configurations of interest. The configurations are defined as follows:

Config_0000no matching corners;Config_1000one corner at position 0;Config_1100two corners at positions 0-1;Config_1010two corners at positions 0-2;Config_1001two corners at positions 0-3;Config_1110athree corners at positions 0-1-2;Config_1110bthree corners at positions 0-2-1;Config_1101athree corners at positions 0-1-3;Config_1101bthree corners at positions 0-3-1;Config_1011athree corners at positions 0-2-3;Config_1011bthree corners at positions 0-3-2; andConfig_1111four corners at positions 0-1-2-3.
The corner configurations defined above are used to construct hypothesis for a given corner so as to determine whether the corner can be used alone or in conjunction with other corners to form an image area rectangle.

To form an image area rectangle, strokes used to define the corners can be used to verify the validity of each rectangle. Specifically, each corner is constructed by an incoming stroke and an outgoing stroke. The convention used in the present embodiment to describe the incoming and outgoing strokes at each corner is given in FIG.26. For example, corner position0is formed by incoming stroke C4S1and outgoing stroke C4S2. This convention will be used in the following description.

FIG. 24is a flowchart illustrating the rectangle detection process of the image area detection method according to one embodiment of the present invention. Rectangle detection process114starts by selecting a corner from the list of corners142(step550). Then, process114initiates a depth-first search by going through all the corners in the corner list (step551) and generates a list of hypothesis for all possible corner configurations associated with the current corner. Depth-first searching is a well known technique for traversing graphs or trees. Specifically, depth-first search is any search algorithm which considers outgoing edges of a vertex before any neighbors of the vertex in the search. Description of the depth-first search technique can be found at www.nist.gov/dads/HTML/depthfirst.html and www1.ics.uci.edu/˜eppstein/161/960215.html.

In operation, process114takes the current corner and determines if the current corner fits any corner configuration defined in the set of corner configurations (step552). The determination is aided by information of the surrounding strokes. A 1D hypothesis is generated for corner configurations having one detected corner (step554).

Then, the depth-first search operates to determine if the current corner can be matched with another corner in the corner list to fit into a two-corner configuration in the set of corner configurations (step556). If so, a 2D hypothesis is generated for each fitted corner configurations having two detected corners (step558).

The depth-first search continues to determine if the current corner can be matched with two other corners in the corner list to fit into a three-corner configuration in the set of corner configurations (step560). If so, a 3D hypothesis is generated for each fitted corner configurations having three detected corners (step562).

Lastly, the depth-first search continues to determine if the current corner can be matched with three other corners in the corner list to fit into the four-corner configuration in the set of corner configurations (step564). If so, a 4D hypothesis is generated for the fitted corner configurations having four detected corners (step566).

It is important to note that in the construction of the 2D, 3D and 4D hypothesis, each higher level hypothesis is built on a lower level hypothesis. That is, process114operates by taking a given hypothesis (having less than four detected corners) and adding a new corner into the hypothesis. Process114then verifies if the new corner is compatible with the existing corners. In the present embodiment, the verification criteria are as follows:

(1) Incoming and outgoing strokes of the new corner should be consistent with the incoming and outgoing strokes of the existing corners. Consistency is determined by testing whether the corresponding strokes are collinear or whether the corresponding strokes are parallel. For example, referring toFIG. 26, assume that corner2is the new corner added and corners0and1are the existing corners, an incoming stroke C2S1of corner2should be collinear with an outgoing stroke C1S2of corner1. Also, the incoming stroke C2S1should be parallel with the incoming stroke C4S1of corner0.

(2) Strokes corresponding to the new corner should be in the correct spatial order with strokes corresponding to the existing corners. Using the same example above, incoming stroke C2S1should be the same stroke as outgoing stroke C1S2or stroke C2S1should follows C1S2. Stroke C2S1follows stroke C1S2when the start point of C2S1is near the end point of stroke C1S2.

After generating the 1D, 2D, 3D and 4D hypothesis where applicable in the depth-first search, rectangle detection process114proceeds to compute likelihood values for each hypothesis (step568). The likelihood value for each hypothesis is computed by identifying the strokes which fit along the perimeter of each hypothesis and computing the length of the strokes. The likelihood value is the total length of strokes which can be fitted on the perimeter of each corner configuration hypothesis. The longer the total stroke length, the larger is the likelihood value.

At step570, the hypothesis with the best likelihood value is selected. To ensure that the likelihood value is of sufficient strength, a likelihood threshold is applied (step572). Thus, the best likelihood value has to be greater than the likelihood threshold for the hypothesis to be valid. If the best likelihood value is less than the threshold, the hypothesis is not valid and the rectangle detection process terminates.

In the present embodiment, the likelihood value is normalized to a maximum value of 1. Therefore, the likelihood value is proportional to the total length of strokes which can be fitted to the hypothesis. A likelihood value of 0.5 represents a hypothesis where two sides of the image area rectangle can be fitted with strokes. Furthermore, in the present embodiment, a likelihood threshold of 0.48 is used. The threshold value is chosen so that a hypothesis is valid only if the hypothesis is fitted with strokes sufficient to delineate almost two sides of the image area rectangle.

If the best likelihood value is greater than the likelihood threshold, the hypothesis is deemed a valid rectangle. Process114then removes all the strokes and corners associated with the rectangle from the list of strokes and corners (step574). Specifically, strokes and corners lying on the perimeter of the rectangle and strokes and corners laying within the perimeter of the rectangle are removed. Then, the hypothesis is converted into an image area rectangle (step576). In the present embodiment, an image area rectangle is defined by the pixel locations of its four vertexes. Thus, rectangle detection process114outputs a set of coordinates identifying the vertexes of an image area rectangle. In this manner, an image area rectangle defining a binding box surrounding an image area is defined.

As described above with reference toFIG. 3, rectangle detection process114is repeated until all rectangles have been identified, that is, when all corners have been removed from the corner list.FIG. 27is an image illustrating the detected image area rectangles for resized image132. The image area rectangles are shown as white binding boxes surrounding each image area. In the present illustration, rectangle detection process114successfully and correctly identifies four image area rectangles surrounding the four image areas in resized image132.

Algorithm Cleanup

Returning toFIG. 3, after all the rectangles have been defined, method100performs an algorithm cleanup step118.FIG. 28is a flowchart illustrating the algorithm cleanup process of the image area detection method according to one embodiment of the present invention. The image area rectangles identified by the rectangle detection step are based on resized image132having lower image resolution. At step602, the image area rectangles are resized to the original resolution of digital image10. In the present embodiment, the image area rectangles are resized to the resolution of digital image10which has a size of 2261×3122 pixels.

Then, algorithm cleanup step118may perform an optional step of releasing the data structures used in method100(step604). The setup and release of data structures used in the method of the present invention depend on the implementation used and data structure setup and release are well known steps in software implementation.

Summary and Advantages

The image area detection method of the present invention has numerous applications in image processing. In general, the image detection method receives a digital image containing one or more image areas and operates to automatically detect image area rectangles for each image area. The list of the image area rectangles generated by the method of the present invention can be provided to any image editing tool for use in cropping the image areas. Conventional image editing tools which can utilize the list of image area rectangles generated by the method of the present invention include ArcSoft's PhotoStudio 2000, available from Arcsoft, Inc., and Adobe PhotoShop, available from Adobe System Incorporated.

The image area detection method of the present invention incorporates image processing techniques such as region segmentation, edge detection and spatial reasoning to generate reliable and accurate detection results. The image area detection method is very robust as shown by the detected rectangles result in FIG.27. The method is able to detect image areas which are slanted or not a perfect rectangle. Furthermore, the method is able to detect an image area even when the image area has the same background color as the background of the digital image and one or more of the boundaries of the image area are missing. InFIG. 27, the method of the present invention correctly identifies an image area rectangle for the business card even though only two sides of the business card are recognized in the digital image (see for example the stroke detection result in FIG.16). The image area detection method of the present invention achieves reliable and robust detection result not attainable using conventional techniques.

When used in conjunction with a scanner for scanning multiple images at each scan job, the method of the present invention can improve the performance of the scanner by allowing multiple image objects to be scanned at the same time and automatically detecting the multiple image objects subsequent to the scanning process.

The method of the present invention can be implemented either in software or in hardware. In one embodiment, the method is implemented as a dynamically linked library accessible by any conventional image editing software.

The above detailed descriptions are provided to illustrate specific embodiments of the present invention and are not intended to be limiting. Numerous modifications and variations within the scope of the present invention are possible. For example, while the flowcharts in the figures of the present invention illustrate certain process sequence. One of ordinary skill in the art, upon being apprised of the present invention, would know that some of the process sequence can be rearranged to achieve the same result. The process sequence in the flowcharts are illustrative only. The present invention is defined by the appended claims.