Methods for retrieving shapes and drawings

• US 7,583,272 B2
• Filed: 11/29/2005
• Issued: 09/01/2009
• Est. Priority Date: 11/29/2004
• Status: Active Grant

• Current Assignee: Purdue Research Foundation (The Trustees of Purdue University (d/b/a Purdue University))
• Original Assignee: Purdue Research Foundation (The Trustees of Purdue University (d/b/a Purdue University))
• Inventors: Ramani, Karthik, Pu, Jiantao
• Primary Examiner(s): Tung; Kee M
• Assistant Examiner(s): CRAWFORD, JACINTA M
• Application Number:
  US11/288,911
• Publication Number:
  US 20060114252A1
• Time in Patent Office: 1,372 Days
• Field of Search: 707/3, 345/418, 345/621, 345/622
• US Class Current: 345/621
• CPC Class Codes: G06F 16/532 Query formulation, e.g. graphical querying
• CPC Class Codes: G06F 30/00 Computer-aided design [CAD]
• CPC Class Codes: G06T 15/10 Geometric effects
• CPC Class Codes: G06T 19/00 Manipulating 3D models or images for computer graphics
• CPC Class Codes: G06V 10/478 Contour-based spectral representations or scale-space representations, e.g. by Fourier analysis, wavelet analysis or curvature scale-space [CSS]
• CPC Class Codes: G06V 10/752 Contour matching
• CPC Class Codes: G06V 20/647 by matching two-dimensional images to three-dimensional objects
• CPC Class Codes: G06V 30/422 Technical drawings; Geographical maps

Abstract

There are disclosed methods to provide stable pose determinations of various three dimensional shapes. Methods are also disclosed for determining multiple, unique drawing descriptors for two dimensional drawings, and for obtaining intermediate three dimensional representations of two dimensional drawings as one way to determine the descriptor. Methods are also disclosed to provide for searching of two dimensional drawings and three dimensional shapes using user-defined input, which may be a drawing or sketch. User interactivity is provided to further refine search results.

Claims

1. A method comprising:

conducting a search of a database comprising 2D or 3D representations of objects using at least one graphical input parameter, wherein said graphical input parameter is a 2D or a 3D representation of all or part of an object;

receiving a set of results from said search;

inputting a new graphical input parameter;

searching said set of results with respect to said new parameter; and

obtaining a subset of said results;

wherein said conducting a search comprises providing at least one two-dimensional drawing of an object to a computer system;

creating one or more descriptors for said at least one drawing, said descriptor being adapted for use in a search of two-dimensional drawings; and

further wherein said creating step includes expanding the at least one drawing to three dimensions to create a new 2.5D shape and representing the 2.5D shape as a spherical function and employing a spherical harmonic transformation, thereby obtaining a rotation invariant descriptor; and

wherein said drawing is oriented with respect to two axes in a plane, and wherein said expanding a drawing to three dimensions includes;

computing a bounding box aligned with said axes, said bounding box having a center and two diagonals, said diagonals having lengths that are either equal or unequal;

determining a sphere having as its center the center of said bounding box, said sphere further having a radius of half the longer of said diagonal lengths of said bounding box and having an equator plane that is coplanar with the plane of said drawing;

generating a set of rays in said equator plane that originate from said center of said sphere

and calculating the points of intersection between said rays and said drawing, said points being identified by coordinates, said rays having a unique angle;

calculating a spherical angle unique to each intersection point distributed along a ray, said spherical angle being the arctan of the distance to the intersection point from said center divided by said radius; and

lifting each intersection point out of said plane of said drawing by the spherical angle unique to said intersection point.

2. A method according to claim 1, wherein said bounding box has a first edge parallel to one of said axes and a second edge parallel to a second of said axes, the method further comprising:

normalizing one of said edges by a predetermined value.

3. A method according to claim 2, wherein said transformation is a fast spherical transformation, wherein a spherical function of bandwidth B is sampled on Chebyshev points.

4. A method, comprising:

conducting a search of a database comprising 2D or 3D representations of objects using at least one graphical input parameter, wherein said graphical input parameter is a 2D or a 3D representation of all or part of an object;

receiving a set of results from said search;

inputting a new graphical input parameter;

searching said set of results with respect to said new parameter; and

obtaining a subset of said results;

wherein said conducting a search comprises providing at least one two-dimensional drawing of an object to a computer system;

creating one or more descriptors for said at least one drawing, said descriptor being adapted for use in a search of two-dimensional drawings; and

further wherein said creating step includes expanding the at least one drawing to three dimensions to create a new 2.5D shape and representing the 2.5D shape as a spherical function and employing a spherical harmonic transformation, thereby obtaining a rotation invariant descriptor; and

wherein said creating step includes building a distance histogram for said drawing; and

wherein said building step includes transforming said drawing into a set of line segments;

sampling points from said segments to derive a shape distribution; and

wherein said sampling step includes summing the length of said segments to obtain a total length value generating a first random number between zero and said total length value;

finding the segment along whose length said first random number falls, said segment having a first endpoint with a first and second coordinate and a second endpoint with a first and second coordinate;

generating a second random number between zero and one, said second random number being a real number;

creating a sample point having first and second coordinates, said first coordinate of said sample point determined by multiplying the difference between the second coordinates of said endpoints by said second random number and adding the first coordinate of said first endpoint, and said second coordinate of said sample point determined by multiplying the difference between the second coordinates of said endpoints by said second random number and adding the second coordinate of said first endpoint.

5. A method, comprising:

conducting a search of a database comprising 2D or 3D representations of objects using at least one graphical input parameter, wherein said graphical input parameter is a 2D or a 3D representation of all or part of an object;

receiving a set of results from said search;

inputting a new graphical input parameter;

searching said set of results with respect to said new parameter; and

obtaining a subset of said results;

wherein said conducting a search comprises providing at least one two-dimensional drawing of an object to a computer system;

creating one or more descriptors for said at least one drawing, said descriptor being adapted for use in a search of two-dimensional drawings; and

further wherein said creating step includes expanding the at least one drawing to three dimensions to create a new 2.5D shape and representing the 2.5D shape as a spherical function and employing a spherical harmonic transformation, thereby obtaining a rotation invariant descriptor;

wherein said drawing is oriented with respect to two axes in a plane, and wherein said expanding a drawing to three dimensions includes;

computing a bounding box aligned with said axes, said bounding box having a center and two diagonals, said diagonals having lengths that are either equal or unequal;

determining a sphere having as its center the center of said bounding box, said sphere further having a radius of half the longer of said diagonal lengths of said bounding box and having an equator plane that is coplanar with the plane of said drawing;

generating a set of rays in said equator plane that originate from said center of said sphere

and calculating the points of intersection between said rays and said drawing, said points being identified by coordinates, said rays having a unique angle;

calculating a spherical angle unique to each intersection point distributed along a ray, said spherical angle being the arctan of the distance to the intersection point from said center divided by said radius; and

lifting each intersection point out of said plane of said drawing by the spherical angle unique to said intersection point;

wherein said bounding box has a first edge parallel to one of said axes and a second edge parallel to a second of said axes, the method further comprising;

normalizing one of said edges by a predetermined value;

wherein said transformation is a fast spherical transformation, wherein a spherical function of bandwidth B is sampled on Chebyshev points; and

further comprising;

defining a division number for the distance histogram, said division number identifying the number of parts of the distance histogram;

determining a standard value for normalization; and

calculating the distances between sample point pairs and counting the number of pairs in each part of the distance histogram.