Method of and apparatus for low-complexity detection of periodic textures orientation

A method includes calculating a Fourier transform of an image, extracting a plurality of arrays, from the Fourier transform utilizing, for each of the plurality of arrays, one of a plurality of templates each of said templates corresponding to a texture orientation, calculating a maximum value for each of the plurality of arrays, identifying each of the plurality of arrays having a calculated maximum value greater than a predetermined threshold and determining, for each of the plurality of identified arrays, the texture orientation of the template utilized to extract the identified one of the plurality of arrays.

BACKGROUND OF THE INVENTION

The performance of accurate texture detection and analysis is an important task when performing image analysis. Specifically, texture detection and analysis is utilized when detecting motion for use in frame interpolation for frame rate up-conversion, video surveillance, and the like. The performance of such analysis in real or near real time when dealing with video can require substantial computational resources.

There may therefore exist a need to provide a low-complexity solution to identifying texture orientations, particularly those which repeat with an identifiable periodicity.

DETAILED DESCRIPTION OF EXAMPLE EMBODIMENTS

In accordance with various exemplary embodiments described herein, there is provided a method for determining the orientation of periodic textures in images. There is additionally described a low-complexity solution for implementing the aforementioned method of texture orientation determination.

An image may contain periodic patterns where the color or intensity and shape of one or more texture elements are repeated at approximately equal intervals. With reference toFIGS. 1A-1Bthere are illustrated two exemplary images2,2′ showing a repeating pattern comprising, generally, a plurality of linear darkened lines repeating at approximately even intervals and oriented in approximate parallel fashion one to the other. As used herein, a “regular texture” refers to an image, perhaps forming a part of a larger image, that is comprised of at least one repeating or periodic pattern having different orientations.

With reference toFIGS. 2A-2B, there are illustrated the orientation vectors4,4′ corresponding to the textures illustrated inFIGS. 1A-1B. Each orientation vector4,4′ is a vector wherein the texture is repeated along the direction of the orientation vector4,4′.

In accordance with exemplary and non-limiting embodiments, an algorithm for texture orientation detection is based, at least in part, on the following two properties of regular (periodic) textures. First, a Fourier transform of regular textures contain one or more peaks. These peaks represent locations where the energy of the Fourier transform is concentrated. Second, the location of these peaks determines two features of a regular texture, specifically, the orientation and the period of the regular texture.

In accordance with an exemplary and non-limiting embodiment, texture orientation may be derived from each peak location using the following rule: the texture orientation, and hence the direction component of a corresponding orientation vector4, is parallel to line drawn through the origin point (0, 0), corresponding to the DC coefficient of the Fourier transform, and the point corresponding to the coordinates of the peak.

With reference toFIG. 3A, there is illustrated a perspective rendering of a Fourier transform of a regular texture. With reference toFIG. 3B, there is illustrated a gray scale rendering of the Fourier transform ofFIG. 3Awherein there is labeled a peak6, the DC coefficient8and the resultant derived orientation10. Note that a line drawn through the origin and perpendicular to the orientation operates as an axis of symmetry between pairs of related peaks. As a result, two orientation vectors4each starting at the origin and extending to each of a pair of related peaks would have a difference in direction of approximately 180 degrees. This results from the attribute that a regular texture may repeat in one of two directions effectively forwards or backwards along an orientation vector4. Lastly,FIG. 3Cillustrates orientation10superimposed upon the regular texture from which orientation10was derived. Note that, as used herein, “orientation10” is a line parallel to an orientation vector4and, as such, may be used interchangeably with “orientation vector4” where appropriate.

In accordance with an exemplary and non-limiting embodiment, a series of templates12are computed and stored wherein each template represents a unique and quantized orientation. Each template may be represented by an array, Tkij where k is the number of templates and i and j are the horizontal and vertical array dimensions of the Fourier transform. With reference toFIG. 4, there is illustrated a plurality of exemplary orientation angles12. In the present example, each orientation angle12differs from its closest neighbors by approximately thirty-three (33) degrees. In practice, any desired degree of resolution between orientation angles12may be realized by increasing the number of templates, Q, each corresponding to a unique orientation angle12as illustrated inFIG. 4.

