Algorithms, Computer Engineering

Assignment Help:
Design an algorithm (using pseudocode) that takes in as an input, two 2-D int arrays that are assumed to be 2 black-and-white images: initialImage x, whose dimensions are IxJ, and finalImage y, whose dimensions are IxK. The algorithm will compare x to the y, row-by-row, as defined below. Your algorithm will employ a dynamic programming scheme to compare X to Y identifying the minimal difference between each row.

Because you are working with black-and-white images only, you should assume that each image is a 2-D int array consisting of 2 possible values: 0 or 1, where 0 represents black and 1 represents white. Thus, this 2-D grid of 0 and 1 values comprise a 2-D black-and-white image. Each row of this image is then simply a 1-D int array filled with either 0s or 1s. Therefore, you must define how you will measure the difference between the strings of 0s and 1s in each row.

Remember that you will do the comparison one row in the images at a time.

First, compare X1,* to Y1,*. (Here X1,* is the first row in image X and Y1,* is the first row in image Y ). Next, compare X2 to Y2... Each one of these comparisons will require the construction of a D (distance) matrix.

In the following example, the first row of X is X1,*, and the first row of Y is Y1,* = 00110.



Use the following recurrence relation to develop your pseudocode:



After the D matrix is completed, the minimum number in the bottom row is the minimal mismatch for this row. You will assign this value to the variable minVali. This number tells how different row X1,* is from row Y1,* . You will then repeat this comparison for all rows i and aggregate the difference when complete into variable totalDifference = Si minVali.

As a result, the algorithm will compare the total difference to a threshold value called thresh. If total value is above the threshold, the images are declared different, otherwise they are declared to be similar images. You can assume that the thresh variable is supplied as an input to your algorithm.

Part 1

Create a portfolio that includes all previous IPs.

Part 2a:

Design pseudocode for the image comparison algorithm discussed above, given input Images X, Y, and thresh. The output is a declaration: The images are similar, or the images are different.

Part 2b:

Discuss the optimality of the dynamic programming solution. Discuss the time complexity of this algorithm in terms of the size of the inputs X and Y.

Related Discussions:- Algorithms

The job allocation register, Signify this problem by means of: i.    An Ent...

Signify this problem by means of: i.    An Entity Relationship model; ii.    Relational tables. Pete's Programmers is a firm which supplies part time staff on contract to organisat

How is network examined by intranets, How is network examined by intranets,...

How is network examined by intranets, extranets and Internet? When more and more businesses seek to build their mission critical business solutions onto IP networks, networking

Important part of process - canonical genetic algorithm, Important part of ...

Important part of Process - canonical genetic algorithm: In such a scenario evolution or random mutations are often highly deleterious or can say harmful to the organism it me

Explain in detail about real time processing, Explain in detail about Real ...

Explain in detail about Real time (transaction) processing When booking seats on a flight, for illustration, real time (transaction) processing would be used. Response to a que

Which interface controls what is shown on the p.c., Which interface control...

Which interface controls what is shown on the p.c.? Presentation Interface  controls what is shown on the p.c

C, "Super ASCII", if it contains the character frequency equal to their asc...

"Super ASCII", if it contains the character frequency equal to their ascii values. String will contain only lower case alphabets (''a''-''z'') and the ascii values will starts from

How do you control instructions like branch, How do you control instruction...

How do you control instructions like branch, cause problems in a pipelined processor? Pipelined processor gives the best throughput for sequenced line instruction. In branch in

Limits of traditional payment instruments and overcome, What are the restri...

What are the restrictions of traditional payment instruments? How are such restrictions overcome by electronic payment systems? The restrictions of traditional payment system a

Opcode field of an instruction, For this machine there can be two more poss...

For this machine there can be two more possible addressing modes in addition to direct andimmediate.   Opcode field of an instruction is a group of bits which define various pro

Episodes - artificial intelligence , Episodes - artificial intelligence: ...

Episodes - artificial intelligence: If an agent's current choice of action not based on its past reactions, then the environment is known as episodic. In the non-episodic envi

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd