KR20120118482A

KR20120118482A - 3ｄ 메시 모델의 법선을 인코딩하기 위한 방법, 3ｄ 메시 모델의 법선을 디코딩하기 위한 방법, 인코더 및 디코더

Info

Publication number: KR20120118482A
Application number: KR1020127022212A
Authority: KR
Inventors: 강잉 차이; 웨이웨이 리; 지보 첸
Original assignee: 톰슨 라이센싱
Priority date: 2010-01-25
Filing date: 2010-01-25
Publication date: 2012-10-26
Also published as: WO2011088595A1; CN102725775A; US9214042B2; US20120306875A1; CN102725775B; EP2529356A1; BR112012017138A2; JP5512827B2; JP2013518315A

Abstract

3D 메시 모델의 법선 성분이라고도 알려진 꼭지점 배향을 인코딩하기 위한 방법은 법선 성분의 제1 클러스터링 단계, 제1 클러스터 각각에 대해 그 요소의 대부분이 속하는 구체 구획을 결정하는 단계, 법선 성분을 미리 정의된 구획에 매핑하는 단계, 미리 정의된 구획 내의 법선 성분을 제2 클러스터로 재클러스터링하는 단계, 제2 클러스터에 대한 예측자를 결정하는 단계 및 법선 성분을 그 잔차(residual), 그 예측자에 대한 참조, 그리고 상기 거울 매핑 동작 중 어느 것이 수행되었는지를 가리키는 데이터에 의해 인코딩하는 단계를 포함한다. 구체 구획은 구체를 m개의 동등한 구체 분절로 분할하고 상기 구체 분절 각각을 n개의 동등한 구획으로 분할함으로써 얻어진다. 구획 매핑을 위한 제1 클러스터링 및 예측 코딩을 위한 제2 클러스터링은 향상된 압축률을 낳는다.

Description

3Ｄ 메시 모델의 법선을 인코딩하기 위한 방법, 3Ｄ 메시 모델의 법선을 디코딩하기 위한 방법, 인코더 및 디코더{METHOD FOR ENCODING NORMALS OF A 3D MESH MODEL, METHOD FOR DECODING NORMALS OF A 3D MESH MODEL, ENCODER AND DECODER}

본 발명은 3D 메시(mesh) 모델의 법선의 인코딩 및 디코딩과 관련된다. 특히, 본 발명은 이러한 법선을 인코딩 및 디코딩하기 위한 방법, 대응되는 인코더 및 디코더, 그리고 인코딩된 3D 모델과 관련된다.

대개 3D 메시 모델은 연관된 위치, 색 및 법선 성분으로 각각 표현되는 삼각형으로 구성된다. 위치는 이것의 세 모퉁이 또는 꼭지점의 부동 소수점(floating-point)으로 주어진다. 각각의 꼭지점은 연관된 법선 성분을 갖는데, 이는 또한 부동 소수점 값이다. 법선 성분은 공간 꼭지점 배향을 제공한다. 이러한 3D 메시 모델을 압축함에 있어서, 위치, 색 및 법선 성분 각각이 별개로 압축된다. [D95]¹는 이러한 압축을 기술한다. [D95]에서, 단위 법선의 말단점이 놓인 법선 구체는 8개의 8분 공간(octant)으로 분할되고, 각각의 8분 공간은 6개의 6분 공간(sextant)으로 이루어진다. 6분 공간을 더 하위 분할하면, 1/48 구체 상의 법선의 평균에 의해 참조된다. 그러나, [D95]에서 주어진 접근법은 모델 법선들이 구체에 걸쳐 고르게 분포되는 경우에만 적합하다. 3D 메시 모델의 법선들이 대개 고르게 분포되지 않는다는 관찰에 기초하여, [DYH02]²는 향상된 압축을 위한 법선들의 k-평균 클러스터링(k-means clustering)을 제안한다. 그러나, 이 접근법에서 클러스터의 개수 k가 고정된다. 더욱이, k를 미리 결정하는 것은 항상 어려운 일이다. 또한, 법선 인코딩 파라미터화와 같은, [D95]에서 이용 가능한 장점은 [DYK02]에서 더 이상 이용 가능하지 않다.

복잡한 3D 메시 모델은 연결 성분이라고 불리는 몇몇 성분으로 구성된다. 이들은 SBM01³에서 아래와 같이 정의된다. 두 개의 다각형은 이들이 모서리를 공유하는 경우 인접 다각형이다. 인접 다각형의 시퀀스가 존재하는 경우 다각형 p_i와 p_j 사이에 경로가 존재한다. 메시 모델 O의 부분집합 O_c는 O_c 내의 임의의 두 다각형 사이에 경로가 존재하는 경우 연결 성분이라고 불린다. 이러한 메시 모델은 다중 연결 모델이라고 불린다. 또한, 다중 연결 모델의 경우, 효과적인 압축 방안은 반복되는 특징을 발견한 후 변환 데이터를 압축할 수 있다. 배향은 변환 데이터의 중요한 부분들 중 하나이다.

많은 3D 모델에서, 법선은 고르지 않게 분포된다. 따라서, 이들은 가변적인 개수의 클러스터로 분류되어야 한다. 효율적인 법선 압축 방법은 현실적인 모델에 바람직한데, 여기에는 법선들이 가변적인 개수의 클러스터로 분포되는 경우가 포함된다.

본 발명은 거대 3D 공학 모델의 연결 성분의 배향을 압축하기 위한 효율적인 방법을 제공한다. 본 발명의 압축 방법은 매핑(mapping) 동작 및 클러스터링, 특히 k-평균 클러스터링의 능력을 결합시킨다.

