The arithmetic decoding process is the reverse of the encoding procedure. Decode the message 0.23355 given the coding model.
Symbol
Probability
a
0.2
e
0.3
i
0.1
o
0.2
u
0.1
!
0.1
Answer:
To decode the message 0.23355 using arithmetic decoding with the given coding model, we reverse the arithmetic encoding process. The coding model provides symbols with their probabilities, which we use to define intervals in [0, 1). The goal is to determine the sequence of symbols that corresponds to the given number by iteratively narrowing down the interval.
Step 1: Define the Cumulative Probability Intervals
The coding model is:
Symbol
Probability
Cumulative Probability
Interval
a
0.2
0.0
[0.0, 0.2)
e
0.3
0.2
[0.2, 0.5)
i
0.1
0.5
[0.5, 0.6)
o
0.2
0.6
[0.6, 0.8)
u
0.1
0.8
[0.8, 0.9)
!
0.1
0.9
[0.9, 1.0)
The cumulative probability for a symbol ss is the sum of probabilities of all symbols before it. The interval for symbol ss with probability p_(s)p_s and cumulative probability F_(s)F_s is [F_(s),F_(s)+p_(s))[F_s, F_s + p_s).
Step 2: Initialize the Decoding Process
The encoded message is D=0.23355D = 0.23355. We start with the initial interval [low,high)=[0,1)[low, high) = [0, 1), where low=0low = 0, high=1high = 1, and the range is range=high-low=1range = high – low = 1. We iteratively select the symbol whose interval contains DD, update the interval, and continue until we encounter the termination symbol !! or reach sufficient precision.
Step 3: Decode Iteratively
We compute which symbol’s interval contains D=0.23355D = 0.23355 and update the interval accordingly.
Iteration 1: Initial Interval [0, 1)
Range: range=1-0=1range = 1 – 0 = 1.
Compute the scaled position of D=0.23355D = 0.23355 within [0, 1):“Scaled value”=(D-low)/(range)=(0.23355-0)/(1)=0.23355.\text{Scaled value} = \frac{D – low}{range} = \frac{0.23355 – 0}{1} = 0.23355.
Find the symbol whose interval contains 0.23355:
aa: [0.0, 0.2) → 0.23355 is not in this interval.
ee: [0.2, 0.5) → 0.2 <= 0.23355 < 0.50.2 \leq 0.23355 < 0.5, so the symbol is ee.
Update the interval using ee’s interval [0.2, 0.5):low_(“new”)=low+range*F_(e)=0+1*0.2=0.2,low_{\text{new}} = low + range \cdot F_e = 0 + 1 \cdot 0.2 = 0.2,high_(“new”)=low+range*(F_(e)+p_(e))=0+1*(0.2+0.3)=0.5.high_{\text{new}} = low + range \cdot (F_e + p_e) = 0 + 1 \cdot (0.2 + 0.3) = 0.5.
New interval: [0.2, 0.5).
New range: range=0.5-0.2=0.3range = 0.5 – 0.2 = 0.3.
Find the symbol whose interval contains 0.9166667:
aa: [0.0, 0.2) → not in this interval.
ee: [0.2, 0.5) → not in this interval.
ii: [0.5, 0.6) → not in this interval.
oo: [0.6, 0.8) → not in this interval.
uu: [0.8, 0.9) → not in this interval.
!!: [0.9, 1.0) → 0.9 <= 0.9166667 < 1.00.9 \leq 0.9166667 < 1.0, so the symbol is !!.
Since !! is the termination symbol, we stop decoding.
Step 4: Output the Decoded Message
The sequence of symbols decoded is e,a,i,i,!e, a, i, i, !. In arithmetic coding, the termination symbol !! typically indicates the end of the message. Thus, the decoded message, excluding the termination symbol, is:
“eaii”\text{eaii}
Verification
To ensure correctness, we can encode the sequence e,a,i,i,!e, a, i, i, ! using the arithmetic encoding process to see if it produces a value consistent with 0.23355:
Start with [0, 1).
Symbol e: Interval [0.2, 0.5), low=0.2low = 0.2, high=0.5high = 0.5, range = 0.3.
Symbol a: Interval [0.0, 0.2), low=0.2low = 0.2, high=0.2+0.3*0.2=0.26high = 0.2 + 0.3 \cdot 0.2 = 0.26, range = 0.06.
The final interval [0.23354, 0.2336) contains 0.23355, confirming that the sequence e,a,i,i,!e, a, i, i, ! encodes to a value consistent with the given input.
Final Answer
The decoded message for the value 0.23355, given the provided coding model, is:
“eaii”\boxed{\text{eaii}}
Question:-1(b)
A binary image contains straight lines oriented horizontally, vertically, at 45°, and at -45°. Give a set of 3×3 masks that can be used to detect 1-pixel breaks in these lines. Assume that the intensities of the lines and background are 1 and 0, respectively.
Answer:
To detect 1-pixel breaks in straight lines oriented horizontally, vertically, at 45°, and at -45° in a binary image, we can use a set of 3×3 masks that are designed to respond to gaps in these specific directions. The idea is to create masks that match the expected neighborhood of a pixel on a line in each direction, and then look for deviations that indicate a break.
Here is a set of 3×3 masks for detecting 1-pixel breaks in each of the four directions:
1. Horizontal Line Break Mask:
A break in a horizontal line would mean that the middle pixel in the row is 0, while the surrounding pixels in the horizontal direction are 1. The mask should detect this pattern.
Mask:
[ 1 1 1 ]
[ 1 0 1 ]
[ 1 1 1 ]
This mask will respond strongly if the center pixel is 0 (break) and the pixels to the left and right (in the horizontal direction) are 1 (line). However, this is a general mask. To specifically detect breaks in horizontal lines, we can use the following approach:
For a horizontal line, the expected neighborhood is:
[ 0 0 0 ]
[ 1 1 1 ]
[ 0 0 0 ]
A break in the horizontal line would be:
[ 0 0 0 ]
[ 1 0 1 ]
[ 0 0 0 ]
So the mask to detect this break is:
[ 0 0 0 ]
[ 1 -2 1 ]
[ 0 0 0 ]
This mask will give a high response (specifically, a negative response) when the center pixel is 0 and the left and right pixels are 1.
2. Vertical Line Break Mask:
Similarly, for a vertical line, the expected neighborhood is:
[ 0 1 0 ]
[ 0 1 0 ]
[ 0 1 0 ]
A break in the vertical line would be:
[ 0 1 0 ]
[ 0 0 0 ]
[ 0 1 0 ]
The mask to detect this break is:
[ 0 1 0 ]
[ 0 -2 0 ]
[ 0 1 0 ]
3. 45° Diagonal Line Break Mask:
For a 45° diagonal line (top-right to bottom-left), the expected neighborhood is:
[ 0 0 1 ]
[ 0 1 0 ]
[ 1 0 0 ]
A break in the 45° line would be:
[ 0 0 1 ]
[ 0 0 0 ]
[ 1 0 0 ]
The mask to detect this break is:
[ 0 0 1 ]
[ 0 -2 0 ]
[ 1 0 0 ]
4. -45° Diagonal Line Break Mask:
For a -45° diagonal line (top-left to bottom-right), the expected neighborhood is: