ARTag, An Improved Marker System Based on ARToolkit S.Y. Lee

Contents Intro Planar Marker Systems ARToolkit ARTag False Positive Marker Detection Uniqueness of Markers ARTag and ARToolkit Processing Time Conclusion

Intro AR(Augmented Reality, mixed Reality) 가상 object를 실상에 rendering 하여 보여줌 일반적으로 HMD(head mounted display)을 위한 응용 프로그램에 사용할 목적 HMD나 카메라의 위치를 가장 간단하고 비용이 적게 드는 passive marker pattern과 computer vision을 이용 미래에는 markerless 기술이 전망이 밝으나, 현재 가장 견고한 시스템들은 2D planar marker system을 사용

Planar Marker System

Planar Marker System(1) - Barcode Maxicode, Data matrix, QR : convey shipping information, industrial setting (labeling) 데이터를 복구 하는 Error correction 체계 존재. Pattern을 이치화 : 픽셀당 decision -> threshold decision으로 축소 조명과 카메라 감도 (camera sensitivity) 요구 사항을 줄임. 신호의 선형화( linearization of the signal )의 필요성을 없앰

Planar Marker System(1) - Barcode Commercial system step Identification of the marker: 마커를 구분하는 유일한 식별자 ( Maxicode system bull’s eye) Alignment : digitization을 위해 pattern 정렬 Digitization: threshold 과정 ( 절대값, 또는 local ) 0과 1들로 추출 Error Detection and Correction : data의 무결 성을 신뢰할 수 있는 단계로 향상시킴 Decoding : bit pattern을 사용할 정보로 변환

Planar Marker System(2) - Ring Coded Marker, AIcon, Capture3D 사진 측량법 application에 사용 마커의 개수 한정 Intersense: 여러 개의 반지름을 이용하여 확장, But 여러 개 마커 사용-> 총 픽셀수 증가

Planar Marker System(3) -AR marker ARToolkit, ARSTudio 주로 한 개의 마커만 사용 위치 추출에 적어도 4개의 분명한 포인트 필요 ARToolkit: 사각형 외곽선을 사용하여 코너 네개의 포인트를 사용

<ARToolkit marker> Dr.Hirokazu Kato of Osaka University(Japan) Planar 마커를 사용 쉽게 프린트하여 사용 가능. 검은색 사각형 외곽선, 안쪽에 다양한 패턴으로 구성 Method 외곽선 사용 identification 과 alignment수행. sampling할 격자를 정의하여 추출 library에 이미 존재하는 마커들과 비교. <ARToolkit marker>

ARToolkit (2) 흑백의 차이를 이용하여 간단한 임계값 한 개로 마커 구분하여 이진화 : robust한 operation이 가능 임계값 이하의 값을 갖는 연결된 픽셀들의 그룹들의 윤곽선을 찾음 직선이 네개인 윤곽선을 잠재적 마커로 식별

ARToolkit (3) 마커의 윤곽선: perspective distortion(원근감 왜곡 효과) 제거, 정식 전경 ( canonical front view ) 로 가져오는데 사용 윤곽선 안 쪽을 NxN( original 16x16 )격자들로 샘플, pattern file 참조 격자들과 비교. Confidence factor : 저장되어 있던 prototype과 샘플한 16x16 벡터와 normalized vector dot product 한 결과. 임계값에 의하여 존재여부 결정. Pattern file: 4개의 회전에 대한 각각 조명, 거리 환경이 다른 3개의 버전들에 대한정보

ARTag(1) National Research Council of Canada 2064개의 마커를 사용 ARToolkit의 성능 향상, pattern file도 필요하지 않음. 안쪽의 pattern에 digital하게 접근, 잘못된 마커 인식이나 (falsely detected) 마커 혼동실패 감소 검은색 바탕에 흰색 패턴 지원

ARTag(2) ARToolkit과 DataMatrix의 장점을 뽑아 minimal, robust한 AR 마커 detection: 사각형 외곽선을 인식하는 ARToolkit과 같음 외곽선 안의 6X6 격자로 나눔 각 셀은 1bit의 디지털 데이터 (검은색/흰색): 각각 4가지 방향에 36bit의 정보 추출 36bit 정보에서 10bit만이 마커의 ID로 사용 나머지 26bit = redundancy DataMatrix: robust data communication capability, but 이미지가 평면과 평행해야 함, perspective distortion한 view에 부적절. False detection, identification