일 태양에서, 3D 메시 모델의 법선 성분이라고도 알려진 꼭지점 배향을 인코딩하기 위한 방법은 법선 성분의 제1 클러스터링 단계, 제1 클러스터 각각에 대해 그 요소의 대부분이 속하는 구체 구획을 결정하는 단계, 법선 성분을 미리 정의된 구획에 매핑하는 단계, 미리 정의된 구획 내의 법선 성분을 제2 클러스터로 재클러스터링하는 단계, 제2 클러스터에 대한 예측자를 결정하는 단계 및 법선 성분을 그 잔차(residual), 그 예측자에 대한 참조, 그리고 상기 거울 매핑 동작 중 어느 것이 수행되었는지를 가리키는 데이터에 의해 인코딩하는 단계를 포함한다. 구체 구획은 구체를 m개의 동등한 구체 분절로 분할하고 상기 구체 분절 각각을 n개의 동등한 구획으로 분할함으로써 얻어진다. 구획 매핑을 위한 제1 클러스터링 및 예측 코딩을 위한 제2 클러스터링은 향상된 압축률을 가져온다.

원리상으로, 본 발명의 태양은 법선을 인코딩함에 있어서 법선의 제1 클러스터링이 수행된 후 클러스터들이 단위 구체의 미리 정의된 구획으로 매핑되고 제2 클러스터링이 그 결과에 대해 수행되는 것이다. 제1 클러스터링의 목적은 매핑 동작을 최적화하는 것이고, 제2 클러스터링의 목적은 법선의 예측된 코딩을 최적화하는 것이다.

본 발명의 일 태양에 따르면, 법선 성분이 이것의 단위 구체 상의 위치에 의해 정의 가능한 3D 메시 모델의 법선 성분을 인코딩하기 위한 방법은 3D 메시 모델의 법선 성분을 클러스터링하는 단계(하나 이상의 제1 클러스터가 획득되고, 각각의 법선 성분은 상기 제1 클러스터 중 적어도 하나의 요소임), 법선 성분의 제1 클러스터 각각에 대해 그 요소들 중 대부분이 속하는 구체 구획을 결정하는 단계(구체 구획은 구체를 m개의 동등한 구체 분절로 분할하고 상기 구체 분절 각각을 n개의 동등한 구획으로 분할함으로써 획득 가능함), 상기 결정 단계에 따르면 상기 구획 중 미리 정의된 것에 속하지 않은 법선 성분을 미리 정의된 구획으로 매핑하는 단계, 법선 성분을 재클러스터링하는 단계(하나 이상의 제2 클러스터가 획득되고, 각각의 법선 성분은 상기 제2 클러스터 중 적어도 하나의 요소임), 법선 성분을 양자화하는 단계, 상기 제2 클러스터 각각에 대해 대표 예측자 요소를 결정하는 단계, 법선 성분에 대한 잔차를 결정하는 단계(잔차는 법선 성분과 그 각각의 예측자 요소 사이의 차이임) 및 법선 성분을 그 잔차, 그 예측자 요소에 대한 참조, 그리고 상기 거울 매핑 동작 중 어느 것이 수행되었는지를 가리키는 데이터에 의해 인코딩하는 단계를 포함한다.

일반적으로, 매핑은 int(log₂(m)+log₂(n)+1)회까지의 거울 매핑 동작을 포함한다.

본 발명의 일 태양에 따르면, 법선 성분이 이것의 단위 구체 상의 위치에 의해 정의 가능한 3D 메시 모델의 법선 성분을 인코딩된 비트스트림으로부터 디코딩하기 위한 방법은 인코딩된 비트스트림으로부터 예측자인 법선 성분의 데이터를 추출하는 단계, 예측자에 대한 식별자를 추출하는 단계, 인코딩된 비트스트림으로부터 인코딩된 법선 성분과 관련된 데이터를 추출하는 단계(상기 데이터는 잔차 데이터, 예측자 식별 데이터 및 매핑 데이터를 포함하고, 상기 매핑 데이터는 복수의 미리 정의된 거울 매핑 동작 각각이 인코딩된 법선 성분에 대해 수행될지 여부를 가리킴) 및 법선 성분을 디코딩하는 단계(잔차 데이터는 상기 예측자 식별 데이터에 따라 예측자에 부가되고, 결과적인 법선 성분은 상기 미리 정의된 거울 매핑 동작에 따라 매핑됨)를 포함한다.

디코딩 방법의 일 실시예에서, 매핑 데이터는 법선 성분에 대한 클러스터 식별 데이터 및 각 클러스터에 대한 클러스터 매핑 데이터를 포함한다. 클러스터 식별 데이터는 법선 성분을 클러스터와 연관시킨다. 클러스터 매핑 데이터는 특정 클러스터와 관련되고, 복수의 미리 정의된 거울 매핑 동작 각각이 특정 클러스터와 연관된 법선 요소에 대해 수행될지 여부를 가리킨다.

