Patent US5214530A successfully refreshed from Google Patents.
Patent US6564082B2 successfully refreshed from Google Patents.
Patent US7330787B2 successfully refreshed from Google Patents.
US7330787B2
Expired / Lapsed
US
⏱️ 0.0 years remaining
System and method for abstracting and visualizing a route map
Assignee: Microsoft Technology Licensing LLC
•
Filing: 2004-12-06
•
Granted: 2008-02-12
•
Expires: 2024-12-06
Abstract
Abstract A system and method for making computer-generated maps includes a different scale factor for each road in a route. The scale factors are used to optimize the route map against a target function that considers factors such as the number of false intersections in the route and the number of roads falling below a minimum length threshold. A refinement technique such as simulated annealing is used to find a solution to the target function. Each road in the scaled map is rendered to provide a finished product having the appearance of a hand-drawn map. The finished product includes context roads that intersect the main route but are not part of the main route. Furthermore, the hand-drawn map is optimized to the characteristics of the viewport used to visualize the map.
Inventors
- 👤 Maneesh Agrawala
- 👤 Chris Stolte
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 12:42
CPC Classifications
G; G06; G06T; G06T17/00; G06T17/05; G01; G01C; G01C21/00; G01C21/26; G01C21/34; G01C21/36; G01C21/3667; G01C21/367; G01C21/3673; G06T11/00; G06T11/20; G06T11/26; G06T11/60; G06T11/65
Claims Analysis
Total Claims: 21
Claim 1
Independent Claim
252 words
A method of adding a cross street and a cross street label that is associated with said cross street to a route map having a main path, the method comprising: determining an intersection point at which said cross street intersects said main path; placing said cross street in said route map with a constraint that said cross street intersects said main path at a first test position that is randomly chosen from a segment of said main path that includes said intersection point; positioning said cross street label at a second test position within a predetermined area, said predetermined area including said intersection point; adjusting a length of said cross street so that said cross street passes under said cross street label and intersects said main path; perturbing said first or said second test position by an amount; obtaining a score of a function that is determined by a location of said cross street and said cross street label in said route map; repeating said perturbing and obtaining steps until said score reaches a threshold value or said perturbing and obtaining steps have been executed a predetermined number of times; wherein: said cross street and said cross street label is added to said route map when said score reaches said threshold value; and said cross street and said cross street label is not added to said route map when said perturbing, obtaining and determining steps have been executed said predetermined number of times and said score does not reach said threshold value.
Claim 2
Independent Claim
252 words
A method of adding a cross street and a cross street label that is associated with said cross street to a route map having a main path, the method comprising: determining an intersection point at which said cross street intersects said main path; placing said cross street in said route map with a constraint that said cross street intersects said main path at a first test position that is randomly chosen from a segment of said main path that includes said intersection point; positioning said cross street label at a second test position within a predetermined area, said predetermined area including said intersection point; adjusting a length of said cross street so that said cross street passes under said cross street label and intersects said main path; perturbing said first or said second test position by an amount; obtaining a score of a function that is determined by a location of said cross street and said cross street label in said route map; repeating said perturbing and obtaining steps until said score reaches a threshold value or said perturbing and obtaining steps have been executed a predetermined number of times; wherein: said cross street and said cross street label is added to said route map when said score reaches said threshold value; and said cross street and said cross street label is not added to said route map when said perturbing, obtaining and determining steps have been executed said predetermined number of times and said score does not reach said threshold value.
Claim 3
Dependent Claim
116 words
The method of claim 1 , wherein said function that is determined by a location of said cross street and said cross street label in said route map comprises: a first component that is determined by a distance between said first test position and said intersection point; a second component that is determined by a number of objects in said map that overlap said cross street or said cross street label; wherein an amount that an intersecting object contributes to said second component is weighted by a degree of overlap between said overlapping object and said cross street or said cross street label; and a third component that is determined by an amount of visual clutter.
Claim 4
Dependent Claim
57 words
The method of claim 2 wherein said amount of visual clutter is determined by: rendering a pixel based image of said route map; choosing a focus region in said pixel based image that includes said cross street; and convolving said focus region with a Gaussian kernel using a luminance value of each pixel in said focus region.
Claim 5
Dependent Claim
109 words
The method of claim 2 wherein said amount of visual clutter is determined by: rendering a pixel based image of said route map; choosing a focus region in said pixel based image that includes said cross street; computing an area for each object in said focus region; and weighting each computed area by (i), multiplying said area by an average luminance of the object that corresponds to the area and (ii), dividing said area by a distance between the object that corresponds to said area and a center of said focus region; wherein said amount of visual clutter is a sum of each weighted area in said focus region.
Claim 6
Dependent Claim
88 words
The method of claim 2 , said perturbing step further including an option to toggle said cross street between a hidden state and a visible state; wherein one of said option to toggle, perturbation of said first test position, and perturbation of said second position is randomly selected during said perturbing step; and said function that is determined by a location of said cross street and said cross street label includes a fourth component that serves as a penalty when said cross street is in said hidden state.
Claim 7
Independent Claim
258 words
A method of adding a set of cross streets and corresponding cross street labels to a route map having a main path, the method comprising: for each cross street in said set of cross streets and corresponding cross street labels: determining an intersection point at which said cross street intersects said main path; placing said cross street in said route map with a constraint that said cross street intersects said main path at a first test position that is randomly chosen from a segment of said main path that includes said intersection point; positioning said cross street label at a second test position within a predetermined area, said predetermined area including said intersection point; and adjusting a length of said cross street so that said cross street passes under said cross street label and intersects said main path; the method further comprising: perturbing a cross street randomly selected from said set of cross streets by adjusting said first or said second test position corresponding to said cross street by a random amount; obtaining a score of a function that is determined by a location of each cross street and corresponding cross street label in said set of cross streets and corresponding cross street labels; determining whether to accept a change made during said perturbing step based on said score of said function in accordance with a search algorithm; and repeating said perturbing, obtaining and determining steps until said score reaches a threshold value or said perturbing, obtaining and determining steps have been executed a predetermined number of times.
Claim 8
Independent Claim
258 words
A method of adding a set of cross streets and corresponding cross street labels to a route map having a main path, the method comprising: for each cross street in said set of cross streets and corresponding cross street labels: determining an intersection point at which said cross street intersects said main path; placing said cross street in said route map with a constraint that said cross street intersects said main path at a first test position that is randomly chosen from a segment of said main path that includes said intersection point; positioning said cross street label at a second test position within a predetermined area, said predetermined area including said intersection point; and adjusting a length of said cross street so that said cross street passes under said cross street label and intersects said main path; the method further comprising: perturbing a cross street randomly selected from said set of cross streets by adjusting said first or said second test position corresponding to said cross street by a random amount; obtaining a score of a function that is determined by a location of each cross street and corresponding cross street label in said set of cross streets and corresponding cross street labels; determining whether to accept a change made during said perturbing step based on said score of said function in accordance with a search algorithm; and repeating said perturbing, obtaining and determining steps until said score reaches a threshold value or said perturbing, obtaining and determining steps have been executed a predetermined number of times.
Claim 9
Dependent Claim
175 words
The method of claim 6 , wherein said function that is determined by a location of each cross street and corresponding cross street label in said set of cross streets and corresponding cross street labels comprises: a first component that is determined by a combination of a set of distances; each distance in said set of distances determined by a difference in a first test position, which is associated with a different cross street in said set of cross streets, and an intersection point that corresponds to said different cross street; a second component that is determined by a number of objects in said route map that overlap a cross street or cross street label in said set of cross streets and corresponding cross street labels; wherein an amount that an intersecting object contributes to said second component is weighted by a degree of overlap between said overlapping object and said cross street or said cross street label; and a third component that is determined by an amount of visual clutter in said route map.
Claim 10
Dependent Claim
45 words
The method of claim 7 wherein said amount of visual clutter is determined by: rendering a pixel based image of said route map; and convolving said pixel based image with a Guassian kernel using a luminance value of each pixel in said pixel based image.
Claim 11
Dependent Claim
97 words
The method of claim 7 wherein said amount of visual clutter is determined by: rendering a pixel based image of said route map; computing an area for each object in said pixel based image; and weighting each computed area by (i), multiplying said area by an average luminance of the object that corresponds to the area and (ii), dividing said area by a distance between the object that corresponds to said area and a center of said focus region; wherein said amount of visual clutter is a sum of each weighted area in said pixel based image.
Claim 12
Dependent Claim
101 words
The method of claim 6 , said perturbing step further including an option to toggle said cross street between a hidden state and a visible state; wherein one of (i) said option to toggle, (ii) perturbation of said first test position, and (iii) perturbation of said second position is randomly selected during said perturbing step; and said function that is determined by a location of each cross street and corresponding cross street label in said set of cross streets and corresponding cross street labels includes a fourth component that serves as a penalty for each cross street in a hidden state.
Claim 13
Dependent Claim
39 words
The method of claim 6 , wherein said search algorithm is selected from the group consisting of simulated annealing, adaptive simulated annealing, a Tabu search, A*, IDA*, a genetic algorithm, a greedy search, gradient descent, and a random walk.
Claim 14
Dependent Claim
266 words
A computer readable medium encoding a computer program of instructions for executing a computer process for adding a cross street and a cross street label that is associated with said cross street to a route map having a main path, said computer process comprising: determining an intersection point at which said cross street intersects said main path; placing said cross street in said route map with a constraint that said cross street intersects said main path at a first test position that is randomly chosen from a segment of said main path that includes said intersection point; positioning said cross street label at a second test position within a predetermined area, said predetermined area including said intersection point; adjusting a length of said cross street so that said cross street passes under said cross street label and intersects said main path; perturbing said first or said second test position by an amount; obtaining a score of a function that is determined by a location of said cross street and said cross street label in said route map; repeating said perturbing and obtaining steps until said score reaches a threshold value or said perturbing and obtaining steps have been executed a predetermined number of times; wherein: said cross street and said cross street label is added to said route map when said score reaches said threshold value; and said cross street and said cross street label is not added to said route map when said perturbing, obtaining and determining steps have been executed said predetermined number of times and said score does not reach said threshold value.
Claim 15
Dependent Claim
266 words
A computer readable medium encoding a computer program of instructions for executing a computer process for adding a cross street and a cross street label that is associated with said cross street to a route map having a main path, said computer process comprising: determining an intersection point at which said cross street intersects said main path; placing said cross street in said route map with a constraint that said cross street intersects said main path at a first test position that is randomly chosen from a segment of said main path that includes said intersection point; positioning said cross street label at a second test position within a predetermined area, said predetermined area including said intersection point; adjusting a length of said cross street so that said cross street passes under said cross street label and intersects said main path; perturbing said first or said second test position by an amount; obtaining a score of a function that is determined by a location of said cross street and said cross street label in said route map; repeating said perturbing and obtaining steps until said score reaches a threshold value or said perturbing and obtaining steps have been executed a predetermined number of times; wherein: said cross street and said cross street label is added to said route map when said score reaches said threshold value; and said cross street and said cross street label is not added to said route map when said perturbing, obtaining and determining steps have been executed said predetermined number of times and said score does not reach said threshold value.
Claim 16
Dependent Claim
115 words
The medium of claim 12 wherein said function that is determined by a location of said cross street and said cross street label in said route map comprises: a first component that is determined by a distance between said first test position and said intersection point; a second component that is determined by a number of objects in said map that overlap said cross street or said cross street label; wherein an amount that an intersecting object contributes to said second component is weighted by a degree of overlap between said overlapping object and said cross street or said cross street label; and a third component that is determined by an amount of visual clutter.
Claim 17
Dependent Claim
57 words
The medium of claim 13 wherein said amount of visual clutter is determined by: rendering a pixel based image of said route map; choosing a focus region in said pixel based image that includes said cross street; and convolving said focus region with a Gaussian kernel using a luminance value of each pixel in said focus region.
Claim 18
Dependent Claim
109 words
The medium of claim 13 wherein said amount of visual clutter is determined by: rendering a pixel based image of said route map; choosing a focus region in said pixel based image that includes said cross street; computing an area for each object in said focus region; and weighting each computed area by (i), multiplying said area by an average luminance of the object that corresponds to the area and (ii), dividing said area by a distance between the object that corresponds to said area and a center of said focus region; wherein said amount of visual clutter is a sum of each weighted area in said focus region.
Claim 19
Dependent Claim
88 words
The medium of claim 13 , said perturbing step further including an option to toggle said cross street between a hidden state and a visible state; wherein one of said option to toggle, perturbation of said first test position, and perturbation of said second position is randomly selected during said perturbing step; and said function that is determined by a location of said cross street and said cross street label includes a fourth component that serves as a penalty when said cross street is in said hidden state.
Claim 20
Independent Claim
278 words
A system comprising: a processor; and a memory coupled with and readable by the processor and containing a series of instructions that, when executed by the processor, cause the processor to add a cross street and a cross street label that is associated with said cross street to a route map having a main path by: determining an intersection point at which said cross street intersects said main path; placing said cross street in said route map with a constraint that said cross street intersects said main path at a first test position that is randomly chosen from a segment of said main path that includes said intersection point; positioning said cross street label at a second test position within a predetermined area, said predetermined area including said intersection point; adjusting a length of said cross street so that said cross street passes under said cross street label and intersects said main path; perturbing said first or said second test position by an amount; obtaining a score of a function that is determined by a location of said cross street and said cross street label in said route map; repeating said perturbing and obtaining steps until said score reaches a threshold value or said perturbing and obtaining steps have been executed a predetermined number of times; wherein: said cross street and said cross street label is added to said route map when said score reaches said threshold value; and said cross street and said cross street label is not added to said route map when said perturbing, obtaining and determining steps have been executed said predetermined number of times and said score does not reach said threshold value.
Claim 21
Independent Claim
278 words
A system comprising: a processor; and a memory coupled with and readable by the processor and containing a series of instructions that, when executed by the processor, cause the processor to add a cross street and a cross street label that is associated with said cross street to a route map having a main path by: determining an intersection point at which said cross street intersects said main path; placing said cross street in said route map with a constraint that said cross street intersects said main path at a first test position that is randomly chosen from a segment of said main path that includes said intersection point; positioning said cross street label at a second test position within a predetermined area, said predetermined area including said intersection point; adjusting a length of said cross street so that said cross street passes under said cross street label and intersects said main path; perturbing said first or said second test position by an amount; obtaining a score of a function that is determined by a location of said cross street and said cross street label in said route map; repeating said perturbing and obtaining steps until said score reaches a threshold value or said perturbing and obtaining steps have been executed a predetermined number of times; wherein: said cross street and said cross street label is added to said route map when said score reaches said threshold value; and said cross street and said cross street label is not added to said route map when said perturbing, obtaining and determining steps have been executed said predetermined number of times and said score does not reach said threshold value.
References Cited (Backward Citations)
US5689717A
Cited
US6067502A
Cited
US6202026B1
Cited
US6154219A
Cited
US6565610B1
Cited
US6424911B2
Cited
WO2001071484A1
Cited
EP1266282A1
Cited
US20050149303A1
Cited
US20050182604A1
Cited
US20050182605A1
Cited
US7076409B2
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2011-02-11 | 2011-08-13 | 2012-02-12 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2015-02-11 | 2015-08-13 | 2016-02-12 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2019-02-11 | 2019-08-13 | 2020-02-12 | $7700.00 | Window Closed / Lapsed |