a) Transform the quadrilateral ABCD with vertices A(1,0),B(4,−1),C(5,3) and D(−1,5) under a translation by the point (4, 5) followed by a counter-clockwise rotation by an angle of 45◦

.b) If you perform an x-direction shear transformation, and then a y-direction shear transformation, will the result be the same as the one which is obtained when it is simultaneous shear in both the directions? Justify your answer.

 c) Let W be a window with corners (0,0),(8,0),(8,4) and (0,4). Clip a triangle with vertices (1,1),(10,2) and (5,9) against the window W by tracing Liang Barskey line clipping algorithm

a) Consider a polygon with vertices at (5, 20), (12, 5), (15, 15), (25, 5), (30, 25), and (15, 30). Prepare a sorted edge list, and then make the active edge list for the

scanlines y = 5,10,15,20,25,30.

b) Develop and implement the flood fill algorithm.

 c) Prove or disprove: "Multiplication of transformation matrices for two successive rotations is commutative."

a) Explain what do you understand by the terms persistence, refresh rate, resolution, aspect ratio, horizontal and vertical retrace.

 b) Compute the pixel positions along the line path of the lien joining the points A and B(10,8).

 c) Using the midpoint method and symmetry in account, develop an efficient method

for scan converting the curve  n the interval [0, 10].

A binary image contains straight lines oriented horizontally, vertically, at 45⁰ , and at – 45o . Give a set of 3 × 3masks 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.

The arithmetic decoding process is the reverse of the encoding procedure. Decode the message 0.23355 given the coding model

a) Consider an 8-pixel line of intensity data, {108,139,135,244,172,173 56, 99, }. If it is uniformly quantized with 4-bit accuracy, compute the rms error and rms signal-tonoise ratios for the quantized data. 

 b) Prove that, for a zero-memory source with q symbols, the maximum value of the entropy is log q, which is achieved if and only if all source symbols are equiprobable.
[Hint: Consider the quantity log q-H(z) and note the inequality In x ≤x − ].1 

The white bars in the test pattern shown are 7 pixels wide and 210 pixels high. The separation between bars is 17 pixels. What would this image look like after application of

 i) A 3 × 3 arithmetic mean filter? 

ii) A 7 × 7 arithmetic mean filter?

iii) A 9 × 9 arithmetic mean filter?

Consider a 3 × 3 spatial mask that averages the four closet neighbours of a point  but excludes the point itself from the average.

i) Find the equivalent filter, H (u, v), in the frequency domain.

ii) Show that your result is a lowpass filter.

Prove that both 2-D continuous and discrete Fourier transforms are linear operations.

Write an expression for 2-D continuous convolution.

a) Two images, f (x,y) and g (x,y), have histograms  and  Give the condition under which you can determine the histograms of

i) 

ii) 

iii) 

iv) 

Consider the two image subsets, S1 and S2, shown in the following figure. For V = { },1 determine whether these two subsets are (i) 4-adjacent, (ii) 8-adjacent, or (iii) m-adjacent.                                                                                                      

An automobile manufacturer is automating the placement of certain components on the bumpers of a limited-edition line of sports cars. The components are colour coordinated, so the robots need to know the colour of each car in order to select the appropriate bumper component. Models come in only four colours: blue, green, red, and white. Find a solution based on imaging and determine the colour of each car, keeping in mind that cost is the most important consideration.

(a) Find the values of n for which Qn is Eulerian.

(b) Using Fleury’s algorithm, find an Eulerian circuit in the following graph.

(c) The complement of a planar graph is planar. True or false? Justify

(a) What is the maximum possible flow that can pass through the following network? Define such a flow.

(b) State and prove the K¨onig Eg´arvary Theorem. 
(c) Let G be a graph having no isolated vertex and no induced subgraph with exactly two edges. Show that G is a complete graph.

(a) Verify Euler’s formula for the following plane graph.

(b) Check whether the line graph of C5 × K2 is planar or not. 
(c) What is the minimum possible thickness of a 4-connected triangle-free graph on 8 vertices? Also draw such a graph. 
(d) Define the parameters α(G) and β(G) for a graph G. Also, show that
α(G) + β(G) = n(G).

(a) Find the number of spanning trees of the following graph.

(b) Solve the Chinese Postman Problem for the graph given in Q. 3(b). 
(c) Give an example of a 4-critical graph different from a complete graph. Justify the choice of your example.                                                                 (d) State and prove the Handshaking Lemma for planar graphs.

(a) Let G be a connected n-vertex graph. Prove that G has exactly one cycle iff G has exactly n edges

(b) Find a minimum-weigh spanning tree in the following graph

(c) Prove that every maximal matching of a graph G has at least α 0 (G)/2 edges. 

(d) Find the chromatic and edge-chromatic numbers of the following graph.

The maximum subsequence sum problem is defined as follows: If are in Z, find the maximum value  for all   See Answer →

(a) The complement of the Petersen graph is 2-connected. Prove or disprove

(b) Consider a graph G. Let x, y ∈ V (G) be such that x ↔ y. Show that for all z ∈ V (G), |d(x, z) − d(y, z)| ≤ 1

(c) Check whether the following graphs G and H are isomorphic or not