I've read that if we want to use images of different sizes in a convolutional neural network without resizing the images to a default size, we can use Fully Convolutional Neural Networks. But I do not see how they solve the issue of images of different sizes. In this video Andrew Ng explains how we can turn a fully connected layer into a fully convolutional layer, you can see the complete drawing which presents the idea at 3:45, if you don't want to watch the entire video. But with only this change we still couldn't use images of different sizes. The critical part is where Andrew transformed a $5$ x $5$ x $16$ volume into a $1$ x $1$ x $400$ volume using $400$ filters with size $5$ x $5$. But given an input image of a different size, this won't work anymore. If the input image will be larger, then the volume at that layer won't be $5$ x $5$ x $16$ anymore, and so the $5$ x $5$ filters won't turn the volume into a $1$ x $1$ x $400$ volume, and the rest of the neural network won't work anymore. So what do people mean when they say that a fully connected network can work with images of different sizes, since this fully connected network couldn't accept an image of a different size if we wanted to do that. What am I missing? I've tried to read the original Fully Convolutional Neural Networks paper, but I am not sure I understand it.
A fully convolutional network is independent of the number of pixels in the input if the output size is allowed to have a different number of pixels as well. This is due to the fact that the number of parameters in a convolutional layer is independent of the number of pixels in the input. However, the same convolution applied to images of different sizes, will produce outputs with different sizes. This scenario typically occurs in some sort of auto-encoder setup. After all, it is typically no problem if the size of the hidden representations is greater for large than for small images. E.g. for segmentation, as in the fully convolutional networks paper, or compression tasks.
To make a prediction network truly independent of the image size, you would typically use global average pooling at some point in the network. Global average pooling reduces all pixels to a single value by computing the average pixel value. This makes it possible to add fully-connected (or convolutional) layers with fixed dimensions to obtain the desired output size. However, this has nothing to do with fully convolutional networks per se.