본 발명의 일 태양에 따르면, 법선 성분이 이것의 단위 구체 상의 위치에 의해 정의 가능한 3D 메시 모델의 법선 성분을 인코딩하기 위한 장치는 3D 메시 모델의 법선 성분을 클러스터링하기 위한 제1 클러스터링 수단(하나 이상의 제1 클러스터가 획득되고, 각각의 법선 성분은 상기 제1 클러스터 중 적어도 하나의 요소임), 법선 성분의 제1 클러스터 각각에 대해 그 요소들 중 대부분이 속하는 구체 구획을 결정하기 위한 결정 수단(구체 구획은 구체를 m개의 동등한 구체 분절로 분할하고 상기 구체 분절 각각을 n개의 동등한 구획으로 분할함으로써 획득 가능함), 상기 결정에 따르면 상기 구획 중 미리 정의된 것에 속하지 않은 법선 성분을 미리 정의된 구획으로 매핑하기 위한 매핑 수단, 법선 성분을 재클러스터링하기 위한 제2 클러스터링 수단(하나 이상의 제2 클러스터가 획득되고, 각각의 법선 성분은 상기 제2 클러스터 중 적어도 하나의 요소임), 법선 성분을 양자화하기 위한 양자화기, 상기 제2 클러스터 각각에 대해 대표 예측자 요소를 결정하고 법선 성분에 대한 잔차를 결정하기 위한 예측 코더(잔차는 법선 성분과 그 각각의 예측자 요소 사이의 차이임) 및 법선 성분을 그 잔차, 그 예측자 요소에 대한 참조, 그리고 상기 거울 매핑 동작 중 어느 것이 수행되었는지를 가리키는 데이터에 의해 인코딩하기 위한 인코더를 포함한다. 또한, 엔트로피 인코더가 이후에 사용될 수 있다.

본 발명의 일 태양에 따르면, 법선 성분이 이것의 단위 구체 상의 위치에 의해 정의 가능한 3D 메시 모델의 법선 성분을 인코딩된 비트스트림으로부터 디코딩하기 위한 장치는 인코딩된 비트스트림으로부터 예측자인 법선 성분의 데이터를 추출하기 위한 제1 추출 수단, 예측자에 대한 식별자를 추출하기 위한 제2 추출 수단, 인코딩된 비트스트림으로부터 인코딩된 법선 성분과 관련된 데이터를 추출하기 위한 제3 추출 수단(상기 데이터는 잔차 데이터, 예측자 식별 데이터 및 매핑 데이터를 포함하고, 상기 매핑 데이터는 복수의 미리 정의된 거울 매핑 동작 각각이 인코딩된 법선 성분에 대해 수행될지 여부를 가리킴) 및 법선 성분을 디코딩하기 위한 디코딩 수단(잔차 데이터는 상기 예측자 식별 데이터에 따라 예측자에 부가되고, 결과적인 법선 성분은 상기 미리 정의된 거울 매핑 동작에 따라 매핑됨)을 포함한다.

디코딩 장치의 일 실시예에서, 상기 장치는 매핑 데이터로부터 법선 성분에 대한 클러스터 식별 데이터 및 각 클러스터에 대한 클러스터 매핑 데이터를 추출하기 위한 수단을 포함한다. 클러스터 식별 데이터는 법선 성분을 클러스터와 연관시킨다. 클러스터 매핑 데이터는 특정 클러스터와 관련되고, 복수의 미리 정의된 거울 매핑 동작 각각이 특정 클러스터와 연관된 법선 요소에 대해 수행될지 여부를 가리킨다. 이 실시예에서, 상기 디코딩 장치는 미리 정의된 거울 매핑 동작에 따라 법선 성분을 매핑하기 위한 매핑 수단을 더 포함한다.

본 발명의 일 태양에 따르면, 데이터 구조는 3D 메시 모델의 꼭지점 데이터 및 인코딩된 꼭지점 배향 데이터를 포함하는데, 인코딩된 꼭지점 배향 데이터는 적어도 예측자, 예측자와 연관된 식별자 및 인코딩된 꼭지점 배향과 관련된 데이터를 포함하고, 인코딩된 꼭지점 배향과 관련된 데이터는 잔차 데이터, 예측자 식별 데이터 및 매핑 데이터를 포함하며, 매핑 데이터는 복수의 미리 정의된 거울 매핑 동작 각각이 인코딩된 꼭지점 배향을 디코딩하기 위해 수행될지 여부를 가리킨다.

데이터 구조의 일 실시예에서, 매핑 데이터는 꼭지점 배향에 대한 클러스터 식별 데이터 및 각 클러스터에 대한 클러스터 매핑 데이터를 포함하는데, 클러스터 식별 데이터는 꼭지점 배향을 클러스터와 연관시키고, 클러스터 매핑 데이터는 특정 클러스터와 관련되며, 복수의 미리 정의된 거울 매핑 동작 각각이 특정 클러스터와 연관된 꼭지점 배향에 대해 수행될지 여부를 가리킨다.

본 발명의 유리한 실시예들이 종속 청구항, 아래의 설명 및 도면에 개시된다.

본 발명의 예시 실시예들이 첨부 도면을 참조하여 기술된다.
도 1은 단위 구체의 분절을 도시하는 도면.
도 2는 원기둥인 3D 메시 모델의 배향축들을 도시하는 도면.
도 3은 단위 구체 상의 예시 3D 메시 모델의 배향축들의 분포를 도시하는 도면.
도 4는 클러스터링 및 매핑 후의 단위 구체 상의 배향축들의 분포를 도시하는 도면.
도 5는 제1 클러스터링, 매핑 및 재클러스터링 후의 클러스터 대표를 도시하는 도면.
도 6은 (a) 매핑 전 및 (b) 매핑 후의 배향들과 평균 배향 사이의 최대 오차를 도시하는 도면.
도 7은 인코딩의 블록도.
도 8은 디코딩의 블록도.
도 9는 단위 구체에 대한 대안적인 분절 방법을 도시하는 도면.
도 10은 가지 달린 촛불(candelabra light)의 예시 3D 모델, 그 연결 성분의 제1 배향축의 분포 및 매핑 후의 제1 배향축의 분포를 도시하는 도면.

