WO2004084437A1

WO2004084437A1 - Navigation system using mobile device and method thereof

Info

Publication number: WO2004084437A1
Application number: PCT/KR2004/000417
Authority: WO
Inventors: Young Min Ji
Original assignee: Thinkware Systems Corporation
Priority date: 2003-03-19
Filing date: 2004-02-27
Publication date: 2004-09-30
Also published as: JP2006521033A

Abstract

The present invention discloses a phone navigation system, a navigation system, wherein a vector map engine is loaded with a mobile phone having a positioning function, and connects to a service center which manages a vector map server and a route detection server for pedestrians and drivers. For this purpose, the navigation system of the present invention includes a mobile communication terminal and a service server. The server includes components comprising: a map data base which maintains vector map data, which is map data composed of a vector map formation; a route detection module wherein a route to a prescribed destination is detected from a prescribed departure using the vector map data and wherein route data connected to the above route are generated; a vector map data detection module for detecting vector map data related to the above route data among the map data base; a vector map data packet generation module for generating a vector map data packet including the above detected vector map data; and the interface module for transmitting the vector map data packet including the vector map data to the mobile communication terminal. The mobile communication terminal comprises a step wherein the above route data and vector map data packet are inputted from the service server. In addition, the terminal includes components comprising: a second interface module wherein position information of the present position from a prescribed GPS receiver is inputted; a map image generation module wherein a map image is generated by a vector map method using the above route data, the above vector map data packet and the above position information; and a display control module wherein the map image is displayed on the indication device of the mobile communication terminal.

Description

NAVIGATION SYSTEM USING MOBILE DEVICE AND METHOD THEREOF

Technical Field

The present invention relates to a navigation system using a mobile device and method thereof. More particularly, the present invention relates to a navigation system and method thereof, wherein a map image can be generated in and displayed on a mobile device by using vector map data that correspond to map data in a vector map format and have been transmitted to the mobile device.

Background Art

Map services have been recently provided to mobile phones, but conventional map services are accomplished by a method of simply providing map images.

That is, if a map is to be displayed on a mobile phone located at a specific location, the mobile phone requests map information on a relevant location to a server which in turn generates a map image for a predetermined range and sends the generated map image to the mobile phone.

At this time, the map image is transmitted to the mobile phone in a raster data format. A method of representing an image may be broadly classified into a case where vector data are used and a case where raster data are used, depending on how the image data were processed in a computer.

Vector data has a spatial data structure including spots, lines and planes in order to represent an image. On the contrary, raster data has a structure in which each of the data is stored in a regular lattice called a cell or pixel.

For example, a black and white bitmap mode corresponding to a mode for generating raster data allows an image composed of a collection of cells to be represented using "0" and "1". For instance, a white cell corresponds to "0" and a black cell corresponds to "1" so that only one bit can be allocated to represent a single cell. If a color image can be represented, the amount of data of 8, 16 or 24 bits per cell can be allocated. Therefore, since the amount of data of at least 8 bits should be allocated to each cell to represent a color image, the amount of data necessary for the representation of a single image is increased.

Furthermore, since it is difficult to reduce or magnify an image transferred from a server to a mobile phone through conventional methods, the mobile phone should access the server via the Internet and receive a desired image again so as to reduce or magnify the image. Therefore, there is a problem in that related traffic is increased and communication fees become proportionately larger.

Accordingly, a conventional map service, which has been provided to a mobile phone, has problems in that an image cannot be provided at a satisfactory level and that the related traffic is increased while communication fees grow heavier. Further, since the image map has no additional information, there is a problem that it is difficult to further develop applications in a mobile device after the image map is downloaded.

Brief Description of Drawings FIG. 1 is a diagram showing the configuration of a phone navigation system according to the present invention.

FIG. 2 is a block diagram illustrating how a mobile phone and a service center are connected with each other.

FIGS. 3 to 7 are views illustrating an example in which a map is drawn at five stages of magnification/reduction.

FIGS. 8 to 12 are views illustrating an example in which a map is drawn while it is rotated.

FIGS. 13 to 17 are views illustrating a navigation example in which a map is drawn on a phone as the phone moves. FIG. 18 is a block diagram showing the configuration of a navigation system according to another embodiment of the present invention.

FIG. 19 (a) to (c) is a diagram illustrating an example of vector map data maintained in a map database according to an embodiment of the present invention.

FIG. 20 is a diagram illustrating sequential coordinate information of vertexes included in the vector map data according to the embodiment of the present invention.

FIG. 21 is a flowchart illustrating the steps for embodying a navigation method according to another embodiment of the present invention. FIG. 22 shows a process of generating a vector map data packet according to another embodiment of the present invention.

FIG. 23 is a diagram illustrating a map segment according to another embodiment of the present invention.

FIG. 24 is a diagram illustrating a process of generating a vector map data packet by using map segments and grids according to a further embodiment of the present invention.

FIG. 25 is a diagram illustrating the process of generating a map image in a mobile according to a still further embodiment of the present invention.

Disclosure of Invention

The present invention is conceived to solve the aforementioned problems in the prior art. An object of the present invention is to provide a navigation system and method, wherein when a user of a mobile device wishes, a map can be provided to the mobile device in a vector map mode using GPS information by installing a vector map engine in the mobile device and operating a service center that provides a vector map.

Another object of the present invention is to provide a navigation system and method, wherein vector map data in a vector map format are transmitted to a mobile device to generate a map image that will be displayed on a display device of the mobile device.

A further object of the present invention is to provide a navigation system and method, wherein transmission time and communication fees can be reduced by transmitting vector map data in a map segment unit.

A still further object of the present invention is to provide a navigation system and method, wherein a mobile device can easily search vector map data needed for generating a map image by dividing each map segment into one or more grids.

