무선 멀티미디어 단말기 상에서 효과적인 이미지 브라우징을 위한 M-Tree 기반의 인덱싱 방법
An Indexing Method based on M-Tree for Effective Image Browsing in Mobile Multimedia Devices
- 발행기관 서강대학교 컴퓨터공학과
- 지도교수 낭종호
- 발행년도 2009
- 학위수여년월 2009. 2
- 학위명 석사
- 실제URI http://www.dcollection.net/handler/sogang/000000044818
- 본문언어 한국어
초록/요약
최근 플래시 메모리의 대용량화와 함께 휴대 기기 상에서 대량의 사진을 보관하는 것이 가능하게 되었다. 이에 따라 휴대 기기 환경에 적합한 대량의 사진들에 대한 검색 및 탐색 방법이 필요하게 되었다. 대부분의 휴대 기기는 화면 크기의 제한을 가지며, 휴대 기기에서 촬영되어 저장된 사진은 일반 웹 상의 이미지에 비하여 사용자에게 비교적 덜 생소하기 때문에 내용 기반의 계층적 클러스터링을 통한 브라우징 방법이 적합하다고 볼 수 있다. 휴대 기기 환경에서 계층적 클러스터링을 구축하기 위해서는 저 수준 특징 데이터를 통한 정확한 유사도 측정, 특징 데이터의 추출 비용, 브라우징에 적합한 계층적 클러스터링 방법, 플래시 메모리상에서 구축되는 클러스터링의 입출력 비용등과 같은 문제가 발생한다. 본 논문에서는 이러한 사항들에 대한 충분한 고려와 함께 설계 및 구현된 휴대 기기 환경에서 내용 기반의 계층적 클러스터링을 통한 브라우징 및 검색 시스템을 제안한다. 특징 데이터에 대한 유사도 측정의 정확도 문제에 대해서는 블록 기반의 근사 영역 분할 방법을 사용하였으며, 휴대 기기 환경을 고려하여 적절한 수준의 블록 크기를 결정하기 위한 실험을 수행하였다. 특징 데이터의 추출 비용 문제에 대해서는 MPEG-7 Color Structure Descriptor와 Dominant Color Descriptor에 대하여 각각 PBH와 ARP/RARP 방법을 사용하여 계산 량을 약 20% 이하로 감소시켰다. 브라우징에 적합한 클러스터링 방법에 대해서는 고차원 거리 공간과 동적 구축에 적합한 M-Tree를 기반으로 하였으며, 노드 선택 방법과 노드 분할 조건 및 분할 방법들을 브라우징에 적합하도록 변경하여 노드 응집도와 클러스터링 정확도를 각각 약 2배, 1.5배 정도 증가시켰다. 이러한 방법들을 적용하여 400MHz ARM9 PDA상에서 플래시 메모리에 저장 된 홈 포토 3000장에 대한 브라우징 및 검색 시스템을 구현하였고, 플래시 메모리의 높은 쓰기 비용 문제를 위하여 노드 캐싱 방법을 적용하여 입출력 비용을 약 70%정도 감소시켰으며, 노드 분할 방법을 적용하여 쓰기 횟수를 약 7%정도로 현저히 감소시켰다. 제안한 문제 해결 방법들과 시스템에 기반한다면 휴대 기기 환경에서 효과적인 계층적 클러스터링을 응용하는 시스템을 구축할 수 있을 것이다.
more초록/요약
In recent, it becomes normal to store a large amount pictures in mobile device thanks to the increase of flash memory capacity. Browsing scheme via content-based hierarchical clustering is very proper one because the mobile device has the limitation of display size as well as the pictures taken by mobile device are more familiar with user than general web images. For building hierarchical clustering on mobile environment, the several issues are required such as the robust calculation of similarity by low-level feature data, the high computation cost for feature extraction, the hierarchical clustering method that meets the case of browsing, and I/O cost of construction of clustering on flash memory. In this thesis, with sufficient consideration of above issues, we propose both browsing and search system through content-based hierarchical clustering built on mobile environment. For the problem of accuracy of similarity measuring in feature domain, we not only adopt block-based approximated image segmentation method but also perform the experiment to decide proper block size considering mobile environment. For the cost of feature extraction, we use PBH to reduce of duplicated computation during extracting MPEG-7 Color Structure Descriptor and ARP/RARP schemes for Dominant Color Descriptor, so that total computation cost is reduced to about 20%. For the clustering method that fits the purpose of browsing, we share the basic data structures with the M-Tree which is designed for indexing in high-dimensional metric space as well as dynamic insertion and deletion, but we modify the node selection scheme, split condition, and split policy to be suitable for browsing effect. The result of experiment shows improvement of node cohesion by 2 times and clustering accuracy by 1.5. Applying these methods, browsing and search system is implemented with 3,000 home photos stored in flash memory, on 400MHz ARM9 PDA. Our system reduced 70% write costs of flash memory via node caching method and 7% write times via node split method. Based on these solutions and systems, we can build efficient hierarchical clustering system for mobile device.
more목차
제１장 서론 = 11
제２장 관련 연구 = 15
제１절 내용 기반 유사 검색 = 15
제２절 MPEG-7 시각 기술자 = 16
제３절 고차원 데이터의 클러스터링 및 M-Tree 방법 = 19
제４절 플래시 메모리의 특성 = 22
제３장 휴대 기기에서 촬영된 사진들에 대한 유사도 측정의 정확도 향상 방법 = 24
제１절 블록 기반의 영역 비교 방법 = 24
제２절 실험 결과 및 분석 = 26
제４장 MPEG-7 색상 기술자 추출의 성능 향상 방법 = 31
제１절 Color Structure Descriptor의 추출 성능 향상 방법 및 실험 결과 = 31
제２절 Dominant Color Descriptor의 추출 성능 향상 방법 및 실험 결과 = 35
제５장 브라우징을 위한 M-Tree기반의 계층적 클러스터링 = 40
제１절 노드 선택 방법 = 40
제２절 노드 분할 조건 = 43
제３절 노드 분할 방법 = 45
제４절 실험 결과 및 분석 = 45
제６장 휴대 기기 상에서 계층적 클러스터링을 통한 사진 탐색 시스템의 구현 = 53
제１절 시스템 구조 = 53
제２절 플래시 메모리 상에서의 M-Tree 입출력 성능 향상 = 56
제３절 삽입 성능 평가 = 65
제７장 결론 = 67
참고문헌 = 69
그림목차
그림 １-１ 계층적 클러스터링을 통한 브라우징 = 12
그림 １-２ 본 논문의 연구 항목 = 13
그림 ２-１ 특징 데이터를 통한 유사 검색 = 15
그림 ２-２ 영역 기반 이미지 비교 = 16
그림 ２-３ Color Structure Descriptor의 추출 과정 = 17
그림 ２-４ Dominant Color Descriptor의 추출 과정 = 17
그림 ２-５ Color Layout Descriptor의 추출 과정 = 18
그림 ２-６ M-Tree 의 기본 구조 = 20
그림 ２-７ M=3인 경우의 M-Tree 삽입 과정 = 21
그림 ２-８ 2Gb, 2Kb Page SLC NAND 구조 = 22
그림 ２-９ 플래시 메모리의 블록 병합 연산 = 23
그림 ３-１ Color Structure Descriptor 의 전역 비교 시의 오차 = 25
그림 ３-２ 부분 영역의 크기 차이 경우 = 26
그림 ３-３ 영역 기반 비교의 Precision과 Recall = 27
그림 ３-４ 블록 크기에 따른 Precision과 Recall = 28
그림 ３-５ 블록 크기에 따른 추출 비용 = 29
그림 ３-６ 영역 기반 비교의 결과 예시 = 30
그림 ４-１ Color Structure 추출 과정의 Accumulation 알고리즘 = 33
그림 ４-２ Presence-Bit-Histogram 구조 = 33
그림 ４-３ Presence-Bit-Histogram 을 이용한 Accumulation 알고리즘 = 34
그림 ４-４ LBA (Linear Block Algorithm) = 35
그림 ４-５ : RGB공간에서 픽셀들의 각 클러스터 중심에 대한 지역성 = 36
그림 ４-６ : Approximate Rectangle Partition = 37
그림 ４-７ : 점진적 근사 ARP 계산 방법 = 37
그림 ４-８ : ARP 적중률 = 38
그림 ４-９ : RARP 적중률 = 38
그림 ４-１０ : ARP/RARP 를 이용한 픽셀 클러스터링 알고리즘 = 39
그림 ５-１ : 브라우징에 적합하지 않은 M-Tree 삽입 예 = 41
그림 ５-２ : 브라우징 효과가 향상된 노드 선택 예 = 42
그림 ５-３ : 브라우징에 적합하도록 제안한 노드 선택 방법 = 43
그림 ５-４ : 레벨에 따른 노드 응집도 = 44
그림 ５-５ : 분할 방법에 따른 브라우징 효과의 비교 = 45
그림 ５-６ : 노드 응집도 C0 (30 홈 포토 셋) = 46
그림 ５-７ : 클러스터링 정확도 Accuracy0 (30 홈 포토 셋) = 47
그림 ５-８ 검색 성능 결과 = 48
그림 ５-９ : 사진 300장에 대한 M-Tree의 클러스터링 결과 = 50
그림 ５-１０ : 사진 300장에 대한 변경된의 클러스터링 결과 = 52
그림 ６-１ : 내용 및 시간 기반 계층적 브라우징 = 54
그림 ６-２ : 사용자 인터페이스의 구성 = 55
그림 ６-３ : 브라우징 및 검색 실행 예 = 55
그림 ６-４ : M-Tree의 노드 쓰기 연산 = 56
그림 ６-５ : 노드 접근 패턴 = 58
그림 ６-６ 노드 캐싱의 성능 측정 = 58
그림 ６-７ : Node Partiality 현상 = 59
그림 ６-８ : 노드 분할 방법의 구조 = 60
그림 ６-９ : 노드 분할 효과의 예 = 62
그림 ６-１０ : 지연 쓰기를 통한 읽기 인다이렉션 감소 = 62
그림 ６-１１ : 노드 분할 방식을 사용하는 경우의 노드 입출력 알고리즘 = 63
그림 ６-１２ : 노드 분할 성능 측정 = 64
그림 ６-１３ : 노드 분할 성능 측정 = 64
그림 ６-１４ : 노드 분할 방식 적용 시 입출력 시간의 감소 = 65
그림 ６-１５ : 삽입 성능 비교 = 65
그림 ６-１６ : 총 삽입 반응 속도 비교 = 66
표목차
표 ２-1 : MPEG-7 색상 기술자의 추출 성능 = 18
표 ４-1 : Color Structure Descriptor의 각 추출 과정의 비용 = 31
표 ４-2 : 400MHz ARM9에서 640×480 이미지에 대한 CSD 추출 성능 향상 = 34
표 ４-3 : RARP를 사용한 최적화의 성능 측정 = 39
표 ６-1 : 플래시 메모리 상에서 M-Tree 삽입 비용 = 57