도 1은 단위 법선이 놓인 단위 구체의 구획들을 도시한다. 구체 구획은 구체를 m개의 동등한 구체 분절 S1으로 분할하고 상기 구체 분절 각각을 n개의 동등한 구획 000, …, 101로 분할함으로써 획득 가능하다. 편의상, 구체를 구체 분절로 분할하는 것은 2³=8개의 분절이 도출되도록 3개의 직교 X, Y 및 Z축들을 따라 이루어질 수 있다. 예컨대 도 9와 유사한 다른 분할 방법이 가능하다. m개의 구획과 n개의 분절 사이의 매핑은 int(log₂(m)+log₂(n)+1)회까지의 거울 매핑 동작을 포함할 수 있다. 예컨대, 8개의 분절 S1과 6개의 구획 000, …, 101에 대해, 분절들 사이에서 3회의 매핑 동작이 도출되어 대부분의(대체로 모든) 법선들이 하나의 미리 정의된 분절로 매핑되고, 다른 3회의 매핑 동작이 미리 정의된 분절 내에서 이루어져 대부분의(대체로 모드) 법선들이 하나의 미리 정의된 구획 000으로 매핑된다.

바람직하게는, 법선들이 하나씩 매핑되지 않고, 제1 클러스터링 단계에서의 매핑에 앞서 법선들이 클러스터링된다. 이러한 클러스터링 단계는 k-평균 클러스터링을 사용할 수 있다. 이것의 목적은 매핑을 단순화하는 것인데, 그 까닭은 동일한 매핑이 클러스터의 모든 법선들에 대해 수행되기 때문이다. 상이한 클러스터들이 상이한 매핑을 사용할 수 있는데(그러나 사용할 필요는 없음), 이는 이용 가능한 매핑의 상이한 조합들을 의미한다.

매핑 후에 다른 클러스터링을 수행하는 것이 유리한데, 그 까닭은 대개 매핑 후에 법선들이 더 가깝기 때문이다. 따라서, 대개 새롭고 더 큰 클러스터들이 도출될 것이다. 이러한 제2 클러스터링은 또한 본 명세서에서 재클러스터링라고 불린다. 이전의 제1 클러스터링은 매핑을 위해서만 사용되었다. 재클러스터링 후에, 대표 법선이 결정되고(클러스터에서 대표를 발견하기 위한 공지된 방법을 사용함), 법선들이 이들의 클러스터(즉 제2 클러스터)의 대표에 대해 인코딩되어 대표가 예측자가 되도록 한다. 법선들을 인코딩함에 있어서, 각각의 법선은 자신의 대표 예측자, 자신의 예측 오차(잔차) 및 자신의 매핑에 관한 정보를 가질 필요가 있다. 대표 예측자 및 잔차로부터 법선이 재구축될 수 있고, 매핑 정보로부터 이것의 원래 위치가 결정될 수 있다. 매핑 정보는 제1 클러스터링의 클러스터 식별자에 관하여 인코딩될 수 있고, 클러스터 매핑 정보는 클러스터의 모든 법선에 대해 인코딩될 수 있다. 이는 모든 클러스터 요소들에 대해 매핑 정보가 한 번만 인코딩, 송신 및 디코딩될 필요가 있다는 이점을 갖는다.

본 발명의 개시 내용은 배향을 압축하기 위한 효율적인 방법을 제안하는데, 이는 매핑 동작 및 적응적 k-평균 클러스터링 방법의 능력을 조합할 수 있다. 우리의 알고리즘은 매핑 동작을 사용할지 여부를 적응적으로 결정할 수 있다. 첫째로, 모든 배향은 적응적 k-평균 클러스터링 방법을 사용하여 클러스터링되는데, 이는 매우 효율적이다. 둘째로, 이러한 클러스터들이 매핑될 필요가 있는지 여부가 판단된다. 상이한 6분 공간에 분포된 데이터 지점들을 갖는 클러스터의 경우, 매핑 동작을 수행할 것이다. 매핑 동작은 라벨 000을 갖는 1/48 구체 라벨에 배향축들을 매핑할 것이다. 매핑 후에, 모든 데이터가 동일한 6분 공간에 매핑되므로 클러스터들의 분산(variance)은 감소될 것이고, 도 5 및 6에 도시된 바처럼 이들을 더 적은 비트를 가지고 양자화하여 압축률을 더 향상시킬 수 있다. 이어서, "000" 1/48 구체 부분에 속하는 모든 배향축들 및 인접한 모든 1/48 구체 부분들은 적응적 k-평균 클러스터링 방법을 사용하여 재클러스터링된다. 여전히 다른 1/48 구체 부분에 속하는 배향축들의 경우, 이들은 재클러스터링될 필요가 없다.

도 5는 매핑 전의 제1 클러스터의 배향들과 평균 배향 사이의 최대 오차(5v)를 도시한다. 도 6은 매핑 및 재클러스터링 후의 제1 클러스터의 배향들과 평균 배향 사이의 최대 오차(6v)를 도시한다. 확인할 수 있는 바처럼, 최대 오차는 매핑 및 재클러스터링 전보다 훨씬 더 작다.

모델의 배향은 두 개의 축으로 효율적으로 표현될 수 있다. 제1 축은 두 개의 자유도를 갖고 제2 축은 단지 한 개의 자유도를 갖는다. 우리의 접근법은 또한 제2 축을 압축하는 데 사용될 수 있다. 유일한 차이는 제2 축이 원 위에 분포된다는 점이다.

