(a) Feedforward-designed Convolutional Neural Networks (FF-CNNs) (20%) When two CNN layers are cascaded, a non-linear activation function is used in between. As an alternative to the non-linear activation, Kuo et al. proposed the Saak (subspace approximation via augmented kernels) transform [1] and the Saab (subspace approximation via adjusted bias) transform [2].Specifically, Kuo et al. [2] proposed the first example of a feedforward-designed CNN (FF-CNN), where all model parameters are determined in a feedforward manner without backpropagation. It has two main cascaded modules: 1) Convolutional layers via multi-stage Saab transforms 2) Fully-connected (FC) layers via multi-stage linear least squared regression (LLSR)Although the term “successive subspace learning” (SSL) was not used in [2] explicitly, it does provide the first SSL design example.Read paper [2] carefully and answer the following questions: (1) Summarize the Saab transform with a flow diagram. Explain it in your own words. The codes for the Saab transform can be found at https://github.com/USC-MCL/Channelwise-Saab-Transform. Please read the codes with the paper to understand the Saab transform better.(2) Explain similarities and differences between FF-CNN and backpropagation-designed CNN (BPCNNs). Do not copy any sentence from a paper directly which is plagiarism. Your scores will depend on the degree of your understanding.(b) Understanding PixelHop and PixelHop++ (15%) Two interpretable models adopting the SSL principle for the image classification task were proposed by Chen et al. They are known as PixelHop [3] and PixelHop++ [4]. Read the two papers carefully and answer the questions below. You can use various tools in your explanation such as flow charts, figures, formula etc. You should demonstrate your understanding through your answer.(1) Explain the SSL methodology in your own words. Compare Deep Learning (DL) and SSL. (2) What are the functions of Modules 1, 2 and 3, respectively, in the SSL framework?(3) Explain the neighborhood construction and subspace approximation steps in the PixelHop unit and the PixelHop++ unit and make a comparison. Specifically, explain the differences between the basic Saab transform and the channel-wise (c/w) Saab transform.Please apply PixelHop and PixelHop++ to the MNIST and the Fashion-MNIST datasets. (a) Building PixelHop++ Model (35%) The block diagram of PixelHop++ isshown in Figure 1. It contains three PixelHop++ Units. The codes for the c/w Saab transform module is provided in the GitHub. You can import them in your program to build your model in Python based on the diagram. You should adopt the parameters and the classifier choice in Table 1.Figure 1 Block diagram of the PixelHop++ model [4] Table 1 Choice of hyper-parameters of PixelHop++ model for MNIST dataset Spatial Neighborhood size in all PixelHop++ units 5×5 Stride 1 Max-pooling (2×2) -to- (1×1) Energy threshold for intermediate nodes (TH1) 0.005 Energy threshold for discarded nodes (TH2) 0.001 Classifier XGBoost Number of estimators in classifier 100(1) Train Module 1 using the whole set or a subset of 10000 training images (depending on your memory). Remember to keep balance among different classes (i.e. randomly select 1000 images per class if you use 10,000 training images). Then, train Module 3 only on Hop3 feature. Report training time and train accuracy. What is your model size in terms of the total number of parameters? (2) Apply your model to 10,000 testing images and report the test accuracy. (3) With the same TH2, try different TH1 energy threshold values in Module 1 and report the testaccuracy and the model size for different choices. Plot the curve of TH1 vs. the test accuracy. Discuss your result.(b) Comparison between PixelHop and PixelHop++ (15%) The codes for the Saab transform are provided in the GitHub. Please use the Saab transform (instead of c/w Saab transform) to build the PixelHop model with the same parameter settings as PixelHop++ in Table 1. Note that TH2 is treated as the energy threshold used in the PixelHop paper.(1) Compare the performance of PixelHop and PixelHop++ in terms of the train accuracy and the test accuracy. Discuss your result. (2) Compare the model size of PixelHop and PixelHop++ in terms of the number of model parameters. Discuss your result.(c) Error analysis (15%) A dataset often contains easy and hard classes. Conduct the following error analysis based on your trained PixelHop++ model using 60,000 training images:(1) Compute the confusion matrix and show it as a heat map in your report. Which object class yields the lowest error rate? Which object class yields the highest one? (2) Find out the confusing class groups and discuss why they are easily confused with each other. You can use some exemplary images to support your statement.(3) Propose ideas to improve the accuracy of difficult classes for PixelHop++ and justify your ideas. There is no need to implement your ideas.References [1] C.-C. Jay Kuo and Yueru Chen, “On data-driven Saak transform,” Journal of VisualCommunication and Image Representation, vol. 50, pp. 237–246, 2018. [2] C.-C.Jay Kuo, Min Zhang, Siyang Li,Jiali Duan, and Yueru Chen, “Interpretable convolutional neural networks via feedforward design,” Journal of Visual Communication and Image Representation, vol. 60, pp. 346–359, 2019.[3] Yueru Chen and C.-C. Jay Kuo, “Pixelhop: A successive subspace learning (ssl) method for object recognition,” Journal of Visual Communication and Image Representation, p. 102749, 2020.[4] Yueru Chen, Mozhdeh Rouhsedaghat, Suya You, Raghuveer Rao, C.-C. Jay Kuo, “PixelHop++: A Small Successive-Subspace-Learning-Based (SSL-based) Model for Image Classification,” https://arxiv.org/abs/2002.03141, 2020[5] Yueru Chen, Yijing Yang, Wei Wang, C.-C. Jay Kuo, “Ensembles of Feedforward-designed Convolutional Neural Networks”, in International Conference on Image Processing, 2019
In assignment 1, you will complete three tasks. The goal of these tasks is to help you get familiar with Spark operations (e.g., transformations and actions) and MapReduce.2.1 Programming Requirements a. You must use Python to implement all tasks. You can only use standard python libraries (i.e., external libraries like numpy or pandas are not allowed). There will be 10% bonus for Scala implementation. You can get the bonus only when both Python and Scala implementations are correct. b. You are required to only use Spark RDD, i.e. no point if using Spark DataFrame or DataSet.2.2 Programming Environment Python 3.6, Scala 2.11, and Spark 2.3.0 We will use Vocareum to automatically run and grade your submission. We highly recommend that you first test your scripts on your machine and then submit to Vocareum if the testing is successful. You should have received an email from Vocareum to access the assignment 1. The email should contain some text like: “Welcome to Vocareum’s Coding Lab! You have been enrolled in the following course: Course: INF 553 – Spring 2020”. If you do not receive such an email, please contact your TA.2.3 Write your own code Do not share code with other students!! For this assignment to be an effective learning experience, you must write your own code! We emphasize this point because you will be able to find Python implementations of some of the required functions on the web. Please do not look for or at any such code! TAs will combine all the code we can find from the web (e.g., Github) as well as other students’ code from this and other (previous) sections for plagiarism detection. We will report all detected plagiarism to the university.In this assignment, you are provided with two datasets (i.e., reviews and businesses) extracted from the Yelp dataset for developing your assignment. 1 You can access and download the datasets either under the directory on Vocareum: resource/asnlib/publicdata/ or in the Google Drive: https://drive.google.com/drive/folders/1dnVCZazaR84UkvhHAwoHyFqxmFF01IHa?usp=sharing We generated these datasets in a random sampling way. These given datasets are only for your testing. During the grading period, we will use different sampled subsets of the Yelp datasets.4. Tasks You need to submit the following files on Vocareum: (all lowercase) A. Python scripts: task1.py, task2.py, task3.py B. [OPTIONAL] Scala scripts: task1.scala, task2.scala, task3.scala; Jar package: hw1.jar4.1 Task1: Data Exploration (3pts) 4.1.1 Task description You will explore the review dataset and write a program to answer the following questions: A. The total number of reviews (0.5pts) B. The number of reviews in a given year, y (0.5pts) C. The number of distinct users who have written the reviews (0.5pts) D. Top m users who have the largest number of reviews and its count (0.5pts) E. Top n frequent words in the review text. The words should be in lower cases. The following punctuations i.e., “(”, “[”, “,”, “.”, “!”, “?”, “:”, “;”, “]”, “)”, and the given stopwords are excluded (1pts)4.1.2 Execution commands Python: $ spark-submit task1.py Scala: $ spark-submit –class task1 hw1.jar Params: input_file – the input file (the review dataset) output_file – the output file contains your answers stopwords – the file contains the stopwords that should be removed for Question E y/m/n – see 4.1.1 4.1.3 Output format: You must write the results in the JSON format using exactly the same tags for each question (see an example in Figure 2). The answer for A/B/C is a number. The answer for D is a list of pairs [user, count]. The answer for E is a list of frequent words. All answers should be sorted by the count in the descending order. If two users/words have the same count, please sort them in the alphabetical order. 1 https://www.yelp.com/dataset Figure 2: An example output for task1 in JSON format 4.2 Task2: Exploration on Multiple Datasets (2pts)4.2.1 Task description In task2, you will explore the two datasets together (i.e., review and business) and write a program to compute the average stars for each business category and output top n categories with the highest average stars(1pts). The business categories should be extracted from the “categories” tag in the business file and split by comma (also need to remove leading and trailing spaces for the extracted categories). You need to implement a version without Spark and compare to a version with Spark for reducing the time duration of execution (1pts).4.2.2 Execution commands Python: $ spark-submit task2.py Scala: $ spark-submit –class task2 hw1.jar Params: review _file – the input file (the review dataset) business_file – the input file (the business dataset) output_file – the output file contains your answers if_spark – either “spark” or “no_spark” n – top n categories with highest average stars (see 4.2.1) 4.2.3 Output format: You must write the results in the JSON format using exactly the same tags (see an example in Figure 3). The answer is a list of pairs [category, stars], which are sorted by the stars in the descending order. If two categories have the same value, please sort the categories in the alphabetical order. Figure 3: An example output for task2 in JSON format4.3 Task3: Partition (3pts) 4.3.1 Task description In this task, you will learn how partitions work in the RDD. You need to compute the businesses that have more than n reviews in the review file (1pts). At the same time, you need to show the number of partitions for the RDD and the number of items per partition with either default or customized partition function (1pts). You should design a customized partition function to improve the computational efficiency, i.e., reducing the time duration of execution (1pts).4.3.2 Execution commands Python: $ spark-submit task3.py Scala: $ spark-submit –class task3 hw1.jar Params: input_file – the input file (the review dataset) output_file – the output file contains your answers partition_type – the partition function, either “default” or “customized” n_partitions – the number of partitions (only effective for the customized partition function) n – the threshold of the number of reviews (see 4.3.1) 4.3.3 Output format: You must write the results in the JSON format using exactly the same tags (see an example in Figure 4). The answer for the number of partitions is a number. The answer for the number of items per partition is a list of numbers. The answer for result is a list of pairs [business, count] (no need to sort). Figure 4: An example output for task3 in JSON format 5. About Vocareum 1. You can use the provided datasets under the directory resource: /asnlib/publicdata/ 2. You should upload the scripts under your workspace: work/ 3. Once you click on “Submit”, all the scripts are submitted and automatically run on Vocareum.4. We highly recommend that you first test your scripts on your machine and then submit to Vocareum if the testing is successful. 5. You can also test your Python/Scala implementations using the required execution commands in the Vocareum terminal before submitting. 6. Here are the testing commands for your reference: 7. You will receive a submission report after Vocareum finishes executing your scripts. The submission report should include the running time and score of each task for the Python implementation. We do not test the Scala implementation during the submission period.8. Vocareum will automatically run both Python and Scala implementations during the grading period. 9. Please start your assignment early! You can resubmit any script on Vocareum. We will grade on your last submission.6. Grading Criteria (% penalty = % penalty of possible points you get) 1. You can use your free 5-day extension separately or together. You must submit a late-day request via https://forms.gle/worKTbCRBWKQ6jqu6. This form is recording the number of late days you use for each assignment. By default, we will not count the late days if no request submitted.2. There will be 10% bonus for each task (i.e., 0.3pts, 0.2pts, and 0.3pts) if your Scala implementations are correct. Only when your Python results are correct, the bonus of using Scala will be calculated. There is no partial point for Scala. 3. There will be no point if your submission cannot be executed on Vocareum.4. There is no regrading. Once the grade is posted on the Blackboard, we will only regrade your assignments if there is a grading error. No exceptions. 5. There will be 20% penalty for the late submission within one week and no point after that.
This exercise introduces the ARM Cortex and FP coprocessor assembly languages, instruction sets and their addressing modes. The ARM calling convention will need to be respected, such that the assembly code can be used with C programming language. The lab and a prior tutorial will introduce you to the STM32CubeIDE, including the compiler and associated tools. In the second part of the exercise, the code developed here will be used in a larger program written in C and the Cortex Microprocessor Software Interface Standard (CMSIS-DSP) application programming interface (API) that incorporates a large set of routines optimized for different ARM Cortex processors.Hence, this lab consists of two components, each requiring a week to compete: Part 1: Assembly language exercise – Kalman filter in one dimension Part 2: Combining assembly/embedded C and optimizing performance; CMSIS-DSPIn assembly and C, parameters for a subroutine are passed via stack or internal registers. In ARM processors, the registers R0:R3 are used for passing integer or pointer variables. Up to four parameters are placed in these registers, and the result is placed in R0 and R1. If any parameter requires more than 32 bits, then multiple registers are used. If there are no free scratch registers, or the parameter requires more registers than remain, then the parameter is pushed onto the stack.Since we will be also dealing with the floating-point parameters on hardware that performs floating-point arithmetic, be aware of having the option of using either software or hardware floating-point linkage, depending on whether the parameters are passed via general purpose or floating-point registers. The objective here is to use the hardware linkage, hence the floating-point registers will be used for parameter and result passing.In addition to the class notes, please refer to the document “Procedure Call Standard for the ARM Architecture”, especially its sections describing The Base Procedure Call Standard. Other documents that will be of importance include the Cortex M4 programming manual, quick reference cards for ARM ISA and the (vector) floating point instructions, all available within the course online documentation. This particular order of passing parameters is applied by major compilers.Using the STM32CubeIDE Integrated Development Environment Tool To prepare for Lab 1, you will need to go through Tutorial 1, where you will learn how to create and define projects, including assembly code projects. The tutorial shows you how to let the tool insert the proper startup code for the given processor, write and compile the code, as well as provide the basics of the program debugging.You will develop the working assembly language code for single-variable Kalman filter that can be used in later exercises. The single-variable version avoids the use of matrix operations required for larger Kalman filters, and makes it amenable to an assembly code implementation, while it still allows experimenting with and appreciating the features of this filter.Kalman filter is a state-based adaptive estimator of a physical process. Its estimation error is provably minimal for linear systems with Gaussian noise. It is the type of an adaptive filter, which is generally preferred to the fixed linear filters. The state space adaptation is performed by a sequence of discrete steps, during which the parameters of the filter change depending on the observed physical value, as well as the current state.Kalman filter performs the adaptation by maintaining the internal state, consisting of the estimated value x, the adaptive tuning factor k and the estimation error, represented by its covariance p. To obtain these values, it requires the knowledge of the noise parameters of the input measurements and the state estimation, represented by their respective covariances q and r.The high-level description of the Kalman filter code is given in the working python program in Figure 1. While the code is fully functional, and it can be directly run within a larger (Python) program, it is used here as a compact high-level specification. Please note that only the update function is required in the assembly part of Lab 1. In the second part, when you include your assembly code with the C code, the initialization function will be needed. That part will be written in C. Note also that there will be differences in the code caused by different syntax and semantics of C, compared to Python. For instance, you will need to carefully specify the data types and include the function prototypes in the code to be able to correctly link the assembly and C code.Figure 1: Python Code Definition of the Kalman Filter Class used in Lab 1 One interpretation of Kalman filter is that of tracking (or estimating the trajectory of) device for the input signal stream. At each time instance i, it generates the tracking consisting of the value vector x[i], that aims to reconstruct the original signal measurement[i]. An important feature of the Kalman filter is that the estimated value differs from the input by a value that has the statistical properties of the white noise. You will be asked later to inspect those properties using your additional statistical processing.Write a subroutine kalman in ARM Cortex M4 assembly language that processes one measurement input to update the local state required for the process estimation. You should naturally use the built-in floating-point unit by using the existing floating-point assembler instructions Your subroutine should follow the ARM compiler parameter passing convention. Recall that up to four integer and 4 floating-point parameters can be passed by integer and floating-point registers, respectively. For instance, R0 and R1 to contain the values of the first two integers and S0 will contain the value of the floating-point parameter to be added. If the datatype is more complex (e.g, struct or a matrix), then a pointer to it is passed instead. For the function return value, the register R0 or S0 are used for integers and floating-point result of the subroutine, respectively.In your case, there is a need for one fixed-point (the address of the struct) detailed below and one floating-point input parameter (value of current measurement). The state of the Kalman filter is the result of your subroutine, but keep in mind that this can be achieved in a way that no output value is produced by the subroutine. This is effectively, the “call by reference” that you should be familiar with from the C programming.The filter will hold its state as a quintuple (q, r, x, p, k) that are five single-precision floating-point numbers. In the next lab, it will be convenient to keep these state variables in a single C language struct, holding Kalman filter state in each time step, consisting of: float q; //process noise covariance float r; //measurement noise covariance float x; //estimated value float p; //estimation error covariance float k; // adaptive Kalman filter gain.The operation of the filter should be correct for all operations of inputs and state variables, including when there are the arithmetic conditions such as overflow.1. All registers specified by ARM calling convention to be preserved, as well as the stack position should be unaffected by the subroutine call upon returning. 2. The calling convention will obey that of the compiler. Two registers, R0 and S0 contain the arguments, which are respectively the pointer to the state variables structure and the current measurement value. While there is no required result value, please note that the state variables pointed to by the pointer, will be modified.3. No memory location should be used to store any intermediate data. Not only that it should be faster, but no memory allocation is needed that way. 4. The subroutine should be location independent. It should be able to run properly when it is placed in different memory locations.5. The subroutine should not use any global variables. 6. The subroutine should be as fast as possible, but robust and correct for all cases of positive and negative numbers, as well as the overflows. Grading of the experiment will depend on how efficiently you solve the problem, with all the corner cases being correct.Hints: ARM Assembly Code1. It helps to solve the problem conceptually at first, taking into account all corner cases, including the arithmetic overflows. Move to assembly code when the algorithm is well defined. (If you wish to implement the code in C, it can only help you here and also for Part 2, where you will be asked to produce several variations to the basic solution.)2. Follow the examples of codes and instructions elaborated in classes, tutorials and material posted online for getting quickly to the working code. When optimizing for speed, some ARM Cortex instructions, such as those replacing directly bits between two words could help.3. Document assembly code thoroughly and thoughtfully. It takes only a few hours for you to forget what each register holds and what implicit assumptions were used. It is useful to consider the assembler features that improve the coding style, such as the declaration of register variables, symbolic constants and similar.4. Please keep in mind that the processor does not activate the floating-point unit on powerup. Following the example given in the tutorial, ensure that the floating-point unit is not bypassed.Linking 1. When creating a new project, it is simplest to follow the created template. You will notice that your IDE creates main.c and also the startup code in assembly. You can either a. modify the startup code to branch to kalman rather than __main for testing assembly code alone, prior to embedding into C main program, orb. you can call your assembly code from the main (all calling conventions need to be observed). Please note that you will need to declare as global (exported) the subroutine name in your assembly code, as well as follow up the syntax rules for GCC Assembly language.2. For linking with C code that has main.c, no special measures should be needed, so option b) above is better and is readily expandable to the Part 2 extension.3. If the linker complains about some other missing variable to be imported in startup code, you can either declare it as “dummy” in your assembly code, or comment its mention in the startup code.Test Samples Be prepared to use your and TA-provided test samples exercising all the relevant cases.The demonstration involves showing your source code and demonstrating a working program. Your program will be placed at an arbitrary memory location. You should be able to call your subroutine several times consecutively. You should be able to explain what every line in your code does – there will be questions in the demo dealing with all the aspects of your code and its performance. The questions might regard the skeleton code to initiate and start the assembly code that we gave you in the tutorial 1; ask if you do not know!While the full report will be needed for Part 2, which will include the code developed here, it is by far the most efficient that you have the full documentation on your assembly code subroutine completed upon demonstrating the Part 1, especially that the second part will require lots of documentation and additional code development on its own.You will perform this exercise in several stages and record the results obtained at each step in your lab report. First, you will augment the main C program to use the subroutine kalman repeatedly for an array of inputs.Your subroutine call will appear in the C source code exactly as if the C subroutine is used. In doing this, you should follow all the usual rules of writing C programs, keeping in mind that the executable program consists of multiple independently compiled modules.The filter state is a quintuple (q, r, x, p, k) kept in a single C language structkalman_state, consisting of: float q; //process noise covariance float r; //measurement noise covariance float x; //estimated value float p; //estimation error covariance float k; // adaptive Kalman filter gain.The operation of the program should be correct and as efficient as possible. To illustrate the operation of Kalman filter within your main program, Table 1 lists the state vector entries before and after the execution of first four iterations for the case where the initial value of x=5 and measurement(i)=i.Table 1: Evolving Kalman Filter State Space measurement(i) Before 0 0 1 2 3 4 q 0.1 0.1 0.1 0.1 0.1 0.1 r 0.1 0.1 0.1 0.1 0.1 0.1 p 0.1 0.067 0.0625 0.06 0.06 0.06 x 5 1.67 1.25 1.71 2.5 3.43 k 0 0.67 0.625 0.62 0.62 0.62 Processing filtered dataIn the second part of the lab, you will implement functions in embedded C to track the input variable, following the Kalman filter tracking algorithm. The code should execute on a fixed-length input value vector, consisting, say, of 100 values that will be provided by TAs.1. To assess the properties of the Kalman filter tracking of the input stream, you will add four additional operations at the end: a. Subtraction of original and data obtained by Kalman filter tracking. b. Calculation of the standard deviation and the average of the difference obtained in a). c. Calculation of the correlation between the original and tracked vectors. d. Calculation of the convolution between the two vectors.You will then profile the code and compare the speed of your assembly code implementation of the Kalman filter with the equivalent C code subroutine.You will also re-implement the C and assembly code for kalman using the CMSIS-DSP library with the aims of: 1. Cross-validating the C code against the CMSIS-DSP implementation – one lab group member can start preparing the CMSIS-DSP implementation from the beginning, so that your assumptions about the code get validated as well.2. Comparing the performance and appreciating the utility of CMSIS-DSP.3. Becoming proficient in CMSIS-DSP and capable of using any part of the CMSIS in future labs.Some observations from these calculations are in place: • Kalman filter convergence depends on the initial values. The closer the x is to the measurement, the smaller the need for correction. • By deviating from C programming practices, you risk passing the wrong parameters, so please be aware of that Function RequirementsDesign a C function: int Kalmanfilter(float* InputArray, float* OutputArray, kalman_state* kstate, int Length)Here: -InputArray is the array of measurements -OutputArray is the array of values x obtained by Kalman fiter calculations over the input field (cf. Table 1)-The kstate struct contains the Kalman filter state that is readily available for your debugging -Integer Length specifies the length of the data array to process The output encodes whether the function executed properly (by returning 0) or the result is not a correct arithmetic value (e.g., it has run into numerical conditions leading to NaN)1. The function KalmanFilter should call your ‘kalman’ subroutine wherever appropriate. Unnecessary operations should be avoided. 2. Use the ARM calling conventions for later inclusion into a C program. 3. Upon returning from subroutines, the registers and stack should be untouched. 4. The subroutine should be location independent. 5. The subroutine should be robust, correct and then fast.The idea is that the C function will be the interface to the test harness provided by TAs, and with the same interface (often referred to as a wrapper) you can call either the assembly, plain C or the CMSIS-DSP code.Useful Notes In realizing your code, you are encouraged to use good C coding practices, such as the use of conditional compiling for retargeting to different execution cases given above. Feel free to consult our online tutorial on embedded C, found in the Documentation part of the Content.While developing your code, you will spend substantial time using the debugger. Please follow the instruction from Tutorial 2 to ensure that the compilation for the simulator (and the debugger running on simulated code) compiles properly. The profiler will be a useful tool when the code is bug free and you want to assess and improve the performance of your code.Experimental Results to Report You are asked to perform the following experiments and include the results in your report. 1. Run the program and record the execution for a trace of your choice that nicely illustrates the properties of Kalman filter, such as the convergence towards the input stream and the statistical properties of the deviation to the input,2. Explicitly calculate in your program the difference to the input stream, standard deviation and average of that difference, as well as the correlation and convolution between the two streams. 3. Using CMSIS-DSP, perform the same functions as in 2.4. Using code profiling, report the running times for all the procedures with your code and CMSIS-DSP. You should get the results as fast as possible. 5. Rewrite your core Kalman filter code in plain C as well as in C using the CMSIS-DSP. Keep in mind that it is possible to obtain the “scalar” version of CMSIS-DSP when needed. 6. Report the profiling data that compares the three versions of Kalman filter core (assembly, plain C and CMSIS-DSP). 7. Summarize the lessons learned on the use of assembler, C and CMSIS-DSP by selecting the suitable profiling data. 8. Finally, run the code on the actual processor and use the debugger to inspect and modify the program variables while the code is running. Summarize in the report on the rules: which variables can be watched, modified and whether and how that can be done without stopping the processor. Final Report Once you have all the parts working, include all the relevant data to your report, which will be due first day in a week following the Lab 2 demonstration, but not later than 4 days after the demo. Please follow the report guidelines included in the lecture slides.
1. (24 marks) This question will examine the concept of Locks. 1.1. Implement the Filter lock described in Chapter 2 of the course text. 1.2. Does the Filter lock allow some threads to overtake others an arbitrary number of times? Explain. 1.3. Implement Lamport’s Bakery lock also described in Chapter 2.1.4. Does the Bakery lock allow some threads to overtake others an arbitrary number of times? Explain 1.5. Propose a test that verifies if a lock works, i.e., if it provides mutual exclusion.1.6. Provide an implementation for the proposed test and verify if the implemented locks do provide mutual exclusion.2. (8 marks) Consider LockOne and LockTwo introduced in the text book; do they still satisfy twothread mutual exclusion if the shared atomic registers – “flag” in LockOne and “victim” in LockTwo – are replaced by regular registers?3. (12 marks) Programmers at the Flaky Computer Corporation designed the protocol shown in Fig. 1 to achieve n-thread mutual exclusion. For each question, either sketch a proof, or display an execution where it fails.3.1. Does this protocol satisfy mutual exclusion? (Hint: Start the proof by assuming that two threads A and B are in the critical section at the same time.) 3.2. Is this protocol deadlock-free? Explain. 3.3. Is this protocol starvation-free? Explain.1 class LockThree implements Lock { 2 private int turn; 3 private boolean busy = false; 4 public void lock() { 5 int me = ThreadID.get(); 6 turn = me; 7 do { 8 busy = true; 9 } while ( turn = me || busy); 10 } 11 public void unlock() { 12 Busy = false; 13 } 14 } Fig.1 LockThree Lock used in Question 24. (12 marks) For each of the histories shown in Figs. 2 and 3, are they sequentially consistent? Linearizable? Justify your answer. Fig. 2 History (a) Fig. 3 History (b)5. (8 marks) Consider the class shown in Fig. 4. Suppose two threads A and B are concurrently calling the methods writer and reader. 5.1. According to what you have been told about the Java memory model, will the reader method ever divide by zero? If yes, describe the order in which writer and reader should be invoked (by threads A and B) and take effect for a division by zero to happen.5.2. Is division by zero possible if both x and v are volatile? What happens if neither x nor v are volatile? Justify your answer. Fig. 4 Volatile example6. (8 marks) Consider the regular M-valued MRSW construction shown in Fig. 5; True or false: 6.1. If we change the loop at line 11 to “for (int i = x + 1; i < RANGE; i++)”, then the construction is still a regular M-valued MRSW register. Justify your answer.6.2. If we change the loop at line 11 to “for (int i = x + 1; i < RANGE; i++)”, then the construction yields a safe M-valued MRSW register. Justify your answer. Fig. 5 The regular M-valued MRSW class7. (4 marks) Show that if binary consensus using atomic registers is impossible for two threads, then it is also impossible for n threads, where n > 2. (Hint: argue by reduction: if we had a protocol to solve binary consensus for n threads, then we can transform it into a two-thread protocol.)8. (4 marks) Show that if binary consensus using atomic registers is impossible for n threads, then so is consensus over k values, where k > 2. Total: 80 marks
Question 1. Add the stamps for the following elements in functions named makeGmatrix.m, makeCmatrix.m, and makeBvect.m a. Resistor (already Implemented) b. Capacitor c. Inductord. Voltage Source (already Implemented for DC voltage sources) e. Current Source f. Voltage Controlled Voltage Source g. Voltage Controlled Current Source h. Current Controlled Current Source i. Mutual Inductor j. Ideal opampQuestion 2. Write a frequency analysis function named fsolve.m. Run all test bench functions provided to test your simulator.Deliverables: 1. Submit all your code in a zip file. 2. Submit a PDF file containing your results for all testbench functions.
In this problem, you will implement texture analysis and segmentation algorithms based on the 5×5 Laws Filters constructed by the tensor product of the five 1D kernels in Table 1.a) Texture Classification – Feature Extraction (15%) 48 images of four types of textures are given for the texture classification task. They are split into two sets, 36 training samples and 12 testing samples. The ground truth labels of the 36 training samples are known, while the testing samples’ categories are waiting for you to explore. Samples of these images are shown in Fig. 1. Figure 1: Examples of Grass, Blanket, Stones, Brick [2]Please follow steps below to extract features for all texture images provided and do analysis: 1. Filter bank response computation: Use the twenty-five 5×5 Laws Filters in Table 1 to extract the response vectors from each pixel in the image (use appropriate boundary extensions).2. Energy feature averaging: Compute the energy feature of each element of the response vector. Average the energy feature vectors of all image pixels, leading to a 25-D feature vector for each image. Which feature dimension has the strongest discriminant power? Which has the weakest? Please justify your answer.3. Feature reduction: Reduce the feature dimension from 25 to 3 using the principal component analysis (PCA). Plot the reduced 3-D feature vectors in the 3-D feature space. Please conduct texture classification using the nearest neighbor rule based on the Mahalanobis distance. Note: Built-in PCA function can be used.b) Advanced Texture Classification — Classifier Exploration (20%) Based on the 25-D and 3-D feature vectors obtained above, conduct both unsupervised and supervised learning. Please follow the steps below.1. Unsupervised: K-means clustering is a kind of unsupervised learning algorithm which separates the textures into different categories without the help of ground truth labels. It will not directly tell the class for each image but will group similar images together.a. Apply the K-means algorithm for test images based on the 25-D feature and the reduced 3- D feature, respectively. Set the hyperparameter K (number of clusters) equal to the number of possible classes in the dataset (e.g. K=4).b. Use the test labels to evaluate the purity of each cluster. Specifically, classify the images in each cluster as the majority class of that cluster. Report the error rate for both methods. Discuss the effectiveness of the feature dimension reduction over the K-means clustering.2. Supervised: Use the 3-D feature of training images to train the Random Forest (RF) and the Support Vector Machine (SVM), respectively. Then predict the test set labels and report the error rate. Compare the two classifiers. Note: Built-in K-means function, RF and SVM can be used.a) Basic Texture Segmentation (20%) Segment the texture mosaic Mosaic.raw in Fig. 2 by following the steps below: 1. Filter bank response computation: Use the twenty-five 5×5 Laws Filters in Table 1 to extract the response vectors from each pixel in the image (use appropriate boundary extensions).2. Energy feature computation: Use a window approach to compute the energy measure for each center pixel based on the results from step 1. You may try a couple of different window sizes. After this step, you will obtain 25-D energy feature vector for each pixel.3. Energy feature normalization: All kernels have a zero-mean except for �5!�5. Actually, the feature extracted by the filter �5! �5 is not a useful feature for texture classification and segmentation. Use its energy to normalize all other features at each pixel.4. Segmentation: Discard the feature associated with L5T L5. Use the K-means algorithm to perform segmentation on the composite texture image given in Fig. 2 based on the 24-D energy feature vectors.If there are K textures in the image, your output image will be of K colors, with each color represents one type of texture. Use the following randomly generated color map to represent the K=6 regions. The ordering does not matter. 0 1 2 3 4 5 R 107 114 175 167 144 157 G 143 99 128 57 147 189 B 159 107 74 32 104 204 Figure 2: Texture mosaic image. [3]b) Advanced Texture Segmentation (10%) You may not get good segmentation results for the complicated texture mosaic image in Fig. 2. Please develop some techniques to improve your segmentation result. Several ideas are sketched below.1. Use the PCA for feature reduction. Use the dimension reduced features to do texture segmentation of Fig. 2. 2. Develop a post-processing technique to merge small holes. 3. Enhance the boundary of two adjacent regions by focusing on the texture properties in these two regions only.Image feature extractors are useful for representing the image information in a low dimensional form. (a) Salient Point Descriptor (Basic: 10%) SIFT is an effective tool to extract salient points in an image. Read the paper in [1] and answer the following questions.1. From the paper abstract, the SIFT is robust to what geometric modifications? 2. How does SIFT achieve its robustness to each of them? 3. How does SIFT enhance its robustness to illumination change? 4. What are the advantages of using Difference of Gaussians (DoG) instead of Laplacian of Gaussians (LoG) in SIFT?5. What is the SIFT’s output vector size in its original paper?(b) Image Matching (Basic: 15%) You can apply SIFT to image matching. Extract and show SIFT features. 1. Find key-points of the Cat_1 and Cat_Dog images in Fig. 3. Pick the key-point with the largest scale in Cat_1 and find its closest neighboring key-point in Cat_Dog. You can do nearest neighbor search in the searching database for the query image Cat_1 which is represented as a SIFT extracted feature vector. Discuss your results, especially the orientation of each key-point. Show the corresponding SIFT pairs between Cat_1 and Cat_Dog.2. Perform the same processing with the following three image pairs: a) Dog_1 and Cat_Dog, b) Cat_1 vs Cat_2, c) Cat_1 vs Dog_1. The matching may not work well between different objects or against the same object but with a large viewing angle difference. Show and comment on the matching results. Explain why it works or fails in some cases.You are allowed to use open source library (OpenCV or VLFeat) to extract features. (a) Cat_1 (b) Cat_2(c) Dog_1 (d) Cat_Dog Figure 3: Images for image matching. [4] (c) Bag of Words (10%) If we create a codebook with K codewords representing K types of key patterns, each image can be represented by the codewords. A histogram can be calculated to reflect the occurrence of each codeword in an image. This representation is called the Bag of Words (BoW).Apply the K-means clustering to the extracted SIFT features from the four images in part (b) to form a codebook with K=8 codewords. Each codeword is characterized by the centroid of the SIFT feature vectors. Generate the BoW representations for Cat_1, Dog_1 and Dog_2 provided in the materials. Match Dog_2’s BoW representation with Cat_1 and Dog_1, respectively. Which one gives you the better matching? Show the histograms of these three images and discuss your observations.Figure 4: Dog_2 image. [4] Appendix: Problem 1: Texture Analysis 48 texture images (./train and ./test) 128×128 8-bit grayscale Problem 2: Texture Segmentation Mosaic.raw 512×512 8-bit grayscale Problem 3: Image Feature Extractors Cat_1.raw 600×400 24-bit Color (RGB) Cat_2.raw 600×400 24-bit Color (RGB)Cat_Dog.raw 600×400 24-bit Color (RGB) Dog_1.raw 600×400 24-bit Color (RGB) Dog_2.raw 600×400 24-bit Color (RGB) Reference Images Images in this homework are taken from SIPI Image Database [2], Prague dataset [3] and Google images [4].References [1] David G. Lowe, “Distinctive image features from scale-invariant keypoints,” International Journal of Computer Vision, 60(2), 91-110, 2004 [2] https://sipi.usc.edu/database/ [3] https://mosaic.utia.cas.cz/ [4] [Online] http://images.google.com/
(a) Bilinear Demosaicing (10%) To capture color images, digital camera sensors are usually arranged in form of a color filter array (CFA), called the Bayer array, as shown in Figure 1. Since each sensor at a pixel location only captures one of the three primary colors (R, G, B), the other two colors have to be re-constructed based on their neighbor pixel values to obtain the full color. Demosaicing is the process of translating this Bayer array of primary colors into a color image that contains the R, G, B values at each pixel.Figure 1: (a) Single CCD sensor covered by a CFA and (b) Bayer pattern [1]. Implement the simplest demosaicing method based on bilinear interpolation. Exemplary demosaicing results are given in Figure 2. With this method, the missing color value at each pixel is approximated by bilinear interpolation using the average of its two or four adjacent pixels of the same color.To give an example, the missing blue and green values at pixel �!,# are estimated as: As for pixel �!,!, the blue and red values are calculated as:(a) (b) Figure 2: (a) The original image and (b) the demosaiced image by bilinear interpolation. Figure 3: The House image before demosaicing. (1) Apply the bilinear demosaicing to the House image in Figure 3 and show your results. (2) Compare your demosaiced image with the color image House_ori which is obtained from a more advanced demosaicing algorithm. Do you observe any artifacts? If yes, explain the cause of the artifacts and provide your ideas to improve the demosaicing performance.(b) Histogram Manipulation (20%) Implement two histogram equalization techniques: • Method A: the transfer-function-based histogram equalization method, • Method B: the cumulative-probability-based histogram equalization method to enhance the contrast of the Hat image in Figure 4 below.(1) Plot the histograms of the original image. The figure should have the intensity value as the x-axis and the number of pixels as the y-axis. (2) Apply Method A to the original image and show the enhanced image. Plot the transfer function. (3) Apply Method B to the original image and show the enhanced image. Plot the cumulative histograms before and after enhancement.(4) Discuss your observations on these two enhancement results. Which one do you think is better and why? Note that MATLAB users CANNOT use functions from the Image Processing Toolbox except displaying function like imshow(). Figure 4: Hat image(c) Contrast Limited Adaptive Histogram Equalization (15%) Instead of histogram equalization using global statistics from the entire image, adaptive histogram equalization breaks one image into several regions (tiles) and finds the histogram in each separately. Contrast Limited Adaptive Histogram Equalization (CLAHE) is one of the most popular algorithms.Please read the paper [2] carefully to learn about CLAHE. In this problem, you will apply the CLAHE to do image haze removal, where you remove the fog in the provided image taken in a bad weather. Figure 5 shows an example before and after the haze removal. The process can be done through the following 3 steps.Step-1: Transform the image from RGB color space to YUV color space. The transformation can be found in the Appendix. Step-2: Apply a histogram equalization algorithm on the Y channel to get Y’. Step-3: Combine Y’ with U and V, transform them back to RGB color space. The resulted image is your haze-removed image.(1) Explain CLAHE in your own words. (2) Perform the above three steps on Taj_Mahal.raw by applying the two histogram equalization methods in Problem 1(b) in step-2. Show the resulted images for both methods.(3) Repeat the three steps but apply the CLAHE in step-2. Here, you are allowed to use open-source code for CLAHE. For C++, you can use OpenCV. For Matlab, you can check function adapthisteq. Tune the hyperparameters including the number of tiles and the clip limit. Show the resulted image that you think is the most pleasant subjectively.(4) Compare your results between (2) and (3). Discuss your observations. (a) Original foggy image (b) Defogged image Figure 5: An examples of image haze removal.In this problem, you will implement a set of denoising algorithms to improve image quality. You can use the PSNR (peak-signal-to-noise-ratio) quality metric to assess the performance of your denoising algorithm. The PSNR value for R, G, B channels can be, respectively, calculated as follows:Remove noise in the image in Figure 5(b), compare it with the original image in Figure 5(a), and answer the following questions: (a) Basic denoising methods (10%) (1) What is the type of embedded noise in Figure 5(b)? Justify your answer. (2) Apply a linear filter to the noisy image. Compare the performance of two choices of the filter parameters – the uniform weight function and the Gaussian weight function under different filter sizes.(a) Original image (b) Noisy image Figure 5: The original and noisy Flower images. (b) Bilateral Filtering (10%)In most low-pass linear filters, we often see degradation of edges. However, using some nonlinear filters, we can preserve the edges. Bilateral filters are one such kind of filters. A discrete bilateral filter is given by: where (�, �) is the neighboring pixel location within the window centered around (�,�), � is the image with noise, � is the filtered image. �$ and �% are two spread parameters.(1) Implement the bilateral denoising filter and apply it to the noisy image. (2) Explain the roles of �$ and �%. Discuss the change in filter’s performance with respect to the values of �$ and �%. (3) Does this filter perform better than linear filters you implemented in Problem 2(a)? Justify your answer in words.(c) Non-Local Means (NLM) Filtering (10%) The non-local mean filter utilizes the pixel value from a larger region rather the mean of a local window centered around the target pixel. A discrete non-local mean filter with Gaussian weighting function is as follows:where �, � are the noisy and filtered images respectively, �&,’ is the window centered around location (�, �), and ℎ is the filtering parameter, �( ≤ � and �( ≤ � denote the window size of your choice.The Gaussian weighted Euclidian distance between window �3�),*4and �3�+,,4 is defined as: 5�3�),*4 − �3�+,,45-,. – = 8 �.(�/, �-)3�(� − �/,� − �-) − �(� − �/, � − �-)4 0!,0″∈ℵ – where ℵ denotes the local neighborhood centered at the origin, �!, �” ∈ ℵ denotes the relative position in the neighborhood window. � > 0 is the standard deviation of the Gaussian kernel.(1) Apply the NLM filter (using any open-source code, e.g. C++ can use OpenCV, Matlab can check function imnlmfilt) to the noisy image. Try several filter parameters and discuss their effect on filtering process. Clearly state your final choice of parameters in your report.(Note that there are four parameters to discuss: the big search window size ℵ, the small neighbor window size �( , the Gaussian smoothing parameter for the search window ℎ, the Gaussian smoothing parameter for the neighbor window �. If the open source code doesn’t provide ways to adjust a certain parameter, just analyze that parameter theoretically.)(2) Compare the performance of NLM with filters used in Problem 2(a) and Problem 2(b). (d) Mixed noises in color image (10%) Figure 6 (b) is a noisy color image corrupted with mixed types of noises. Please identify noise types in the image and answer the following questions:(1) What types of noises are there? Justify your answer. (2) What filters would you like use to remove mixed noise? Can you cascade these filters in any order? Justify your answer. (3) Get the best results in removing mixed noise. Include the following in your report: 1. Describe your method and show its results 2. Discuss its shortcomings. 3. Give some suggestions to improve its performance. (a) (b) Figure 6: (a) the original Flower image (b) the Flower image with mixed noises.An exemplary frosted glass effect for the Lake image is shown in Figure 8.Figure 8 An example of frosted glass effect This effect can be created by simply replacing the color at each pixel with the color at a random pixel in its local neighborhood of size NxN. For example, considering N=3, the color of the center pixel at location 0 can be replaced by the color at any of the location 0-8 (including the location 0 which means unchanged).(1) Implement the frosted glass filtering with N = 5 or 7 and apply it to the Flower.raw image. Note that you can still formulate the process as a 2-D image filtering problem. (2) Repeat the process for the noisy image Flower_noisy.raw. Describe your observations and discuss whether the noise leads to any difference.(3) Considering the Bilateral filtering denoising algorithm. Try the following two processes: a. First, perform denoising on Flower_gray_noisy.raw. Then, apply the frosted-glass filtering. b. First, apply the frosted-glass filtering on Flower_gray_noisy.raw. Then, perform denoising. Compare your results and discuss your observations.Appendix: Problem 1: Image Demosaicing and Histogram Manipulation House.raw 768×512 8-bit gray House_ori.raw 768×512 24-bit color(RGB) Hat.raw 256×256 8-bit gray Taj_Mahal.raw 600×400 24-bit color(RGB) Problem 2: Image Denoising & Problem 3 Flower.raw 768×512 24-bit color(RGB) Flower_noisy.raw 768×512 24-bit color(RGB) Flower_gray.raw 768×512 8-bit gray Flower_gray_noisy.raw 768×512 8-bit gray Note: “768×512” means “width=768, height=512”. Convert from RGB to YUV color space Y = (0.257 * R) + (0.504 * G) + (0.098 * B) + 16 U = -(0.148 * R) – (0.291 * G) + (0.439 * B) + 128 V = (0.439 * R) – (0.368 * G) – (0.071 * B) + 128 Convert from YUV to RGB color space R = 1.164(Y – 16) + 1.596(V – 128) G = 1.164(Y – 16) – 0.813(V – 128) – 0.391(U – 128) B = 1.164(Y – 16) + 2.018(U – 128)Reference Images All images in this homework are from Google images [3], USC-SIPI image database [4], Kodak image dataset [5] or others [6].References [1] M. E. Celebi et al. (eds.), Color Image and Video Enhancement. [2] Zuiderveld, Karel. “Contrast Limited Adaptive Histograph Equalization.” Graphic Gems IV. San Diego: Academic Press Professional, 1994. 474–485. [3] [Online] http://images.google.com/ [4] [Online] http://sipi.usc.edu/database/ [5] http://r0k.us/graphics/kodak/ [6] https://comedytravelwriting.com/5-best-photos-of-the-taj-mahal-in-fog/
Take what you’ve learned in this class and design and implement a fun/cool project that utilizes the DE1SoC board and peripherals.Be creative! You are required to use: 1) A VGA display (building off of Lab 5). 2) Some form of significant memory storage (e.g., pixel data, audio clip, other game data). You can refer to Labs 2–4 for a refresher on initializing and using memory.3) Some form of user input, which could be the switches and push buttons or some of the peripherals listed below.You can, and are encouraged to, use additional peripherals. All drivers you will need for this lab can be found in the folder on Canvas within the folder. Unfortunately, we are limited to the currently available interfaces on Labs Land, but these include:• Sound output from a speaker (building off of Lab 3). • A virtual 360-degree joystick. • An “N8” controller, shown in the form of an old controller System (4 directional pad, Select, Start, A, B). from the Nintendo EntertainmentNotes for using a VGA display: Please note that the provided VGA driver in the featured than the one provided in Lab 5. folder is different and more fullyNotes for using audio output: Recall that LabsLand does not allow you hear your audio live. Unfortunately, this means you can’t do things like producing sounds/noises at certain events as they would only be heard in the recording afterward. However, it would be acceptable to produce an audio output as a final artifact based on the user input (e.g., a beat or drum generator).Project Ideas You are allowed to take inspiration and code from elsewhere (e.g., a software implementation, your 271/369 project), but make sure that you cite your sources. However, these portions will not count towards the overall difficulty of your project – we care about what you will be implementing this quarter.Category 1: Games • Side-scrolling: The player(s) move through a level, avoiding or destroying obstacles or enemies. • Combat: Two or more players compete to collect points and/or defeat the others, maybe with projectiles or by growing their own body as an obstacle. • Tile-matching: Tetris, Bust-a-Move, Candy Crush, or something of similar complexity. • Card: Blackjack, Solitaire, Set, or something of similar complexity.Category 2: Audiovisual • Paint: Allow the user to draw on the VGA or otherwise change an image output. • Audio Visualization: Use an audio input file to display some sort of reactive visualization. • Music Generation: Take in user input to generate sound, e.g., music notation/composition. Basic pixel-by-pixel painting is not complex enough to be used as the sole feature of a project – this will need to be extended with other, more complex features.Category 3: Create Your Own Come up with your own idea that satisfies the list of requirements above and submit a proposal to the course staff! Past class video with other examples: https://youtu.be/3J6ZwsfqRKQ Do note that that video is from when the course was using DE1-SoC lab kits, so there were different peripherals available.Project Explanation Video This quarter will not require a video demo. The links below are left as examples. Here are some links (UW login required) to past project videos that earned full scores on the video (i.e., not necessarily on the project itself):• Flood Fill Algorithm: https://drive.google.com/file/d/1wQ0kaWS5sYTW_nqx97thSxf5XRjbGFSy/view?usp=sharing • Red Light, Green Light Game: https://drive.google.com/file/d/17OUh_Y5rUIQt0QEx2tVa1pa4yn0tr5e/view?usp=sharingProject Demonstration/Turn-In Requirements In-Person Demo • Demonstrate your completed project working on LabsLand. • Be prepared to answer questions on both the theoretical and practical parts of the project.Project Report (submit as PDF on Gradescope) • Include the required Design Procedure, Results, and Experience Report sections. o If you worked with a partner, include a partner work summary in your Experience Report. • Don’t forget to also submit your SystemVerilog files ( ), including testbenches!Lab 6 Rubric Grading Criteria Points Name, student ID, lab number 2 pts Design Procedure 20 pts Results 14 pts Experience Report 14 pts SystemVerilog code uploaded 5 pts Code Style 5 pts PROJECT DEMO 70 pts ▪ Bonus points available for particularly impressive projects (10 pts) 140 ptsSubmit a PDF document to Gradescope detailing your proposed Lab 6 project, even if it is from the list of suggestions. This document should be only a few paragraphs long and will give us a chance to verify that you’ve put some thought into your project and that your project (especially if not from the list of suggestions), is of an appropriate difficulty level, i.e., it is not too simple nor too difficult.Recall that, in addition to the standard DE1-SoC switches and push buttons, you have the following peripherals available for use, though in pre-defined subsets based on the LabsLand interfaces: 1) A VGA display (building off of Lab 5, but note that there is a new driver available for Lab 6). 2) Sound output from a speaker (building off of Lab 3)†. 3) A virtual 360-degree joystick. 4) An “N8” controller, shown in the form of an old controller from the Nintendo Entertainment System (4 directional pad, Select, Start, A, B).† Recall that LabsLand does not allow you hear your audio live. In your proposal: • Describe your major project behavior, features, components/modules, and user interaction. • Include at least a top-level block diagram (other diagrams welcome). Be sure to label the blocks and ports in your diagram as best you can. Don’t worry if the final design differs from your proposal.Lab 6 Proposal Rubric Grading Criteria Points Project description 5 pts System block diagram, with labels 5 pts 10 pts
In computer systems it is necessary to provide a substantial amount of memory. If a system is implemented using only FPGA technology, it is possible to provide some amount of memory by using the memory resources that exist in the FPGA device. In this lab, we will examine the general issues involved in implementing such memory.The FPGA included on the DE1-SoC board provides dedicated memory resources and has M10K blocks, each of which contains 10240 memory bits. The M10K blocks can be configured to implement memories of various sizes. A common term used to specify the size of a memory is its aspect ratio, which gives the depth (in words) and the width (in bits) as depth × width. In this lab, we will use an aspect ratio of 32 × 3.There are two important features of the M10K blocks: 1) They include registers to synchronize all the input and output signals to a clock input. 2) They have separate ports for writing data to the memory and reading data from the memory.A conceptual diagram of the Random-Access Memory (RAM) module that we want implement is shown in Figure 1a. It contains 32 three-bit words (i.e., rows) that are accessed using a five-bit port, a three-bit bidirectional port, and a control input. However, given the properties of the M10K blocks, we will instead implement the modified 32 x 3 RAM module shown in Figure 1b. It includes registers for the address, data input, and write ports, and uses a separate unregistered data output port. Figure 1: 32 x 3 RAM module for Lab 2.Remember to start the tasks in this lab by either following the first steps from the Warmup Task from Lab 1 or by making a copy of an existing Quartus project folder.Commonly used logic structures, such as adders, registers, counters, and memories, can be implemented in an FPGA chip by using prebuilt modules that are provided in libraries. In this exercise, we will use such a module to implement the memory shown in Figure 1b. 1) Create a new Quartus project. 2) Get a library RAM module from the IP Catalog: a) Open the IP Catalog in the Quartus menu by clicking on → “ ”. b) In the IP Catalog window, expand “ ”, then “ ”, then “ ”. Then double-click “ ”.c) In the “ ” dialog box that opens, append the text “ ” to the end of the file name and select “ ” as the file type. Then click “ ” to open the configuration wizard. d) In the configuration window, specify 3-bit width for the output bus and 32 words of memory.Then select the “ ” radio button for memory block type and “ ” for the clocking method before clicking “ ”.e) Now, deselect the check box for registering (i.e., placing a register on) the “ ”. This creates a RAM module that matches the structure in Figure 1b. Click “ ” to accept the defaults for the rest of the settings in the Wizard. f) You will have to click “ ” one more time at the Summary page to exit the Wizard. If prompted, add the new Quartus Prime IP File to your project by clicking “ ”.3) Go to “ ” in the Project Navigator window and open (nested under ) to examine it. It defines the following module:4) Create a new SystemVerilog file called that instantiates the module, using appropriate input and output signals for the memory ports as shown in Figure 1b. a) Once you compile your circuit, various parts of the Compilation Report will indicate that the RAM circuit is implemented using 96 bits in one of the FPGA memory blocks. module ram32x3 (address, clock, data, wren, q); input [4:0] address; // Address input clock; input [2:0] data; // DataIn input wren; // Write output [2:0] q; // DataOut // …Check above the definition of this module. If you see a line that looks like the following: you will need to add the same line just above your testbench module in Step 4, otherwise you may see the following error message during simulation: “… does not have a timeunit/timeprecision specification in effect, but other modules do.”5) Create a suitable testbench to verify that you can read and write to the memory in simulation.Instead of creating a memory module by using the IP Catalog, we can implement the required memory by specifying its structure in SystemVerilog code as a multidimensional array. A 32 × 3 array, which has 32 words with 3 bits per word, can be declared by the statement: On the FPGA, such an array can be implemented either by using flip-flops found in each logic cell or, more efficiently, by using the built-in memory blocks.1) Write a SystemVerilog module in a new file that provides the necessary functionality as Task #1 but using a multidimensional array. You should be able to use the same testbench as Task #1. 2) Create a top-level SystemVerilog module in a new file that instantiates your new module and uses the inputs and outputs on the DE1-SoC as specified: a. Use switches – to specify and switches – to specify . b. Use as the signal and as the input.c. Display the value (in hex) on – , the value on , and on . A basic 7-segment driver module has been provided for you, which you can freely change; describe any changes you make, but no testbench or waveforms are needed for this module.3) Synthesize the circuit and download it to a DE1-SoC on LabsLand to test its functionality.You will likely encounter the following simulation error at first: “Instantiation of ‘altsyncram’ failed. The design unit was not found.” Solution: In the ModelSim menu, select → “ ” and then go to the tab and add under “ ”.Then, go to the tab, select your testbench module, and click . If you are using files to run your simulations, you can also add the text “ ” to the end of line where you specify your testbench module. logic [2:0] memory_array [31:0];In general, arrays with asynchronous reads (i.e., not registered) will be mapped to flip-flops and arrays with synchronous reads (i.e., registered) will be mapped to memory blocks. In LabsLand, make sure that you select the “Standard” user interface, as opposed to the “Breadboard” that we used in Lab 1:The RAM blocks in Figure 1 have a single port for both read and write operations. For this task you will create a different type of memory module that has separate ports for the addresses of read and write operations. You will also learn how to create and use a memory initialization file (MIF).1) Generate the desired memory module from the IP Catalog by using the “ ” module and call the file . a) Under “ ”, select “ ” and then “ ”. b) Configure the memory size, clocking method, and registered ports the same way as in Task #1. c) Under “ ”, select “ ”.i. This setting specifies that it does not matter whether the memory outputs the new data being written, or the old data previously stored, in the case that the write and read addresses are the same during a write operation.d) Under “ ”, select “ ” and specify the filename . i. This memory initialization file (MIF) allows us to initialize our RAM to specific values that are loaded when the circuit is programmed into the FPGA chip. You will create this MIF file in Step 2. e) Finish the Wizard and then examine the generated memory module in .2) Create your MIF file : a) In the Quartus menu, go to → and then select “ ”. b) Specify 32 words and word size of 3. c) Manually fill the grid with the values you want to place in each memory address. i. If helpful, the menu will let you adjust the number of cells per row displayed and the address and memory radices. d) Save the MIF file as . You can also manually edit this file in a text editor.3) Augment the top-level module (and its testbench) from Task #2 to use to toggle between the memories of Task #2 ( ) and Task #3 ( ). The following requirements are purposefully similar to Task #2 but pay attention to the differences. Any significant, new modules should have testbenches and simulations; you should mention the source for any provided or reused modules.a) Use – and – to specify the write address and write data, respectively. Display (in hex) the write address on – and the write data on . b) Use a counter to cycle through read addresses about one per second (no verification needed). Display (in hex) the read address on – and the 3-bit word content on .c) Use the 50 MHz clock, , to synchronize the system and use as a reset signal. Make sure that you properly handle metastability issues for asynchronous inputs. d) Make sure that the memories from Task #2 and Task #3 are independent of each other (i.e., writing to one memory should not be reflected in the other memory)!4) Test your circuit and verify that the initial contents of the memory match your file. Make sure that you can independently write data to any address by using the switches and move between the Task #2 and Task #3 memories using .Lab Demonstration/Turn-In Requirements In-Person Demo • Briefly show and explain your SystemVerilog memory implementation from Task #2. • Briefly show and your file from Task #3. • Demonstrate your working Task #3 memory circuit (which includes the Task #2 circuit) on the DE1- SoC. • Be prepared to answer 1-2 questions about your lab experience to the TA.Lab Report (submit as PDF on Gradescope) • Include the required Design Procedure, Results, and Experience Report sections. o The designs for basic or provided modules like the 7-segment driver and counter should be briefly mentioned, but you do not need to include state diagrams or simulations for these. • Don’t forget to also submit your SystemVerilog files ( ), including testbenches!Lab 2 Rubric Grading Criteria Points Name, student ID, lab number 2 pts Design Procedure ▪ System block diagram for your finished Task #3 (this includes Tasks #2) 6 pts Results ▪ Waveforms & explanations of Tasks #1 & 2 memories (recommended combined into a single simulation) ▪ Waveforms & explanations of top-level module for Task #3 ▪ Waveforms & explanations of any other significant and new modules for Task #3 12 pts Experience Report 6 pts SystemVerilog code uploaded 5 pts Code Style 5 pts LAB DEMO 26 pts 62 pts
This lab is a refresher on finite state machines (FSMs) that you learned about and designed in EE271 or CSE369.Consider a parking lot with a single gate for both entry and exit. To keep track of the occupancy of the lot, we decide to use two photosensors to track when cars enter or exit, as shown in Figure 1.When an object is between the photo transmitter and the photo receiver, the light is blocked and the corresponding output is asserted to . By monitoring the events of both sensors, we can determine whether a car is entering or exiting, or even if a pedestrian is passing through! You may assume that two cars won’t be entering/exiting at the same time.For example, the following sequence indicates that a car entered: 1) Initially, both sensors are unblocked (i.e., ) 2) Sensor becomes blocked (i.e., ) 3) Both sensors are blocked (i.e., ) 4) Sensor becomes unblocked (i.e., ) 5) Both sensors are unblocked (i.e., )Your task is to design a parking lot occupancy counter as follows: 1) Design and implement an FSM for the car detection with two input signals, and , and two output signals, and . The and signals assert true for one clock cycle when a car enters or exits the lot, respectively. a) You may assume that cars will not change direction while entering or exiting the parking lot. b) Make sure that your FSM does not detect pedestrians (how would the input pattern differ?).2) Design and implement a car counter with two control signals, and , which increment and decrement the counter, respectively, when asserted. a) Assume that the maximum capacity of the parking lot is 16 spots.3) Design and implement a module for the parking lot occupancy, which combines the car detection and the counter. Your system should have the following properties: Read the whole lab before starting on any work. If you have any questions at any point, first double-check the lab document. If you still cannot find the answer, you should ask a TA. Figure 1: The parking lot photosensor setup.a) Use off-board switches (i.e., not the s) to mimic the two photosensor outputs. b) Display the current car count on the seven-segment displays and , with the following exceptions: i. If the counter reaches , display “ ” on – . ii. When the lot is empty, display “ ” on – and the number “ ” on . c) Use 2 off-board LEDs (i.e., not your LEDRs) to indicate the values of the and signals.i. A logical should turn the corresponding LED on and a logical should turn it off. Figure 2: LabsLand GPIO headers (from GPIO_Guide.pdf) for your reference. Connecting off-board components requires the use of the GPIO pins of the DE1-SoC board. Please refer to the document “ ” for information on their usage in LabsLand. a) Wire the anodes of 2 LEDs to FPGA output ports. b) Wire the middle pins of the 3 switches to FPGA input ports of your choosing as your three inputs ( , , and ).Lab Demonstration/Turn-In Requirements In-Person Demo • Demonstrate your working parking lot occupancy counter on the DE1-SoC. • Demonstrate your reset functionality. • Be prepared to answer 1-2 questions about your design to the TA. Lab Report (submit as PDF on Gradescope) • Include the required Design Procedure, Results, and Experience Report sections. • Don’t forget to also submit your commented SystemVerilog files ( ), including testbenches!Lab 1 Rubric Grading Criteria Points Name, student ID, lab number 2 pts Design Procedure ▪ System block diagram and diagrams for car detection and counting 12 pts Results ▪ Simulations for top-level and car detection (none needed for car counting) ▪ Present state included in all FSM simulations 10 pts Experience Report 6 pts SystemVerilog code uploaded 5 pts Code Style 5 pts LAB DEMO 20 pts 60 pts Make sure that you read the document “ ” for details about what to expect during the lab demo and what we expect to be in your submitted lab report and SystemVerilog code. You can also read “ ” for more detailed examples.
1. (18 marks) Chapter 7, Memory access, Anderson Lock The following benchmark is designed to measure the average time for reading array A containing L elements from memory, when the array elements are s words apart: for stride s from 4 Bytes (1 word) to L/2 by 2x (s = 1, 2, 4, …, L/2) time the following loop (repeat many times and average) for i from 0 to L-1 load A[i*(s+1)] from memory (4 Bytes)So, the benchmark reads L words from memory into cache, where L is a constant; however, these L words are not consecutive memory locations (they are “s” words apart). The results obtained from the benchmark are shown in Fig.1: Figure1. Average time for reading each array elementAssuming only one level of cache exists, the cache line size is 4 words, and a single processor is running the benchmark, answer the following questions: 1.1 In Fig.1, when the total number of elements of the array – L – is smaller than L’, the average time per access remains constant. What does the value of L’ represent? What does time t0 show?1.2 When L is larger than L’, what does time t1 indicate in Fig.1? 1.3 For each part of the graph – parts 1, 2 and 3 -, justify its behaviour. We know a phenomenon called false sharing could cause unnecessary invalidations in ALock (Anderson Lock), and one way to avoid false sharing is to pad array elements so that distinct elements are mapped to distinct cache lines.1.4 Considering the results from Fig.1, how could the padding technique used in ALock degrade the overall performance of the lock?2. (18 marks) Chapter 9, examining the fine-grained algorithm 2.1. Provide the code for the contains() method missing from the fine-grained algorithm described in chapter 9. 2.2. Write a test to verify the contains() method and explain why your implementation is correct.3. (12 marks) Chapter 10, designing a bounded lock-based queue 3.1. Design a bounded lock-based queue implementation using an array instead of a linked list. Allow parallelism by using two separate locks for head and tail. 3.2. Try to transform your algorithm to be lock-free. Where do you run into difficulty?4. (32 marks) Chapter 16, matrix vector multiplication 4.1. Implement a sequential matrix vector multiplication. 4.2. Give an efficient and highly parallel multithreaded algorithm for multiplying an n × n matrix A by a length-n vector x that achieves work Θ(n 2 ) and critical path Θ(log n).[Hint: If you use a cached thread pool with the Future interface, to achieve the Θ(log n) critical path you can follow the algorithm for matrix multiplication in Chapter 16. Otherwise, depending on how you divide the problem, you could obtain a critical path different than Θ(log n). This is acceptable, just be sure to show your work and justify in your report the critical path of your implementation.]4.3. Write a test program that measures the execution time for multiplying a 2,000 by 2,000 matrix with a corresponding 2000 wide vector using the parallel method and sequential method, respectively. Discuss the execution time of the two methods and compute the speedup. Be sure to indicate how many threads are being used.4.4. Analyze and discuss the work and critical-path length of your implementation, and give the parallelism. Total: 80 marks
1. (24 marks) Matrix multiplication is a common operation in linear algebra. Suppose you have multiple processors, so you can speed up a given matrix multiplication. 1.1. Modify the following method in the sample code to Implement a matrix multiplication sequentially: public static double[][] sequentialMultiplyMatrix(double[][] a, double[][] b)1.2. Modify the following method in the sample code to Implement a matrix multiplication in parallel: public static double[][] parallelMultiplyMatrix(double[][] a, double[][] b) Explain the parallel tasks defined in your code.1.3. Add a method to the source code that measures the execution time for both sequential and parallel matrix multiplication.1.4. Vary the number of threads being used by the parallel method for matrix sizes of 2000 by 2000 and plot the execution time as a function of the number of threads.1.5. Vary the size of the matrices being multiplied as (100 by 100, 200 by 200, 500 by 500, 1000 by 1000, 2000 by 2000, 3000 by 3000, 4000 by 4000) and plot the execution time as a function of matrix size for both parallel and sequential methods in one figure. Use the number of threads for which the parallel execution time in 1.4 is minimum.1.6. For the generated graphs in 1.4 and 1.5 comment on their shape and possible reasons for the observed behavior.2. (8 marks) Write a program that demonstrates deadlock. 2.1. Explain under what conditions deadlock could occur and comment on its possible consequences. 2.2. Discuss possible design solutions to avoid deadlock.3. (16 marks) The original dining philosophers problem was invented by E. W. Dijkstra, a concurrency pioneer, to clarify the notions of deadlock- and starvation-freedom. Imagine five philosophers who spend their days just thinking and feasting on sushi. They sit around a circular table with five chairs. The table has a big plate of sushi in the center; however, due tocurrent dining restrictions, there are only five chopsticks available, as shown in Fig. 1. Each philosopher thinks. When she/he gets hungry, they pick up the two chopsticks closest to them. If a philosopher can pick up both chopsticks, they can eat for a while. After a philosopher finishes eating, they put down the chopsticks and start to think again.Figure 1 3.1. Modify the class public class DiningPhilosophers in the sample code to simulate the behavior of the philosophers for any number n of them, where each philosopher is a thread, and the chopsticks are shared objects. Notice that you must prevent a situation where two philosophers hold the same chopstick at the same time. Notice that in this program philosophers should be eventually deadlocked.3.2. Amend your program so that it never reaches a state where philosophers are deadlocked, that is, it is never the case that each philosopher holds one chop- stick and is stuck waiting for another to get the second chopstick. Explain your solution to avoid deadlock. 3.3. Amend your program so that no philosopher ever starves. Explain your solution to avoid starvation.4. (12 marks) Use Amdahl’s law to answer the following questions: 4.1. Suppose the sequential part of a program accounts for 40% of the program’s execution time on a single processor. Find a limit for the overall speedup that can be achieved by running the program on an n-processor machine.4.2. Now suppose the sequential part accounts for 30% of the program’s computation time. Let sn be the program’s speedup on n processors, assuming the rest of the program is perfectly parallelizable. Your boss tells you to double this speedup: the revised program should have speedup s′n > sn*2. You advertise for a programmer to replace the sequential part with an improved version that decreases the sequential time percentage by a factor of k. What value of k should you require?4.3. Suppose the sequential time percentage could be decreased 3-fold, and when we do so, the modified program takes half the time of the original on n processors. What fraction of the overall execution time did the sequential part account for? Express your answer as a function of n.You may assume that the program, when executed sequentially, takes unit time. Total: 60 marks
1. Load and Convert Image to Grayscale: path = ‘/content/drive/Mydrive/Assignment_x/images/’ image = cv2.imread(path + ‘img1.png’)Read the image ./images/mcgill_arts_building.jpg and convert it to grayscale using an appropriate image processing library.2. Compute Image Derivatives: Calculate the image derivatives and in both the x and y directions using Sobel filters or another derivative method. Compute the products of the derivatives: , , and .3. Apply Gaussian Filtering: Smooth the derivative products , , and using Gaussian filtering to reduce noise.4. Compute the Corner Response: For each pixel, calculate the corner response function using the formula: where is the second moment matrix formed from the smoothed derivative products, and .5. Non-Maximum Suppression: Perform non-maximum suppression on the corner response map to identify potential corner points by keeping only the local maxima.6. Detect and Mark Corners: Apply a threshold to the corner response map, and mark the local maxima that exceed the threshold as detected corners. Overlay the detected corners on the original image for visualization, similar to the example shown in the demo.7. Experiment with Thresholds: Experiment with different threshold values to control the sensitivity of corner detection. Summarize your findings on the effect of varying thresholds in a markdown cell.2.1 SIFT Keypoint Matching Between Two Images 1. Compute SIFT Keypoints and Descriptors: Detect SIFT keypoints and compute descriptors for the images ./images/graf1.png and ./images/graf2.png . 2. Match Keypoints: Use a brute-force matching method to find correspondences between the keypoints of both images.3. Sort Matches by Distance: Sort the matched keypoints in ascending order based on their matching distance. 4. Display the Top Ten Matches: Visualize the top ten matched keypoints, overlaying them on both images.5. Plot the Matching Distances for the Top 100 Matches: Create a plot with keypoint indices on the x-axis and their corresponding matching distances on the y-axis to visualize the distribution of matching distances.2.2 Scale Invariance 1. Compute SIFT Keypoints for the Original Image: Detect the SIFT keypoints and compute their descriptors for ./images/graf1.png . 2. Scale the Original Image: Create 4 scaled versions of ./images/graf1.png using scaling factors of 0.25, 0.6, 3, and 5. Display each of the scaled images.3. Compute SIFT Keypoints for the Scaled Images: For each scaled image, compute the SIFT keypoints and their descriptors. 4. Match Keypoints: Perform brute-force matching between the keypoints of the original image ( ./images/graf1.png ) and each of the scaled images.5. Sort Matches by Distance: For each pair of images (original vs. scaled), sort the matches according to the matching distance.6. Display the Top Ten Matches: Visualize the top ten matches between the original and each scaled image. 7. Plot the Matching Distances: For each pair, plot the matching distance for the top 100 keypoints, using the keypoint index on the x-axis and matching distance on the y-axis.8. Discuss Trends: Analyze the results and discuss how increasing the scale affects the matching distances. 2.3 Rotation Invariance 1. Rotate Image: Rotate ./images/graf1.png by the following angles: 30°, 75°, 90°, and 180°. Display the four rotated images.2. Compute SIFT Keypoints for Rotated Images: For each of the four rotated images, compute SIFT keypoints and descriptors.3. Match Keypoints: Use a brute-force matching method to match the keypoints of the original image ( ./images/graf1.png ) to each of the rotated images.4. Sort Matches by Distance: Sort the matched keypoints for each image pair based on the matching distance in ascending order.5. Display the Top Ten Matches: Visualize the top ten matched keypoints for each image pair (original vs. rotated). 6. Plot the Matching Distances for the Top 100 Matches: Create a plot showing the matching distance for the top 100 keypoints, with keypoint indices on the x-axis and corresponding matching distances on the y-axis.7. Discuss Trends: Analyze how increasing the angle of rotation affects the matching distances. Explain the trends observed in the plot. 2.4 Repeat 2.1-2.3 using the image pair you obtained from assignment 1.You are given three different views of the same scene located in the folder ./images/Q3 . Follow these steps to stitch the images together: 1. Keypoint Detection and Matching: a. Compute SIFT keypoints and descriptors for images 1 and 2. b. Match the keypoints between images 1 and 2. Display the 20 best matching pairs.2. Homography Estimation and Transformation: a. Use the RANSAC method to compute the homography matrix that aligns keypoints from image 1 to image 2. b. Apply the computed homography to transform image 1. Image 2 should remain unchanged.3. Image Stitching: a. Stitch the transformed image 1 with the original image 2. For better visualization, average the pixel intensity in the overlap region so that you can see patterns from both images. Name this result image_12 . Display image_12 .4. Repeat the Process for Image 3: a. Compute SIFT keypoints and descriptors for image_12 and image 3. b. Match the keypoints between image_12 and image 3. Display the 20 best matching pairs. c. Compute the homography using RANSAC to align keypoints from image_12 to image 3. Apply this homography to transform image 3. Image image_12 should remain unchanged.5. Final Stitching: a. Stitch the transformed image 3 with image_12 . Also average the pixel intensity in the overlap region. Display the final stitched image.
Using a cellphone camera or a standalone digital camera, capture two images of a household object, where each image of the object is taken from a slightly different viewpoint. These images can be of any size. An example of such an image pair is shown below:Please note that all assignments are to be done individually (not in groups), and so you must acquire your own images. Do not share images or copy someone else’s images! You will be using these images, as well as the processed images, in some future assignments, so it is important to do all the steps correctly. Display the original images in the assignment’s Jupyter notebook.If your images are color (RGB), convert them to grayscale (monochrome) by using the python statement: gray = np.dot(your_image[…,:3], [0.2989, 0.5870, 0.1140]) In your notebook explain what this python statement does. Display the grayscale images in the assignment’s Jupyter notebook. Use the resize() function of scikit-image to resize your image so that the largest dimension has a size of 256 pixels. A tutorial on how to use the resize function can be found at: https://scikit-image.org/docs/stable/auto_examples/transform/plot_rescale.htmlWrite python code that can perform convolution on an image with a specific filter kernel. Using the convolution code, smooth the pair of resized grayscale images using a 5×5 pixel Gaussian kernel. Then repeat the smoothing on the original grayscale images, this time using a 15×15 Gaussian kernel. Display the smoothed images in the notebook. Also show in the notebook the kernel values (either as an array of numbers or as an image).Using your convolution code, compute the x and y derivative images of each of the smoothed images using the horizontal and vertical Sobel filters. Display the derivative images in the notebook.With python, compute the edge gradient magnitude and orientation of the smoothed images using the Sobel filter values computed in part 5. Display the magnitude and orientation images in the notebook.For the orientation image, display the angle value using an RGB colormap, such as ‘jet’ in the imshow() function (e.g. something like ax.imshow(data, cmap=’jet’) ).Details about matplotlib colormaps, including other colormaps you can try, can be found at: https://matplotlib.org/stable/tutorials/colors/colormaps.html
In this section, you are going to train models on the publicly available CIFAR-10 dataset source. The CIFAR-10 dataset consists of 60000 32×32 color images in 10 classes, with 6000 images per class. For more information, you are encouraged to look at their webpage. You are expected to implement a Convolution Neural Network (CNN) to classify the images based on their context. Free T4 GPU in Colab is highly recommended for executing the code in this section.1. Implement a shallow CNN with the layers mentioned below. • A Convolution layer with 32 kernels of size 3×3 • A ReLU activation • A Convolution layer with 64 kernels of size 3×3 • A ReLU activation • A maxpool layer with kernels size of 2×2• A convolution layer with 64 kernels of size 3×3 • A ReLU activation • A convolution layer with 64 kernels of size 3×3 • A ReLU activation • A flattening layer. (This layer resizes a 3D tensor to a feature vector). • A fully connected layer with an output size of 10. (Classes should be predicted as numerical values (like 0-9). Note: If you use Pytorch, you can use print(next(model.parameters()).device) to check if you’re using the GPU for training.2. Use Pytorch Class torchvision.datasets.CIFAR10 to load the dataset. 3. Training, validation and test settings are shown below. • 50,000 images for training (training set). Divide the 10,000 test set images of CIFAR10 into two subsets by 1:1. 5,000 images for validation (validation set), and 5,000 images for final testing (test set).• Batch size = 32. • SGD optimizer with an initial learning rate of 0.002. • Loss function: categorical cross entropy criterion.• Training iteration can be 90,000 or more (If you use epoch counting, epoch can be 58 or more). Perform a validation every 5000 iterations (3 epochs). It may take about 30 minutes on T4 GPU. If you don’t have enough computational resources, you are allowed to reduce the number of images by taking a subset of this dataset or reduce the training iterations (epochs). State the size of your subset and iterations (epochs) in the README.• Use the default setting for the rest of the hyperparameters.4. Plot the training loss, validation loss, and validation accuracy over the training iterations (or epochs). Fig. 1 shows an example. State whether the training appears to be overfitting and why. 3/3 Fig. 1. Training loss, validation loss, and validation accuracy over the training iterations. 5. Please give the test accuracy on the test set from the iteration (or epoch) where the validation accuracy is maximum as your test accuracy result.6. Let’s discuss the effects of the Kernel size. Change all kernel sizes to 5×5 and train a new network with the same other hyperparameters. Compare the run time and the test accuracy of models under different kernel sizes and briefly discuss the possible factors that affect the performance of a CNN.7. Use Pytorch Class torchvision.models.resnet18 to implement a deep network ResNet18. Set the training iteration as 6000 or more (If you use epoch counting, epoch can be 5 or more) and perform a validation on the validation set every 500 iterations (1 epoch). Give the test accuracy on the test set from the iteration (or epoch) where the validation accuracy is maximum as the test accuracy result. The rest of the hyperparameters should be the same as the above shallow CNN. Note that:7.1 By setting the parameter pretrained, you can choose to either train a new ResNet18 model from scratch or fine-tune the ResNet18 model that has been fully trained on the ImageNet dataset.7.2 Since the image size of CIFAR10 is 32×32 and the standard ResNet18 accepts 224×224 input by default, we may need to first resize the input image to 224×224 (You are free to use other available transformation, such as padding). Besides, the output channel of the final fully connected layer of ResNet18 needs to be modified to 10 to meet the classification requirements of CIFAR10. Compare the impact of using a pre-trained ResNet18 versus not and discuss the reason. Compare the test accuracy of the deep ResNet18 versus the shallow CNN.YOLOv8 is a state-of-the-art (SOTA) model for a wide range of object detection and tracking, instance segmentation, image classification and pose estimation tasks. In this section, you will be asked to take a photo of a street in Montreal and summarize the information in this image by using a trained YOLOv8 model. This section does not ask to implement and train the model from scratch.You can use a well-trained YOLOv8 model from its official implementation. 1. Use your cellphone or a digital camera to capture a street scene in Montréal. 2. Implement the trained YOLOv8 object detection model to identify what are the types of objects included in the image (such as person, bicycle, vehicle, tree) and count the number of each object. 3. Display the original and predicted images in your notebook.
In this section, we will ask you to train Classifiers on the CIFIAR10 dataset. The CIFIAR10 dataset contains 60000 32×32 images. Ten classes are included, with 6000 images per class in it. Further information can be found on the dataset webpage https://www.cs.toronto.edu/ kriz/cifar.html. GPU is highly recommended for running code in this section.1. Resize the train/test images to 64×64 and convert them to grayscale images. Compute HoG features with cells of 8×8 pixels, blocks of 4×4 cells, and 4 bins. This should generate a feature vector of size 1600 per image, which can be regarded as features for training classifiers.2. Fit a non-linear SVM classifier with default hyperparameters on the features and the class features of the training images.3. Predict labels of the test images by feeding the test features to the trained classifier and calculate classification accuracy.4. Tune values of hyperparameters ’gamma’ and ’C’ to observe the accuracy change and select the hyperparameters with the highest test accuracy. Display your fine-tuning process by listing all the test cases with their parameter and corresponding accuracy.5. Fit a Random Forest(RF) classifier (set n_estimators=10, max_depth=5, and criterion=’entropy’) on the features and the class labels of the training images. 6. Predict labels of the test images by feeding the test features to the trained classifier and calculate classification accuracy.7. Compare the performance of SVM and RF. Experiment training both classifiers with a range of random states(different values for random_state). Evaluate the stability within the random state. List the strengths and weaknesses of each model.In this section, you will work on face detection. To achieve this purpose, you are required to compute EigenFaces and use the Viola-Jones detector to identify faces. We have provided a subset from CelebA(1) face dataset under the folder Q2 part1. The subset contains 100 color images. Figure 1: Sample images from CelebA dataset.1. Read this subset into the code environment and convert all images into grayscale. 2. Implement the Snapshot method for PCA (covered in Lecture 8, Slide 55) from scratch using Numpy. Display the first five face images.3. Use a sliding window method to detect faces in the image??, which is named Person.png under folder Q2 part2. Use the result from the previous step to compute the distance in the eignspace between the window contents and your training data.4. Set a threshold to detect faces and select the best-performed value. Show your fine-tuned process. 5. Label the detected images with bound boxes and display the final result image with labels.6. Use an existing implementation of the Viola-Jones face detector to detect faces on the same image. Compare the result with the method you implemented. 7. Evaluate your predicted result in both methods(True/False, Positive/Negative).8. Explain under what conditions the Viola-Jones detector works when PCA does not. Figure 2: Face Detection on Multi-person image.9. Evaluate the performance of this model and explain the steps that this network took to achieve the final result.References [1] LIU, Z., LUO, P., WANG, X., AND TANG, X. Deep learning face attributes in the wild. In Proceedings of International Conference on Computer Vision (ICCV) (December 2015).
For this part of the assignment, you will examine the workings of the Harris corner detector. Implement the Harris corner detector as described in class (Lecture 5, Slide 48, and Tutorial 2&3) mainly using NumPy , going through each of the described steps: 1. Compute the image derivatives (optionally, blur first). 2. Compute the square of the derivatives. 3. Apply Gaussian Filtering on the output of Step 2. 4. Compute the cornerness function response: Determinant(H) − kT race(H) 2 ), where k=0.05.5. Perform non-maximum suppression. Note 1: note that you can use OpenCV functions for gaussian filtering and computing image derivatives.Note 2: This question is worth 20 points: • 10 points for correct analysis and displaying desired outputs. • 10 points for correct, complete, and clean code.Note 3: You can access the images from: ‘data/Q1’ Apply the algorithm to three different images: 1. Checkerboard (Left part of Figure 1): Change the value of the threshold to attain detected corners that are similar to those in the right part of Figure 1. Observe and report the effect of changing the threshold values.2. Building image (Figure 2): Explore the different thresholds and report your observations. Figure 1: Checkerboard input image and the expected Harris corner detector output. (red dots represent the detected corners) (source) Figure 2: Federal Building in Port Huron, MI, US (source)Note 1: This question is worth 40 points: • 4 points for answering section 2.1 correctly. • 6 point for correct analysis and displaying desired outputs for section 2.2. • 10 points for correct analysis and displaying desired outputs for section 2.3. • 10 points for correct analysis and displaying desired outputs for section 2.4. • 10 points for correct, complete, and clean code.Note 2: For this question, you should utilize the pair of images that you captured in assignment 1. In this question, we are going to call them image_1 and image_2. Verify the invariance of SIFT features under changes in image scale and rotation. You are allowed to use inbuilt OpenCV/Scikit-Image functions for this question.Note 3: An instance of a brute-force method here could be computing Euclidean distances between all possible pairs of sift features in the two images.2.1 SIFT in a nutshell Briefly describe the 4 main actions/steps of the SIFT method. 2.2 SIFT between two different pictures 1. Compute SIFT keypoints for image_1 and image_2. 2. Match all keypoints between two images using a brute-force method. 3. Sort the matching keypoints according to the matching distance. 4. Display the top ten matched keypoints. 5. Plot the matching distance for the top 100 matched keypoints. Plot the indices of keypoints on the x-axis and the corresponding matching distance on the y-axis.2.3 Invariance Under Scale 1. Compute SIFT keypoints for the image_1. 2. Scale image_1 using scaling factors of (0.25, 0.6, 3, 5). This should result in a total of 4 different transformed images. Display scaled images. 3. Compute SIFT keypoints for all scaled images (total 4) transformed images.4. Match all keypoints of image_1 to the transformed images from the previous part using a brute-force method. 5. Sort the matching keypoints according to the matching distance.6. Display the top ten matched keypoints for each pair of the image_1 and a transformed image. 7. Plot the matching distance for the top 100 matched keypoints. Plot the indices of keypoints on the x-axis and the corresponding matching distance on the y-axis.8. Discuss the trend in the plotted results. What is the effect of increasing the scale on the matching distance? Explain.2.4 Invariance Under Rotation 1. Rotate image_1 at the angle of (30, 75, 90, 180). Display rotated images. 2. Compute SIFT keypoints for all (total 4) transformed images. 3. Match all keypoints of image_1 to the transformed images using a brute-force method.4. Sort the matching keypoints according to the matching distance. 5. Display the top ten matched keypoints for each pair of image_1 and a transformed image. 6. Plot the matching distance for the top 100 matched keypoints. Plot the indices of the key points on the x-axis and the corresponding matching distance on the y-axis.7. Discuss the trend in the plotted results. What is the effect of increasing the angle of rotation on the matching distance? Explain.You are given three different views of the same scene in a folder ‘data/Q3’ (Figure:3). Follow these steps in order to stitch given images: (a) Compute the SIFT keypoints and corresponding descriptors for images 1 and 2. (b) Find matching keypoints in images 1 and 2 and display the 20 best pairs.(c) Find the homography that best matches the keypoints from image 1 and 2 using the RANSAC method, and apply the resulting transformation to image 1. Image 2 should not be transformed.(d) Stitch the transformed image 1 and the original image 2 together using linear image blending. Let us call this image 12. Display this image. (e) Compute the SIFT keypoints and corresponding descriptors for images 12 and 3.(f) Find the matching keypoints in 12 and 3 images and display the 20 best pairs. (g) Compute the homography using the RANSAC method. Apply the transformation to image 3. Image 12 should not be transformed.(h) Stitch the transformed image 3 and image 12 together using linear image blending. Display the resulting image. (i) Discuss: Note that we could also use multi-band blending in the section (h). When should one prefer pyramid blending over linear blending? Hint: Here is a short introduction to image blending. Figure 3: Scenery to Stitch.
Using a cellphone camera or a standalone digital camera, capture two images of a household object, where each image of the object is taken from a different viewpoint. These images can be of any size. An example of such an image pair is shown below:Please note that all assignments are to be done individually (not in groups), and so you must acquire your own images. Do not share images or copy someone else’s images! You will be using these images, as well as the processed images, in some future assignments, so it is important to do all the steps correctly. Display the original images in the assignment’s Jupyter notebook.If your images are color (RGB), convert them to Grayscale, by averaging each pixel’s R, G, and B values. Display the grayscale images in the assignment’s Jupyter notebook.Smooth the pair of grayscale images using a 5×5 pixel Gaussian kernel. Then repeat the smoothing on the original grayscale images, this time using a 11×11 Gaussian kernel. Display the smoothed images in the notebook.Compute the x and y derivative images of the smoothed images using the horizontal and vertical Sobel filters. Display the derivative images in the notebook.Compute the edge gradient magnitude and orientation of the smoothed images using the Sobel filter values. Display the magnitude and orientation images in the notebook. For the orientation image, display the angle value using an RGB colormap, such as ‘jet’ in the imshow() function (e.g. something like ax.imshow(data, cmap=’jet’) ). Details about matplotlib colormaps, including other colormaps you can try, can be found at: https://matplotlib.org/stable/tutorials/colors/colormaps.htmlSetup opencv in your colab or home computer environment (go to the Tutorial to learn how to do this). Use the Canny edge detector implementation in opencv to compute the Canny edge detector on your smoothed images. (look at https://docs.opencv.org/3.4/da/d22/tutorial_py_canny.html for details). Plot the Canny detector output images in the notebook.
