### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# Digital Image Processing EE 4663

UTSA

GPA 3.89

### View Full Document

## 20

## 0

## Popular in Course

## Popular in Electrical Engineering

This 15 page Class Notes was uploaded by Valentine White on Thursday October 29, 2015. The Class Notes belongs to EE 4663 at University of Texas at San Antonio taught by Staff in Fall. Since its upload, it has received 20 views. For similar materials see /class/231451/ee-4663-university-of-texas-at-san-antonio in Electrical Engineering at University of Texas at San Antonio.

## Reviews for Digital Image Processing

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 10/29/15

ART code I A New Method Of Optimal Coding Artyom M Grigoryan Department of Electrical and Computer Engineering The University of Texas at San Antonio amgrigoryan utsaedu Notes for class 4663 from the presentation in the International IEEE conference ITCC 2002 A new technique for optimally encoding a given source statistical properties of which are de scribed by the first order model is introduced The calculation of a minimum length of code words is based on the consecutive redistribu tion of the self information of symbols in ac cordance with their probabilities at each stage of the encoding The proposed method performs equally well for an arbitrary order of symbol probabilities While codewords are generated by a separate combinatorial procedure the overall computa tional cost of the proposed method is lower than that for the Huffman code For a given alphabet Am 2 a1a2am of letters a1 139 12m gt 1 which have prob abilities pz gt O and for which 191 I pm 1 the entropy rate of Am is 8 28 ZPiIOQQ a 8 P 39092 i1 1 z where 81 denotes the self information of a1 1 l1 2 log bits must be aSSIgned to a1 1 Since only integer numbers of bits are taken a difference di may occur between the actual number l1 and rounded integer value ii 1 l Og2 lz d l 17 0Sd lt1 p L Letters of the alphabet Am are arranged in de scending order of their probabilities Starting with a letter a1 a length 1 l1 log P1 of the codeword dog for al is calculated The difference D1 of the self information of the codeword and letter a1 D1 51 81 111191 81 is distributed among the remaining letters a2 613 am in proportion to their probabilities If D1 O or ll 2 l1 then a2 is processed If D1 72 O the self information of the rest let ters are calculated as D1 21 k1 2p pk17 k1im 1 n ngt1 The self information 82 of a2 becomes D1 39192 2 pm ngt1 A new length 2 of codeword c2 will be calcu lated as 82282 182 p2 and l 2 bits will be assigned for the codeword of letter 619 The remainder of the self information of the letter a2 D2 52 82 p2l2 82 is distributed among the remaining m 2 let ters a3a4 am in proportion to their proba bilities At following steps the letters a3a4 am are processed similarly The algorithm results in the set of the numbers of bits l1 l2 lm which are supposed to be used for encoding the corresponding letters a1 a2 am If the Kraft McMillan condition holds 1 1 1 m 2lm gt 1 there exists an uniquely decodable procedure for encoding the alphabet Am for which 1 bits will be used to obtain codewords ca i 1 m Example The alphabet A5 a1a2a5 whose elements have the probabilities p1 04 p2 2193 Z and p4 2195 The entropy rate of A5 is a 2122bitsletter Step 1 Letter is al p1 04 1 Ingl 13219 81 052877 and l1 2 2 bits are assigned to encode al The self information of the letter a1 increases by the value D1 p1l1 51 04 2 052877 2 027123 This amount of the self information is sub tracted from the self information of the re maining letters 828384 and 85 in accordance with their probabilities ie respectively in pro portions D13 D13 D16 and D16 The renewed values of the self information of letters are defined as follows 8E2 51 p1l1 04 2 08 2 D1 a2 82 O 6 02 046439 009041 2 D1 a3 a3 O 6 02 046439 009041 2 D1 2 D1 85 85 O 6 01 033219 004521 The initial and processed data at this step are shown in the following table Tablel Step 1 a D a i 1 52877 27123 8 13219 2 46439 13 37398 46439 13 37398 33219 16 28698 IIPOOMl l HHMM 33219 16 28698 Step 2 Letter is 09 p2 02 and the self information of a2 becomes 8E2 037398 1 2 2 89192 186985 and 12 2 bits are assigned for the letter 09 The difference of the self information D2 p2l 2 a 2 022 037398 002602 is subtracted from the self inf of letters a a 02 037398 001302 sf 2 12 01 028698 000651 823 a 01 028698 000651 and the new data table takes the form Table 2 Step 2 8 13 eE3 l Hg 7 7 52877 27123 8 13219 2 37398 02602 4 18698 2 37398 12 36096 28698 14 28047 U39IPCDNl h l l MMP 28698 14 28047 Tables Steps 34 and 5 A pi 870 Di 874 1 1 1 4 52877 27123 8 13219 2 2 2 37398 02602 4 18698 2 3 2 36096 03904 4 18048 2 4 1 28047 12 26096 5 1 28047 12 26096 A p 870 Di 875 1 1 1 4 52877 27123 8 13219 2 2 2 37398 02602 4 18698 2 3 2 36096 03904 4 18048 2 4 1 26096 03904 3 26096 3 5 1 26096 1 22192 A pi 810 Di 5 1 1 1 4 52877 27123 08 13219 2 2 2 37398 02602 04 18698 2 3 2 36096 03904 04 18047 2 4 1 26096 03904 03 26096 3 5 1 22192 07808 03 22192 3 The last remainder D5 of the self information of a5 is equal to the redundancy of the code 5 R Z pkug a 2 D5 007808 bitsletter k1 The lengths of the codewords are 2 2 2 3 3 Therefore 12 bits are required for encoding the alphabet A5 by using the proposed method Indeed the Kraft McMillan inequality is ful filled and the following code can be consid ered Cal 00 CCL2 01 C03 10 Ca4 110 ca5 111 Other codes are 110001 100101 10 1100010011 and 011011000001 The variance of the length for this codes is 023664 and the average length for codeword is 220 bitsletter That is the encoding pro cedure is optimal 10 The letter probabilities are in increasing order Table 6 A p 80 D 5 ii 11 5 1 33219 06781 4 332193 4 4 1 32466 07534 4 324659 4 3 2 43048 16952 6 215241 3 2 2 37398 02602 4 186988 2 1 4 32192 07808 4 080480 1 The sequence of lengths for codewords is 44 321 which requires 14 bits for encoding the alphabet A5 The variance of the codeword length is 058652 which is greater than the variance obtained in the previous example but the average code word length is the same 220 bitsletter 11 The order of letters a1 a2 a5 is not essential for the proposed procedure For instance by processing letters in the sequences 61102 a4a3 a5 and a1a4a5a2a3 respectively the follow ing data tables are obtained Table 7 A p 810 D a 1 1 1 4 52877 27123 8 132193 2 2 2 37398 02602 4 186988 2 4 1 28048 01952 3 280482 3 3 2 34795 05205 4 173976 2 5 1 22192 07808 3 221928 3 Table 8 A p 870 D a 1 lg 1 4 52877 27123 8 132193 2 4 1 28699 01301 3 286988 3 5 1 28439 01561 3 284386 3 2 2 36096 03904 4 180482 2 3 2 32192 07808 4 160964 2 The lengths for codewords are 22233 12 Let us consider another example when letters are taken in the order a2a1a4a3a5 Table 9 A 191 81 Di 83 2 2 46439 46439 13561 6 1 4 52877 46096 33904 8 4 1 33219 23048 06952 3 3 2 46439 21462 18538 4 5 1 33219 02192 07808 3 l 1 232193 3 115241 2 230482 3 107309 2 021928 1 The sequence of lengths 2323 1 for code words ca1 ca5 for which no decodable code exists The Kraft McMillan inequality does not hold 5 1 1 1 1 1 1 5 gt1 igjl 232223222 4 13 Since 192 lt 191 82 lt 81 and 2 232193 we have to assign only two bits for the code word dog and add the remainder of its self information D2 52 2 02 006439 to the letters a1 a4 a3 a5 in accordance with their probabilities In other words we consider that 2 2 l2 m2 where 0 g m2 lt 1 Table 10 A 191 81 Di 51 2 2 46439 46439 06439 4 1 4 52877 56097 23904 8 4 1 33219 28048 01952 3 3 2 46439 34795 05205 4 5 1 33219 22192 07808 3 l 1 232193 2 115241 2 284383 3 107309 2 221920 3 The codeable sequence of lengths is 2 2 2 3 3

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

#### "Selling my MCAT study guides and notes has been a great source of side revenue while I'm in school. Some months I'm making over $500! Plus, it makes me happy knowing that I'm helping future med students with their MCAT."

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.