ARTag(3) Encoding Phase (creation marker from the ID) Decoding phase ( recognition ID from 36-bit code )

ARTag(4) XOR operation : ID에 ‘0’을 사용 할 수 있도록 CRC-16 : CRC-16 polynomial Deconvolution 결과, remainder는 ‘0’이어야 됨. FEC : 36bit code에서 에러를 detect 하여 고침. False positive rate을 조금 증가시키지만 false negative rate을 개선시킴.

False Positive Marker Detection(1) ARToolkit ARTag : 사각형 모양이 배경에 있고 pattern이 pass될 경우 발생.

False Positive Marker Detection(2) ARToolkit 성능 향상 : 특정 application에 적합한 카메라와 조명, 환경을 맞추는 것 마커가 보여지면 높은 confidence factor 값을 갖게 됨. Confidence factor의 임계값을 최대치로 올리는 것이 목적 ARTag: 패턴을 디지털 코드로 process하기 때문에 false positive rate가 훨씬 적음. 마커가 아닌 사각형이 마커로 인식될 확률은 0.0079 % 35.6% N=2 1333 * 4092

False Positive Marker Detection(3)

False Positive Marker Detection(4) ARTag: False Positive가 발생하지 않음. 확률 0.0079%로 사각형 안쪽에 36bit의비슷한 패턴이 있는 경우의 확률 실제로 False Positive가 발생할 확률은 더 낮음. robot navigation에서 landmark로 사용 가능

False Positive Marker Detection(3)

False Positive Marker Detection(5) c.f. 0.75의 값을 갖기 위해서는 최소한 40pixel 너비 필요 c.f. = 0.90일때 detection이 크게 쓸모없음.

Uniqueness of Markers: Reducing Inter-Marker Confusion(1) Inter-Marker Confusion : ARToolkit, ARTag의 마커가 인식 될 때 엉뚱한 마커의 ID가 반환. ARToolkit: MSE(Mean Squared Error )로 접근 image 안쪽 256개의 vector들의 Euclidean distance를 찾아내어 마커 사이의 유사성을 계산 “C”와 “G”의 경우 0.820 ( c.f. 임계값을 0.8로 잡아도 이 두 마커는 혼동될 수 있음.) ARTag: 마커 사이의 혼동은 하나의 디지털 symbol을 다른 것으로 혼동할 확률을 계산하여 분석 Hamming Distance( 두 디지털 시퀀스의 서로 다른 비트들의 수 )를 사용하여 계산 모든 마커들 사이의 Hamming distance가 커야 유리

Uniqueness of Markers: Reducing Inter-Marker Confusion(2) Ex) 마커 A가 B로 혼동될 확률 ( rotation만 고려 ) 각각 h.d = 10 (0도) hd = 12 (90도) hd = 16 (180도) hd = 24 (270도) P = 비트가 flip될 확률 mirroring을 고려할 경우 4가지 방향과 reflected 된 4가지 확률 포함, 총 8 가지로 계산. 모든 마커 적용, 정리 식 (2)와 같은 형태가 되어 마커 A가 다른 마커로 잘못 인식될 총 확률을 구함.

Uniqueness of Markers: Reducing Inter-Marker Confusion(3) ARTag inter-marker confusion 확률 계산 식 P = 비트가 flip될 확률 n= hammaing distance HD(n) = hamming distance가 n인 case들의 수

Uniqueness of Markers: Reducing Inter-Marker Confusion(4) 확률(p): 시스템의 여러 가지 요인(noise etc)에 의 Hamming distance:시스템에 돕립적 마커 set을 histogram으로 계산 가능. histogram을 사용하여 inter-marker confusion 확률을 감소, 시스템을 최적화 할 수 있음. 특히 histogram에서 n의 값이 작은 확률 값들을 줄일 수 있는 방법을 모색 Hamming distance histogram은 각각의 마커에 따라 다르게 나타남. 모든 마커에 대한 확률을 더하여 총 마커 혼동의 확률을 구함 histogram에서 n의 값이 작은 확률 값들을 줄일 수 있는 방법: 히스토그램을 오른쪽으로 push 하거나, 처음의 non-zero 값을 갖는 HD(n) 값이 적을수록 마커 혼동에 더 안전하다.