With reference toFIG. 5, there is illustrated a plurality of templates14and the orientation10having an orientation angle12associated therewith where Q=8. As illustrated, each template is an array of values having dimensions corresponding to those of a Fourier transform with a line16extending from the center of the template14to a periphery of template14at an angle corresponding to an orientation angle12. In an exemplary embodiment, the values of each array element of each template12located in close proximity to line16have a value of one (1) with every other array element having a value of zero (0). As is evident, line16is parallel to the orientation10corresponding to each template14. As a result, as used herein, a template14, Tk (k=1, 2, . . . Q), may be referred to as possessing a corresponding orientation10where the corresponding orientation10is parallel to a unique one of the k orientation angles12.

With reference toFIG. 6, there is illustrated a flow diagram of an exemplary and non-limiting embodiment. In the following discussion, the following notation is used:

In accordance with an exemplary embodiment, a method receives as input an image comprising a regular texture and returns an array MAP={map1, map2, . . . , mapQ}:

For example, map1has a value of “1” if a regular texture having an orientation10corresponding to the orientation of the template14is present in input block B. In an exemplary embodiment, only half of Fourier transform F is utilized owing to the symmetric properties of the Fourier transform peaks described above.

First, at step1, a Fourier transform F of an image B is computed. In accordance with an exemplary embodiment, there is first performed DC cancellation on a block B identified as comprising at least one periodic texture to produce B′. This procedure is used to decrease the value of DC coefficients after the Fourier transform is performed and is applied to pixel values of block B before the Fourier transform is performed. In accordance with an exemplary embodiment there is first calculated the mean value of elements in the block B:

Next, the mean value is subtracted from the block elements:
B′i,j=Bi,j−mB

For example, for an exemplary 3×3 block:

In this example, the result of the Fourier transform output without DC offset cancellation is:

With the DC offset cancellation, the Fourier transform output is:

There is next calculated a Fourier transform F of block B′. In an exemplary embodiment, the size of the Fourier transform F equals the block size of block B′. An exemplary embodiment of this process is illustrated with reference toFIG. 7. With continued reference toFIG. 6, next, at step2, Q arrays of pixels, Ak, are extracted from the position of Fourier transform F specified by the masks Tk according to equation:
Ak={Fi,j:Fi,j×Tki,j>0},k=1,2, . . . , Q

where T1, T2, . . . , T8—pre-defined masks consisting of ones and zeros as illustrated inFIG. 5. As described above, each mask Tk corresponds to one quantized texture orientation. Note that if one superimposes a template Tk over Fourier transform F and the line comprised of values of “1” in template Tk is coincident with a peak in Fourier transform F, the value of the peak will be multiplied by “1” and will be entered as an array element of Ak. Peaks in Fourier transform F that are not coincident with a value of “1” in template Tk are not entered into Ak.

Next, at step3, a maximum value for each of the plurality of arrays is calculated. Specifically, maximal values for every array Ak are calculated and saved into new array M where:
M={max(A1),max(A2), . . . , max(AQ)}

Note that each value of array M corresponds to a relative prevalence of a peak in Fourier transform F corresponding to the orientation associated with a single template14. Next, array M is sorted into descending order and the permutation indices of the sorted array M are saved:
M={m1,m2, . . . , mQ},m1>m2> . . . >mQ
pInds={pInd1,pInd2, . . . , pIndQ}

An example of the preceding calculation of the permutation indices is as follows Consider an exemplary array M=[5, 10, 4, 6, 3]. When sorted in descending order Msorted=[10, 6, 5, 4, 3]. In this example, pInds=[2, 4, 1, 3, 5]. As is evident, the sorted array M, Msorted,=[M2, M4, M, M3, M5]. As is evident, the permutation indices denote the positions of elements in unsorted array M.

Next, at step4, there is identified each of the plurality of arrays having a calculated maximum value greater than a predetermined threshold. Specifically, a value, nPeaks, is calculated representing the number of peaks in Fourier transform F:

where thr is a pre-defined threshold.