배향축은 이것이 속하는 (제2) 클러스터의 대표에 의해 예측될 것이다. 예측 오차, 또는 잔차가 양자화될 것이다.

매핑 동작으로 인해, 법선의 클러스터의 분산이 도 4에 도시된 바처럼 크게 감소될 수 있다.

인코더 및 디코더의 블록도가 도 7 및 도 8에 도시된다.

"적응적 k-평균 클러스터링" 블록(52)은 아래와 같이 수행된다.

초기화: n = 0

(1) k를 작은 수로 설정한다(예컨대 k = 4).

(2) 데이터 집합을 k-평균 클러스터링에 의해 분류한다.

(3) n = 0.

(4) 각각의 클러스터에 대해, 클러스터의 분산이 α보다 크면 n++.

(5) n = 0이면 종료한다.

(6) 분산이 α보다 큰 각각의 클러스터에 대해, 2-평균 클러스터링 절차에 의해 클러스터를 둘로 분리한다.

(7) (3)으로 진행한다.

여기서 α는 문턱값이다. 이는 고정되거나 사용자 정의될 수 있다.

판정 블록(53)은 적응적 k-평균 클러스터링 블록(52) 후에 각각의 결과적인 클러스터를 검사한다. 구획 매핑 블록(54)에서, 상이한 "1/48 구체" 부분에 속하는 법선들을 포함하는 클러스터는 "000" 1/48 구체(이는 이 예에서 미리 정의된 목표 구획임)에 매핑될 것이다.

일 실시예에서, 압축된 배향축 정보의 비트스트림은 두 부분을 포함한다.

- 일부 비트는 클러스터의 개수를 가리킨다.

- 각각의 클러스터에 대해:

- 일부 부동 소수점 값은 대표를 가리킨다.

- 일부 비트는 각 배향축의 잔차를 양자화하는 데 사용되는 비트수를 가리킨다.

- 일부 비트는 매핑 동작으로 압축된 배향축의 개수를 표시한다.

- 각각의 매핑된 배향축에 대해:

- 6개의 비트는 매핑 절차를 표시한다.

- 일부 비트는 자신이 속하는 클러스터의 ID를 표시한다.

- 일부 비트는 양자화된 잔차를 표시한다.

- 일부 비트는 매핑 없이 압축된 배향축의 개수를 표시한다.

- 각각의 배향축에 대해:

- 일부 비트는 자신이 속하는 클러스터의 ID를 표시한다.

- 일부 비트는 양자화된 잔차를 표시한다.

일 실시예에서, 압축된 배향축의 개수가 인코딩/송신되는데, 그 까닭은 상이한 클러스터는 대개 상이한 분산을 갖기 때문이다. 분산은 상이한 비트수에 의해 양자화될 수 있다. 따라서 이 실시예에서는 각 법선 성분의 잔차를 양자화하기 위해 사용되는 비트수를 가리킨다. 또한, 각각의 매핑된 법선 성분에 대해 "매핑 없이 압축된 배향축의 개수"를 표시하는 일부 비트가 이 실시예에 포함된다. 그 까닭은 이러한 경우에 매핑으로 및 매핑 없이 압축된 배향축의 개수를 알 필요가 있기 때문이다. 주로 그 이유는 압축 해제를 위해서는 압축된 축들의 개수를 알아야 이들을 위한 공간을 할당할 수 있기 때문이다.

일 실시예에서, 3D 메시 모델의 법선 성분을 인코딩하기 위한 방법은 3D 메시 모델의 법선 성분을 클러스터링하는 단계(하나 이상의 제1 클러스터가 획득되고, 각각의 법선 성분은 상기 제1 클러스터 중 적어도 하나의 요소임), 법선 성분의 제1 클러스터 각각에 대해 그 요소들 중 대부분이 속하는 구체 구획을 결정하는 단계(구체 구획은 구체를 m개의 동등한 구체 분절로 분할하고 상기 구체 분절 각각을 n개의 동등한 구획으로 분할함으로써 획득 가능함), 상기 결정 단계에 따르면 상기 구획 중 미리 정의된 것에 속하지 않은 법선 성분을 미리 정의된 구획으로 매핑하는 단계{매핑은 int(log₂(m)+log₂(n)+1)회까지의 거울 매핑 동작을 포함함}, 법선 성분을 재클러스터링하는 단계(하나 이상의 제2 클러스터가 획득되고, 각각의 법선 성분은 상기 제2 클러스터 중 적어도 하나의 요소임), 법선 성분을 양자화하는 단계, 상기 제2 클러스터 각각에 대해 대표 예측자 요소를 결정하는 단계, 법선 성분에 대한 잔차를 결정하는 단계(잔차는 법선 성분과 그 각각의 예측자 요소 사이의 차이임) 및 법선 성분을 그 잔차, 그 예측자 요소에 대한 참조, 그리고 상기 거울 매핑 동작 중 어느 것이 수행되었는지를 가리키는 데이터에 의해 인코딩하는 단계를 포함한다.

일 실시예에서, 제1 및/또는 제2 클러스터링 동작은 적응적 k-평균 클러스터링을 사용한다.

일 실시예에서, 구체 분절의 개수는 m = 8이고, 각 분절 내의 구획의 개수는 n = 6이다. 일 실시예에서, 상기 구체 분절은 구체 삼각형이다.

