Python代写｜Block Model Compression Algorithm

本次澳洲代写是一个Python压缩算法的assignment

Introduction

This project is presented as a gamified design and implementation challenge. You are required to develop and
submit either an .exe file or a Python script to a verification service. The program you deliver has to take
uncompressed input data on standard input and produce compressed output data on standard output with no
loss – see below for details. The verification service will execute your code and score it compared to all the
other entries received on processing speed and compression performance. The group that submits the best
performing program in each category at the end of the semester will win the competition in that category.

Multiple entries per group are encouraged and the service can be used for verification, bench-marking and
testing along the way. Can a well organised team employing cooperation and teamwork beat individual entries?

Algorithm Background

Images that do not contain many colours can be compressed by grouping neighbouring pixels into larger
‘parent’ pixels of the same colour, as can be seen in the first term of the sum below. Where this is not possible,
the remaining parent-sized regions, as shown in the last term, can be encoded as collections of rectangular
regions of uniform colour that pack to perfectly fill each region.

This technique is especially effective for low colour resolution images in 3D. Such structures are commonly
used to represent geological domains in the Earth’s crust and are known as block models. This project involves
developing algorithms for such compression on very large block models and can explore GPU as well as CPU
techniques.

Functional Requirements Detail

Input block models are provided as comma separated values (CSV) where each line encodes a block as a
string of the form “x, y, z, x_size, y_size, z_size, ‘domain’”:

1. x, y and z are integers representing the spatial origin of the block in the overall model
2. x_size, y_size and z_size represent the integer dimensions of the block
3. ‘domain’ is a string labelling the domain (equivalent to the pixel colour) of the block

{ Input streams will have x, y, and z monotonically increasing per row, column and slice respectively from 0 up
to but excluding x_count, y_count and z_count values respectively. These three counts specify the overall
dimensions of the block model and the parent sub-division size allowed in each dimension. These six integers
are given in a special header line of the form “# x_count, y_count, z_count, parent_x, parent_y, parent_z” as
the first line in the input stream. Complete rows are listed in succession within each column and complete
columns are listed in succession within each slice to completely describe the model. }

The algorithm is required to output a stream of the same format. To achieve compression, block sizes greater
than one up to the specified parent block size in x, y and z can be specified in the output. Such sub-blocks must
completely lie within boundaries defined by the parent blocks. Parent blocks always sub-divide the model
dimensions without remainder and the boundaries between parent blocks are fixed by this subdivision.

For example, consider the map of Australia above as a single slice at z=0 through a geological model – also
known as a block model. The input stream would contain every pixel starting from x=0, y=0 the bottom left
corner and going up to x=63, y=63 in the top right corner, 4096 lines in total. The 8×8 ‘salmon’ coloured parent
block (the area inside what would be South Australia), located at 32, 24, 0 would be described by 64 separate
lines in the input but could be described by a single line in the output, “32, 32, 0, 8, 8, 8, ‘salmon’”. The parent
region immediately below, however, is more complicated consisting of the ‘salmon’ and the ‘sea’ colours in an
irregular pattern. We can visualise this 8×8 region in the image below. One way of encoding it is shown by the
thick lines here: