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 PDFInfo
- 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
Links
Images
Classifications
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06T—IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
- G06T9/00—Image coding
- G06T9/001—Model-based coding, e.g. wire frame
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06T—IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
- G06T17/00—Three dimensional [3D] modelling, e.g. data description of 3D objects
- G06T17/20—Finite element generation, e.g. wire-frame surface description, tesselation
-
- H—ELECTRICITY
- H03—ELECTRONIC CIRCUITRY
- H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
- H03M7/00—Conversion 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/30—Compression; Expansion; Suppression of unnecessary data, e.g. redundancy reduction
- H03M7/3002—Conversion to or from differential modulation
- H03M7/3044—Conversion 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/3046—Conversion 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]
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04N—PICTORIAL COMMUNICATION, e.g. TELEVISION
- H04N19/00—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals
- H04N19/10—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals using adaptive coding
- H04N19/102—Methods 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/124—Quantisation
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04N—PICTORIAL COMMUNICATION, e.g. TELEVISION
- H04N19/00—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals
- H04N19/10—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals using adaptive coding
- H04N19/102—Methods 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/13—Adaptive entropy coding, e.g. adaptive variable length coding [AVLC] or context adaptive binary arithmetic coding [CABAC]
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04N—PICTORIAL COMMUNICATION, e.g. TELEVISION
- H04N19/00—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals
- H04N19/10—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals using adaptive coding
- H04N19/134—Methods 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/136—Incoming video signal characteristics or properties
- H04N19/14—Coding unit complexity, e.g. amount of activity or edge presence estimation
Landscapes
- Engineering & Computer Science (AREA)
- Multimedia (AREA)
- Physics & Mathematics (AREA)
- Theoretical Computer Science (AREA)
- Signal Processing (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
Description
본 발명은 영상 압축에 관한 것으로, 특히 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
메쉬 모델 양자화부(102)는 데이터 분석부(100)로부터 분석된 3차원 메쉬 모델의 정점 정보, 속성 정보 및 3차원 메쉬 모델의 정점들간 연결정보를 이용하여 양자화된 정점 정보, 속성 정보 및 연결정보를 생성한다. 이때 위 연결정보는 복수 개의 정점 정보가 하나의 다각형을 형성하는 인덱스 리스트로 표현되며, 속성정보는 다각형으로 이루어지는 3차원 메쉬 모델의 법선, 색상 및 텍스쳐(texture) 좌표 를 포함한다.The mesh
공유 정점 분석부(104)는 3차원 메쉬 모델의 정점들간 공유 정보를 분석한다. 차분 펄스 코드 변조부(difference pulse code modulation)(106)는 메쉬 모델 양자화부(102)에서 양자화된 연결정보에 따라 3차원 메쉬 모델의 연속된 연결정보의 공유 정점 분석(sharable vertex analysis)을 이용하여 차분 펄스 코드 변조 예측을 수행한다.The shared
엔트로피 부호화부(108)는 메쉬 모델 양자화부(102)에서 양자화된 3차원 메쉬 모델의 정점 정보, 속성 정보 및 차분 펄스 코드 변조된 연결정보를 (이진)산술 부호화하여 3차원 메쉬 모델의 이진 산술 부호화 혹은 결정 비트 부호화된 데이터를 비트스트림(bit stream) 형태로 출력한다. The
이하, 공유정점 분석(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
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
이 두 데이터간의 공유 관계를 이용하여 부호화된 데이터를 부호화/복호화 하기 위해서는 위치(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 1은 이전 페이스와 현재 페이스간의 공유된 정점이 하나일 때를 나타낸다. 이러한 데이터를 부호화하기 위해서는, Type information(모드 정보), 인덱스 값이 같은 포지션 정보와 두 개의 DIV를 이용하여 부호화한다.
Type 2는 이전 페이스와 현재 페이스간의 두개의 공유된 정점을 가지고 있다. 이러한 데이터를 부호화하기 위해서는, Type information(모드 정보), 인덱스 값이 다른 포지션 정보와 하나의 DIV 그리고 방향정보를 이용하여 부호화하게 된다.
Type 3은 이전 페이스와 현재 페이스간의 공유된 정점이 세 개일 때를 나타낸다. 이러한 데이터를 부호화하기 위해서는, Type information(모드 정보)와 방향 정보(face direction)를 부호화한다.
아래의 [표 1]은 실제 VRML 데이터의 coordindex 값의 예제를 표현한 것이다.[Table 1] below shows an example of coordindex value of actual VRML data.
[표 1] 연결정보 부호화[Table 1] Connection Information Coding
위 [표 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
도 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
도 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
엔트로피 부호화의 경우 입력 심볼의 부호는 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
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
다음으로, 엔트로피 부호화부(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
[표 3] BPC부호화[Table 3] BPC Encoding
먼저 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
[표 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
위 [표 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
이진산술부호화 경우 이진수 형태의 값이 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)
Applications Claiming Priority (2)
Application Number | Priority Date | Filing Date | Title |
---|---|---|---|
KR20080068229 | 2008-07-14 | ||
KR1020080068229 | 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)
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)
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 |
-
2008
- 2008-12-10 KR KR1020080125428A patent/KR101048368B1/en not_active IP Right Cessation
Cited By (12)
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 | |
TW202425638A (en) | Encoding method, decoding method, decoder, encoder, code stream, and storage medium | |
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 |