Rectilinear object image matcher
AssigneeHughes Aircraft Company
InventorsArthur F. Griffin, Caesar P. Ancheta
Life of this patent
Estimating the term…
Abstract
A process for extracting the precise perimeter of buildings from down-looking terrain images. The process works for any rectilinear building shape, and no restrictions are placed on the orientation or scale of the buildings within an image. The process has the advantages of robustness and execution speed. The process is robust in that it can extract building perimeters from a digitized image in the presence of multiple noise sources. The execution speed is proportional to N+M, where the size of the image is N by M pixels.
Claims30
A method for extracting the perimeters of buildings from a down-looking terrain image comprising N.times.M pixels in a rectilinear pixel grid, comprising a sequence of the following steps:
- processing said image to obtain building regions which are candidates for buildings and provide a binary image representation wherein pixels comprising said building regions have a value of one and pixels not comprising said building regions have a value of zero;
- operating on said binary image representation to provide a list of x-y pixel coordinates of the contour of each candidate building region comprising said terrain image;
- aligning the principle axes of each building region contour with respect to the pixel grid of said binary image to provide a list of aligned building region contours;
- calculating vertical and horizontal edge direction histograms of said aligned building region contour list;
- using peaks in said edge histograms to hypothesize corner candidates of said building region pixel coordinate list;
- selecting different combinations of corner candidates, testing each combination as a valid perimeter by attempting to connect the corners of each combination to form a closed, continuous perimeter and discarding each combination which cannot be so connected;
- and
- selecting as the building perimeter that validated combination of corner candidates with the greatest number of corner candidates.
A method for extracting the perimeters of buildings from a down-looking terrain image comprising NxM pixels in a rectilinear pixel grid, comprising a sequence of the following steps:
- processing said image to obtain building regions which are candidates for buildings and provide a binary image representation wherein pixels comprising said building regions have a value of one and pixels not comprising said building regions have a value of zero;
- testing the vertical and horizontal dimensions of each building region against a set of prototype building dimensions, and judging a building region not to be a building if the dimensions of the region are too small or too large;
- operating on said binary image representation to provide a list of x-y pixel coordinates of the contour of each candidate building region comprising said terrain image;
- aligning the principle axes of each building region contour with respect to the pixel grid of said binary image to provide a list of aligned building region contours;
- calculating vertical and horizontal edge direction histograms of said aligned building region contour list;
- testing the peak concentration ratio of said histograms against preset threshold and judging said building region not to be a building if the ratio is less than said threshold;
- using peaks in said edge histograms to hypothesize corner candidates of said building region pixel coordinate list;
- selecting different combinations of corner candidates, testing each combination as a valid perimeter by attempting to connect the corners of each combination to form a closed, continuous perimeter and discarding each combination which cannot be so connected;
- and
- selecting as the building perimeter that validated combination of corner candidates with the greatest number of corner candidates.
A system for extracting the perimeters of buildings from a down-looking terrain image, comprising:
- means for digitizing said image to form an image representation comprising NxM pixels in a rectilinear pixel grid;
- an image processing means for processing said image representation, comprising:
- means for obtaining building regions which are candidates for buildings and providing a binary image representation wherein pixels comprising said building regions have a value of one and pixels not comprising said building regions have a value of zero;
- means for operating on said binary image representation to provide a list of x-y pixel coordinates of the contour of each candidate building region comprising said terrain image;
- means for aligning the principle axes of each building region contour with respect to the pixel grid of said binary image;
- means for calculating vertical and horizontal edge direction histograms of said aligned building region contour list;
- means employing peaks in said histograms for hypothesizing corner candidates of said building region pixel coordinates list;
- means for selecting different combinations of corner candidates, testing each combination as a valid perimeter by attempting to connect the corners of each combination to form a closed, continuous perimeter and discarding each combination which cannot be so connected;
- and
- means for selecting as the building perimeter that validated combination of corner candidates with the greatest number of corner candidates;
- means for displaying said selected building perimeter.
Dependencies are inferred from the claim text.