According to an aspect of the present invention for achieving the objects and solving the problems in the prior art, there is provided a navigation system, comprising a map database for maintaining vector map data corresponding to map data formed in a vector map format, a path search module for searching a path from a predetermined source to a predetermined destination using the vector map data and generating path data associated with the path, a vector map data search module for searching the map database for vector map data associated with the path data, a vector map data packet generation module for generating a vector map data packet including the searched vector map data, and a first interface module for transmitting the vector map data packet including the vector map data to a mobile device. Preferably, the vector map data include polygon information, polyline information and point information, the polygon information includes, in conjunction with a predetermined polygon, the number of vertexes of the polygon and sequential coordinate information of the vertexes, the polyline information includes, in conjunction with a predetermined polyline, the number of vertexes of the polyline and sequential coordinate information of the vertexes, the point information includes coordinate and icon information of the point, and each of the polygon information, the polyline information, and the point information is a vector map data element.

Further, the sequential coordinate information may comprise a first coordinate for one vertex represented in the absolute coordinate system, and a second coordinate for the remaining vertexes represented in the relative coordinate system on the basis of the first coordinate.

More preferably, the vector map data further comprises level information or color information, which is associated with the polygon information and the polyline information, respectively, and at least one of level information, icon information, and text information associated with the point information, the text information including a text and the length of the text; and the level information is information indicating whether the vector map data element is represented when a map of a predetermined scale is displayed on a display means of the mobile device.

Furthermore, the mobile device comprises a second interface module for receiving the path data and the vector map data packet, a screen region decision module for deciding a screen region to be displayed on a display device of the mobile device by using the path data and positional information on a current position received from a predetermined GPS receiver, a map image generation module for generating a map image corresponding to the screen region by using the vector map data packet, and a display module for displaying the map image on the display device. Best Mode for Carrying Out the Invention

Hereinafter, preferred embodiments of a phone navigation system according to the present invention will be described in detail with reference to the accompanying drawings. Referring to FIG. 1, the phone navigation system according to the present invention is implemented by the linkage of a phone 10 and a service center 12. To this end, the system includes a mobile communication network 14 and the Internet 16 connected to the mobile communication network 14 via a dedicated line. Furthermore, the phone 10 and the mobile communication network 14 communicate with each other in a wireless mamier, and the Internet 16 and the service center 12 are connected in a wired manner.

In the above, the phone 10 has a vector map engine and a GPS module, which will be described with reference to FIG. 2, mounted therein. The service center 12 has a vector map server and a vector map database, which will be described with reference to FIG. 2. Detailed explanation on the functions of them will be described with reference to FIG. 2.

Hereinafter, the construction and functions of the phone 10 and the service center 12 will be described in detail with reference to FIG. 2.

The phone 10 has an application 20 and a vector map engine 22 mounted therein. The phone 10 further includes a GPS module 21, which may be mounted as an internal type (MS-Assisted, MS-Based mode or the like) or an external type (a stand or a type connected to a serial port).

The GPS module 21 calculates positional information, direction information and speed information by using the latitude/longitude coordinates in conjunction with satellites. The application 20 performs a call setup for a map service to communicate with the service center 12. ^"

Furthermore, the vector map engine 22 performs the function of drawing a map by use of map information supplied from a vector map server 30 of the service center 12 and displaying the drawn map. The service center 12 has an agent server 24 serving as a gateway, a POI (Point of

Interests) server 26, a vector map server 30 and a vector map database 32.

The agent server 24 receives positional information and phone information of the phone 10 and information selected and inputted by a user in the phone through communication with the application 20 of the phone 10, and transmits information containing a list of a source/destination or a path search result.

The POI server 26 has data in which buildings, their geographical names, their addresses, etc. matched one another. On the basis of the data, the POI server 26 supplies a user of the phone 10 with a list, which is associated with a text input by the user for searching a source/destination. At this time, the POI server 26 also supplies the user with information such as a POI name, positional information, addresses, etc., which correspond to elements of the list. The list provided by the POI server 26 is sent to the phone 10 through the agent server 24.

Furthermore, the path search server 28 searches a variety of paths between the source and destination selected by the user considering specifications (shortest, optimum or traffic information) which are defined by the user in a form according to an

"environment setting" function of the phone 10, and then provides the path search result to the phone 10 through the agent server 24.

The vector map database 32 stores map information of a vector map format therein, which is needed for the vector map engine 22 of the phone 10 to draw a map. The map information includes display information, information on buildings or the names of places (icon information corresponding to buildings or the names of places), and guide information (text and sound).

The vector map server 30 provides the vector map engine 22 of the phone 10 with map information of the vector map database 32, which corresponds to the current location of the phone 10, and a source/destination.

Through the navigation system of the present invention constructed as above, a map service using a vector map can be accomplished.

The phone 10 has values in which a path search method, a range of a map, a scale of a map and a guide mode (a traveling mode, a walk mode, etc., which will be described later) are specified to have predetermined formats by means of the "environment setting" function. As a user pushes or clicks on a navigation button or service start button that is previously set in the phone 10 (CD), a system according to the present invention is driven.

If a phone navigation system is driven, the application 20 drives the GPS module 21 to calculate its own positional information, progress direction and speed information. The GPS module 21 calculates those information using latitude/longitude coordinates in conjunction with satellites.

The application 20 transmits the positional information calculated in the GPS module 21 and phone information of the device itself (a phone number or a user ID) to the agent server 24 of the service center 12 and then performs a call.

At this time, the application 20 basically transmits its mobile information (a phone number or a user ID) to the service center 12 in order to generate logging information and accounting information when requesting data to the service center 12. If a call setup depending on the call of the application 20 is established between the phone 10 and the service center 12, the user uses the phone 10 to input text to search for a source/destination to the service center 12.

The text for searching the source/destination is transmitted from the application 20 to the POI server 26 through the agent server 24 (©). At this time, the application 20 supplies the POI server 26 with a text search function for information containing a name, an address, etc. Accordingly, the POI server 26 extracts a list associated with the text and then transmits the extracted list to the application 20 of the phone 10 through the agent server 24 (©).

