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

Give the truth table of S-R and D-flipflops, Give the truth table of S-R an...

Give the truth table of S-R and D-flipflops. Ans: The Truth Table for S-R Flip-Flop is illustrated in Fig.(a) and truth table of D Flip-Flop is illustrated in Fig.(b)

Define side tone is essential in telephone communication, A certain amount ...

A certain amount of side tone is essential in telephone communication. Ans: It is true that a specific amount of side tone is necessary in telephone communication.

What are the advantages of public key cryptography, What are the advantages...

What are the advantages of Public Key Cryptography? Advantages of Public Key Cryptography are illustrated in below: a) Increased convenience and security and b) Electro

What is the network service access policy, What is the Network Service Acce...

What is the Network Service Access Policy A high-level, issue-specific policy which defines those services that are allowed or denied from the restricted network. It also co

Which things should microprocessor validate, Q. Which things should micropr...

Q. Which things should microprocessor validate? A microprocessor should validate: Powerful addressing modes More addressing capability More throughput Po

Define the concept of inheritance, Define the concept of Inheritance I...

Define the concept of Inheritance Inheritance is property of reusing the code within the object oriented development. While modelling, we look at the all the classes, and try

What is npblox framework, Designed, developed, tested and documented the de...

Designed, developed, tested and documented the demo created for NPBlox framework. NPBlox framework is a framework which enabled developers to create CLI/WEB/SNMP interfaces for

What are the pros and cons of on-line documentation, Question 1: You wa...

Question 1: You want to perform the task of setting an alarm on your mobile phone. You can assume that the alarm option is accessible from the main menu of your phone. (a) P

Internet programming, Futoshiki is a game played on an N by N (usually 5 by...

Futoshiki is a game played on an N by N (usually 5 by 5) grid and uses the symbols 1 .. N. The objective of the game is to place each symbol on the grid so that it only occurs once

Modality and cardinality, Ask question #Midifference between cardinality an...

Ask question #Midifference between cardinality and modality nimum 100 words accepted#

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