Lastly, at step5, for each of the plurality of arrays identified in step4, the texture orientation of the template utilized to extract the identified one of the plurality of arrays is determined. Specifically, an output array MAP: mappIndi=1, pIndiε{1, 2, . . . , nPeaks} is formed. Note that array MAP is comprised of zero values and a number of “1” values where the number of “1” values is equal to the number of detected peaks. Further, as each element in array MAP corresponds to a template14and a corresponding orientation, it is possible to select any or all of the elements of array MAP having a value of “1” to determine one or more of the orientations of regular textures present in B.

With reference toFIG. 8, there is illustrated a schematic logic diagram of step2through step5described above. With reference toFIGS. 9A-9D, there are illustrated four exemplary regular textures with the computed orientations10superimposed upon the regular textures.

As is evident from the discussion above, the use of templates as described allows for the implementation a low complexity scheme for deriving texture orientations in images. With reference toFIG. 8, each Fourier transform F is parallel processed by a set of templates. Processing includes selecting the elements from the Fourier transform F on non-zero positions of template. Then the maximal value is found in the output of every template (local maximum) and among all the elements (global maximum). For those templates for which the difference between local maximum and global maximum is lower than some pre-defined threshold thr the output is 1. Otherwise the output is 0.

With reference toFIG. 10, there is illustrated a device110for performing the various exemplary embodiments described herein. The device110includes a processor112according to any of the embodiments described herein. For example, the processor112might be comprised of a host processor, a co-processor, and/or a memory unit for storing instructions and/or data required to perform any of the functions described above. In addition to an internal memory, the processor112may additionally be in communication with the memory114comprised of, for example, RAM memory for storing instruction and/or data.

In addition, some embodiments described herein are associated with an “indication”. As used herein, the term “indication” may be used to refer to any indicia and/or other information indicative of or associated with a subject, item, entity, and/or other object and/or idea. As used herein, the phrases “information indicative of” and “indicia” may be used to refer to any information that represents, describes, and/or is otherwise associated with a related entity, subject, or object. Indicia of information may include, for example, a code, a reference, a link, a signal, an identifier, and/or any combination thereof and/or any other informative representation associated with the information. In some embodiments, indicia of information (or indicative of the information) may be or include the information itself and/or any portion or component of the information. In some embodiments, an indication may include a request, a solicitation, a broadcast, and/or any other form of information gathering and/or dissemination.

FIG. 11illustrates an embodiment of a system1100. In embodiments, system1100may be a media system although system1100is not limited to this context. For example, system1100may be incorporated into a personal computer (PC), laptop computer, ultra-laptop computer, tablet, touch pad, portable computer, handheld computer, palmtop computer, personal digital assistant (PDA), cellular telephone, combination cellular telephone/PDA, television, smart device (e.g., smart phone, smart tablet or smart television), mobile internet device (MID), messaging device, data communication device, and so forth.

In embodiments, system1100comprises a platform1102coupled to a display1120. Platform1102may receive content from a content device such as content services device(s)1130or content delivery device(s)1140or other similar content sources. A navigation controller1150comprising one or more navigation features may be used to interact with, for example, platform1102and/or display1120. Each of these components is described in more detail below.

Processor1110may be implemented as Complex Instruction Set Computer (CISC) or Reduced Instruction Set Computer (RISC) processors, x86 instruction set compatible processors, multi-core, or any other microprocessor or central processing unit (CPU). In embodiments, processor1110may comprise dual-core processor(s), dual-core mobile processor(s), and so forth.

Graphics subsystem1115may perform processing of images such as still or video for display. Graphics subsystem1115may be a graphics processing unit (GPU) or a visual processing unit (VPU), for example. An analog or digital interface may be used to communicatively couple graphics subsystem1115and display1120. For example, the interface may be any of a High-Definition Multimedia Interface, DisplayPort, wireless HDMI, and/or wireless HD compliant techniques. Graphics subsystem1115could be integrated into processor1110or chipset1105. Graphics subsystem1115could be a stand-alone card communicatively coupled to chipset1105.

