Nothing Special   »   [go: up one dir, main page]

KR20100007685A - Fast 3d mesh coding apparatus using connectivity analysis and method thereof - Google Patents

Fast 3d mesh coding apparatus using connectivity analysis and method thereof Download PDF

Info

Publication number
KR20100007685A
KR20100007685A KR1020080125428A KR20080125428A KR20100007685A KR 20100007685 A KR20100007685 A KR 20100007685A KR 1020080125428 A KR1020080125428 A KR 1020080125428A KR 20080125428 A KR20080125428 A KR 20080125428A KR 20100007685 A KR20100007685 A KR 20100007685A
Authority
KR
South Korea
Prior art keywords
mesh model
information
vertex
connection information
encoding
Prior art date
Application number
KR1020080125428A
Other languages
Korean (ko)
Other versions
KR101048368B1 (en
Inventor
이승욱
구본기
장의선
김대용
김병준
손경수
Original Assignee
한국전자통신연구원
한양대학교 산학협력단
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by 한국전자통신연구원, 한양대학교 산학협력단 filed Critical 한국전자통신연구원
Publication of KR20100007685A publication Critical patent/KR20100007685A/en
Application granted granted Critical
Publication of KR101048368B1 publication Critical patent/KR101048368B1/en

Links

Images

Classifications

    • GPHYSICS
    • G06COMPUTING; CALCULATING OR COUNTING
    • G06TIMAGE DATA PROCESSING OR GENERATION, IN GENERAL
    • G06T9/00Image coding
    • G06T9/001Model-based coding, e.g. wire frame
    • GPHYSICS
    • G06COMPUTING; CALCULATING OR COUNTING
    • G06TIMAGE DATA PROCESSING OR GENERATION, IN GENERAL
    • G06T17/00Three dimensional [3D] modelling, e.g. data description of 3D objects
    • G06T17/20Finite element generation, e.g. wire-frame surface description, tesselation
    • HELECTRICITY
    • H03ELECTRONIC CIRCUITRY
    • H03MCODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M7/00Conversion of a code where information is represented by a given sequence or number of digits to a code where the same, similar or subset of information is represented by a different sequence or number of digits
    • H03M7/30Compression; Expansion; Suppression of unnecessary data, e.g. redundancy reduction
    • H03M7/3002Conversion to or from differential modulation
    • H03M7/3044Conversion to or from differential modulation with several bits only, i.e. the difference between successive samples being coded by more than one bit, e.g. differential pulse code modulation [DPCM]
    • H03M7/3046Conversion to or from differential modulation with several bits only, i.e. the difference between successive samples being coded by more than one bit, e.g. differential pulse code modulation [DPCM] adaptive, e.g. adaptive differential pulse code modulation [ADPCM]
    • HELECTRICITY
    • H04ELECTRIC COMMUNICATION TECHNIQUE
    • H04NPICTORIAL COMMUNICATION, e.g. TELEVISION
    • H04N19/00Methods or arrangements for coding, decoding, compressing or decompressing digital video signals
    • H04N19/10Methods or arrangements for coding, decoding, compressing or decompressing digital video signals using adaptive coding
    • H04N19/102Methods or arrangements for coding, decoding, compressing or decompressing digital video signals using adaptive coding characterised by the element, parameter or selection affected or controlled by the adaptive coding
    • H04N19/124Quantisation
    • HELECTRICITY
    • H04ELECTRIC COMMUNICATION TECHNIQUE
    • H04NPICTORIAL COMMUNICATION, e.g. TELEVISION
    • H04N19/00Methods or arrangements for coding, decoding, compressing or decompressing digital video signals
    • H04N19/10Methods or arrangements for coding, decoding, compressing or decompressing digital video signals using adaptive coding
    • H04N19/102Methods or arrangements for coding, decoding, compressing or decompressing digital video signals using adaptive coding characterised by the element, parameter or selection affected or controlled by the adaptive coding
    • H04N19/13Adaptive entropy coding, e.g. adaptive variable length coding [AVLC] or context adaptive binary arithmetic coding [CABAC]
    • HELECTRICITY
    • H04ELECTRIC COMMUNICATION TECHNIQUE
    • H04NPICTORIAL COMMUNICATION, e.g. TELEVISION
    • H04N19/00Methods or arrangements for coding, decoding, compressing or decompressing digital video signals
    • H04N19/10Methods or arrangements for coding, decoding, compressing or decompressing digital video signals using adaptive coding
    • H04N19/134Methods or arrangements for coding, decoding, compressing or decompressing digital video signals using adaptive coding characterised by the element, parameter or criterion affecting or controlling the adaptive coding
    • H04N19/136Incoming video signal characteristics or properties
    • H04N19/14Coding unit complexity, e.g. amount of activity or edge presence estimation

Landscapes

  • Engineering & Computer Science (AREA)
  • Multimedia (AREA)
  • Theoretical Computer Science (AREA)
  • Signal Processing (AREA)
  • Physics & Mathematics (AREA)
  • General Physics & Mathematics (AREA)
  • Computer Graphics (AREA)
  • Geometry (AREA)
  • Software Systems (AREA)
  • Compression Or Coding Systems Of Tv Signals (AREA)
  • Compression, Expansion, Code Conversion, And Decoders (AREA)
  • Compression Of Band Width Or Redundancy In Fax (AREA)

Abstract

PURPOSE: A device and a method for encoding a 3D mesh model by analyzing connection information are provided to apply differential pulse code modulation and arithmetic encoding or determining bit encoding through analysis of a shared vertex without performing phase incision, thereby improving compression complexity of 3D model data and improving a compression rate. CONSTITUTION: A data analyzer(100) separates a vertex, an attribute and vertex connection information configuring a 3D mesh model from data of a 3D mesh model. A mesh model quantization unit(102) uses the information to generate a quantized vertex, attribute and connection information. A differential pulse code modulation unit(106) analyzes a sharing vertex of consecutive connection information of the 3D mesh model according to the quantized connection information to perform differential pulse code modulation. An entropy encoder(108) arithmetically encodes the quantized vertex, attribute information and connection information which is different-pulse-code modulated to output binary arithmetic or determining bit encoded data.

Description

연결정보 분석을 통한 3차원 메쉬 모델의 부호화 장치 및 방법{FAST 3D MESH CODING APPARATUS USING CONNECTIVITY ANALYSIS AND METHOD THEREOF}Coding apparatus and method for 3D mesh model through connection information analysis {FAST 3D MESH CODING APPARATUS USING CONNECTIVITY ANALYSIS AND METHOD THEREOF}

본 발명은 영상 압축에 관한 것으로, 특히 3차원 모델의 정점 정보를 양자화 하고, 3차원 메쉬 모델을 이루는 연결 정보는 공유 정점 분석(Sharable Vertex Analysis :SVA)를 통해 공유된 정점을 제외한 나머지 값을 차분 펄스 코드 변조(Difference Pulse Code Modulation : DPCM) 및 (이진) 산술부호화 혹은 결정비트(Bit Precision) 부호화를 진행하는 3차원 메쉬 모델의 부호화 장치 및 방법에 관한 것이다.The present invention relates to image compression, and in particular, quantizes vertex information of a three-dimensional model, and the connection information constituting the three-dimensional mesh model differs from the remaining values except for shared vertices through shared vertex analysis (SVA). The present invention relates to an apparatus and method for encoding a 3D mesh model that performs pulse code modulation (DPCM) and (binary) arithmetic coding or bit precision coding.

본 발명은 지식경제부 및 정보통신연구진흥원의 IT신성장동력핵심기술개발사업의 일환으로 수행한 연구로부터 도출된 것이다[과제관리번호: 2008-F-030-01, 과제명: 방통융합형 Full 3D 복원 기술 개발].The present invention is derived from the research conducted as part of the IT new growth engine core technology development project of the Ministry of Knowledge Economy and the Ministry of Information and Telecommunication Research and Development. [Task management number: 2008-F-030-01] Technology development].