The user selects a destination/source from the list displayed on the application 20 of the phone 10 and then makes a request for a path search accordingly ((3)). The path search request is transferred to the path search server 28 via the agent server 24, wherein the positional coordinate of the source and destination is transferred to the path search server 28. In the above, when the POI server 26 provides the list to the application 20, the positional coordinate may be transferred in a state where additional information by the list element is added to the positional coordinate. If the user selects the destination/source, relevant positional coordinates are transferred to the service center 12.

Accordingly, the path search server 28 performs the path search between the source and the destination.

The path search may be classified into the shortest distance path search, optimal path search considering the type of roads and the number of lanes, a path search considering real-time traffic information and so on. A path search index corresponding to it is defined in the above-mentioned "environment setting" and can be thus provided according to selection of an option in the phone 10 by the user.

The path search server 28 transfers path search information that has been determined to be optimal among a variety of paths, which can be formed between a specified source and a destination, to the application 20 of the phone 10 via the agent server 24 (©).

Then, the application 20 drives the vector map engine 22. The vector map engine

22 requests map data, which are needed to represent a map from the source to the destination, to the vector map server 30 (©). At this time, the vector map engine 22 transmits phone information, a map scale, centric coordinates (self positional coordinate), and the range of a map to be clipped (X, Y axis size) to the vector map server 30.

The vector map server 30 searches the vector map database 32 and then sends map information corresponding to it (©).

At this time, map information including all data from a source to a destination can be transmitted. It is, however, preferred that the map information is transmitted in a state where the map information is sliced into a given unit or limited range in order to reduce communication fees depending on the reception of data, and is transmitted (©) at the request of transmission of a secondary (additional) map (©) before the phone deviates from a corresponding region as the position of the mobile device moves.

In the above, regarding the slicing, a map of a corresponding range may be first transmitted and a map of a range deviating from a path may be then transmitted additionally as the position of the phone moves, in such a manner that the path from the source to a destination is divided into a plurality of sections or the range of the map (X, Y axis size) is limited.

Furthermore, in order to reduce communication fees, the map infonnation may be transmitted in a compressed form from the vector map server 30 and may be decompressed in the vector map engine 22.

In a common map shape, it is preferred that the map is guided in a road shape-oriented simple map mode from which a turn-by-turn mode, polygon information or the like is omitted. Further, it is preferable that only map data around complicated roads are previously received at a time or data around a corresponding road are received when the current position is around a complicated road in order to prevent loss upon deviation from a path. Definition on complicated roads is included in the path search database upon the generation of map information.

If a device is located around a complicated road, the mode is automatically switched to a detailed map mode to display a detailed map. This provides a user (or a driver) with improved visibility and readability. In the above, the map information may contain display information necessary to represent a map, buildings or traffic information of a pertinent area, and guide information for text or sound guidance.

Display of a map as described above is implemented as the vector map engine 22 draws a map by using display information received from the vector map server 30. To this end, the vector map engine 22 carries out an operation for drawing a map using map information based on a predetermine mathematical calculation method.

As described above, as display of the map is implemented in a vector map mode, i.e., the mathematical calculation method, the map can be easily magnified and reduced in multiple stages, as shown in FIGS. 3 to 7. Furthermore, a map displayed according to the present invention can be freely moved and rotated, as shown in FIGS. 8 to 12, due to the application of the above mathematical calculation method. As shown in FIGS. 3 to 7, and FIGS. 8 to 12, the magnification/reduction or the movement and rotation are implemented by mathematical calculation by using previously received map information. The vector map engine 22 of the present invention does not need to request the vector map server 30 to transmit additional data.

The embodiment according to the present invention can be implemented as described above. In the present invention, text or sound guide functions using guide infonnation can be additionally set.

The sound guide function is added to map information and is transferred from the vector map server 30 to the vector map engine 22. The GPS module 21 and the vector map engine 22 jointly perform the sound guide function through the interface of the application 20.

Furthermore, the guide may be set to determine how far an object to be guided is spaced apart from its current position and may be set step by step as an object to be guided approaches such as a predetermined distance (2 km 1 km, 500 m, 100 m, 30 m: guide by the distance can be dynamically changed considering the speed of a vehicle).

In order to set the sound guide function, guide sounds may be defined as much as direction information. For example, guide sounds may be defined as "the distance ahead up to a guide place + direction information (please turn right 500 m ahead)". Furthermore, if information to be guided now and information to be guided sooner or later are within a specific distance, consecutive guide may be set. In a place where a lot of traffic accidents occur or a place where speeding is prohibited, guides for safe driving may be implemented.

Also, in an embodiment according to the present invention, a current position can be determined by referring to GPS information while the phone moves. A map may be displayed with it rotated while constantly keeping a moving direction depending on its movement state, as shown in FIGS. 13 to 17. This can be implemented by matching surrounding maps while referring to a moving direction and its own positional material.

Furthermore, a display mode may be classified into a traveling mode and a walk mode. In the display mode, it can changes the state where a map is displayed corresponding to traveling location and direction, by displaying a place on the above road. In walk mode, it may be set to represent only coordinates on a map without placing the location on a road.

If a user uses the phone 10 while driving, the mode may be set to store a current position and restore to its original state after the call.

Also, if the phone deviates from a searched range, the present invention may provide a function of sensing the deviated position based on self-positional information and then requesting a path research automatically or manually.

Hereinafter, a navigation system using a mobile device according to another embodiment of the present invention will be described. FIG. 18 shows a schematic structure of a navigation system according to this embodiment and a network connection of the navigation system. A mobile device 1810 can be connected to a navigation system 1800 via a wireless communication network. A mobile device used in this specification may include a hand phone, a PDA, a smart phone and the like.

The navigation system 1800 includes a map database 1801, a path search module

