Methods for retrieving shapes and drawings

• US 20060114252A1
• Filed: 11/29/2005
• Published: 06/01/2006
• 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
• Granted Patent: US 7,583,272 B2
• Time in Patent Office: Days
• US Class Current: 345/419
• 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 of posing a computer-based representation of a three-dimensional shape, said representation being formed of multiple polygons, comprising:

calculating an area value of polygons having similar normals and signed distances;

associating a normal with the area value; and

selecting the normal with the maximum area value.

2. The method of claim 1, wherein said area value of the polygons is a continuous area.

3. The method of claim 1, wherein said area value is a virtual contact area.

4. The method of claim 1, further comprising orienting said representation so that one of said axis vectors is a vertical axis.

5. The method of claim 1, further comprising:

creating a two-dimensional projection of said representation along one of said axis vectors.

6. The method of claim 5, wherein said projection is one of a full view, a contour view and a silhouette view of said representation.

7. The method of claim 1, further comprising:

creating a first two-dimensional projection of said representation along a first of said axis vectors, creating a second two-dimensional projection of said representation along a second of said axis vectors, and creating a third two-dimensional projection of said representation along a third of said axis vectors.

8. A method comprising:

projecting a representation of a three-dimensional object into three two-dimensional drawings, said drawings including silhouette and contour views.

9. The method of claim 8, further comprising editing one or more of the two-dimensional drawings.

10. The method of claim 8, wherein said representation is used in a computer system for searching for representations similar to said representation.

11. A method comprising:

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.

12. The method of claim 11, 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.

13. The method of claim 12, 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.

14. The method of claim 13, 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.

15. The method of claim 12, wherein said transformation is a fast spherical transformation, wherein a spherical function of bandwidth B is sampled on Chebyshev points.

16. The method of claim 11, wherein said creating step includes building a distance histogram for said drawing.

17. The method of claim 16, wherein said building step includes

transforming said drawing into a set of line segments;

sampling points from said segments to derive a shape distribution.

18. The method of claim 17, 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 first 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.

19. The method of claim 18, wherein said steps of generating a first random number, finding the segment, generating a second random number, and creating a sample point are repeated at least once, thereby producing a plurality of sample points.

20. The method of claim 17, further comprising normalizing said drawing.

21. The method of claim 17, 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.

22. The method of claim 21, wherein said determining step includes calculating the maximum distance among all pairs of sampled points, and using said maximum distance as said standard value.

23. The method of claim 21, wherein said determining step includes calculating the average distance between all pairs of sampled points, and using said average distance as said standard value.

24. The method of claim 17, wherein said sampling incorporates a bias that emphasizes at least one particular part of said drawing.

25. A method comprising:

inputting a two-dimensional drawing into a computer system having access to a library of representations of objects;

creating one or more descriptors for said two-dimensional drawing;

searching said library of by comparing said one or more descriptors to data of said representations; and

outputting a set of representations of objects that are determined to be sufficiently similar to said two-dimensional drawing.

26. The method of claim 25, wherein said representations are two-dimensional representations of objects.

27. The method of claim 25, wherein said representations are three-dimensional representations of objects.

28. The method of claim 27, wherein said data includes one or more descriptors of one or more two-dimensional views of said representations.

29. The method of claim 28, wherein said creating step includes one of using a spherical transform to create said descriptors and using a histogram to create said descriptors.

30. The method of claim 28, wherein said descriptors of said views of said representations are predetermined and stored in said library.

31. The method of claim 28, wherein said descriptors of said views of said representations are calculated after said inputting step.

32. The method of claim 25, further comprising the step of editing said drawing after said inputting step.

33. The method of claim 25, further comprising:

entering at least one parameter after said outputting step,

searching said set of representations for representations having said parameter; and

outputting a subset of said set of representations.

34. The method of claim 33, wherein said parameter is a higher sensitivity of comparison between said one or more descriptors of said drawing and said one or more descriptors of said representations.

35. The method of claim 33, wherein said parameter is a desired feature of said representations.

36. A method comprising:

inputting a two-dimensional drawing into a computer system having access to a set of two-dimensional representations of objects;

measuring the similarity between said drawing and said representations, said measuring including randomly sampling view edges of said drawing and said representations, generating shape distributions of said drawing and said representations, normalizing said shape distributions, and ascertaining degrees of correspondence between said shape distributions.

37. The method of claim 36 wherein at least some of said two-dimensional representations are projected from three-dimensional representations of said objects.

38. A method comprising:

receiving a set of results from a search conducted using at least one input parameter;

inputting a new parameter;

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

obtaining a subset of said results.

39. A method comprising:

receiving a set of results from a search conducted using at least one input parameter;

altering said input parameter;

searching a set of results with respect to said altered parameter; and

obtaining a subset of said results.

40. The method of claim 39 wherein said altering step includes erasing features from said input parameter.

41. The method of claim 39 wherein said altering step includes adding features from said input parameter.