KR20110053737A - Vector Map Data Compression Method of Geographic Information System for Efficient Storage and Transmission - Google Patents

Abstract

The present invention relates to a vector map data compression method of a geographic information system (GIS). According to the vector map data compression method of the present invention, a layer having a property of polylines and polygons having the largest amount of data is selected from a geographic information database, and minimum coding properties are set by extracting record information from each selected layer. A coordinate value is extracted from each minimum coding attribute, and the integer part and the fractional part of the extracted coordinate value are separated. Two-step spatial domain energy concentration and parameter rearrangement are performed on the integer part, and hierarchical compression is performed on the fractional part. The integer data and the fractional data processed in this way are compressed by a predetermined entropy coder.

Description

TECHNICAL FOR COMPRESSING VECTOR MAP DATA FOR GEOGRAPHIC INFORMATION SYSTEM IN ORDER TO ACHIEVE EFFICIENT STORAGE AND TRANSMISSION}

The present invention relates to a method for compressing vector map data of a geographic information system (GIS), and more particularly, to perform Spatial Energy Compaction (SEC) on a spatial domain for lossless compression of GIS vector map data. The present invention relates to a GIS vector map data compression method that enables hierarchical encoding by independently processing an integer portion and a real portion of a real number with respect to 64-bit floating point coordinates.

Recently, with the development of network, portable Internet, personal multimedia terminal, etc., GIS has been applied to daily life and used in various forms, and it is used for electronic map and mashup service on the Internet. The demand for GIS is expanding rapidly through the existing Web-GIS service and the new paradigm of Where 2.0.

However, compared to these demands and marketability, when you want to send and store GIS data necessary for the actual user in a short time to the Internet, a mobile terminal, a personal PMP, or when a GIS service provider wants to operate a GIS server, geographic information The massive capacity problem of data is steadily being caused by the development of GIS. Also, given that governments, municipalities, and governments tend to require increasingly high precision GIS vector map data, and furthermore, full 3D GIS engine technologies will be implemented in the future. It can be expected that the problem of the capacity of the map data will become more serious.