1802, a vector map data search module 1803, a vector map data packet generation module 1804 and a first interface module 1805. Further, the mobile device 1810 includes a second interface module 1811, a screen region decision module 1812, a map image generation module 1813 and a display module 1814. The map database 1801 stores vector map data therein. The vector map data are map data of a vector map format.

According to an embodiment of the present invention, the vector map data include polygon information, polyline information and point information. The polygon information includes i) the number of vertexes of a predetermined polygon and sequential coordinate information of the vertexes, ii) level information and iii) color information, in conjunction with the polygon. The polyline information includes i) the number of vertexes of a predetermined polyline and sequential coordinate information of the vertexes, ii) level information and iii) color information, in conjunction with the polyline. Point information includes i) coordinate and icon information of a point and ii) text information (a text and the length of the text). Each of the polygon information, the polyline information and the point information is defined herein as a "vector map data element".

FIG. 19 (a) to (c) shows an example of vector map data stored in the map database 1801 as above. FIG. 19 (a) shows polygon information associated with a polygon having n vertexes. Reference numeral 1901 indicates sequential coordinate information of the vertexes of the polygon.

FIG. 19 (b) shows polyline information associated with a polyline (comprising a (N-l) number of links formed by N vertexes (nodes)) having the N nodes. According to another embodiment of the present invention, although not shown in

FIG. 19, the polygon information, the polyline information and the point information may further include information for identifying the type of a vector map data element (for example, polygon information). Further, according to another embodiment of the present invention, in order to identify the type of each vector map data element, the polygon information, the polyline information and the point information may be stored at different fields in the map database.

According to an embodiment of the present invention, the sequential coordinate information is a coordinate of first to N^th vertexes, which are represented by an absolute coordinate system. If a quadrilateral polygon is represented (at this time, N = 4) as shown in FIG. 20, a first vertex coordinate is (1000, 2000), a second vertex coordinate is (1020, 2000), a third vertex coordinate is (1020, 2030), and a fourth vertex coordinate is (1000, 2030). An x-axis and y-axis in FIG. 20 is an absolute coordinate axis by the absolute coordinate system.

Furthermore, according to another embodiment of the present invention, the sequential coordinate information comprises a first coordinate for a single vertex that is represented by the absolute coordinate system, and a second coordinate for the remaining vertexes, which are represented by a relative coordinate system on the basis of the first coordinate. If FIG. 20 is taken as an example, a first vertex coordinate is (1000, 2000), a second vertex coordinate is (20, 0), a third vertex coordinate is (20, 30) and a fourth vertex coordinate is (0, 30). At this time, the first vertex coordinate corresponds to a first coordinate using the absolute coordinate system, and the second to fourth vertex coordinates correspond to a second coordinate using the relative coordinate system on the basis of the first vertex coordinate. According to this embodiment, it is possible to significantly reduce the amount of data required to represent vertex coordinates associated with a polygon or a polyline.

Alternatively, color information included in the polygon information is used to decide color within a polygon, which is generated by a line segment that sequentially connects respective vertexes. Color information included in the polyline information is used to decide a color of a line segment (this line segment has a thickness decided according to a predetermined basis), which is connected by respective vertexes.

Icon information contained in the point information is information for generating an icon image, etc., which is displayed at a position corresponding to a coordinate of the point. The icon image may have a simple point shape and may be one where a school shape is simplified if a school is located at a location corresponding to the coordinate. Text included in the point information may be a "school" in association with the coordinate and the text may be displayed on a map image that will be described later, in association with the point. The text length is information that is used to read the text in the mobile device 1810, which has received a vector map data packet containing the point information.

The level information associated with the vector map data element is information indicating whether the vector map data element is represented when a map of a predetermined scale is displayed on the display means of the mobile device 1810. For example, in case where three scale sizes such as reduced, standard and magnified modes are provided, if level information associated with first polygon information is (1, 1, 0) and level information associated with second polygon information is (1, 1, 1), the first polygon information is used in the reduced and standard modes so as to generate a map image as described later (i.e., the first polygon information is displayed on the display device), but is not displayed in the magnified mode. The second polygon information is used in all the reduced, standard and magnified modes in order to generate a map image. In the example, "1" indicates display and "0" indicates non-display.

The path search module 1802 searches a path from a predetermined source to a predetermined destination by using the vector map data, thus generating path data associated with the path. A user may input the selected source and destination by using the mobile device 1810. In this case, the navigation system 1800 may further have a positional database (not shown) on which positional data are recorded in order for the source and destination to be easily selected and may provide a "keyword search service" to the mobile device 1810.

Alternatively, according to another embodiment of the present invention, the user can input the source or the destination with sound. In this case, sound data for a source or destination, which are input with sound, are converted into text data by means of a predetermined sound recognition system (not shown).

For example, the sound recognition system is included as a part of the mobile device 1810. At this time, the mobile device 1810 further includes a user input module (not shown) for receiving sound data for a source or destination input by a user. The mobile device 1810 uses a sound recognition system to convert sound data into text data.

The second interface module 1811 transmits the character data to the navigation system 1800. The path search module 1802 uses the text data to decide a source or destination. If positional data matching the text data are not searched from the positional database or one or more positional data are searched, text data can be again input to the mobile device 1810 in order to correctly decide a source or destination.

Further, the sound recognition system is provided on the part of the navigation system 1800. The user input module receives sound data for a source or destination from a user. The second interface module 1811 sends the sound data to the first interface module 1805.

The path search module 1802 uses the sound recognition system to convert the sound data into text data and uses the converted text data to decide the source or destination.

Therefore, users can easily select a source or destination with sound while driving.

The vector map data search module 1803 determines a predetermined region from the map database 1801 and searches the map database 1801 for vector map data included in the region. According to an embodiment of the present invention, the vector map data search module 1803 decides vector map data associated with the generated path data as vector map data to be sent and searches for vector map data accordingly.

