The present invention provides processes to encode substrates (e.g., paper, synthetics, etc.) with information, and substrates including signals encoded therein. One claim recites a substrate-making process including: obtaining an element to be utilized in a substrate-making process, the element including a property to introduce a texture pattern including an encoded signal into a substrate, the encoded signal being machine-detectable from image data corresponding to at least a portion of the texture pattern, the encoded signal including a variable component; and utilizing the element to impart the texture pattern into a substrate during the substrate-making process. Another claim recites a physical substrate including: a surface having a texture pattern provided in the surface during a substrate-making process. The texture pattern includes a machine-readable signal that is detectable from image data corresponding to at least a portion of the texture pattern. The signal includes a variable component that has discernable properties in a frequency domain. The texture pattern is provided in the surface during the substrate-marking process by a non-printing element. Of course, other claims and combinations are also provided.