Methods, apparatus, software, and systems of the present invention allow for optimization of color and shades of gray documents prior to their conversion to a monochrome format. If color/gray elements are identified in the document, the distance between them and their intensity is determined. If there are elements with the same or similar intensity in close proximity to each other, colors of some of the elements may be replaced with solid monochrome colors, and/or dithered surfaces, and/or monochrome patterns. Further, the elements may be outlined. These improvements make elements in the document more distinguishable after its conversion to a monochrome format. The described color optimization and outlining may have wide applicability in the Internet Fax technology.