Sparse Matrix Operations for Images

mediumFREENotationData StructuresCV: Introduction to Computer Vision

Implement sparse matrix operations for efficient image processing, in plain Python.

Many image operations produce sparse results (few non-zero values). Sparse representation saves memory and speeds up computation.

Sparse format (COO - Coordinate format):

Store only (row, col, value) for non-zero entries
Memory: O(nnz) instead of O(m×n)

Common sparse operations:

Conversion: dense ↔ sparse
Matrix-vector multiplication
Element access and modification

Output format (what the tests check):

to_sparse returns a tuple of three Python lists (rows, cols, values), with entries listed in row-major order (row by row, left to right within a row)
from_sparse returns a list of lists of size shape; positions not in the sparse lists hold the integer 0
sparse_multiply returns a Python list of length shape[0]

Applications in CV:

Graph-based segmentation (sparse affinity matrices)
Optical flow (sparse motion fields)
Feature matching (sparse correspondence matrices)

Example

Input

matrix = [[0, 0, 3],
          [0, 2, 0],
          [1, 0, 0]]

Output

rows=[0,1,2], cols=[2,1,0], values=[3,2,1]

Reasoning

Input: matrix is a $3 \times 3$ grid, a tiny mostly-black image: 9 entries, only 3 non-zero.
Row by row, left to right: row 0 has a $3$ in column 2, row 1 a $2$ in column 1, row 2 a $1$ in column 0. Each becomes a triple $(r, c, v)$ : $(0,2,3)$ , $(1,1,2)$ , $(2,0,1)$ .
Output: the triples split into three parallel lists, rows=[0,1,2], cols=[2,1,0], values=[3,2,1]; position $k$ in each list describes the same entry. Storage is $3 \cdot \text{nnz}$ numbers instead of $m \times n$ , a big saving for large, mostly-zero images.
Going back: with shape $(3, 3)$ , start from all zeros and put each $v$ at row $r$ , column $c$ ; the original grid reappears.
Times a vector: $y_r = \sum v \, x_c$ over the triples in row $r$ . With $x = [1, 2, 3]$ : $y_0 = 3 \cdot 3 = 9$ , $y_1 = 2 \cdot 2 = 4$ , $y_2 = 1 \cdot 1 = 1$ , so $y = [9, 4, 1]$ . Notice that zeros never contribute, so only stored entries matter.

Constraints

Implement: to_sparse(), from_sparse(), sparse_multiply()
to_sparse: Returns (rows, cols, values) for non-zero entries
from_sparse: Reconstructs dense matrix from sparse format
sparse_multiply: Sparse matrix × dense vector

More from CV: Introduction to Computer Vision

Multi-Scale Feature Pyramidhard Implement Prewitt Edge Detectorhard Connected Components Labelinghard K-Means Color Quantizationmedium Image Histogram Equalizationmedium

Concept primer

1. Background Knowledge (concepts & theory)

A grayscale image of size $H \times W$ can be seen as a matrix where each entry is a pixel value. Many CV operations (e.g., certain filters, masks, graphs over pixels) produce results where most entries are zero and only a small fraction are non-zero. Storing the full $H \times W$ dense matrix wastes memory and time, especially for high-resolution images.

A sparse matrix stores only the non-zero entries and their locations. In COO (Coordinate) format, we store three 1D arrays: row, col, and data, each of length nnz (number of non-zeros). Index k in these arrays tells you: there is a non-zero at (row[k], col[k]) with value data[k]. This reduces memory from $O(mn)$ to $O($ \text{nnz} $)$ , and many linear algebra operations in scipy.sparse are implemented to work efficiently in this form or in related formats (CSR, CSC).

In CV, representing things like affinity matrices for segmentation, sparse motion fields, or feature correspondence matrices as sparse helps scale to large images and video. Matrix–vector products, graph operations, and solving linear systems become much more tractable when the structure is sparse instead of dense.

2. Algorithm / Approach Pattern

For a problem like “Sparse Matrix Operations for Images” using scipy.sparse, the typical pattern is:

Start from a dense image (NumPy array).
Convert it to a sparse matrix (usually COO, CSR, or CSC).
Perform operations (e.g., matvec, indexing, updates) in sparse form using scipy.sparse APIs.
Convert back to dense if needed for visualization or further dense processing.