On the other hand, in the Geographic Information System (GIS), ASCII and Binary formats are widely used as a representation and storage method of vector map data. Among them, in most GIS applications, vector map data stored in binary format is mainly used due to data capacity problems. As such binary map vector map data, an ESRI SHP file format is exemplified (http://www.esri.com, "ESRI Shapefile Technical Description" An ESRI White Paper, July 1998.).

In order to improve data accessibility, the SHP file format is designed so that files such as Main, Index, and Db are bundled into one layer, and include only one theme in one layer. 1 illustrates a structure of an SHP file for representing vector map data in a general binary format.

Referring to FIG. 1, an SHP file is composed of one file header, a plurality of record headers, and a plurality of record information corresponding thereto, and the SHP format has one attribute. It is used to express.

As an actual application example of the GIS vector map data, a process of a general GIS vector map service will be described with reference to FIG. 2. 2 is a service flow diagram for explaining a process of a general GIS vector map service.

The Geographic Information System (GIS) stores all geographic information data in a geographic information database connected to the server 10 in order to efficiently manage, search, and express a large amount of geographic information data.

In FIG. 2, the server 10 loads files of various subjects generated for each region from a database. The client 20 may be, for example, a web client on the Internet, a portable multimedia player (PMP), a mobile device, or a software application. The client 20 accesses the server 10 to receive and display a desired map area, and transmits information such as a horizontal distance, a vertical distance, a center coordinate, and a magnification of the request area to the server 10.

The server 10 calculates a view area based on the received map request area and magnification, and the like, and includes geospatial data (ie, several layers included in the map request area) of the corresponding view area from a database. The layer searches for, extracts, and compresses polylines, polygons, lines, and points, and the like, and then compresses them as server data. Send to The client 20 reconstructs the received geospatial data, completes it as a vector map, and displays it on the screen.

If the user clicks a zoom or move command on the map displayed on the screen, the client 20 packetizes and compresses the command related to the packet by encoding the server as a client packet. Send to (10). The server 10 analyzes the received client packet, calculates the view area changed by zooming or moving, retrieves and extracts geographic data of the corresponding view area from the database, and parses the packet for the geographic data. The packet thus parsed is packetized and compressed by packet encoding, and transmitted to the client 20 as a server packet. The client 20 zooms or moves according to the received geospatial data, completes one vector map, and displays it on the screen.

In FIG. 2, when the client 20 first accesses the server 10, Load_Default_Map_Data () performs an operation of searching, extracting, and compressing basic vector map data, which is the initial map area, by the server 10. Packet_Encoding () of the server side performs packetizing to a packet suitable for a corresponding transport protocol for transmitting GIS map data from the server 10 to the client 20. Packet_Encoding () on the client side performs a process of packetizing data (center coordinates, magnification, etc.) for transmission from the client 20 to the server 10. Load_Detailed_Map_Data is a process of searching and extracting geospatial data of the map request area changed by zoom or movement requested by the client 20 from the database using data received from the client 20 (such as central coordinates and magnification). To perform.

On the other hand, as a prior art regarding the compression of the vector map data, Kolesnikov proposed a compression method for the progressive transmission of the vector map (Alexander Kolesnikov, "Vector Maps Compression for Progressive Transmission" Proc. Of the 2nd IEEE International Conference on Digital Information). Management (ICDIM '07), pp. 81-86. Lyon, France, October 28-31, 2007).

The prior art decomposes a spatial multiresolution layer using an approximation method of polygons for a polygon based large vector map for efficient vector map transmission in a narrowband network environment, and performs arithmetic coding on low quality data and quantization error. It is a technique to perform transmission gradually for each by performing. Although the prior art achieves a high compression ratio and a high performance speed, it is disadvantageous that it can be applied only to polygon properties and is difficult to apply to an application for expressing a precision map. In addition, when the prior art is applied to a fine and high-density map, a large degradation occurs in the calculation rate uncompressed ratio, and the data compatibility for practical application is also not considered in the prior art.

More specifically, in the prior art, energy compaction of vector information in an existing frequency transform region (discrete cosine transform (DCT), discrete wavelet transform (DWT, etc.), etc.) for efficient compression of SHP data is performed. Although compression was attempted, it was found that it was difficult to apply to precision map compression and lossless reversible compression because of the high possibility of quantization error and integer conversion error. In addition, even if lossless compression is performed by the method of the prior art, when frequency conversion is performed on the vector map data having the floating point, the overhead of the conversion coefficient may be larger than that of the original. As a result, it has been found to be inappropriate to apply the prior art to the compression of precision vector maps.

On the other hand, when the general data compression method is applied to the SHP format itself, the entropy of the coordinate data represented by 64-bit floating point is not reduced, so that the improvement of the compression efficiency cannot be expected, and the compressed data is not restored. The disadvantage is that the state cannot maintain the data accessibility of the SHP format.

SUMMARY OF THE INVENTION The present invention has been made to solve the above-described technical problem. The present invention relates to a layer having a property of polylines and polygons having the largest amount of data in vector map data for efficient storage and transmission of vector map data in binary format with various precisions. It is an object of the present invention to provide an applicable vector map data compression method.

More specifically, the present invention performs energy concentration on a spatial domain for lossless compression of precision vector map data, and enables hierarchical coding by independently processing integers and fractions for 64-bit floating point coordinates, thereby improving compression efficiency. It is an object to provide a vector map data compression method that can be improved.

A vector map data compression method of a geographic information system according to the present invention for achieving the above object, (a) a polyline and polygon from a database for storing a plurality of layer files classified according to a plurality of attributes Selecting a layer having an attribute of), and extracting record information from each of the selected layers; (b) setting a minimum coding attribute (MCA) for each record information extracted in step (a); (c) extracting a coordinate value of an attribute included in each minimum coding attribute and constituting a part of the record content from each minimum coding attribute set in step (b), and the integer part and the decimal part of the extracted coordinate value Separating the; (d) 2-step space using the minimum boundary rectangle (MBR) coordinate value of each layer and the minimum boundary rectangle coordinate value of each attribute in each layer, for the integer part of the attribute coordinate value obtained in step (c). Performing region energy concentration and rearranging the displacement data and the sign data generated by the two-step spatial region energy concentration with information necessary for decoding; (e) For the fractional part of the attribute coordinate value obtained in step (c), the precision of the compression is determined, and the fractional part of the attribute coordinate value is grown in one record unit using a predetermined shift operation and the determined compression precision. Heating; And (f) compressing the integer part data and the fractional part data of the attribute coordinate values processed by the steps (d) and (e) by a predetermined entropy coder.

The vector map data compression method of the geographic information system according to the present invention provides a hierarchical and attribute independent compression technique for GIS vector map data, thereby enabling efficient storage and transmission of accurate GIS vector map data.

In particular, the vector map data compression method of the geographic information system according to the present invention separates the coordinate data represented by the floating point method into an integer part and a real part, performs energy concentration and parameter rearrangement on the spatial part, and By performing hierarchical compression, lossless compression of the precision vector map data is enabled.

In addition, the vector map data compression method of the geographic information system according to the present invention can improve compatibility with existing file formats by using the concept of minimum coding attributes, and can be applied to compression of most binary formats.

Hereinafter, preferred embodiments of the present invention will be described with reference to the accompanying drawings. However, the present invention is not limited to the embodiments disclosed below, but may be embodied in various different forms, and only the embodiments are intended to complete the disclosure of the present invention and to those skilled in the art. It is provided for complete information.

First, a GIS vector map data compression method according to an embodiment of the present invention will be described with reference to FIG. 3.

3 is a block diagram illustrating a GIS vector map data compression method according to an embodiment of the present invention.

As described with reference to FIG. 2, it is assumed that the GIS vector map data is stored in, for example, a geographic information database connected to a GIS server.

Regarding "GIS vector map data", according to the inventors of the present application, "most of the GIS data is composed of several layers according to the characteristics of the data such as railway, river, road, building, terrain, etc. , Each layer can be expressed with four attributes of points, lines, faces, and texts ("Geographic Information System Watermarking using the Center of Polygon Data" (Jang Hye-Jung, Jang Bong-Ju, Moon Kwang-Suk, Lee Seok-Hwan, Kee-Ryong Kwon) 20th Image Processing and Understanding Workshop, pp. 186, January 2008).

4 is a diagram illustrating GIS vector map data configured in the SHP format used in the GIS vector map data compression method according to an embodiment of the present invention, wherein the GIS vector map data configured in the SHP format file is an attribute. The file is divided into several layers and stored as a file. In an embodiment of the present invention, attributes are largely divided into lines, polylines, polygons, characters, and the like. FIG. 4 is a set of GIS vector map data files for representing a specific administrative area of 1: 1000 scale, in which a plurality of layers are stored in the form of files (LAYERID 0 to 27 on the right side), and each layer is a "polygon". It can be seen that it is divided into attributes such as "polyline", "line", and "point". FIG. 5 illustrates a 1: 1000 scale precision vector map used in the GIS vector map data compression method according to an embodiment of the present invention, and GIS vector map data files for representing the vector map of FIG. Is shown.

The GIS vector map data compression method according to an embodiment of the present invention is applied to a layer having the properties of polygons and polylines with the largest amount of data.

Referring back to FIG. 3, in the GIS map load block 310, the GIS server accesses the geographic information database and loads the GIS vector map data in response to a request from a client.

가 선택된다.Next, in the layer selection block 312, a layer having a property of a polyline and a polygon to which the GIS vector map data compression method according to an embodiment of the present invention is applied is selected from among the plurality of layers shown in FIG. That is, M layers L = with attributes of polylines and polygons in a vector map stored in a geographic database.

Is selected.

In the record extraction block 314, record information is extracted from each layer selected in the layer selection block 312. Each layer file has a file structure as shown in FIG. That is, in the record extraction block 314, record information is extracted from the file structure shown in FIG. 1 of each selected layer. For example, a "general housing" layer file, which is a component of GIS vector map data, a "general housing" layer file consists of a set of polygon (or polyline) properties representing all the generic houses in the area represented by that layer. Can be assumed. In this case, one record information may mean each polygon (or polyline) representing each of these general houses.

의 수 N만큼의 MCA가 생성된다. 이와 같이 생성된 각각의 속성

에 대해서는 추후에 독립적으로 코딩이 수행될 수 있다.In the MCA setting block 316, a "Minimum Coding Attribute (MCA)" is set for each extracted record information. In other words, the properties contained in each layer

The number N of MCAs is generated. Each property created in this way

For, coding may be performed independently later.

In the embodiment of the present invention, in order to compress each record information extracted by the record extraction block 314, the concept of a packet called "Minimum coding attribute (MCA)" is introduced as a compression unit for one record information. . In addition to the record information, such MCA is added with information necessary for compression and decoding. In other words, the MCA is defined as a set together with record information and information necessary for compression and decoding. 6 shows the internal structure of the MCA used in the GIS vector map data compression method according to an embodiment of the present invention.

Referring to FIG. 6, an MCA is composed of an MCA header (2 bytes), an MCA size (2 bytes), the number of points (2 bytes), an MBR code, and a payload. The MCA header is the MCA label number as the identification information of the MCA, the MCA size is the size of the compressed MCA, the MBR code is the MBR (Minimum Bounding Rectangle) coordinate to which the MCA belongs to facilitate data accessibility of the MCA, and the payload (payload) is the coordinate data of a corresponding attribute to be compressed, that is, a polygon (or polyline). In the embodiment of the present invention, since the compression and decompression of the GIS vector map data is performed in MCA units as described above, access to any attribute of any layer is easy even in the compressed data.

및 소수부(decimal portion)

로 분리된다. 여기서, 소수부는 실수(real number)이다.After the MCA is set for each record information in the MCA setting block 316, in the integer division block 320 and the decimal division block 322, all coordinate values constituting each attribute represented by 64-bit floating point. That is, the value indicated by the coordinate data included in the payload of the MCA is an integer portion according to the following equation (1).

And decimal portions

To be separated. Here, the fractional part is a real number.

In Equation 1, c is decimal precision, the first equation of Equation 1 is for separating the integer part from the set of vector coordinates, and the second equation is for integer fractionation.

If the value represented by the coordinate data represented by the 64-bit floating point is immediately compressed, it is difficult to minimize the entropy of the value represented by each coordinate data and the compression efficiency is lowered. Therefore, the present inventor has devised a method of separately compressing the high-purity water purification unit in order to increase the compression efficiency, that is, the compression ratio. More specifically, the coordinate data of the attribute stored in the payload of the MCA is represented by 64-bit floating point, and in order to increase the compression ratio, the coordinate data is separated into an integer part and a real part, and the integer part is spaced in a space domain. Spatial Energy Compaction (SEC) (two-step SEC in the embodiment of the present invention) is performed, and hierarchical compression is performed on the fractional part with various precisions.

As described above, for the purified water separated by Equation 1 by the purified water separating block 320, in the two-step SEC block 330, energy concentration in the spatial domain is performed using the characteristics of the SHP format.

The layer file of the SHP format includes MBR (minimum bounding rectangle) coordinates of a layer in which x- and y-coordinates are represented as axes, and MBR coordinates of attributes in each layer. MBR stands for the minimum bounding rectangle, one in the header of the layer file in SHP format (called "layer MBR"), and one for each record constituting one layer file (called "MCA MBR"). ). The MBR consists of the x-axis coordinate value with the smallest value, the y-axis coordinate value with the smallest value, the x-axis coordinate value with the largest value, and the y-axis coordinate value with the largest value. Since each coordinate value is represented by 64-bit floating point, four coordinate values are represented by 32 bytes in total.

