[알고리즘][객체관리모듈][문자인식]알고리즘의 조건, 객체관리모듈 알고리즘, 문자인식 알고리즘, 단어이동텍스트워터마킹 알고리즘, 압축 알고리즘, 셀기반의 셀추출 알고리즘, 제안한 모양분해 알고리즘 분석

소개글

[알고리즘][객체관리모듈][문자인식]알고리즘의 조건, 객체관리모듈 알고리즘, 문자인식 알고리즘, 단어이동텍스트워터마킹 알고리즘, 압축 알고리즘, 셀기반의 셀추출 알고리즘, 제안한 모양분해 알고리즘 분석에 대한 보고서 자료입니다.

목차

Ⅰ. 개요

Ⅱ. 알고리즘의 조건
1. 입력
2. 출력
3. 명확성(Definiteness)
4. 유한성(Finiteness)
5. 유효성(Effectiveness)

Ⅲ. 객체관리모듈 알고리즘
1. 단일 파티션 방법
2. 객체 연결 방법
3. 파티션 할당 방법
4. 병합 방법

Ⅳ. 문자인식 알고리즘
1. 문서 처리 과정(Document Processing)
2. 전처리 과정(Preprocessing)
3. 특징 추출 과정(Feature Extraction)
4. 분류 과정(Classification)
5. 후처리 과정(Postprocessing)

Ⅴ. 단어이동텍스트워터마킹 알고리즘
1. 기본 원리
2. 알고리즘
1) 단어의 분류
2) 워터마크 삽입 알고리즘

Ⅵ. 압축 알고리즘
1. 손실코딩
2. 비손실 코딩
3. 압축 알고리즘의 구현
1) RLC[running length coding]
2) VLC[Variable Length Coding]
3) 허프만 코딩[Huffman coding]
4) DBC[Dictionary Based Coding]
5) D C T [손실 코딩;discrete cosine transform]

Ⅶ. 셀기반의 셀추출 알고리즘
1. 개요
2. 셀 추출 알고리즘의 해석적 성능 모델
1) 동기 유지 시간
2) 동기 획득 시간

Ⅷ. 제안한 모양분해 알고리즘

참고문헌

본문내용