In embodiments, display1120may comprise any television type monitor or display. Display1120may comprise, for example, a computer display screen, touch screen display, video monitor, television-like device, and/or a television. Display1120may be digital and/or analog. In embodiments, display1120may be a holographic display. Also, display1120may be a transparent surface that may receive a visual projection. Such projections may convey various forms of information, images, and/or objects. For example, such projections may be a visual overlay for a mobile augmented reality (MAR) application. Under the control of one or more software applications1116, platform1102may display user interface1122on display1120.

In embodiments, content services device(s)1130may be hosted by any national, international and/or independent service and thus accessible to platform1102via the Internet, for example. Content services device(s)1130may be coupled to platform1102and/or to display1120. Platform1102and/or content services device(s)1130may be coupled to a network1160to communicate (e.g., send and/or receive) media information to and from network1160. Content delivery device(s)1140also may be coupled to platform1102and/or to display1120.

Movements of the navigation features of controller1150may be echoed on a display (e.g., display1120) by movements of a pointer, cursor, focus ring, or other visual indicators displayed on the display. For example, under the control of software applications1116, the navigation features located on navigation controller1150may be mapped to virtual navigation features displayed on user interface1122, for example. In embodiments, controller1150may not be a separate component but integrated into platform1102and/or display1120. Embodiments, however, are not limited to the elements or in the context shown or described herein.

In embodiments, drivers (not shown) may comprise technology to enable users to instantly turn on and off platform1102like a television with the touch of a button after initial boot-up, when enabled, for example. Program logic may allow platform1102to stream content to media adaptors or other content services device(s)1130or content delivery device(s)1140when the platform is turned “off” In addition, chip set1105may comprise hardware and/or software support for 5.1 surround sound audio and/or high definition 11.1 surround sound audio, for example. Drivers may include a graphics driver for integrated graphics platforms. In embodiments, the graphics driver may comprise a peripheral component interconnect (PCI) Express graphics card.

In various embodiments, any one or more of the components shown in system1100may be integrated. For example, platform1102and content services device(s)1130may be integrated, or platform1102and content delivery device(s)1140may be integrated, or platform1102, content services device(s)1130, and content delivery device(s)1140may be integrated, for example. In various embodiments, platform1102and display1120may be an integrated unit. Display1120and content service device(s)1130may be integrated, or display1120and content delivery device(s)1140may be integrated, for example. These examples are not meant to limit the invention.

As described above, system1100may be embodied in varying physical styles or form factors.FIG. 12illustrates embodiments of a small form factor device1200in which system1100may be embodied. In embodiments, for example, device1200may be implemented as a mobile computing device having wireless capabilities. A mobile computing device may refer to any device having a processing system and a mobile power source or supply, such as one or more batteries, for example.

As shown inFIG. 12, device1200may comprise a housing1202, a display1204, an input/output (I/O) device1206, and an antenna1208. Device1200also may comprise navigation features1212. Display1204may comprise any suitable display unit for displaying information appropriate for a mobile computing device. I/O device1206may comprise any suitable I/O device for entering information into a mobile computing device. Examples for I/O device1206may include an alphanumeric keyboard, a numeric keypad, a touch pad, input keys, buttons, switches, rocker switches, microphones, speakers, voice recognition device and software, and so forth. Information also may be entered into device1200by way of microphone. Such information may be digitized by a voice recognition device. The embodiments are not limited in this context.

Various modifications and changes may be made to the foregoing embodiments without departing from the broader spirit and scope set forth in the appended claims. The following illustrates various additional embodiments and do not constitute a definition of all possible embodiments, and those skilled in the art will understand that the present invention is applicable to many other embodiments. Further, although the following embodiments are briefly described for clarity, those skilled in the art will understand how to make any changes, if necessary, to the above-described apparatus and methods to accommodate these and other embodiments and applications.

Although embodiments have been described with respect to particular types of video files, note that embodiments may be associated with other types of information. For example, a digital book or audio file might be associated with a chop file. Moreover, while embodiments have been illustrated using particular ways of selecting a level of detail, note that embodiments might be associated with other ways of determining detail levels (e.g., by automatically detecting that a person is not paying attention to the current level of detail).

Embodiments have been described herein solely for the purpose of illustration. Persons skilled in the art will recognize from this description that embodiments are not limited to those described, but may be practiced with modifications and alterations limited only by the spirit and scope of the appended claims.