The vector map data packet generation module 1804 generates a vector map data packet using the searched vector map data.

The first interface module 1805 transmits the generated vector map data packet to the mobile device 1810.

The mobile device 1810 comprises the second interface module 1811, the screen region decision module 1812, the map image generation module 1813 and the display module 1814, as described above.

The second interface module 1811 receives the path data and the vector map data packet from the navigation system 1800.

The screen region decision module 1812 determines a screen region to be displayed on a display device of a mobile device, by using the received path data and positional information on a current position received from a predetermined GPS receiver (not shown). The screen region decision module 1812 can determine a screen region on the basis of a path by using the path data (i.e., in order for a user to easily decide a current position on the path). The screen region may be differently decided according to the ratio of a horizontal length and a vertical length of a display region in the display device, depending on which of the north-up method and the heading-up method is adopted. The GPS receiver may be embedded in the mobile device 1810 or may be connected to the mobile device 1810 as an additional module.

The map image generation module 1813 generates a map image corresponding to the screen region. The map image generation module 1813 searches the received vector map data packet for vector map data corresponding to the screen region and generates a map image by using polygon information, polyline information or point information included in the searched vector map data. FIGS. 3 to 17 illustrate an exemplary map image generated by the configuration as above. Further, if a user inputs a magnification or reduction command, the screen region decision module 1812 decides a new screen region according to the command, and the map image generation module 1813 again generates a map image corresponding to the new screen region. To generate the map image, the map image generation module 1813 must include a read algorithm related to the structure of the vector map data packet therein, which can read information contained in the received vector map data packet in a predetermined manner.

In the above, a process of selecting vector map data elements to be represented from vector map data that are included in the screen region by using level information contained in the vector map data is carried out in advance.

The display module 1814 has the generated map image displayed on the display device.

Unlike a prior art that transmits a map image consisting of raster data, the navigation system 1800 according to this embodiment sends a vector map data packet including vector map data of map data having a vector map format to the mobile device 1810. It is thus possible to significantly reduce the amount of data transmitted via a communication network compared to the prior art.

In other words, in order to represent a polygon as shown in FIG. 20, in a prior art, a total of 100 cells such as (1000, 2000), (1001, 2000), (1002, 2000), ..., (1020,2000) and a map image itself including corresponding cells therein have to be transmitted. According to this embodiment, however, the navigation system 1800 can transmit only coordinate information of four vertexes ((1000, 2000), (20, 0), (20, 30), (0, 30)) in order to specify the shape of the polygon. Furthermore, in order to represent the inner color of the polygon with a specific color (for example, blue), in the prior art, color information as many number as respective cells has to be transmitted. In the navigation system 1800 according to the present invention, however, only single color information can be transmitted.

Also, in case where a user inputs a command for magnifying or reducing a map image that is displayed on the display device, in the prior art, a mobile device has to repeatedly perform a process of requesting transmission of a new map image (a map image when it is magnified or reduced) and receiving the map image. In the mobile device 1810 according to this embodiment, however, coordinate information included in an already received vector map data packet is multiplied by a predetermined value (a value higher than 1 in case of magnification, and a value lower than 1 in case of reduction). For this reason, the amount of data transmitted via a communication network is significantly reduced.

Alternatively, even in case where a user inputs a command for rotating a map image displayed on the display device, in vector map data included in a vector map data packet according to this embodiment, the spatial relationship can be identified by itself. Thus, a rotated map image can be generated by applying a predetermined rotary algorithm to vector map data included in a vector map data packet that is already received/stored, without receiving a new map image as in the prior art. It is thus possible to significantly reduce the amount of data transmitted via a communication network.

As such, as the amount of the data transmitted via the communication network is reduced, it is possible to reduce time until the map image is displayed on the display device of the mobile device after a user inputs a command, compared to the prior art.

Meanwhile, the GPS receiver may either be internal or external. In case of an internal type, the GPS receiver may use A-GPS technology or Autonomous GPS technology. In case of an external type, the GPS receiver can be connected to the mobile device 1810 through a universal asynchronous receiver/transmitter (UART) terminal, a universal serial bus (USB) terminal, an infrared rays (IR) terminal, a Bluetooth module and the like.

Hereinafter, a navigation system using a mobile device according to another embodiment of the present invention will be described. The navigation system according to this embodiment includes a map database, a path search module and an interface module.

The map database stores vector map data of map data therein, which have a vector map format. The path search module uses the vector map data to search a path from a predetermined source to a predetermined destination.

The interface module sends the path data to the mobile.

The mobile that received the path data generates a map image by using the path data and has the generated map image displayed on its display device. The map image may be generated using raster data or vector map data. Further, the raster data or vector map data may be data stored in the mobile device, or data received from the navigation system. As such, as the path search is carried out in the navigation system not the mobile device and the mobile device receives the path search result via a communication network, data or an algorithm for a path search need not to be stored in the mobile. Furthermore, a problem occurring since data needed for a path search are not updated when the path search is performed in the mobile device can be solved. A navigation method according to another embodiment of the present invention will now be described with reference to FIG. 21 and 22. FIG. 21 is a flowchart illustrating the steps for embodying a navigation method according to this embodiment. The navigation method may be performed by a predetermined navigation system.

The navigation system has vector map data being map data maintained in a predetermined database, wherein the vector map data have a vector map format (2110). The vector map data have been described in detail with reference to the aforementioned embodiment. Detailed description on them will be thus omitted in this embodiment for simplicity.

The navigation system receives a source and destination from a mobile device (2120). According to an embodiment of the present invention, a user can select the source and destination in a keyword search mode. To this end, the navigation system may further include a positional identifier database for storing positional identifiers that indicate predetermined locations therein. For example, if the keyword is "patent office", the navigation system transmits a search result such as "patent office", "patent office library" (each indicating a positional identifier) and the like, which are keywords including the keyword called "patent office", to the mobile device for a user's review. The user selects a source or destination by selecting "patent office library".