현재, 컴퓨터 그래픽스 분야에서 3차원 영상을 표현하는 방법으로, 삼각형 메쉬(Triangular Mesh)가 널리 이용되고 있다. 삼각형 메쉬 영상은 불균일한 구조로 인해 삼각형을 형성하는 꼭지점 들의 위치 정보(Geomety information) 및 꼭지 점들 간의 연결 정보(connectivity information)로 구성되어, 균일한 구조를 가진 이차원 영상에 비해 데이터량이 매우 크다.Currently, a triangular mesh is widely used as a method of representing a 3D image in the field of computer graphics. The triangular mesh image is composed of geographic information of the vertices forming the triangle and connectivity information between the vertices due to the non-uniform structure, so that the amount of data is much larger than a two-dimensional image having a uniform structure.

따라서, 삼각형 메쉬 영상의 저장 및 전송의 문제점을 해소하기 위하여 많은 연구가 활발히 진행되고 있다.Therefore, many studies have been actively conducted to solve the problem of storing and transmitting a triangle mesh image.

한편, 이와 같이, 3차원 메쉬 모델을 이용한 3차원 그래픽스 분야는 최근 들어 많이 사용되고 있으나, 3차원 메쉬 모델을 사용함에 있어서 그 정보량의 방대함 때문에 그 사용 범위가 제한되어 있다. On the other hand, in the field of three-dimensional graphics using a three-dimensional mesh model in recent years, the use of the three-dimensional mesh model is limited because of the vast amount of information in the use of the three-dimensional mesh model.

이는, 32비트 부동소수점으로 3차원 메쉬 모델의 기하 정보가 표현된다고 가정하면, 하나의 기하 정보를 표현하기 위하여 96비트, 즉 12바이트의 메모리 공간이 필요하다. 이는, 3차원 모델이 기하 정보만을 가지는 1만 개의 정점에 의해 표현된다면 120KB를 필요로 하고, 10만 개의 정점에 의해 표현된다면 1.2MB의 메모리가 필요하게 됨을 의미한다.This assumes that geometric information of a 3D mesh model is represented by 32-bit floating point, and 96 bits, or 12 bytes of memory space are required to represent one geometric information. This means that if the three-dimensional model is represented by 10,000 vertices having only geometric information, 120 KB is required, and 1.2 MB of memory is required if represented by 100,000 vertices.

또한, 연결정보는 2번 이상의 중복을 허용하기 때문에 다각형 메쉬에 의한 3차원 모델을 저장하기 위해서는 매우 많은 메모리를 필요로 하게 된다.In addition, since the connection information allows two or more overlaps, very much memory is required to store the 3D model by the polygon mesh.

따라서, 이러한 정보들의 방대함으로 인하여 3차원 영상의 압축에 있어서 부호화의 필요성이 대두되었다. 이를 위하여, MPEG-4(Moving Picture Expert Group-4) - 3DGC(3 Dimensional Graphics Compression) 분야에서 ISO/IEC(International Organization for Standardization/International Electrotechnical Compression)의 표준안으로 채택된 3차원 메쉬 코딩(3D Mesh Coding:3DMC) 방식은 가상 언어 모델링 언어(Virtual Reality Modeling Language:VRML) 파일 내에 인덱스드 페이스 셋(IndexedFaceSet:IFS)으로 표현되는 3차원 모델의 메쉬 정보를 부호화 및 복호화 함으로써 3차원 메쉬 정보에 대한 데이터의 전송 효율을 향상시킨다.Therefore, the necessity of encoding has arisen in the compression of 3D images due to the enormous amount of such information. To this end, MPEG-4 (Moving Picture Expert Group-4)-3D Mesh Coding has been adopted as a standard of ISO / IEC (International Organization for Standardization / International Electrotechnical Compression) in the field of 3 Dimensional Graphics Compression (3DGC). The: 3DMC method encodes and decodes the mesh information of a three-dimensional model represented by an indexed faceset (IFS) file in a virtual language modeling language (VRML) file. Improve the transmission efficiency

따라서, 본 발명은 위상절개를 수행하지 않으면서, 공유된 정점의 분석을 통해서 차분 펄스 코드 변조와 (이진)산술 부호화 혹은 결정 비트(Bit Precision) 부호화를 적용하여 3차원 모델의 데이터 압축의 복잡도를 개선하고, 압축률 향상시키는 연결정보 분석을 통한 실시간 3차원 메쉬 모델의 부호화 장치 및 방법을 제공하고자 한다. Therefore, the present invention applies the differential pulse code modulation and the (binary) arithmetic coding or the decision bit (bit precision) coding to analyze the complexity of the data compression of the three-dimensional model without performing the phase cutting. An object of the present invention is to provide an apparatus and method for encoding a real-time three-dimensional mesh model through connection information analysis that improves and improves a compression ratio.

상술한 본 발명은 3차원 메쉬 모델의 부호화 장치로서, 입력된 3차원 메쉬 모델의 데이터로부터 고유의 정점 정보, 상기 3차원 메쉬 모델의 고유의 특성을 나타내는 속성 정보 및 상기 3차원 메쉬 모델을 구성하는 정점들 간의 연결 정보로 분리하는 데이터 분석부; 상기 데이터 분석부로부터 분석된 상기 3차원 메쉬 모델의 정점 정보, 속성 정보 및 상기 3차원 메쉬 모델의 정점들 간의 연결 정보를 이용하여 양자화된 정점 정보, 속성 정보 및 연결 정보를 생성하는 메쉬 모델 양자화부; 상기 메쉬 모델 양자화부에서 양자화된 연결 정보에 따라 상기 3차원 메쉬 모델의 연속된 연결 정보의 Sharable Vertex Analysis를 이용하여차분 펄스 코드 모 듈레이션 예측을 수행하는 차분 펄스 코드 모듈레이션 예측 수행부; 및 상기 양자화된 3차원 메쉬 모델의 정점 정보, 속성 정보 및 상기 차분 펄스 코드 모듈레이션된 연결 정보를 (이진)산술 부호화하여 상기 3차원 메쉬 모델의 이진 산술 부호화 혹은 결정 비트 부호화된 데이터를 비트스트림 형태로 출력하는 엔트로피 부호화부를 포함한다.The present invention as described above is an apparatus for encoding a three-dimensional mesh model, comprising the unique vertex information, the attribute information representing the unique characteristics of the three-dimensional mesh model and the three-dimensional mesh model from the input data of the three-dimensional mesh model. A data analyzer which separates the connection information between the vertices; Mesh model quantization unit for generating quantized vertex information, attribute information and connection information using the vertex information, the attribute information and the connection information between the vertices of the three-dimensional mesh model analyzed by the data analysis unit ; A differential pulse code modulation prediction execution unit configured to perform differential pulse code modulation prediction using Sharable Vertex Analysis of continuous connection information of the 3D mesh model according to the connection information quantized by the mesh model quantization unit; And (binary) arithmetic-encode the vertex information, the attribute information, and the differential pulse code modulated connection information of the quantized three-dimensional mesh model to convert the binary arithmetic coding or decision bit-coded data of the three-dimensional mesh model into a bitstream form. It includes an output entropy encoder.