The leftmost figure of FIG. 8 shows an SHP format file of a layer composed of polyline attributes representing roads of a specific area as a GIS map. In the leftmost diagram of FIG. 8, B _{min l m} and B _{max l m} are values of the layer MBR defined in the header of the SHP format file for one layer, and in the middle diagram of FIG. 8, B _minPn and B _maxPn are The value of the MCA MBR for one record content (here, polyline) extracted from the layer of the leftmost figure. In the middle of FIG. 8, I represents the number of coordinate values constituting the polyline.

Next, the operation of the two-step SEC block 330 of FIG. 3 will be described in more detail with reference to FIGS. 7 and 8.

Referring to FIG. 7, since the two-step SEC block 330 according to an embodiment of the present invention uses only the difference value of each coordinate value as valid data, the size of the coordinate values can be reduced. In Fig. 7, the first subtraction blocks 71, 72 represent the first step of the SEC, and the second subtraction block 74 represents the second step of the SEC.

FIG. 8 is a view for explaining the processing principle of the two-step SEC in FIG. 7, and the leftmost diagram shows the GIS vector map of the mth layer, and the middle diagram shows the nth record in the mth layer (here, Polyline), and the rightmost figure shows the coordinate Z _i obtained by two subtractions in the xy plane.

First, in the first subtraction block 71, the layer MBR (B _{min l m} , B _{max l m} ) and the MCA MBR (B _minPn , B) of each record using one layer MBR stored in the header of the SHP format layer file. The difference value between _maxPn ) MCA MBR '(B ^* _minPn , B ^* _maxPn ) is obtained, and the specific process can be expressed by the following Equation 2.

