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 2ドルs+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.
-
$\begingroup$ 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 ... $\endgroup$babou– babou2015年07月18日 11:46:15 +00:00Commented Jul 18, 2015 at 11:46
-
1$\begingroup$ 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. $\endgroup$babou– babou2015年07月18日 11:56:54 +00:00Commented Jul 18, 2015 at 11:56
-
1$\begingroup$ Step 1: write down your algorithm in pseudocode. Step 2: see our reference question. $\endgroup$Raphael– Raphael2015年07月18日 13:29:35 +00:00Commented Jul 18, 2015 at 13:29
-
$\begingroup$ @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 ... $\endgroup$user35624– user356242015年07月18日 14:42:42 +00:00Commented Jul 18, 2015 at 14:42
-
$\begingroup$ @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. $\endgroup$babou– babou2015年07月18日 14:47:59 +00:00Commented Jul 18, 2015 at 14:47
1 Answer 1
We need to estimate how many times block operation is performed.
- 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.
- 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)$.
-
$\begingroup$ What do you mean by " If S will be big enough (e.g. S=O(B))". In what way does S=O(B) imply that S is big, and how big would that be. $\endgroup$babou– babou2015年07月18日 14:18:28 +00:00Commented Jul 18, 2015 at 14:18
-
$\begingroup$ I updated the algorithm with more details, please feel free to update your answer in case ... UPVOTE ! $\endgroup$user35624– user356242015年07月18日 14:59:45 +00:00Commented Jul 18, 2015 at 14:59
-
$\begingroup$ @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)$ $\endgroup$knok16– knok162015年07月19日 11:07:50 +00:00Commented Jul 19, 2015 at 11:07
-
$\begingroup$ Your sentence was meaningless for several reasons. The first is That you stated S=O(B). That is verified even when S is constant independent of O(B), though, in that case, complexity grows as B². @D.W. took care of that by writing instead S=Θ(B). But even then there is an arbitrary factor between S and B. What matters is the ratio between S/B, which must be constant, not the size of S in an absolute sense. You should not write "e.g. S=O(B)" but rather "i.e. S=O(B)". It is not an example, but a requirement. S must be bis enough in proportion to B. - not theori vs implementation - just clarity. $\endgroup$babou– babou2015年07月19日 15:01:13 +00:00Commented Jul 19, 2015 at 15:01
-
$\begingroup$ I am still suggesting that you improve that sentence. $\endgroup$babou– babou2015年07月19日 15:05:55 +00:00Commented Jul 19, 2015 at 15:05