9 ms·
Image Kernels explained visually
- Isamu 10y agoI don't see image kernels compared to cellular automata, but that's what they are. We just don't iterate more than once or twice with a kernel, and the long-term evolution (stability, chaos, or more interesting dynamics) is not the concern here. That is to say, there is more to cellular automata than the GOL, and one bit per cell.
- cmrx64 10y agoI'd be interested to learn more about this! I'm completely outside image processing/machine learning/whatever this is, but articles about it really fascinate me.
- nealabq 10y agoGolly is a free game-of-life program you can play with: http://golly.sourceforge.net/ http://golly.sourceforge.net/ There's an active community searching-for/categorizing/discussing patterns in Conway's game-of-life (GOL) (and other cellular automata). Examples: http://conwaylife.com/forums/ http://conwaylife.com/forums/ http://pentadecathlon.com/lifenews/ http://pentadecathlon.com/lifenews/
- cmrx64 10y agoI know about GOL and other simple automata, I'm mostly curious about applications in image processing.
- corysama 10y agoHere's a classic article that blurs the lines between image processing and automata. Very sad that it seems offline today. https://web.archive.org/web/20160325174539/http://freespace.virgin.net/hugo.elias/graphics/x_water.htm https://web.archive.org/web/20160325174539/http://freespace....
- avyfain 10y agoThanks for this. I have been playing with CAs recently[1], and doing a lot of GIF rendering based on the Game of Life rules. This water rendering algorithm seems like a great next step for me to experiment with. [1] https://twitter.com/tweetgameoflife https://twitter.com/tweetgameoflife
- Isamu 10y agoYou might find this paper interesting: http://arxiv.org/abs/1407.7626 http://arxiv.org/abs/1407.7626 A Survey on Two Dimensional Cellular Automata and Its Application in Image Processing Parallel algorithms for solving any image processing task is a highly demanded approach in the modern world. Cellular Automata (CA) are the most common and simple models of parallel computation. So, CA has been successfully used in the domain of image processing for the last couple of years. This paper provides a survey of available literatures of some methodologies employed by different researchers to utilize the cellular automata for solving some important problems of image processing. The survey includes some important image processing tasks such as rotation, zooming, translation, segmentation, edge detection, compression and noise reduction of images. Finally, the experimental results of some methodologies are presented.
- protomok 10y agoOne way to get into image processing / computer vision would be to pick up an OpenCV book. I liked this book: https://www.amazon.ca/Practical-Introduction-Computer-Vision-OpenCV/dp/1118848454 https://www.amazon.ca/Practical-Introduction-Computer-Vision....
- thearn4 10y agoIt is a pretty good comparison - I implemented a fast GOL code in Python using FFT-based kernel convolution a few years back https://github.com/thearn/game-of-life https://github.com/thearn/game-of-life
- jpfed 10y agoImage kernels generalize very naturally to real values (so naturally that it hardly constitutes a generalization). CAs can be generalized but it seems less natural. The common element you are picking up on, I think, is [comonadic computation](http://blog.sigfpe.com/2006/12/evaluating-cellular-automata-is.html http://blog.sigfpe.com/2006/12/evaluating-cellular-automata-...).
- Isamu 10y agoCAs are already highly generalized, we are just conditioned to only think of the famous ones like the Game of Life. All you need for a CA is a space in which to map your cells (in an arbitrary number of dimensions, with an arbitrary mapping), some state for each cell (maybe a real, this is arbitrary) and some transition function to compute the next state of each cell from its current state and that of its "neighborhood" (which again is arbitrarily defined.)
- contravariant 10y agoThe problem is that CAs are too generalized. They don't have the kind of structure image kernels have (in particular, they aren't linear transformations).
- obashut0 10y agoJust wanted to add this is quoting the definition of CA as instances of dynamical systems. It is interesting to think about how a large number of filter passes would affect an image. Makes me wonder if there are very simple filters that create absolute chaos after a while (could an edge detector be one?).
- deleted 10y ago[deleted]
- anjc 10y agoNice site. This would've been very helpful to me in college when I was trying to get an intuitive grasp of Gaussian blurs and so on via the formulas.
- Kinnard 10y agoIn what context did you learn about Gaussian Blurs?
- guelo 10y agoHow are the kernels derived? Is it just an art where people play with the matrices to see their effects or is there well-understood math behind them?
- salehenrahman 10y agoThere is a well-understood math behind it. For blur, you can either do two things: - generate a matrix such that each element in the matrix is equal to 1 (e.g. averaging) - generate a matrix such that it represents the Gaussian distribution (you can use a 2D Gauss function) For edge detection, you essentially have "derivative", e.g. rate of change; the more abrupt the change, the brighter the resulting pixel, hence why edges are highlighted. A good convolution kernel for edge detection would be the Laplacian. For sharpness, it's pretty much the Laplacian Kernel + identity kernel.
- echelon 10y agoI never realized sharpness was identity + Laplacian, but that absolutely makes sense. Thanks!
- sforzando 10y agoAn example of a kernel that has a mathematical explanation for its values is the (discrete) Gaussian kernel, used to blur/smooth images: http://dev.theomader.com/gaussian-kernel-calculator/ http://dev.theomader.com/gaussian-kernel-calculator/ The values of the gaussian kernel matrix are determined by doing a discrete sampling of the gaussian function. You get to choose sigma (gaussian's standard deviation) and kernel size (spatial neighborhood of the kernel, ie how much of the surroundings that the kernel will examine). Another example is the Sobel operator, used to extract edges from images: https://en.wikipedia.org/wiki/Sobel_operator https://en.wikipedia.org/wiki/Sobel_operator The kernel matrix is the result of composing a gaussian smoothing with a spatial-differencing operation. Thus, the Sobel estimates edges from smoothed images. As for the sharpen kernel described in the post -- an intuitive explanation is that you want to accentuate differences in pixel intensities.
- mistercow 10y ago
- deleted 10y ago[deleted]
- besselheim 10y agoThe previous discussion has some good comments and links: https://news.ycombinator.com/item?id=8966785 https://news.ycombinator.com/item?id=8966785
- deleted 10y ago[deleted]
- kragen 10y agoThis is super cool but it's unfortunate that it clamps negative result values to black. It's probably worth mentioning that there are a lot of ways to implement convolution with a kernel, and the kernel can be of any size, not just 3×3. The explanation here shows how to implement the output-side algorithm nonrecursively; http://www.dspguide.com/ch6/3.htm http://www.dspguide.com/ch6/3.htm gives this for the one-dimensional case. But you can implement it on the input side instead (iterating over the input samples instead of the output samples), there are kernels that have a much more efficient recursive implementation (including zero-phase kernels using time-reversal), you can implement very large kernels if you can afford to do the convolution in the frequency domain, and there's a whole class of kernels that have efficient sparse filter cascade representations, including large Gaussians. (To say nothing of convolutions over other rings.)
- bpchaps 10y ago(Can't comment on much else, but just wanted to say thanks for the link. I just got an SDR and the link you sent looks incredibly useful for learning. Thanks!)
- pthreads 10y agoThanks for the DSP link. The book looks interesting.
- colejohnson66 10y ago> This is super cool but it's unfortunate that it clamps negative result values to black. Curious: What would a negative pixel look like? What use would that have?
- kragen 10y agoThe standard thing to do in these cases is to make zero be a medium gray, so that you can see negative output as well as positive. If you use one of the edge-detection filters, you'll see what I mean.
- hexane360 10y agoNo experience with this stuff, but it feels like you could do an abs(kernel) to extract some meaning from the negative value. Applying this to the "outline" kernel, it seems like white bordered by black would show up just as white as black bordered by white, with homogeneous kernels still showing up black.
- jomamaxx 10y agoMan we need more articles like this. So nice and clear. I've been working with images for 12 years and I was never sure exactly what 'sharpen' actually did ...
- jscardella 10y agoThis was an interesting article though I am not an image-o-phile. However, what I really like was the base site! I am a part time instructor for business students and I am teaching them about the power of visualization. This is an incredibly illustrative source that explains points well, and I'll be able to use it as a teaching tool! Thanks for the post!
- kixpanganiban 10y agoWish we had this when I was taking Discrete Math and Numerical Methods back in college. Really neat visualization!
- oyvkva 10y agoReally cool way to see how image kernels work.
- zk00006 10y agoBug: 3x3 blur kernel, e.g. [1 1 1; 1 1 1; 1 1 1], outputs white image.