본 발명에서는 3차원 메쉬 모델의 부호화에 있어서, 위상절개 과정을 수행하지 않으며, 페이스간은 공유된 정점정보를 이용하여 차분 펄스 코드 변조와 (이진)산술 부호화 및 결정 비트 부호화를 적용함으로써 3차원 모델의 복잡도를 개선하고 압축률을 향상시킬 수 있으며, 상기 압축의 복잡도 개선에 따라서 압축된 3차원 모델을 신속하고 정확하게 복원시킬 수 있으므로, 인력과 자원의 소모의 효율을 향상시키는 효과가 있다. In the present invention, in the encoding of a 3D mesh model, a phase cutting process is not performed, and the face is a 3D model by applying differential pulse code modulation, (binary) arithmetic coding, and decision bit coding using shared vertex information. It is possible to improve the complexity of the compression and improve the compression ratio, and according to the improvement of the complexity of the compression can be quickly and accurately reconstructed the compressed three-dimensional model, there is an effect of improving the efficiency of the consumption of manpower and resources.

이하, 첨부된 도면을 참조하여 본 발명의 동작 원리를 상세히 설명한다. 하기에서 본 발명을 설명함에 있어서 공지 기능 또는 구성에 대한 구체적인 설명이 본 발명의 요지를 불필요하게 흐릴 수 있다고 판단되는 경우에는 그 상세한 설명을 생략할 것이다. 그리고 후술되는 용어들은 본 발명에서의 기능을 고려하여 정의된 용어들로서 이는 사용자, 운용자의 의도 또는 관례 등에 따라 달라질 수 있다. 그 러므로 그 정의는 본 명세서 전반에 걸친 내용을 토대로 내려져야 할 것이다. Hereinafter, with reference to the accompanying drawings will be described in detail the operating principle of the present invention. In the following description of the present invention, when it is determined that a detailed description of a known function or configuration may unnecessarily obscure the subject matter of the present invention, the detailed description thereof will be omitted. Terms to be described later are terms defined in consideration of functions in the present invention, and may be changed according to intentions or customs of users or operators. Therefore, the definition should be made based on the contents throughout the specification.

도 1은 연결정보 분석을 통한 실시간 3차원 메쉬 부호화 장치의 블록 구성을 도시한 것으로, 본 발명의 3차원 메쉬 부호화 장치는 입력신호의 데이터를 분석하여 정점정보와 연결정보, 부가정보를 분석하여 정점 정보로 표현될 수 있는 부분은 메쉬 부호화를 시키고 연결정보로 구성된 부분에 대해서 공유 정점 분석(sharable vertex analysis)를 수행하는 부분과 이러한 데이터를 엔트로피 부호화시키는 부분으로 구성되어 있다. 1 is a block diagram of a real-time three-dimensional mesh encoding apparatus through connection information analysis. The three-dimensional mesh encoding apparatus of the present invention analyzes vertex information, connection information, and additional information by analyzing data of an input signal. The information that can be expressed is composed of a part of performing mesh coding and performing shared vertex analysis on the part of the connection information and the part of entropy encoding such data.

위 도 1을 참조하면, 데이터 분석부(100)는 입력된 3차원 메쉬 모델의 데이터로부터 3차원 메쉬 모델을 구성하는 고유의 정점 정보, 3차원 메쉬 모델의 고유의 특성을 나타내는 속성 정보 및 3차원 메쉬 모델을 구성하는 정점들간 연결정보를 분리한다. 또한, 데이터 분석부(100)는 3차원 메쉬 모델의 복잡도를 연산하여 3차원 메쉬 모델의 복잡도 값이 미리 설정된 기준 복잡도 값을 초과하는 경우 3차원 메쉬 모델을 복수개의 부분 메쉬로 분할한다.Referring to FIG. 1, the data analyzer 100 may include unique vertex information constituting a three-dimensional mesh model, attribute information indicating a characteristic of the three-dimensional mesh model, and three-dimensional information from the input data of the three-dimensional mesh model. Separate connection information between vertices that make up the mesh model. In addition, the data analyzer 100 calculates the complexity of the 3D mesh model and divides the 3D mesh model into a plurality of partial meshes when the complexity value of the 3D mesh model exceeds a preset reference complexity value.

메쉬 모델 양자화부(102)는 데이터 분석부(100)로부터 분석된 3차원 메쉬 모델의 정점 정보, 속성 정보 및 3차원 메쉬 모델의 정점들간 연결정보를 이용하여 양자화된 정점 정보, 속성 정보 및 연결정보를 생성한다. 이때 위 연결정보는 복수 개의 정점 정보가 하나의 다각형을 형성하는 인덱스 리스트로 표현되며, 속성정보는 다각형으로 이루어지는 3차원 메쉬 모델의 법선, 색상 및 텍스쳐(texture) 좌표 를 포함한다.The mesh model quantization unit 102 uses the vertex information, the attribute information of the three-dimensional mesh model analyzed by the data analysis unit 100, and the connection information between the vertices of the three-dimensional mesh model. Create In this case, the above connection information is expressed as a list of indexes in which a plurality of vertex information forms a polygon, and the attribute information includes normals, colors, and texture coordinates of a 3D mesh model composed of polygons.

공유 정점 분석부(104)는 3차원 메쉬 모델의 정점들간 공유 정보를 분석한다. 차분 펄스 코드 변조부(difference pulse code modulation)(106)는 메쉬 모델 양자화부(102)에서 양자화된 연결정보에 따라 3차원 메쉬 모델의 연속된 연결정보의 공유 정점 분석(sharable vertex analysis)을 이용하여 차분 펄스 코드 변조 예측을 수행한다.The shared vertex analyzing unit 104 analyzes shared information between vertices of the 3D mesh model. The differential pulse code modulation unit 106 uses a shared vertex analysis of the continuous connection information of the three-dimensional mesh model according to the connection information quantized by the mesh model quantization unit 102. Perform differential pulse code modulation prediction.

엔트로피 부호화부(108)는 메쉬 모델 양자화부(102)에서 양자화된 3차원 메쉬 모델의 정점 정보, 속성 정보 및 차분 펄스 코드 변조된 연결정보를 (이진)산술 부호화하여 3차원 메쉬 모델의 이진 산술 부호화 혹은 결정 비트 부호화된 데이터를 비트스트림(bit stream) 형태로 출력한다. The entropy encoder 108 performs (binary) arithmetic coding on the vertex information, the attribute information, and the differential pulse code modulated connection information of the three-dimensional mesh model quantized by the mesh model quantization unit 102 to perform binary arithmetic coding on the three-dimensional mesh model. Alternatively, the decision bit-coded data is output in the form of a bit stream.

이하, 공유정점 분석(Sharable Vertex Analysis :SVA) 과정을 보다 상세히 설명하기로 한다. Hereinafter, the shared vertex analysis (SVA) process will be described in more detail.

SVA는 이전 페이스(face)와 현재 페이스 간의 정점 정보를 분석하여 정점들간의 중복성을 제거하는 방법으로, Type 정보를 구하는 수식은 아래 [수학식1]과 같다.SVA is a method of removing the redundancy between the vertices by analyzing the vertex information between the previous face and the current face, the equation for obtaining the type information is shown in Equation 1 below.

Figure 112008085113561-PAT00001
Figure 112008085113561-PAT00001