In the first subtraction block 71, MCA MBR '(B ^* _minPn , B ^* _maxPn ), which is a difference value of MCA MBR obtained by Equation 2, has a positive sign in the mth layer to minimize entropy. It is added to the MCA header of the MCA having the structure as shown in FIG.

Next, in another first subtraction block 72, coordinate values (Z _i (x), Z _i (y)) of the integer part obtained by Equation 1 in the integer part separating block 320 of FIG. The difference value Z _i ^* (x), Z _i ^* (y) between the integer parts of the MCA MBR of the corresponding record (called “MCA offset” in the embodiment of the present invention) is represented by the following equation (3). Obtained by The integer portion of the MCA MBR, that is, the MCA offset, is obtained by applying the floor function to _round down the decimal point of the MCA MBR (B _minPn ) of each record.

In Equation 3, floor (B _minPn (x)) and floor (B _minPn (y)) are the MCA offset described above. As a result, in the first subtraction block 72, a coordinate value Z ^* _i having both positive sign values in the integer part P _Zn of the nth polyline is obtained by equation (3). The set P _Zn ′ of the coordinate values Z ^* _i thus obtained is obtained from the output of the first subtraction block 72. Since P _Zn 'is a set of difference values obtained by subtracting the MCA offset from the coordinate value of the integer part of the nth polyline, the start coordinate can be set to (0,0) while maintaining the shape of the corresponding record attribute.

