The present invention relates generally to security documents (e.g., banknotes, ID documents, certificates, packaging, etc.). One claim recites a security document including a security pattern provided thereon. The security pattern includes a line structure in which lines width or line spacing is adjusted to convey a predefined, machine-readable pattern in a frequency transform domain. Another claim recites a security document including a security pattern provided thereon. The security pattern is provided in the security document through modifications to a color provided on the security document. The security pattern conveys a predefined, machine-readable pattern in a frequency transform domain. Of course, additional combinations and claims are provided as well.