Image analysis – Pattern recognition – Feature extraction
Reexamination Certificate
1998-02-27
2001-10-02
Johns, Andrew W. (Department: 2721)
Image analysis
Pattern recognition
Feature extraction
Reexamination Certificate
active
06298157
ABSTRACT:
CROSS REFERENCE TO RELATED APPLICATIONS
Not Applicable.
STATEMENT REGARDING FEDERALLY SPONSORED RESEARCH OR DEVELOPMENT
Not Applicable.
BACKGROUND OF THE INVENTION
The present invention relates to computer-implemented image processing to find embedded images within raster images.
A common application for scanners is to scan and digitize photographs. Often, the scanned and digitized photograph is smaller than the scanner image size, so it is embedded in a larger digitized image, from which the embedded photograph image will have to be extracted before it is used. Often, too, a photograph placed in a scanner will be tilted with respect to the scanning axes and so the digitized photograph will be somewhat misaligned, requiring that it be rotated as well as cropped from the larger image. The user is generally interested in removing any border around the digitized photograph and rotating the digitized photograph so that it is aligned with horizontal and vertical axes parallel to the edges of the photograph.
SUMMARY OF THE INVENTION
The apparatus and methods of the invention automate the task of locating a photograph or other image that is embedded within a larger image. The invention finds an edge curve that approximates the perimeter of the embedded image and from the edge curve calculates the rectangle of the embedded image or a rectangle covering the embedded image by processing density profiles of the edge curve taken along two axes. The invention can provide both location and orientation of an embedded image. It can provide the location of the four corners of a rectangular embedded image, which enables automatic cropping and rotation of the embedded image, even if fewer than all four corners are visible. It can provide a rectangle covering the image, including a rectangle aligned with the axes of a larger embedding image such as is created when scanning a small photograph on a flatbed scanner. The invention operates well on rectangular images, as well as on images having polygonal and other border shapes, such as circles and ellipses, including images with irregular shapes.
In general, in one aspect, the invention features apparatus for finding an image embedded in a larger image. The apparatus includes means for finding an edge curve of the embedded image in the larger image; means for calculating a rotation angle of the embedded image from the edge curve; and means for calculating from the edge curve a location and orientation of one or more line segments of a side of a rectangle bounding the embedded image in the larger image. Advantageous implementations of the invention include one or more of the following features. Where the embedded image is an image of a rectangular photograph, the apparatus includes means for locating edge segments in the edge curve corresponding to sides of the embedded image in the larger image. The apparatus includes means for locating corners of a covering rectangle of the embedded image. The apparatus includes means for cropping the embedded image in the frame of reference of the larger image. The means for finding an edge curve include means for calculating density profiles on two axes of the larger image; and means for detecting edge points. The apparatus includes means for removing pixel noise from the larger image.
In general, in another aspect, the invention features a method of processing a digital raster image embedded in a larger digital raster image. The method includes finding an edge curve of the embedded image in the larger image; calculating a rotation angle of the embedded image from the edge curve; and calculating from the edge curve a location and orientation of a line segment of a side of a rectangle bounding the embedded image in the larger image. Advantageous implementations of the invention include one or more of the following features. The method includes finding the edge curve by calculating the positions of edge points in the larger image, and scanning from the perimeter into the larger image from starting points on all sides of the larger image and selecting as a point in the edge curve the first edge point encounter from each starting point; calculating a rotation angle by calculating an average angle of the edge curve points over a windowed set of neighboring edge curve points; rotating the edge curve by the complement of the calculated rotation angle; and calculating the location of corners of a rectangle covering the embedded image. The method uses two axes that are perpendicular. The method includes calculating the positions of edge points by applying a Sobel filter to the larger image. The method includes calculating the positions of edge points by applying a Hough transform to the larger image. The method includes cropping the embedded image according the covering rectangle. The method includes removing pixel noise from the larger image before performing the step of finding an edge curve.
Among the advantages of the invention are one or more of the following. Applied to a rectangular embedded image, the invention does not need all four corners of the rectangle to be present in the larger image. The invention is insensitive to noise which may be present in the larger image or the embedded image. The invention can accurately locate the outer boundary of the edge of the embedded image. The invention provides a rotation angle, so the embedded image can be aligned. The invention can be applied to automate the process of scanning in images with flatbed scanners. The invention can be applied to determine whether a photograph is present in a larger image and, if present, where it is.
Other features and advantages of the invention will become apparent from the following description and from the claims.
REFERENCES:
patent: 4926490 (1990-05-01), Mano
patent: 5317689 (1994-05-01), Nack et al.
patent: 5452374 (1995-09-01), Cullen et al.
patent: 5748783 (1998-05-01), Rhoads
patent: 5834749 (1998-11-01), Durbin
patent: 6026186 (2000-02-01), Fan
patent: 0660256A2 (1995-06-01), None
patent: 0703696A2 (1996-03-01), None
patent: 0736999A2 (1996-10-01), None
Davies, E.R., “Machine Vision: Theory, Algorithms, Practicalities,” Academic Press, pp. 191-207, 241-301.
Adobe Systems Incorporated
Azarian Seyed
Fish & Richardson P.C.
Johns Andrew W.
LandOfFree
Locating and aligning embedded images does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Locating and aligning embedded images, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Locating and aligning embedded images will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2558660