Type 정보는 도 2에 도시된 바와 같이, 이전 페이스와 현재 페이스간의 공유되는 정점의 수를 이용하여 계산된다. 예를 들어, 이전 페이스의 정점 인덱스가 (0, 1, 2) 이고 현재 페이스의 정점 인덱스가 (2, 3, 0) 일 때, 인덱스 "0"과 "2" 즉 두개의 인덱스가 공유되므로 Type 2가 선택된다. 이러한 Type 정보는 Type0, Type1, Type2, Type3 의 4가지 정보로 표현된다.Type information is calculated using the number of vertices shared between the previous face and the current face, as shown in FIG. For example, when the vertex index of the previous face is (0, 1, 2) and the vertex index of the current face is (2, 3, 0), the index "0" and "2", that is, two indexes are shared, so Type 2 is selected. This type information is represented by four types of information: Type0, Type1, Type2, and Type3.

이 두 데이터간의 공유 관계를 이용하여 부호화된 데이터를 부호화/복호화 하기 위해서는 위치(position) 정보, 방향(face direction) 정보 그리고 공유되지 않는 두 정점 인덱스간의 차분값이 필요하다. 위치 정보는 삼각형 메쉬의 경우 0, 1, 2의 3가지 값 중 하나로 표현된다. Type1에서는 인덱스 값이 같은 위치 정보, Type2에서는 다른 위치 정보를 부호화한다. 방향 정보는 현재 페이스의 방향이 이전 페이스와 같은 방향인지, 다른 방향인지를 나타내고, 이는 0과 1로 표현된다. 인덱스간의 차분값은 정보량을 줄이기 위해 써큘러 디퍼런스(circular difference)값을 부호화한다. 이렇게 적용된 차분값(difference value)를 DIV(Differential Index Value)로 정의한다. In order to encode / decode data encoded using the sharing relationship between the two data, position information, face direction information, and a difference value between two unshared vertex indices are required. The location information is represented by one of three values of 0, 1, and 2 for the triangle mesh. In Type1, location information having the same index value is encoded. In Type2, different location information is encoded. The direction information indicates whether the direction of the current face is the same or different direction as the previous face, which is represented by 0 and 1. The difference between the indexes encodes a circular difference value to reduce the amount of information. The difference value thus applied is defined as DIV (Differential Index Value).

즉, 위 도 2를 참조하면, Type 0은 이전 페이스와 현재 페이스간의 공유된 정점이 하나도 없을 때를 나타낸다. 이러한 데이터를 부호화하기 위해서는, Type information(모드 정보), 세 개의 DIV를 이용하여 부호화한다.That is, referring to FIG. 2 above, Type 0 indicates when there is no shared vertex between the previous face and the current face. In order to encode such data, encoding is performed using Type information (mode information) and three DIVs.

Type 1은 이전 페이스와 현재 페이스간의 공유된 정점이 하나일 때를 나타낸다. 이러한 데이터를 부호화하기 위해서는, Type information(모드 정보), 인덱스 값이 같은 포지션 정보와 두 개의 DIV를 이용하여 부호화한다. Type 1 indicates when there is one shared vertex between the previous face and the current face. In order to encode such data, encoding is performed using type information (mode information), position information having the same index value, and two DIVs.

Type 2는 이전 페이스와 현재 페이스간의 두개의 공유된 정점을 가지고 있다. 이러한 데이터를 부호화하기 위해서는, Type information(모드 정보), 인덱스 값이 다른 포지션 정보와 하나의 DIV 그리고 방향정보를 이용하여 부호화하게 된다. Type 2 has two shared vertices between the previous face and the current face. In order to encode such data, encoding is performed using position information having different type information (mode information), index values, one DIV, and direction information.

Type 3은 이전 페이스와 현재 페이스간의 공유된 정점이 세 개일 때를 나타낸다. 이러한 데이터를 부호화하기 위해서는, Type information(모드 정보)와 방향 정보(face direction)를 부호화한다.Type 3 indicates when there are three shared vertices between the previous face and the current face. In order to encode such data, Type information (mode information) and direction information (face direction) are encoded.

아래의 [표 1]은 실제 VRML 데이터의 coordindex 값의 예제를 표현한 것이다.[Table 1] below shows an example of coordindex value of actual VRML data.

[표 1] 연결정보 부호화[Table 1] Connection Information Coding

Figure 112008085113561-PAT00002
Figure 112008085113561-PAT00002

위 [표 1]에서 첫번째 페이스(F1)의 인덱스는 (0, 1, 2)이고 두번째 페이스(F2)의 인덱스는 (2, 3, 0)이다. 이 경우 첫번째 인덱스는 그대로 부호화되고, 두번째 인덱스부터 SVA가 적용된다. F2의 경우 "0"과 "2" 두 개가 공유됨으로 Type2가 된다. 공유되지 않는 인덱스는 0,1,2의 위치 중 두번째이므로 위치(position) 정보는 1이 된다. DIV1의 값은 "3-1" 즉 "2"가 된다. F2를 복호화 할 때 이전 정보 (F1)는 미리 복호화 되어 있다. Tpye 정보가 2이므로, 2개가 공유되고, 공유되지 않는 한 개의 인덱스는 DIV1으로부터 "2(DIV1)+1(F1의 position 1의 값)" 즉 3이 계산된다. 따라서 (0, 3, 2)로 복호화 된다. 방향(Face direction) 의 정보가 1이므로, (0, 3, 2)를 반대로 뒤집어 (2, 3, 0)의 값을 구할 수 있다.In Table 1, the index of the first face F1 is (0, 1, 2) and the index of the second face F2 is (2, 3, 0). In this case, the first index is encoded as it is, and SVA is applied from the second index. In the case of F2, "2" and "2" are shared, resulting in Type2. Since the unshared index is the second of the positions of 0, 1, and 2, the position information is 1. The value of DIV1 becomes "3-1" or "2". When decoding F2, the previous information F1 is previously decoded. Since the Tpye information is 2, two are shared, and one index is calculated as "2 (DIV1) +1 (value of position 1 of F1)" or 3 from DIV1. Therefore, it is decoded as (0, 3, 2). Since the information in the face direction is 1, the value of (2, 3, 0) can be obtained by inverting (0, 3, 2) in reverse.

도 3과 아래 [표 2]는 본 발명에 따른 DIV의 값을 줄이기 위해 사용되는 써큘러 디퍼런스(circular difference) 방법으로, 두 가지 차분값을 계산하여 둘 중 절대값이 작은 것을 사용하는 방법의 설명이다.3 and [Table 2] below are circular difference methods used to reduce the value of DIV according to the present invention. Description.

[표 2] Circular difference에 의한 연결정보 부호화[Table 2] Connection Information Coding by Circular Difference

Figure 112008085113561-PAT00003
Figure 112008085113561-PAT00003

도 3을 참조하여 [표 1]의 F5의 DIV1의 경우를 생각해보면, 이 예제에서 사용되는 VRML데이터의 인덱스 최대값은 7이다. 일반적인 차분값은 "5-0 = 5"이다. 이 값이 도 3에서 보여지는 바와 같이 a에 저장된다(S300). 이 경우 c와 p값 크기 비교단계(S302)에서 c<p 이므로, b = -(7-5+0+1) = -3이 된다(S306). 이어 다시 a와 b의 절대값 크기 비교단계(S308)에서 a의 절대값이 b의 절대값보다 크므로, 써큘러 디퍼런스(circular difference)에 의한 차분값은 -3이 된다. 즉, 위 [표 2]와 같이 써큘러 디퍼런스가 변경된다. 이때, 위 도 3에서 b값을 계산할 때 양쪽 모두 "+1"의 값을 없애도 된다.Considering the case of DIV1 of F5 in Table 1 with reference to Fig. 3, the maximum index value of VRML data used in this example is 7. Typical difference is "5-0 = 5". This value is stored in a as shown in FIG. 3 (S300). In this case, since c <p in the c and p value size comparison step (S302), b = − (7-5 + 0 + 1) = − 3 (S306). Subsequently, since the absolute value of a is larger than the absolute value of b in the step S308 of comparing the absolute values of a and b, the difference value due to the circular difference becomes -3. That is, the circular difference is changed as shown in [Table 2]. In this case, when calculating the b value in FIG. 3, both values may be eliminated.

이하, 엔트로피 부호화부(108)에서의 동작을 보다 상세히 살펴보기로 한다.Hereinafter, the operation in the entropy encoder 108 will be described in more detail.

엔트로피 부호화의 경우 입력 심볼의 부호는 1비트의 부호화 비트를 보내주는 것으로 대신하고, 실제 엔트로피 부호화는 절대값에 적용한다. 먼저, 엔트로피 부호화부(108)에서 산술 부호화(Arithmetic coding : AC) 동작에 대해 설명하면,In the case of entropy encoding, the sign of the input symbol is transmitted by sending one bit of encoded bits, and the actual entropy encoding is applied to the absolute value. First, the arithmetic coding (AC) operation in the entropy encoder 108 will be described.

AC를 적용하기 위해서는 각 심볼에 대한 확률분포를 알아야 하는데, 심볼의 개수가 모델의 정점 개수에 비례하여 증가함으로 모든 심볼의 확률을 계산하기 어 렵다. 따라서 본 발명에서는 입력값을 몫과 나머지로 나누어 AC를 수행한다. 정점 좌표의 경우 양자화 비트의 크기에 따라 심볼의 개수가 정해지고, 이는 비교적 크지 않은 값이므로, 몫과 나머지의 연산 없이 그대로 진행할 수 있다. In order to apply AC, we need to know the probability distribution for each symbol. It is difficult to calculate the probability of every symbol because the number of symbols increases in proportion to the number of vertices in the model. Therefore, in the present invention, AC is performed by dividing the input value by the quotient and the remainder. In the case of vertex coordinates, the number of symbols is determined according to the size of the quantization bit, and since it is a relatively small value, it can proceed as is without calculation of quotient and remainder.

앞서 구해진 DIV값을 입력으로 받아 도 4와 같은 과정을 수행한다. 여기에 사용되는 MaxBit는 임의로 조절 가능하다.The process as shown in FIG. 4 is performed by receiving the previously obtained DIV value. MaxBit used here can be arbitrarily adjusted.

위 도 4를 참조하면, 여기서 floor[]는 내림 연산이다. 예를 들어, 데이터 입력(input)이 3000 이고(S400), Maxbit이 1024이면, 먼저 3000%1024 즉 952가 인코딩 되고(S402), 입력(input)은 "floor[3000/1024] = 2"가 된다(S404), 이때 입력(input)이 "0"이 되는지를 검사하고(S406), 입력(input)이 "0"아닌 경우 계속코드가 삽입된다(S408). 그 후 변경된 입력(input) 2가 다시 반복적으로 인코딩 된다. 만약 입력(input)이 "0"이 되면 종료코드를 삽입하고(S410), 다음 입력(input)을 부호화한다.Referring to FIG. 4 above, where floor [] is a rounding operation. For example, if the data input is 3000 (S400) and the Maxbit is 1024, first 3000% 1024 or 952 is encoded (S402), and the input is "floor [3000/1024] = 2". In step S404, it is checked whether the input becomes "0" (S406). If the input is not "0", the continuation code is inserted (S408). The changed input 2 is then iteratively encoded again. If the input becomes "0", an end code is inserted (S410), and the next input is encoded.

다음으로, 엔트로피 부호화부(108)에서 결정비트 부호화(Bit Precision Coding :BPC) 동작에 대해 설명하면, BPC는 입력 심볼을 BPL(Bit Precision Length)의 정수배의 비트수로 표현하는 방법이다. 아래 [표 3]에는 입력 시퀀스가 5, 3, 8, 2인 경우 각 심볼이 BPL에 따라 어떻게 부호화되는지 설명되어 있다. Next, when the bit precision coding (BPC) operation is described in the entropy encoder 108, the BPC is a method of expressing an input symbol by an integer multiple of the bit precision length (BPL). Table 3 below describes how each symbol is encoded according to the BPL when the input sequence is 5, 3, 8, or 2.

[표 3] BPC부호화[Table 3] BPC Encoding

Figure 112008085113561-PAT00004
Figure 112008085113561-PAT00004

먼저 BPL이 2인 경우를 생각하면, BPL이 2인 경우 최대로 표현 가능한 값은 "11(2) = 3"이다. 첫번째 입력 심볼인 5=3+2이므로, "11(2) + 10(2)"로 나타낼 수 있다. 다음 입력 심볼 3은 "3+0"로 나타낼 수 있고 이는 "11(2) + 00(2)"으로 표현한다. 이러한 방법으로 8=3+3+2의 형태인 "11(2) + 11(2) + 00(2)"로, 2는 "10(2)"로 부호화된다. 복호화 할 때는 비트스트림("11101100")과 BPL(2)를 알고 있다. 먼저 BPL 비트만큼 읽으면 "11(2) = 3"을 알 수 있다. 그런데 "11(2)"은 뒤에 값이 더 붙을 수 있다. 따라 다음 두 비트를 읽어 "10(2) = 2"값을 구한다. 이는 "11(2)"이 아니므로 여기서 한 심볼 읽기를 종료하여 "3+2 = 5"의 값을 복호화 한다. 나머지 역시 같은 방식으로 복호화 한다.First, when the BPL is 2, the maximum representable value when the BPL is 2 is "11 (2) = 3". Since 5 = 3 + 2, which is the first input symbol, it may be represented as "11 (2) + 10 (2)". The next input symbol 3 may be represented by "3 + 0", which is represented by "11 (2) + 00 (2)". In this way, "11 (2) + 11 (2) + 00 (2)" in the form of 8 = 3 + 3 + 2, and 2 is encoded as "10 (2)". When decoding, the bitstream ("11101100") and the BPL (2) are known. First, read by the BPL bits to see "11 (2) = 3". By the way, "11 (2)" may be added later. Read the next two bits to get the value "10 (2) = 2". Since this is not " 11 (2) " The rest is decrypted in the same way.

[표 3]에서 BPL이 3인 경우를 생각하면, 5는 "101(2)"로 표현되지만, 8은 "111(2) + 001(2)"로 표현된다. 즉, [표 3]에서 알 수 있듯이 BPL에 따라 비트스트림 크기가 변한다. 이 예제에서는 BPL이 3인 경우, 토탈 부호화 비트가 15비트로 가장 적은 비트가 소요된다. 따라서 이 경우는 BPL을 3으로 하여 BPC를 수행한다.Considering the case where BPL is 3 in [Table 3], 5 is expressed as "101 (2)", but 8 is expressed as "111 (2) + 001 (2)". That is, as shown in [Table 3], the bitstream size changes according to the BPL. In this example, when BPL is 3, the total coded bit is 15 bits and the least bit is required. Therefore, in this case, BPC is performed by setting BPL to 3.

위 [표 3]에서와 같이, 최적의 BPL을 구하기 위해 모든 BPL에 대해 BPC를 먼저 수행하는 과정이 필요하다. 이는 상당히 시간이 걸리는 요소이다. 이를 좀 더 빠르게 하기 위해 아래 [표 4]에서와 같이 빈도수 테이블을 이용하여 계산한다. As shown in [Table 3], BPC is first performed for all BPLs to obtain an optimal BPL. This is a time consuming factor. To make this faster, calculate using a frequency table as shown in Table 4 below.