Uniqueness of Markers: Reducing Inter-Marker Confusion(5) 처음 몇 개의 n에서 non-zero 값을 갖는 값들이 총 확률을 좌우 이를 기반으로 총 마커 set의 최적화 가능 모든 마커의 4가지 rotation 대한 hamming distance를 모아 histogram 작성 최소 non-zero value와 histogram의 처음 부분의 면적을 줄이도록 시도. 이를 고려하여 시스템 설계

Uniqueness of Markers: Reducing Inter-Marker Confusion(6) 시스템에서 parameter로 사용되는 변수들 고려 XOR mask: linearity of the GF-2operators checksum convolution: constant polynomial XOR mask, Checksum은 H.D.에 영향을 주지 못함. convolution code(FEC): 최적의 histogram을 결정하는 변수로 사용.

Uniqueness of Markers: Reducing Inter-Marker Confusion(7) 최적의 Hamming distance histogram 최소 Hamming distance와 최초 몇 개의 entry에 대한 면적이 적은 것 선택 사용할 수 있는 6개의 polynomial의 조합 (15개): 선택된 histogram은 다른 histogram에 비해 n=4일때의 값이 클 수도 있지만, n=10일 떄의 값이 훨씬 적기 때문에 n=4에 해당하는 마커들은 not-recommended marker로 지정함.

Uniqueness of Markers: Reducing Inter-Marker Confusion(8) Mirroring Mirroring은 자주 일어나지 않음 마커의 반사된 상은 인식되면 안됨 Hamming distance가 커야 됨 Histogram에서 자기 자신의 반사된 상과 Hamming distance가 2밖에 안되는 270 마커는 not-recommended list에 추가되었다.

Uniqueness of Markers: Reducing Inter-Marker Confusion(9) Not recommended marker list Hamming distance Mirroring ( 44개의 마커 (12개의 sub-ID) : 12 hamming distance, 10 mirror )

Uniqueness of Markers: Reducing Inter-Marker Confusion(10) Recommended markers Hamming Distance 차이가 크게 되는 순서 가장 Hamming distance가 크게 되는 순서. H.D.는 한 Order 위의 마커와의 H.D. artag_get_id() function으로 sequential 하게 사용 가능.

Uniqueness of Markers: Reducing Inter-Marker Confusion(11) Hamming distance Histogram using Recommended markers in order 1. 모든 마커 (mirror 까지 고려) 사용 2. 1023 sub-Id만 사용된 경우 1. 모든 마커 (mirror 까지 고려) 사용 2. 1023 sub-Id만 사용된 경우

Uniqueness of Markers: Reducing Inter-Marker Confusion(11) Hamming distance Histogram using Recommended markers in order 3. recommended 1002 마커만 사용 4. Recommended 50 마커만 사용 3. recommended 1002 마커만 사용 4. Recommended 50 마커만 사용

Minimum Pattern Size and the False Negative Detection Ratio(1) ARToolkit : 한 개의 마커 최소 14pixel wide, 여러 개 마커 사용, 60 pixel ARTag : 35-40 pixel wide( 95% detection) 12pixel인 경우 occasionally detected. Pattern 이 10 unit이기 때문에 그 두배인 20pixel이 lower bound가 됨.

Minimum Pattern Size and the False Negative Detection Ratio(2) Pixel width에 따른 인식률 ARToolkit 이나 ARTag는 검은색 border가 배경과 대비되어야 함. 배경: marker 너비의 50%정도 필요

Processing Time (1) ARTag: 6X6 points만 sample하기 때문에 빠름 multiplication하는 횟수가 훨씬 적음 ARToolkit : 한 마커당 3328번 (3072 for correlating, 256 for normalizing. ) Ex) Library 10 patterns -> 33280번 (library 증가에 비례) ARToolkit이 10개의 마커 사용 & ARTag 가 2046개의 마커 사용의 빠르기 비슷. ARTag: 처음에 36 bit deconvolution operation, two searchs 12bytes long 한번만 하면됨, FEC에 통과 되면 deconvolution 3번더, 이후 XOR stage. Library에 존재하는 마커수와 상관 없음

Processing Time (2) ARToolkit & ARTag Processing Time ARToolkit의 경우 library에 마커가 10개 마커가 보이지 않은 경우 processing time비슷.

Conclusion – ARTag improvements ARToolkit의 Marker system 개선 Digitally encoded error corrected ID Pattern file이 필요 없음 낮은 false negative rate 낮은 False positive error rate (%0.0079) 낮은 inter-marker confusion rate 여러개의 마커가 동시에 사용될 때 성능이 좋음.