일 실시예에서, 상기 인코딩 방법은 상기 매핑 단계 후에 상기 매핑된 제1 클러스터의 더 많은 요소가 상기 미리 정의된 구획에 놓이도록 3D 메시 모델을 회전시키는 단계를 더 포함한다.

일 실시예에서, 제2 클러스터의 대표 예측자 요소는 상기 법선 성분 중 하나인데, 이는 클러스터의 실제 멤버이다. 다른 실시예에서, 이는 가상의(존재하지 않는) 예측자 요소이다.

일 실시예에서, 상기 거울 매핑 동작 중 어느 것이 수행되었는지를 가리키는 데이터는 법선 성분이 어느 제1 클러스터에 속하는지를 식별하는 데이터와, 상기 거울 매핑 동작 중 어느 것이 그 제1 클러스터에 대해 수행되었는지를 가리키는 매핑 지시 데이터를 포함한다.

일 실시예에서, 상기 거울 매핑 동작 중 어느 것이 수행되었는지를 가리키는 데이터는 구체를 m개의 동등한 구체 분절로 분할하고 상기 구체 분절 각각을 n개의 동등한 구획으로 분할하는 것을 정의하는 데이터를 포함한다.

일 실시예에서, 3D 메시 모델의 법선 성분을 인코딩된 비트스트림으로부터 디코딩하기 위한 방법은 인코딩된 비트스트림으로부터 예측자인 법선 성분의 데이터를 추출하는 단계, 예측자에 대한 식별자를 추출하는 단계, 인코딩된 비트스트림으로부터 인코딩된 법선 성분과 관련된 데이터를 추출하는 단계(상기 데이터는 잔차 데이터, 예측자 식별 데이터 및 매핑 데이터를 포함하고, 상기 매핑 데이터는 복수의 미리 정의된 거울 매핑 동작 각각이 인코딩된 법선 성분에 대해 수행될지 여부를 가리킴) 및 법선 성분을 디코딩하는 단계(잔차 데이터는 상기 예측자 식별 데이터에 따라 예측자에 부가되고, 결과적인 법선 성분은 상기 미리 정의된 거울 매핑 동작에 따라 매핑됨)를 포함한다.

디코딩 방법의 일 실시예에서, 매핑 데이터는 법선 성분에 대한 클러스터 식별 데이터 및 각 클러스터에 대한 클러스터 매핑 데이터를 포함하고, 클러스터 식별 데이터는 법선 성분을 클러스터와 연관시키고, 클러스터 매핑 데이터는 특정 클러스터와 관련되며, 복수의 미리 정의된 거울 매핑 동작 각각이 특정 클러스터와 연관된 법선 요소에 대해 수행될지 여부를 가리킨다.

일 실시예에서, 상기 디코딩 방법은 거울 동작 데이터를 비트스트림으로부터 추출하는 단계를 더 포함하는데, 상기 미리 정의된 거울 동작은 상기 거울 동작 데이터에 의해 정의된다.

일 실시예에서, 3D 메시 모델의 법선 성분을 인코딩하기 위한 장치는 도 7에 도시된 기능 블록에 대응되는 모듈을 포함한다.

일 실시예에서, 3D 메시 모델의 법선 성분을 디코딩하기 위한 장치는 도 8에 도시된 기능 블록에 대응되는 모듈을 포함한다.

일 실시예에서, 데이터 구조는 3D 메시 모델의 꼭지점 데이터 및 인코딩된 꼭지점 배향 데이터를 포함하는데, 인코딩된 꼭지점 배향 데이터는 적어도 예측자, 예측자와 연관된 식별자 및 인코딩된 꼭지점 배향과 관련된 데이터를 포함하고, 인코딩된 꼭지점 배향과 관련된 데이터는 잔차 데이터, 예측자 식별 데이터 및 매핑 데이터를 포함하며, 매핑 데이터는 복수의 미리 정의된 거울 매핑 동작 각각이 인코딩된 꼭지점 배향을 디코딩하기 위해 수행될지 여부를 가리킨다.

본 발명은 원리상으로 모든 현실적인 3D 메시 모델에 대해 유리하다. 본 발명은 특히 고르게 분포되지 않은 법선을 갖는 3D 메시 모델에 대해 유리하다. 3D 메시 모델이 더 많은 꼭지점을 가질수록(즉 모델이 더 클수록) 본 발명은 더 효과적이다. 또한, 모델이 법선의 제1 클러스터를 더 많이 가질수록 본 발명은 더 효과적인데, 그 까닭은 매핑 후에 결과적인 제2 클러스터가 더 클 것이기 때문이다.

도 2는 원통형인 3D 메시 모델의 배향축을 예시한다. 확인할 수 있는 바처럼, 법선들은 XY 평면 주위에서 모든 방향으로 분포되지만, XY 평면에서는 두 방향, 즉 위와 아래로만 분포된다. 따라서, 적어도 XY 평면의 법선들은 용이하게 클러스터링될 수 있고, 그 인코딩에 있어서 비트가 절감될 수 있다. 일 실시예에서, 개시된 법선 인코딩 방법은 3D 메시 모델의 모든 법선이 아닌 일부 법선에만 사용된다.

도 3은 다른 예시 3D 메시 모델의 배향축의 위치를 도시한다. 모델 형상에 따르면, 법선들은 단위 구체(31) 상의 그룹(31a 내지 31d)에 배치된다. 그룹 각각이 클러스터링될 수 있고, 각각의 클러스터는 이미 목표 분절 또는 구획에 있지 않은 한 미리 정의된 목표 분절 및 구획에 매핑된다. 클러스터가 이미 목표 분절에 있는 경우, 구획 매핑만을 수행하는 것으로 충분하다. 각각의 매핑 단계가 수행될 필요가 있는지 여부, 예컨대 인코딩 및 매핑 정보가 여전히 인코딩/디코딩될 필요가 있다.

