9
$\begingroup$

Markov Chains can be used to generate, or auto-complete, text.

https://en.wikipedia.org/wiki/Markov_chain#Markov_text_generators

Training text is read, and some information about the text is remembered, for example:

The word "I" is usually followed by the word "have".
The word "to" is usually followed by the word "go", and somtimes the word "be".

etc...

This can be used to generate in text like:

A pride of related females and a key species sought for exhibition in the four big cats in breeding programs for ten years, as injuries sustained from continual fighting with rival males exceeding 250 kg (550 lb) in historic times. Until the Lascaux and medieval cultures where they may take to Peru.

Although, this is a lot less effective with many other types of texts.

Q: Can example images be shown, where an aproach similar to the use of Markov Chains to generate/auto-complete text, has been used to process images?

Alternatively, is this still unrealistically computationally expensive?

I was unable to find examples by searching, I may be lacking the correct vocabulary to do so.

Using Markov Chains like this could be very computationally expensive, a small 5x5 neighborhood, in monocrome image (black and white only, no shades of grey) has 2^(5^2) ≈ 33 million possible combinations.

Such processing could include: Inpainting, synthisis, improving resolution and and error correction/checking.

Examples of inpainting and synthisis, using other approaches:

Inpainting: Gaps in images being fixed.

inpainting example Other inpainting examples and information:

https://reference.wolfram.com/language/ref/Inpaint.html (click "open all").

Synthisis: For example Google Deep Dream, using convolutional neural networks and inceptionism.

synthisis example

Improve this question
$\endgroup$
2
  • $\begingroup$ Just FYI, I did some quick googling, and it looks like the original work on this topic is from 1979 in generating grayscale textures: sciencedirect.com/science/article/pii/0031320379900335 $\endgroup$
    – Jonno_FTW
    Commented Jan 16, 2017 at 2:14
  • $\begingroup$ Just a remark from a non-expert: I think the use of recurrent neural networks (as, e.g., in deep dream) for text/image/whatever generation is also based on the idea of considering the probability of neighboring elements in a similar sense as you explain. Let $w_i$, $i=1,\cdots,N$, be a sequence of words. In both cases $w_{j+1} = f(w_1,\cdots,w_j)$ where $f$ has some probabilistic component. In case of RNNs we sample $w_{j+1}$ from a posteriori distribution defined by the output of a neural network. In your case the probability distribution is just defined in a different way, $w_{j+1}=f(w_j)$. $\endgroup$
    – knl
    Commented Jan 17, 2017 at 10:44

2 Answers 2

Reset to default
11
$\begingroup$

I've implemented this recently, basically it counts how many times each specific colour borders another colour to make up a frequency table. To generate an image, a random colour and position are selected and the rest of the image is built up from there. Results aren't very coherent, but they match the colour palette of the original.

In order to make sure each colour has a neighbour, the colours are bucketed. You can modify this degree of information loss. You can also use 8 neighbours or 4 neighbours and also learn the direction of colours (top, left, right, bottom etc.).

At this time it only generates random images after learning from input images, the code is here: https://gist.github.com/JonnoFTW/5b036797593c5c40aabdf2d6c1399387

UPDATE: Full repository is here: https://github.com/JonnoFTW/markov-img-gen

It should be simple enough to try and make it fill in gaps in images, though I suspect the result would be nonsensical.

Here's some sample output: Sample Markov Based image

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ I love this! Yeet! $\endgroup$
    – duhaime
    Commented Apr 7, 2021 at 12:44
1
$\begingroup$

Blog post on an experimentation using Markov to recreate art: https://magenta.as/using-machine-learning-to-make-art-84df7d3bb911

Code is on github made by @william-index: https://github.com/william-index/markov-fun

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Welcome to scicomp.stackexchange! When you cite a link is good spend some lines to describe the content, in this way the answer is self contain and it does not depend by external link. $\endgroup$
    – Mauro Vanzetto
    Commented Dec 19, 2018 at 15:13

Your Answer

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

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