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

What is simd, What is SIMD? Single Instruction stream, Multiple Data st...

What is SIMD? Single Instruction stream, Multiple Data stream (SIMD) shows an organization that contains many processing units under the supervision of a common control unit. A

Explain about joint application development, Q. Explain about Joint Applica...

Q. Explain about Joint Application Development? It is defined as a structured approach in which users, managers, and analysts work together for many days in a series of intensi

Signals and systems, Im doing computer engineering in Thailand.. Second yea...

Im doing computer engineering in Thailand.. Second year, and got project regarding sysnal and systems.. I and my team mates have no idea on what should we do.. Could u kindly sugge

CRTscreen as a two-dimensional matrix, Explain the statement- CRT screen as...

Explain the statement- CRT screen as a two-dimensional matrix One can imagine the CRT screen as a two-dimensional matrix which has m rows and n  columns and this is usually ref

Explain about the public key cryptography, Explain about the Public Key Cry...

Explain about the Public Key Cryptography. Public Key Cryptography: It is a cryptographic system which uses two keys as a public key identified to everyone and a private

State some criterias and their effects on a database, It is possible to ent...

It is possible to enter one or more criteria in the rows which can influence your database significantly. >="Callahan" this returns all the several records from Callahan to the

Instruction length - assembly language, Instruction Length: Variabl...

Instruction Length: Variable-length instructions (Intel 80x86, VAX) need multi-step fetch and decode, but permit for a much more flexible and compressed instruction set.

Classification according to pipeline configuration, Classification accordin...

Classification according to pipeline configuration: According to the configuration of a pipeline, the following parts are recognized under this classification: Unifunct

What is Video Card Interfaces, Q. What is Video Card Interfaces? A video i...

Q. What is Video Card Interfaces? A video interface is the link of video system to rest of the PC. To improve video performance there is required to be an intimate connection betw

Different message types available in the abap/4, What are the different mes...

What are the different message types available in the ABAP/4 ? There are 5 types of message types available. E: ERROR W-WARNING I -INFORMATION A-ABNORMAL TERMINA

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