도 4는 클러스터링 및 매핑 후의 단위 구체 상의 배향축들의 분포를 도시한다. 확인할 수 있는 바처럼, 도 3의 클러스터들 중 두 개(31a, 31b)는 동일 영역으로 매핑되었다. 따라서, 새로운 클러스터(41ab)가 재클러스터링 단계에서 생성된다. 이러한 새로운 클러스터(41ab)의 모든 요소들은 새로운 클러스터에 대한 예측자 역할을 하는 클러스터 대표(41abr)로부터 예측될 수 있다.

도 10은 다수의 원통형 연결 성분을 포함하는 가지 달린 촛불의 예시 3D 모델을 도시한다. 이들 각각은 도 2의 모델과 같은 정규 분포를 갖는다. 도 10의 b)는 모델의 제1 배향축들의 분포를 도시한다. 연결 성분의 배향축이 우세함을 확인할 수 있는데, 그 까닭은 많은 배향축이 원 위에 놓이기 때문이다. 도 10의 c)는 매핑 후의 제1 배향축들의 분포를 도시한다. 확인할 수 있는 바처럼, 매우 밀집한 두 개의 클러스터만이 주로 남아있고, 따라서 유리하게도 예측을 사용하여 인코딩될 수 있다.

본 발명은 또한 연결 성분의 배향축/법선(완전한 3D 모델의 일부일 뿐임)뿐만 아니라 완전한 3D 모델의 배향축/법선의 압축에 관한 임의의 시나리오에 적용될 수 있다.

다른 유형의 단위 구체 분절이 도 1에 도시된 바와 달리 구축될 수 있음에 주목해야 하는데, 이는 본 기술 분야의 당업자에게 자명할 것이며, 이 모두가 본 발명의 사상 및 범위 내에서 구상된다. 도 9는 몇몇 대안적인 가능성 중 하나를 도시하는데, 여기서는 8개의 구획 각각이 몇몇 박편(71n, 71s)으로 분리된다.

본 발명의 바람직한 실시예들에 적용되는 본 발명의 기본적인 신규한 특징들이 도시, 기술 및 지적되었지만, 개시된 장치의 형태 및 세부 사항과 그 동작에 있어서 기술된 장치 및 방법의 다양한 생략과 치환 및 변경이 본 발명의 사상으로부터 벗어나지 않고 본 기술 분야의 당업자에 의해 이루어질 수 있음을 이해할 것이다. 또한, 모든 실시예는 서로 명백히 상충되지 않는 한 자유롭게 결합될 수 있다. 동일한 결과를 달성하기 위해 실질적으로 동일한 방식으로 실질적으로 동일한 기능을 수행하는 요소들의 모든 조합이 본 발명의 범위 내에 있도록 명시적으로 의도된다. 기술된 일 실시예로부터의 요소들을 다른 실시예로부터의 요소들로 치환하는 것이 또한 완전히 의도 및 구상된다.

본 발명은 순전히 예시로서 기술되었고, 세부 사항의 수정은 본 발명의 범위로부터 벗어나지 않고 이루어질 수 있음을 이해할 것이다.

설명 및 (적절한 경우) 청구항과 도면에 개시된 각각의 특징은 독립적으로 또는 임의의 적절한 조합으로 제공될 수 있다. 특징들은 적절한 경우 하드웨어, 소프트웨어, 또는 이 둘의 조합으로 구현될 수 있다. 청구항에 나타나는 참조 번호는 오직 예시를 위한 것이며, 청구항의 범위에 대한 한정적인 효과를 갖지 않을 것이다.

Claims