[표 4] 심볼의 빈도 수에 따라 심볼에 할당되는 비트 수[Table 4] Number of bits allocated to a symbol according to the frequency of the symbol

Figure 112008085113561-PAT00005
Figure 112008085113561-PAT00005

위 [표 4]에서와 같이 빈도수 테이블을 이용하면 각 심볼에 대해 BPL에 따라 필요한 비트수를 계산하고, 이를 심볼의 빈도수로 곱해주면 해당 심볼에서 필요한 모든 비트수를 계산할 수 있다.As shown in [Table 4], if you use the frequency table, you can calculate the required number of bits for each symbol according to the BPL, and multiply it by the frequency of the symbol to calculate all the required number of bits in that symbol.

심볼S를 BPC 할때 필요한 비트수는 BPL*floor[S/(2BPL-1)+1]가 된다. 따라서 S가 FS개 있다면, 모든 S를 BPC하는데 필요한 비트수는 FS* BPL*floor[S/(2BPL-1)+1]가 된다. BPL을 계산할 때, "BPL = floor[log2Max + 1]-1"일 때까지만 계산한다. BPL이 이 값 이상일 때는 BPC를 사용하지 않고 일반적인 이진수 표현방법을 사용하면 되기 때문이다. 따라서 BPL이 1에서 "floor[log2Max + 1]-1" 이때까지의 총 비트수를 계산하고, 입력 시퀀스를 이진화 했을 때 필요한 비트수(총 심볼의 개수* floor[log2Max + 1]) 중 가장 작은 경우를 선택한다. The number of bits needed to BPC the symbol S is BPL * floor [S / (2BPL-1) +1]. Thus, if there are FS S, the number of bits needed to BPC all S is FS * BPL * floor [S / (2BPL-1) +1]. When calculating BPL, calculate it only until "BPL = floor [log2Max + 1] -1". If the BPL is above this value, you can use the normal binary representation instead of the BPC. Therefore, the BPL calculates the total number of bits from 1 to "floor [log2Max + 1] -1", and it is the smallest of the number of bits (total number of symbols * floor [log2Max + 1]) needed to binarize the input sequence. Select the case.

마지막으로, 엔트로피 부호화부(108)에서 이진산술 부호화(Binary Arithmetic Coding :BAC)동작에 대해 설명하면,Finally, the binary arithmetic coding (BAC) operation in the entropy encoder 108 will be described.

이진산술부호화 경우 이진수 형태의 값이 BAC의 입력 값으로 사용된다. 본 발명에서는 이진수 입력값을 선처리(preprocessing)를 통하여 데이터 크기가 작은 형태로 변환한 후 BAC에 입력하여 비트스트림을 출력한다. 어떤 심볼의 집합이 존재할 때 이 심볼들을 이진수로 표현하기 위해 필요한 비트수는 그 집합의 최대값을 표현하는데 필요한 비트 수와 동일하다. 이때 필요한 비트수를 RBL(Representation Bit Length)(이)라 정의한다. In binary arithmetic encoding, a binary value is used as the input value for BAC. In the present invention, the binary input value is converted into a form having a small data size through preprocessing, and then input to a BAC to output a bitstream. When a set of symbols is present, the number of bits needed to represent these symbols in binary is equal to the number of bits needed to represent the maximum of the set. The number of bits required at this time is defined as RBL (Representation Bit Length).

도 5는 본 발명의 실시 예에 따른 BAC의 예로서, 입력 심볼이 5이고 최대값이 1023 인 경우, 즉 RBL이 ceil[log2(1023+1)] = 10인 경우를 설명한다. 5는 10비트로 표현 시 이진수 “0000000101”로 표현된다. 부호를 표현하기 위해 1비트의 부호비트를 삽입하고 이 값은 비트스트림으로 바로 출력된다. 본 발명에서는 부호를 제외한 입력 이진수를 고정된 BPL비트수를 가지는 Prefix와 가변의 크기를 가지는 Postfix로 표현한다. Prefix의 값은 LSB(Least Significant Bit)로부터 가장 멀리 있는 1의 위치를 나타내는 값이다. 본 예제에서는 ceil[log2(5+1)] = 3이다. 이 값은 0∼RBL(=10)의 값을 가질 수 있으므로 ceil[log2(RBL+1)] 비트로 표현할 수 있다. 여기서 ceil[]은 올림 연산이다. Prefix는 ceil[log2(RBL+1)]의 크기로 정의되고, "3 = 0011(2)", 즉 4비트 형태로 표현된다. Postfix는 원본 바이너리 표현에 서 LSB부터 가장 멀리 1 다음의 전체 비트스트림이 된다. 본 예제에서는 Postfix는 "01"이다. 따라서 "0000000101"는 선처리 과정을 거쳐 "prefix + postfix = 001101"이 되고 이 값이 BAC의 입력이 된다. 5 illustrates an example of a BAC according to an embodiment of the present invention, in which an input symbol is 5 and a maximum value is 1023, that is, an RBL is ceil [log2 (1023 + 1)] = 10. 5 is represented by the binary number “0000000101” when expressed in 10 bits. In order to represent a sign, a 1-bit sign bit is inserted and this value is directly output to the bitstream. In the present invention, an input binary number except a sign is expressed as a prefix having a fixed number of BPL bits and a Postfix having a variable size. The value of Prefix is a value indicating the position of 1 which is furthest from the Least Significant Bit (LSB). In this example, ceil [log2 (5 + 1)] = 3. Since this value can have a value from 0 to RBL (= 10), it can be expressed as a ceil [log2 (RBL + 1)] bit. Where ceil [] is a rounding operation. Prefix is defined as the size of ceil [log2 (RBL + 1)], and is expressed as "3 = 0011 (2)", that is, in 4-bit form. Postfix is the entire bitstream one after the farthest from the LSB in the original binary representation. In this example, the Postfix is "01". Therefore, "0000000101" goes through preprocessing and becomes "prefix + postfix = 001101", which is the input of the BAC.

한편 상술한 본 발명의 설명에서는 구체적인 실시 예에 관해 설명하였으나, 여러 가지 변형이 본 발명의 범위에서 벗어나지 않고 실시될 수 있다. 따라서 발명의 범위는 설명된 실시 예에 의하여 정할 것이 아니고 특허청구범위에 의해 정하여져야 한다.Meanwhile, in the above description of the present invention, specific embodiments have been described, but various modifications may be made without departing from the scope of the present invention. Therefore, the scope of the invention should be determined by the claims rather than by the described embodiments.

도 1은 본 발명의 실시 예에 따른 3차원 메쉬 모델 부호화 장치 구성도,1 is a block diagram of an apparatus for encoding a 3D mesh model according to an embodiment of the present invention;

도 2는 본 발명의 실시 예에 따른 공유 정점 분석 예시도,2 is an exemplary view of shared vertex analysis according to an embodiment of the present invention;

도 3은 본 발명의 실시 예에 따른 써큘러 부호화 처리 흐름도,3 is a flowchart of a circular encoding process according to an embodiment of the present invention;

도 4는 본 발명의 실시 예에 따른 산술 부호화 처리 흐름도,4 is a flowchart of an arithmetic coding process according to an embodiment of the present invention;

도 5는 본 발명의 실시 예에 따른 결정비트 처리 개념도.5 is a conceptual diagram of decision bit processing according to an exemplary embodiment of the present invention.

<도면의 주요 부호에 대한 간략한 설명><Brief description of the major symbols in the drawings>