On the other hand, in the embodiment of the present invention, the 2-step SEC is used to further reduce the magnitude of the coordinate value, and in the secondary subtraction block 74 that performs the secondary subtraction on the result of the primary subtraction, the primary The difference value between the coordinate obtained by subtraction and the average value is calculated | required.

In order to average the coordinate values obtained by the first subtraction, the average V storage block 73 _obtains the average V of the coordinate values Z ^* _i output from the first subtraction block 72.

The second subtraction block 74 accepts the set P _Zn ′ of the coordinate values obtained in the first subtraction block 72 and the average V provided by the average V storage block 73, and then, according to the following equation (4): Subtraction is performed using the coordinate value Z ^* _i and the mean V to find the displacement Z ^** _i from the mean of each coordinate value Z ^* _i . This set P _{Zn 의} of the displacement Z ^** _i is obtained at the output side of the secondary subtraction block 74.

In Equation 4, I is the number of coordinate values Z ^* _i .

The displacement Z ^** _i obtained by the above Equation 4 has a sign value, and the sign value of S = {s ₀ , s ₁ , s ₂ , ... s _I }, s _i = [0,1] Stored in a format. This code value is an "X, Y code code" that constitutes the final MCA payload to be compressed, as described later with reference to FIG. The absolute value of the displacement | Z ^** _i | is the "X, Y integer code" that constitutes the final MCA payload to be compressed, as described later with reference to FIG. The absolute value | Z ^** _i | of the displacement is very small compared to the coordinate value Z _i due to its correlation with adjacent coordinates. Thus, by storing or transmitting the displacement obtained by the offset and the difference in the spatial domain, a two-step SEC block 330 implemented as described above provides " energy such as DC coefficients and high frequency components in the frequency domain. Concentration ”may be performed.

Referring again to FIG. 3, the set of sign values S generated by the two-step SEC block 330 and the coordinate values P _Zn 최종 of the final displacement are performed in the parameter rearrangement block 340. Are rearranged and stored within the MCA. More specifically, the parameter rearrangement block 340 rearranges coordinate data of the integer part to be finally compressed and information necessary for decoding, and rearranges the coordinate elements for maximizing the compression ratio shown in FIG. 10.

As described above, the integer portion P _Zn of the MCA coordinate data is converted into final compression target data by two-step SEC and parameter rearrangement. In general, even if the GIS vector map data to be decoded at the client includes only an integer part, a large problem does not occur in constructing geographic information. When the GIS vector map data includes only the integer part, it is also possible to apply hierarchical compression to the integer part according to the magnification of the map data.