Furthermore, according to another embodiment of the present invention, the source is the current position of the mobile device. The mobile device identifies the current position by using GPS information received from a predetermined GPS receiver and transmits an input for selecting the identified current position as a source to the navigation system. The navigation system searches a path from the source to the destination by using vector map data stored in the database (2130). In order to search the path from the source to the destination, the navigation system may employ a variety of algorithms such as a method of searching the shortest distance path, a method of searching the shortest time path using traffic information and the like.

The navigation system transmits path data associated with the searched path to the mobile device (2140).

The navigation system generates a vector map data packet including predetermined vector map data and transmits the generated packet to the mobile device (2150). According to an embodiment of the present invention, the navigation system searches the vector map data stored in the database for vector map data associated with the path and generates a vector map data packet including the searched vector map data. In other words, the vector map data packet is generated in conjunction with the path.

The mobile receives the path data and vector map data packet (2160), generates a map image using the vector map data packet (2170) and displays the map image on a display device of the mobile device (2180).

Hereinafter, step 2150 for generating the vector map data packet will be described in more detail.

According to an embodiment of the present invention, the vector map data packet is a packet consisting of a header and a body. The header includes the number by the vector map data element included in the searched vector map data (i.e., a first number of polygon information, a second number of polyline information and a third number of point information). The body contains the polygon information, the polyline information or the point information. The mobile that received the vector map data packet can search vector map data elements necessary to generate a map image by using information on the number included in the header, when generating the map image in step 2170.

Further, according to another embodiment of the present invention, the vector map data packet is generated and transmitted by the map segment (2150). The searched vector map data can be processed with them divided into one or more map segment units.

In other words, information on the number included in the header is the number by the vector map data element, which is included in the map segment. As such, if a vector map data packet is generated and "transmitted" by the map segment, that is, if searched vector map data are transmitted with them dividedly loaded onto one or more vector map data packets, the amount of data that have to be sent at one time is reduced. Therefore, as the mobile device generates and transmits the vector map data packet according to the sequence of vector map data required to generate a map image, it is possible to reduce time from when a user requests a predetermined display to when the mobile device receives a vector map data packet, generates a map image and displays the generated map image. In other words, the mobile device can perform the process of generating a map image using received vector map data packets, displaying the generated map image and transmitting the remaining vector map data packets at the same time.

If a user resets another place as a destination without heading for an original destination while moving along the path, the user does not receive data from the current position to the original destination, which prevents unnecessary reception of data.

Furthermore, according to another embodiment of the present invention, the map segment can be divided into one or more grids. In other words, the map segment can be processed with it divided into one or more grids. At this time, if the map segment is used as a transmission unit of a vector map data packet, the grid is a search unit which is used to facilitate a search for vector map data needed to generate a predetermined map image among the vector map data packet, if the vector map data packet associated with the map segment is sent to the mobile device, as will be described later.

Hereinafter, step 2150 of generating the vector map data packet in the navigation system by using the map segment and grids according to one embodiment of the present invention will be described with reference to FIGS. 22 to 24. The navigation system divides the searched vector map data into one or more map segments (2151). FIG. 23 is a view shown to explain step 2151. Vector map data 2320a, 2320b indicate some of vector map data searched in conjunction with a path. There is shown in FIG. 23 that a vector map data packet is generated in which vector map data are divided into two map segments 2320a and 2320b.

Meanwhile, although a rectangular region including a path 2310 has been used as vector map data associated with the path in FIG. 23, the vector map data associated with a path can be defined in various ways.

The navigation system divides the respective divided map segments into one or more grids (2152). FIG. 24 shows a case where the map segment 2320a is divided into grids of 10x10, i.e. 100 grids.

The navigation system calculates a first number of polygon information, a second number of polyline information and a third number of point information, which are included in each grid (2153).

The navigation system groups the polygon information, the polyline information or the point information, which is included in each grid, to generate a group. In other words, the group is generated one by one by the grid (2154).

The navigation system generates a group identifier for the group considering the location within the map segment of the grid (2155). Numbers indicated in each grid of FIG. 24 designate a group identifier of a group associated with the grid. As shown in FIG. 24, as the group identifier is generated considering the location of the grid in the map segment, the group identifier can be used as a search unit for searching a group corresponding to a desired location, as will be described later. The navigation system generates vector map data, which contain a header having the first number, the second number, the third number and a total number of map segments, and a body having the group identifier and a group associated with the group identifier (2156).

Hereinafter, step 2170 of generating the map image in the mobile will be described in more detail by reference to FIG. 25. The mobile detennines a screen region to be displayed on the display device based on the position of the mobile and the path data (2171). For example, the mobile device may decide a portion indicated by an oblique line region in FIG. 23 as a screen region 2330. The screen region 2330 may be differently decided depending on the size, the aspect ratio, etc. of the display device, according to which of the heading-up method and the north-up method is used.

The mobile device decides grids associated with the screen region among vector map data included in the vector map data packet (2172). The grids correspond to grids, which can include all the vector map data that must be represented in the screen region. For example, if the screen region shown in FIG. 23 is a region as indicated by reference numeral 2330 among the vector map data shown in FIG. 24, grids associated with the screen region are determined as grids 44 to 46, 54 to 56, and 64 to 66. Also, group identifiers of a group associated with the grids determined as above are 44, 45, 46, 54, 55, 56, 64, 65 and 66.

The group identifier is used to search a group corresponding to the determined grids (2173). As the group is included in the vector map data packet in association with the group identifier, the group can be searched using the group identifier. A map image is generated using polygon information, polyline information or point information included in the searched group (2174).

As such, vector map data elements necessary to generate a map image are searched from only vector map data corresponding to a grid associated with a screen region, without sequentially searching all the vector map data included in a received vector map data packet. Therefore, time taken for a search is reduced and a load applied to a mobile in order to perform the search is reduced.

