# How can I compute the time complexity of this image processing algorithm?

Well, my question is simple, I would like to compute the complexity time of an algorithm related to image processing.

I simplified the algorithm ... so that we focus only on the problematic part.

## Algorithm

You have an image/matrix of $N =n \times m$ size and a block of size $b \times b$ (block is just a window or rectangle that will slid through the picture of pixels or the matrix of intensities).

The algorithm goes through most pixels in the image (as center of the block, so it may step over the end of the line or the beginning) by a step of size $s$. The step is inferior to the size of the block $s<b$, so there is some overlapping (because some pixels are being considered in multiple blocks), and then it performs some operations with a complexity relative to the size $b$ equals $O(b^2)$.

Concretely, the algorithm starts in line $1$, and process blocks starting at $1, s+1, 2s+1, ...$ columns, then it goes to the $s+1$ line and do the same as on line $1$, then to $2s+1$ line and so on. Every iteration, the algorithm computes some operations related to the size of the block (which can be $3 \times3$ or $5 \times 5$, ... and $s$ is $1/8$ the $b$ for instance).

Any help, or reference related to this topic is a welcome.

• Welcome to Computer Science Stack Exchange. Since you do not address the question to image processing specialists, please be kind enough to explain the structure. What is a block? Why does it interfere with the stepping s. Is m a multiple of s? Can the stepping go over the line end, or does it necessarily begin at the beginning of each lines? etc ... – babou Jul 18 '15 at 11:46
• Have you tried to compute the nimber of times the algorithm iterates? That is a primary school problem. Given a floor of size $n\times m$, how many square tiles of size $s$ do you need to cover the floor. You multiply by the price of a tile, which is $b^2$ and you get the price of the whole tiling. – babou Jul 18 '15 at 11:56
• Step 1: write down your algorithm in pseudocode. Step 2: see our reference question. – Raphael Jul 18 '15 at 13:29
• @babou I will edit the question right now to answer your comments. BUT it is not a primary school problem, it is a research one, kind of simplified here ... – user35624 Jul 18 '15 at 14:42
• @OSryx Sorry for the quip. As the problem is stated, the number of step seems rather straightforward, and since you have the cost of each step, you only have to do the product. No I may hav missed a point ... I often do. My purpose is also to get people to improve the question. Asking questions is often harder than answering. – babou Jul 18 '15 at 14:47

1. First lets answer in how many rows we will start block processing - easy to see that each $S$ row are taken into account, so answer to this sub-question is $O(N/S)$. If we suppose that $N$ - number fo rows and $M$ number of columns.
2. Then we need answer to question - how many times we will run block processing for each row, due to we perform processing of blocks that starts only in each $S$ columns - answer for this sub-question will be $O(M/S)$.
Now we have that block processing will be performe $O(N*M/S^2)$ times for whole input. And result time-complexity for whole algorithm will be $O(N*M*B^2/S^2)$.
• @babou sorry, here I mixed a little to things: 1. "If S will be big enough" - relates to real implementation - so if $S=B-1$ or $S=B-2$ runnniong time should not differ for reading whole image from disk (or preparing somehow in other way). 2. $S=\Theta(B)$ relates to formal proof of complexity, e.g. if we say that $S$ is not constant but choosen based on B (for example $S=B/2$ - blocks is overflow in halves or $S=B/1000$ - blocks have small gap between each other) - we can say that resulting complexity is $O(N*M)$ – knok16 Jul 19 '15 at 11:07