As shown in Fig. 3, the processing by the hierarchical compression block 342 is performed on the fractional portion P _Rn of the MCA coordinate data. In an embodiment of the present invention, by applying hierarchical compression only to the fractional part P _Rn of the MCA coordinate data, the precision of the fractional part may be varied according to the precision required by the client. In the embodiment of the present invention, it is assumed that the precision is determined in units of 1 byte, but the unit of determination of the precision may be changed in some cases.

In the hierarchical compression block 342, the following equation (5) is applied to the fractional portion Ri obtained by the equation (1).

Dn (R _i ) = (R _i >> 8n) & 0xFF

In more detail, the procedure performed by Equation 5 is described in detail. Each fractional portion R _i , which is integerized by Equation 1, is shifted by 8 bits, the precision is divided by one byte unit, and is represented by one record unit. Rearranged as 9

For example, if the x-axis fractional part of the first coordinate value of a particular record is 0.123456, it will be rkqtdms 123456 of the fractionalized fraction R _i . This value is expressed as 0x1E240 in hexadecimal hexadecimal code. Thus, this number can be divided into three layers with 8-bit precision.

Referring to the above description in connection with FIG. 9, K in FIG. 9 is a hierarchy and K = 3. I is the total number of coordinate values of the record, and the fractional part R _i is the i-th coordinate value of the record.

Therefore, if the x-axis coordinate of the first coordinate value R ₀ of the decimal part is defined as r _{0 , x} and is represented in the format of FIG. 9, the byte D corresponding to each layer is substituted as follows.

D ₀ (r _{0 , x} ) = 0x1E, D ₁ (r _{0 , x} ) = 0x24, D ₂ (r _{0 , x} ) = 0x00

For final transmission, the precision may be adjusted by not compressing / transmitting the fractional data according to the precision or by accumulating / compressing by selecting up to D ₀ to D ₂ groups.