법선 성분(normal component)이 이것의 단위 구체(unit sphere) 상의 위치에 의해 정의 가능한 3D 메시 모델의 법선 성분들을 인코딩하기 위한 방법으로서,
상기 3D 메시 모델의 법선 성분들을 클러스터링하는 단계 - 하나 이상의 제1 클러스터가 획득되고, 각각의 법선 성분은 상기 제1 클러스터들 중 적어도 하나의 요소임 -;
상기 법선 성분들의 제1 클러스터들의 각각에 대해 그 요소들 중 대부분이 속하는 구체 구획(sphere sector)을 결정하는 단계 - 구체 구획은 구체를 m개의 동등한 구체 분절들(sphere segments)로 분할하고 상기 구체 분절들의 각각을 n개의 동등한 구획들로 분할함으로써 획득 가능함 -;
상기 결정 단계에 따라 상기 구획들 중 미리 정의된 구획에 속하지 않은 법선 성분들을 미리 정의된 구획으로 매핑하는 단계 - 상기 매핑은 int(log₂(m)+log₂(n)+1)회까지의 거울 매핑 동작들을 포함함 -;
상기 법선 성분들을 재클러스터링(re-clustering)하는 단계 - 하나 이상의 제2 클러스터가 획득되고, 각각의 법선 성분은 상기 제2 클러스터들 중 적어도 하나의 클러스터의 요소임 -;
상기 법선 성분들을 양자화하는 단계;
상기 제2 클러스터들의 각각에 대해 대표 예측자 요소를 결정하는 단계;
상기 법선 성분들에 대한 잔차들(residuals)을 결정하는 단계 - 잔차는 법선 성분과 그 각자의 예측자 요소 사이의 차이임 -; 및
법선 성분을 그 잔차, 그 예측자 요소에 대한 참조, 그리고 상기 거울 매핑 동작들 중 어느 것이 수행되었는지를 가리키는 데이터에 의해 인코딩하는 단계
를 포함하는 방법.
제1항에 있어서,
상기 제1 및/또는 제2 클러스터링 동작은 적응적 k-평균 클러스터링을 사용하는 방법.
제1항 또는 제2항에 있어서,
m = 8이고 n = 6이며, 상기 구체 분절들은 구체 삼각형들인 방법.
제1항 내지 제3항 중 어느 한 항에 있어서,
상기 매핑 단계 후에, 매핑된 제1 클러스터들의 더 많은 요소들이 상기 미리 정의된 구획에 놓이도록 상기 3D 메시 모델을 회전시키는 단계를 더 포함하는 방법.
제1항 내지 제4항 중 어느 한 항에 있어서,
상기 제2 클러스터의 상기 대표 예측자 요소는 상기 법선 성분들 중 하나인 방법.
제1항 내지 제5항 중 어느 한 항에 있어서,
상기 거울 매핑 동작들 중 어느 것이 수행되었는지를 가리키는 데이터는, 상기 법선 성분이 어느 제1 클러스터에 속하는지를 식별하는 데이터와, 상기 거울 매핑 동작 중 어느 것이 상기 제1 클러스터에 대해 수행되었는지를 가리키는 매핑 지시 데이터를 포함하는 방법.
제1항 내지 제5항 중 어느 한 항에 있어서,
상기 거울 매핑 동작들 중 어느 것이 수행되었는지를 가리키는 데이터는, 구체를 m개의 동등한 구체 분절들로 분할하고 상기 구체 분절들의 각각을 n개의 동등한 구획들로 분할하는 것을 정의하는 데이터를 포함하는 방법.
법선 성분이 이것의 단위 구체 상의 위치에 의해 정의 가능한 3D 메시 모델의 법선 성분들을 인코딩된 비트스트림으로부터 디코딩하기 위한 방법으로서,
상기 인코딩된 비트스트림으로부터 예측자인 법선 성분의 데이터를 추출하고 상기 예측자에 대한 식별자를 추출하는 단계;
상기 인코딩된 비트스트림으로부터, 인코딩된 법선 성분과 관련된 데이터를 추출하는 단계 - 상기 데이터는 잔차 데이터, 예측자 식별 데이터 및 매핑 데이터를 포함하고, 상기 매핑 데이터는 복수의 미리 정의된 거울 매핑 동작들의 각각이 상기 인코딩된 법선 성분에 대해 수행될지 여부를 나타냄 -; 및
상기 법선 성분을 디코딩하는 단계 - 상기 잔차 데이터는 상기 예측자 식별 데이터에 따라 상기 예측자에 부가되고, 결과적인 법선 성분은 상기 미리 정의된 거울 매핑 동작들에 따라 매핑됨 -
를 포함하는 방법.
제8항에 있어서,
상기 매핑 데이터는 상기 법선 성분에 대한 클러스터 식별 데이터, 및 각 클러스터에 대한 클러스터 매핑 데이터를 포함하고,
상기 클러스터 식별 데이터는 상기 법선 성분을 클러스터와 연관시키며,
상기 클러스터 매핑 데이터는 특정 클러스터와 관련되고, 복수의 미리 정의된 거울 매핑 동작들의 각각이 상기 특정 클러스터와 연관된 법선 요소에 대해 수행될지 여부를 나타내는 방법.
제8항 또는 제9항에 있어서,
거울 동작 데이터를 상기 비트스트림으로부터 추출하는 단계를 더 포함하고,
상기 미리 정의된 거울 동작은 상기 거울 동작 데이터에 의해 정의되는 방법.
3D 메시 모델의 법선 성분들을 인코딩하기 위한 장치로서,
제1항 내지 제7항 중 어느 한 항에 따른 방법을 이용하는 장치.
3D 메시 모델의 법선 성분들을 디코딩하기 위한 장치로서,
제8항 내지 제10항 중 어느 한 항에 따른 방법을 이용하는 장치.
데이터 구조로서,
3D 메시 모델의 꼭지점 데이터 및 인코딩된 꼭지점 배향(orientation) 데이터를 포함하고,
상기 인코딩된 꼭지점 배향 데이터는 적어도 예측자, 상기 예측자와 연관된 식별자 및 인코딩된 꼭지점 배향과 관련된 데이터를 포함하며,
상기 인코딩된 꼭지점 배향과 관련된 데이터는,
- 잔차 데이터;
- 예측자 식별 데이터; 및
- 매핑 데이터
를 포함하고,
상기 매핑 데이터는 복수의 미리 정의된 거울 매핑 동작들의 각각이 상기 인코딩된 꼭지점 배향을 디코딩하기 위해 수행될지 여부를 나타내는 데이터 구조.
제13항에 있어서,
상기 매핑 데이터는 상기 꼭지점 배향에 대한 클러스터 식별 데이터, 및 각 클러스터에 대한 클러스터 매핑 데이터를 포함하고,
상기 클러스터 식별 데이터는 상기 꼭지점 배향을 클러스터와 연관시키며,
상기 클러스터 매핑 데이터는 특정 클러스터와 관련되고, 복수의 미리 정의된 거울 매핑 동작들의 각각이 상기 특정 클러스터와 연관된 꼭지점 배향에 대해 수행될지 여부를 나타내는 데이터 구조.