Alternatively, according to another embodiment of the present invention, the mobile device can sequentially generate a first map image using polygon information, a second map image using polyline information, and a third map image using point information, if the map images are generated using the polygon information, the polyline information or the point information included in a group searched in step 2174. In addition, the mobile device sequentially displays the first to third map images in the order in which they are generated when the map images are displayed on the display device in step 2180. At this time, as first to third numbers for the number such as the number of polygon information by the group, etc. are stored in the header of the vector map data packet, the type of the polygon information, the polyline information and the point information can be identified using the number information. In other words, if the first number is 3, the first three vector map data elements may be identified as polygon information and the fourth vector map data element may be identified as polyline information.

According to this embodiment, a mobile device generates a map image in such a manner that the map image itself is not sent to the mobile device in a raster data format, but rather a vector map data packet of a vector data format is sent to the mobile device. Therefore, the amount of data transmitted via a communication network is significantly reduced compared to a prior art.

Furthermore, as vector map data included in a vector map data packet are data that can represent the spatial relationship themselves, the mobile device can generate a map image corresponding to a user's command by using previously received vector map data, without receiving additional data even if the inputs a magnification, reduction or rotation command. Accordingly, the amount of data transmitted via a communication network is significantly reduced compared to a prior art and time taken until a predetermined result corresponding to a user's command is provided is reduced.

In addition, the present invention further provides a computer-readable recording medium in which a program for implementing a navigation method in a computer or a mobile device constituting a navigation system is recorded. The computer-readable recording medium may be composed of one of a program command, a data file and a data structure, or any combination of them. The medium may be one specially designed or constructed for the present invention, or one known to those skilled in the field of computer software.

Industrial Applicability According to the present invention, there are disclosed a navigation system and method thereof, which can provide a user with a navigation service by using a mobile device and can transmit vector map data of a vector map format as map data for generating a map image, which will be displayed on a display device of the mobile device, to the mobile device. According to the present invention, as a mobile generates a map image using vector map data received from a predetermined server, the map data need not to be stored in the mobile. Therefore, the present invention has an effect that it can provide a navigation service using a mobile device such as a hand phone, etc. having a low storage capacity. In particular, the present invention has an effect that it can reduce the amount of data (vector map data), which has to be sent to a mobile device in order to generate a map image, since the vector map data are map data having a vector map format. Further, there are effects in that transmission of data such as a magnified map image is not required even when the map image is magnified, reduced, moved or rotated, and vector map data corresponding to a previously received region need not to be received again even when additional data are necessary.

Furthermore, according to the present invention, the vector map data are transmitted to a mobile by a map segment as much amount as needed as the mobile device changes its position. Therefore, the present invention has effects in that time taken until a vector map image is displayed on a display device of a mobile device is reduced and unnecessary vector map data need not to be received according to varying conditions.

Therefore, the present invention has an effect that it can reduce communication fees needed to use a navigation service since communication fees are usually decided depending on the amount of data transmitted/received via a wireless communication network.

Claims

1. A navigation system using a mobile device, comprising: a mobile device; and a service server, wherein the service server comprises: a map database for maintaining vector map data corresponding to map data formed in a vector map format; a path search module for searching a path from a predetermined source to a predetermined destination using the vector map data and generating path data associated with the path; a vector map data search module for searching the map database for vector map data associated with the path data; a vector map data packet generation module for generating a vector map data packet including the searched vector map data; and a first interface module for transmitting the vector map data packet including the vector map data to the mobile device, and wherein the mobile device comprises: a second interface module for receiving the path data and the vector map data packet from the service server and for receiving positional information on a current position from a predetermined GPS receiver; a map image generation module for generating a map image in a vector map mode by using the path data, the vector map data packet, and the positional information; and a display control module for displaying the map image on a display device of the mobile device.

2. A navigation system using a mobile device, comprising: a map database for maintaining vector map data corresponding to map data formed in a vector map format; a path search module for searching a path from a predetermined source to a predetermined destination using the vector map data and generating path data associated with the path; a vector map data search module for searching the map database for vector map data associated with the path data; a vector map data packet generation module for generating a vector map data packet including the searched vector map data; and a first interface module for transmitting the vector map data packet including the vector map data to the mobile device.

3. The navigation system as claimed in claim 2, wherein the vector map data include polygon information, polyline information, and point information, the polygon information includes, in conjunction with a predetermined polygon, the number of vertexes of the polygon and sequential coordinate information of the vertexes, the polyline information includes, in conjunction with a predetermined polyline, the number of vertexes of the polyline and sequential coordinate information of the vertexes, the point information includes coordinate and icon information of the point, and each of the polygon information, the polyline information, and the point infonnation is a vector map data element.

4. The navigation system as claimed in claim 3, wherein the sequential coordinate information comprises: a first coordinate for one vertex represented in the absolute coordinate system, and a second coordinate for the remaining vertexes represented in the relative coordinate system on the basis of the first coordinate.

5. The navigation system as claimed in claim 3, wherein the vector map data further comprises: level information or color information, which is associated with the polygon information and the polyline information, respectively, and at least one of level information, icon information, and text information associated with the point information, the text information including a text and the length of the text, and wherein the level information is information indicating whether the vector map data element is represented when a map of a predetermined scale is displayed on a display means of the mobile device.

6. The navigation system as claimed in claim 2, wherein the mobile device comprises: a second interface module for receiving the path data and the vector map data packet; a screen region decision module for deciding a screen region to be displayed on a display device of the mobile device by using the path data and positional information on a current position received from a predetermined GPS receiver; a map image generation module for generating a map image corresponding to the screen region by using the vector map data packet; and a display module for displaying the map image on the display device.

7. The navigation system as claimed in claim 1 or 6, wherein if the GPS receiver is an internal GPS receiver, the GPS receiver is an A-GPS receiver or an Autonomous GPS receiver.