100 : 데이터 분석부 102 : 메쉬모델 양자화부100: data analysis unit 102: mesh model quantization unit

104 : 공유 정점 분석부 106 : 차분펄스 코드 변조부104: shared vertex analysis unit 106: differential pulse code modulation unit

108 : 엔트로피 부호화부 108: entropy encoder

Claims (13)

입력된 3차원 메쉬 모델의 데이터로부터 상기 3차원 메쉬 모델을 구성하는 정점 정보, 속성 정보 및 상기 정점들 간의 연결 정보를 분리하는 데이터 분석부와,A data analysis unit that separates vertex information, property information, and connection information between the vertices of the 3D mesh model from data of the input 3D mesh model; 상기 데이터 분석부로부터 분석된 상기 3차원 메쉬 모델의 정점 정보, 속성 정보 및 연결 정보를 이용하여 양자화된 정점 정보, 속성 정보 및 연결 정보를 생성하는 메쉬 모델 양자화부와,A mesh model quantization unit generating quantized vertex information, attribute information, and connection information by using the vertex information, the attribute information, and the connection information of the 3D mesh model analyzed by the data analyzer; 상기 메쉬 모델 양자화부로부터 양자화된 연결정보에 따라 상기 3차원 메쉬 모델의 연속된 연결 정보의 공유 정점 분석을 이용하여 차분 펄스 코드 변조를 수행하는 차분 펄스 코드 변조부와,A differential pulse code modulator for performing differential pulse code modulation by using shared vertex analysis of continuous connection information of the 3D mesh model according to the connection information quantized from the mesh model quantization unit; 상기 양자화된 3차원 메쉬 모델의 정점 정보, 속성 정보 및 상기 차분 펄스 코드 변조된 연결 정보를 이진산술 부호화하여 상기 3차원 메쉬 모델의 이진 산술 부호화 혹은 결정 비트 부호화된 데이터를 비트스트림 형태로 출력하는 엔트로피 부호화부 Entropy for performing binary arithmetic coding on the vertex information, the attribute information, and the differential pulse code modulated connection information of the quantized 3D mesh model, and outputting binary arithmetic coding or decision bit coded data of the 3D mesh model in a bitstream form. Encoder 를 포함하는 3차원 메쉬 모델의 부호화 장치.3D mesh model encoding apparatus comprising a. 제 1 항에 있어서,The method of claim 1, 상기 엔트로피 부호화부는,The entropy coding unit, 상기 3차원 메쉬 모델의 정점 정보, 속성 정보 및 연결 정보에 대한 데이터를 저장하는 헤더를 포함하는 것을 특징으로 하는 3차원 메쉬 모델의 부호화 장치.And a header for storing data about vertex information, property information, and connection information of the 3D mesh model. 제 1 항에 있어서,The method of claim 1, 상기 3차원 메쉬 모델의 연결 정보는,Connection information of the three-dimensional mesh model, 복수 개의 정점 정보가 하나의 다각형을 형성하는 인덱스 리스트로 표현되는 것을 특징으로 하는 3차원 메쉬 모델의 부호화 장치.A device for encoding a 3D mesh model, wherein a plurality of vertex information is represented by an index list forming one polygon. 제 3 항에 있어서,The method of claim 3, wherein 상기 3차원 메쉬 모델의 속성 정보는,Attribute information of the three-dimensional mesh model, 다각형으로 이루어지는 상기 3차원 메쉬 모델의 법선, 색상 및 텍스처 좌표를 포함하는 것을 특징으로 하는 3차원 메쉬 모델의 부호화 장치.And a normal, color, and texture coordinate of the three-dimensional mesh model formed of polygons. 제 1 항에 있어서,The method of claim 1, 상기 데이터 분석부는,The data analysis unit, 상기 3차원 메쉬 모델의 복잡도를 연산한 후, 상기 3차원 메쉬 모델의 복잡도 값이 기 설정된 기준값을 초과하는 경우 상기 3차원 메쉬 모델을 복수개의 부분 메쉬로 분할하는 것을 특징으로 하는 3차원 메쉬 모델의 부호화 장치.After calculating the complexity of the three-dimensional mesh model, if the complexity value of the three-dimensional mesh model exceeds a predetermined reference value of the three-dimensional mesh model, characterized in that to divide the three-dimensional mesh model into a plurality of partial mesh Encoding device. 제 5 항에 있어서,The method of claim 5, wherein 상기 복잡도는The complexity is 상기 3차원 메쉬 모델을 형성하는 페이스셋의 갯수에 따라 결정되는 것을 특징으로 하는 3차원 메쉬 모델의 부호화 장치.And an apparatus for encoding a 3D mesh model according to the number of facesets forming the 3D mesh model. 입력된 3차원 메쉬 모델의 데이터로부터 상기 3차원 메쉬 모델을 구성하는 정점정보, 속성 정보 및 상기 정점들 간의 연결 정보를 분리하는 단계와,Separating vertex information, property information, and connection information between the vertices constituting the 3D mesh model from data of the input 3D mesh model; 상기 분리된 3차원 메쉬 모델의 정점 정보, 속성 정보 및 연결 정보를 이용하여 양자화된 정점 정보, 속성 정보 및 연결 정보를 생성하는 단계와,Generating quantized vertex information, property information, and connection information using the vertex information, property information, and connection information of the separated three-dimensional mesh model; 상기 3차원 메쉬 모델의 연속된 연결 정보의 양자화 값을 이용하여 차분 펄스 코드 변조를 수행하는 단계와,Performing differential pulse code modulation using quantization values of consecutive connection information of the three-dimensional mesh model; 상기 양자화된 3차원 메쉬 모델의 정점 정보, 속성 정보 및 상기 차분 펄스 코드 변조된 연결 정보를 이진 산술 부호화 혹은 결정 비트 부호화하여 상기 3차원 메쉬 모델의 엔트로피 부호화를 수행하는 단계Performing entropy encoding of the 3D mesh model by performing binary arithmetic coding or decision bit coding on the vertex information, the attribute information, and the differential pulse code modulated connection information of the quantized 3D mesh model 포함하는 3차원 메쉬 모델의 부호화 방법.3D mesh model encoding method. 제 7 항에 있어서,The method of claim 7, wherein 상기 엔트로피 부호화된 데이터는,The entropy encoded data is, 비트스트림 형태로 출력되는 것을 특징으로 하는 3차원 메쉬 모델의 부호화 방법.3D mesh model encoding method characterized in that the output in the form of a bitstream. 제 7 항에 있어서,The method of claim 7, wherein 상기 3차원 메쉬 모델의 연결 정보는,Connection information of the three-dimensional mesh model, 복수 개의 정점 정보가 단위 다각형을 형성하는 인덱스 리스트로 표현되는 것을 특징으로 하는 3차원 메쉬 모델의 부호화 방법.And a plurality of vertex information is represented by an index list forming a unit polygon. 제 7 항에 있어서,The method of claim 7, wherein 상기 3차원 메쉬 모델의 속성 정보는,Attribute information of the three-dimensional mesh model, 단위 다각형으로 이루어진 상기 3차원 메쉬 모델의 법선, 색상 및 텍스처 좌표를 포함하는 것을 특징으로 하는 3차원 메쉬 모델의 부호화 방법.And a normal, color, and texture coordinate of the three-dimensional mesh model formed of unit polygons. 제 7 항에 있어서,The method of claim 7, wherein 상기 정점들간 연결 정보 분리 단계는,Separating the connection information between the vertices, 상기 3차원 메쉬 모델의 복잡도를 연산하는 단계와,Calculating a complexity of the three-dimensional mesh model; 상기 연산된 3차원 메쉬 모델의 복잡도 값이 기 설정된 기준값 초과하는 경우, 상기 3차원 메쉬 모델을 복수 개의 부분 메쉬로 분할하는 단계Dividing the 3D mesh model into a plurality of partial meshes when the calculated complexity value of the 3D mesh model exceeds a preset reference value 를 포함하는 것을 특징으로 하는 3차원 메쉬 모델의 부호화 방법.3D mesh model encoding method comprising a. 제 11 항에 있어서,The method of claim 11, 상기 복잡도는,The complexity is 상기 3차원 메쉬 모델을 형성하는 페이스셋의 갯수에 따라 결정되는 것을 특징으로 하는 3차원 메쉬 모델의 부호화 방법.And a method of encoding the 3D mesh model according to the number of facesets forming the 3D mesh model. 제 7 항 내지 제 12 항 중 어느 한 항의 3차원 메쉬 모델의 부호화 방법을 수행하는 컴퓨터 프로그램이 기록된 기록매체.A recording medium on which a computer program for performing the encoding method of any one of claims 7 to 12 is recorded.
KR1020080125428A 2008-07-14 2008-12-10 Apparatus and method for encoding 3D mesh model through connection information analysis KR101048368B1 (en)

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
KR1020080068229 2008-07-14
KR20080068229 2008-07-14

