Objectives

• manipulating 2-d arrays
• preparation for assignment 1

Preparation

Getting Started

Create a new directory for this lab called lab07 by typing:

mkdir lab07

cd lab07

Practice Session In Exam envionment

Your tutor will set up the exam environment and tell you what to do.

This is not worth any marks but is a valuable chance to prepare!

Introduction

You can use these functions for the assignment (make sure you include a comment acknowledging your lab partner's contribution). Solutions for these functions will also be made available after the lab deadline and you are permitted to use these for the assignment (again with a comment indicating the authorship of the functions).

First you will need image files to test the functions you write in this week's lab.

If you are working at CSE you can link the directory containing all the digit images into your current directory using a command like this:

ln -s ~cs1511/public_html/assignments/captcha/digit .

It can be helpful to also have simpler and smaller images to test your code on.

Fortunately it is very easy to create images in the PBM format used for the assignment

Use gedit or another editor to create a file named 9.pbm with these contents:

P1
20 20
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000001111100000
00000000111111110000
00000001110001110000
00000011100001110000
00000011100001110000
00000111000001110000
00000111000001110000
00000111000011110000
00000011111111100000
00000001111111100000
00000000000111100000
00000000000111000000
00000111001110000000
00000111111100000000
00000011110000000000
00000000000000000000

You are given with the assignment read_pbm.c which contains contains C functions to read portable bitmap format (PBM) files.

If you are working at CSE you can copy read_pbm.c with a command like this:

cp ~cs1511/public_html/assignments/captcha/read_pbm.c .

read_pbm.c contains 2 important functions:

int read_pbm(char filename[], int height, int width, int pixels[height][width]);
int get_pbm_dimensions(char filename[], int *height, int *width);

get_pbm_dimensions extracts the height and width of a PBM image file. We need to know height and width so we can declare an array to hold the image pixels.

We pass this array to read_pbm and it sets the array elements to 1 if the corresponding pixels is black otherwise it set the element to 0.

Its important to understand how the elements of the array correspond to pixels in the image. For example here is how the image in 9.pbm corresponds to array elements.

Header File

You will place each function in a separate file so you also can use them in the programs you create for the assignment, so you will need a header file.

Create a file named captcha.h with these contents:

int read_pbm(char filename[], int height, int width, int pixels[height][width]);
int get_pbm_dimensions(char filename[], int *height, int *width);
void print_image(int height, int width, int pixels[height][width]);
void get_bounding_box(int height, int width, int pixels[height][width],
                  int *start_row, int *start_column, int *box_height, int *box_width);
void copy_pixels(int height, int width, int pixels[height][width],
                 int start_row, int start_column, int copy_height, int copy_width,
                 int copy[copy_height][copy_width]);
double get_horizontal_balance(int height, int width, int pixels[height][width]);

Exercise: Print Image

void print_image(int height, int width, int pixels[height][width]);

print_image should print the image using '.' for white pixels and '*' for black characters.

Do not add a main function to print_image.c. You will want to use print_image.c in other programs which already have main functions.

Create a separate file test_print_image.c with these contents:

#include <stdio.h>
#include "captcha.h"

int main(int argc, char *argv[]) {
    int height, width;

    if (argc < 2) {
        fprintf(stderr, "Usage: %s <image-file>\n", argv[0]);
        return 1;
    }

    // first get image dimensions
    if (get_pbm_dimensions(argv[1], &height, &width) != 1) {
        return 1;
    }

    // now declare appropriate array
    int pixels[height][width];
    if (read_pbm(argv[1], height, width, pixels)) {
        print_image(height, width, pixels);
    }
    return 0;
}

Compile print_image.c with print_image_test.c and read_pbm.c and test it:

dcc print_image.c read_pbm.c test_print_image.c -o test_print_image
./test_print_image 9.pbm
....................
....................
....................
....................
..........*****.....
........********....
.......***...***....
......***....***....
......***....***....
.....***.....***....
.....***.....***....
.....***....****....
......*********.....
.......********.....
...........****.....
...........***......
.....***..***.......
.....*******........
......****..........
....................

./test_print_image digit/3_42.pbm

 ~cs1511/bin/autotest lab07 print_image.c

// written by andrewt@unsw.edu.au April 2017
// as COMP1511 sample solution

#include <stdio.h>
#include "captcha.h"

// print a monochrome image to stdout
void print_image(int height, int width, int image[height][width]) {

    // need to print rows in reverse order
    for (int row = height - 1; row >= 0; row--) {
        for (int column = 0; column < width; column++) {
            if (image[row][column] == 1) {
                printf("*");
            } else {
                printf(".");
            }
        }
        printf("\n");
    }
}

Exercise: Bounding Box

Create a file named bounding_box.c which includes captcha.h and defines a function get_bounding_box with exactly this signature:

void get_bounding_box(int height, int width, int pixels[height][width],
                  int *start_row, int *start_column, int *box_height, int *box_width);

get_bounding_box should find the minimum rectangle (bounding box) enclosing the black pixels of the image and then set the variables pointed to by start_row and start_column to the bottom left-hand corner of the rectangle and set the variables pointed to by box_height and box_width to the height and width of the rectangle.

For example here is the bounding box of 9.pbm:

Do not add a main function to bounding_box.c. You will want to use bounding_box.c in other programs which already have main functions.

Create a separate file test_bounding_box.c with these contents:

#include <stdio.h>
#include "captcha.h"

void analyze_image(int height, int width, int pixels[height][width]);

int main(int argc, char *argv[]) {
    int height, width;

    if (argc < 2) {
        fprintf(stderr, "Usage: %s <image-file>\n", argv[0]);
        return 1;
    }

    // first get image dimensions
    if (get_pbm_dimensions(argv[1], &height, &width) != 1) {
        return 1;
    }

    // now declare appropriate array
    int pixels[height][width];
    if (read_pbm(argv[1], height, width, pixels)) {
        analyze_image(height, width, pixels);
    }
    return 0;
}

void analyze_image(int height, int width, int pixels[height][width]) {
    int start_row, start_column, box_width, box_height;

    get_bounding_box(height, width, pixels, &start_row, &start_column, &box_height, &box_width);
    printf("Bounding box height %d pixels, width %d pixels\n", box_height, box_width);
    printf("Bounding box bottom left corner is row %d column %d\n", start_row, start_column);
}

Compile bounding_box.c with bounding_box_test.c and read_pbm.c and test it:

dcc bounding_box.c  read_pbm.c test_bounding_box.c -o test_bounding_box
./test_bounding_box 9.pbm
Bounding box height 15 pixels, width 11 pixels
Bounding box bottom left corner is row 1 column 5
./test_bounding_box digit/3_42.pbm
Bounding box height 37 pixels, width 25 pixels
Bounding box bottom left corner is row 15 column 13

As usual autotest is available to help you test your program.

 ~cs1511/bin/autotest lab07 bounding_box.c

#include "captcha.h"

// find minimum rectangle containing all black pixels in image
void get_bounding_box(int height, int width, int pixels[height][width], int *start_row, int *start_column, int *box_height, int *box_width) {
    int min_row = height - 1;
    int max_row = 0;
    int min_column = width - 1;
    int max_column = 0;
    for (int row = 0; row < height; row++) {
        for (int column = 0; column < width; column++) {
            if (pixels[row][column] == 1) {
                if (row < min_row) {
                    min_row = row;
                }
                if (row > max_row) {
                    max_row = row;
                }
                if (column < min_column) {
                    min_column = column;
                }
                if (column > max_column) {
                    max_column = column;
                }
            }
        }
    }
    if (min_row <= max_row) {
        *start_row = min_row;
        *box_height = max_row -  min_row + 1;
        *start_column = min_column;
        *box_width = max_column -  min_column + 1;
    } else {
        // no black pixels in image
        *start_row = 0;
        *box_height = 0;
        *start_column = 0;
        *box_width = 0;
    }
}

Exercise: Copy Pixels

Create a file named copy_pixels.c which includes captcha.h and defines a function copy_pixels with exactly this signature:

void copy_pixels(int height, int width, int pixels[height][width],
                 int start_row, int start_column, int copy_height, int copy_width,
                 int copy[copy_height][copy_width]);

copy_pixels should copy the rectangle of pixel values specified by start_row, start_column, copy_height and copy_width from the array pixels into the array copy.

start_row and start_column specify the bottom left corner of the rectangle

copy_height and copy_width specify the size of the rectangle.

Create a separate file test_copy_pixels.c with these contents:

#include <stdio.h>
#include "captcha.h"

void analyze_image(int height, int width, int pixels[height][width]);

int main(int argc, char *argv[]) {
    int height, width;

    if (argc < 2) {
        fprintf(stderr, "Usage: %s <image-file>\n", argv[0]);
        return 1;
    }

    // first get image dimensions
    if (get_pbm_dimensions(argv[1], &height, &width) != 1) {
        return 1;
    }

    // now declare appropriate array
    int pixels[height][width];
    if (read_pbm(argv[1], height, width, pixels)) {
        analyze_image(height, width, pixels);
    }
    return 0;
}

void analyze_image(int height, int width, int pixels[height][width]) {
    int start_row, start_column, box_width, box_height;

    get_bounding_box(height, width, pixels, &start_row, &start_column, &box_height, &box_width);
    int box_pixels[box_height][box_width];
    copy_pixels(height, width, pixels, start_row, start_column, box_height, box_width, box_pixels);

    print_image(box_height, box_width, box_pixels);
}

Compile copy_pixels.c with test_copy_pixels.c, bounding_box.c, read_pbm.c print_image.c and test it:

dcc copy_pixels.c bounding_box.c  read_pbm.c print_image.c test_copy_pixels.c -o test_copy_pixels
./test_copy_pixels 9.pbm
.....*****.
...********
..***...***
.***....***
.***....***
***.....***
***.....***
***....****
.*********.
..********.
......****.
......***..
***..***...
*******....
.****......

 ~cs1511/bin/autotest lab07 copy_pixels.c

// written by andrewt@unsw.edu.au April 2017
// as COMP1511 sample solution

#include <stdio.h>
#include "captcha.h"

// copy  rectangle of pixels specified by parameters start_row, start_column, copy_height, copy_width
// from array pixels to array copy

void copy_pixels(int height, int width, int pixels[height][width], int start_row, int start_column, int copy_height, int copy_width, int copy[copy_height][copy_width]) {
    for (int row = 0; row < copy_height; row++) {
        for (int column = 0; column < copy_width; column++) {
            copy[row][column] = pixels[start_row + row][start_column + column];
        }
    }
}

Exercise: Horizontal Balance

This is one dimension of what a physicist would call the image's centre of gravity

It is calculated like this:

horizontal_balance = (column_sum/n_black_pixels + 0.5)/width
    where
       column_sum = sum of the column indices of all black pixels
       n_black_pixels = number of black pixels
       width = image width

For example here is a small example image:

column_sum = 0 + 1 + 2 + 3 + 3 + 2 + 1 = 12
n_black_pixels = 7
width = 4
horizontal_balance = (12/7 + 0.5)/4 = 0.553571

Note, if an image is horizontally symmetric the horizontal_balance will be 0.5. So an '8' will tend to have a horizontal balance near '0.5'.

Similar a '3'will likely have a horizontal balance > '0.5' because it has more pixels on the right of an image.

Create a file named horizontal_balance.c which includes captcha.h and defines a function horizontal_balance with exactly this signature:

double get_horizontal_balance(int height, int width, int pixels[height][width]);

get_horizontal_balance should return the horizontal balance of the image as a double.

Create a separate file test_horizontal_balance.c with these contents:

#include <stdio.h>
#include "captcha.h"

int main(int argc, char *argv[]) {
    int height, width, start_row, start_column, box_width, box_height;
    double balance;

    if (argc < 2) {
        fprintf(stderr, "Usage: %s <image-file>\n", argv[0]);
        return 1;
    }

    if (get_pbm_dimensions(argv[1], &height, &width) != 1) {
        return 1;
    }

    int pixels[height][width];
    if (read_pbm(argv[1], height, width, pixels)) {
        get_bounding_box(height, width, pixels, &start_row, &start_column, &box_height, &box_width);

        int box_pixels[box_height][box_width];
        copy_pixels(height, width, pixels, start_row, start_column, box_height, box_width, box_pixels);

        balance = get_horizontal_balance(box_height, box_width, box_pixels);

        printf("Horizontal balance %.3lf\n", balance);
    }
    return 0;
}

Compile horizontal_balance.c with copy_pixels.c, bounding_box.c, read_pbm.c print_image.c and test it:

dcc horizontal_balance.c copy_pixels.c bounding_box.c read_pbm.c print_image.c test_horizontal_balance.c -o test_horizontal_balance
./test_horizontal_balance 9.pbm
Horizontal balance 0.523
 ./test_horizontal_balance digit/6_00.pbm
Horizontal balance 0.476

 ~cs1511/bin/autotest lab07 horizontal_balance.c

// written by andrewt@unsw.edu.au April 2017
// as COMP1511 sample solution

#include "captcha.h"

// find horizontal balance point (centre of gravity) of image

double get_horizontal_balance(int height, int width, int pixels[height][width]) {
    double column_sum = 0;
    int n_black_pixels = 0;
    for (int row = 0; row < height; row++) {
        for (int column = 0; column < width; column++) {
            if (pixels[row][column] == 1) {
                column_sum = column_sum + column;
                n_black_pixels = n_black_pixels + 1;
            }
        }
    }
    return (column_sum/n_black_pixels + 0.5)/width;
}

Exercise: Digit Cracking

Write a first version of crack_digit.c which works only for the digits '3' or '6'.

In other words assume the digit is '3' or '6'.

Use only the horizontal_balance function to determine whether the digit is '3' or '6'.

Unlike the previous exercises crack_digit.c should contain a main function.

Hint: test_horizontal_balance.c does almost what you need, so just change it a little.

dcc crack_digit.c horizontal_balance.c read_pbm.c bounding_box.c copy_pixels.c -o crack_digit
./crack_digit digit/6_50.pbm
6
./crack_digit digit/3_50.pbm
3

 ~cs1511/bin/autotest lab07 crack_digit.c

// written by andrewt@unsw.edu.au April 2017
// as COMP1511 sample solution
// identify digit in monochrome image

#include <stdio.h>
#include "captcha.h"

void analyze_image(int height, int width, int pixels[height][width]);
int identify_digit(double horizontal_balance);

int main(int argc, char *argv[]) {
    int height, width;

    if (argc < 2) {
        fprintf(stderr, "Usage: %s <image-file>\n", argv[0]);
        return 1;
    }

    // first get image dimensions
    if (get_pbm_dimensions(argv[1], &height, &width) != 1) {
        return 1;
    }

    // now declare appropriate array
    int pixels[height][width];
    if (read_pbm(argv[1], height, width, pixels)) {
        analyze_image(height, width, pixels);
    }
    return 0;
}

// extract digit bounding box from image
// determine attribute horizontal balance
// dand idientify digit

void analyze_image(int height, int width, int pixels[height][width]) {
    int start_row, start_column, box_width, box_height;

    get_bounding_box(height, width, pixels, &start_row, &start_column, &box_height, &box_width);

    int box_pixels[box_height][box_width];
    copy_pixels(height, width, pixels, start_row, start_column, box_height, box_width, box_pixels);

    double horizontal_balance = get_horizontal_balance(box_height, box_width, box_pixels);

    int digit = identify_digit(horizontal_balance);

    printf("%c\n", digit);
}

// identify digit based on horizontal balnce
// digit assumed to be either 3 or 6

int identify_digit(double horizontal_balance) {
    if (horizontal_balance < 0.513) {
        return '6';
    } else {
        return '3';
    }
}

Challenge Exercises

Submission/Assessment

give cs1511 lab07 print_image.c bounding_box.c copy_pixels.c horizontal_balance.c crack_digit.c

If you are working at home, you may find it more convenient to upload your work via give's web interface.

Remember the lab assessment guidelines - if you don't finish the exercises you can finish them in your own time, submit them by Monday 11:00am using give and ask your tutor to assess them at the start of the following lab.

Either or both members of a programming pair can submit the work (make sure each program lists both of you as authors in the header comment).