I|ll||||||||||||||||||||||||||||||||||||||I
`
`US00?9?4339B2
`
`(12) United States Patent
`
`Krichevsky et al.
`
`(10) Patent No.:
`
`US 7,974,339 B2
`
`(45) Date of Patent:
`
`Jul. 5, 2011
`
`.\=IacI.eod ct al.
`T-"I998
`Ir’.-"1998 Lee
`ll.-‘I998 Nlnisilo
`'
`
`5.-"2000 Duly
`3-""2001 Chiang.
`l2:'200l Nlori ct al.
`
`
`
`53006 Barncsmal‘
`(#2009 Hunter
`
`H 383,239
`345-698
`
`345.5604
`an
`
`345.-1500
`345-‘G98
`345-""695
`
`(54) OPTIMIZED DATA TRANSMISSION SYSTEM
`AND METHOD
`
`(76)
`
`Iiivemorsz Alex Krichevsky. l.aguna Beach. (TA
`(U5); Constance Nash. Laglma 13I-‘aCh-
`CA (US)
`
`( as ) Notice:
`
`Subject to any disclaimer. the term oftlijs
`patent is extended or £l(.l|l]Eslt.!(.l under 35
`U-S-(7 15401) by 1401 d'cI)'==-
`
`5."r‘78.D92 A
`S.?84.l'I'5 A
`5,838,333 A ’l‘
`-9
`..
`6.078.307 A *
`6.198.467 Bl "‘
`6.326.981 Bl "‘
`
`:
`7‘05U‘639 Bl .,
`7.551.139 132*
`
`(21) Appt Nu; 101392590
`
`(22)
`
`Filed:
`
`Jul. 16, 2004
`
`El’
`
`EP
`El’
`
`FORIJIUN PA'l'l_il\l’l‘ DOCUMIJNTS
`0 712 033 A2
`551996
`
`l 006 T15 A2
`l 006 TI’? A2
`
`6-"2000
`6-"3000
`
`(65)
`
`Prior Publication Data
`
`OTHER PUBLICATIONS
`
`Us 2034'IIl02S8l50 A1
`
`Dec‘ 23' 2004
`
`SlIPpl€l‘!‘l€I1THJ'}‘ Etlmpean Search Report. dated %p. 23. 2005.
`
`(63) Continuation of application No. PCTI’US02I’00503_.
`filed on Jan. 15. 2002.
`
`3
`
`_ d b
`we
`
`,
`5’ ‘°”“"“““"’
`
`(51)
`
`Int CL
`IIt'MN 7/12
`375240.01
`(52) U.S. (:1.
`3'I'5I’240.0l,
`(58) Field ofClassificatiun Search
`375,040.15, 240.23; 38054; 382,939, 236;
`348K699
`See application file for complete search history,
`
`(2006.01)
`
`
`
`(56)
`
`References Cited
`
`US. PATENT DOCUMENTS
`4.?'i'(1.013 A ‘‘
`10.51938 Kafrictal.
`4385.349 A *
`ll.-"1988 Keith ctal.
`
`380.-"54
`3T5-‘£40.23
`
`,
`
`Pr.='iImr_i-' E.\'aniiner
`
`TLu1gVo
`1,
`,
`_
`A535 ”’”‘F'
`(57)
`l3m"’1d‘3d- “"3 5Y5l‘3m
`A 5?-‘Wm ml’ l1"dn511“l“11E dam 15
`includes a frame analysis system receiving frznne data. such
`as 21 frame ofvideu data. and generating region data. such as
`at uniform matrix size that is used to divide the frame into a
`redetermined set of matrices. A ixel selection 5 'stem
`P
`_
`_
`P
`_
`3
`receives the region data and generates one set of pixel data for
`each region. such as by selecting one of the pixels contained
`within each of the original matrices that comprise the frame.
`
`13 Claims,4 Drawing Sheets
`
`
`
`DATA TRANSMISSION SYSTEM fl
` PIXEL
`SELECTION
`
`SYSTEM
`1%
`
`
`
`
`
`FRAME
`ANALYSIS
`SYSTEM
`1%
`
`
`
`
`
`DISPLAY
`GENERATION
`svsnan
`M
`
`
`
`
`PIXEL DATA
`SYSTEM
`11_°
`
`
`
`DATA RECEIVING SYSTEM L5
`
`100?
`
`1
`
`Google Inc.
`
`GOOG 1001
`IPR of US Pat. No. 7,974,339
`
`

`
`U.S. Patent
`
`Jul. 5, 2011
`
`Sheetl of4
`
`US 7,974,339 B2
`
`DATA TRANSMISSION SYSTEM 1_O_2_
`
`
`
`FRAME
`
`PIXEL
`
`ANALYSIS
`
`SYSTEM
`
`E‘?
`
`SELECTION
`
`SYSTEM
`
`1%
`
`
`
`
`
`
`
`DISPLAY
`GENERATION
`SYSTEM
`1 1 2
`
`
`
`P';‘$'§f[’Efl‘°‘
`1'19‘
`
`
`
`DATA RECEIVING SYSTEM 133
`
`FIGURE 1
`
`100%
`
`PIXEL
`
`VARIATION
`SYSTEM
`$32
`
`”"‘S1;,':3r‘ESlJ‘ZE
`204
`
`MATRl)(
`
`IDENTIFICATION
`SYSTEM
`
`FRAME ANALYSIS SYSTEM M
`
`

`
`U.S. Patent
`
`Jul. 5, 2011
`
`Sheet 2 of4
`
`US 7,974,339 B2
`
`PIXEL
`RANDOMFZER
`SYSTEM
`302
`
`PIXEL
`SEQUENCER
`SYSTEM
`
`PIXEL
`IDENTIFICATION
`SYSTEM
`
`PIXEL SELECTION SYSTEM 1_c§
`
`DEFINITION
`
`SYSTEM
`
`E
`
`PIXEL LOCATION
`
`SYSTEM
`
`Q
`
`PIXEL DATA SYSTEM 1_1_q
`
`FIGURE 4
`
`wofi
`
`DETERMINE MATRIX SIZE
`
`| 502
`
`I
`
`
`
`504
`
`506
`
`SELECT P%XEL IN MATRIX
`
`
`
`TRANSMIT MATRIX AND PIXEL DATA
`
`
`
`
`FRAME COMPLETE?
`
`GO TO NEXT FRAME
`
`514
`
`
`
`ASSEMBLE MATRIX AND PIXEL DATA INTO FRAME
`
`503
`
`GENERATE DISPLAY USING MATRIX AND PIXEL DATA 510
`
`

`
`U.S. Patent
`
`Jul. 5, 2011
`
`Sheet 3 of4
`
`US 7,974,339 B2
`
`DETERMINE PIXEL VARIATION
`
`VARIATION > TOL?
`
`
`
`
`
`GO TO NEXT PIXEL
`
`MODIFY TOL
`
`608
`
`610
`
`
`
`FIGURE 6
`
`fioofi
`
`
`
`RECEIVE MATRIX DATA
`
`
`
`
`RAN DOM
`RANDOM OR SEQUENCE?
`
`
`SEQUENCE
`
`ASSIGN MATRIX SIZE
`
`
`
`606
`
`702
`
`OBTAIN SEQUENCE DATA
`
`SELECT PIXEL BASED on
`SEQUENCE DATA
`
`ms
`
`703
`
`7oofi
`
` GENERATE RANDOM NUMBER
`710
`
`
`
`
`
`SELECT PIXEL BASED on
`RANDOM NUMBER
`
`712
`neuae 7
`
`802
`
`§
`
`
`
`
`
`RECEIVE MATRIX AND PIXEL DATA
`
`COMBINE MATRIX. PIXEL DATA INTO FRAME DATA
`
`
`
`FRAME COMPLETE?
`
`
`
`FIGURE 3
`800?
`
`GO TO NEXT FRAME
`
`
`
`303
`
`806
`
`

`
`

`
`US 7,974,339 B2
`
`1
`OPTIMIZED DATA TRANSMISSION SYSTEM
`AND METHOD
`
`FIELD OF THE INVENTION
`
`The present invention pertains to the field of data tra11s1nis—
`sion. and 111ore particularly to a system and method for opti-
`mizing data transmission that decreases bandwidth require-
`ments for data transmission.
`
`BACKGROUND OF THE INVENTION
`
`Data transmission systems are known in the art. Such data
`transmission systems often use compression to decrease
`bandwidth requirements. For example, compression tech-
`niques have been characterized as “lossless" when no redttc-
`tion in data occurs. or “lossy" when a loss ofdata occurs that
`does not adversely affect the intended use.
`One drawback with such data transmission systems is that
`the compressed data must be “decompressed” on the receiv-
`ing end. Thus. for lossless data compression systems, the
`exact configuration of the data must be achieved when the
`data is decompressed. Likewise. even for lossy data compres-
`sion systems, the data is decompressed and the lost data is
`then approximated. The need for such decompression con-
`tributes to the overall difficulty in implementing data trans-
`mission in conjunction with compression.
`
`SUMMARY OF THE INVENTION
`
`In accordance with the present invention, a system and
`method for transmitting data are provided that overcome
`known problems with data transmission systems and meth-
`ods.
`
`In particular. a system and method fordata transmission are
`provided that use data optimization instead of compression,
`so as to provide a mixed lossless a11d lossy data transmission
`technique.
`I11 accordance with an exemplary embodiment of the
`present invention. a system for transmitting data is provided.
`The system includes a frame analysis system receiving frame
`data. such as a frame ofvideo data. audio data, graphical data,
`text data. or other suitable data. and generating region data_.
`such as a uniform matrix size that is used to divide the frame
`
`into a predetermined set ofmatrices. A pixel selection system
`receives the region data and generates one set ofpixel data for
`each region. such as by selecting one of the pixels contained
`within each of the original matrices that comprise the frame.
`For data that is used for purposes other than the generation of
`a display. the pixel data can instead be audio data. text data. or
`other suitable data.
`
`The present invention provides many important technical
`advantages. One important teclmical advantage of the present
`invention is a system and method for transmitting data that do
`not require the data to be compressed at the sending end and
`dccomprcsscd at the receiving end. The present invention
`uses data optimization to transmit only the data that is neces-
`sary for the application. such that decompression of the data
`on the receiving end is not required. In this manner. the
`present invention incorporates features of both lossless and
`lossy compression without requiring the data to be decom-
`pressed on the receiving end.
`Those skilled iii the art will further appreciate the advan-
`tages and superior features of the invention together with
`other important aspects thereof on reading the detailed
`description that follows in conjunction with the drawings.
`
`10
`
`15
`
`30
`
`35
`
`4U
`
`55
`
`60
`
`2
`BRIEF DESCRIPTION OF TIIF, DRAWINGS
`
`I-‘IG. l is a diagram of a system for transmitting data in
`accordance with an exemplary embodiment of the present
`invention:
`
`FIG. 2 is a diagram of a system for perzlomting frame
`analysis in accordance with an exemplary embodiment of the
`present invention;
`FIG. 3 is a diagram of a system for selecting optimized
`pixel data for transmission in accordance with an exemplary
`embodiment of the present invention;
`FIG. 4 is a diagram of a system for generating a frame in
`accordance with an exentplary embodiment of the present
`invention;
`FIG. 5 is a flow chart of a method for optimizing data
`transmission in accordance with an exemplary embodiment
`of the present invention:
`FIG. 6 is a flowchart ofa method for detemtining or assign-
`ing matrix or region size based on alt exemplary embodiment
`of the present invention:
`FIG. 7 is a flowchart ofa method for selecting a pixel within
`a region in accordance with an exemplary embodiment of the
`present invention:
`FIG. 8 is a flowchart for method for generating optimized
`frame data in accordance with an exemplary embodiment of
`the present invention:
`FIG. 9 is a diagram 900 showing an exemplary ttnifomt
`matrix segmentation of an array of pixel data; and
`FIG. 10 is a diag.ram 1000 showing an exemplary non-
`uniform matrix segmentation of an array of pixel data.
`
`DETAILED DESCRIPTION OF PREFERRED
`EMBODIMENTS
`
`like pans are marked
`]n the description that follows,
`throughout the specification and drawings with the saute ref-
`erence ntunerals, respectively. The drawing figures might not
`be to scale, and certain components can be shown i11 gener-
`alized or schematic form and identified by commercial des-
`ignations in the interest of clarity and conciseness.
`FIG. 1 is a diagram ofa system 100 fortransmitting data in
`accordance with an exemplary embodiment of the present
`invention. System 100 allows data such as video data to be
`transmitted in a manner that does not require the data to be
`compressed. and which results in significant decreases in
`bandwidth requirements for data transmission.
`System 100 includes data transmission system 102. which
`is coupled to data receiving system 104 over a suitable com-
`munications medium 114. As used herein, the term “couple"
`and its cognate terms, such as “couples" and “couple ," can
`include a physical connection (such as a copper conductor), a
`virtual connection (such as through randomly assigned
`memory locations ofa data memory device). a logical con-
`nection (such as through logical gates of a semiconducting
`device). other suitable comtections, or a suitable combination
`ofsuch connections. In one exemplary emhodintent, systems
`and components are coupled to other systems and compo-
`nents through intervening systems and components, such as
`through an operating system of a general purpose computing
`platform. Communications medium 114 can be the Internet,
`the public switched telephone network, a wireless network. a
`local area network, an optical network, other suitable com-
`munications media. or a suitable combination of such com-
`munications media.
`
`Data transmission system 102 includes frame analysis sys-
`tem l(]6 and pixel selection system 108. each of which can be
`implemented in hardware, software, or a suitable combina-
`
`

`
`US 7,974,339 B2
`
`3
`tion ofhardware and software, and which can be one or more
`software systems operating on a general purpose processing
`platforr11..f\s used herein. a software system can include one
`or more objects, agents, threads, lines of code, subroutines.
`separate software applications. user-readable (source) code,
`nrachine—readable (object) code, two or rrrore lines of code in
`two or more corresponding software applications, databases,
`or other suitable soiiware architectures. In one exemplary
`embodiment. a software system can include one or tnore lines
`ofcode in a general purpose software application. such as an
`operating system, and one or more lines of software in a
`specific purpose software application.
`Data transmission system 102 reduces data transmission
`requirements by eliminating data that is not required for the
`application of the data on the receiving end. In one exemplary
`embodiment. data transmission system 102 can receive
`frames of video data. and can select pixels of data for trans-
`mission that are needed in order to allow the frames of video
`
`111 this exetrrplary
`data to be viewed by the human eye.
`embodiment, a video display having a quiescent state ofpix—
`els in either the “on" or “ofi"" states can be used to generate
`video data by selecting a subset of pixels within the frame to
`display image data. In this exemplary embodiment, ifa frame
`of video data has low detail,
`it may only be necessary to
`provide a data value for one of every twenty—five pixels or less
`in order to create the image to be viewed by the human eye.
`l.ike'w‘ise_. if the frame of video data has a large amount of
`detail, it may be necessary to transmit each pixel in order to
`generate a suitable image. When a frame of video data
`includes regions ofhigit detail and low detail. it may likewise
`be desirable to transmit only the necessary number of pixels
`in each region that are required to generate the image. In this
`exemplary embodiment. the number ofpixels to transmit can
`be decided on a region-by-region basis within the frame.
`Data receiving system 104 includes pixel data system 110
`and display generation system 112, each of which can be
`implemented in hardware. software, or a suitable combina-
`tion ofhardware and software, and which can be one or more
`software systems operating on a general purpose processor
`platform. Data receiving system 104 receives the data from
`data transmission system 102. and generates a display for a
`user that utilizes the optimized data set transmitted by data
`transmission system 102. In one exemplary embodiment,
`data receiving system 104 can generate a video display, such
`as by illuminating predetermined pixels within a frame based
`on the determination of the level of detail required for the
`frame, and by leaving the remaining pixels in a quiescent state
`of either “off” or “on." Likewise. data receiving system 104
`can generate frames of video data that have variable levels of
`detail, to accommodate the image data being transmitted.
`Frame analysis system 106 receives frame data including
`pixel data and generates matrix size data based upon the pixel
`data. In one exemplary embodiment. frame analysis system
`106 can analyze adjacent pixel data valttes in the frame. and
`can apply one or more predetermined variation tolerances to
`select a matrix size for a data optimization region.
`I11 this
`exemplary embodiment, the matrix size for each data optimi-
`zation region ofa frame can be ttn.iform. such that each data
`optimization matrix has the same dimensions. Thtts. if a 640x
`480 pixel frame is being transmitted, then the 640x480 pixel
`frame can be split up into a 64x48 frame of matrices. where
`each matrix is a 10x10 matrix. likewise, frame analysis sys-
`tem 106 can assign a different matrix size on a frame by frame
`basis, such as where a first frame is transmitted using 10x10
`matrices for a 64x48 matrix frame. and a subseqttent frame
`could then be transmitted using SXS data matrices. for a
`128x96 matrix frame. In another exemplary embodiment, the
`
`10
`
`15
`
`30
`
`35
`
`4U
`
`55
`
`60
`
`4
`size of matrices within the frame can be varied. such that a
`given frame is made up of matrices varying in size, such as
`from a 1x1 matrix to a 5x5 matrix or greater. In yet another
`exemplary embodiment. the size of the matrices can be tron-
`symmctrical, such that an NXM matrix can be used where N
`and M are integer values that are not equivalent. Likewise,
`other suitable data optimization regions can be selected, such
`as ones that are not based on a matrix structure. bttt which may
`be circular, elliptical, amorphous, or based on other suitable
`structures.
`
`Pixel selection system 108 selects one or tttore pixel within
`a predefmed matrix or other region for transmission in an
`optimized data transmission system.
`In one exemplary
`embodiment. pixel selection system 108 can randomly select
`a pixel from a location within a matrix or other region. can use
`a sequence selection scheme such that the pixel is selected in
`accordance with a predetermined sequence, or other suitable
`selection criteria can be used. Pixel selection system 108 can
`further generate pixel location data within the matrix, such
`that the pixel can be regenerated at a predetermined location.
`at a random location. or in other suitable manners. For
`example, if a predetermined location is used, the predeter-
`mined loeatiort can be the same for each matrix or other
`
`region, such as by assigning a quadrant or other location (eg,
`the first row and colunm position in the matrix). Likewise, if
`randomi‘/ation is ttsed, control data can be generated that will
`cause data receiving system 104 to randomize the location of
`each pixel in each matrix or other region withottt requiring
`individual control data for each matrix or other region. like-
`wise, other suitable pixel selection data can be generated.
`Pixel data system 110 receives matrix data and pixel data
`and assembles frame data based on the matrix data and pixel
`data. In one exemplary embodiment. pixel data system 110
`receives a matrix size identifier for an entire frame. such that
`it catt be determined that a uniform matrix size is used for
`each frame. Likewise, pixel data system I 10 can receive
`matrix map data, sttch that a sequence of matrices and the size
`of each matrix can be detemrined. Likewise. pixel data sys-
`tem 110 can receive pixel data for each matrix, such as pixel
`data with each matrix identifier. pixel data in a predetermined
`order based on the order of matrix data transmitted. or other
`suitable data.
`
`Display generation system 112 receives frames of data
`from pixel data system 110 and generates video data. audio
`data, graphical data, textual data, or other suitable data for use
`by a user. I11 one exemplary embodiment, display generation
`system 112 receives an entire frame of data afier it has been
`reconstructed by pixel data system 110. In another exemplary
`embodiment, display generation system 112 can receive
`frame data as it is generated by pixel data systetrr 110 prior to
`the generation of the entire frame. Other suitable configura-
`tions can be used.
`
`In operation, system 100 allows data transmission to be
`optimized so as to decrease bandwidth requirements. System
`100 determines the optimal data for transmission based on the
`end use of the data. For example. system 100 call reduce the
`data transmitted for video display generation, such as by
`determining the level ofdetail required. and then transmitting
`data based on the level of detail required. Likewise, similar
`optimization processes can be used for audio data. graphical
`data. textual data, or other suitable data. Thus, system 100 is
`a lossy data transmission system, but can also be a lossless
`data transmission system depending on the data fields within
`a set of data for which lossy or lossless data transmission is
`desired. 111 this exemplary embodiment. system 100 allows
`data sets to be processed iii a manner that allows data trans-
`
`

`
`US 7,974,339 B2
`
`5
`mission to be both lossless and lossy based on application
`criteria for the data on the receiving end.
`System 100 can also be used in conjunction witl1 a com-
`pression system. a frame elimination system, or with other
`suitable systems or processes to achieve further savings in
`bandwidth requirements. For example, after data optimiza-
`tion has been achieved, the optimized data can then be com-
`pressed using a lossy or lossless compression tecluiique.
`Likewise, frame elimination can be ttsed where such tech-
`niques do 11ot result in an unacceptable decrease in the quality
`of the data at the receiving end.
`FIG. 2 is a diagram ofa system 200 for performing frame
`analysis in accordance with an exemplary embodiment ofthe
`present invention. System 200 includes frame analysis sys-
`tem 106 and pixel variation system 202. matrix size system
`204, and matrix identification system 206, each of which can
`be implemented in hardware. software, or a suitable combi-
`nation of hardware and software. and which can be one or
`more software syste111s operating on a general purpose pro-
`cessing platform.
`Pixel variation system 202 determines the level of detail
`required based on variations in pixel data. In one exemplary
`embodiment. pixel variation system 202 can receive pixel
`data values, such as (xlyfz} in a suitable pixel color pixel
`system (e.g., 16-bit values for RJGIB, Yi'(".bi’Cr. Yi'Ui'\-", or
`other suitable color data formats). Pixel variation system 202
`can then compare two adjacent pixels to determine whether
`the amount of variation between those two adjacent pixels
`exceeds a predetermined tolerance. such that the amount of
`pixel data required to transmit image data or other suitable
`data for perception by a human eye or other suitable applica-
`tions can be determined. In this exemplary embodiment, pixel
`variation system 202 can have a number oftolerance settings,
`so that a matrix size, region, or otherdata optimiration set can
`be determined. For example, consider the following pixel set:
`Pl(l2lt34fl87] P2(l l9i’39i’l98) P3(l 171421202)
`In this example, the variation between P] and P2 may be
`lower than a first tolerance for the purposes ofselecting a first
`data set, such as a 2x2 matrix. but the variation between P1
`and P3 may be greater than a second tolerance for the purpose
`of selecting a second data set. such as a 3x3 matrix. In this
`mamier. increasing groups of pixels can be analyzed so as to
`insure that desired levels ofdelail are not inadvertently omit-
`ted. For example, ifvideo data includes an image ofan essen-
`tially uniform object, such as the ocean or a grassy field, and
`where that essentially uniform object has details that are
`nonetheless of interest to the viewer. such as wave whitecaps
`or wildflowers, pixel variation system 202 can include toler-
`ance settings such that variations between pixels that identify
`such details would be identified, but where such variations
`between two adjacent pixels within the field would be
`ignored. Likewisc_. other suitable pixel variation detection
`functionality can be provided.
`Matrix size system 204 generates matrix size data based on
`pixel variation data. In one exemplary embodiment. matrix
`size system 204 can receive pixel variation data based on an
`analysis of an entire frame of data, such that a uniform matrix
`size can be assigned. Likewise, matrix size system 204 can
`receive pixel variation data from pixel variation system 202.
`and can generate nonsymmetrical matrix dimensional data,
`such as l\l><M dimensions where “N" and “M" are integers
`that are not equivalent. circular region data, elliptical region
`data. amorphous region data, or other suitable region identi-
`fication data. Matrix si‘/ie system 204 can also generate matrix
`size control data. such as where a non-unifomi matrix or
`region size is used within a frame. 111 this exemplary e111bodi-
`ment, matrix size system 204 can identify a sequence for
`
`10
`
`15
`
`30
`
`35
`
`4-0
`
`55
`
`60
`
`6
`matrices, coordinate data for matrices, size data for matrices,
`or other suitable data that can be used to assemble or sequence
`pixel data within matrices.
`Matrix identification system 206 receives matrix size data
`and generates matrix identification data. In one exemplary
`embodiment, matrix identification system 206 can receive
`matrix sequence data, and can assemble the matrix sequence
`data for use with pixel data generated by pixel selection
`system 108. In this exemplary embodiment. matrix identifi-
`cation system 206 can identify whether a uniform matrix size
`is being generated, the number of matrices within a frame,
`sequence data for the matrices when a non-tiniform matrix or
`region is being used. or other suitable data. Matrix identifi-
`cation system 206 generates matrix identification data for use
`by data receiving system 104. so as to allow data receiving
`system 104 to generate the optimized data display.
`In operation. system 200 allows frames to be analyzed so as
`to determine the optimal data to be transmitted. based on the
`intended use of the frame. In one exemplary enibodiment,
`pixel variation system 202 or other suitable systems can be
`used to identify lossy and lossless regions within the frame.
`Likewise, unifonn lossy regions can be identified, such as
`matrices having predetermined dimensions of greater than
`1x1 or other suitable data.
`
`FIG. 3 is a diagram ofa system 300 for selecting optimized
`pixel data for transmission in accordance with an exemplary
`embodiment of the present invention. System 300 includes
`pixel selection system 108 and pixel randomizer system 302.
`pixel sequencer system 304. and pixel identification system
`306. each of which can be implemented in hardware. soft-
`ware, or a suitable combination of hardware and software,
`and which can be one or more software systems operating on
`a general purpose processor platform.
`Pixel randomize-r system 3 02 selects a random pixel within
`a matrix or other region. In one exemplary embodiment, pixel
`randomizer system 302 can generate a random number and
`can select a pixel based upon a pixel sequence and the rela-
`tionship of the generated random number to that pixel
`sequence. I11 this exemplary embodiment. pixel randomizer
`system 302 can generate a random number between 0 and I.
`and can multiply that random number times the number of
`pixels within a region. and can then select the pixel based
`ttpon a pixel sequence from a predetermined location. Like-
`wise. other suitable random pixel selection processes can be
`used. Pixel randomizer system 302 generates random pixel
`location data and random pixel value data.
`Pixel sequencer system 304 generates pixel selection data
`based on pixel sequence data. In one exemplary embodiment,
`such as when a uniform frame matrix size is being used, pixel
`sequencer system 304 can select pixels in a predetermined
`order. such that if a 3x3 matrix is used uniformly across the
`frame. the pixel at location (l,l) is transmitted in the first
`frame. the pixel at location (1.2) is transmitted in the second
`frame. the pixel at location (1.3) is transmitted in the third
`frame. and so forth, until the pixel at location (3,3) has been
`transmitted, after which the pixel at location (1.1) will be
`transmitted. Pixel sequencer system 304 can likewise send
`other suitable sequences, such as skipping every other pixel.
`skipping pixels based on predetennined display generation
`characteristics, or other suitable sequences.
`Pixel identification system 306 generates pixel identifica-
`tion data. such as may be required by a data receiving system
`to illuminate the pixel in a display. In one exemplary en1bodi—
`ment, pixel identification system 306 can identify the coordi-
`nates of a pixel where generation of the pixel by the data
`receiving system at the exact location is desired. Likewise,
`pixel identification system 306 can identify a uniform pixel
`
`

`
`US 7,974,339 B2
`
`7
`location within each matrix or other region, strch as location
`(1, 1) tor all matrices. such as randomizer control data that will
`randomly place a pixel within a matrix or region. or other
`suitable pixel identification data.
`In operation. system 300 allows a pixel within a 111atrix or
`other suitable region to be selected based on data optimiza-
`tion. System 300 allows random, sequenced, or other suitable
`processes to be used to select and locate pixels within opti-
`miaed regions.
`FIG. 4 is a diagram ofa system 400 for generating a frame
`in accordance with an exemplary embodiment of the present
`invention. System 400 includes pixel data system 1 10, matrix
`definition system 402 and pixel location system 404. each of
`which cart be implemented in hardware, software, or a s1tit—
`able combination ofhardware and software, and which can be
`one or more software systems operating on a general purpose
`processor platform.
`Matrix definition system 402 receives matrix definition
`data for use i11 generating frame data. In one exemplary
`embodiment, matrix definition data can include data that
`identifies a uniform matrix size throughout the frame. In
`another exemplary embodiment. matrix definition data can
`include data that identifies matrix dimensions and sequences,
`so that a sequence of non-similar matrices can be assembled
`into a frame. Likewise, matrix definition system 402 can
`include region definition data, such as for ellipses, circles.
`amorphous shapes. or other suitable definition data.
`Pixel location system 404 receives pixel location data for
`locating a pixel within a matrix or other region. In one exem-
`plary embodiment. pixel location system 404 cart receive data
`that locates pixels for each matrix within a frame on a uniform
`basis. such that each pixel received will be generated in a
`predetermined location (e.g. (1,1) ina 3x3 matrix). Likewise,
`pixel location system 404 can receive randoniization data.
`such that the location ofa pixel within a matrix or other region
`is randomly assigned. In yet another exemplary embodiment.
`pixel location system 404 can receive exact coordinates for
`placement of pixels. Other suitable processes can be imple-
`mented by pixel location system 404.
`I11 operation, system 400 is used to locate pixels of data
`within a matrix or other region in an optimized data transrnis-
`sion system. System 400 thus allows optimized data. such as
`video data, audio data, or other suitable data, to be used to
`generate a display, an audio stream, gaphic images. textual
`data, and other suitable data on a frame by frame basis.
`FIG. 5 is a flow chart ofa method 500 for optimizing data
`transmission in accordance with an exemplary embodiment
`of the present invention. Method 500 begins at 502 where a
`matrix size is determined. In one exemplary embodiment, the
`matrix size can be unilorrnly assigned across the frame, a
`matrix size can assigned based upon regions within the frame,
`a region other than a matrix can be used, or other suitable
`matrix sizes or region sizes can be determined. The method
`then proceeds to 504.
`At 504 a pixel within the matrix is selected. In one exem-
`plary embodiment, the pixel can be selected based on a pre-
`determined location within tl1e matrix, such as wl1e11 uniform
`matrix sizes are used within a frame, or in other suitable
`mamiers. I11 another exemplary embodiment. pixel selection
`can be performed based on random selection, based upon
`predetermined rules regarding selection of pixels. or in other
`suitable mamiers. The method then proceeds to 506.
`At 506 the matrix and pixel data is transmitted. In one
`exemplary embodiment. the matrix and pixel data can be
`transmitted in pairs, such that each set of matrix definition
`data or location data is paired with corresponding pixel
`brightness data. Likewise, matrix data and pixel data can be
`
`10
`
`15
`
`30
`
`35
`
`4U
`
`55
`
`60
`
`8
`transmitted in sequence. such that the sequence ofmatrix data
`is received first. and the sequence of pixel data for each
`corresponding matrix is then received. Other suitable trans-
`mission sequences can likewise be trsed. The method then
`proceeds to 508.
`At 508 the matrix and pixel data is assembled into a frame.
`In one exemplary embodiment, the frame assembly cart be
`performed on a line—by—line basis. such that each line of data
`can be generated as it
`is created. In another exemplary
`embodiment. an entire liame ofdata can be generated prior to
`utilization of the frame of data. The method then proceeds to
`510.
`
`At 510 a display is generated using the matrix and pixel
`data. As previously described, the display can be generated
`from an entire frame data set after it has been completed.
`Likewise, the display can be generated on a line-by-line basis.
`audio streams or graphical displays can be generated. or other
`suitable displays can be generated. The method then proceeds
`to 512.
`
`At 512 it is determined whether a frame is completed. Ifthe
`frame is not completed the method returns to 508. Otherwise
`the frame is complete, the method proceeds to 514 and the
`method proceeds to the next trame.
`FIG. 6 is a flowchart of a method 600 for determining or
`assigning matrix or region size based on an exemplary
`embodiment of the present invention. Method 600 begins at
`602 where a pixel variation is determined. In one exemplary
`embodiment. the pixel data values for two adjacent pixels can
`be compared. and it can be determined whether the variations
`between the two adjacent pixel data values exceed predeter-
`mined allowable variations. The suitable variation techniques
`can be implemented. The method then proceeds to 604.
`At 604 it is determined whether the variation is greater than
`a predetermined tolerance. If it is determined at 604 that the
`variation is greater than the tolerance the method proceeds to
`606 where the matrix size is assigned based on the number of
`pixels under consideration. In one exemplary embodiment, if
`a first and second pixel have been compared and it is deter-
`mined that the variation between pixels exceeds the tolerance,
`then a matrix size of lxl (i.e.. an individual pixel ). can be
`transmitted such that data transmission is lossless. If it is
`
`determined that the variation is not greater than the tolerance,
`the method proceeds to 608.
`is selected. In one exemplary
`At 608,
`the next pixel
`embodiment, the next pixel can be selected based upon an
`N><N matrix size. an N><M matrix size. a circular region size