Display method and apparatus for navigation system for performing cluster search of objects

• US 20050177303A1
• Filed: 02/05/2004
• Published: 08/11/2005
• Est. Priority Date: 02/05/2004
• Status: Active Grant

• Current Assignee: Alpine Electronics Incorporated (Alps Alpine Co., Ltd.)
• Original Assignee: Alpine Electronics Incorporated (Alps Alpine Co., Ltd.)
• Inventors: Han, Maung W.
• Granted Patent: US 7,353,109 B2
• Time in Patent Office: Days
• US Class Current: 701/209
• CPC Class Codes: G01C 21/36 Input/output arrangements for on-board computers
• CPC Class Codes: G01C 21/367 Details, e.g. road map scale, orientation, zooming, illumination, level of detail, scrolling of road map or positioning of current position marker
• CPC Class Codes: G01C 21/3682 output of POI information on a road map G01C21/3614, G01C21/3685 take precedence

Abstract

A method and apparatus for a navigation system conducts a data search for finding relative density of objects such as points of interest in a specified area and displays the result of the search in various manners. The display method includes the steps of: defining a size and shape of a search template; scanning the search template on the search area by displacing its position by a predetermined increment; counting and recording a number of objects on the search area within the search template at every increment of the displacement position, thereby creating an object distribution matrix; applying a cluster search algorithm to the object distribution matrix, thereby detecting distribution of clusters of the objects; and displaying the clusters of the objects in the search area.

Claims

1. A display method for a navigation system for searching and displaying objects clustered within a search area, comprising the following steps of:

defining a size and shape of a search template for searching objects in the search area;

scanning the search template on the search area by displacing its position by a predetermined increment;

counting and recording a number of objects on the search area within the search template at every increment of said displacement position, thereby creating an object distribution matrix;

applying a cluster search algorithm to the object distribution matrix, thereby detecting distribution of clusters of the objects in the search area; and

displaying the clusters of the objects in the search area by a predetermined display method.

2. A display method of clustered objects as defined in claim 1, wherein said objects are points of interest of a specified type within the search area.

3. A display method of clustered objects as defined in claim 1, wherein said predetermined increment for scanning the search template is smaller than the size of the search template so that an area on the search area covered by the search template is overlapped by consecutive increments of said displacement position.

4. A display method of clustered objects as defined in claim 1, wherein said cluster search algorithm includes the following step of:

finding numbers on the object distribution matrix that are larger than any neighboring numbers and recording the higher numbers;

temporarily masking the higher numbers on the object distribution matrix and erasing the neighboring numbers from the object distribution matrix;

repeating the above operations until any remaining numbers on the object distribution matrix become equal to or smaller than a predetermined value; and

erasing all the remaining numbers and recovering the masked numbers on the object distribution matrix, thereby obtaining distribution of the clusters of the object in the search area.

5. A display method of clustered objects as defined in claim 4, wherein said step of finding numbers on the object distribution matrix includes the following steps of:

selecting a number having a larger sum of neighboring numbers when a number larger than any neighboring numbers is not found; and

temporarily masking the selected number on the object distribution matrix and erasing the neighboring numbers from the object distribution matrix.

6. A display method of clustered objects as defined in claim 4, wherein said step of finding numbers on the object distribution matrix includes the following steps of:

selecting a number having a larger sum of neighboring numbers when a number larger than any neighboring numbers is not found;

temporarily masking the selected number on the object distribution matrix and erasing the neighboring numbers from the object distribution matrix;

picking one of the numbers having equal sums of neighboring numbers when a number having the larger sum of neighboring numbers is not found; and

temporarily masking the picked number on the object distribution matrix and erasing the neighboring numbers from the object distribution matrix.

7. A display method of clustered objects as defined in claim 1, wherein said search template has a square shape and a side length of the search template is larger than said predetermined increment of displacement by three times or more.

8. A display method of clustered objects as defined in claim 1, wherein said step of displaying the clusters of the objects in the search area includes a step of listing the clusters of objects in an order of cluster size where the cluster size is a number of the objects in a small portion in the search area.

9. A display method of clustered objects as defined in claim 1, wherein said step of displaying the clusters of the objects in the search area includes a step of listing the clusters of objects in an order of distance from a current user position.

10. A display method of clustered objects as defined in claim 1, wherein said step of displaying the clusters of the objects in the search area includes a step of listing names of the objects within a specified cluster thereby allowing the user to select one of the objects.

11. A display method of clustered objects as defined in claim 10, wherein said step of listing the names of the objects within the selected cluster includes a step of listing the names in an order of distance from an object at a center of the selected cluster or an alphabetical order of the names of the objects.

12. A display method of clustered objects as defined in claim 1, wherein said step of displaying the clusters of the objects in the search area includes a step of displaying a map image showing distribution of the objects within a selected cluster.

13. A display method of clustered objects as defined in claim 1, wherein said step of scanning the search template on the search area includes a step of moving the search template from one horizontal end to another horizontal end of the search area and vertically shifting to a next row, and repeating the above movements to cover all the search area to produce the object distribution matrix.

14. A display method of clustered objects as defined in claim 1, wherein said step of scanning the search template on the search area includes a step of moving the search template starting from a center of the search area and spirally moving the search template around the center toward an outer area of the search area.

15. A display method of clustered objects as defined in claim 14, wherein said step of applying said cluster search algorithm starts as soon as sufficient data of object distribution at a center portion of the search area is available without waiting for completing the scanning step for all of the search area.

16. A display apparatus for a navigation system for searching and displaying objects clustered within a search area, comprising:

means for defining a size and shape of a search template for searching objects in the search area;

means for scanning the search template on the search area by displacing its position by a predetermined increment;

means for counting and recording a number of objects on the search area within the search template at every increment of said displacement position, thereby creating an object distribution matrix;

means for applying a cluster search algorithm to the object distribution matrix, thereby detecting distribution of clusters of the objects in the search area; and

means for displaying the clusters of the objects in the search area by a predetermined display method.

17. A display apparatus of clustered objects as defined in claim 16, wherein said objects are points of interest of a specified type within the search area.

18. A display apparatus of clustered objects as defined in claim 16, wherein said predetermined increment for scanning the search template is smaller than the size of the search template so that an area on the search area covered by the search template is overlapped by consecutive increments of said displacement position.

19. A display apparatus of clustered objects as defined in claim 16, wherein said means for applying the cluster search algorithm includes:

means for finding numbers on the object distribution matrix that are larger than any neighboring numbers and recording the higher numbers;

means for temporarily masking the higher numbers on the object distribution matrix and erasing the neighboring numbers from the object distribution matrix;

means for repeating the above operations until any remaining numbers on the object distribution matrix become equal to or smaller than a predetermined value;

and

means for erasing all the remaining numbers and recovering the masked numbers on the object distribution matrix, thereby obtaining distribution of the clusters of the object in the search area.

20. A display apparatus of clustered objects as defined in claim 19, wherein said means for finding numbers on the object distribution matrix includes:

means for selecting a number having a larger sum of neighboring numbers when a number larger than any neighboring numbers is not found; and

means for temporarily masking the selected number on the object distribution matrix and erasing the neighboring numbers from the object distribution matrix.

21. A display apparatus of clustered objects as defined in claim 19, wherein said means for finding numbers on the object distribution matrix includes:

means for selecting a number having a larger sum of neighboring numbers when a number larger than any neighboring numbers is not found;

means for temporarily masking the selected number on the object distribution matrix and erasing the neighboring numbers from the object distribution matrix;

means for picking one of the numbers having equal sums of neighboring numbers when a number having the larger sum of neighboring numbers is not found; and

means for temporarily masking the picked number on the object distribution matrix and erasing the neighboring numbers from the object distribution matrix.

22. A display apparatus of clustered objects as defined in claim 16, wherein said search template has a square shape and a side length of the search template is larger than said predetermined increment of displacement by three times or more.

23. A display apparatus of clustered objects as defined in claim 16, wherein said means for displaying the clusters of the objects in the search area includes means for listing the clusters of objects in an order of cluster size where the cluster size is a number of the objects in a small portion in the search area.

24. A display apparatus of clustered objects as defined in claim 16, wherein said means for displaying the clusters of the objects in the search area includes means for listing the clusters of objects in an order of distance from a current user position.

25. A display apparatus of clustered objects as defined in claim 16, wherein said means for displaying the clusters of the objects in the search area includes means for listing names of the objects within a specified cluster thereby allowing the user to select one of the objects.

26. A display apparatus of clustered objects as defined in claim 25, wherein said means for listing the names of the objects within the selected cluster includes means for listing the names in an order of distance from an object at a center of the selected cluster or an alphabetical order of the names of the objects.

27. A display apparatus of clustered objects as defined in claim 16, wherein said means for displaying the clusters of the objects in the search area includes means for displaying a map image showing distribution of the objects within a selected cluster.

28. A display apparatus of clustered objects as defined in claim 16, wherein said means for scanning the search template on the search area includes means for moving the search template from one horizontal end to another horizontal end of the search area and vertically shifting to a next row, and repeating the above movements to cover all the search area to produce the object distribution matrix.

29. A display apparatus of clustered objects as defined in claim 16, wherein said means for scanning the search template on the search area includes means for moving the search template starting from a center of the search area and spirally moving the search template around the center toward an outer area of the search area.

30. A display apparatus of clustered objects as defined in claim 29, wherein said means for applying said cluster search algorithm starts as soon as sufficient data of object distribution at a center portion of the search area is available without waiting for completing the scanning step for all of the search area.