비트열로 대치되었다.
가장 많이 사용되는 \'A\'는 2비트 , 가장 낮은 빈도를 갖는 문자 \'F\'는 4비트로 대치되었다.
4) DBC[Dictionary Based Coding]
DBC는 문자를 읽어 가면서 한 개의 단어를 사전식으로 저장해 가면서 같은 단어가 나오면 토큰으로 바꾸어 가면서 바꿀 단어가 토큰보다 긴 비트일 때 압축 효과가 나타난다. 아울러 PC상에서 사용되고 있는 대부분의 압축 유틸리티들이 채용하고 있으며 보다 빠른 속도와 검색을 위해서 추가적인 방법이 사용된다. 특징을 간단히 요약하면 다음과 같다.
문자의 빈도와는 관계없이 압축을 수행한다
데이타를 처음부터 끝까지 읽지 않는다
2개이상의 문자를 하나의 토큰으로 바꾼다
토큰의 크기가 대치할 문자열보다 작은 경우 압축이 발생한다
121-011 서울시 마포구 아현동을 나타낸다.
990.999 듀우이의 10진 도서분류법에 의하면 국제 도박진흥회지음
민속도박 제 3편 고도리에 대한 모든것을 나타낸다.
DBC의 단적인 예를 든 것이다.
5) D C T [손실 코딩;discrete cosine transform]
DCT는 변환 코딩으로서 x(n)을 0·n·N-1이외는 0을 갖는 N개의 값을 수열이라고 할때 DCT의 여러 형태중 우수 대칭인 구조로 하여 DFT와 연관 시켜보자.
N개의 x(n)을 2N개의 y(n)으로 하고 y(n)을 DFT하여 Y(k)를 얻고 Y(k)로 부터 Ck를 구한다. 예를 들어 N=4일때 Y(n)은 n=N-1/2점에 대하여 대칭적이다 그리고 X(n)의 주기적인 구조는 불연속이나 Y(n)의 주기적인 구조는 더 이상 불연속적이 아니다 따라서 이러한 불연속성의 제거는 에너지 집중율을 더 좋게 한다. 이렇게 변환된 연속적인 Y(n)을 주파수 차원에서 해석한것이 DFT이고 DCT의 토대가 되는 것이다.
DCT가 본격적으로 영상처리에 이용하기 위해 N=8인 블록단위로 처리하고 있으며 2차원 계산이 사용된다. 8*8의 영상 블럭은 2개의 공간 차원(즉 X,Y축)의 함수인 64화소 이산 신호이다. FDCT는 이러한 이산신호를 입력으로 취하여 64직교 BASIS신호로 분리하여 출력한다 각 직교 BASIS성분(즉 DCT계수)은 입력신호의 주파수 성분을 64개의 2차원 공간 주파수 성분으로 나타낼 때 각각의 공간 주파수 성분을 나타낸다. 따라서 DCT계수들은 64화소 입력영상에 따라 결정되는 독특한 주파수 성분의 표현이라고 볼수 있다.
X=0 및 Y=0일때의 DCT 계수는 양차원으로 영 주파수를 나타내기 때문에 DC계수라 불리고 나머지 63개의 계수들은 AC계수라 불린다. 8*8블록내에 있는 화소값들이 보통 급격히 변화하지 않으므로 대부분의 에너지가 저주파수 성분들에 모이게 된다. 따라서 대부분의 공간주파수 성분들은 영이거나 또는 크기가 거의 영에 가까울 정도로 작아서 인코딩할 필요가 없게 된다.
여기서 DCT는 자체로 압축효과를 갖는게 아니고 단지 원영상 블록의 표현방법을 공간영역에서 주파수 영역으로 바뀌었고 결과적으로 신호에너지를 제한된 몇개의 DCT계수에 집중시키게 되었다는 것이다. 이말은 나중에 설명할 디코더의 마지막 단계인 엔트로피 코딩에서 중요한 의미를 갖는다.
DCT처리를 한 이후의 데이타는 양자화 과정을 거친다. 64개의 양자화 테이블에 의해 유니폼 양자화를 거치게 되는데 구체적으로 테이블의 값들은 정수로서 범위는 1에서 255까지인데 각각의 DCT계수들에 대한 양자화스탭 사이즈를 나타낸다. 아울러 DCT기반의 압축알고리듬의 주요 손실 원인은 양자화 과정에 있다는 것을 알수 있다. 왜냐하면 엔트로피 코딩을 위한 라운딩(ROUNDING)에러가 존재하기 때문이다.
양자화 스텝사이즈는 DCT계수를 나누는 역할을 해주면서 Q(u,v)값이 크면 클수록 양자화된 DCT계수들의 크기가 작아지므로 압축률은 증가함을 알 수 있는데 문제는 시각적으로 영상 품질저하를 느끼지 않는 범위에서 압축률을 크게 해야 되는 것이다.
DCT기반의 부호화 과정의 최종 단계는 엔트로피 부호화인데 이 과정을 통하여 추가로 압축 효과를 얻는다 여기에서 무손실 압축효과는 양자화된 DCT계수들의 통계적인 특성을 부호화에 이용하므로서 얻게 된다. 즉 통계적으로 자주 나타나는 계수들에 대해서는 짧은 코드워드를 부여하고 , 흔치않은 경우에는 긴 코드워드를 매핑해줌으로서 계수들을 표현하는데 필요한 평균데이타량을 감축하는 것이다. 코딩 방법에는 허프만 코딩과 산술코딩(ARITHMETIC CODING)이 있는데 산술코딩은 구현시에 복잡도가 증가하는 이유로 앞에서 언급한 HUFFMAN CODING이 쓰인다.
지금까지의 모든 설명은 DCT기반의 부호화 과정이었고 복호화 과정은 엔트로피코딩-양자화-IDCT의 반대의 순서로 이루어진다.
Ⅶ. 셀기반의 셀추출 알고리즘
1. 개요
셀 경계의 식별은 입력 데이터의 흐름에서 셀 경계를 찾아내는 기능으로, 이를 위한 기본적인 방법은 ATM 셀 헤더의 HEC 필드를 이용하는 것이다. HEC를 이용한 셀 경계 식별 상태 천이도이다.
동기를 찾기 위해서 먼저 추적 상태에서 비트 단위로 5바이트에 대하여 CRC(Cyclic Redundancy Check)를 한다. 즉 연속적인 5바이트를 39차의 이진 다항식으로 표시할 때, 만일 이것이 생성 다항식 x8 + x2 + 1 로 나누어 나머지가 0(올바른 HEC)이면 일단 셀 헤더로 간주하고 준동기 상태가 된다. 준동기 상태에서는 셀 크기인 53바이트 간격으로 셀 헤더에 대한 CRC를 하는데, 연속적으로 δ번 올바른 HEC를 찾으면 동기 상태가 되고 그렇지 않으면 다시 추적 상태가 된다. 동기 상태에서는 에러가 있는 헤더가 연속적으로 α번 반복되면 동기 상태를 벗어난다. 연속 헤더 오류 횟수 α와 연속 헤더 확인 횟수 δ는 셀 경계 식별 성능을 좌우하는 가장 중요한 변수로, ITU-T에서는 α와 δ값을 각각 7과 6으로 권장한다.
2. 셀 추출 알고리즘의 해석적 성능 모델
1) 동기 유지 시간
동기 유지 시간은 동기를 획득한 후 동기를 잃을 때까지의 평균 시간이다. 비트 에러율에 따른 알고리즘의 성능 평가를 위해서 랜덤 비트 에러 환경을 가정하고 이 랜덤 비트 에러율을 p라 할

키워드

알고리즘,   알고리즘적용,   객체관리모듈알고리즘,   문자인식알고리즘,   압축알고리즘