As described above, the integer part data and the fractional part data processed in the parameter rearrangement block 340 and the hierarchical compression block 342, respectively, are losslessly compressed by the entropy coding block 350. For lossless compression, an existing lossless compression algorithm may be used, and in embodiments of the present invention, zlib (http://zlib.net/, April 2009) or 7zip (http://7-zip.org /, June 2009) The algorithm is used as an entropy coder.

Finally, in the file recording / packetizing block 360, a process of recording compressed data into a file or packetizing it into packets for transmission is performed. When recording compressed data to a file, recording is performed in accordance with the file structure of the SHP format described above. Here, the record header and record information of the SHP format are replaced with the data of the compressed layer of the format as shown in FIG. Accordingly, unlike the existing SHP format shown in FIG. 1, the record header portion is composed of an MCA header, an MCA size, the number of points, an MBR code, and the like, and the record contents correspond to the payload portion. The data added to the payload is meaningless as it is a compressed bit stream, and the data before and after decompression (decoding) is as shown in FIG.

In order to evaluate the compression efficiency of the GIS vector map data compression method according to an embodiment of the present invention, the present inventors measured the amount of change of the vector map before and after compression through the root mean square error (RMS), The compression rate was calculated for several layers with the property of line, and the compression rate was also calculated for various precision considering transmission. Compression was also performed on SHP-format files created in other environments, confirming that compatibility and high compression rates were achievable.

FIG. 11 illustrates a layer in which the attributes extracted from the precision vector map of FIG. 5 used in the compression experiment of the GIS vector map data compression method according to an embodiment of the present invention are polygons and polylines. (A) is a high speed road, (b) is a city road, (c) is a general road, (d) is a 100m elevation line. All layers shown in FIG. 11 have a scale of 1: 1000 and a precision of c = 6.

Table 1 below shows the attribute information of FIG. 11 and the compression results of applying the zlib and 7zip compression algorithms to the compression method according to the embodiment of the present invention, respectively. In addition, Table 2 below shows the size of the final output file by comparing the conventional general data compression method and the other compression method according to the embodiment of the present invention.

Attribute (count) Source file
(byte) Compressed data
File (zlib) Compressed data
File (7z) RMSE (a) Polyline
(127) 43,228 25,495 24,429 0 (b) Polyline
(99) 41,760 26,858 25,360 0 (c) Polyline
(1140) 515,424 325,066 300,499 0 (d) Polygons
(22) 213,860 90,232 83,142 0

Source data Invention
( zlib ) Invention
(7z) 7z zip rar gz (a) 43 25 24 26 30 29 30 (b) 47 27 25 30 35 34 35 (c) 566 333 302 306 414 395 415 (d) 213 92 84 86 156 93 156

From Table 1 and Table 2, it can be seen that energy concentration was efficiently performed in the compression method of the present invention as compared to the conventional general compression method. In addition, in the compression method of the present invention, since most encoding processes are performed by + /-/ Shift operations, satisfactory results are obtained even in the real time of the compression process.

Next, Table 3 shows the results of the lossless compression and the selective layer-specific compression for (c) and (d) which have a lot of attribute and coordinate information among the layers shown in FIG. 11. The compression ratio was calculated for pure coordinates except for all headers and fields in each layer, and the reduced amount was calculated based on the data size of the original layer. In particular, Table 3 shows the results of experiments classified into 1 to 4 layers according to the amount of bits transmitted with 8-bit precision and 20-bit depth.

4 tiers
(all) 3 tiers
(16 bit) 2 tiers
(8 bit) 1 tier
(0 bit)

(c)
zlib
(%) 325,066
(64.31) 254,324
(49.34) 216,278
(41.96) 149,703
(29.04) 7z
(%) 300,499
(58.30) 284,110
(55.12) 213,209
(41.37) 129,729
(25.17) RMSE 0.0 0.0027 0.0453 0.7076

(d)
zlib
(%) 90,232
(42.46) 86,178
(40.55) 66,418
(31.25) 41,330
(19.45) 7z
(%) 83,142
(39.12) 73,389
(34.53) 45,794
(21.55) 23,454
(11.04) RMSE 0.0 0.0031 0.0501 0.7823

As shown in Table 3, when lossless compression is performed using the compression method of the present invention, i.e., when all layers of the precision map data are transmitted, the amount of data is on average about 65% of the original data. It can be seen that a data compression ratio of 35% is achieved. In addition, Table 3 numerically shows data compression ratio and RMSE when transmitting data hierarchically according to a user's request, and on the third layer, twice the compression efficiency is achieved on average, Compression efficiencies of at least -9 times were achieved. On the other hand, it can be seen that the RMSE, which is a measure of error, was hardly shown.

12 illustrates original vector map data and one-layer compressed and transmitted vector map data before applying the GIS vector map data compression method according to an embodiment of the present invention. FIG. It is shown enlarged. (A) of FIG. 12 is original vector map data, and (b) is vector map data transmitted by one layer compression. Comparing Figs. 12A and 12B, it can be seen that even though the compression method of the present invention is applied to one layer, the vector map data is almost identical.

This shows that general users who use Web-GIS, mobile-GIS, or navigation can be provided with sufficient service with little sense of scale error even if they transmit only one-layer compressed vector map data.

In addition, in the compression method of the present invention, a real number operation is hardly performed, and since the access to the accurate vector map data for the desired area on the actual map is possible without restoring the compressed data, it is useful for real time processing. In addition, since it is possible to apply a simple compression module to the existing SHP format, it is possible to apply the compression method of the present invention while maintaining the existing system to the maximum.

The above-described GIS vector map data compression method of the present invention may be implemented by a computer program. In addition, the computer program may be used in various computer readable storage media such as floppy disk, hard disk, magnetic disk, CD-ROM, CD-R / W, DVD-ROM, DVD-R / W, USB storage media, and web hard disk. Can be stored.

So far, the configuration and operation of the embodiment of the present invention have been described. The present invention is not limited to the above-described embodiments, and various modifications may be made without departing from the scope of the present invention. Therefore, the scope of the present invention should not be limited to the described embodiments, but should be defined not only by the claims but also by the equivalents of the claims.

1 is a diagram showing the structure of an SHP file for representing vector map data in a general binary format.

2 is a service flow diagram for explaining a process of a general GIS vector map service.

3 is a block diagram illustrating a GIS vector map data compression method according to an embodiment of the present invention.

4 is a diagram illustrating GIS vector map data configured in an SHP format used in a GIS vector map data compression method according to an embodiment of the present invention.

5 is a diagram illustrating a 1: 1000 scale precision vector map used in the GIS vector map data compression method according to an embodiment of the present invention.

FIG. 6 is a diagram illustrating an internal structure of a minimum coding attribute (MCA) used in a GIS vector map data compression method according to an embodiment of the present invention.

FIG. 7 is a block diagram illustrating a detailed configuration of the two-step spatial energy compaction (SEC) block of FIG. 3.

FIG. 8 is a diagram illustrating a processing result in the two-step SEC block of FIG. 7.

FIG. 9 is a diagram for explaining a principle of rearranging decimal parts in the hierarchical compression block of FIG. 3.

FIG. 10 is a diagram illustrating a processing principle in the entropy coding block of FIG. 3.

11 illustrates (a) highway, (b) downtown road, (c) general road, and (d) 100m elevation above sea level among layers used in GIS vector map data compression method according to an embodiment of the present invention. Drawing.

12 is a diagram illustrating original vector map data and one-layer compressed vector map data before the GIS vector map data compression method according to an embodiment of the present invention is applied.

Claims (11)

(a) Loading a geographic information database storing a plurality of layer files classified according to a plurality of properties to select a layer having the properties of polyline and polygon, and record information from each of the selected layers Extracting; (b) setting a minimum coding attribute (MCA) for each record information extracted in step (a); (c) extracting a coordinate value of an attribute included in each minimum coding attribute and constituting a part of the record content from each minimum coding attribute set in step (b), and the integer part and the decimal part of the extracted coordinate value Separating the; (d) 2-step space using the minimum boundary rectangle (MBR) coordinate value of each layer and the minimum boundary rectangle coordinate value of each attribute in each layer, for the integer part of the attribute coordinate value obtained in step (c). Performing region energy concentration and rearranging the displacement data and the sign data generated by the two-step spatial region energy concentration with information necessary for decoding; (e) For the fractional part of the attribute coordinate value obtained in step (c), the precision of the compression is determined, and the fractional part of the attribute coordinate value is grown in one record unit using a predetermined shift operation and the determined compression precision. Heating; And (f) compressing the integer part data and the fractional part data of the attribute coordinate values processed by steps (d) and (e) by a predetermined entropy coder. Vector map data compression method of geographic information system. The method of claim 1, The geographic information database is connected to a geographic information system server that provides geographic information services upon request from a client. Vector map data compression method of geographic information system. The method of claim 1, The minimum coding attribute is a set of corresponding record information and information necessary for compression and decoding. Vector map data compression method of geographic information system. The method of claim 3, wherein The minimum coding attribute consists of a minimum coding attribute header, a minimum coding attribute size, a number of points, a minimum bounding rectangle code of the attribute, and a payload Vector map data compression method of geographic information system. The method of claim 4, wherein The payload includes coordinate data of the attribute to be compressed. Vector map data compression method of geographic information system. The method of claim 1, In the step (c), the separation of the integer part and the fractional part of the extracted coordinate value is performed by the following equation,

Where c is the decimal precision The first equation is used to separate the integer parts from the set of vector coordinates, and the second equation is used to integer the fraction parts. Vector map data compression method of geographic information system. The method of claim 1, In the step (d), the two-step spatial region energy concentration is (g) subtract between the minimum bounding rectangle coordinate value (layer MBR) of each layer and the minimum bounding rectangle coordinate value (MCA MBR) of each property in each layer, and the result is added to the header of the minimum coding attribute. Adding; (h) subtracting between the coordinate values of the integer part separated in step (c) and the integer part of the MCA MBR of the attribute; And (i) obtaining an average value of the coordinate values obtained by the subtraction in step (h), subtracting using the coordinate value and the average value obtained in step (h), and each coordinate value obtained in step (h) By the step of finding the displacement and its sign from the mean value of Vector map data compression method of geographic information system. The method of claim 7, wherein Subtraction in step (g) is performed by the following equation

Where B _{min l m} and B _{max l m} are the minimum bounding rectangle coordinates of each layer, and B _minPn and B _maxPn are the minimum bounding rectangle coordinates of any property in any layer. Vector map data compression method of geographic information system. The method of claim 7, wherein Subtraction in step (h) is performed by the following equation

(Where, Z _i (x), Z _i (y) is the coordinate value of the integer part separated in step (c), and the floor function is a function to _round down the decimal point of MCA MBR (B _minPn )) Vector map data compression method of geographic information system. The method of claim 7, wherein Subtraction in step (i) is performed by the following equation

(Wherein Z ^* _i is the coordinate value obtained in step (h) and I is the number of the coordinate value Z ^* _i ) Vector map data compression method of geographic information system. A computer-readable recording medium storing a program including each step of the vector map data compression method of the geographic information system according to claim 1.

Images