0
$\begingroup$

i have a set of images that i need to send through an hourglass-type convolutional system.

I understand convolutions are shift-invariant, so i will ignore them

the question is then: If I downsample a signal by 2x, then upsample by 2x -- what constraints do i need to make sure the system is shift-invariant?

Improve this question
$\endgroup$
3
  • $\begingroup$ You need to ensure you don’t have aliasing in the downsampling step, meaning apply a low pass filter first. I think that is all you need, though I’m not sure. $\endgroup$
    – Cris Luengo
    Oct 30, 2021 at 3:03
  • $\begingroup$ Can you put constraints on the signal? $\endgroup$
    – TimWescott
    Oct 31, 2021 at 15:10
  • $\begingroup$ For downsampling only signals: if ratio of shift to subsampling is integer. For downsampling convolutions: if both inputs are bandlimited. Proven here. $\endgroup$
    – OverLordGoldDragon
    May 31 at 23:33

2 Answers 2

Reset to default
2
$\begingroup$

In theory, strictly, never.

In theory, if you mean effectively shift invariant, then yes, if you low-pass filter the signal so that it is strictly bandlimited to $\frac{1}{2} \mathrm{\frac{cycles}{pixel}}$, then downsample, then reconstruct through a $\frac{1}{2} \mathrm{\frac{cycles}{pixel}}$ filter.

In practice, such a filter won't work. In a processing context where you assume a signal is of infinite extent, you can -- in theory -- construct a perfect bandlimiting filter, but it has an infinitely long impulse response. This is kind of difficult to realize in practice*.

In the context of a 2D signal that is finite both vertically and horizontally, you could make a filter with the required properties. It would have two problems:

  1. The "infinitely long" character of the filter would turn into a high degree of bleeding of pixel values across the screen -- basically, with a finite field like this the edges of the screen appear mathematically** to butt against each other. So things happening in the right and left edges of the screen will bleed into each other. Ditto things happening in the top and bottom edges.
  2. Any real filtering process won't be perfect. So your original image, converted, and your original image shifted by one and converted won't be exactly the same but for the shift.

* But easy to fake -- just make a "filter" that always returns zero, and if anyone asks, tell them you're waiting for the impulse response to start up.

** Sorta kinda -- there's a lot of ways to look at this.

Improve this answer
$\endgroup$
1
  • $\begingroup$ thanks for the explanation, it makes sense, i will have to figure out a new way to think about this -- applying band-limited filters on dense inputs quickly $\endgroup$
    – Anatoly
    Nov 2, 2021 at 14:21
0
$\begingroup$

I understand convolutions are shift-invariant, so i will ignore them

and here lies your mistake!

counter-example:

input: $[0\, 1\, 0\, 1\, 0\, 1\, …]$

you then decimate by 2, convolve with a discrete filter of impulse response $[1 \, 1]$, and get constant zero or constant one, depending on whether your shift was even or off numbers of samples.

Remark

This is a special case of a signal that is insufficiently bandlimited (to be specific, this is a signal that has a frequency component at DC, and one at $f_{\text{sample}}/2$, and that second frequency is just an $\varepsilon$ too high) from Tim's excellent answer.

Improve this answer
$\endgroup$
1
  • $\begingroup$ i did get the "all even positions are equal" and same for odd answer from mathematica, just wanted to see if there's a less restrictive way to get the shift-invariance $\endgroup$
    – Anatoly
    Nov 2, 2021 at 14:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.