Publications (2)

Publication Number Publication Date
KR20100007685A true KR20100007685A (en) 2010-01-22
KR101048368B1 KR101048368B1 (en) 2011-07-11

Family

ID=41816623

Family Applications (1)

Application Number Title Priority Date Filing Date
KR1020080125428A KR101048368B1 (en) 2008-07-14 2008-12-10 Apparatus and method for encoding 3D mesh model through connection information analysis

Country Status (1)

Country Link
KR (1) KR101048368B1 (en)

Cited By (11)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
KR20150018952A (en) * 2013-08-12 2015-02-25 삼성전자주식회사 Method for generating tessellation data and apparatuses performing the same
US9787321B1 (en) 2016-11-17 2017-10-10 Google Inc. Point cloud data compression using a space-filling curve
US10313673B2 (en) 2016-10-19 2019-06-04 Google Llc Methods and apparatus to encode and/or decode normals of geometric representations of surfaces
US10430975B2 (en) 2016-11-17 2019-10-01 Google Llc Advanced k-D tree encoding for point clouds by most significant axis selection
US10496336B2 (en) 2016-11-17 2019-12-03 Google Llc K-D tree encoding for point clouds using deviations
US10553035B2 (en) 2017-06-02 2020-02-04 Google Llc Valence based implicit traversal for improved compression of triangular meshes
KR20200064811A (en) * 2018-11-29 2020-06-08 전자부품연구원 System and method for compression and decompression of 3d mesh model
US10733766B2 (en) 2016-10-19 2020-08-04 Google, Llc Methods and apparatus to encode and/or decode normals of geometric representations of surfaces
CN112146596A (en) * 2020-08-31 2020-12-29 南昌航空大学 Optimal quantization phase coding three-dimensional measurement method
US10891758B2 (en) 2018-07-23 2021-01-12 Google Llc Geometry encoder
US10950042B2 (en) 2017-06-02 2021-03-16 Google Llc Guided traversal in compression of triangular meshes

Family Cites Families (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US6009201A (en) * 1997-06-30 1999-12-28 Intel Corporation Efficient table-lookup based visually-lossless image compression scheme
KR100634506B1 (en) * 2004-06-25 2006-10-16 삼성전자주식회사 Low bitrate decoding/encoding method and apparatus

Cited By (12)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
KR20150018952A (en) * 2013-08-12 2015-02-25 삼성전자주식회사 Method for generating tessellation data and apparatuses performing the same
US10313673B2 (en) 2016-10-19 2019-06-04 Google Llc Methods and apparatus to encode and/or decode normals of geometric representations of surfaces
US10733766B2 (en) 2016-10-19 2020-08-04 Google, Llc Methods and apparatus to encode and/or decode normals of geometric representations of surfaces
US9787321B1 (en) 2016-11-17 2017-10-10 Google Inc. Point cloud data compression using a space-filling curve
US10430975B2 (en) 2016-11-17 2019-10-01 Google Llc Advanced k-D tree encoding for point clouds by most significant axis selection
US10496336B2 (en) 2016-11-17 2019-12-03 Google Llc K-D tree encoding for point clouds using deviations
US10553035B2 (en) 2017-06-02 2020-02-04 Google Llc Valence based implicit traversal for improved compression of triangular meshes
US10950042B2 (en) 2017-06-02 2021-03-16 Google Llc Guided traversal in compression of triangular meshes
US10891758B2 (en) 2018-07-23 2021-01-12 Google Llc Geometry encoder
KR20200064811A (en) * 2018-11-29 2020-06-08 전자부품연구원 System and method for compression and decompression of 3d mesh model
CN112146596A (en) * 2020-08-31 2020-12-29 南昌航空大学 Optimal quantization phase coding three-dimensional measurement method
CN112146596B (en) * 2020-08-31 2022-01-28 南昌航空大学 Optimal quantization phase coding three-dimensional measurement method

Also Published As

Publication number Publication date
KR101048368B1 (en) 2011-07-11

Similar Documents

Publication Publication Date Title
KR101048368B1 (en) Apparatus and method for encoding 3D mesh model through connection information analysis
CN113574540B (en) Point cloud encoding and decoding method and device and electronic equipment
JP5033261B2 (en) Low-complexity three-dimensional mesh compression apparatus and method using shared vertex information
US11935270B2 (en) Predictive geometry coding in G-PCC
US11350132B2 (en) High level syntax for geometry-based point cloud compression
KR20230020418A (en) Attribute Residual Coding in G-PCC
KR100910031B1 (en) Apparatus and Method of encoding 3 dimensional mesh model and Recording medium thereof
AU2012344426B2 (en) Terminable spatial tree-based position coding and decoding
KR100927601B1 (en) Method and apparatus for encoding / decoding of 3D mesh information
TW202141984A (en) Predictor index signaling for predicting transform in geometry-based point cloud compression
CN113632142A (en) Method and device for point cloud compression
JP2023545917A (en) High-level syntax for laser rotation in geometry point cloud compression (G-PCC)
EP4133724A1 (en) Global scaling for point cloud data
CN117897728A (en) Connectivity information encoding method and apparatus for encoding a grid representation
KR101086774B1 (en) Method and apparatus for low complexity 3d mesh compression
CN115102934B (en) Decoding method, encoding device, decoding equipment and storage medium for point cloud data
CN113906681A (en) Point cloud data encoding and decoding method, system and storage medium
WO2024221458A1 (en) Point cloud encoding/decoding method and apparatus, device, and storage medium
KR101086772B1 (en) Method and apparatus for 3d mesh compression based quantization
KR20240113803A (en) Methods, devices and media for point cloud coding
JP2024093896A (en) Point group decoding device, point group decoding method, and program
JP2024093897A (en) Point group decoding device, point group decoding method, and program
CN115733990A (en) Point cloud coding and decoding method, device and storage medium
CN116438797A (en) Point cloud encoding and decoding method and system, point cloud encoder and point cloud decoder

Legal Events

Date Code Title Description
A201 Request for examination
E902 Notification of reason for refusal
E701 Decision to grant or registration of patent right
GRNT Written decision to grant
FPAY Annual fee payment

Payment date: 20140630

Year of fee payment: 4

LAPS Lapse due to unpaid annual fee