Common conversions and operations in SciPy:

from scipy.sparse import coo_matrix

# dense -> COO
A_coo = coo_matrix(A_dense)

# COO -> dense
A_dense2 = A_coo.toarray()

# matvec
y = A_coo @ x # x is a 1D or 2D NumPy array

# element access (may need format conversion, see pitfalls)
value = A_coo[row, col]

3. Step-by-Step Strategy

When asked to implement sparse matrix operations for images, you can think in terms of the following steps:

Represent the image as a dense matrix

Input: image as a NumPy array of shape (H, W) (or possibly (HW, HW) if it’s a graph/affinity matrix).

Create a COO sparse matrix

If starting from dense:

from scipy.sparse import coo_matrix

A_coo = coo_matrix(image) # zeros are skipped automatically

If you are given (row, col, data) directly:

A_coo = coo_matrix((data, (row, col)), shape=(m, n))

Implement conversion operations

Dense → sparse: coo_matrix(dense_array)
Sparse → dense: A_coo.toarray() (or .A for legacy shortcut).
Possibly support conversions to CSR/CSC for efficient arithmetic:

A_csr = A_coo.tocsr()

Matrix–vector multiplication

Given vector x (e.g., flattening an image or working with feature vectors):

y = A_coo @ x

For repeated multiplications, convert to CSR or CSC:

A_csr = A_coo.tocsr()
y = A_csr @ x

Element access

Simple reads:

val = A_csr[i, j] # CSR/CSC are efficient for access

For COO, direct indexing works but may be less efficient; if random access is needed a lot, use CSR/CSC.

Element modification

SciPy’s COO is not efficient for incremental writes. A common pattern:
Convert to LIL (List of Lists) for construction/editing:

A_lil = A_coo.tolil()
A_lil[i, j] = new_value
A_coo = A_lil.tocoo()

Or build from scratch using LIL or DOK, then convert to CSR/COO at the end.

Convert back to dense for output

After applying the sparse operation:

result_dense = A_csr.toarray()

4. Common Pitfalls

Using COO for frequent updates COO is good as an input/output format, but not for repeated modifications. Use LIL or DOK while building/updating, then convert to CSR/COO.
Inefficient element access patterns Repeated A[i, j] on COO can be slow. For random access, prefer CSR/CSC (for general matrices) or LIL (while constructing).
Forgetting shapes when building from (row, col, data) You must specify the correct shape=(m, n) or ensure row/col indices correctly fit the intended dimensions (e.g., image height/width).
Mismatched vector dimensions in matvec If A is shape (m, n), the vector must be length n for A @ x. When flattening images, pay attention to whether you use row-major (ravel() / reshape(-1)) and keep consistent ordering.
Converting very large sparse matrices to dense toarray() can explode memory for big images or large graph matrices. Only convert to dense when sizes are manageable.

5. Time & Space Complexity

Let:

$m, n$ be the matrix dimensions.
$\text{nnz}$ be the number of non-zero entries.
Storage (COO)
Arrays row, col, data: each length nnz.
Space: $O($ \text{nnz} $)$ vs $O(mn)$ for dense.
Dense → COO conversion
If built from a dense array: scan all $mn$ entries to find non-zeros.
Time: $O(mn)$ in worst case.
Space: $O($ \text{nnz} $)$ .
COO → dense conversion (toarray())
Allocate $mn$ and fill from nnz.
Time: $O(mn)$ to initialize + $O($ \text{nnz} $)$ to scatter.
Space: $O(mn)$ .
Matrix–vector multiplication (A @ x)
For sparse matrices, only non-zeros matter.
Time: $O($ \text{nnz} $)$ .
Space: $O(m)$ for the output vector.
Element access
CSR/CSC: roughly $O(\log($ \text{nnz} $_{$ \text{row} $}))$ or $O(1$ \text{–} $\log)$ average for access in a row/column.
COO: may be up to $O($ \text{nnz} $)$ if implemented as a simple scan.

Understanding these costs helps you justify why sparse representations are so beneficial for image-based problems where the majority of entries are zero, and guides you to choose the right format for each operation.

solution.py

Python 3.13

Test results