8. The navigation system as claimed in claim 1 or 6, wherein if the GPS receiver is an external GPS receiver, the GPS receiver is connected to the mobile device through any one of a universal asynchronous receiver/transmitter (UART) terminal, a universal serial bus (USB) terminal, an infrared rays (IR) tenninal, and a Bluetooth module.

9. The navigation system as claimed in claim 1 or 6, wherein the mobile device further comprises: a user input module for receiving sound data from a user; and a sound recognition system for converting the sound data into character data by recognizing the sound data, wherein the second interface module transmits the character data to the navigation system, and the source or destination is decided using the character data.

10. The navigation system as claimed in claim 1 or 2, wherein the first interface module receives sound data from the mobile device, and the path search module converts the sound data into character data by using a predetermined sound recognition system and determines the source or destination by using the converted character data.

11. A navigation system using a mobile device, comprising: a map database for maintaining vector map data corresponding to map data formed in a vector map format; a path search module for searching a path from a predetermined source to a predetermined destination using the vector map data and generating path data associated with the path; and an interface module for transmitting the path data to the mobile device, wherein the mobile device performs the steps of generating a map image using the path data and displaying the map image on a display device of the mobile device.

12. A navigation method using a mobile device, comprising the steps of: maintaining vector map data, which correspond to map data formed in a vector map format, in a predetermined database means; receiving selection of a source and destination from the mobile device; searching a path from the source to the destination using the vector map data; transmitting path data associated with the searched path to the mobile device; generating a vector map data packet including the vector map data; and transmitting the vector map data packet to the mobile device, wherein the mobile device generates a map image using the vector map data packet.

13. The navigation method as claimed in claim 12, wherein the step of generating the vector map data packet including the vector map data comprises the steps of: searching the vector map data for vector map data associated with the path; and generating a vector map data packet including the searched vector map data.

14. The navigation method as claimed in claim 12, wherein the vector map data include polygon information, polyline information, and point information, the polygon information includes, in conjunction with a predetermined polygon, the number of vertexes of the polygon and sequential coordinate information of the vertexes, the polyline information includes, in conjunction with a predetermined polyline, the number of vertexes of the polyline and sequential coordinate information of the vertexes, the point information includes coordinate and icon information of the point, and each of the polygon information, the polyline information, and the point information is a vector map data element.

15. The navigation method as claimed in claim 14, wherein the sequential coordinate information comprises: a first coordinate for one vertex represented in the absolute coordinate system, and a second coordinate for the remaining vertexes represented in the relative coordinate system on the basis of the first coordinate.

16. The navigation method as claimed in claim 14, wherein the vector map data further comprises: level information or color information, which is associated with the polygon information and the polyline information, respectively, and at least one of level information, icon information, and text information associated with the point information, the text information including a text and the length of the text, and wherein the level information is information indicating whether the vector map data element is represented when a map of a predetermined scale is displayed on a display means of the mobile device.

17. The navigation method as claimed in claim 14 or 16, wherein the step of generating the vector map data packet including the searched vector map data comprises: a first step of calculating a first number of polygon information, a second number of polyline information, and a third number of point information, which are included in the searched vector map data; and a second step of generating a vector map data packet including a header having the first number, the second number, and the third number and a body having the polygon information, the polyline information, and the point information.

18. The navigation method as claimed in claim 14 or 16, wherein the step of generating the vector map data packet including the searched vector map data comprises the steps of: dividing the searched vector map data into one or more map segments; and generating a vector map data packet according to the map segment, wherein the step of generating the vector map data packet according to the map segment comprises: a first step of calculating a first number of polygon information, a second number of polyline information, and a third number of point information, which are included in the map segment, and a second step of generating a vector map data packet including a header having the first number, the second number, the third number, and the number of the map segments and a body having the polygon information, the polyline information, or the point information, and wherein the step of transmitting the vector map data packet to the mobile device comprises the step of transmitting the vector map data packet to the mobile device on the map segment basis.

19. The navigation method as claimed in claim 18, wherein the step of generating the vector map data packet according to the map segment further comprises the step of dividing the map segment into one or more grids, the first step comprises the step of calculating the first number of the polygon information, the second number of the polyline information, and the third number of the point information, which are included in the grid, the second step comprises the steps of: generate a group by grouping the polygon information, polyline information, or point information, which are included in the grid; allocating a group identifier for the group by considering a position of the grid within the map segment; and generating a vector map data packet including a header having the first, second, third numbers, and the number of the map segments and a body having the group identifier and a group associated with the group identifier.

20. The navigation method as claimed in claim 19, wherein the mobile device performs the steps of: receiving the vector map data packet; generating a map image by using the vector map data packet; and displaying the generated map image on a display device of the mobile device, wherein the step of generating the map image comprises the steps of: determining a screen region to be displayed on the display device based on the position of the mobile device and the path data; determining a grid associated with the screen region among the vector map data packet; searching a group corresponding to the determined grid by using the group identifier; and generating a map image by using polygon information, polyline information, or point information, which are included in the searched group.

21. The navigation method as claimed in claim 20, wherein the step of generating the map image comprises the steps of: generating a first map image by searching the polygon information included in the searched group; generating a second map image by searching the polyline information included in the searched group; and generating a third map image by searching the point information included in the searched group, wherein the step of displaying the map image on the display device comprises the step of sequentially displaying the first, second, and third map images on the display device.

22. The navigation method as claimed in claim 15, wherein the mobile device performs the steps of: receiving a command related to a scale of the map image from a user; selecting predetermined vector map data elements based on the command and the level information; generating second vector map data elements by multiplying coordinate information among the selected vector map data elements by a predetermined value decided according to the command, and; generating a map image using the second vector map data elements; and displaying the map image on a display device of the mobile device.

23. A computer-readable recording medium in which a program for implementing a method according to any one of claims 12 to 16 and 19 to 22 in a computer is recorded.