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

State the implementation of a security policy, State the implementation of ...

State the implementation of a security policy The implementation of a security policy should invariably cover all parameters of security such as physical access to the server,

Define a protocol when an error recovery develop for a link, Suppose you ha...

Suppose you have to develop an error recovery protocol for a link that is unreliable and delay sensitive, which of the following protocol would you choose? (i) Stop & wait.

Programming, how can compare alphabates of two words in c programming ?????...

how can compare alphabates of two words in c programming ?????

Explain the typical functions of operating systems, List the typical functi...

List the typical functions of operating systems. Classical functions of operating system are given as: (1) Process management: A process is a program throughout execution.

Illustrate function of 4-input multiplexer using basic gates, Illustrate fu...

Illustrate functional diagram of digital multiplexer . Write the scheme of a 4- input multiplexer using basic gates (AND/OR/NOT) and explain its operation. Ans: Multiple

Bell lapadula model, A computer system provides protection using the Bell-L...

A computer system provides protection using the Bell-LaPadula policy. How would a virus spread if A) the virus were placed on the system at system low (the compartment that all o

Differentiate between static and dynamic memory, Differentiate between stat...

Differentiate between static and dynamic memory? The static RAM is simpler to use and has shorter read and write cycles. One of the main applications of static RAM is in execut

What is a privileged instruction, What is a privileged instruction? To ...

What is a privileged instruction? To protect the operating system of a computer from being corrupted by user programs, particular instructions can be executed only whereas the

C++, Byteland county is very famous for luminous jewels. Luminous jewels ar...

Byteland county is very famous for luminous jewels. Luminous jewels are used in making beautiful necklaces. A necklace consists of various luminous jewels of particular colour. Nec

What is sgml, SGML is very large, influential, and difficult. It has been i...

SGML is very large, influential, and difficult. It has been in important industrial and commercial use for nearly two decades, and there is a important body of expertise and softwa

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